操作系统课件：05第五章 死锁与饥饿

1、第五章 死锁与饥饿死锁与饥饿死锁: indefinite wait.可察觉饥饿: not necessarily in wait state.?死锁和饥饿都是由于进程竞争资源而引起的. 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、。定义死锁时刻：无限等待发生时；等待发生前（已注定死锁）。由定义得到的结论几个有用的结论：参与死琐的进程至少有二个；每个参与死锁的进程均等待资源；参与死锁的进程中至少有两个进程占有资源；死锁进程是系统中当前进程集合的一个子集。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, 释放 a P1: a a a a a a

3、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 死锁的条件Coffman条件（必要条件）资源独占（mutual exclusion）不可抢占（non preemption）保持申请（hold-while-applying）循环等待（circular wait）当每类资源只有一个实例时，充要条件。破坏上述任意一个条件可以消除死锁。5.4 死锁的处理死锁预防（deadlock p

4、revention）-静态死锁避免（deadlock avoidance）-动态死锁检测（deadlock detection）死锁恢复（deadlock recovery）5.5 资源分配图定义: G=(V,E), V=PR, P=p1,p2,pn, R=r1,r2,rm, E=(pi,rj)(rj,pi), piP, rjR. 申请边(pi,rj): pi申请rj； 分配边(rj,pi): rj分配pi;图示： 进程： 资源： 申请边：由进程到资源类； 分配边：由资源实例到进程。5.5 资源分配图申请：pi申请rj中的一个资源实例，由pi向rj画一条申请边，如可满足，改为分配边。释放：去掉

5、分配边。例子（无环路，无死锁）例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例子（有环路，有死锁）p1p2p3r1r3r2r4增加边（p3,r2)例子（有环路，无死锁）p1p2p3p4r1r2例子（有环路，无死锁）p1p2p3p4r1r2P2释放占有资源r1, 分给P1, (p1,r1)改为(r1,p1)5.5.2 资源分配图的约简寻找一个非孤立且没有请求边的节点pi, 若无算法结束去除pi的所有分配边使其成为一个

6、孤立节点;寻找所有请求边都可满足的进程pj, 将pj的所有请求边全部改为分配边;转步骤1死锁定理若算法结束时,所有节点均为孤点,则称资源分配图是完全可约简的,否则称为不可完全约简的.死锁定理:S为死锁状态的充分必要条件是S的资源分配图不可完全约简.5.6 死锁预防 对进程有关资源的活动加限制，所有进程遵循这种限制，即可保证没有死锁发生。优点：简单，系统不需要做什么。缺点：对进程的约束，违反约束仍可能死锁。预防方法：预先分配法；有序分配法。5.6.1 预先分配法进程：运行前申请所需全部资源；系统：能够满足，全部分配，否则，一个也不分配。破坏“hold-and-wait”条件缺点：资源利用效率低；

7、一次提出申请困难。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: p2无限等待rk2中的资源实例，被p3占有； tn: pn无限等待rkn中的资源实例，被p1占有; 根据有序申请假设： F(rk1)F(

8、rk2)F(rkn)F(rk1)矛盾。5.6.2 有序分配法优点与预先分配相比,资源利用率提高.缺点资源编号困难;为保持按序申请,某些暂时不用的资源也需提前申请, 牺牲资源利用率.例子DBACW:直行E：左转S：左转死锁的可能性：情形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);

9、 驶入A; V(S2); P(S4); 驶入C； V(S3); 驶出C; V(S4);Procedure W: P(S1); P(S4); 驶入C; 驶入D； 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.进程：事先申明所需资源最大量（并不分配） Clai

10、m=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; /尚需资源 Request: array1.n,1.mof integer; /当前请求临时变量： Work: array1.mo

11、f 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不满足，等待Available:=Available-RequestIAllocationI:=AllocationI+RequestINeedI:=NeedI-RequestI安全确认，pi继续Available:=Ava

12、ilable+RequestIAllocationI:=AllocationI-RequestINeedI:=NeedI+RequestIpi等待FTFTTF安全性检测算法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:安全进程序列：p2请求：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:假定分配：安全进程序列：，确认分配；p4请求：Request4=(3,3,0), 不能满足，等待；p0请求：Request0=(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

15、), 安全，分配。银行家算法的保守性银行家算法的保守性Request2=(0,1), 不安全，不分配，（分配不导致死锁） 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 Complete)。Remarks3: 预先给出进程有关资源的命令序列是困难

16、的(程序的分枝和循环）。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:=false;有满足条件的i:Finishi=falseRequestiWorkFinishi=true;Work:=Work+AllocationiTi ,f

17、inishi=trueTFF无死锁死锁FinishI=truefor allocationI=0Remarks1. 上述算法可以检测到参与死锁的全部进程，包括占有资 源和不占有资源的进程。2. 如果希望只检测占有资源的进程，初始化时： Finishi=true, for AllocationI=0Remarks令P是所有进程的集合，P包含于P是所有占有资源的进程集合，则:P死锁P死锁。死锁检测之后是恢复，只考虑P中的进程。死锁检测不考虑P-P中的进程，缩小了检测范围，降低了系统开销。死锁例子例子：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 未死锁。此时，Request2=(0,0,1), 死锁，参与死锁进程p1,p2,p3,p45.8.2 死锁检测时刻考虑因素： 死锁发生频度； 死锁发生迹象（如进程等待时间过久）。1. 等待时检测： 发现早，恢复代价小，开销大（overhead)。2. 定时检测：3. 资源（eg. CPU）利用率下降时检测；4. 交互式任务没有响应

19、时检测。5.9 死锁的恢复1. 重新启动 简单，代价大，涉及未参与死锁的进程。2. 终止进程(process termination) 环路上占有资源的进程。 (1) 一次性全部终止；(2) 逐步终止（优先级，代价函数）3. 剥夺资源(resource preemption)+进程回退(rollback) (1) select a victim；(2) rollback. 问题: (1) 保存snapshot代价大；(2) 消除影响困难; (3) starvation.5.10 鸵鸟算法视而不见Pro:工程师观点(考虑死锁发生的频率,危害,处理代价)死锁发生频率危害Cont:数学家观点必须处理

20、,无论代价如何目前系统实际如此Eg. UNIX proc结构(50 and up)5.11 有关问题的讨论关于充要性算法已知进程关于资源活动序列困难: 程序中的分枝与循环复杂度高(NP Complete)生灭资源问题消息消耗性资源与可重用资源并存关于两阶段封锁增长阶段有可能死锁5.12 饥饿与活锁饥饿(starvation)：当等待时间给进程推进和响应带来明显影响时,称发生了进程饥饿.饥饿到一定程度的进程所赋予的使命即使完成也不再具有实际意义时称该进程被饿死(starved to death).没有时间上界的等待排队等待忙式等待忙式等待条件下发生的饥饿,称为活锁(live lock).死锁与饥

21、饿饥饿 vs 死锁死锁进程处于等待状态，忙式等待的进程并非处于等待状态, 但却可能被饿死;死锁进程等待永远不会释放的资源, 饿死进程等待可能被释放,但却不会分给自己的资源,其等待时间没有上界;死锁一定发生了循环等待,饿死不然;死锁至少涉及两个进程, 饿死进程可能只有一个.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

22、; (0,0); wq, eq: semaphore; mutex:semaphore;西面过河者活动： 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; 过河； 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);过河问题过河问题东面过河者活动： 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 W

24、hile west_wait 0 Do Begin west_wait:=west_wait-1; west_crossing:=west_crossing+1; V(wq); End; V(mutex);思考问题对于过河问题，考虑一个没有饿死情况的解法。例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);走到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 简单组合资源死锁的静态分析条件：已知各个进程有关资源的活动序列；判断：有无死锁可能性。步骤1：以每个进程占有资源，申请资源作为一个状态， 记作：(pi：aj：ak1,akn)=(进程：请求：占有);步骤2：以每个状态为一个节点；步骤3：如s1所申请资源为s2所占有，则由s1向s2画一有向 弧（相同进程间不画）；步骤4：找出所有环路；步骤5：判断环路上状态是否能同时到达，如是有死锁可能