05第五章死锁与饥饿1ppt课件

1、第五章第五章 死锁与饥饿死锁与饥饿n死锁与饥饿死锁与饥饿n死锁死锁: indefinite wait.n可觉察可觉察n饥饿饥饿: not necessarily in wait state.n?n死锁和饥饿都是由于进程竞争资源而引死锁和饥饿都是由于进程竞争资源而引起的起的. 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

2、死锁定义死锁定义n一组进程中的每一个进程，均无限期地等待此一组进程中的每一个进程，均无限期地等待此组进程中某个其他进程占有的，因此永远无法组进程中某个其他进程占有的，因此永远无法得到的资源，这种景象称为进程死锁。得到的资源，这种景象称为进程死锁。n定义死锁时辰：定义死锁时辰：n无限等待发生时；无限等待发生时；n等待发生前已注定死锁。等待发生前已注定死锁。由定义得到的结论由定义得到的结论n几个有用的结论：几个有用的结论：n参与死琐的进程至少有二个；参与死琐的进程至少有二个；n每个参与死锁的进程均等待资源；每个参与死锁的进程均等待资源；n参与死锁的进程中至少有两个进程占有参与死锁的进程中至少有两个

3、进程占有资源；资源；n死锁进程是系统中当前进程集合的一个死锁进程是系统中当前进程集合的一个子集。子集。5.2 死锁类型死锁类型1. 竞争资源引起的死锁竞争资源引起的死锁 1不同种资源不同种资源 DBACW:直行直行E：左转：左转S：左转：左转5.2 死锁类型死锁类型1. 竞争资源引起的死锁竞争资源引起的死锁 1不同种资源不同种资源 SSEWW:直行直行E：左转：左转S：左转：左转5.2 死锁类型死锁类型1. 竞争资源引起的死锁竞争资源引起的死锁 1不同种资源不同种资源 SEEWW:直行直行E：左转：左转S：左转：左转5.2 死锁类型死锁类型2同种资源同种资源 4台打印机，恳求台打印机，恳求:a

4、, 释放释放 a P1: a a a a a a a a P2: a a a a5.2 死锁类型死锁类型(Cont.)2. 进程通讯引起的死锁进程通讯引起的死锁 P1：receive(P2,M1); P2: receive(P3,M2); P3: receive(P1,M3);其它缘由引起的死锁其它缘由引起的死锁After you / after you5.3 死锁的条件死锁的条件nCoffman条件必要条件条件必要条件n资源独占资源独占mutual exclusionn不可抢占不可抢占non preemptionn坚持恳求坚持恳求hold-while-applyingn循环等待循环等待cir

5、cular waitn当每类资源只需一个实例时，充要条件。当每类资源只需一个实例时，充要条件。n破坏上述恣意一个条件可以消除死锁。破坏上述恣意一个条件可以消除死锁。5.4 死锁的处置死锁的处置n死锁预防死锁预防deadlock prevention-静态静态n死锁防止死锁防止deadlock avoidance-动态动态n死锁检测死锁检测deadlock detectionn死锁恢复死锁恢复deadlock recovery5.5 资源分配图资源分配图定义定义: G=(V,E), V=PR, P=p1,p2,pn, R=r1,r2,rm, E=(pi,rj)(rj,pi), piP, rjR.

6、 恳求边恳求边(pi,rj): pi恳求恳求rj； 分配边分配边(rj,pi): rj分配分配pi;图示：图示： 进程：进程： 资源：资源： 恳求边：由进程到资源类；恳求边：由进程到资源类； 分配边：由资源实例到进程。分配边：由资源实例到进程。5.5 资源分配图资源分配图n恳求：恳求：pi恳求恳求rj中的一个资源实例，由中的一个资源实例，由pi向向rj画一条恳求边，如可满足，改为分画一条恳求边，如可满足，改为分配边。配边。n释放：去掉分配边。释放：去掉分配边。例子无环路，无死锁例子无环路，无死锁例例1. P=p1,p2,p3, R=r1(1),r2(2),r3(1),r4(3) E=(p1,r

7、1),(p2,r3),(r1,p2),(r2,p1),(r2,p2),(r3,p3), (r4,P3)p1p2p3r1r3r2r4例子有环路，有死锁例子有环路，有死锁p1p2p3r1r3r2r4添加边添加边p3,r2)例子有环路，无死锁例子有环路，无死锁p1p2p3p4r1r2例子有环路，无死锁例子有环路，无死锁p1p2p3p4r1r2P2释放占有资源r1, 分给P1, (p1,r1)改为(r1,p1)5.5.2 资源分配图的约简资源分配图的约简n寻觅一个非孤立且没有恳求边的节点寻觅一个非孤立且没有恳求边的节点pi, 假设无算法终了假设无算法终了n去除去除pi的一切分配边使其成为一个孤立的一切

8、分配边使其成为一个孤立节点节点;n寻觅一切恳求边都可满足的进程寻觅一切恳求边都可满足的进程pj, 将将pj的一切恳求边全部改为分配边的一切恳求边全部改为分配边;n转步骤转步骤1死锁定理死锁定理n假设算法终了时假设算法终了时,一切节点均为孤点一切节点均为孤点,那么那么称资源分配图是完全可约简的称资源分配图是完全可约简的,否那么称否那么称为不可完全约简的为不可完全约简的.n死锁定理死锁定理:nS为死锁形状的充分必要条件是为死锁形状的充分必要条件是S的资源的资源分配图不可完全约简分配图不可完全约简.5.6 死锁预防死锁预防 n对进程有关资源的活动加限制，一切进对进程有关资源的活动加限制，一切进程遵照

9、这种限制，即可保证没有死锁发程遵照这种限制，即可保证没有死锁发生。生。n优点：简单，系统不需求做什么。优点：简单，系统不需求做什么。n缺陷：对进程的约束，违反约束仍能够缺陷：对进程的约束，违反约束仍能够死锁。死锁。n预防方法：预防方法：n预先分配法；预先分配法；n有序分配法。有序分配法。5.6.1 预先分配法预先分配法n进程：运转前恳求所需全部资源；进程：运转前恳求所需全部资源；n系统：系统：n可以满足，全部分配，可以满足，全部分配，n否那么，一个也不分配。否那么，一个也不分配。n破坏破坏“hold-and-wait条件条件n缺陷：缺陷：n资源利用效率低；资源利用效率低；n一次提出恳求困难。一

10、次提出恳求困难。5.6.2 有序分配法有序分配法资源集：资源集：R=r1,r2,rn 函数：函数：F：RN 例如：例如：R=scanner,tape,printer F(scanner)=1; F(tape)=2; F(printer)=3;进程进程pi可以恳求资源可以恳求资源rj中的实例中的实例rl,pi当前占有当前占有rl, F(rl)F(rj)r1r2rkrm.恳求次序恳求次序5.6.2 有序分配法有序分配法证明无死锁证明无死锁deadlock free)：反证，假定死锁反证，假定死锁 时辰时辰t1: p1无限等待无限等待rk1中的资源实例，被中的资源实例，被p2占有；占有； t2: p

11、2无限等待无限等待rk2中的资源实例，被中的资源实例，被p3占有；占有； tn: pn无限等待无限等待rkn中的资源实例，被中的资源实例，被p1占有占有; 根据有序恳求假设：根据有序恳求假设： F(rk1)F(rk2)F(rkn)F(rk1)矛盾。矛盾。5.6.2 有序分配法有序分配法n优点优点n与预先分配相比与预先分配相比,资源利用率提高资源利用率提高.n缺陷缺陷n资源编号困难资源编号困难;n为坚持按序恳求为坚持按序恳求,某些暂时不用的资源也某些暂时不用的资源也需提早恳求需提早恳求, 牺牲资源利用率牺牲资源利用率.例子例子DBACW:直行直行E：左转：左转S：左转：左转死锁的能够性：情形死锁

12、的能够性：情形1，情形，情形2资源编号：资源编号：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); 驶入驶入D； P(S2); 驶入驶入B; V(S1); P(S3); 驶入驶入A； V(S2); 驶出驶出A; V(S3)Procedure E: P(S2); 驶入驶入B； P(S3); 驶入驶入A; V(S2); P(S4); 驶入驶入C； V(S3); 驶出驶出C; V(S4);Procedure W: P(S1); P(S4); 驶入驶入C; 驶入驶入D；

13、V(S4); 驶出驶出D； V(S1);例子例子COBEGIN S1:S; ; Sm:S; E1:E; ; En:E; W1:W; . ; Wo:WCOEND; 5.7 死锁防止死锁防止可满足恳求可满足恳求 分配分配 不分配不分配平安平安不平安不平安系统处于平安形状：存在平安进程序列系统处于平安形状：存在平安进程序列进程序列进程序列平安，平安，p1,p2,pn可依次进可依次进展完。展完。平安平安不平安不平安死锁死锁检测银行家算法银行家算法(Cont.)Bankers algorithm, E.W. Dijkstra.进程：事先声明所需资源最大量并不分配进程：事先声明所需资源最大量并不分配 Cl

14、aim=Max系统：对每个可满足的资源恳求命令进展平安性检查。系统：对每个可满足的资源恳求命令进展平安性检查。 平安平安,分配分配;不平安不平安:不分配不分配 P=p1,p2,pn; R=r1,r2,rm;银行家算法银行家算法(Cont.)数据构造：数据构造： Available: array1.mof integer; /系统可用资源系统可用资源 Claim: array1.n,1.mof integer; /进程最大需求进程最大需求 Allocation: array1.n,1.mof integer; /当前分配当前分配 Need: array1.n,1.mof integer; /尚需

15、资源尚需资源 Request: array1.n,1.mof integer; /当前恳求当前恳求暂时变量：暂时变量： Work: array1.mof integer; Finish: array1.nof boolean;银行家算法银行家算法(Cont.)设设X,Y为下标为下标1.l的一维数组：的一维数组： XY j (1jl), XjYj X:=Y j (1jl), Xj:=Yj X:=c j (1jl), Xj:=c XY j (1jl), XjYj资源分配资源分配Pi恳求资源恳求资源RequestINeedI恳求超量，错返恳求超量，错返RequestIAvailable不满足，等待不

16、满足，等待Available:=Available-RequestIAllocationI:=AllocationI+RequestINeedI:=NeedI-RequestI平安平安确认，确认，pi继续继续Available:=Available+RequestIAllocationI:=AllocationI-RequestINeedI:=NeedI+RequestIpi等待等待FTFTTF平安性检测算法平安性检测算法FWork:=Available;Finish:=false; 有满足条件的有满足条件的j:Finishj=falseNeedjWorkFinishj:=true;Work:

17、=Work+AllocationjT j ,finishj=trueTF平安平安不平安不平安银行家算法例子银行家算法例子R=A(10),B(5),C(7) P=p0,p1,p2,p3,p4 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 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:平安进程序列：平安进程序列：p2恳求：恳求：Req

18、uest2=(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 2 1 1 0 1 14 3 3 0 0 2 4 3 1 P0:p1:p2:p3:p4:假定分配：假定分配：平安进程序列：平安进程序列：，确认分配；，确认分配；p4恳求：恳求：Request4=(3,3,0), 不能满足，等待；不能满足，等待；p0恳求：恳求：Reques

19、t0=(0,2,1), 不平安，取消分配，等待。不平安，取消分配，等待。例子：例子：R=A,B, 恳求恳求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), 平安，分配。平安，分配。银行家算法的保守性银行家算法的保守性银行家算法的保守性银行家算法的保守性Request2=(0,1), 不平安，不分配，分配不导致死锁不平安，

20、不分配，分配不导致死锁 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: 银行家算法要求条件：进程所需资源最大量银行家算法要求条件：进程所需资源最大量, 这个信息这个信息对于充要性分析是不够的。对于充要性分析是不够的。Remarks2: 假设：进程预先给出有关资源的命令序列，那么可以给假设：进程预先给出有关资源的命令序列，那么可以给出死锁防止的充要性算法，复杂度出死锁防止的充要性算法，复杂度NP Complet

21、e)。Remarks3: 预先给出进程有关资源的命令序列是困难的预先给出进程有关资源的命令序列是困难的(程序的分程序的分枝和循环。枝和循环。5.8 死锁的检测死锁的检测数据构造：数据构造： Available: array1.mof integer; Allocation: array1.n,1.mof integer; Request: array1.n,1.mof integer;暂时变量：暂时变量： Work: array1.mof integer; Finish: array1.nof Boolean;5.8.1 死锁检测算法死锁检测算法Work:=Available;Finish:=

22、false;有满足条件的有满足条件的i:Finishi=falseRequestiWorkFinishi=true;Work:=Work+AllocationiT i ,finishi=trueTFF无死锁无死锁死锁死锁FinishI=truefor allocationI=0Remarks1. 上述算法可以检测到参与死锁的全部进程，包括占有资上述算法可以检测到参与死锁的全部进程，包括占有资 源和不占有资源的进程。源和不占有资源的进程。2. 假设希望只检测占有资源的进程，初始化时：假设希望只检测占有资源的进程，初始化时： Finishi=true, for AllocationI=0Remar

23、ksn令令P是一切进程的集合，是一切进程的集合，P包含于包含于P是一是一切占有资源的进程集合，那么切占有资源的进程集合，那么:nP死锁死锁P死锁。死锁。n死锁检测之后是恢复，只思索死锁检测之后是恢复，只思索P中的进中的进程。程。n死锁检测不思索死锁检测不思索P-P中的进程，减少了中的进程，减少了检测范围，降低了系统开销。检测范围，降低了系统开销。死锁例子死锁例子例子：例子：R=A(7),B(3),C(6); P=p0,p1,p2,p3,p4 Allocation Request Available Work Finish A B C A B C A B C A B C p0: 0 1 0 0

24、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 未死锁。未死锁。此时，此时，Request2=(0,0,1), 死锁，参与死锁进程死锁，参与死锁进程p1,p2,p3,p45.8.2 死锁检测时辰死锁检测时辰思索要素：思索要素： 死锁发生频度；死锁发生频度； 死锁发生迹象如进程等待时间过久。死锁发生迹象如进程等待时间过久。1. 等待时检测：等待时检测： 发现早，恢复代价小，开销大发现早，恢复代价小，开销大overhead)。2. 定时检测：定时检测：3. 资源资源eg. CPU利用率下降时检测；利用率下

25、降时检测；4. 交互式义务没有呼应时检测。交互式义务没有呼应时检测。5.9 死锁的恢复死锁的恢复1. 重新启动重新启动 简单，代价大，涉及未参与死锁的进程。简单，代价大，涉及未参与死锁的进程。2. 终止进程终止进程(process termination) 环路上占有资源的进程。环路上占有资源的进程。 (1) 一次性全部终止；一次性全部终止；(2) 逐渐终止优先级，代价函数逐渐终止优先级，代价函数3. 剥夺资源剥夺资源(resource preemption)+进程回退进程回退(rollback) (1) select a victim；(2) rollback. 问题问题: (1) 保管保管

26、snapshot代价大；代价大；(2) 消除影响困难消除影响困难; (3) starvation.5.10 鸵鸟算法鸵鸟算法n视而不见视而不见nPro:n工程师观念工程师观念(思索死锁发生的频率思索死锁发生的频率,危害危害,处置代处置代价价)n死锁发生频率死锁发生频率危害危害nCont:n数学家观念数学家观念n必需处置必需处置,无论代价如何无论代价如何n目前系统实践如此目前系统实践如此nEg. UNIX proc构造构造(50 and up)5.11 有关问题的讨论有关问题的讨论n关于充要性算法关于充要性算法n知进程关于资源活动序列知进程关于资源活动序列n困难困难: 程序中的分枝与循环程序中的

27、分枝与循环n复杂度高复杂度高(NP Complete)n生灭资源问题生灭资源问题n音讯音讯n耗费性资源与可重用资源并存耗费性资源与可重用资源并存n关于两阶段封锁关于两阶段封锁n增长阶段有能够死锁增长阶段有能够死锁5.12 饥饿与活锁饥饿与活锁n饥饿饥饿(starvation)：当等待时间给进程推进和：当等待时间给进程推进和呼应带来明显影响时呼应带来明显影响时,称发生了进程饥饿称发生了进程饥饿.饥饿饥饿到一定程度的进程所赋予的使命即使完成也不到一定程度的进程所赋予的使命即使完成也不再具有实践意义时称该进程被饿死再具有实践意义时称该进程被饿死(starved to death).n没有时间上界的等

28、待没有时间上界的等待n排队等待排队等待n忙式等待忙式等待n忙式等待条件下发生的饥饿忙式等待条件下发生的饥饿,称为活锁称为活锁(live lock).死锁与饥饿死锁与饥饿n饥饿饥饿 vs 死锁死锁n死锁进程处于等待形状，忙式等待的进死锁进程处于等待形状，忙式等待的进程并非处于等待形状程并非处于等待形状, 但却能够被饿死但却能够被饿死;n死锁进程等待永远不会释放的资源死锁进程等待永远不会释放的资源, 饿死饿死进程等待能够被释放进程等待能够被释放,但却不会分给本人但却不会分给本人的资源的资源,其等待时间没有上界其等待时间没有上界;n死锁一定发生了循环等待死锁一定发生了循环等待,饿死不然饿死不然;n死

29、锁至少涉及两个进程死锁至少涉及两个进程, 饿死进程能够只饿死进程能够只需一个需一个.5.13 死锁的例子死锁的例子过河问题：过河问题：12 n-1nWestEastW-EE-WDeadlock prevention: one direction at any time.过河问题过河问题Var west_crossing,east_crossing:integer; (0,0) west_wait, east_wait:integer; (0,0); wq, eq: semaphore; mutex:semaphore;西面过河者活动：西面过河者活动： P(mutex); If east_cro

30、ssing0 Then Begin west_wait:=west_wait+1; V(mutex); P(wq) End; Else Begin west_crossing:=west_crossing+1; V(mutex) End; 过河；过河； P(mutex); west_crossing:=west_crossing-1; If west_crossing=0 Then While east_wait 0 Do Begin east_wait:=east_wait-1; east_crossing:=east_crossing+1; V(eq); End; V(mutex);过河问

31、题过河问题过河问题过河问题东面过河者活动：东面过河者活动： 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;过河问题过河问题 过河；过河； P(mutex); east_crossing:=east_crossing-1; If east_crossing=0 Then While west_wait 0 Do Begin west_wait:=west_wait-1

32、; west_crossing:=west_crossing+1; V(wq); End; V(mutex);思索问题思索问题n对于过河问题，思索一个没有饿死情况对于过河问题，思索一个没有饿死情况的解法。的解法。例例2. 过河问题过河问题(2)WestEast12 6587341-2-3-4-6-55-6-7-8-2-1要求要求: (1)无死锁无死锁; (2)无饿死无饿死; (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);走到走到

33、6;V(s5);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 简单组合资源死锁的静态分析简单组合资源死锁的静态分析条件：知各个进程有关资源的活动序列；条件：知各个进程有关资源的活动序列；判别：有无死锁能够性。判别：有无死锁能够性。步骤步骤1：以每个进程占有资源，恳求资源作为一个形状，：以每个进程占有资源，恳求资源作为一个形状， 记作：记作：(pi：aj：ak1,akn)=(进程：恳求：占有进程：恳求：占有);步骤步骤2：以每个形状为一个节点；：以每个形状为一个节点；步骤步骤3：如：如s1所恳求资源为所恳求资源为s2所占有，那么由所占有，那么由s1向向s2画一有画一有向向 弧一样进程间不画；弧一样进程间不画；步骤步骤4：找出一切环路；：找出一切环路；步骤步骤5：判别环路上