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