第3章 處理機(jī)調(diào)度與死鎖

1、處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖1第三章 處理機(jī)調(diào)度與死鎖3.1 處理機(jī)調(diào)度的層次和調(diào)度算法的目標(biāo)處理機(jī)調(diào)度的層次和調(diào)度算法的目標(biāo) 3.2 作業(yè)與調(diào)度算法作業(yè)與調(diào)度算法3.3 進(jìn)程調(diào)度進(jìn)程調(diào)度3.4 實(shí)時(shí)調(diào)度實(shí)時(shí)調(diào)度3.5 死鎖死鎖概述概述3.6 預(yù)防死鎖預(yù)防死鎖3.7 避免死鎖避免死鎖3.8 死鎖的檢測與解除死鎖的檢測與解除處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖23.1 處理機(jī)調(diào)度的層次處理機(jī)調(diào)度的層次3.1.1 高高級調(diào)度級調(diào)度 3.1.2 低低級調(diào)度級調(diào)度3.1.3 中中級調(diào)度級調(diào)度P85P85處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖3q高級調(diào)度高級調(diào)度(High-Level Scheduling)

2、又稱又稱作業(yè)調(diào)度，決定后備作業(yè)中誰調(diào)入內(nèi)存運(yùn)行 q低級調(diào)度低級調(diào)度(Low-Level Scheduling)又稱又稱進(jìn)程調(diào)度，決定就緒隊(duì)列中哪個(gè)進(jìn)程獲得CPU； q中級調(diào)度中級調(diào)度( (Intermediate-Level Scheduling)又稱又稱在虛擬存儲(chǔ)器中引入，在內(nèi)、外存對換區(qū)進(jìn)行進(jìn)程對換。處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖4就 緒 隊(duì) 列阻 塞 隊(duì) 列進(jìn)程調(diào)度CPU進(jìn)程完成等待事件交互用戶事件出現(xiàn)時(shí)間片完圖圖 僅具有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型僅具有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型 1. 僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖5就 緒 隊(duì) 列進(jìn)程調(diào)度

3、CPU進(jìn)程完成等待事件1作業(yè)調(diào)度事件1出現(xiàn)時(shí)間片完等待事件2事件2出現(xiàn)等待事件n事件n出現(xiàn)后 備 隊(duì) 列圖 3-2具有高、低兩級調(diào)度的調(diào)度隊(duì)列模型 2. 具有具有高級、低級調(diào)度高級、低級調(diào)度的調(diào)度隊(duì)列模型的調(diào)度隊(duì)列模型6就緒隊(duì)列進(jìn)程調(diào)度CPU就緒，掛起隊(duì)列中級調(diào)度阻塞，掛起隊(duì)列阻塞隊(duì)列等待事件進(jìn)程完成時(shí)間片完作業(yè)調(diào)度交互型作業(yè)后備隊(duì)列批量作業(yè)掛起事件出現(xiàn)事件出現(xiàn)圖 具有三級調(diào)度時(shí)的調(diào)度隊(duì)列模型 3. 具有三級調(diào)度的調(diào)度隊(duì)列模型具有三級調(diào)度的調(diào)度隊(duì)列模型處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖71. 處理機(jī)調(diào)度算法共同目標(biāo)（處理機(jī)調(diào)度算法共同目標(biāo)（從全局角度）從全局角度）1. 資源利用率高（系統(tǒng)吞吐量高

4、）資源利用率高（系統(tǒng)吞吐量高） 單位時(shí)間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)，跟作業(yè)本身和調(diào)度算法有關(guān) 批處理系統(tǒng)批處理系統(tǒng) 2. 公平性公平性 （將領(lǐng)） 調(diào)度方式和算法，不發(fā)生饑餓現(xiàn)象3. 各資源的平衡利用各資源的平衡利用（士兵） 適當(dāng)?shù)恼{(diào)度算法，能保持系統(tǒng)中各類資源都處于忙適當(dāng)?shù)恼{(diào)度算法，能保持系統(tǒng)中各類資源都處于忙碌狀態(tài)。碌狀態(tài)。如CPU繁忙的作業(yè)和I/O繁忙的作業(yè)搭配4. 策略強(qiáng)制執(zhí)行策略強(qiáng)制執(zhí)行 譬如安全策略，必須準(zhǔn)確執(zhí)行處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖82. 批處理系統(tǒng)的目標(biāo)批處理系統(tǒng)的目標(biāo)1、周轉(zhuǎn)時(shí)間短、周轉(zhuǎn)時(shí)間短 作業(yè)從提交給系統(tǒng)到作業(yè)完成所經(jīng)歷的時(shí)間（作業(yè)周轉(zhuǎn)時(shí)間作業(yè)周轉(zhuǎn)時(shí)間= = 等待時(shí)間

5、+運(yùn)行時(shí)間 =作業(yè)完成時(shí)刻 - 作業(yè)提交時(shí)刻 批處理系統(tǒng)批處理系統(tǒng) 平均周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間 T=（T1+T2+Tn）/n 帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間W = 周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間/CPU執(zhí)行時(shí)間執(zhí)行時(shí)間2、系統(tǒng)吞吐量高、系統(tǒng)吞吐量高 單位時(shí)間內(nèi)完成的作業(yè)數(shù)3、處理機(jī)利用率高、處理機(jī)利用率高 因CPU貴處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖9 3. 分時(shí)系統(tǒng)的目標(biāo)分時(shí)系統(tǒng)的目標(biāo)2. 均衡性均衡性 系統(tǒng)相應(yīng)時(shí)間的快慢應(yīng)與用戶所請求服務(wù)的復(fù)雜性相適應(yīng)1. 響應(yīng)時(shí)間快響應(yīng)時(shí)間快 從輸入一個(gè)請求到給出首次響應(yīng)的時(shí)間分時(shí)系統(tǒng)分時(shí)系統(tǒng) (此時(shí)進(jìn)程并不一定執(zhí)行完畢)處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖10 4. 實(shí)時(shí)系統(tǒng)的目

6、標(biāo)實(shí)時(shí)系統(tǒng)的目標(biāo)1. 截止時(shí)間的保證截止時(shí)間的保證l實(shí)時(shí)系統(tǒng)性能的重要指標(biāo)實(shí)時(shí)系統(tǒng)性能的重要指標(biāo)，因而是選擇實(shí)時(shí)調(diào)度算法的重要準(zhǔn)則。l開始截止時(shí)間（必須開始執(zhí)行的最遲時(shí)間）和完成截止時(shí)間（必須完成的最遲時(shí)間）2. 可預(yù)測性可預(yù)測性 希望連續(xù)，譬如游戲、電影處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖113.2 作業(yè)與作業(yè)調(diào)度作業(yè)與作業(yè)調(diào)度資源分配算法/系統(tǒng)資源分配策略不同的系統(tǒng)，不同目標(biāo)，采用不同的調(diào)度算法1 先來先服務(wù)先來先服務(wù)（FCFSFCFS）算法2 短作業(yè)短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法3 高優(yōu)先權(quán)優(yōu)先優(yōu)先權(quán)優(yōu)先調(diào)度算法4 基于時(shí)間片的輪轉(zhuǎn)基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法P89P89處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與

7、死鎖121. 先來先服務(wù)先來先服務(wù)( (FCFS)FCFS)調(diào)度算法調(diào)度算法l最簡單，可用于作業(yè)調(diào)度和進(jìn)程調(diào)度作業(yè)調(diào)度和進(jìn)程調(diào)度l在作業(yè)調(diào)度作業(yè)調(diào)度中，是從后備作業(yè)隊(duì)列后備作業(yè)隊(duì)列中選擇一個(gè)或多個(gè)最先進(jìn)入該隊(duì)列的作業(yè)，調(diào)入內(nèi)存，分配資源、創(chuàng)建進(jìn)程，放入就緒隊(duì)列。l在進(jìn)程調(diào)度進(jìn)程調(diào)度中，是從就緒隊(duì)列就緒隊(duì)列中選擇一個(gè)最先進(jìn)入隊(duì)列的進(jìn)程，分配處理機(jī)使之運(yùn)行。進(jìn)程則一直運(yùn)行到完成或發(fā)生某事件而阻塞后才放棄處理機(jī)。l特點(diǎn)： 比較有利于長作業(yè)比較有利于長作業(yè)(進(jìn)程進(jìn)程)，而不利于短作業(yè)，而不利于短作業(yè)(進(jìn)程進(jìn)程) 。 有利于有利于CPU繁忙的作業(yè)，而不利于繁忙的作業(yè)，而不利于I/O繁忙的作業(yè)。繁忙的作業(yè)

8、。 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖13l可用于作業(yè)調(diào)度和進(jìn)程調(diào)度。l短作業(yè)優(yōu)先短作業(yè)優(yōu)先(SJF) 是從后備隊(duì)列后備隊(duì)列中選擇一/多個(gè)估計(jì)運(yùn)行時(shí)間最短的作業(yè)，將它們調(diào)入內(nèi)存運(yùn)行。l短進(jìn)程優(yōu)先短進(jìn)程優(yōu)先(SPF) 則是從就緒隊(duì)列就緒隊(duì)列中選出一個(gè)估計(jì)運(yùn)行時(shí)間最短的進(jìn)程運(yùn)行，并一直執(zhí)行到完成，或發(fā)生某事件而阻塞放棄處理機(jī)時(shí)再重新調(diào)度。l缺點(diǎn)：缺點(diǎn)：2. 短作業(yè)短作業(yè)(進(jìn)程進(jìn)程)優(yōu)先調(diào)度算法優(yōu)先調(diào)度算法(SJF/SPF) 對長作業(yè)對長作業(yè)(進(jìn)程進(jìn)程)不利不利 沒有考慮緊迫程度沒有考慮緊迫程度 運(yùn)行時(shí)間難以估計(jì)運(yùn)行時(shí)間難以估計(jì)處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖143.2.4 優(yōu)先權(quán)優(yōu)先調(diào)度算法優(yōu)先權(quán)優(yōu)

9、先調(diào)度算法為照顧為照顧緊迫型緊迫型作業(yè)，使之在進(jìn)入系統(tǒng)后便獲得作業(yè)，使之在進(jìn)入系統(tǒng)后便獲得優(yōu)先處理優(yōu)先處理1. 優(yōu)先權(quán)的類型優(yōu)先權(quán)的類型2. 高響應(yīng)比優(yōu)先調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法(priority-scheduling algorithm，PSA)15： 靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán) 在創(chuàng)建進(jìn)程時(shí)確定的，在整個(gè)運(yùn)行期間不再改變。依據(jù)有：進(jìn)程類型、進(jìn)程對資源的要求、用戶要求的優(yōu)先權(quán)。動(dòng)態(tài)優(yōu)先權(quán)動(dòng)態(tài)優(yōu)先權(quán) 動(dòng)態(tài)優(yōu)先權(quán)是基于某種原則，使進(jìn)程的優(yōu)先權(quán)隨時(shí)間改變而改變。 譬如輪轉(zhuǎn)法處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖162. 高響應(yīng)比優(yōu)先調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法因?yàn)椋喉憫?yīng)時(shí)間因?yàn)椋喉憫?yīng)時(shí)間= =等待時(shí)間等待

10、時(shí)間+ +服務(wù)時(shí)間服務(wù)時(shí)間所以：優(yōu)先權(quán)所以：優(yōu)先權(quán)= =響應(yīng)比響應(yīng)比RP：作業(yè)的優(yōu)先級，隨著等待時(shí)間的增加以速率a提高；則長作業(yè)在等待一定時(shí)間后，必有機(jī)會(huì)分配到處理機(jī)有機(jī)會(huì)分配到處理機(jī)。優(yōu)先權(quán)的變化規(guī)律： 要求服務(wù)時(shí)間要求服務(wù)時(shí)間等待時(shí)間優(yōu)先權(quán)要求服務(wù)時(shí)間響應(yīng)時(shí)間要求服務(wù)時(shí)間要求服務(wù)時(shí)間等待時(shí)間PR處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖173.3 進(jìn)程調(diào)度進(jìn)程調(diào)度1.進(jìn)程調(diào)度任務(wù)： 保存處理機(jī)的現(xiàn)場信息 按某種算法選取進(jìn)程 把處理機(jī)分配給進(jìn)程2. 相應(yīng)機(jī)制1 1 排隊(duì)器：排隊(duì)器： 按指定算法排2 2 分派器分派器 ：依據(jù)調(diào)度程序選進(jìn)程3 3 上下文切換器：上下文切換器： 執(zhí)行大量的load 和sto

11、reP91P91處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖進(jìn)程調(diào)度機(jī)制進(jìn)程調(diào)度機(jī)制18(1) (1) 排隊(duì)器排隊(duì)器 (2) (2) 分派器分派器(3) (3) 上下文切換器上下文切換器處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖193進(jìn)程調(diào)度方式(1) 非搶占方式非搶占方式 (Non-preemptive Mode) 一旦把處理機(jī)分配給某進(jìn)程后，不管它要運(yùn)行多長時(shí)間，都一直讓它運(yùn)行下去，不搶搶，等。 直至該進(jìn)程完成完成，自愿釋放處理機(jī)，或發(fā)生某事件而被阻塞阻塞時(shí)，才再把處理機(jī)分配給其他進(jìn)程。 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖20非搶占方式非搶占方式可能引起進(jìn)程調(diào)度的因素可能引起進(jìn)程調(diào)度的因素： 自己down掉了：正

12、在執(zhí)行的進(jìn)程執(zhí)行完畢，或因發(fā)生某事件而不能再繼續(xù)執(zhí)行； 自己跑去做別的事：執(zhí)行中的進(jìn)程因提出I/O請求而暫停執(zhí)行； 自己被阻塞：在進(jìn)程通信或同步過程中執(zhí)行了某種原語操作，如wait操作、Block原語。優(yōu)點(diǎn)是優(yōu)點(diǎn)是實(shí)現(xiàn)簡單，系統(tǒng)開銷小實(shí)現(xiàn)簡單，系統(tǒng)開銷小，適用于大多數(shù)，適用于大多數(shù)批批處理系統(tǒng)處理系統(tǒng)環(huán)境。但難以滿足緊急任務(wù)的要求環(huán)境。但難以滿足緊急任務(wù)的要求立即執(zhí)行。立即執(zhí)行。 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖21(2) 搶占方式搶占方式(preemptive Mode) 1.1. 優(yōu)先權(quán)原則優(yōu)先權(quán)原則2.2. 短作業(yè)短作業(yè)( (進(jìn)程進(jìn)程) )優(yōu)先原則優(yōu)先原則3.3. 時(shí)間片原則時(shí)間片原則n

13、（搶）根據(jù)某種原則暫停根據(jù)某種原則暫停正在執(zhí)行的進(jìn)程，將正在執(zhí)行的進(jìn)程，將處理機(jī)重新處理機(jī)重新分配給另一進(jìn)程分配給另一進(jìn)程。n優(yōu)點(diǎn)：能滿足對響應(yīng)時(shí)間有嚴(yán)格要求的實(shí)時(shí)任務(wù)的需求。n缺點(diǎn)：調(diào)度所需付出的開銷較大開銷較大。n（盜亦有道）搶占的幾條原則：搶占的幾條原則：處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖223.3.2 輪轉(zhuǎn)調(diào)度算法輪轉(zhuǎn)調(diào)度算法 1. 時(shí)間片輪轉(zhuǎn)法時(shí)間片輪轉(zhuǎn)法l基本原理基本原理 所有就緒進(jìn)程按先來先服務(wù)(FCFS)的原則排成一個(gè)隊(duì)列，每次調(diào)度時(shí)，把CPU分配給隊(duì)首進(jìn)程，并令其執(zhí)行一個(gè)時(shí)間片時(shí)間片后停止執(zhí)行，進(jìn)行進(jìn)程調(diào)度(例子)l時(shí)間片大小的確定時(shí)間片大小的確定 對對響應(yīng)時(shí)間響應(yīng)時(shí)間的要求的

14、要求 就緒隊(duì)列中就緒隊(duì)列中進(jìn)程的數(shù)目進(jìn)程的數(shù)目 系統(tǒng)的系統(tǒng)的處理能力處理能力處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖232. 2. 多級反饋隊(duì)列調(diào)度算法多級反饋隊(duì)列調(diào)度算法n時(shí)間片輪轉(zhuǎn)算法和優(yōu)先級算法的綜合和發(fā)展時(shí)間片輪轉(zhuǎn)算法和優(yōu)先級算法的綜合和發(fā)展n算法的原理算法的原理(圖3-4)設(shè)置多個(gè)就緒隊(duì)列設(shè)置多個(gè)就緒隊(duì)列，并為各個(gè)隊(duì)列賦予不同的優(yōu)先級。第一個(gè)隊(duì)列最高，第二隊(duì)列次之，其余優(yōu)先權(quán)逐個(gè)降低。各隊(duì)列中執(zhí)行時(shí)間片的大小各不相同各隊(duì)列中執(zhí)行時(shí)間片的大小各不相同，優(yōu)先權(quán)愈高的隊(duì)列，每個(gè)進(jìn)程的執(zhí)行時(shí)間片就愈小。新進(jìn)程進(jìn)入第一隊(duì)列的末尾新進(jìn)程進(jìn)入第一隊(duì)列的末尾，按FCFS調(diào)度，未完成放入下一隊(duì)列當(dāng)?shù)谝魂?duì)列空閑

15、時(shí)，才調(diào)度第二隊(duì)列，當(dāng)?shù)谝魂?duì)列空閑時(shí)，才調(diào)度第二隊(duì)列，處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖243. 3. 多級反饋隊(duì)列調(diào)度算法的性能多級反饋隊(duì)列調(diào)度算法的性能該算法有較好的性能，能很好地滿足各種類型用戶的該算法有較好的性能，能很好地滿足各種類型用戶的需要。需要。 (1) (1) 終端型作業(yè)用戶終端型作業(yè)用戶。作業(yè)大多屬于交互型作業(yè)，通常較小，系統(tǒng)只要能使這些作業(yè)在第一隊(duì)列所規(guī)定的時(shí)間片內(nèi)完第一隊(duì)列所規(guī)定的時(shí)間片內(nèi)完成成，便可使終端型作業(yè)用戶都感到滿意。 (2) (2)短批處理作業(yè)用戶短批處理作業(yè)用戶。對很短的批處理型作業(yè)，像終端型作業(yè)一樣。對稍長的作業(yè)，也只需在第二隊(duì)列和第三隊(duì)列各執(zhí)行一個(gè)時(shí)間片即

16、可完成，其周轉(zhuǎn)時(shí)間仍然較短周轉(zhuǎn)時(shí)間仍然較短。 (3) (3)長批處理作業(yè)用戶長批處理作業(yè)用戶。對于長作業(yè)，它將依次在第1，2，n個(gè)隊(duì)列中運(yùn)行，然后再按輪轉(zhuǎn)方式運(yùn)行，用戶不必?fù)?dān)不必?fù)?dān)心其作業(yè)長期得不到處理心其作業(yè)長期得不到處理。 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖253.4 3.4 實(shí)時(shí)調(diào)度實(shí)時(shí)調(diào)度3.4.1 實(shí)現(xiàn)實(shí)時(shí)調(diào)度的實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件基本條件3.4.2 實(shí)時(shí)調(diào)度實(shí)時(shí)調(diào)度算法的分類算法的分類3.4.3 常用的幾種常用的幾種實(shí)時(shí)調(diào)度算法實(shí)時(shí)調(diào)度算法處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖263.4.1 實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件1. 提供必要的提供必要的調(diào)度信息調(diào)度信息2. 系統(tǒng)

17、系統(tǒng)處理能力強(qiáng)處理能力強(qiáng)3. 采用采用搶占式調(diào)度搶占式調(diào)度機(jī)制機(jī)制4. 具有具有快速切換快速切換機(jī)制機(jī)制處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖27條件條件1. 提供必要的調(diào)度信息提供必要的調(diào)度信息n就緒時(shí)間就緒時(shí)間：成為就緒狀態(tài)的起始時(shí)間起始時(shí)間，周期任務(wù)是事先預(yù)知的一串時(shí)間序列，而非周期任務(wù)也可能是預(yù)知的n開始截止時(shí)間和完成截止時(shí)間開始截止時(shí)間和完成截止時(shí)間n處理時(shí)間處理時(shí)間：任務(wù)從開始執(zhí)行直至完成所需的時(shí)間n資源要求資源要求：任務(wù)執(zhí)行時(shí)所需的一組資源n優(yōu)先級優(yōu)先級: 賦予“絕對絕對”優(yōu)先級/“相對相對”優(yōu)先級 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖28條件條件2. 系統(tǒng)處理能力強(qiáng)系統(tǒng)處理能力強(qiáng)在實(shí)時(shí)系

18、統(tǒng)中，通常都有多個(gè)實(shí)時(shí)任務(wù)。在實(shí)時(shí)系統(tǒng)中，通常都有多個(gè)實(shí)時(shí)任務(wù)。需要強(qiáng)大的處理能力，否則忙不過來，某些需要強(qiáng)大的處理能力，否則忙不過來，某些任務(wù)難及時(shí)處理，導(dǎo)致發(fā)生難以預(yù)料的后果。任務(wù)難及時(shí)處理，導(dǎo)致發(fā)生難以預(yù)料的后果。11miiiPC 假定系統(tǒng)有假定系統(tǒng)有m m個(gè)周期性的硬實(shí)時(shí)任務(wù)，它們的處理個(gè)周期性的硬實(shí)時(shí)任務(wù)，它們的處理時(shí)間表示為時(shí)間表示為CiCi，周期時(shí)間表示為周期時(shí)間表示為PiPi，則則單處理機(jī)情況單處理機(jī)情況下，必須滿足下面的限制條件下，必須滿足下面的限制條件, ,系統(tǒng)才是可調(diào)度的：系統(tǒng)才是可調(diào)度的： 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖29假如系統(tǒng)中有6個(gè)硬實(shí)時(shí)任務(wù)，它們的周期時(shí)間都

19、是 50 ms，而每次的處理時(shí)間為 10 ms，則此時(shí)是不能滿足上式的，因而系統(tǒng)是不可調(diào)度的。Straightforward ways out： （自己做）（自己做）單處理機(jī)系統(tǒng)，單處理機(jī)系統(tǒng)，增強(qiáng)處理能力增強(qiáng)處理能力，減少，減少對每一個(gè)任務(wù)的處理時(shí)間；對每一個(gè)任務(wù)的處理時(shí)間； （找人幫忙）（找人幫忙）采用采用多處理機(jī)多處理機(jī)系統(tǒng)。假定系統(tǒng)中的系統(tǒng)。假定系統(tǒng)中的處理機(jī)數(shù)為處理機(jī)數(shù)為N N，則應(yīng)將上述的限制條件改為：則應(yīng)將上述的限制條件改為： NPCmiii1處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖30n硬實(shí)時(shí)任務(wù)硬實(shí)時(shí)任務(wù)( (差一點(diǎn)，都要發(fā)生災(zāi)難的）的實(shí)時(shí)系的實(shí)時(shí)系統(tǒng)中，必須采用統(tǒng)中，必須采用搶占搶

20、占機(jī)制，以滿足硬實(shí)時(shí)任務(wù)對機(jī)制，以滿足硬實(shí)時(shí)任務(wù)對截止時(shí)間的要求。截止時(shí)間的要求。條件條件3. 采用搶占式調(diào)度機(jī)制采用搶占式調(diào)度機(jī)制處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖31 為保證及時(shí)運(yùn)行，實(shí)時(shí)系統(tǒng)應(yīng)具有快速切換機(jī)為保證及時(shí)運(yùn)行，實(shí)時(shí)系統(tǒng)應(yīng)具有快速切換機(jī)制，以保證能進(jìn)行任務(wù)的快速切換。有兩方面能力：制，以保證能進(jìn)行任務(wù)的快速切換。有兩方面能力： 條件條件4. 具有快速切換機(jī)制具有快速切換機(jī)制n對外部中斷的對外部中斷的快速響應(yīng)能力快速響應(yīng)能力 為使在緊迫事件的請求能及時(shí)響應(yīng)及時(shí)響應(yīng)，要求系統(tǒng)具有快速硬件中斷機(jī)構(gòu)，還應(yīng)使禁止中斷的時(shí)間間隔盡量短使禁止中斷的時(shí)間間隔盡量短，以免耽誤時(shí)機(jī)(緊迫任務(wù))。n快

21、速的任務(wù)快速的任務(wù)分派能力分派能力 為提高分派程序進(jìn)行任務(wù)切換的速度，系統(tǒng)中的每個(gè)運(yùn)行功能單位適當(dāng)?shù)匦∵\(yùn)行功能單位適當(dāng)?shù)匦?，以減少任務(wù)切換的時(shí)間開銷。 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖323.4.2 實(shí)時(shí)調(diào)度算法的分類實(shí)時(shí)調(diào)度算法的分類l任務(wù)性質(zhì)：硬實(shí)時(shí)調(diào)度算法和軟實(shí)時(shí)軟實(shí)時(shí)調(diào)度算法l調(diào)度方式：非搶占調(diào)度算法和搶占調(diào)度算法l調(diào)度時(shí)間：靜態(tài)調(diào)度算法和動(dòng)態(tài)調(diào)度算法l多處理機(jī)環(huán)境：集中式調(diào)度和分布式調(diào)度算法 1. 非搶占式調(diào)度算法非搶占式調(diào)度算法非搶占式非搶占式輪轉(zhuǎn)調(diào)度輪轉(zhuǎn)調(diào)度算法算法 非搶占式非搶占式優(yōu)先調(diào)度優(yōu)先調(diào)度算法算法。2. 搶占式調(diào)度算法搶占式調(diào)度算法基于基于時(shí)鐘中斷時(shí)鐘中斷的搶占式優(yōu)先權(quán)

22、調(diào)度算法的搶占式優(yōu)先權(quán)調(diào)度算法立即搶占立即搶占的優(yōu)先權(quán)調(diào)度算法的優(yōu)先權(quán)調(diào)度算法(a) 非搶占式輪轉(zhuǎn)調(diào)度當(dāng)前進(jìn)程實(shí)時(shí)進(jìn)程實(shí)時(shí)進(jìn)程請求調(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)程請求調(diào)度當(dāng)前進(jìn)程運(yùn)行完成調(diào)度時(shí)間當(dāng)前進(jìn)程實(shí)時(shí)進(jìn)程請求調(diào)度時(shí)鐘中斷到來時(shí)調(diào)度時(shí)間(c) 基于時(shí)鐘中斷搶占的優(yōu)先權(quán)搶占調(diào)度調(diào)度時(shí)間實(shí)時(shí)進(jìn)程圖圖3-8 3-8 實(shí)時(shí)進(jìn)程調(diào)度四種情況的調(diào)度時(shí)間實(shí)時(shí)進(jìn)程調(diào)度四種情況的調(diào)度時(shí)間處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖343.4.3 常用的幾種實(shí)時(shí)調(diào)度算法常

23、用的幾種實(shí)時(shí)調(diào)度算法1. 最早截止時(shí)間優(yōu)先最早截止時(shí)間優(yōu)先(EDF, Earliest Deadline First) )算法算法n非搶占式調(diào)度方式用于非搶占式調(diào)度方式用于非周期非周期實(shí)時(shí)任務(wù)實(shí)時(shí)任務(wù)n搶占式調(diào)度方式用于搶占式調(diào)度方式用于周期周期實(shí)時(shí)任務(wù)實(shí)時(shí)任務(wù)2. 最低松弛度優(yōu)先最低松弛度優(yōu)先 (LLF,Least Laxity First)算法算法P99P99P101P101處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖351. 最早截止時(shí)間優(yōu)先最早截止時(shí)間優(yōu)先(EDF, Earliest Deadline First) )算法算法n根據(jù)任務(wù)的根據(jù)任務(wù)的開始截止時(shí)間開始截止時(shí)間來確定任務(wù)的優(yōu)先級來確定任

24、務(wù)的優(yōu)先級n系統(tǒng)保持一個(gè)實(shí)時(shí)任務(wù)就緒隊(duì)列，隊(duì)列按任務(wù)系統(tǒng)保持一個(gè)實(shí)時(shí)任務(wù)就緒隊(duì)列，隊(duì)列按任務(wù)截止時(shí)間的早晚排序截止時(shí)間的早晚排序n既可用于既可用于搶占搶占式調(diào)度，也可用于式調(diào)度，也可用于非搶占非搶占式調(diào)度式調(diào)度P99P99處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖36(1)(1) 非搶占式調(diào)度方式用于非周期實(shí)時(shí)任務(wù)非搶占式調(diào)度方式用于非周期實(shí)時(shí)任務(wù)1342開始截止時(shí)間任務(wù)執(zhí)行任務(wù)到達(dá)12 341342tn4個(gè)非周期任務(wù)先后到達(dá)。先調(diào)度任務(wù)1，在任務(wù)1執(zhí)行期間，任務(wù)2、3先后到達(dá)。n任務(wù)3的開始截止時(shí)間早于任務(wù)2，故在任務(wù)1后將調(diào)度任務(wù)3。n又到達(dá)的作業(yè)4，其開始截止時(shí)間仍早于任務(wù)2，故在任務(wù)3執(zhí)行完后，

25、系統(tǒng)又調(diào)度任務(wù)4執(zhí)行，最后才調(diào)度任務(wù)2執(zhí)行。處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖37(2)(2) 搶占式調(diào)度方式用于周期實(shí)時(shí)任務(wù)搶占式調(diào)度方式用于周期實(shí)時(shí)任務(wù)n兩個(gè)周期性任務(wù)兩個(gè)周期性任務(wù)，任務(wù)，任務(wù)A的周期時(shí)間為的周期時(shí)間為20 ms，每每個(gè)周期的處理時(shí)間為個(gè)周期的處理時(shí)間為10 ms；任務(wù)任務(wù)B的周期時(shí)間為的周期時(shí)間為50 ms，每個(gè)周期的處理時(shí)間為每個(gè)周期的處理時(shí)間為25 ms。n任務(wù)任務(wù)A的到達(dá)時(shí)間為的到達(dá)時(shí)間為0、20、40、；最后期限為；最后期限為20、40、60、；n任務(wù)任務(wù)B的到達(dá)時(shí)間為的到達(dá)時(shí)間為0、50、100、；最后期限為；最后期限為50、100、150、。n圖圖3-10的第

26、一行示出了兩個(gè)任務(wù)的到達(dá)時(shí)間、最的第一行示出了兩個(gè)任務(wù)的到達(dá)時(shí)間、最后期限和執(zhí)行時(shí)間圖。后期限和執(zhí)行時(shí)間圖。處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖38A1 B1 A2B1A3 B2 A4B2A5B1A2A3B2A5A1B1B1 A2 B1 A3 B2 A4 B2 A5 B2A1A2B2A3A4A5B1最后期限B2最后期限A1最后期限A2最后期限A3最后期限A4最后期限A5最后期限到達(dá)時(shí)間、執(zhí)行時(shí)間和最后期限A1固定優(yōu)先級調(diào)度固定優(yōu)先級調(diào)度A2 B1A3A4A5，B2A5，B2A4A1(錯(cuò)過)A2 B1 A3(錯(cuò)過)A1A2 B1(錯(cuò)過)A3A4A5，B201020304050 60708090100

27、 時(shí)間 t/ms使用完成最后期限最早和最后期限調(diào)度(A有較高優(yōu)先級)(B有較高優(yōu)先級)圖3-10 最早截止時(shí)間優(yōu)先算法用于搶占調(diào)度方式之例 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖39 2. 最低松弛度優(yōu)先最低松弛度優(yōu)先 (LLF,Least Laxity First)算法算法n根據(jù)任務(wù)根據(jù)任務(wù)緊急緊急/ /松弛的程度松弛的程度, ,來確定任務(wù)的優(yōu)先級來確定任務(wù)的優(yōu)先級n任務(wù)的緊急程度愈高，賦予的優(yōu)先級就愈高任務(wù)的緊急程度愈高，賦予的優(yōu)先級就愈高，以，以便優(yōu)先執(zhí)行。便優(yōu)先執(zhí)行。n算法主要用于可搶占調(diào)度方式中。算法主要用于可搶占調(diào)度方式中。P101P101處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖40A1A2A3

28、A4A5A6A7A820406080100120140160B1B2B3t0例子：例子：周期性實(shí)時(shí)任務(wù)周期性實(shí)時(shí)任務(wù)A A和和B B：任務(wù)A：每20ms執(zhí)行一次，執(zhí)行時(shí)間為10ms；任務(wù)B：每50ms執(zhí)行一次，執(zhí)行時(shí)間為25ms。任務(wù)A和B每次必須完成的時(shí)間必須完成的時(shí)間分別為：A1、A2、A3、和B1、B2、B3、。 為保證不遺漏任何一次截止時(shí)間，應(yīng)采用最低松弛度為保證不遺漏任何一次截止時(shí)間，應(yīng)采用最低松弛度優(yōu)先的搶占調(diào)度策略。優(yōu)先的搶占調(diào)度策略。處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖41LLF算法算法A1A2A3A4A5A6A7A820406080100120140160B1B2B3t0t1A1

29、(10)10203040506080t0t10B1(20)t2t370A2(10)A3(10)A4(10)t4t5t6t7t8B1(5)B2(15)B2(10)處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖423.5 死鎖的原因和必要條件死鎖的原因和必要條件1. 產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因2. 產(chǎn)生死鎖的必要條件產(chǎn)生死鎖的必要條件3. 處理死鎖的基本方法處理死鎖的基本方法l死鎖概念的提出死鎖概念的提出1965年，Dijkstra研究銀行家算法時(shí)提出l死鎖死鎖（Deadlock） 多個(gè)進(jìn)程在運(yùn)行過程中，因爭奪資源而造成的 一種僵局一種僵局，若無外力作用，它們都將無法推進(jìn)下去。處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖

30、431 產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因可歸結(jié)為如下兩點(diǎn)產(chǎn)生死鎖的原因可歸結(jié)為如下兩點(diǎn)：1 1、競爭資源、競爭資源 當(dāng)供多個(gè)進(jìn)程共享的資源（如打印機(jī)、公用隊(duì)列等）數(shù)目不足時(shí)，會(huì)引起諸進(jìn)程對資源的競爭而產(chǎn)生死鎖。2 2、進(jìn)程間推進(jìn)順序非法、進(jìn)程間推進(jìn)順序非法 進(jìn)程在運(yùn)行過程中，請求和釋放資源的順序不當(dāng)。處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖44 產(chǎn)生死鎖的四個(gè)必要條件產(chǎn)生死鎖的四個(gè)必要條件1 1、互斥條件、互斥條件 （只能一人使用） 進(jìn)程對所分配到的資源進(jìn)行排它性使用，即在一段時(shí)間內(nèi)某資源只由一個(gè)進(jìn)程占用由一個(gè)進(jìn)程占用。2 2、請求和保持條件、請求和保持條件 （兜里攢著一個(gè)，又要求另一個(gè)）

31、進(jìn)程已經(jīng)保持了至少一個(gè)資源，但又提出了新的資源請求，而該資源又已被其它進(jìn)程占有，此時(shí)請求進(jìn)程阻塞，但又對自己已獲得的其它資源保持不放。 3 3、不剝奪條件、不剝奪條件 （占著，不給） 進(jìn)程已獲得的資源，在未使用完之前，不能被剝奪，只能在使用完時(shí)由自己釋放自己釋放。 4 4、環(huán)路等待條件、環(huán)路等待條件 （自己不釋放，搶對方的） 發(fā)生死鎖時(shí)，必然存在一個(gè)進(jìn)程資源的環(huán)形鏈資源的環(huán)形鏈。P107P107處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖45 處理死鎖的基本方法處理死鎖的基本方法l預(yù)防死鎖預(yù)防死鎖 通過設(shè)置某些限定條件，破壞導(dǎo)致死鎖的四個(gè)必要條件之一或幾個(gè)，來預(yù)防死鎖發(fā)生。l避免死鎖避免死鎖 通過某方法防

32、止系統(tǒng)進(jìn)入不安全狀態(tài)l檢測死鎖檢測死鎖 允許發(fā)生死鎖，通過措施清除。l解除死鎖解除死鎖 與檢測死鎖配套的措施。P108P108處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖463.6 預(yù)防死鎖的方法預(yù)防死鎖的方法1. 破壞“請求和保持”條件2. 破壞“不可搶占”條件3. 破壞“循環(huán)等待”條件 在系統(tǒng)設(shè)計(jì)時(shí)確定資源分配算法，保證不發(fā)生死鎖。具體的做法是破壞產(chǎn)生死鎖的四個(gè)必要條破壞產(chǎn)生死鎖的四個(gè)必要條件之一件之一。 “互斥條件互斥條件”由由資源的性質(zhì)決定資源的性質(zhì)決定。處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖471. 摒棄“請求和保持條件請求和保持條件”條件 所有進(jìn)程在開始運(yùn)行前，都必須一次性地申請整個(gè)運(yùn)所有進(jìn)程在開始

33、運(yùn)行前，都必須一次性地申請整個(gè)運(yùn)行過程所需的行過程所需的全部資源全部資源。簡單易實(shí)現(xiàn)，安全性高；資源浪費(fèi)簡單易實(shí)現(xiàn)，安全性高；資源浪費(fèi), 進(jìn)程延遲運(yùn)行進(jìn)程延遲運(yùn)行n若系統(tǒng)有足夠的資源有足夠的資源，則把需要的所有資源分配給該進(jìn)程，這樣，進(jìn)程在整個(gè)運(yùn)行期間便不會(huì)再提出資源要求，從而摒棄了請求條件請求條件。n分配資源時(shí)，只要有一種資源不能滿足某進(jìn)程的要求，也不進(jìn)行分配，而讓進(jìn)程等待。n由于進(jìn)程等待期間，并未占有任何資源未占有任何資源，也就摒棄了保持條件保持條件，從而避免死鎖發(fā)生。處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖482. 摒棄“不剝奪不剝奪”條件n進(jìn)程有新的資源請求時(shí)，如果得不到滿足，要先釋放原先占有

34、的資源，待以后重新申請。n等價(jià)于“被剝奪被剝奪”。n實(shí)現(xiàn)比較復(fù)雜，系統(tǒng)代價(jià)很高實(shí)現(xiàn)比較復(fù)雜，系統(tǒng)代價(jià)很高。例如例如: : 進(jìn)程在運(yùn)行過程中已用打印機(jī)輸出信息打印機(jī)輸出信息，但中途又因申請另一資源未果而被迫暫停運(yùn)行并釋放打印機(jī)，后來系統(tǒng)又把打印機(jī)分配給其它進(jìn)程使用。當(dāng)進(jìn)程再次恢復(fù)運(yùn)行并再次獲得打印機(jī)繼續(xù)打印時(shí)，這前后兩次打印輸出的數(shù)據(jù)并兩次打印輸出的數(shù)據(jù)并不連續(xù)不連續(xù)，即打印輸出的信息其中間有一段是另一進(jìn)程的。處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖493. 摒棄“環(huán)路等待環(huán)路等待”條件n系統(tǒng)資源按類型系統(tǒng)資源按類型線性排序線性排序，并賦予不同的序號，并賦予不同的序號。例如：例如：輸入機(jī)序號為1，打印機(jī)

35、為2，磁帶機(jī)為3，磁盤為4n資源請求必須嚴(yán)格按照資源序號遞增序號遞增的次序提出。這樣，在資源分配圖中，不可能再出現(xiàn)環(huán)路，因而摒棄了“環(huán)路等待”條件。n特性特性l各類資源所分配的序號必須相對穩(wěn)定，這限制了限制了新類型設(shè)備的增加新類型設(shè)備的增加。l進(jìn)程使用各類資源的順序與系統(tǒng)規(guī)定的順序不同，可造成對資源的浪費(fèi)資源的浪費(fèi)。l限制用戶簡單、自主地編程。處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖503.7 系統(tǒng)的安全狀態(tài)系統(tǒng)的安全狀態(tài)基本思想：讓系統(tǒng)處于安全狀態(tài)基本思想：讓系統(tǒng)處于安全狀態(tài)1. 安全狀態(tài)安全狀態(tài)（安全序列）2. 安全狀態(tài)的例子安全狀態(tài)的例子3. 由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換由安全狀態(tài)向不安全狀態(tài)的

36、轉(zhuǎn)換允許進(jìn)程動(dòng)態(tài)地申請資源動(dòng)態(tài)地申請資源，一次申請一部分資源。系統(tǒng)在進(jìn)行資源分配之前，先計(jì)算資源分配的安全性資源分配之前，先計(jì)算資源分配的安全性。若分配不會(huì)導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)，便將資源分配若分配不會(huì)導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)，便將資源分配給進(jìn)程；否則，進(jìn)程必須等待。給進(jìn)程；否則，進(jìn)程必須等待。3.7 避免死鎖避免死鎖處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖51 1. 安全狀態(tài)安全狀態(tài)（安全序列）n安全狀態(tài)安全狀態(tài)：指系統(tǒng)能按某種進(jìn)程順序 ( (P P1 1，P P2 2，P Pn n) ) (稱P1，P2，Pn序列為安全序列安全序列)，為每個(gè)進(jìn)程Pi分配其所需資源，直至滿足每個(gè)進(jìn)程對資源的最大需求，使

37、每個(gè)進(jìn)程都可順利地完成。如果系統(tǒng)無法找到這樣一個(gè)安全序列，則稱系統(tǒng)處于不安全狀態(tài)不安全狀態(tài)n安全狀態(tài)一定是沒有死鎖發(fā)生，安全狀態(tài)一定是沒有死鎖發(fā)生，不安全狀態(tài)是有可能進(jìn)入死鎖狀態(tài)。 因此，避免死鎖的實(shí)質(zhì)在于：系統(tǒng)在進(jìn)行因此，避免死鎖的實(shí)質(zhì)在于：系統(tǒng)在進(jìn)行資源資源分配時(shí)，分配時(shí)，如何使系統(tǒng)如何使系統(tǒng)不進(jìn)入不安全狀態(tài)。不進(jìn)入不安全狀態(tài)。處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖52 2. 安全狀態(tài)的例子安全狀態(tài)的例子(3個(gè)進(jìn)程，12臺(tái)磁帶機(jī))n假定系統(tǒng)中有三個(gè)進(jìn)程P1、 P2和P3，共有12臺(tái)磁帶機(jī)。n進(jìn)程P1總共要求10臺(tái)磁帶機(jī)，P2和P3分別要求4臺(tái)和9臺(tái)。n在T0時(shí)刻，進(jìn)程P1、P2和P3已分別獲得5

38、臺(tái)、2臺(tái)和2臺(tái)磁帶機(jī)，尚有3臺(tái)空閑未分配。進(jìn)程最大需求已分配可用P11053P242P392處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖531. 銀行家算法中的數(shù)據(jù)結(jié)構(gòu)銀行家算法中的數(shù)據(jù)結(jié)構(gòu)2. 銀行家算法銀行家算法3. 安全性算法安全性算法4. 銀行家算法實(shí)例銀行家算法實(shí)例3.7.2 利用銀行家算法避免死鎖利用銀行家算法避免死鎖n創(chuàng)始人Dijkstra，該算法因能用于銀行系統(tǒng)現(xiàn)金貸款的發(fā)放而得名。n銀行家算法的實(shí)質(zhì)就是要設(shè)法保證系統(tǒng)動(dòng)態(tài)分配資源后仍然保持安全狀態(tài)，從而避免死鎖的發(fā)生。n要求進(jìn)程預(yù)先告知自己的最大資源需求，并且假設(shè)系統(tǒng)擁有固定的資源總量。P111P111處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖54

39、1. 銀行家算法中的數(shù)據(jù)結(jié)構(gòu)銀行家算法中的數(shù)據(jù)結(jié)構(gòu) 可用資源向量可用資源向量Available 一個(gè)含有m個(gè)元素的數(shù)組數(shù)組，每個(gè)元素代表一類可利用的資源數(shù)目，初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動(dòng)態(tài)地改變。 Availablej=K 表示系統(tǒng)中現(xiàn)有表示系統(tǒng)中現(xiàn)有Rj類資源有類資源有K個(gè)。個(gè)。 最大需求矩陣最大需求矩陣Max 一個(gè)nm的矩陣矩陣，定義了系統(tǒng)中n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對m類資源的最大需求。 Maxi,j=k 表示進(jìn)程表示進(jìn)程i需要需要Rj類資源的最大數(shù)目為類資源的最大數(shù)目為k處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖55 分配矩陣分配矩陣Allocati

40、on 一個(gè)nm的矩陣，定義系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。 Allocationi,j=k Allocationi,j=k 進(jìn)程進(jìn)程i i當(dāng)前已分配當(dāng)前已分配RjRj類資源的數(shù)目為類資源的數(shù)目為k k 需求矩陣需求矩陣Need 一個(gè)nm的矩陣，用以表示每一個(gè)進(jìn)程尚需的各類資源數(shù)。 Needi,j=k Needi,j=k 進(jìn)程進(jìn)程i i還需還需RjRj類資源類資源k k個(gè)個(gè) 上述三個(gè)矩陣間存在下述關(guān)系：上述三個(gè)矩陣間存在下述關(guān)系： Needi,j = Maxi,j - Allocation i,jNeedi,j = Maxi,j - Allocation i,j處理機(jī)調(diào)度與死鎖處理

41、機(jī)調(diào)度與死鎖562. 銀行家算法銀行家算法 設(shè) R e q u e s ti是 進(jìn) 程 Pi的 請 求 向 量 。 若Requestij=k，表示進(jìn)程Pi需要k個(gè)j類資源。當(dāng)Pi發(fā)出資源請求后，系統(tǒng)按下述步驟進(jìn)行檢查：若RequestiNeedi ，則轉(zhuǎn)；否則，認(rèn)為出錯(cuò)。因?yàn)樗枰馁Y源數(shù)已超過它所宣布的最大值。若RequestiAvailable，則轉(zhuǎn)；否則，表示系統(tǒng)中尚無足夠的資源，Pi必須等待。處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖57系統(tǒng)試探著把資源分配給進(jìn)程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值。 Available=Available Available=Available Request

42、Requesti i AllocationAllocationi i = = AllocationAllocationi i + Request+ Requesti i NeedNeedi i = = NeedNeedi i Request Requesti i系統(tǒng)執(zhí)行安全性算法，檢測此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。l安全正式將資源分給進(jìn)程Pi；l不安全試探分配作廢，恢復(fù)資源狀態(tài)，Pi等待處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖583安全性算法安全性算法安全性算法可描述如下：(1) (1) 設(shè)置兩個(gè)向量：設(shè)置兩個(gè)向量： 工作向量Work。系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目，它含有m個(gè)元素

43、，在執(zhí)行安全算法開始時(shí)，Work:=Available。后期，work:=work + allocation Finish。系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。開始時(shí)先做Finishi:=false；當(dāng)有足夠資源分配給進(jìn)程時(shí)，再令Finishi:=true。 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖59(2) (2) 從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程：從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程： Finishi=false； Needi,jWorkj；若找到，執(zhí)行步驟(3)， 否則，執(zhí)行步驟(4)。(3) 當(dāng)進(jìn)程當(dāng)進(jìn)程PiPi獲得資源后，可順利執(zhí)行，直至完成，獲得資源后，可順利執(zhí)行，直

44、至完成， 并釋放出分配給它的資源，故應(yīng)執(zhí)行：并釋放出分配給它的資源，故應(yīng)執(zhí)行：Workj:= Workj+Allocationi,j；Finishi:=true；go to step （2）； (4) (4) 如果如果所有進(jìn)程的所有進(jìn)程的Finishi=trueFinishi=true都滿足，則表都滿足，則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖604. 銀行家算法實(shí)例銀行家算法實(shí)例 假定系統(tǒng)中有五個(gè)進(jìn)程P0，P1，P2，P3，P4和三類資源A，B，C，各種資源的數(shù)量分別為10、5、7，在T0時(shí)刻的資源分配情

45、況如圖所示Max Allocation Need Available 資源 情況 進(jìn) 程 A B C A B C A B C A B C P0 7 5 3 0 1 0 7 4 3 3 3 2 (2 3 0) P1 3 2 2 2 0 0 1 2 2 (3 0 2) (0 2 0) P2 9 0 2 3 0 2 6 0 0 P3 2 2 2 2 1 1 0 1 1 P4 4 3 3 0 0 2 4 3 1 圖3-15 T0時(shí)刻的資源分配表 P113P113處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖61(1) T0時(shí)刻的安全性時(shí)刻的安全性：利用安全性算法對利用安全性算法對T T0 0時(shí)刻的資源分配時(shí)刻的資源

46、分配情況進(jìn)行分析情況進(jìn)行分析( (見圖見圖 3-16 3-16所示所示) )可知，在可知，在T T0 0時(shí)刻存在著一個(gè)安時(shí)刻存在著一個(gè)安全序列全序列 P P1 1，P P3 3，P P4 4，P P2 2，P P0 0 ，故系統(tǒng)是安全的。故系統(tǒng)是安全的。 Work Need Allocation Work+Allocation 資源 情況 進(jìn) 程 A B C A B C A B C A B C Finish P1 3 3 2 1 2 2 2 0 0 5 3 2 true P3 5 3 2 0 1 1 2 1 1 7 4 3 true P4 7 4 3 4 3 1 0 0 2 7 4 5 tru

47、e P2 7 4 5 6 0 0 3 0 2 10 4 7 true P0 10 4 7 7 4 3 0 1 0 10 5 7 true 圖3-16T0時(shí)刻的安全序列 Max Allocation Need Available 資源 情況 進(jìn) 程 A B C A B C A B C A B C P0 7 5 3 0 1 0 7 4 3 3 3 2 (2 3 0) P1 3 2 2 2 0 0 1 2 2 (3 0 2) (0 2 0) P2 9 0 2 3 0 2 6 0 0 P3 2 2 2 2 1 1 0 1 1 P4 4 3 3 0 0 2 4 3 1 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖6

48、2(2) P1請求資源請求資源：P1發(fā)出請求向量Request1(1，0，2)，系統(tǒng)按銀行家算法進(jìn)行檢查： Request1(1，0，2)Need1(1，2，2) Request1(1，0，2)Available1(3，3，2) 系統(tǒng)先假定可為P1分配資源，并修改Available，Allocation1和Need1向量，由此形成的資源變化情況如下圖中的圓括號所示。Max Allocation Need Available 資源 情況 進(jìn) 程 A B C A B C A B C A B C P0 7 5 3 0 1 0 7 4 3 3 3 2 (2 3 0) P1 3 2 2 2 0 0 1

49、2 2 (3 0 2) (0 2 0) P2 9 0 2 3 0 2 6 0 0 P3 2 2 2 2 1 1 0 1 1 P4 4 3 3 0 0 2 4 3 1 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖63 再利用安全性算法檢查此時(shí)系統(tǒng)是否安全(圖3-17)W ork Need Allocation W ork+Allocation 資源 情況 進(jìn) 程 A B C A B C A B C A B C Finish P1 2 3 0 0 2 0 3 0 2 5 3 2 true P3 5 3 2 0 1 1 2 1 1 7 4 3 true P4 7 4 3 4 3 1 0 0 2 7 4 5 tr

50、ue P0 7 4 5 7 4 3 0 1 0 7 5 5 true P2 7 5 5 6 0 0 3 0 2 10 5 7 true 圖3-18P1申請資源時(shí)的安全性檢查 Max Allocation Need Available 資源 情況 進(jìn) 程 A B C A B C A B C A B C P0 7 5 3 0 1 0 7 4 3 3 3 2 (2 3 0) P1 3 2 2 2 0 0 1 2 2 (3 0 2) (0 2 0) P2 9 0 2 3 0 2 6 0 0 P3 2 2 2 2 1 1 0 1 1 P4 4 3 3 0 0 2 4 3 1 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與

51、死鎖64(3) P4請求資源請求資源：P4發(fā)出請求向量Request4(3，3，0)，系統(tǒng)按銀行家算法進(jìn)行檢查： Request4(3，3，0)Need4(4，3，1)； Request4(3，3，0)Available(2，3，0)，讓P4等待。(4) P0請求資源：P0發(fā)出請求向量Requst0(0，2，0)，系統(tǒng)按銀行家算法進(jìn)行檢查： Request0(0，2，0)Need0(7，4，3)； Request0(0，2，0)Available(2，3，0)； 系統(tǒng)暫時(shí)先假定可為P0分配資源，并修改有關(guān)數(shù)據(jù)，如下圖所示。 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖65圖3-18為P0分配資源后的有關(guān)資

52、源數(shù)據(jù) P0發(fā)出請求向量Requst0(0，2，0)，處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖66圖3-18為P0分配資源后的有關(guān)資源數(shù)據(jù) (5) (5) 進(jìn)行安全性檢查進(jìn)行安全性檢查：可用資源Available(2，1，0)已不能滿足任何進(jìn)程的需要，故系統(tǒng)進(jìn)入不安全狀態(tài)，此時(shí)系統(tǒng)不分配資源。若把若把P0發(fā)出的請求向量改為發(fā)出的請求向量改為Request0(0，1，0)，系統(tǒng)是否能將資源分配給它系統(tǒng)是否能將資源分配給它? ?處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖673.8 死鎖的檢測和解除死鎖的檢測和解除3.8.1 死鎖的檢測死鎖的檢測3.8.2 死鎖的解除死鎖的解除 系統(tǒng)為進(jìn)程系統(tǒng)為進(jìn)程分配資源時(shí)，如果沒

53、有分配資源時(shí)，如果沒有采取任何采取任何限制性措施，則必須提供限制性措施，則必須提供檢測和解除死鎖檢測和解除死鎖的的手段，手段，為此要做為此要做： 保存有關(guān)資源的請求和分配信息信息； 提供算法算法，利用這些信息來檢測系統(tǒng)是n否已進(jìn)入死鎖狀態(tài)。P115P115處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖683.8.1 死鎖的檢測死鎖的檢測1. 資源分配圖資源分配圖 G=(N,E) 2. 死鎖定理死鎖定理(資源分配圖是不可完全簡化) 3. 死鎖檢測中的數(shù)據(jù)結(jié)構(gòu)死鎖檢測中的數(shù)據(jù)結(jié)構(gòu)處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖691. 資源分配圖資源分配圖 (Resource Allocation Graph)系統(tǒng)死鎖可利用資源分配圖來描述系統(tǒng)死鎖可利用資源分配圖來描述 資源分配圖資源分配圖是由一組結(jié)點(diǎn)N和一組邊E所組成的一個(gè)對偶G=(N,E)，有下述定義： (1) N是一組結(jié)點(diǎn)，分兩個(gè)互斥的子集：一組進(jìn)程結(jié)點(diǎn)P=p1，p2，pn和一組資源結(jié)點(diǎn)R=r1，r2，rn，N=PR。 (2) E是邊集合。e=pi，rj是資源是資源請求邊請求邊，由進(jìn)程pi指向資源rj，表示進(jìn)程pi請求一個(gè)單位的rj資源。e=rj，pi是資源是資源分配邊分配邊，由資源rj指向進(jìn)程pi，表示把一個(gè)單位的資源rj分配給進(jìn)程pi。處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖70圓圈圓圈代表一個(gè)進(jìn)程，代表一個(gè)進(jìn)程，方框方框代表一類