【正文】 下 : 已占用資源 最大需求數(shù) P1 1 4 P2 4 6 P3 5 8 剩余資源數(shù) 2 系統(tǒng)處于安全狀態(tài) :可將剩余的 2個(gè)資源分給 p2,讓它運(yùn)行完畢后歸還 6個(gè)資源 ,6個(gè)資源就可以滿足p1和 p3的要求 . 已占用資源 最大需求數(shù) P1 2 4 P2 4 6 P3 5 8 剩余資源數(shù) 1 若在 t2時(shí)刻占有和申請(qǐng)最大數(shù)如右表 : 系統(tǒng)處于不安全狀態(tài) ,會(huì)產(chǎn)生死鎖 . 優(yōu)點(diǎn)：分配時(shí)，使系統(tǒng)總處于絕對(duì)安全狀態(tài) ,不會(huì)產(chǎn)生死鎖。 若系統(tǒng)有同類資源 m個(gè) ,共享的進(jìn)程最多 n個(gè) ,每個(gè)進(jìn)程申請(qǐng)的最多的資源數(shù) x個(gè) (1≤x≤m)只要下列不等式成立 ,系統(tǒng)無(wú)死鎖 : n (x1)+1≤m 缺點(diǎn)： ①必須事先知道每個(gè)進(jìn)程的資源最大需求量。 ②算法過(guò)于保守。 ③要求系統(tǒng)不斷地測(cè)試各類資源申請(qǐng)和占用情況，需要花費(fèi)較多的系統(tǒng)時(shí)間。 五 .檢測(cè)死鎖和解除死鎖 系統(tǒng)對(duì)資源的分配不加限制 ,可定時(shí)運(yùn)行一個(gè)測(cè)試死鎖程序 ,測(cè)試系統(tǒng)是否有死鎖存在 . 分兩種情況討論測(cè)試死鎖的算法 . (1) 每個(gè)資源類中只有一個(gè)資源 方法 :測(cè)試死鎖程序定時(shí)檢查 :資源占用表和進(jìn)程等待表 ,若發(fā)現(xiàn)有循環(huán)等待資源的進(jìn)程存在 ,則發(fā)出死鎖信號(hào) . 例 :系統(tǒng)有 3個(gè)進(jìn)程 p1,p2,p3,共享 5個(gè)資源 r1,r2,r3,r4,r5, 申請(qǐng)和占用資源的情況 : p1 占用 r1,r5,申請(qǐng) r3； p2 占用 r3,r4,申請(qǐng) r2。 p3 占用 r2,申請(qǐng) r5。 將申請(qǐng)和占用情況登記在資源占用表和進(jìn)程等待表中 : 資源 占用 的進(jìn)程 r1 p1 r2 p3 r3 p2 r4 p2 r5 p1 進(jìn)程 等待資源 p1 r3 p2 r2 p3 r5 r5 r3 r2 r4 r1 p1 p2 p3 環(huán)路中無(wú)非封鎖的進(jìn)程存在 :有死鎖發(fā)生。 資源占用表 進(jìn)程等待表 進(jìn)程 資源圖 (2) 資源類中含有若干資源 根據(jù)進(jìn)程對(duì)各類資源的占用量 ,尚需量和剩余量來(lái)檢測(cè)死鎖是否存在 . 步驟 : a. 初步檢測(cè) .找出資源已滿足的進(jìn)程 ,若它們運(yùn)行結(jié)束 ,歸還資源 ,再加上剩余的資源 ,作為繼續(xù)分配的資源 ,并為這些進(jìn)程作標(biāo)記 。 b. 循環(huán)檢測(cè) .檢測(cè)無(wú)標(biāo)記的進(jìn)程 ,找出一個(gè)所需資源量不超過(guò)可分配資源數(shù)的進(jìn)程 ,若找到 ,就把資源分配給它 ,讓它運(yùn)行完畢后歸還 .重復(fù) a,b兩步 . .若所有進(jìn)程都有標(biāo)記 ,系統(tǒng)無(wú)死鎖 ,否則 ,有死鎖 . 例 :5個(gè)進(jìn)程 p1,p2,p3,p4,p5共享 3類資源 ,分別有 7個(gè) ,2個(gè) ,6個(gè) : 已占用的資源量 尚需的資源量 A B C A B C P1 0 1 0 0 0 0 P2 2 0 0 2 2 2 P3 3 0 3 0 0 0 P4 2 1 1 1 0 0 P5 0 0 2 0 0 2 檢測(cè)程序發(fā)現(xiàn) :資源全部被占用 ,剩余數(shù) ( 0,0,0),但找到 p1和 p3資源滿足 ,運(yùn)行完畢后 ,剩資源余數(shù) : ( 0,0,0)+(0,1,0)+(3,0,3)=(3,1,3), 滿足 p4(或 p2， p5)的要求 ,p4運(yùn)行完畢歸還 ,剩資源余數(shù) : (3,1,3)+(2,1,1)=(5,2,4) 滿足 p2(或 p5)的要求 ,p2運(yùn)行完畢歸還 ,剩資源余數(shù) : (5,2,4)+(2,0,0)=(7,2,4) 滿足 p5的要求： (7,2,4)+(0,0,2)＝ (7,2,6)。系統(tǒng)無(wú) 死鎖 . 方法 :終止進(jìn)程法和剝奪資源法 . (1) 終止進(jìn)程法 :終止一個(gè)或多個(gè)死鎖進(jìn)程 ,使它們讓出資源 ,分配其它進(jìn)程 . (2)剝奪資源法 剝奪一個(gè)或多個(gè)死鎖進(jìn)程占用的資源 ,分配其它死鎖進(jìn)程 ,讓它們運(yùn)行 . 注意 : 進(jìn)程的”餓死”現(xiàn)象 : 如果不斷地從一個(gè)進(jìn)程中搶奪資源 ,這樣，該進(jìn)程總是處于資源不足的狀態(tài) ,以至使它完成不了擔(dān)負(fù)的任務(wù)而處于一種”餓死” . 解決”餓死”現(xiàn)象 :總是從運(yùn)行時(shí)間短的進(jìn)程那里搶奪資源。 第三章 練習(xí)題 一 .單選題 （ ）狀態(tài)的作業(yè)隊(duì)列中選取適當(dāng)?shù)淖鳂I(yè)投入運(yùn)行。 A處于等待某一個(gè)事件（如 I/O）時(shí)，該進(jìn)程 A所對(duì)應(yīng)的作業(yè)處于（ ）狀態(tài)。 （ ）條件。 （ ）。 D解除死鎖 3個(gè)進(jìn)程競(jìng)爭(zhēng)同類資源，若每個(gè)進(jìn)程需要兩個(gè)該類資源，則至少需要提供（ ）個(gè)資源，才能保證不會(huì)發(fā)生死鎖。 二 .填空題 ： 、＿＿＿ 調(diào)度和＿＿＿ 調(diào)度。 ： ＿＿＿ 、＿＿＿ 、＿＿＿ 和＿＿＿＿。 ：＿＿＿＿ 、＿＿＿＿ 、＿＿＿＿ 、＿＿＿＿和 均衡調(diào)度算法。 ： ＿＿＿＿ 、＿＿＿＿ 、＿＿＿＿ 和分級(jí)的調(diào)度算法。 ：一是＿＿＿＿＿＿＿；二是＿＿＿＿＿＿＿＿＿＿＿＿＿＿。 4個(gè)必要條件是 ＿＿＿、＿＿＿、＿＿＿和＿＿＿。 ，可以采用＿＿＿＿算法進(jìn)行資源安全分配。 ： ＿＿＿＿ 法和＿＿＿＿ 法 。 三 .在單道批處理系統(tǒng)中，有四個(gè)作業(yè)進(jìn)入系統(tǒng)，進(jìn)入時(shí)間及所需計(jì)算時(shí)間如下表所示。現(xiàn)忽略作業(yè)調(diào)度所花時(shí)間。當(dāng)?shù)谝粋€(gè)作業(yè)進(jìn)入系統(tǒng)后就可開始調(diào)度。 作業(yè) 進(jìn)入時(shí)間 所需計(jì)算時(shí)間 1 8∶ 00 2小時(shí) 2 8∶ 30 30分鐘 3 9∶ 00 6分鐘 4 9∶ 30 12分鐘 （ 1）將分別采用“先來(lái)先服務(wù)”和“短作業(yè)優(yōu)先”調(diào)度算法時(shí)，分別列 表給出各個(gè)作業(yè)的開始時(shí)間，完成時(shí)間，周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間 。 （ 2）分別計(jì)算采用“先來(lái)先服務(wù)”和“短作業(yè)優(yōu)先”調(diào)度算法時(shí)的平均 周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。 四 .考 慮四個(gè)進(jìn)程 P1， P2， P3， P4它們本次 CPC周期時(shí)值分別為8ms， 6ms， 22ms和 4ms，且以 P1， P2， P3， P4的次序處于就緒隊(duì)列中，不妨以為它們進(jìn)入就緒隊(duì)列的相對(duì)時(shí)刻均為 0。寫出采用固定式時(shí)間片的輪轉(zhuǎn)調(diào)度算法（時(shí)間片為 5ms）選中進(jìn)程執(zhí)行的次序、計(jì)算各進(jìn)程在就緒隊(duì)列中的等待時(shí)間和平均等待時(shí)間。