計(jì)算機(jī)操作系統(tǒng)課件第三章

1、第三章 處理機(jī)調(diào)度與死鎖 主要內(nèi)容n3.1 處理機(jī)調(diào)度的層次 n3.2 調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則n3.3 調(diào)度算法n3.4 實(shí)時(shí)調(diào)度n3.5 產(chǎn)生死鎖的原因和必要條件 n3.6 預(yù)防死鎖的方法 n3.7 死鎖的檢測(cè)與解除 3.1 處理機(jī)調(diào)度的層次n3.1.1 高級(jí)調(diào)度n3.1.2 低級(jí)調(diào)度n3.1.3 中級(jí)調(diào)度3.1.1 高級(jí)調(diào)度n作業(yè)調(diào)度、長(zhǎng)程調(diào)度n功能n基本概念作業(yè)、作業(yè)步、作業(yè)流、作業(yè)控制塊（JCB）n作業(yè)調(diào)度決定接納多少個(gè)作業(yè)決定接納哪些作業(yè)3.1.1 高級(jí)調(diào)度n思考：分時(shí)系統(tǒng)中是否需要高級(jí)調(diào)度？3.1.2 低級(jí)調(diào)度n進(jìn)程調(diào)度、短程調(diào)度最基本的一種調(diào)度，三種類型的OS都必須配置n功能保存

2、處理機(jī)的現(xiàn)場(chǎng)信息按某種算法選取進(jìn)程把處理器分配給進(jìn)程3.1.2 低級(jí)調(diào)度n進(jìn)程調(diào)度中的三個(gè)基本機(jī)制排隊(duì)器分派器（分派程序）上下文切換機(jī)制3.1.2 低級(jí)調(diào)度n進(jìn)程調(diào)度方式非搶占方式(Non-preemptive Model)搶占方式(Preemptive Model)3.1.2 低級(jí)調(diào)度n非搶占方式(Non-preemptive Model)正在執(zhí)行的進(jìn)程執(zhí)行完畢， 或因發(fā)生某事件而不能再繼續(xù)執(zhí)行;執(zhí)行中的進(jìn)程因提出I/O請(qǐng)求而暫停執(zhí)行；在進(jìn)程通信或同步過程中執(zhí)行了某種原語(yǔ)操作，如P操作(wait操作)、Block原語(yǔ)、Wakeup原語(yǔ)等。優(yōu)缺點(diǎn)優(yōu)缺點(diǎn)3.1.2 低級(jí)調(diào)度n搶占方式(Preem

3、ptive Model)優(yōu)先權(quán)原則短作業(yè)（進(jìn)程）優(yōu)先原則時(shí)間片原則3.1.3 中級(jí)調(diào)度n中程調(diào)度主要目的是為了提高內(nèi)存利用率和系統(tǒng)吞吐量n基本思想主要內(nèi)容n3.1 處理機(jī)調(diào)度的層次 n3.2 調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則n3.3 調(diào)度算法n3.4 實(shí)時(shí)調(diào)度n3.5 產(chǎn)生死鎖的原因和必要條件 n3.6 預(yù)防死鎖的方法 n3.7 死鎖的檢測(cè)與解除 3.2 調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則n3.2.1 調(diào)度隊(duì)列模型n3.2.2 選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則3.2.1 調(diào)度隊(duì)列模型n僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型n具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型n同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型 3.2.1 調(diào)度隊(duì)列模型n僅有進(jìn)程調(diào)度

4、的調(diào)度隊(duì)列模型就 緒隊(duì) 列阻 塞隊(duì)列進(jìn)程調(diào)度CPU進(jìn)程完成等待事件交互用戶事件出現(xiàn)時(shí)間片完3.2.1 調(diào)度隊(duì)列模型n具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型就 緒隊(duì)列進(jìn)程調(diào)度CPU進(jìn)程完成等待事件1作業(yè)調(diào)度事件1出現(xiàn)時(shí)間片完等待事件2事件2出現(xiàn)等待事件n事件n出現(xiàn)后備 隊(duì)列1.就緒隊(duì)列的形式2.設(shè)置多個(gè)阻塞隊(duì)列3.2.1 調(diào)度隊(duì)列模型n同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型就緒隊(duì)列進(jìn)程調(diào)度CPU就緒，掛起隊(duì)列中級(jí)調(diào)度阻塞，掛起隊(duì)列阻塞隊(duì)列等待事件進(jìn)程完成時(shí)間片完作業(yè)調(diào)度交互型作業(yè)后備隊(duì)列批量作業(yè)掛起事件出現(xiàn)事件出現(xiàn)3.2.2 選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則n面向用戶的準(zhǔn)則周轉(zhuǎn)時(shí)間短響應(yīng)時(shí)間快截止時(shí)間的保證優(yōu)

5、先權(quán)準(zhǔn)則n面向系統(tǒng)的準(zhǔn)則系統(tǒng)吞吐量高處理機(jī)利用率高各類資源的平衡利用3.2.2 選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則n周轉(zhuǎn)時(shí)間短定義，組成部分平均周轉(zhuǎn)時(shí)間作業(yè)的周轉(zhuǎn)時(shí)間T與系統(tǒng)為它提供服務(wù)的時(shí)間TS之比，即W=T/TS，稱為帶權(quán)周轉(zhuǎn)時(shí)間，平均帶權(quán)周轉(zhuǎn)時(shí)間可表示為:iiiTnT11niSiiTTnW113.2.2 選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則n響應(yīng)時(shí)間快分時(shí)系統(tǒng)從用戶通過鍵盤提交一個(gè)請(qǐng)求開始，直至系統(tǒng)首次產(chǎn)生響應(yīng)為止的時(shí)間，或者說，直到屏幕上顯示出結(jié)果為止的一段時(shí)間n截止時(shí)間的保證：實(shí)時(shí)系統(tǒng)n優(yōu)先權(quán)準(zhǔn)則3.2.2 選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則n面向系統(tǒng)的準(zhǔn)則面向系統(tǒng)的準(zhǔn)則系統(tǒng)吞吐量高。n單位

6、時(shí)間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)處理機(jī)利用率好。 各類資源的平衡利用。主要內(nèi)容n3.1 處理機(jī)調(diào)度的層次 n3.2 調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則n3.3 調(diào)度算法n3.4 實(shí)時(shí)調(diào)度n3.5 產(chǎn)生死鎖的原因和必要條件 n3.6 預(yù)防死鎖的方法 n3.7 死鎖的檢測(cè)與解除 3.3 調(diào)度算法n3.3.1 先來先服務(wù)和短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法n3.3.2高優(yōu)先權(quán)優(yōu)先調(diào)度算法n3.3.3 基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法3.3.1 先來先服務(wù)和短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法n先來先服務(wù)調(diào)度算法進(jìn)程名到達(dá)時(shí)間服務(wù)時(shí)間開始執(zhí)行時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間A01B1100C21D310001111101100 110110210

7、0 1001022021991.99有利于長(zhǎng)作業(yè)，不利于短作業(yè)最短作業(yè)優(yōu)先調(diào)度(Shortest-Job-First, SJR)n將每個(gè)進(jìn)程與其下一個(gè)CPU區(qū)間段相關(guān)聯(lián)。當(dāng)CPU為可用時(shí)，它會(huì)賦給具有最短后續(xù)CPU區(qū)間的進(jìn)程。如果兩個(gè)進(jìn)程具有同樣長(zhǎng)度的CPU區(qū)間，那么可以使用FCFS調(diào)度來處理。n兩種方式非搶占式搶占式nSJF是最佳的：對(duì)于給定的一組進(jìn)程，SJF算法的平均等待時(shí)間最小。非搶占式SJF的實(shí)例搶占式SJF的實(shí)例確定下一CPU區(qū)間的長(zhǎng)度n只能估計(jì)CPU區(qū)間的長(zhǎng)度，無法精確計(jì)算n下一CPU區(qū)間的長(zhǎng)度通?？深A(yù)測(cè)為以前CPU區(qū)間的測(cè)量長(zhǎng)度的指數(shù)平均下一個(gè)CPU區(qū)間長(zhǎng)度的預(yù)測(cè)指數(shù)平均計(jì)算的實(shí)

8、例3.3.2 高優(yōu)先權(quán)優(yōu)先調(diào)度算法n優(yōu)先權(quán)調(diào)度算法的類型非搶占式優(yōu)先權(quán)算法搶占式優(yōu)先權(quán)調(diào)度算法n優(yōu)先權(quán)類型靜態(tài)優(yōu)先權(quán)n進(jìn)程類型n進(jìn)程對(duì)資源的需求n用戶要求n缺點(diǎn)及解決辦法饑餓與老化動(dòng)態(tài)優(yōu)先權(quán)n高響應(yīng)比優(yōu)先調(diào)度算法要求服務(wù)時(shí)間等待時(shí)間要求服務(wù)時(shí)間要求服務(wù)時(shí)間等待時(shí)間優(yōu)先權(quán)1要求服務(wù)時(shí)間響應(yīng)時(shí)間要求服務(wù)時(shí)間要求服務(wù)時(shí)間等待時(shí)間優(yōu)先權(quán)等待時(shí)間相同時(shí)？要求服務(wù)時(shí)間相同時(shí)？等待時(shí)間變長(zhǎng)時(shí)？3.3.3 基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法n基本原理n時(shí)間片大小的確定n圖3-5、3-6Example of RR with Time Q = 20Process Burst TimeP153 P2 17 P368 P4 2

9、4nThe Gantt chart is: P1P2P3P4P1P3P4P1P3P302037577797117121 134154 162n多級(jí)反饋隊(duì)列調(diào)度算法性能：終端型作業(yè)用戶。 短批處理作業(yè)用戶。 長(zhǎng)批處理作業(yè)用戶。作業(yè)nP114:167n對(duì)于下面一組進(jìn)程，假設(shè)在0時(shí)刻以ABCDE的順序到達(dá)進(jìn)程服務(wù)時(shí)間優(yōu)先級(jí)A103B11C23D14E521、畫圖演示進(jìn)程使用FCFS、SJF、非搶占優(yōu)先級(jí)、時(shí)間片輪轉(zhuǎn)法(RR=1)算法調(diào)度時(shí)進(jìn)程的執(zhí)行過程2、每個(gè)進(jìn)程在每種調(diào)度算法下的周轉(zhuǎn)時(shí)間和平均周轉(zhuǎn)時(shí)間？3、每個(gè)進(jìn)程在每種調(diào)度算法下的等待時(shí)間？主要內(nèi)容n3.1 處理機(jī)調(diào)度的層次 n3.2 調(diào)度隊(duì)列模

10、型和調(diào)度準(zhǔn)則n3.3 調(diào)度算法n3.4 實(shí)時(shí)調(diào)度n3.5 產(chǎn)生死鎖的原因和必要條件 n3.6 預(yù)防死鎖的方法 n3.7 死鎖的檢測(cè)與解除 3.4 實(shí)時(shí)調(diào)度n3.4.1 實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件n3.4.2 實(shí)時(shí)調(diào)度算法的分類n3.4.3 常用的幾種實(shí)時(shí)調(diào)度算法3.4.1 實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件n提供必要的信息n系統(tǒng)處理能力強(qiáng)n采用搶占式調(diào)度機(jī)制n具有快速切換機(jī)制n必要的信息就緒時(shí)間開始截止時(shí)間和完成截止時(shí)間處理時(shí)間資源要求優(yōu)先級(jí)n系統(tǒng)處理能力強(qiáng)若處理機(jī)的處理能力不夠強(qiáng)，則有可能因處理機(jī)忙不過來而使某些實(shí)時(shí)任務(wù)不能得到及時(shí)處理， 從而導(dǎo)致發(fā)生難以預(yù)料的后果。假定系統(tǒng)中有m個(gè)周期性的硬實(shí)時(shí)任務(wù)，它們

11、的處理時(shí)間可表示為Ci，周期時(shí)間表示為Pi，則在單處理機(jī)情況下，必須滿足下面的限制條件：miiiPC113.4.2 實(shí)時(shí)調(diào)度算法的分類n非搶占式調(diào)度算法一些小實(shí)時(shí)系統(tǒng)或要求不太嚴(yán)格的實(shí)時(shí)系統(tǒng)非搶占式輪轉(zhuǎn)調(diào)度算法非搶占式優(yōu)先調(diào)度算法n搶占式調(diào)度算法基于時(shí)鐘終端的搶占式優(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)程請(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í)鐘中

12、斷到來時(shí)調(diào)度時(shí)間(c) 基于時(shí)鐘中斷搶占的優(yōu)先權(quán)搶占調(diào)度調(diào)度時(shí)間實(shí)時(shí)進(jìn)程圖 3-6 實(shí)時(shí)進(jìn)程調(diào)度 3.4.3 常用的幾種實(shí)時(shí)調(diào)度算法n最早截止時(shí)間優(yōu)先算法EDF (Earliest Deadline First)非搶占式調(diào)度方式用于非周期實(shí)時(shí)任務(wù)搶占式調(diào)度方式用于周期實(shí)時(shí)任務(wù)n最低松弛度優(yōu)先算法LLF (Least Laxity First)問題描述n有兩個(gè)周期性任務(wù)，任務(wù)A的周期時(shí)間為20ms，每個(gè)周期處理時(shí)間為10ms；任務(wù)B的周期時(shí)間為50ms，每個(gè)周期處理時(shí)間為25ms。兩個(gè)任務(wù)的到達(dá)時(shí)間，最后期限和執(zhí)行時(shí)間如下圖：B2最后期限A1A3A5A4A2B1B2A1最后期限A2最后期限A3最

13、后期限A4最后期限A5最后期限B1最后期限0 10 20 30 40 50 60 70 80 90 100 時(shí)間t/ms1. 非搶占式調(diào)度方式用于非周期實(shí)時(shí)任務(wù)圖 3-7 EDF算法用于非搶占調(diào)度方式 1342開始截止時(shí)間任務(wù)執(zhí)行任務(wù)到達(dá)12341342t搶占式調(diào)度方式用于周期實(shí)時(shí)任務(wù)2. 最低松弛度優(yōu)先即最低松弛度優(yōu)先即LLF(Least Laxity First)算法算法 A1A2A3A4A5A6A7A820406080100120140160B1B2B3t0松弛度松弛度=必須完成時(shí)間必須完成時(shí)間-其本身的運(yùn)行時(shí)間其本身的運(yùn)行時(shí)間-當(dāng)前時(shí)間當(dāng)前時(shí)間過橋的實(shí)例主要內(nèi)容n3.1 處理機(jī)調(diào)度的層

14、次 n3.2 調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則n3.3 調(diào)度算法n3.4 實(shí)時(shí)調(diào)度n3.5 產(chǎn)生死鎖的原因和必要條件 n3.6 預(yù)防死鎖的方法 n3.7 死鎖的檢測(cè)與解除 n死鎖死鎖指多個(gè)進(jìn)程在運(yùn)行過程中因爭(zhēng)奪資源而造成的指多個(gè)進(jìn)程在運(yùn)行過程中因爭(zhēng)奪資源而造成的一種僵局。一種僵局。是是OS的一種隨機(jī)故障，是指兩個(gè)或兩個(gè)以上的一種隨機(jī)故障，是指兩個(gè)或兩個(gè)以上的進(jìn)程都無限制的地等待永遠(yuǎn)不會(huì)出現(xiàn)的事件的進(jìn)程都無限制的地等待永遠(yuǎn)不會(huì)出現(xiàn)的事件而發(fā)生的狀態(tài)。而發(fā)生的狀態(tài)。3.5.1 產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因 (1) 競(jìng)爭(zhēng)資源。競(jìng)爭(zhēng)資源。 (2) 進(jìn)程間推進(jìn)順序非法。進(jìn)程間推進(jìn)順序非法。 1. 競(jìng)爭(zhēng)資源引起進(jìn)程

15、死鎖競(jìng)爭(zhēng)資源引起進(jìn)程死鎖 1) 可剝奪和非剝奪性資源：內(nèi)存VS打印機(jī) 2) 競(jìng)爭(zhēng)非剝奪性資源 ：3) 競(jìng)爭(zhēng)臨時(shí)性資源 ：消息、緩沖區(qū)等圖 3-12 I/O設(shè)備共享時(shí)的死鎖情況 R1R2P1P2圖 3-13 進(jìn)程之間通信時(shí)的死鎖 S2P1S3P3S1P22. 進(jìn)程推進(jìn)順序不當(dāng)引起死鎖進(jìn)程推進(jìn)順序不當(dāng)引起死鎖 1) 進(jìn)程推進(jìn)順序合法 圖 3-14 進(jìn)程推進(jìn)順序?qū)λ梨i的影響 P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2)D3.5.2 產(chǎn)生死鎖的必要條件產(chǎn)生死鎖的必要條件 (1) 互斥條件 (2) 請(qǐng)求和

16、保持條件 (3) 不剝奪條件 (4) 環(huán)路等待條件 3.5.3 處理死鎖的基本方法處理死鎖的基本方法(1) 預(yù)防死鎖。 (2) 避免死鎖。 (3) 檢測(cè)死鎖。 (4) 解除死鎖。 主要內(nèi)容n3.1 處理機(jī)調(diào)度的層次 n3.2 調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則n3.3 調(diào)度算法n3.4 實(shí)時(shí)調(diào)度n3.5 產(chǎn)生死鎖的原因和必要條件 n3.6 預(yù)防死鎖的方法 n3.7 死鎖的檢測(cè)與解除 3.6 預(yù)防死鎖的方法n3.6.1 預(yù)防死鎖n3.6.2 系統(tǒng)安全狀態(tài)n3.6.3 銀行家算法3.6.1 預(yù)防死鎖n產(chǎn)生死鎖的必要條件？n預(yù)防死鎖摒棄“請(qǐng)求和保持”條件 摒棄“不剝奪”條件 摒棄“環(huán)路等待”條件3.6.2 系統(tǒng)

17、安全狀態(tài)n安全狀態(tài)系統(tǒng)能按某種進(jìn)程順序(P1, P2, ，Pn)來為每個(gè)進(jìn)程Pi分配其所需資源，直至滿足每個(gè)進(jìn)程對(duì)資源的最大需求，使每個(gè)進(jìn)程都可順利地完成，并且稱P1, P2, , Pn序列為安全序列如果系統(tǒng)無法找到這樣一個(gè)安全序列，則稱系統(tǒng)處于不安全狀態(tài)。安全、不安全、死鎖狀態(tài)空間避免死鎖的實(shí)質(zhì)在于：系統(tǒng)在資源分配時(shí)，如何使系統(tǒng)不進(jìn)入安全狀態(tài)安全狀態(tài)之例安全狀態(tài)之例n系統(tǒng)當(dāng)前是否為安全狀態(tài)？n若P3又請(qǐng)求1臺(tái)磁帶機(jī)，并且分配給它，系統(tǒng)是否仍然處于安全狀態(tài)？進(jìn) 程 最 大 需 求 已 分 配 可 用 P1P2P310495223系統(tǒng)可能會(huì)由安全狀態(tài)系統(tǒng)可能會(huì)由安全狀態(tài)進(jìn)入不安全狀態(tài)進(jìn)入不安全狀

18、態(tài)3.6.3 銀行家算法避免避免死鎖n由于該算法能用于銀行系統(tǒng)現(xiàn)金貸款的發(fā)放而得名操作系統(tǒng)看作是銀行家，操作系統(tǒng)管理的資源相當(dāng)于銀行家管理的資金，進(jìn)程向操作系統(tǒng)請(qǐng)求分配資源相當(dāng)于用戶向銀行家貸款。 n當(dāng)一個(gè)顧客對(duì)資金的最大需求量不超過銀行家現(xiàn)有的資金時(shí)就可接納該顧客; n顧客可以分期貸款,但貸款的總數(shù)不能超過最大需求量; n當(dāng)銀行家現(xiàn)有的資金不能滿足顧客尚需的貸款數(shù)額時(shí),對(duì)顧客的貸款可推遲支付,但總能使顧客在有限的時(shí)間里得到貸款; n當(dāng)顧客得到所需的全部資金后,一定能在有限的時(shí)間里歸還所有的資金. 數(shù)據(jù)結(jié)構(gòu)n可利用資源向量Available。這是一個(gè)含有m個(gè)元素的數(shù)組，其中的每一個(gè)元素代表一類

19、可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動(dòng)態(tài)地改變。如果Availablej=K，則表示系統(tǒng)中現(xiàn)有Rj類資源K個(gè)。n最大需求矩陣Max。這是一個(gè)nm的矩陣，它定義了系統(tǒng)中n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對(duì)m類資源的最大需求。如果Maxi,j=K，則表示進(jìn)程i需要Rj類資源的最大數(shù)目為K。n分配矩陣Allocation。這也是一個(gè)nm的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果Allocationi,j=K，則表示進(jìn)程i當(dāng)前已分得Rj類資源的數(shù)目為K。n需求矩陣Need。這也是一個(gè)nm的矩陣，用以表示每一個(gè)進(jìn)程尚需的各類資源數(shù)。

20、如果Needi,j=K，則表示進(jìn)程i還需要Rj類資源K個(gè)，方能完成其任務(wù)Needi,j=Maxi,j-Allocationi,j 銀行家算法銀行家算法n設(shè)Requesti是進(jìn)程Pi的請(qǐng)求向量，如果Requestij=K，表示進(jìn)程Pi需要K個(gè)Rj類型的資源。如果RequestijNeedi,j，便轉(zhuǎn)向步驟2；否則認(rèn)為出錯(cuò)，因?yàn)樗枰馁Y源數(shù)已超過它所宣布的最大值。如果RequestijAvailablej，便轉(zhuǎn)向步驟(3)；否則， 表示尚無足夠資源，Pi須等待。 系統(tǒng)試探著把資源分配給進(jìn)程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)：n Availablej =Availablej-Requestij;n All

21、ocationi,j =Allocationi,j+Requestij;n Needi,j =Needi,j-Requestij;系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程Pi，以完成本次分配；否則， 將本次的試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓進(jìn)程Pi等待。 安全性算法安全性算法 (1) 設(shè)置兩個(gè)向量： 工作向量Work: 它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目，它含有m個(gè)元素，在執(zhí)行安全算法開始時(shí)，Work =Available; Finish: 它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。開始時(shí)先做Finishi =

22、false; 當(dāng)有足夠資源分配給進(jìn)程時(shí)， 再令Finishi =true。 (2) 從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程： Finishi=false; Needi,jWorkj； 若找到， 執(zhí)行步驟(3)， 否則，執(zhí)行步驟(4)。 (3) 當(dāng)進(jìn)程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行： Workj =Worki+Allocationi,j; Finishi =true; go to step 2; (4) 如果所有進(jìn)程的Finishi=true都滿足， 則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。 實(shí)例實(shí)例nT0時(shí)刻的安全性？nP1發(fā)出請(qǐng)求向量Req

23、uest1(1，0，2)，是否可以滿足？nP4發(fā)出請(qǐng)求向量Request4(3，3，0) ，是否可以滿足？nP0發(fā)出請(qǐng)求向量Requst0(0，2，0) ，是否可以滿足？作業(yè)n18、19、22主要內(nèi)容n3.1 處理機(jī)調(diào)度的層次 n3.2 調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則n3.3 調(diào)度算法n3.4 實(shí)時(shí)調(diào)度n3.5 產(chǎn)生死鎖的原因和必要條件 n3.6 預(yù)防死鎖的方法 n3.7 死鎖的檢測(cè)與解除 3.7 死鎖的檢測(cè)與解除死鎖的檢測(cè)與解除n3.7.1 死鎖的檢測(cè)死鎖的檢測(cè)n3.7.2 死鎖的解除死鎖的解除3.7.1 死鎖的檢測(cè)死鎖的檢測(cè)n1.資源分配圖資源分配圖(Resource Allocation Graph