1、第10章 多處理器和實(shí)時(shí)調(diào)度 主要內(nèi)容 10.1 多處理器調(diào)度 10.2 實(shí)時(shí)調(diào)度 10.3 Linux調(diào)度（自學(xué)） 10.4 UNIX SVR4調(diào)度（自學(xué)） 10.5 FreeBSD調(diào)度器（自學(xué)） 10.6 Windows調(diào)度（自學(xué)） 10.7 Linux虛擬機(jī)進(jìn)程調(diào)度（自學(xué)）110.1 多處理器調(diào)度多處理器系統(tǒng)分類(lèi) 松耦合、分布式多處理器、集群 由一系列相對(duì)自治的系統(tǒng)組成，每個(gè)處理器有自己的內(nèi)存和I/O通道。 專(zhuān)門(mén)功能的處理器 有一個(gè)通用的主處理器，專(zhuān)用處理器受主處理器的控制，并給主處理器提供服務(wù)。 緊耦合多處理 由一系列共享同一個(gè)內(nèi)存并在操作系統(tǒng)完全控制下的處理器組成。210.1.1 粒

2、度 同步粒度和進(jìn)程粒度大小粒度大小說(shuō)明說(shuō)明同步間隔同步間隔細(xì)細(xì)單指令流中固有的并行單指令流中固有的并行2020中等中等在一個(gè)單獨(dú)應(yīng)用中的并行處理或多任在一個(gè)單獨(dú)應(yīng)用中的并行處理或多任務(wù)處理務(wù)處理2020020200粗粗在多道程序環(huán)境中并發(fā)進(jìn)程的多處理在多道程序環(huán)境中并發(fā)進(jìn)程的多處理20020002002000非常粗非常粗在網(wǎng)絡(luò)節(jié)點(diǎn)上進(jìn)行分布處理，以形成在網(wǎng)絡(luò)節(jié)點(diǎn)上進(jìn)行分布處理，以形成一個(gè)計(jì)算環(huán)境一個(gè)計(jì)算環(huán)境20001M20001M無(wú)約束無(wú)約束多個(gè)無(wú)關(guān)進(jìn)程多個(gè)無(wú)關(guān)進(jìn)程不適用不適用310.1.2 設(shè)計(jì)問(wèn)題 把進(jìn)程分配到處理器 靜態(tài)分配、動(dòng)態(tài)分配 主從式、對(duì)等式 在單個(gè)處理器上使用多道程序設(shè)計(jì) 傳統(tǒng)

3、多處理器處理粗粒度或無(wú)約束同步粒度，單處理器使用多道程序設(shè)計(jì)。 運(yùn)行在多處理器系統(tǒng)中的中等粒度應(yīng)用程序，更加關(guān)注如何能為應(yīng)用提供更好的平均性能，單個(gè)處理器是否多道并不重要。 一個(gè)進(jìn)程的實(shí)際分派 使用簡(jiǎn)單的調(diào)度方法會(huì)更有效，降低開(kāi)銷(xiāo)410.1.3 進(jìn)程調(diào)度 多處理器情況下，調(diào)度原則的選擇沒(méi)有在單處理器中顯得重要。 多處理系統(tǒng)中一般使用簡(jiǎn)單的FCFS或者在靜態(tài)優(yōu)先級(jí)方案中使用FCFS。56710.1.4 線程調(diào)度 負(fù)載分配 系統(tǒng)維護(hù)一個(gè)就緒線程的全局隊(duì)列，每個(gè)處理器只要空閑就從隊(duì)列中選擇一個(gè)線程。 組調(diào)度 一組相關(guān)的線程基于一對(duì)一的原則，同時(shí)調(diào)度到一組處理器上運(yùn)行。 專(zhuān)用處理器調(diào)度 組調(diào)度的一種極

4、端形式，在一個(gè)應(yīng)用程序執(zhí)行期間，把一組處理器專(zhuān)門(mén)分配給這個(gè)應(yīng)用程序。 動(dòng)態(tài)調(diào)度 某些應(yīng)用程序允許動(dòng)態(tài)地改變進(jìn)程中線程數(shù)目，需要?jiǎng)討B(tài)調(diào)度。操作系統(tǒng)負(fù)責(zé)分配處理器給作業(yè)，作業(yè)自行調(diào)度。810.2 實(shí)時(shí)調(diào)度10.2.1 背景 實(shí)時(shí)計(jì)算 系統(tǒng)的正確性不僅取決于計(jì)算的邏輯結(jié)果，還依賴(lài)于產(chǎn)生結(jié)果的時(shí)間。 實(shí)時(shí)任務(wù) 硬實(shí)時(shí)任務(wù)、軟實(shí)時(shí)任務(wù) 周期性任務(wù)、非周期性任務(wù) 實(shí)時(shí)系統(tǒng)應(yīng)用的例子 目前：實(shí)驗(yàn)控制、過(guò)程控制、機(jī)器人、空中交通管制、電信、軍事指揮與控制系統(tǒng)。 下一代：自動(dòng)駕駛汽車(chē)、具有彈性關(guān)節(jié)的機(jī)器人控制器、智能化生產(chǎn)中的系統(tǒng)查找、空間站和海底勘探。910.2.2 實(shí)時(shí)操作系統(tǒng)的特點(diǎn)要求 可確定性 按照固定

5、的、預(yù)先確定的時(shí)間或時(shí)間間隔執(zhí)行操作。 可響應(yīng)性 為中斷提供服務(wù)的時(shí)間。 用戶(hù)控制 允許用戶(hù)細(xì)粒度地控制任務(wù)優(yōu)先級(jí)，指定一些特性等。 可靠性 性能的損失或降低可能產(chǎn)生災(zāi)難性的后果。 故障弱化操作 系統(tǒng)在故障時(shí)盡可能多地保存其性能和數(shù)據(jù)的能力。10特征 快速的進(jìn)程或線程切換。 體積?。ㄖ痪邆渥钚∠薅鹊墓δ埽?。 迅速響應(yīng)外部中斷的能力。 通過(guò)諸如信號(hào)量、信號(hào)和時(shí)間之類(lèi)的進(jìn)程間通信工具，實(shí)現(xiàn)多任務(wù)處理。 使用特殊的順序文件，可以快速存儲(chǔ)數(shù)據(jù)。 基于優(yōu)先級(jí)的搶占式調(diào)度。 最小化禁止中斷的時(shí)間間隔。 用于使任務(wù)延遲一段固定的時(shí)間或暫停/恢復(fù)任務(wù)的原語(yǔ)。 特別的警報(bào)和超時(shí)設(shè)定。1110.2.3 實(shí)時(shí)調(diào)度考

6、慮的問(wèn)題 一個(gè)系統(tǒng)是否執(zhí)行可調(diào)度性分析； 如果執(zhí)行，是靜態(tài)的還是動(dòng)態(tài)的； 分析結(jié)果自身是否根據(jù)在運(yùn)行時(shí)分派的任務(wù)產(chǎn)生一個(gè)調(diào)度或計(jì)劃。12調(diào)度算法 靜態(tài)表法 執(zhí)行關(guān)于可行調(diào)度的靜態(tài)分析。分析的結(jié)果是一個(gè)調(diào)度，它用于確定在運(yùn)行時(shí)一個(gè)任務(wù)何時(shí)必須開(kāi)始執(zhí)行。 靜態(tài)優(yōu)先級(jí)搶占法 執(zhí)行一個(gè)靜態(tài)分析，但是沒(méi)有制定調(diào)度，通過(guò)給任務(wù)制定優(yōu)先級(jí)，使用傳統(tǒng)的基于優(yōu)先級(jí)的搶占式調(diào)度。 基于動(dòng)態(tài)規(guī)劃調(diào)度法 在運(yùn)行時(shí)動(dòng)態(tài)地確定可行性，可行性分析的結(jié)果是一個(gè)調(diào)度或規(guī)劃，可用于確定何時(shí)分派這個(gè)任務(wù)。 動(dòng)態(tài)盡力調(diào)度法 不執(zhí)行可行性分析。系統(tǒng)試圖滿(mǎn)足所有的最后期限，并終止任何已經(jīng)開(kāi)始運(yùn)行但錯(cuò)過(guò)最后期限的進(jìn)程。1310.2.4 限

7、期調(diào)度 實(shí)時(shí)應(yīng)用程序通常并不關(guān)注絕對(duì)速度，它關(guān)注的是在最有價(jià)值的時(shí)間完成（或啟動(dòng)）任務(wù)。 限期調(diào)度：最早最后期限優(yōu)先。 最后期限 啟動(dòng)最后期限：任務(wù)必須開(kāi)始的時(shí)間。 完成最后期限：任務(wù)必須完成的時(shí)間。14例1：具有完成最后期限的周期性任務(wù)調(diào)度1516例2：具有啟動(dòng)最后期限的非周期性任務(wù)調(diào)度171810.2.5 速率單調(diào)調(diào)度（RMS） 適應(yīng)于周期性任務(wù)調(diào)度，最短周期的任務(wù)具有最高優(yōu)先級(jí)，次短周期的任務(wù)具有次高的優(yōu)先級(jí)，以此類(lèi)推。 當(dāng)同時(shí)有多個(gè)任務(wù)可以被執(zhí)行時(shí)，最短周期的任務(wù)被優(yōu)先執(zhí)行。 衡量周期調(diào)度算法有效性的標(biāo)準(zhǔn)：是否能夠保證滿(mǎn)足所有硬最后期限，對(duì)于RMS，須滿(mǎn)足： C1/T1+C2/T2+Cn/Tnn(21/n-1)19例 任務(wù)P1：C1=20;T1=100;U1=0.2 任務(wù)P2：C2=40;T2=150;U2=0.267 任務(wù)P3：C3=100;T3=350;U3=0.286 三個(gè)任務(wù)的總利用率為0.2+0.267+0.286=0.753,使用RMS，三個(gè)任務(wù)的可調(diào)度性上界根據(jù)公式計(jì)算為0.779,0.7530.779，故所有的任務(wù)可以成功得到調(diào)度。2010.2.6 優(yōu)先級(jí)反轉(zhuǎn) 在任何優(yōu)先級(jí)調(diào)度方案中，