操作系統(tǒng)：05第五章 死鎖與饑餓

1、第五章 死鎖與饑餓 死鎖與饑餓 死 鎖: indefinite wait. 饑 餓: not necessarily in wait state. 死鎖和饑餓都是由于進(jìn)程競爭資源而引起的。 5.1 死鎖的概念例子: r1 和 r2為可再用資源。P1: apply for r1; . apply for r2; . release r1; . release r2;P2: apply for r2; . apply for r1; . release r1; . release r2;12定 義: 一組進(jìn)程中的每一個進(jìn)程, 均無限期地等待此組進(jìn)程中 某個其它進(jìn)程占有的、 因而永遠(yuǎn)無法得到的資源,

2、 這種現(xiàn)象稱為進(jìn)程死鎖。定義死鎖時刻: 無限等待發(fā)生時; 等待發(fā)生前(已注定死鎖)。5.1 死鎖的概念(Cont.)幾個有用的結(jié)論:參與死瑣的進(jìn)程至少有 2 個;每個參與死鎖的進(jìn)程均等待資源;參與死鎖的進(jìn)程中至少有 2 個進(jìn)程占有資源;死鎖進(jìn)程是系統(tǒng)中當(dāng)前進(jìn)程集合的一個子集。5.1 死鎖的概念(Cont.)5.2 死鎖的類型1. 競爭資源引起的死鎖 不同種資源 BAW直行E左轉(zhuǎn)S左轉(zhuǎn)DC 同種資源： 4臺打印機(jī)。 申請: a 釋放：a P1: a a a a a a a a P2: a a a a5.2 死鎖的類型(Cont.)2. 進(jìn)程通信引起的死鎖 P1：receive(P2,M1); P

3、2: receive(P3,M2); P3: receive(P1,M3);其它原因引起的死鎖After you / after you5.3 死鎖的條件Coffman條件(必要條件):資源獨(dú)占(mutual exclusion)不可搶占(non preemption)保持申請(hold-and-applying)循環(huán)等待(circular wait) 當(dāng)每類資源只有一個實(shí)例時, 充要條件。 破壞上述任意一個條件可以消除死鎖。5.4 死鎖的處理死鎖預(yù)防(deadlock prevention) 靜態(tài): 進(jìn)程有關(guān)資源的活動按某種協(xié)議加以限制, 若所有進(jìn)程都遵守該協(xié)議, 即可保證不發(fā)生死鎖。死鎖避

4、免(deadlock avoidance) 動態(tài): 實(shí)時檢測進(jìn)程的資源申請, 拒絕不安全的請求, 保證不發(fā)生死鎖。死鎖檢測(deadlock detection)死鎖恢復(fù)(deadlock recovery)5.5 資源分配圖5.5.1 資源分配圖的定義: 資源分配圖是有向圖G = ( V , E ) , 其中 V = PR , P = p1 , p2 , , pn , R = r1 , r2 , , rm , E = ( pi , rj ) ( rj , pi ) pi P, rj R . 申請邊 ( pi , rj ) : pi 要申請 rj； 分配邊 ( rj , pi ) : rj 分

5、配給 pi；Resource Allocation Graph資源分配圖圖示：進(jìn) 程: 資源類:申請邊: 進(jìn)程到資源類;分配邊: 由資源實(shí)例到進(jìn)程;申 請: pi 申請 rj 中的一個資源實(shí)例, 由 pi 向 rj 畫一條申請邊, 如可滿足, 改為分配邊。釋 放: 去掉分配邊。5.5 資源分配圖(Cont.)例5.1 (無環(huán)路，無死鎖) P = p1, p2, p3 , R = r1(1), r2(2), r3(1), r4(3) E= (p1,r1), (p2,r3), (r1,p2), (r2,p1), (r2,p2), (r3,p3), (r4,P3) 5.5 資源分配圖(Cont.)例

6、5.2 增加邊(p3,r2)P3P2P1r4r3r2r1發(fā)生死鎖5.5 資源分配圖(Cont.)例5.3 (有環(huán)路, 無死鎖)P1P2P3r1r2圖 1. 有環(huán)路, 無死鎖P1P2P3r1r2圖 2. P2釋放r1，r1分配給P35.5 資源分配圖(Cont.)5.5.2 資源分配圖的約簡約簡方法： 尋找一個非孤立、且沒有請求邊的進(jìn)程節(jié)點(diǎn) Pi , 若無則算法結(jié)束; 去除所有 Pi 的分配邊, 使 Pi 成為一個孤立節(jié)點(diǎn); 尋找所有請求邊均可滿足的進(jìn)程 Pj , 將 Pj 的請求邊全部改為分配邊; 轉(zhuǎn)步驟 。 對資源分配圖G進(jìn)行約簡, 若算法結(jié)束時, 圖中所有節(jié)點(diǎn)均為孤立節(jié)點(diǎn), 則稱G為可完全

7、約簡的, 否則稱G為不可完全約簡的。死鎖定理: 系統(tǒng)狀態(tài) S 為死鎖狀態(tài)的充分必要條件是 S 的資源分配圖 是不可完全約簡的。5.6 死鎖的預(yù)防 保證系統(tǒng)不死鎖的靜態(tài)策略 對進(jìn)程有關(guān)資源的活動加限制, 所有進(jìn)程遵循這種限制, 即可保證沒有死鎖發(fā)生。 優(yōu) 點(diǎn): 簡單, 系統(tǒng)不需要做什么。 缺 點(diǎn): 對進(jìn)程的約束, 違反約束仍可能死鎖。 預(yù)防方法: 預(yù)先分配策略; 有序分配策略。5.6.1 預(yù)先分配策略 進(jìn)程: 運(yùn)行前申請所需全部資源; 系統(tǒng): 能夠滿足, 全部分配; 否則, 一個也不分配。 思想: 破壞“hold-and-apply”條件。 缺點(diǎn): 資源利用效率低; 一次提出申請困難： 程序不同

8、分支可能需要申請不同資源。5.6.2 有序分配策略資源類集: R = r1 , r2 , , rn 函數(shù): f : RN例如: R = scanner , tape , printer f (scanner) = 1 ; f (tape) = 2 ; f (printer) = 3 ;假定: f (r1) f(r2) f (rn), 則對任一進(jìn)程按有序分配法申請資源的順序如下:有序分配法: 進(jìn)程 Pi 可以申請資源 rj 中的實(shí)例 rl, Pi 當(dāng)前占有rl , f(rl) f(rj)。r1r2rjrn.申請次序證明：有序分配法無死鎖(deadlock free)。反證: 假定死鎖, 則出現(xiàn)循

9、環(huán)等待, 即在時刻5.6.2 有序分配策略(Cont.)t1: p1無限等待rk1中的資源實(shí)例, 被p2占有;t2: p2無限等待rk2中的資源實(shí)例, 被p3占有;t3: p3無限等待rk3中的資源實(shí)例, 被p4占有; .tn: pn無限等待rkn中的資源實(shí)例, 被p1占有;綜上, 有 f(rk1)f(rk2)f(rkn)f(rk1)，則 f (rk1) f (rk1)，矛盾。f(rk1)f(rk2)f(rk2)f(rk3)f(rkn)f(rk1) 優(yōu) 點(diǎn)與預(yù)先分配相比, 資源利用率提高。 缺 點(diǎn) 資源編號困難; 按號申請?jiān)黾邮褂谜哓?fù)擔(dān), 一旦不按號申請仍可能死鎖; 為保持按序申請, 某些暫時

10、不用的資源 也需提前申請, 犧牲資源利用率。5.6.2 有序分配策略(Cont.)有序分配法: 資源編號: f (D) = 1 ; f (B) = 2 ; f (A) = 3 ; f (C) = 4 ; Var S1 , S2 , S3 , S4 : semaphore ; (1,1,1,1) 4個信號量分別對應(yīng)D、B、A、C的互斥進(jìn)入。5.6.2 有序分配法(Cont.)BAW直行E左轉(zhuǎn)S左轉(zhuǎn)DC有序分配法預(yù)防死鎖例S2WS1E死鎖的可能性SWE2E1可能性1:可能性2:Procedure S: P(S1); 駛?cè)隓； P(S2); 駛?cè)隑; V(S1); P(S3); 駛?cè)階； V(S2)

11、; 駛出A; V(S3)Procedure E: P(S2); 駛?cè)隑； P(S3); 駛?cè)階; V(S2); P(S4); 駛?cè)隒； V(S3); 駛出C; V(S4);Procedure W: P(S1); /預(yù)先申請 P(S4); 駛?cè)隒; 駛?cè)隓； V(S4); 駛出D； V(S1);5.6.2 有序分配法(Cont.)COBEGIN S1:S; ; Sm:S; E1:E; ; En: E; W1:W; . ; Wk:WCOEND; A(S3)B(S2)C(S4)D(S1)5.7 死鎖的避免動態(tài)檢測策略: 進(jìn)程申請資源不限制, 對能滿足的申請要求進(jìn)行動態(tài)檢測,若安全則分配, 否則不分配

12、?？蓾M足請求 分 配不安全檢 測安 全 不分配5.7.1 安全狀態(tài)與 安全進(jìn)程序列安全狀態(tài): 如果系統(tǒng)中所有進(jìn)程能按某種次序依次運(yùn)行完, 則稱系統(tǒng)處于安全狀態(tài)。形式定義: 如果存在一個由系統(tǒng)中所有進(jìn)程構(gòu)成的安全進(jìn)程序列 , 則稱系統(tǒng)處于安全狀態(tài)。對進(jìn)程序列, 如果有: pi要申請的資源數(shù)當(dāng)前剩余資源數(shù) pj當(dāng)前占有資源數(shù)則稱該進(jìn)程序列是安全的。ji安全狀態(tài)不安全狀態(tài)死鎖狀態(tài)Bankers algorithm (E.W. Dijkstra)進(jìn)程: 事先申明所需資源最大量(并不分配) Claim=Max系統(tǒng): 對每個可滿足的資源申請命令進(jìn)行安全性檢查。 安全: 分配; 不安全: 不分配狀況: P

13、= p1 , p2 , , pn ; R = r1 , r2 , , rm ;5.7.2 銀行家算法數(shù)據(jù)結(jié)構(gòu): int availablem; /系統(tǒng)可用資源 int claimn, m; /進(jìn)程最大需求 int allocationn, m; /進(jìn)程當(dāng)前已分配資源 int needn, m; /進(jìn)程尚需要的資源 int request n, m; /進(jìn)程當(dāng)前請求的資源臨時變量(安全檢查時用): int workm; /可分配資源和已分配資源之和 int finishn; /檢查時標(biāo)識是否有未完成進(jìn)程5.7.2 銀行家算法(Cont.)定義如下數(shù)組操作:設(shè)X、Y是下標(biāo)為 1k 的一維數(shù)組, 定

14、義 X Y j (1 j k), Xj Yj ; X = Y j (1 j k), Xj = Yj ; X = c j (1 j k), Xj = c ; X Y j (1 j k), Xj Yj 。5.7.2 銀行家算法(Cont.)5.7.2 銀行家算法(Cont.)資源分配算法RequestiNeedi安全請求超量，帶錯返回F確認(rèn)分配，pi 繼續(xù)算法結(jié)束TRequestiAvailableTAvailable -= Requesti;Allocationi += Requesti;Needi -= Requesti;T預(yù)分配Available += Requesti;Allocation

15、i -= Requesti;Needi += Requesti;F取消預(yù)分配申請無法滿足進(jìn)程 pi 等待F申請導(dǎo)致不安全進(jìn)程 pi 等待5.7.2 銀行家算法(Cont.)安全檢查算法Work = Available;Finish = 0;有滿足條件的 j ：Finishj=0Needj Work返回“不安全”結(jié) 束Fj ,finishj=1F返回“安全”結(jié) 束TFinishj=1; Work+= AllocationjT找出一個“安全進(jìn)程序列”Pj1、 Pj1、 Pjn5.7.2 銀行家算法(Cont.)例 5.4 資源 R = A (10) , B (5) , C(7) 進(jìn)程 P = p0

16、 , p1 , p2 , p3 , p4 某時刻系統(tǒng)狀態(tài)：134200334P4110112222P3206003209P2221002223P1333247110357P0CBACBACBACBAAvailableNeedAllocationClaimRP試判斷上述系統(tǒng)狀態(tài)是否安全？并找出該狀態(tài)下的安全進(jìn)程序列。5.7.2 銀行家算法(Cont.)對上述系統(tǒng)狀態(tài)運(yùn)行安全檢查算法，首先找到j(luò)=1，狀態(tài)如下：3C3B5AWork0134200334P40110112222P30206003209P21221002223P10247110357P0CBACBACBAFinishNeedAlloca

17、tionClaimRP5.7.2 銀行家算法(Cont.)第二次找到j(luò)=3，狀態(tài)如下：4C4B7AWork0134200334P41110112222P30206003209P21221002223P10247110357P0CBACBACBAFinishNeedAllocationClaimRP5.7.2 銀行家算法(Cont.)第三次找到j(luò)=4，狀態(tài)如下：6C4B7AWork1134200334P41110112222P30206003209P21221002223P10247110357P0CBACBACBAFinishNeedAllocationClaimRP5.7.2 銀行家算法(C

18、ont.)第四次找到j(luò)=2，狀態(tài)如下：6C4B10AWork1134200334P41110112222P31206003209P21221002223P10247110357P0CBACBACBAFinishNeedAllocationClaimRP5.7.2 銀行家算法(Cont.)第五次找到 j=0，狀態(tài)如下：7C5B10AWork1134200334P41110112222P31206003209P21221002223P11247110357P0CBACBACBAFinishNeedAllocationClaimRP所有Finishj均為1，則最初系統(tǒng)狀態(tài)是安全狀態(tài)，并且找到的安全進(jìn)

19、程序列為：實(shí)際上，也是安全進(jìn)程序列。因此，系統(tǒng)安全狀態(tài)下，安全進(jìn)程序列不唯一。5.7.2 銀行家算法(Cont.)134200334P4110112222P3206003209P2221002223P1333247110357P0CBACBACBACBAAvailableNeedAllocationClaimRP在系統(tǒng)最初狀態(tài)下，假設(shè)進(jìn)程P2有資源請求Request2=(1,0,2)，為避免死鎖，該請求是否可以滿足？5.7.2 銀行家算法(Cont.)134200334P4110112222P3005204209P2221002223P1132247110357P0CBACBACBACBAAv

20、ailableNeedAllocationClaimRP在系統(tǒng)最初狀態(tài)下，對資源請求Request2=(1,0,2)，進(jìn)行預(yù)分配，使系統(tǒng)變?yōu)槿缦聽顟B(tài)：可找到安全進(jìn)程序列，故請求Request2=(1,0,2)可以分配。5.7.2 銀行家算法(Cont.)例5.5 銀行家算法的保守性 R = A(1) , B(1) ，P = p1 , p2 申請：a , b 釋放：a , b p1 : a , b , a , b p2 : b , b , b , a , b , a則 p1 , p2 的資源最大需求量均為A(1) , B(1)。某時刻系統(tǒng)狀態(tài)如下：110011P210100111P1BABABA

21、BAAvailableNeedAllocationClaimRP5.7.2 銀行家算法(Cont.)考慮 request2 = (0 , 1)，預(yù)分配后系統(tǒng)狀態(tài)如下：011011P200100111P1BABABABAAvailableNeedAllocationClaimRP上一系統(tǒng)狀態(tài)，經(jīng)安全檢查為不安全狀態(tài)，故 request2 = (0 , 1)不分配。實(shí)際上，即使分配也不是一定導(dǎo)致死鎖。結(jié)論：不安全狀態(tài)不一定會導(dǎo)致死鎖。 亦即，死鎖狀態(tài)是不安全狀態(tài)的真子集。5.8 死鎖的發(fā)現(xiàn) 系統(tǒng)未采用: 死鎖預(yù)防策略; 死鎖避免策略。 可能發(fā)生死鎖 死鎖檢測和恢復(fù)5.8.1 死鎖檢測算法系統(tǒng)狀況:

22、 P = p1 , p2 , , pn ; R = r1 , r2 , , rm ;數(shù)據(jù)結(jié)構(gòu): int Availablem ; int Allocation n , m ; int Request n , m ; /記錄當(dāng)前各進(jìn)程申請資源數(shù)臨時變量： int Workm ; int Finishn ;5.8.1 死鎖檢測算法(Cont.)死鎖檢測算法Work = Available; i,Finishi=(Allocationi0) ? 0 : 1有滿足條件的 i ：Finishi=0Requesti Work發(fā)現(xiàn)死鎖返回Fi ,Finishi=1F無死鎖返回TFinishi=1; Work

23、+= AllocationiT定理：P是進(jìn)程集合，PP占有資源集合。P中存在死鎖P中存在死鎖。5.8.1 死鎖檢測算法(Cont.)例 5.6 資源 R = A (7) , B (3) , C(6) 進(jìn)程 P = p0 , p1 , p2 , p3 , p4 某時刻系統(tǒng)狀態(tài)：200200P4001112P3000303P2202002P1010000010P0CBACBACBAAvailableRequestAllocationRP試判斷上述系統(tǒng)狀態(tài)是否處于死鎖狀態(tài)？5.8.1 死鎖檢測算法(Cont.)200200P4001112P3000303P2202002P1020000010P0CB

24、ACBACBAWorkRequestAllocationRPFinish10000對上述系統(tǒng)狀態(tài)運(yùn)行死鎖檢測算法，首先找到i=0，狀態(tài)如下：5.8.1 死鎖檢測算法(Cont.)第二次找到i=2，狀態(tài)如下：200200P4001112P3000303P2202002P1323000010P0CBACBACBAWorkRequestAllocationRPFinish101005.8.1 死鎖檢測算法(Cont.)第三次找到i=3，狀態(tài)如下：200200P4001112P3000303P2202002P1435000010P0CBACBACBAWorkRequestAllocationRPFin

25、ish101105.8.1 死鎖檢測算法(Cont.)第四次找到i=1，狀態(tài)如下：200200P4001112P3000303P2202002P1437000010P0CBACBACBAWorkRequestAllocationRPFinish111105.8.1 死鎖檢測算法(Cont.)第五次找到i=4，狀態(tài)如下：200200P4001112P3000303P2202002P1637000010P0CBACBACBAWorkRequestAllocationRPFinish11111得到進(jìn)程序列，所有Finishi均為1。因此，最初系統(tǒng)狀態(tài)無死鎖。5.8.1 死鎖檢測算法(Cont.)如果

26、在最初系統(tǒng)狀態(tài)：200200P4001112P3000303P2202002P1010000010P0CBACBACBAAvailableRequestAllocationRP進(jìn)程 p2 有請求：Request2=(0,0,1) ，通過死鎖檢測算法檢測，則發(fā)生死鎖，參與死鎖進(jìn)程p1,p2,p3,p4在最初系統(tǒng)狀態(tài)下，進(jìn)程 p2 的請求Request2=(0,0,1) 系統(tǒng)無法滿足，此時系統(tǒng)的資源分配圖如下：A(0) 2, 3, 2B(1) 1, 1C(0) 3, 1, 2P1P4P3P0P2221125.8.1 死鎖檢測算法(Cont.)5.8.2 死鎖檢測時刻 考慮因素: 死鎖發(fā)生的頻度;

27、死鎖影響的進(jìn)程個數(shù)。 檢測時刻: 等待時檢測: 發(fā)現(xiàn)早, 恢復(fù)代價小, 開銷大(overhead)。 定時檢測; 資源(eg. CPU)利用率下降時檢測。5.9 死鎖的恢復(fù)1. 重新啟動(system restart) 簡單，代價大，涉及未參與死鎖的進(jìn)程。2. 終止進(jìn)程(terminating processes) 終止參與死鎖、占有資源的進(jìn)程： 一次性全部終止； 逐步終止(優(yōu)先級&代價函數(shù))。3. 剝奪資源(preempting resource) 逐步剝奪； 一次性全部剝奪。4. 進(jìn)程回退(process rollback) select a victim； rollback. 問題: 保

28、存snapshot代價大； 消除影響困難; 可能造成進(jìn)程“饑餓”(starvation)。5.10 鴕鳥算法 Ostrich algorithm： 對死鎖視而不見, 當(dāng)死鎖真正發(fā)生且影響系統(tǒng)正常運(yùn)行時, 手工干預(yù)(重新啟動)。 不同觀點(diǎn) 工程師觀點(diǎn)(考慮死鎖發(fā)生的頻率,危害,處理代價) 死鎖發(fā)生頻率 危害。 數(shù)學(xué)家觀點(diǎn)：必須處理,無論代價如何 目前系統(tǒng)實(shí)際如此Eg. UNIX proc結(jié)構(gòu)(PCB)及交換機(jī)制存在死鎖隱患。5.11 有關(guān)問題的討論 關(guān)于充要性算法預(yù)防策略: 進(jìn)程違反協(xié)議也可能死鎖。避免策略: 開銷大, 非必要性算法(保守算法)。充要性算法: 已知進(jìn)程所需資源最大量及其資源活動序

29、列； 困難: 程序中的分枝與循環(huán); 復(fù)雜度高 (NP Complete)。 生滅資源(或消耗性資源)問題資源: 可重用資源；生滅資源(消息): 超時處理;死鎖要考慮兩類資源, 增加了復(fù)雜性?？蓜儕Z資源問題：不會因?yàn)檫M(jìn)程競爭CPU而死鎖； 在虛擬存儲支持下，不會因?yàn)楦偁巸?nèi)存而死鎖。 關(guān)于兩階段鎖 兩階段封鎖協(xié)議: 增長階段（加鎖）和消退階段（開鎖）; 增長階段有可能發(fā)生死鎖。一組進(jìn)程中的每個進(jìn)程，均無限期地等待這組中的其它進(jìn)程引發(fā)的事件，這種現(xiàn)象叫死鎖。5.12 饑餓與活鎖由于資源分配策略的不公平， 可能造成進(jìn)程沒有時間上界的等待 排隊(duì)等待 忙式等待 饑餓(starvation)： 當(dāng)?shù)却龝r間給

30、進(jìn)程推進(jìn)和響應(yīng)帶來明顯影響時, 稱發(fā)生了進(jìn)程饑餓； 饑餓到一定程度的進(jìn)程所賦予的使命即使完成 也不再具有實(shí)際意義時稱該進(jìn)程被餓死 (starved to death).忙式等待條件下發(fā)生的饑餓,稱為活鎖(live lock).餓死 vs 死鎖：都是由競爭資源引起。死鎖進(jìn)程處于等待狀態(tài), 忙式等待的進(jìn)程并非處于等待狀態(tài), 但卻可能被餓死;死鎖進(jìn)程等待永遠(yuǎn)不會釋放的資源, 餓死進(jìn)程等待可能被釋放,但卻不會分給自己的資源,其等待時間沒有上界;死鎖一定發(fā)生了循環(huán)等待,餓死不然;死鎖至少涉及兩個進(jìn)程, 而饑餓或餓死進(jìn)程可能只有一個。 防止饑餓或餓死的資源分配策略如： 先到先服務(wù)和動態(tài)優(yōu)先級調(diào)度5.12

31、饑餓與活鎖(Cont.)5.13 可復(fù)用資源 死鎖的靜態(tài)分析 可復(fù)用資源：一次只能分配給一個進(jìn)程使用的資源。 稱為可復(fù)用資源(reusable resource)。 組合資源：由相對獨(dú)立的若干資源構(gòu)成的資源集合 稱為組合資源。 其中每個相對獨(dú)立的資源稱為子資源。 同種組合資源：由相同類型的子資源構(gòu)成的組合資源 稱為同種組合資源。 簡單組合資源：每類子資源只有一個實(shí)例的組合資源 稱為簡單組合資源。5.13 可復(fù)用資源 死鎖的靜態(tài)分析(Cont.)步驟1：以每個進(jìn)程占有資源、申請資源作為一個狀態(tài)， 記作: (pi: aj: ak1,akn)=(進(jìn)程: 請求: 占有序列) ;步驟2：以每個狀態(tài)為一個

32、節(jié)點(diǎn)；步驟3：如 s1 所申請資源為 s2 所占有，則由 s1 向 s2 畫一有 向邊(相同進(jìn)程間不畫) ;步驟4：找出所有環(huán)路 ;步驟5：判斷環(huán)路上狀態(tài)是否能同時到達(dá)， 如是有死鎖可能性，否則無死鎖可能性。 環(huán)路中有相同進(jìn)程，不能到達(dá)； 環(huán)路中有相同被占有資源，不能到達(dá)。 可復(fù)用簡單組合資源死鎖的靜態(tài)分析算法 條 件：已知各個進(jìn)程有關(guān)資源的活動序列； 判 斷：有無死鎖可能性。5.13 可復(fù)用資源 死鎖的靜態(tài)分析(Cont.)例5-7：死鎖分析例子已知: R = A，B，C，D，E，F(xiàn)，G p1：c d c a b d a b p2：d e d b f e b f p3：c e e f a e

33、 f ap1: d: cp1: a: dp1: b: d, ap2: e: dp2: b: ep2: f: e, bp3: e: cp3: f: cp3: a: c, f根據(jù)步驟1和步驟2有如下狀態(tài)節(jié)點(diǎn)：出現(xiàn)環(huán)路，可能死鎖。5.13 可復(fù)用資源 死鎖的靜態(tài)分析(Cont.)死鎖分析：判斷環(huán)路上的狀態(tài)是否可以同時到達(dá)。 即：p1, p2, p3三個進(jìn)程是否可以同時到達(dá)紅色位置。證明: 假設(shè) p1, p2, p3 三個進(jìn)程可以同時到達(dá)紅線位置, 則 p1, p2, p3 三個進(jìn)程可以同時到達(dá)藍(lán)線位置, 根據(jù)藍(lán)線位置的資源申請情況，并考慮簡單組合資源， 則各進(jìn)程推進(jìn)到藍(lán)線的進(jìn)度為： p3先于p2,

34、p2先于p1, 則 p3先于p1; 又 p1先于p3。矛盾。 所以： p1, p2, p3 三個進(jìn)程不可能同時到達(dá)環(huán)路中的狀態(tài)， 即不能發(fā)生死鎖。p1：c d c a b d a bp2：d e d b f e b f p3：c e e f a e f a5.14 同種組合資源 死鎖的必要條件M : 資源數(shù)量 ;N : 使用該類資源進(jìn)程的數(shù)量 ; : 所有進(jìn)程所需要該類資源的總量；則：當(dāng) M + N 時, 一定沒有死鎖； 當(dāng) M + N 時, 至少有一個交叉有死鎖。證明: 假定發(fā)生了死鎖， 且 n 個進(jìn)程參與了死鎖 (2 n N), 則: 參與死鎖進(jìn)程所需資源數(shù) M + n ; 未參與死鎖進(jìn)程

35、所需資源的總量 使用該類資源但未參與死鎖的進(jìn)程數(shù)= N-n ; 所有進(jìn)程所需資源的總量M+n+N-n=M+N5.14 同種組合資源 死鎖的必要條件(Cont.)例5-8. M=16；N=4； P1(5); P2(6); P3(4); P4(4) =5+6+4+4=19M+N=20 無死鎖可能性。 若 P1(5); P2(6); P3(4); P4(5) 則 =5+6+4+5=20=M+N=20 有死鎖可能性。死鎖情況： P1：a a a a a P2：a a a a a a P3：a a a a P4：a a a a a5.14 同種組合資源 死鎖的必要條件(Cont.)例. 09年計(jì)算機(jī)專業(yè)

36、綜合試卷試題25題 25. 某計(jì)算機(jī)系統(tǒng)中有8臺打印機(jī)，由K個進(jìn)程競爭使 用，每個進(jìn)程最多需要3臺打印機(jī)。該系統(tǒng)可能會 發(fā)生死鎖的K的最小值是 A2 B3 C4 D5 解：依題意，M=8, N=K, =K3。 按必要條件： M + N, 即 3K 8K 成立時，可能發(fā)生死鎖。 K 45.15 死鎖與饑餓的例子例5-9. 哲學(xué)家就餐問題(Dining Philosophers Problem) Proposed and solved by E.W. Dijkstra , in 1965.Roomph0ph4ph3ph2ph1f0f4f3f2f1哲學(xué)家活動:While(1) 思考 ; 進(jìn)食 ; 哲

37、學(xué)家活動(包含資源活動)While(1) 思考 ; 取左叉; 取右叉; 進(jìn)食; 放左叉; 放右叉; 進(jìn) 食: 需要“叉子”；叉 子: 不同種組合資源， 因?yàn)閰^(qū)別左、右叉子。5.15 死鎖與饑餓的例子(Cont.)Roomph0ph4ph3ph2ph1f0f4f3f2f1死鎖情況：每位哲學(xué)家都拿到左叉，等待右叉。5.15 死鎖與饑餓的例子(Cont.)死鎖解決方法(預(yù)先分配): 同時申請左、右兩把叉子;哲學(xué)家狀態(tài)描述(增加 hungry 狀態(tài)): #define N 5 typedef enum action thinking, hungry, eating ; action state N ;

38、等待隊(duì)列設(shè)置(每個哲學(xué)家一個隊(duì)列) : semaphore self N ; (initial self.value = 0 ) ;5.15 死鎖與饑餓的例子(Cont.)共享變量：state; semaphore mutex ; (1)測試 i 號哲學(xué)家是否具備進(jìn)食條件:void test ( int i ) if ( ( state i = hungry ) & ( state ( i 1 ) % N != eating ) & ( state ( i + 1 ) % N != eating ) ) state i = eating ; V ( self i ) ; Remark: 自測試

39、不需要 state i = hungry, 但測試左鄰右舍需要此條件。5.15 死鎖與饑餓的例子(Cont.)i 號哲學(xué)家活動：void philosopher ( int i ) while(1) think()； pick_forks(i); eat()； put_forks(i); 5.15 死鎖與饑餓的例子(Cont.)i號哲學(xué)家放叉：void put_forks ( int i ) P ( mutex ) ; state i = thinking ; test ( ( i 1 ) % N ) ; test ( ( i + 1 ) % N ) ; V ( mutex ) ;i 號哲學(xué)家取叉：void pick_forks ( int i ) P(mutex); statei=hungry; test(i); V(mutex); P(selfi);5.15 死鎖與饑餓的例子(Cont.)void main ( ) for ( i= 0 ; i 0) west_wait + ; V ( mutex ) ; P ( wq ); else wes