【正文】 權(quán)優(yōu)先(FPF)調(diào)度算法和搶占式最高優(yōu)先權(quán)優(yōu)先調(diào)度算法等 。 從機接收到分配的進程后便運行該進程 ， 該進程結(jié)束后從機又向主機發(fā)出請求 。 在進行進程分配時 ， 可采用以下兩種方式之一 。 例如 ， IBM公司的 SR/6000 Model F50, 便是利用 4片 Power PC處理器構(gòu)成的 。 每臺計算機都有自己的存儲器和 I/O設備 ， 并配置了 OS來管理本地資源和在本地運行的進程 。 它們共享主存儲器系統(tǒng)和 I/O設備 ，并要求將主存儲器劃分為若干個能獨立訪問的存儲器模塊 ，以便多個處理機能同時對主存進行訪問 。 在 t6=55ms時 ， 任務 A尚未進入第 4周期 ， 而任務 B已進入第 2周期 ， 故再調(diào)度 B2執(zhí)行 。 在 t2=10 ms時 ， A2的松弛度可按下式算出： A2的松弛度 =必須完成時間 其本身的運行時間 當前時間 =40 ms10 ms10 ms=20 ms 第三章 處理機調(diào)度與死鎖 類似地 ， 可算出 B1的松弛度為 15ms， 故調(diào)度程序應選擇 B2運行 。 在實現(xiàn)該算法時要求系統(tǒng)中有一個按松弛度排序的實時任務就緒隊列 ， 松弛度最低的任務排在隊列最前面 ， 調(diào)度程序總是選擇就緒隊列中的隊首任務執(zhí)行 。 ( a ) 非搶占輪轉(zhuǎn)調(diào)度當前進程 實時進程實時進程請求調(diào)度實時進程槍占當前進程，并立即執(zhí)行( d ) 立即搶占的優(yōu)先權(quán)調(diào)度調(diào)度時間進程 1 進程 2實時進程要求調(diào)度進程 n 實時進程調(diào)度實時進程運行( b ) 非搶占優(yōu)先權(quán)調(diào)度當前進程 實時進程實時進程請求調(diào)度 當前進程運行完成調(diào)度時間當前進程實時進程請求調(diào)度 時鐘中斷到來時調(diào)度時間( c ) 基于時鐘中斷搶占的優(yōu)先權(quán)搶占調(diào)度調(diào)度時間實時進程圖 36 實時進程調(diào)度 第三章 處理機調(diào)度與死鎖 常用的幾種實時調(diào)度算法 1. 最早截止時間優(yōu)先即 EDF(Earliest Deadline First)算法 圖 37 EDF算法用于非搶占調(diào)度方式 1 3 4 2開始截止時間任務執(zhí)行任務到達1 2 3 41 3 4 2t第三章 處理機調(diào)度與死鎖 2. 最低松弛度優(yōu)先即 LLF(Least Laxity First)算法 該算法是根據(jù)任務緊急 (或松弛 )的程度 ， 來確定任務的優(yōu)先級 。 第三章 處理機調(diào)度與死鎖 實時調(diào)度算法的分類 1. 非搶占式調(diào)度算法 (1) 非搶占式輪轉(zhuǎn)調(diào)度算法。 為使在緊迫的外部事件請求中斷時系統(tǒng)能及時響應 ， 要求系統(tǒng)具有快速硬件中斷機構(gòu) ， 還應使禁止中斷的時間間隔盡量短 ， 以免耽誤時機 (其它緊迫任務 )。 但這種調(diào)度機制比較復雜 。假定系統(tǒng)中有 m個周期性的硬實時任務 ， 它們的處理時間可表示為 Ci， 周期時間表示為 Pi， 則在單處理機情況下 ， 必須滿足下面的限制條件： ???mi iiPC11第三章 處理機調(diào)度與死鎖 系統(tǒng)才是可調(diào)度的 。 (4) 資源要求。 (3) 長批處理作業(yè)用戶 。 第三章 處理機調(diào)度與死鎖 (3) 僅當?shù)谝魂犃锌臻e時 ， 調(diào)度程序才調(diào)度第二隊列中的進程運行； 僅當?shù)?1~(i1) 隊列均空時 ， 才會調(diào)度第 i隊列中的進程運行 。 例如 ， 第二個隊列的時間片要比第一個隊列的時間片長一倍 ， ……， 第 i+1個隊列的時間片要比第 i個隊列的時間片長一倍 。 這樣就可以保證就緒隊列中的所有進程 ， 在一給定的時間內(nèi) ， 均能獲得一時間片的處理機執(zhí)行時間 。 (3) 對于長作業(yè) ， 作業(yè)的優(yōu)先級可以隨等待時間的增加而提高 ， 當其等待時間足夠長時 ， 其優(yōu)先級便可升到很高 ， 從而也可獲得處理機 。 當采用搶占式優(yōu)先權(quán)調(diào)度算法時 ， 如果再規(guī)定當前進程的優(yōu)先權(quán)以速率 b下降 ， 則可防止一個長作業(yè)長期地壟斷處理機 。 第三章 處理機調(diào)度與死鎖 2) 動態(tài)優(yōu)先權(quán)是指 ， 在創(chuàng)建進程時所賦予的優(yōu)先權(quán) ， 是可以隨進程的推進或隨其等待時間的增加而改變的 ， 以便獲得更好的調(diào)度性能 。 只是具體用法各異：有的系統(tǒng)用“ 0”表示最高優(yōu)先權(quán) ， 當數(shù)值愈大時 ， 其優(yōu)先權(quán)愈低；而有的系統(tǒng)恰恰相反 。 如果 Pi≤Pj， 原進程 Pj便繼續(xù)執(zhí)行；但如果是 Pi＞ Pj, 則立即停止 Pj的執(zhí)行 ， 做進程切換 ， 使 i進程投入執(zhí)行 。 這種調(diào)度算法主要用于批處理系統(tǒng)中；也可用于某些對實時性要求不嚴的實時系統(tǒng)中 。 更嚴重的是 ， 如果有一長作業(yè) (進程 )進入系統(tǒng)的后備隊列 (就緒隊列 )， 由于調(diào)度程序總是優(yōu)先調(diào)度那些 (即使是后進來的 )短作業(yè) (進程 )， 將導致長作業(yè) (進程 )長期不被調(diào)度 。 它們可以分別用于作業(yè)調(diào)度和進程調(diào)度 。 第三章 處理機調(diào)度與死鎖 2. (1) 系統(tǒng)吞吐量高。 第三章 處理機調(diào)度與死鎖 3. 同時具有三級調(diào)度的調(diào)度隊列模型 圖 33 具有三級調(diào)度時的調(diào)度隊列模型 就緒隊列進程調(diào)度C P U就緒，掛起隊列中級調(diào)度阻塞，掛起隊列阻塞隊列等待事件進程完成時間片完作業(yè)調(diào)度交互型作業(yè)后備隊列批量作業(yè)掛起事件出現(xiàn)事件出現(xiàn)第三章 處理機調(diào)度與死鎖 選擇調(diào)度方式和調(diào)度算法的若干準則 1. 面向用戶的準則 (1) 周轉(zhuǎn)時間短。 第三章 處理機調(diào)度與死鎖 調(diào)度隊列模型 1. 僅有進程調(diào)度的調(diào)度隊列模型 圖 3 1 僅具有進程調(diào)度的調(diào)度隊列模型 就 緒 隊 列阻 塞 隊 列進程調(diào)度C P U進程完成等待事件交互用戶事件出現(xiàn)時間片完第三章 處理機調(diào)度與死鎖 2. 具有高級和低級調(diào)度的調(diào)度隊列模型 圖 32 具有高、低兩級調(diào)度的調(diào)度隊列模型 就 緒 隊 列進程調(diào)度C P U進程完成等待事件 1作業(yè)調(diào)度事件 1 出現(xiàn)時間片完等待事件 2事件 2 出現(xiàn)??等待事件 n事件 n 出現(xiàn)后 備 隊 列? ?第三章 處理機調(diào)度與死鎖 (1) 就緒隊列的形式。 第三章 處理機調(diào)度與死鎖 3. 中級調(diào)度 (IntermediateLevel Scheduling) 中級調(diào)度又稱中程調(diào)度 (MediumTerm Scheduling)。 顯然 ， 在要求比較嚴格的實時系統(tǒng)中 ， 不宜采用這種調(diào)度方式 。第三章 處理機調(diào)度與死鎖 第三章 處理機調(diào)度與死鎖 處理機調(diào)度的基本概念 調(diào)度算法 實時調(diào)度 多處理機系統(tǒng)中的調(diào)度 產(chǎn)生死鎖的原因和必要條件 預防死鎖的方法 死鎖的檢測與解除 第三章 處理機調(diào)度與死鎖 處理機調(diào)度的基本概念 高級、中級和低級調(diào)度 1. 高級調(diào)度 (High Scheduling) 在每次執(zhí)行作業(yè)調(diào)度時 ， 都須做出以下兩個決定 。 但它難以滿足緊急任務的要求 ——立即執(zhí)行 ， 因而可能造成難以預料的后果 。 (3) 時間片原則。 當這些進程重又具備運行條件 、 且內(nèi)存又稍有空閑時 ， 由中級調(diào)度來決定把外存上的哪些又具備運行條件的就緒進程 ， 重新調(diào)入內(nèi)存 ，并修改其狀態(tài)為就緒狀態(tài) ， 掛在就緒隊列上等待進程調(diào)度 。該模型與上一模型的主要區(qū)別在于如下兩個方面 。 (4) 優(yōu)先權(quán)準則。 第三章 處理機調(diào)度與死鎖 調(diào) 度 算 法 先來先服務和短作業(yè) (進程 )優(yōu)先調(diào)度算法 1. 先來先服務調(diào)度算法 第三章 處理機調(diào)度與死鎖 圖 34 FCFS和 SJF調(diào)度算法的性能 第三章 處理機調(diào)度與死鎖 2. 短作業(yè) (進程 )優(yōu)先調(diào)度算法 短作業(yè) (進程 )優(yōu)先調(diào)度算法 SJ(P)F， 是指對短作業(yè)或短進程優(yōu)先調(diào)度的算法 。 第三章 處理