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

1、第五章 死锁与饥饿 死锁与饥饿 死 锁: indefinite wait. 饥 饿: not necessarily in wait state. 死锁和饥饿都是由于进程竞争资源而引起的。 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定 义: 一组进程中的每一个进程, 均无限期地等待此组进程中 某个其它进程占有的、 因而永远无法得到的资源,

2、 这种现象称为进程死锁。定义死锁时刻: 无限等待发生时; 等待发生前(已注定死锁)。5.1 死锁的概念(Cont.)几个有用的结论:参与死琐的进程至少有 2 个;每个参与死锁的进程均等待资源;参与死锁的进程中至少有 2 个进程占有资源;死锁进程是系统中当前进程集合的一个子集。5.1 死锁的概念(Cont.)5.2 死锁的类型1. 竞争资源引起的死锁 不同种资源 BAW直行E左转S左转DC 同种资源： 4台打印机。 申请: a 释放：a P1: a a a a a a a a P2: a a a a5.2 死锁的类型(Cont.)2. 进程通信引起的死锁 P1：receive(P2,M1); P

3、2: receive(P3,M2); P3: receive(P1,M3);其它原因引起的死锁After you / after you5.3 死锁的条件Coffman条件(必要条件):资源独占(mutual exclusion)不可抢占(non preemption)保持申请(hold-and-applying)循环等待(circular wait) 当每类资源只有一个实例时, 充要条件。 破坏上述任意一个条件可以消除死锁。5.4 死锁的处理死锁预防(deadlock prevention) 静态: 进程有关资源的活动按某种协议加以限制, 若所有进程都遵守该协议, 即可保证不发生死锁。死锁避

4、免(deadlock avoidance) 动态: 实时检测进程的资源申请, 拒绝不安全的请求, 保证不发生死锁。死锁检测(deadlock detection)死锁恢复(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资源分配图图示：进 程: 资源类:申请边: 进程到资源类;分配边: 由资源实例到进程;申 请: pi 申请 rj 中的一个资源实例, 由 pi 向 rj 画一条申请边, 如可满足, 改为分配边。释 放: 去掉分配边。5.5 资源分配图(Cont.)例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) 5.5 资源分配图(Cont.)例

6、5.2 增加边(p3,r2)P3P2P1r4r3r2r1发生死锁5.5 资源分配图(Cont.)例5.3 (有环路, 无死锁)P1P2P3r1r2图 1. 有环路, 无死锁P1P2P3r1r2图 2. P2释放r1，r1分配给P35.5 资源分配图(Cont.)5.5.2 资源分配图的约简约简方法： 寻找一个非孤立、且没有请求边的进程节点 Pi , 若无则算法结束; 去除所有 Pi 的分配边, 使 Pi 成为一个孤立节点; 寻找所有请求边均可满足的进程 Pj , 将 Pj 的请求边全部改为分配边; 转步骤 。 对资源分配图G进行约简, 若算法结束时, 图中所有节点均为孤立节点, 则称G为可完全

7、约简的, 否则称G为不可完全约简的。死锁定理: 系统状态 S 为死锁状态的充分必要条件是 S 的资源分配图 是不可完全约简的。5.6 死锁的预防 保证系统不死锁的静态策略 对进程有关资源的活动加限制, 所有进程遵循这种限制, 即可保证没有死锁发生。 优 点: 简单, 系统不需要做什么。 缺 点: 对进程的约束, 违反约束仍可能死锁。 预防方法: 预先分配策略; 有序分配策略。5.6.1 预先分配策略 进程: 运行前申请所需全部资源; 系统: 能够满足, 全部分配; 否则, 一个也不分配。 思想: 破坏“hold-and-apply”条件。 缺点: 资源利用效率低; 一次提出申请困难： 程序不同

8、分支可能需要申请不同资源。5.6.2 有序分配策略资源类集: R = r1 , r2 , , rn 函数: f : RN例如: R = scanner , tape , printer f (scanner) = 1 ; f (tape) = 2 ; f (printer) = 3 ;假定: f (r1) f(r2) f (rn), 则对任一进程按有序分配法申请资源的顺序如下:有序分配法: 进程 Pi 可以申请资源 rj 中的实例 rl, Pi 当前占有rl , f(rl) f(rj)。r1r2rjrn.申请次序证明：有序分配法无死锁(deadlock free)。反证: 假定死锁, 则出现循

9、环等待, 即在时刻5.6.2 有序分配策略(Cont.)t1: p1无限等待rk1中的资源实例, 被p2占有;t2: p2无限等待rk2中的资源实例, 被p3占有;t3: p3无限等待rk3中的资源实例, 被p4占有; .tn: pn无限等待rkn中的资源实例, 被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) 优 点与预先分配相比, 资源利用率提高。 缺 点 资源编号困难; 按号申请增加使用者负担, 一旦不按号申请仍可能死锁; 为保持按序申请, 某些暂时

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个信号量分别对应D、B、A、C的互斥进入。5.6.2 有序分配法(Cont.)BAW直行E左转S左转DC有序分配法预防死锁例S2WS1E死锁的可能性SWE2E1可能性1:可能性2:Procedure S: P(S1); 驶入D； P(S2); 驶入B; V(S1); P(S3); 驶入A； V(S2)

11、; 驶出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； 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 死锁的避免动态检测策略: 进程申请资源不限制, 对能满足的申请要求进行动态检测,若安全则分配, 否则不分配

12、。可满足请求 分 配不安全检 测安 全 不分配5.7.1 安全状态与 安全进程序列安全状态: 如果系统中所有进程能按某种次序依次运行完, 则称系统处于安全状态。形式定义: 如果存在一个由系统中所有进程构成的安全进程序列 , 则称系统处于安全状态。对进程序列, 如果有: pi要申请的资源数当前剩余资源数 pj当前占有资源数则称该进程序列是安全的。ji安全状态不安全状态死锁状态Bankers algorithm (E.W. Dijkstra)进程: 事先申明所需资源最大量(并不分配) Claim=Max系统: 对每个可满足的资源申请命令进行安全性检查。 安全: 分配; 不安全: 不分配状况: P

13、= p1 , p2 , , pn ; R = r1 , r2 , , rm ;5.7.2 银行家算法数据结构: int availablem; /系统可用资源 int claimn, m; /进程最大需求 int allocationn, m; /进程当前已分配资源 int needn, m; /进程尚需要的资源 int request n, m; /进程当前请求的资源临时变量(安全检查时用): int workm; /可分配资源和已分配资源之和 int finishn; /检查时标识是否有未完成进程5.7.2 银行家算法(Cont.)定义如下数组操作:设X、Y是下标为 1k 的一维数组, 定

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确认分配，pi 继续算法结束TRequestiAvailableTAvailable -= Requesti;Allocationi += Requesti;Needi -= Requesti;T预分配Available += Requesti;Allocation

15、i -= Requesti;Needi += Requesti;F取消预分配申请无法满足进程 pi 等待F申请导致不安全进程 pi 等待5.7.2 银行家算法(Cont.)安全检查算法Work = Available;Finish = 0;有满足条件的 j ：Finishj=0Needj Work返回“不安全”结 束Fj ,finishj=1F返回“安全”结 束TFinishj=1; Work+= AllocationjT找出一个“安全进程序列”Pj1、 Pj1、 Pjn5.7.2 银行家算法(Cont.)例 5.4 资源 R = A (10) , B (5) , C(7) 进程 P = p0

16、 , p1 , p2 , p3 , p4 某时刻系统状态：134200334P4110112222P3206003209P2221002223P1333247110357P0CBACBACBACBAAvailableNeedAllocationClaimRP试判断上述系统状态是否安全？并找出该状态下的安全进程序列。5.7.2 银行家算法(Cont.)对上述系统状态运行安全检查算法，首先找到j=1，状态如下：3C3B5AWork0134200334P40110112222P30206003209P21221002223P10247110357P0CBACBACBAFinishNeedAlloca

17、tionClaimRP5.7.2 银行家算法(Cont.)第二次找到j=3，状态如下：4C4B7AWork0134200334P41110112222P30206003209P21221002223P10247110357P0CBACBACBAFinishNeedAllocationClaimRP5.7.2 银行家算法(Cont.)第三次找到j=4，状态如下：6C4B7AWork1134200334P41110112222P30206003209P21221002223P10247110357P0CBACBACBAFinishNeedAllocationClaimRP5.7.2 银行家算法(C

18、ont.)第四次找到j=2，状态如下：6C4B10AWork1134200334P41110112222P31206003209P21221002223P10247110357P0CBACBACBAFinishNeedAllocationClaimRP5.7.2 银行家算法(Cont.)第五次找到 j=0，状态如下：7C5B10AWork1134200334P41110112222P31206003209P21221002223P11247110357P0CBACBACBAFinishNeedAllocationClaimRP所有Finishj均为1，则最初系统状态是安全状态，并且找到的安全进

19、程序列为：实际上，也是安全进程序列。因此，系统安全状态下，安全进程序列不唯一。5.7.2 银行家算法(Cont.)134200334P4110112222P3206003209P2221002223P1333247110357P0CBACBACBACBAAvailableNeedAllocationClaimRP在系统最初状态下，假设进程P2有资源请求Request2=(1,0,2)，为避免死锁，该请求是否可以满足？5.7.2 银行家算法(Cont.)134200334P4110112222P3005204209P2221002223P1132247110357P0CBACBACBACBAAv

20、ailableNeedAllocationClaimRP在系统最初状态下，对资源请求Request2=(1,0,2)，进行预分配，使系统变为如下状态：可找到安全进程序列，故请求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)。某时刻系统状态如下：110011P210100111P1BABABA

21、BAAvailableNeedAllocationClaimRP5.7.2 银行家算法(Cont.)考虑 request2 = (0 , 1)，预分配后系统状态如下：011011P200100111P1BABABABAAvailableNeedAllocationClaimRP上一系统状态，经安全检查为不安全状态，故 request2 = (0 , 1)不分配。实际上，即使分配也不是一定导致死锁。结论：不安全状态不一定会导致死锁。 亦即，死锁状态是不安全状态的真子集。5.8 死锁的发现 系统未采用: 死锁预防策略; 死锁避免策略。 可能发生死锁 死锁检测和恢复5.8.1 死锁检测算法系统状况:

22、 P = p1 , p2 , , pn ; R = r1 , r2 , , rm ;数据结构: int Availablem ; int Allocation n , m ; int Request n , m ; /记录当前各进程申请资源数临时变量： int Workm ; int Finishn ;5.8.1 死锁检测算法(Cont.)死锁检测算法Work = Available; i,Finishi=(Allocationi0) ? 0 : 1有满足条件的 i ：Finishi=0Requesti Work发现死锁返回Fi ,Finishi=1F无死锁返回TFinishi=1; Work

23、+= AllocationiT定理：P是进程集合，PP占有资源集合。P中存在死锁P中存在死锁。5.8.1 死锁检测算法(Cont.)例 5.6 资源 R = A (7) , B (3) , C(6) 进程 P = p0 , p1 , p2 , p3 , p4 某时刻系统状态：200200P4001112P3000303P2202002P1010000010P0CBACBACBAAvailableRequestAllocationRP试判断上述系统状态是否处于死锁状态？5.8.1 死锁检测算法(Cont.)200200P4001112P3000303P2202002P1020000010P0CB

24、ACBACBAWorkRequestAllocationRPFinish10000对上述系统状态运行死锁检测算法，首先找到i=0，状态如下：5.8.1 死锁检测算法(Cont.)第二次找到i=2，状态如下：200200P4001112P3000303P2202002P1323000010P0CBACBACBAWorkRequestAllocationRPFinish101005.8.1 死锁检测算法(Cont.)第三次找到i=3，状态如下：200200P4001112P3000303P2202002P1435000010P0CBACBACBAWorkRequestAllocationRPFin

25、ish101105.8.1 死锁检测算法(Cont.)第四次找到i=1，状态如下：200200P4001112P3000303P2202002P1437000010P0CBACBACBAWorkRequestAllocationRPFinish111105.8.1 死锁检测算法(Cont.)第五次找到i=4，状态如下：200200P4001112P3000303P2202002P1637000010P0CBACBACBAWorkRequestAllocationRPFinish11111得到进程序列，所有Finishi均为1。因此，最初系统状态无死锁。5.8.1 死锁检测算法(Cont.)如果

26、在最初系统状态：200200P4001112P3000303P2202002P1010000010P0CBACBACBAAvailableRequestAllocationRP进程 p2 有请求：Request2=(0,0,1) ，通过死锁检测算法检测，则发生死锁，参与死锁进程p1,p2,p3,p4在最初系统状态下，进程 p2 的请求Request2=(0,0,1) 系统无法满足，此时系统的资源分配图如下：A(0) 2, 3, 2B(1) 1, 1C(0) 3, 1, 2P1P4P3P0P2221125.8.1 死锁检测算法(Cont.)5.8.2 死锁检测时刻 考虑因素: 死锁发生的频度;

27、死锁影响的进程个数。 检测时刻: 等待时检测: 发现早, 恢复代价小, 开销大(overhead)。 定时检测; 资源(eg. CPU)利用率下降时检测。5.9 死锁的恢复1. 重新启动(system restart) 简单，代价大，涉及未参与死锁的进程。2. 终止进程(terminating processes) 终止参与死锁、占有资源的进程： 一次性全部终止； 逐步终止(优先级&代价函数)。3. 剥夺资源(preempting resource) 逐步剥夺； 一次性全部剥夺。4. 进程回退(process rollback) select a victim； rollback. 问题: 保

28、存snapshot代价大； 消除影响困难; 可能造成进程“饥饿”(starvation)。5.10 鸵鸟算法 Ostrich algorithm： 对死锁视而不见, 当死锁真正发生且影响系统正常运行时, 手工干预(重新启动)。 不同观点 工程师观点(考虑死锁发生的频率,危害,处理代价) 死锁发生频率 危害。 数学家观点：必须处理,无论代价如何 目前系统实际如此Eg. UNIX proc结构(PCB)及交换机制存在死锁隐患。5.11 有关问题的讨论 关于充要性算法预防策略: 进程违反协议也可能死锁。避免策略: 开销大, 非必要性算法(保守算法)。充要性算法: 已知进程所需资源最大量及其资源活动序

29、列； 困难: 程序中的分枝与循环; 复杂度高 (NP Complete)。 生灭资源(或消耗性资源)问题资源: 可重用资源；生灭资源(消息): 超时处理;死锁要考虑两类资源, 增加了复杂性。可剥夺资源问题：不会因为进程竞争CPU而死锁； 在虚拟存储支持下，不会因为竞争内存而死锁。 关于两阶段锁 两阶段封锁协议: 增长阶段（加锁）和消退阶段（开锁）; 增长阶段有可能发生死锁。一组进程中的每个进程，均无限期地等待这组中的其它进程引发的事件，这种现象叫死锁。5.12 饥饿与活锁由于资源分配策略的不公平， 可能造成进程没有时间上界的等待 排队等待 忙式等待 饥饿(starvation)： 当等待时间给

30、进程推进和响应带来明显影响时, 称发生了进程饥饿； 饥饿到一定程度的进程所赋予的使命即使完成 也不再具有实际意义时称该进程被饿死 (starved to death).忙式等待条件下发生的饥饿,称为活锁(live lock).饿死 vs 死锁：都是由竞争资源引起。死锁进程处于等待状态, 忙式等待的进程并非处于等待状态, 但却可能被饿死;死锁进程等待永远不会释放的资源, 饿死进程等待可能被释放,但却不会分给自己的资源,其等待时间没有上界;死锁一定发生了循环等待,饿死不然;死锁至少涉及两个进程, 而饥饿或饿死进程可能只有一个。 防止饥饿或饿死的资源分配策略如： 先到先服务和动态优先级调度5.12

31、饥饿与活锁(Cont.)5.13 可复用资源 死锁的静态分析 可复用资源：一次只能分配给一个进程使用的资源。 称为可复用资源(reusable resource)。 组合资源：由相对独立的若干资源构成的资源集合 称为组合资源。 其中每个相对独立的资源称为子资源。 同种组合资源：由相同类型的子资源构成的组合资源 称为同种组合资源。 简单组合资源：每类子资源只有一个实例的组合资源 称为简单组合资源。5.13 可复用资源 死锁的静态分析(Cont.)步骤1：以每个进程占有资源、申请资源作为一个状态， 记作: (pi: aj: ak1,akn)=(进程: 请求: 占有序列) ;步骤2：以每个状态为一个

32、节点；步骤3：如 s1 所申请资源为 s2 所占有，则由 s1 向 s2 画一有 向边(相同进程间不画) ;步骤4：找出所有环路 ;步骤5：判断环路上状态是否能同时到达， 如是有死锁可能性，否则无死锁可能性。 环路中有相同进程，不能到达； 环路中有相同被占有资源，不能到达。 可复用简单组合资源死锁的静态分析算法 条 件：已知各个进程有关资源的活动序列； 判 断：有无死锁可能性。5.13 可复用资源 死锁的静态分析(Cont.)例5-7：死锁分析例子已知: R = A，B，C，D，E，F，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根据步骤1和步骤2有如下状态节点：出现环路，可能死锁。5.13 可复用资源 死锁的静态分析(Cont.)死锁分析：判断环路上的状态是否可以同时到达。 即：p1, p2, p3三个进程是否可以同时到达红色位置。证明: 假设 p1, p2, p3 三个进程可以同时到达红线位置, 则 p1, p2, p3 三个进程可以同时到达蓝线位置, 根据蓝线位置的资源申请情况，并考虑简单组合资源， 则各进程推进到蓝线的进度为： p3先于p2,

34、p2先于p1, 则 p3先于p1; 又 p1先于p3。矛盾。 所以： p1, p2, p3 三个进程不可能同时到达环路中的状态， 即不能发生死锁。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 : 资源数量 ;N : 使用该类资源进程的数量 ; : 所有进程所需要该类资源的总量；则：当 M + N 时, 一定没有死锁； 当 M + N 时, 至少有一个交叉有死锁。证明: 假定发生了死锁， 且 n 个进程参与了死锁 (2 n N), 则: 参与死锁进程所需资源数 M + n ; 未参与死锁进程

35、所需资源的总量 使用该类资源但未参与死锁的进程数= N-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年计算机专业

36、综合试卷试题25题 25. 某计算机系统中有8台打印机，由K个进程竞争使 用，每个进程最多需要3台打印机。该系统可能会 发生死锁的K的最小值是 A2 B3 C4 D5 解：依题意，M=8, N=K, =K3。 按必要条件： M + N, 即 3K 8K 成立时，可能发生死锁。 K 45.15 死锁与饥饿的例子例5-9. 哲学家就餐问题(Dining Philosophers Problem) Proposed and solved by E.W. Dijkstra , in 1965.Roomph0ph4ph3ph2ph1f0f4f3f2f1哲学家活动:While(1) 思考 ; 进食 ; 哲

37、学家活动(包含资源活动)While(1) 思考 ; 取左叉; 取右叉; 进食; 放左叉; 放右叉; 进 食: 需要“叉子”；叉 子: 不同种组合资源， 因为区别左、右叉子。5.15 死锁与饥饿的例子(Cont.)Roomph0ph4ph3ph2ph1f0f4f3f2f1死锁情况：每位哲学家都拿到左叉，等待右叉。5.15 死锁与饥饿的例子(Cont.)死锁解决方法(预先分配): 同时申请左、右两把叉子;哲学家状态描述(增加 hungry 状态): #define N 5 typedef enum action thinking, hungry, eating ; action state N ;

38、等待队列设置(每个哲学家一个队列) : semaphore self N ; (initial self.value = 0 ) ;5.15 死锁与饥饿的例子(Cont.)共享变量：state; semaphore mutex ; (1)测试 i 号哲学家是否具备进食条件: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 号哲学家活动：void philosopher ( int i ) while(1) think()； pick_forks(i); eat()； put_forks(i); 5.15 死锁与饥饿的例子(Cont.)i号哲学家放叉：void put_forks ( int i ) P ( mutex ) ; state i = thinking ; test ( ( i 1 ) % N ) ; test ( ( i + 1 ) % N ) ; V ( mutex ) ;i 号哲学家取叉：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