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