【正文】 第三章 處理機(jī)調(diào)度與死鎖 第三章 處理機(jī)調(diào)度與死鎖 處理機(jī)調(diào)度的基本概念 調(diào)度算法 實時調(diào)度 多處理機(jī)系統(tǒng)中的調(diào)度 產(chǎn)生死鎖的原因和必要條件 預(yù)防死鎖的方法 死鎖的檢測與解除 第三章 處理機(jī)調(diào)度與死鎖 處理機(jī)調(diào)度的基本概念 高級、中級和低級調(diào)度 1. 高級調(diào)度 (High Scheduling) 在每次執(zhí)行作業(yè)調(diào)度時 ， 都須做出以下兩個決定 。 1) 接納多少個作業(yè) 2) 接納哪些作業(yè) 第三章 處理機(jī)調(diào)度與死鎖 2. 低級調(diào)度 (Low Level Scheduling) 1) 非搶占方式 (Nonpreemptive Mode) 在采用非搶占調(diào)度方式時 ， 可能引起進(jìn)程調(diào)度的因素可歸結(jié)為這樣幾個： ① 正在執(zhí)行的進(jìn)程執(zhí)行完畢 ， 或因發(fā)生某事件而不能再繼續(xù)執(zhí)行； ② 執(zhí)行中的進(jìn)程因提出 I/O請求而暫停執(zhí)行； ③ 在進(jìn)程通信或同步過程中執(zhí)行了某種原語操作 ， 如 P操作 (wait操作 )、 Block原語 、 Wakeup原語等 。 這種調(diào)度方式的優(yōu)點是實現(xiàn)簡單 、 系統(tǒng)開銷小 ， 適用于大多數(shù)的批處理系統(tǒng)環(huán)境 。 但它難以滿足緊急任務(wù)的要求 ——立即執(zhí)行 ， 因而可能造成難以預(yù)料的后果 。 顯然 ， 在要求比較嚴(yán)格的實時系統(tǒng)中 ， 不宜采用這種調(diào)度方式 。 第三章 處理機(jī)調(diào)度與死鎖 2) 搶占方式 (Preemptive Mode) (1) 優(yōu)先權(quán)原則。 (2) 短作業(yè) (進(jìn)程 )優(yōu)先原則。 (3) 時間片原則。 第三章 處理機(jī)調(diào)度與死鎖 3. 中級調(diào)度 (IntermediateLevel Scheduling) 中級調(diào)度又稱中程調(diào)度 (MediumTerm Scheduling)。 引入中級調(diào)度的主要目的 ， 是為了提高內(nèi)存利用率和系統(tǒng)吞吐量 。 為此 ， 應(yīng)使那些暫時不能運(yùn)行的進(jìn)程不再占用寶貴的內(nèi)存資源 ， 而將它們調(diào)至外存上去等待 ， 把此時的進(jìn)程狀態(tài)稱為就緒駐外存狀態(tài)或掛起狀態(tài) 。 當(dāng)這些進(jìn)程重又具備運(yùn)行條件 、 且內(nèi)存又稍有空閑時 ， 由中級調(diào)度來決定把外存上的哪些又具備運(yùn)行條件的就緒進(jìn)程 ， 重新調(diào)入內(nèi)存 ，并修改其狀態(tài)為就緒狀態(tài) ， 掛在就緒隊列上等待進(jìn)程調(diào)度 。 第三章 處理機(jī)調(diào)度與死鎖 調(diào)度隊列模型 1. 僅有進(jìn)程調(diào)度的調(diào)度隊列模型 圖 3 1 僅具有進(jìn)程調(diào)度的調(diào)度隊列模型 就 緒 隊 列阻 塞 隊 列進(jìn)程調(diào)度C P U進(jìn)程完成等待事件交互用戶事件出現(xiàn)時間片完第三章 處理機(jī)調(diào)度與死鎖 2. 具有高級和低級調(diào)度的調(diào)度隊列模型 圖 32 具有高、低兩級調(diào)度的調(diào)度隊列模型 就 緒 隊 列進(jìn)程調(diào)度C P U進(jìn)程完成等待事件 1作業(yè)調(diào)度事件 1 出現(xiàn)時間片完等待事件 2事件 2 出現(xiàn)??等待事件 n事件 n 出現(xiàn)后 備 隊 列? ?第三章 處理機(jī)調(diào)度與死鎖 (1) 就緒隊列的形式。 (2) 設(shè)置多個阻塞隊列。 圖 32 示出了具有高 、 低兩級調(diào)度的調(diào)度隊列模型 。該模型與上一模型的主要區(qū)別在于如下兩個方面 。 第三章 處理機(jī)調(diào)度與死鎖 3. 同時具有三級調(diào)度的調(diào)度隊列模型 圖 33 具有三級調(diào)度時的調(diào)度隊列模型 就緒隊列進(jìn)程調(diào)度C P U就緒，掛起隊列中級調(diào)度阻塞，掛起隊列阻塞隊列等待事件進(jìn)程完成時間片完作業(yè)調(diào)度交互型作業(yè)后備隊列批量作業(yè)掛起事件出現(xiàn)事件出現(xiàn)第三章 處理機(jī)調(diào)度與死鎖 選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則 1. 面向用戶的準(zhǔn)則 (1) 周轉(zhuǎn)時間短。 可把平均周轉(zhuǎn)時間描述為： ??????? ??iiiTnT11??????? ??ni SiiTTnW11作業(yè)的周轉(zhuǎn)時間 T與系統(tǒng)為它提供服務(wù)的時間 TS之比 ， 即W=T/TS， 稱為帶權(quán)周轉(zhuǎn)時間 ， 而平均帶權(quán)周轉(zhuǎn)時間則可表示為 : 第三章 處理機(jī)調(diào)度與死鎖 (2) 響應(yīng)時間快。 (3) 截止時間的保證。 (4) 優(yōu)先權(quán)準(zhǔn)則。 第三章 處理機(jī)調(diào)度與死鎖 2. (1) 系統(tǒng)吞吐量高。 (2) 處理機(jī)利用率好。 (3) 各類資源的平衡利用。 第三章 處理機(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， 是指對短作業(yè)或短進(jìn)程優(yōu)先調(diào)度的算法 。 它們可以分別用于作業(yè)調(diào)度和進(jìn)程調(diào)度 。 短作業(yè)優(yōu)先 (SJF)的調(diào)度算法 ， 是從后備隊列中選擇一個或若干個估計運(yùn)行時間最短的作業(yè) ， 將它們調(diào)入內(nèi)存運(yùn)行 。 而短進(jìn)程優(yōu)先 (SPF)調(diào)度算法 ， 則是從就緒隊列中選出一估計運(yùn)行時間最短的進(jìn)程 ， 將處理機(jī)分配給它 ， 使它立即執(zhí)行并一直執(zhí)行到完成 ， 或發(fā)生某事件而被阻塞放棄處理機(jī)時 ， 再重新調(diào)度 。 第三章 處理機(jī)調(diào)度與死鎖 SJ(P)F (1) 該算法對長作業(yè)不利 ， 如作業(yè) C的周轉(zhuǎn)時間由 10增至 16， 其帶權(quán)周轉(zhuǎn)時間由 2增至 。 更嚴(yán)重的是 ， 如果有一長作業(yè) (進(jìn)程 )進(jìn)入系統(tǒng)的后備隊列 (就緒隊列 )， 由于調(diào)度程序總是優(yōu)先調(diào)度那些 (即使是后進(jìn)來的 )短作業(yè) (進(jìn)程 )， 將導(dǎo)致長作業(yè) (進(jìn)程 )長期不被調(diào)度 。 (2) 該算法完全未考慮作業(yè)的緊迫程度 ， 因而不能保證緊迫性作業(yè) (進(jìn)程 )會被及時處理 。 (3) 由于作業(yè) (進(jìn)程 )的長短只是根據(jù)用戶所提供的估計執(zhí)行時間而定的 ， 而用戶又可能會有意或無意地縮短其作業(yè)的估計運(yùn)行時間 ， 致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度 。 第三章 處理機(jī)調(diào)度與死鎖 高優(yōu)先權(quán)優(yōu)先調(diào)度算法 1. 優(yōu)先權(quán)調(diào)度算法的類型 1) 非搶占式優(yōu)先權(quán)算法 在這種方式下 ， 系統(tǒng)一旦把處理機(jī)分配給就緒隊列中優(yōu)先權(quán)最高的進(jìn)程后 ， 該進(jìn)程便一直執(zhí)行下去 ， 直至完成； 或因發(fā)生某事件使該進(jìn)程放棄處理機(jī)時 ， 系統(tǒng)方可再將處理機(jī)重新分配給另一優(yōu)先權(quán)最高的進(jìn)程 。 這種調(diào)度算法主要用于批處理系統(tǒng)中；也可用于某些對實時性要求不嚴(yán)的實時系統(tǒng)中 。 第三章 處理機(jī)調(diào)度與死鎖 2) 在這種方式下 ， 系統(tǒng)同樣是把處理機(jī)分配給優(yōu)先權(quán)最高的進(jìn)程 ， 使之執(zhí)行 。 但在其執(zhí)行期間 ， 只要又出現(xiàn)了另一個其優(yōu)先權(quán)更高的進(jìn)程 ， 進(jìn)程調(diào)度程序就立即停止當(dāng)前進(jìn)程 (原優(yōu)先權(quán)最高的進(jìn)程 )的執(zhí)行 ， 重新將處理機(jī)分配給新到的優(yōu)先權(quán)最高的進(jìn)程 。 因此 ， 在采用這種調(diào)度算法時 ， 是每當(dāng)系統(tǒng)中出現(xiàn)一個新的就緒進(jìn)程 i時 ， 就將其優(yōu)先權(quán) Pi與正在執(zhí)行的進(jìn)程 j的優(yōu)先權(quán) Pj進(jìn)行比較 。 如果 Pi≤Pj， 原進(jìn)程 Pj便繼續(xù)執(zhí)行；但如果是 Pi＞ Pj, 則立即停止 Pj的執(zhí)行 ， 做進(jìn)程切換 ， 使 i進(jìn)程投入執(zhí)行 。 顯然 ， 這種搶占式的優(yōu)先權(quán)調(diào)度算法 ， 能更好地滿足緊迫作業(yè)的要求 ， 故而常用于要求比較嚴(yán)格的實時系統(tǒng)中 ， 以及對性能要求較高的批處理和分時系統(tǒng)中 。 第三章 處理機(jī)調(diào)度與死鎖 2. 優(yōu)先權(quán)的類型 1) 靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進(jìn)程時確定的 ， 且在進(jìn)程的整個運(yùn)行期間保持不變 。 一般地 ， 優(yōu)先權(quán)是利用某一范圍內(nèi)的一個整數(shù)來表示的 ， 例如 ， 0~7或 0~255中的某一整數(shù) ， 又把該整數(shù)稱為優(yōu)先數(shù) 。 只是具體用法各異：有的系統(tǒng)用“ 0”表示最高優(yōu)先權(quán) ， 當(dāng)數(shù)值愈大時 ， 其優(yōu)先權(quán)愈