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

1、第五章 死鎖與饑餓死鎖與饑餓死鎖: indefinite wait.可察覺(jué)饑餓: not necessarily in wait state.?死鎖和饑餓都是由于進(jìn)程競(jìng)爭(zhēng)資源而引起的. 5.1 死鎖的概念例子： r1 和 r2為可再用資源;P1: apply for r1; . apply for r2; . return r1; . return r2;P2: apply for r2; . apply for r1; . return r1; . return r2;12死鎖定義一組進(jìn)程中的每一個(gè)進(jìn)程，均無(wú)限期地等待此組進(jìn)程中某個(gè)其他進(jìn)程占有的，因而永遠(yuǎn)無(wú)法得到的資源，這種現(xiàn)象稱為進(jìn)程死鎖

2、。定義死鎖時(shí)刻：無(wú)限等待發(fā)生時(shí)；等待發(fā)生前（已注定死鎖）。由定義得到的結(jié)論幾個(gè)有用的結(jié)論：參與死瑣的進(jìn)程至少有二個(gè)；每個(gè)參與死鎖的進(jìn)程均等待資源；參與死鎖的進(jìn)程中至少有兩個(gè)進(jìn)程占有資源；死鎖進(jìn)程是系統(tǒng)中當(dāng)前進(jìn)程集合的一個(gè)子集。5.2 死鎖類型1. 競(jìng)爭(zhēng)資源引起的死鎖 （1）不同種資源 DBACW:直行E：左轉(zhuǎn)S：左轉(zhuǎn)5.2 死鎖類型1. 競(jìng)爭(zhēng)資源引起的死鎖 （1）不同種資源 SSEWW:直行E：左轉(zhuǎn)S：左轉(zhuǎn)5.2 死鎖類型1. 競(jìng)爭(zhēng)資源引起的死鎖 （1）不同種資源 SEEWW:直行E：左轉(zhuǎn)S：左轉(zhuǎn)5.2 死鎖類型（2）同種資源 4臺(tái)打印機(jī)，申請(qǐng):a, 釋放 a P1: a a a a a a

3、a a P2: a a a a5.2 死鎖類型(Cont.)2. 進(jìn)程通訊引起的死鎖 P1：receive(P2,M1); P2: receive(P3,M2); P3: receive(P1,M3);其它原因引起的死鎖After you / after you5.3 死鎖的條件Coffman條件（必要條件）資源獨(dú)占（mutual exclusion）不可搶占（non preemption）保持申請(qǐng)（hold-while-applying）循環(huán)等待（circular wait）當(dāng)每類資源只有一個(gè)實(shí)例時(shí)，充要條件。破壞上述任意一個(gè)條件可以消除死鎖。5.4 死鎖的處理死鎖預(yù)防（deadlock p

4、revention）-靜態(tài)死鎖避免（deadlock avoidance）-動(dòng)態(tài)死鎖檢測(cè)（deadlock detection）死鎖恢復(fù)（deadlock recovery）5.5 資源分配圖定義: G=(V,E), V=PR, P=p1,p2,pn, R=r1,r2,rm, E=(pi,rj)(rj,pi), piP, rjR. 申請(qǐng)邊(pi,rj): pi申請(qǐng)rj； 分配邊(rj,pi): rj分配pi;圖示： 進(jìn)程： 資源： 申請(qǐng)邊：由進(jìn)程到資源類； 分配邊：由資源實(shí)例到進(jìn)程。5.5 資源分配圖申請(qǐng)：pi申請(qǐng)rj中的一個(gè)資源實(shí)例，由pi向rj畫一條申請(qǐng)邊，如可滿足，改為分配邊。釋放：去掉

5、分配邊。例子（無(wú)環(huán)路，無(wú)死鎖）例1. 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)p1p2p3r1r3r2r4例子（有環(huán)路，有死鎖）p1p2p3r1r3r2r4增加邊（p3,r2)例子（有環(huán)路，無(wú)死鎖）p1p2p3p4r1r2例子（有環(huán)路，無(wú)死鎖）p1p2p3p4r1r2P2釋放占有資源r1, 分給P1, (p1,r1)改為(r1,p1)5.5.2 資源分配圖的約簡(jiǎn)尋找一個(gè)非孤立且沒(méi)有請(qǐng)求邊的節(jié)點(diǎn)pi, 若無(wú)算法結(jié)束去除pi的所有分配邊使其成為一個(gè)

6、孤立節(jié)點(diǎn);尋找所有請(qǐng)求邊都可滿足的進(jìn)程pj, 將pj的所有請(qǐng)求邊全部改為分配邊;轉(zhuǎn)步驟1死鎖定理若算法結(jié)束時(shí),所有節(jié)點(diǎn)均為孤點(diǎn),則稱資源分配圖是完全可約簡(jiǎn)的,否則稱為不可完全約簡(jiǎn)的.死鎖定理:S為死鎖狀態(tài)的充分必要條件是S的資源分配圖不可完全約簡(jiǎn).5.6 死鎖預(yù)防 對(duì)進(jìn)程有關(guān)資源的活動(dòng)加限制，所有進(jìn)程遵循這種限制，即可保證沒(méi)有死鎖發(fā)生。優(yōu)點(diǎn)：簡(jiǎn)單，系統(tǒng)不需要做什么。缺點(diǎn)：對(duì)進(jìn)程的約束，違反約束仍可能死鎖。預(yù)防方法：預(yù)先分配法；有序分配法。5.6.1 預(yù)先分配法進(jìn)程：運(yùn)行前申請(qǐng)所需全部資源；系統(tǒng)：能夠滿足，全部分配，否則，一個(gè)也不分配。破壞“hold-and-wait”條件缺點(diǎn)：資源利用效率低；

7、一次提出申請(qǐng)困難。5.6.2 有序分配法資源集：R=r1,r2,rn 函數(shù)：F：RN 例如：R=scanner,tape,printer F(scanner)=1; F(tape)=2; F(printer)=3;進(jìn)程pi可以申請(qǐng)資源rj中的實(shí)例rl,pi當(dāng)前占有rl, F(rl)F(rj)r1r2rkrm.申請(qǐng)次序5.6.2 有序分配法證明無(wú)死鎖（deadlock free)：反證，假定死鎖 時(shí)刻t1: p1無(wú)限等待rk1中的資源實(shí)例，被p2占有； t2: p2無(wú)限等待rk2中的資源實(shí)例，被p3占有； tn: pn無(wú)限等待rkn中的資源實(shí)例，被p1占有; 根據(jù)有序申請(qǐng)假設(shè)： F(rk1)F(

8、rk2)F(rkn)F(rk1)矛盾。5.6.2 有序分配法優(yōu)點(diǎn)與預(yù)先分配相比,資源利用率提高.缺點(diǎn)資源編號(hào)困難;為保持按序申請(qǐng),某些暫時(shí)不用的資源也需提前申請(qǐng), 犧牲資源利用率.例子DBACW:直行E：左轉(zhuǎn)S：左轉(zhuǎn)死鎖的可能性：情形1，情形2資源編號(hào)：F(D)=1; F(B)=2; F(A)=3; F(C)=4;Var S1,S2,S3,S4:semaphore; (1,1,1,1)例子Procedure S: P(S1); 駛?cè)隓； P(S2); 駛?cè)隑; V(S1); P(S3); 駛?cè)階； V(S2); 駛出A; V(S3)Procedure E: P(S2); 駛?cè)隑； P(S3);

9、 駛?cè)階; V(S2); P(S4); 駛?cè)隒； V(S3); 駛出C; V(S4);Procedure W: P(S1); P(S4); 駛?cè)隒; 駛?cè)隓； V(S4); 駛出D； V(S1);例子COBEGIN S1:S; ; Sm:S; E1:E; ; En:E; W1:W; . ; Wo:WCOEND; 5.7 死鎖避免可滿足請(qǐng)求 分配 不分配安全不安全系統(tǒng)處于安全狀態(tài)：存在安全進(jìn)程序列進(jìn)程序列安全，p1,p2,pn可依次進(jìn)行完。安全不安全死鎖檢測(cè)銀行家算法(Cont.)Bankers algorithm, E.W. Dijkstra.進(jìn)程：事先申明所需資源最大量（并不分配） Clai

10、m=Max系統(tǒng)：對(duì)每個(gè)可滿足的資源申請(qǐng)命令進(jìn)行安全性檢查。 安全,分配;不安全:不分配 P=p1,p2,pn; R=r1,r2,rm;銀行家算法(Cont.)數(shù)據(jù)結(jié)構(gòu)： Available: array1.mof integer; /系統(tǒng)可用資源 Claim: array1.n,1.mof integer; /進(jìn)程最大需求 Allocation: array1.n,1.mof integer; /當(dāng)前分配 Need: array1.n,1.mof integer; /尚需資源 Request: array1.n,1.mof integer; /當(dāng)前請(qǐng)求臨時(shí)變量： Work: array1.mo

11、f integer; Finish: array1.nof boolean;銀行家算法(Cont.)設(shè)X,Y為下標(biāo)1.l的一維數(shù)組： XY j (1jl), XjYj X:=Y j (1jl), Xj:=Yj X:=c j (1jl), Xj:=c XY j (1jl), XjYj資源分配Pi請(qǐng)求資源RequestINeedI請(qǐng)求超量，錯(cuò)返RequestIAvailable不滿足，等待Available:=Available-RequestIAllocationI:=AllocationI+RequestINeedI:=NeedI-RequestI安全確認(rèn)，pi繼續(xù)Available:=Ava

12、ilable+RequestIAllocationI:=AllocationI-RequestINeedI:=NeedI+RequestIpi等待FTFTTF安全性檢測(cè)算法FWork:=Available;Finish:=false; 有滿足條件的j:Finishj=falseNeedjWorkFinishj:=true;Work:=Work+AllocationjTj ,finishj=trueTF安全不安全銀行家算法例子R=A(10),B(5),C(7) P=p0,p1,p2,p3,p4 Claim Allocation Need Available Work FinishA B C A

13、B C A B C A B C A B C 7 5 3 0 1 1 7 4 2 3 3 33 2 2 2 0 0 1 2 29 0 2 3 0 0 6 0 22 2 2 2 1 1 0 1 14 3 3 0 0 2 4 3 1 P0:p1:p2:p3:p4:安全進(jìn)程序列：p2請(qǐng)求：Request2=(1,0,2)銀行家算法例子 Claim Allocation Need Available Work FinishA B C A B C A B C A B C A B C 7 5 3 0 1 1 7 4 2 2 3 13 2 2 2 0 0 1 2 29 0 2 4 0 2 5 0 02 2 2

14、 2 1 1 0 1 14 3 3 0 0 2 4 3 1 P0:p1:p2:p3:p4:假定分配：安全進(jìn)程序列：，確認(rèn)分配；p4請(qǐng)求：Request4=(3,3,0), 不能滿足，等待；p0請(qǐng)求：Request0=(0,2,1), 不安全，取消分配，等待。例子：R=A,B, 申請(qǐng)a, b; 釋放a, b P=p1,p2, p1: a b a b; p2:b b b a a b Claim Allocation Need Available Work Finish A B A B A B A B A B p1：1 1 0 0 1 1 1 1p2：1 1 0 0 1 1Request1=(1,0

15、), 安全，分配。銀行家算法的保守性銀行家算法的保守性Request2=(0,1), 不安全，不分配，（分配不導(dǎo)致死鎖） Claim Allocation Need Available Work Finish A B A B A B A B A B p1：1 1 1 0 0 1 0 1p2：1 1 0 0 1 1分配后：討論Remarks1: 銀行家算法要求條件：進(jìn)程所需資源最大量, 這個(gè)信息對(duì)于充要性分析是不夠的。Remarks2: 假設(shè)：進(jìn)程預(yù)先給出有關(guān)資源的命令序列，則可以給出死鎖避免的充要性算法，復(fù)雜度（NP Complete)。Remarks3: 預(yù)先給出進(jìn)程有關(guān)資源的命令序列是困難

16、的(程序的分枝和循環(huán)）。5.8 死鎖的檢測(cè)數(shù)據(jù)結(jié)構(gòu)： Available: array1.mof integer; Allocation: array1.n,1.mof integer; Request: array1.n,1.mof integer;臨時(shí)變量： Work: array1.mof integer; Finish: array1.nof Boolean;5.8.1 死鎖檢測(cè)算法Work:=Available;Finish:=false;有滿足條件的i:Finishi=falseRequestiWorkFinishi=true;Work:=Work+AllocationiTi ,f

17、inishi=trueTFF無(wú)死鎖死鎖FinishI=truefor allocationI=0Remarks1. 上述算法可以檢測(cè)到參與死鎖的全部進(jìn)程，包括占有資 源和不占有資源的進(jìn)程。2. 如果希望只檢測(cè)占有資源的進(jìn)程，初始化時(shí)： Finishi=true, for AllocationI=0Remarks令P是所有進(jìn)程的集合，P包含于P是所有占有資源的進(jìn)程集合，則:P死鎖P死鎖。死鎖檢測(cè)之后是恢復(fù)，只考慮P中的進(jìn)程。死鎖檢測(cè)不考慮P-P中的進(jìn)程，縮小了檢測(cè)范圍，降低了系統(tǒng)開銷。死鎖例子例子：R=A(7),B(3),C(6); P=p0,p1,p2,p3,p4 Allocation Req

18、uest Available Work Finish A B C A B C A B C A B C p0: 0 1 0 0 0 0 0 1 0p1: 2 0 0 2 0 2 p2: 3 0 3 0 0 0p3: 2 1 1 1 0 0p4: 0 0 2 0 0 2 未死鎖。此時(shí)，Request2=(0,0,1), 死鎖，參與死鎖進(jìn)程p1,p2,p3,p45.8.2 死鎖檢測(cè)時(shí)刻考慮因素： 死鎖發(fā)生頻度； 死鎖發(fā)生跡象（如進(jìn)程等待時(shí)間過(guò)久）。1. 等待時(shí)檢測(cè)： 發(fā)現(xiàn)早，恢復(fù)代價(jià)小，開銷大（overhead)。2. 定時(shí)檢測(cè)：3. 資源（eg. CPU）利用率下降時(shí)檢測(cè)；4. 交互式任務(wù)沒(méi)有響應(yīng)

19、時(shí)檢測(cè)。5.9 死鎖的恢復(fù)1. 重新啟動(dòng) 簡(jiǎn)單，代價(jià)大，涉及未參與死鎖的進(jìn)程。2. 終止進(jìn)程(process termination) 環(huán)路上占有資源的進(jìn)程。 (1) 一次性全部終止；(2) 逐步終止（優(yōu)先級(jí)，代價(jià)函數(shù)）3. 剝奪資源(resource preemption)+進(jìn)程回退(rollback) (1) select a victim；(2) rollback. 問(wèn)題: (1) 保存snapshot代價(jià)大；(2) 消除影響困難; (3) starvation.5.10 鴕鳥算法視而不見(jiàn)Pro:工程師觀點(diǎn)(考慮死鎖發(fā)生的頻率,危害,處理代價(jià))死鎖發(fā)生頻率危害Cont:數(shù)學(xué)家觀點(diǎn)必須處理

20、,無(wú)論代價(jià)如何目前系統(tǒng)實(shí)際如此Eg. UNIX proc結(jié)構(gòu)(50 and up)5.11 有關(guān)問(wèn)題的討論關(guān)于充要性算法已知進(jìn)程關(guān)于資源活動(dòng)序列困難: 程序中的分枝與循環(huán)復(fù)雜度高(NP Complete)生滅資源問(wèn)題消息消耗性資源與可重用資源并存關(guān)于兩階段封鎖增長(zhǎng)階段有可能死鎖5.12 饑餓與活鎖饑餓(starvation)：當(dāng)?shù)却龝r(shí)間給進(jìn)程推進(jìn)和響應(yīng)帶來(lái)明顯影響時(shí),稱發(fā)生了進(jìn)程饑餓.饑餓到一定程度的進(jìn)程所賦予的使命即使完成也不再具有實(shí)際意義時(shí)稱該進(jìn)程被餓死(starved to death).沒(méi)有時(shí)間上界的等待排隊(duì)等待忙式等待忙式等待條件下發(fā)生的饑餓,稱為活鎖(live lock).死鎖與饑

21、餓饑餓 vs 死鎖死鎖進(jìn)程處于等待狀態(tài)，忙式等待的進(jìn)程并非處于等待狀態(tài), 但卻可能被餓死;死鎖進(jìn)程等待永遠(yuǎn)不會(huì)釋放的資源, 餓死進(jìn)程等待可能被釋放,但卻不會(huì)分給自己的資源,其等待時(shí)間沒(méi)有上界;死鎖一定發(fā)生了循環(huán)等待,餓死不然;死鎖至少涉及兩個(gè)進(jìn)程, 餓死進(jìn)程可能只有一個(gè).5.13 死鎖的例子過(guò)河問(wèn)題：水流12 n-1nWestEastW-EE-WDeadlock prevention: one direction at any time.過(guò)河問(wèn)題Var west_crossing,east_crossing:integer; (0,0) west_wait, east_wait:integer

22、; (0,0); wq, eq: semaphore; mutex:semaphore;西面過(guò)河者活動(dòng)： P(mutex); If east_crossing0 Then Begin west_wait:=west_wait+1; V(mutex); P(wq) End; Else Begin west_crossing:=west_crossing+1; V(mutex) End; 過(guò)河； P(mutex); west_crossing:=west_crossing-1; If west_crossing=0 Then While east_wait 0 Do Begin east_wait

23、:=east_wait-1; east_crossing:=east_crossing+1; V(eq); End; V(mutex);過(guò)河問(wèn)題過(guò)河問(wèn)題東面過(guò)河者活動(dòng)： P(mutex); If west_crossing0 Then Begin east_wait:=east_wait+1; V(mutex); P(eq) End Else Begin east_crossing:=east_crossing+1; V(mutex) End;過(guò)河問(wèn)題 過(guò)河； P(mutex); east_crossing:=east_crossing-1; If east_crossing=0 Then W

24、hile west_wait 0 Do Begin west_wait:=west_wait-1; west_crossing:=west_crossing+1; V(wq); End; V(mutex);思考問(wèn)題對(duì)于過(guò)河問(wèn)題，考慮一個(gè)沒(méi)有餓死情況的解法。例2. 過(guò)河問(wèn)題(2)水流WestEast12 6587341-2-3-4-6-55-6-7-8-2-1要求: (1)無(wú)死鎖; (2)無(wú)餓死; (3)并行度高。WE:P(S);P(s1);走到1;P(s2);走到2;V(s1);P(s3);走到3；V(s2);P(s4);走到4；EW:P(S);P(s5);走到5;P(s6);走到6;V(s5

25、);P(s7);走到7；V(s6);P(s8);走到8；V(s3);P(s5); P(s6);走到6;V(s4);走到5;V(s6);走到E;V(s5);V(S);V(s7);P(s1); P(s2);走到2;V(s8);走到1;V(s2);走到W;V(s1);V(S);Var S, s1,s2,s3,s4,s5,s6,s7,s8:semaphore; (5,1,1,1,1,1,1,1,1)5.14 簡(jiǎn)單組合資源死鎖的靜態(tài)分析條件：已知各個(gè)進(jìn)程有關(guān)資源的活動(dòng)序列；判斷：有無(wú)死鎖可能性。步驟1：以每個(gè)進(jìn)程占有資源，申請(qǐng)資源作為一個(gè)狀態(tài)， 記作：(pi：aj：ak1,akn)=(進(jìn)程：請(qǐng)求：占有);步驟2：以每個(gè)狀態(tài)為一個(gè)節(jié)點(diǎn)；步驟3：如s1所申請(qǐng)資源為s2所占有，則由s1向s2畫一有向 弧（相同進(jìn)程間不畫）；步驟4：找出所有環(huán)路；步驟5：判斷環(huán)路上狀態(tài)是否能同時(shí)到達(dá)，如是有死鎖可能