第10章 多處理器和實(shí)時調(diào)度

1、第10章 多處理器和實(shí)時調(diào)度 主要內(nèi)容 10.1 多處理器調(diào)度 10.2 實(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)分類 松耦合、分布式多處理器、集群 由一系列相對自治的系統(tǒng)組成，每個處理器有自己的內(nèi)存和I/O通道。 專門功能的處理器 有一個通用的主處理器，專用處理器受主處理器的控制，并給主處理器提供服務(wù)。 緊耦合多處理 由一系列共享同一個內(nèi)存并在操作系統(tǒng)完全控制下的處理器組成。210.1.1 粒

2、度 同步粒度和進(jìn)程粒度大小粒度大小說明說明同步間隔同步間隔細(xì)細(xì)單指令流中固有的并行單指令流中固有的并行2020中等中等在一個單獨(dú)應(yīng)用中的并行處理或多任在一個單獨(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)行分布處理，以形成一個計(jì)算環(huán)境一個計(jì)算環(huán)境20001M20001M無約束無約束多個無關(guān)進(jìn)程多個無關(guān)進(jìn)程不適用不適用310.1.2 設(shè)計(jì)問題 把進(jìn)程分配到處理器 靜態(tài)分配、動態(tài)分配 主從式、對等式 在單個處理器上使用多道程序設(shè)計(jì) 傳統(tǒng)

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

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

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

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

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