06 第五章 死锁与饥饿.pptx

第1页：第五章死锁与饥饿

• 死锁与饥饿
  • 死锁:indefinite wait.
  • 饥饿:not necessarily in wait state.
• 死锁和饥饿都是由于进程竞争资源而引起的。

第2页：5.1死锁的概念例子

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

第3页：5.1 死锁的概念

• 定义:一组进程中的每一个进程,均无限期地等待此组进程中某个其它进程占有的、因而永远无法得到的资源,这种现象称为进程死锁。定义死锁时刻:
• 无限等待发生时;
• 等待发生前(已注定死锁)。

第4页：5.1 死锁的概念（续）

• 几个有用的结论:
• 参与死琐的进程至少有2个;
• 每个参与死锁的进程均等待资源;
• 参与死锁的进程中至少有2个进程占有资源;
• 死锁进程是系统中当前进程集合的一个子集。

第5页：5.2 死锁的类型

1.竞争资源引起的死锁⑴不同种资源BAW直行E左转S左转DC⑵同种资源：4台打印机。申请: a释放：aP1:a a aa a a a aP2:aa a a

第6页：5.2 死锁的类型（续）

• 2.进程通信引起的死锁P1：receive(P2,M1);P2: receive(P3,M2);P3: receive(P1,M3);
• 3.其它原因引起的死锁1.After you / after you

第7页：5.2 死锁的类型（续3）

• 5.3死锁的条件Coffman条件(必要条件):
• 1.资源独占(mutual exclusion)
• 2.不可抢占(non preemption)
• 3.保持申请(hold-and-applying)
• 4.循环等待(circular wait)
  • 当每类资源只有一个实例时,充要条件。
  • 破坏上述任意一个条件可以消除死锁。

第8页：5.4 死锁的处理

• 死锁预防(deadlock prevention)静态:进程有关资源的活动按某种协议加以限制,若所有进程都遵守该协议,即可保证不发生死锁。
• 死锁避免(deadlock avoidance)动态:实时检测进程的资源申请,拒绝不安全的请求,保证不发生死锁。
• 死锁检测(deadlock detection)
• 死锁恢复(deadlock recovery)

第9页：5.5 资源分配图

5.5.1资源分配图的定义:资源分配图是有向图G = ( V , E ) ,其中V = P∪R , P = { p1, p2, … , pn} ,R = { r1, r2, … , rm} ,E = { ( pi, rj) }∪{ ( rj, pi) }pi∈P, rj∈R .申请边( pi, rj) : pi要申请rj；分配边( rj, pi) : rj分配给pi；Resource Allocation Graph

第10页：5.5 资源分配图（续）

资源分配图图示：

进程:

资源类:

申请边

进程到资源类;

分配边

由资源实例到进程;

申请

pi申请rj中的一个资源实例,由pi向rj画一条申请边,如可满足,改为分配边。

释放

去掉分配边。

第11页：5.5 资源分配图（续3）

例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资源分配图例5.2增加边(p3,r2)P3P2P1r4r3r2r

第12页：5.5 资源分配图例

5.3 (有环路,无死锁)P1P2P3r1r2图1.有环路,无死锁P1P2P3r1r2图2. P2释放r1，r1分配给P3

第13页：5.5 资源分配图

5.5.2资源分配图的约简约简方法：⑴寻找一个非孤立、且没有请求边的进程节点Pi ,若无则算法结束;⑵去除所有Pi的分配边,使Pi成为一个孤立节点;⑶寻找所有请求边均可满足的进程Pj ,将Pj的请求边全部改为分配边;⑷转步骤⑴。对资源分配图G进行约简,若算法结束时,图中所有节点均为孤立节点,则称G为可完全约简的,否则称G为不可完全约简的。死锁定理:系统状态S为死锁状态的充分必要条件是S的资源分配图是不可完全约简的。

第14页：5.6 死锁的预防

• 保证系统不死锁的静态策略对进程有关资源的活动加限制,所有进程遵循这种限制,即可保证没有死锁发生。
  • 优点:简单,系统不需要做什么。
  • 缺点:对进程的约束,违反约束仍可能死锁。
• 预防方法:
  • 预先分配策略;
  • 有序分配策略。

第15页：5.6.1 预先分配策略

• 进程:运行前申请所需全部资源;
• 系统:
  • 能够满足,全部分配;
  • 否则,一个也不分配。
• 思想:破坏“hold-and-apply”条件。
• 缺点:
  • 资源利用效率低;
  • 一次提出申请困难：程序不同分支可能需要申请不同资源。

第16页：5.6.2有序分配策略资源类集

5.6.2有序分配策略资源类集: R = { r1 , r2 , … , rn }函数: f : R→N例如: 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......申请次序

第17页：5.6.2有序分配策略资源类集（续）

证明：有序分配法无死锁(deadlock free)。反证:假定死锁,则出现循环等待,即在时刻5.6.2有序分配策略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)

第18页：5.6.2 有序分配策略

• 优点与预先分配相比,资源利用率提高。
• 缺点
  • 资源编号困难;
  • 按号申请增加使用者负担,一旦不按号申请仍可能死锁;
  • 为保持按序申请,某些暂时不用的资源也需提前申请,牺牲资源利用率。

第19页：有序分配法

有序分配法:资源编号: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有序分配法BAW直行E左转S左转DC有序分配法预防死锁例S2WS1E死锁的可能性SWE2E1可能性1:可能性2:

第20页：Procedure S

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);

第21页：5.7死锁的避免动态检测策略

5.7死锁的避免动态检测策略:进程申请资源不限制,对能满足的申请要求进行动态检测,若安全则分配,否则不分配。可满足请求分配不安全检测安全不分配

第22页：5.7死锁的避免动态检测策略（续）

5.7.1安全状态与安全进程序列安全状态:如果系统中所有进程能按某种次序依次运行完,则称系统处于安全状态。形式定义:如果存在一个由系统中所有进程构成的安全进程序列< p1, p2, ……, pn > ,则称系统处于安全状态。对进程序列< p1 , p2 , …… , pn >,如果有:pi要申请的资源数≤当前剩余资源数＋∑pj当前占有资源数则称该进程序列是安全的。j<i安全状态不安全状态死锁状态

第23页：5.7.2 银行家算法

Banker’s algorithm(E.W. Dijkstra)进程:事先申明所需资源最大量(并不分配)Claim=Max系统:对每个可满足的资源申请命令进行安全性检查。安全:分配;不安全:不分配状况:P = { p1, p2, … , pn} ;R = { r1, r2, … , rm} ;

第24页：5.7.2 银行家算法（续）

数据结构:intavailable[m];//系统可用资源intclaim[n, m];//进程最大需求intallocation[n, m];//进程当前已分配资源intneed[n, m];//进程尚需要的资源intrequest[ n, m];//进程当前请求的资源临时变量(安全检查时用):intwork[m];//可分配资源和已分配资源之和intfinish[n];//检查时标识是否有未完成进程

第25页：5.7.2 银行家算法（续3）

定义如下数组操作:设X、Y是下标为1～k的一维数组,定义X≤ Y→j (1 ≤ j ≤ k), X[j] ≤ Y[j] ;X = Y→j (1 ≤ j ≤ k), X[j] = Y[j] ;X = c→j (1 ≤ j ≤ k), X[j] = c ;X±Y→j (1 ≤ j ≤ k), X[j]±Y[j]。

第26页：5.7.2 银行家算法（续4）

5.7.2银行家算法资源分配算法Request[i]≤Need[i]<安全检查>＝安全请求超量，带错返回F确认分配，pi继续算法结束TRequest[i]≤AvailableTAvailable-= Request[i];Allocation[i] += Request[i];Need[i]-= Request[i];T预分配Available += Request[i];Allocation[i]-= Request[i];Need[i] += Request[i];F取消预分配申请无法满足进程pi等待F申请导致不安全进程pi等待

第27页：5.7.2银行家算法安全检查算法Wor…

5.7.2银行家算法安全检查算法Work = Available;Finish = 0;有满足条件的j：Finish[j]==0Need[j] ≤Work返回“不安全”结束Fj,finish[j]==1F返回“安全”结束TFinish[j]=1;Work+= Allocation[j]T找出一个“安全进程序列”Pj1、Pj1、…、Pjn

第28页：5.7.2 银行家算法例

5.4资源R = { A (10) , B (5) , C(7) }进程P = { p0 , p1 , p2 , p3 , p4 }某时刻系统状态：134200334P4110112222P3206003209P2221002223P1333247110357P0CBACBACBACBAAvailableNeedAllocationClaimRP试判断上述系统状态是否安全？并找出该状态下的安全进程序列。

第29页：5.7.2银行家算法对上述系统状态运行…

5.7.2银行家算法对上述系统状态运行安全检查算法，首先找到j=1，状态如下：3C3B5AWork0134200334P40110112222P30206003209P21221002223P10247110357P0CBACBACBAFinishNeedAllocationClaimRP

第30页：5.7.2银行家算法第二次找到j=3…

5.7.2银行家算法第二次找到j=3，状态如下：4C4B7AWork0134200334P41110112222P30206003209P21221002223P10247110357P0CBACBACBAFinishNeedAllocationClaimRP

第31页：5.7.2银行家算法第三次找到j=4…

5.7.2银行家算法第三次找到j=4，状态如下：6C4B7AWork1134200334P41110112222P30206003209P21221002223P10247110357P0CBACBACBAFinishNeedAllocationClaimRP

第32页：5.7.2银行家算法第四次找到j=2…

5.7.2银行家算法第四次找到j=2，状态如下：6C4B10AWork1134200334P41110112222P31206003209P21221002223P10247110357P0CBACBACBAFinishNeedAllocationClaimRP

第33页：5.7.2银行家算法第五次找到j=0…

5.7.2银行家算法第五次找到j=0，状态如下：7C5B10AWork1134200334P41110112222P31206003209P21221002223P11247110357P0CBACBACBAFinishNeedAllocationClaimRP所有Finish[j]均为1，则最初系统状态是安全状态，并且找到的安全进程序列为：<p1,p3,p4,p2,p0>实际上，<p1,p3,p4,p0,p2>也是安全进程序列。因此，系统安全状态下，安全进程序列不唯一。

第34页：5.7.2 银行家算法

134200334P4110112222P3206003209P2221002223P1333247110357P0CBACBACBACBAAvailableNeedAllocationClaimRP在系统最初状态下，假设进程P2有资源请求Request[2]=(1,0,2)，为避免死锁，该请求是否可以满足？

第35页：5.7.2 银行家算法（续）

134200334P4110112222P3005204209P2221002223P1132247110357P0CBACBACBACBAAvailableNeedAllocationClaimRP在系统最初状态下，对资源请求Request[2]=(1,0,2)，进行预分配，使系统变为如下状态：可找到安全进程序列<p3,p1,p4,p2,p0>，故请求Request[2]=(1,0,2)可以分配。

第36页：5.7.2 银行家算法例

5.5[银行家算法的保守性]R = { A(1) , B(1) }，P = { p1 , p2 }申请：a , b释放：a , bp1 : a , b , a , bp2 : b , b , b , a , b , a则p1 , p2的资源最大需求量均为A(1) , B(1)。某时刻系统状态如下：110011P210100111P1BABABABAAvailableNeedAllocationClaimRP

第37页：5.7.2银行家算法考虑request…

5.7.2银行家算法考虑request[2] = (0 , 1)，预分配后系统状态如下：011011P200100111P1BABABABAAvailableNeedAllocationClaimRP上一系统状态，经安全检查为不安全状态，故request[2] = (0 , 1)不分配。实际上，即使分配也不是一定导致死锁。结论：不安全状态不一定会导致死锁。亦即，死锁状态是不安全状态的真子集。

第38页：5.8 死锁的发现

• 系统未采用:
  • 死锁预防策略;
  • 死锁避免策略。
• 可能发生死锁
• 死锁检测和恢复

第39页：5.8.1死锁检测算法系统状况

5.8.1死锁检测算法系统状况:P = { p1, p2, … , pn} ;R = { r1, r2, … , rm} ;数据结构:intAvailable[m] ;intAllocation[n , m] ;intRequest[n , m] ;

第40页：5.8.1死锁检测算法死锁检测算法Wo…

5.8.1死锁检测算法死锁检测算法Work = Available;i,Finish[i]=(Allocation[i]≠0) ?0 : 1有满足条件的i：Finish[i]==0Request[i] ≤Work发现死锁返回Fi,Finish[i]==1F无死锁返回TFinish[i]=1;Work+= Allocation[i]T定理：P是进程集合，P’⊆P占有资源集合。P中存在死锁⇔P’中存在死锁。

第41页：5.8.1 死锁检测算法例

5.6资源R = { A (7) , B (3) , C(6) }进程P = { p0 , p1 , p2 , p3 , p4 }某时刻系统状态：200200P4001112P3000303P2202002P1010000010P0CBACBACBAAvailableRequestAllocationRP试判断上述系统状态是否处于死锁状态？

第42页：5.8.1 死锁检测算法

200200P4001112P3000303P2202002P1020000010P0CBACBACBAWorkRequestAllocationRPFinish10000对上述系统状态运行死锁检测算法，首先找到i=0，状态如下：

第43页：5.8.1死锁检测算法第二次找到i=2…

5.8.1死锁检测算法第二次找到i=2，状态如下：200200P4001112P3000303P2202002P1323000010P0CBACBACBAWorkRequestAllocationRPFinish10100

第44页：5.8.1死锁检测算法第三次找到i=3…

5.8.1死锁检测算法第三次找到i=3，状态如下：200200P4001112P3000303P2202002P1435000010P0CBACBACBAWorkRequestAllocationRPFinish10110

第45页：5.8.1死锁检测算法第四次找到i=1…

5.8.1死锁检测算法第四次找到i=1，状态如下：200200P4001112P3000303P2202002P1437000010P0CBACBACBAWorkRequestAllocationRPFinish11110

第46页：5.8.1死锁检测算法第五次找到i=4…

5.8.1死锁检测算法第五次找到i=4，状态如下：200200P4001112P3000303P2202002P1637000010P0CBACBACBAWorkRequestAllocationRPFinish11111得到进程序列<p0,p2,p3,p1,p4>，所有Finish[i]均为1。因此，最初系统状态无死锁。

第47页：5.8.1 死锁检测算法如果在最初系统状

：200200P4001112P3000303P2202002P1010000010P0CBACBACBAAvailableRequestAllocationRP进程p2有请求：Request[2]=(0,0,1)，通过死锁检测算法检测，则发生死锁，参与死锁进程{p1,p2,p3,p4}

第48页：5.8.1 死锁检测算法

在最初系统状态下，进程p2的请求Request[2]=(0,0,1)系统无法满足，此时系统的资源分配图如下：A(0) 2, 3, 2B(1) 1, 1C(0) 3, 1, 2P1P4P3P0P

第49页：5.8.2 死锁检测时刻

• 考虑因素:
  • 死锁发生的频度;
  • 死锁影响的进程个数。
• 检测时刻:
  • 等待时检测:发现早,恢复代价小,开销大(overhead)。
  • 定时检测;
  • 资源(eg. CPU)利用率下降时检测。

第50页：5.9 死锁的恢复

• 1.重新启动(system restart)简单，代价大，涉及未参与死锁的进程。
• 2.终止进程(terminating processes)终止参与死锁、占有资源的进程：⑴一次性全部终止；⑵逐步终止(优先级&代价函数)。
• 3.剥夺资源(preempting resource)⑴逐步剥夺；⑵一次性全部剥夺。
• 4.进程回退(process rollback)⑴select a victim；⑵rollback.问题:⑴保存snapshot代价大；⑵消除影响困难;⑶可能造成进程“饥饿”(starvation)。

第51页：5.10 鸵鸟算法

• Ostrich algorithm：对死锁视而不见,当死锁真正发生且影响系统正常运行时,手工干预(重新启动)。
• 不同观点
  • 工程师观点(考虑死锁发生的频率,危害,处理代价)
  • 死锁发生频率<其它故障引起系统瘫痪的频率;
  • 死锁处理constant overhead >危害。
  • 数学家观点：必须处理,无论代价如何
• 目前系统实际如此Eg. UNIX proc结构(PCB)及交换机制存在死锁隐患。

第52页：5.11 有关问题的讨论

• 关于充要性算法
  • 预防策略:进程违反协议也可能死锁。
  • 避免策略:开销大,非必要性算法(保守算法)。
  • 充要性算法:已知进程所需资源最大量及其资源活动序列；⑴困难:程序中的分枝与循环;⑵复杂度高(NP Complete)。
• 生灭资源(或消耗性资源)问题
  • 资源:可重用资源；生灭资源(消息):超时处理;
  • 死锁要考虑两类资源,增加了复杂性。
• 可剥夺资源问题：不会因为进程竞争CPU而死锁；在虚拟存储支持下，不会因为竞争内存而死锁。
• 关于两阶段锁
  • 两阶段封锁协议:增长阶段（加锁）和消退阶段（开锁）;
  • 增长阶段有可能发生死锁。一组进程中的每个进程，均无限期地等待这组中的其它进程引发的事件，这种现象叫死锁。

第53页：5.12 饥饿与活锁

• 由于资源分配策略的不公平，可能造成进程没有时间上界的等待
  • 排队等待
  • 忙式等待
• 饥饿(starvation)：
  • 当等待时间给进程推进和响应带来明显影响时,称发生了进程饥饿；
  • 饥饿到一定程度的进程所赋予的使命即使完成也不再具有实际意义时称该进程被饿死(starved to death).
• 忙式等待条件下发生的饥饿,称为活锁(live lock).

第54页：5.12 饥饿与活锁（续）

• 饿死vs死锁：都是由竞争资源引起。
• 死锁进程处于等待状态,忙式等待的进程并非处于等待状态,但却可能被饿死;
• 死锁进程等待永远不会释放的资源,饿死进程等待可能被释放,但却不会分给自己的资源,其等待时间没有上界;
• 死锁一定发生了循环等待,饿死不然;
• 死锁至少涉及两个进程,而饥饿或饿死进程可能只有一个。防止饥饿或饿死的资源分配策略如：先到先服务和动态优先级调度

第55页：5.13 可复用资源死锁的静态分析

可复用资源

一次只能分配给一个进程使用的资源。称为可复用资源(reusable resource)。

组合资源

由相对独立的若干资源构成的资源集合称为组合资源。其中每个相对独立的资源称为子资源。

同种组合资源

由相同类型的子资源构成的组合资源称为同种组合资源。

简单组合资源

每类子资源只有一个实例的组合资源称为简单组合资源。

第56页：5.13 可复用资源死锁的静态分析步骤

• 1：以每个进程占有资源、申请资源作为一个状态，记作:(pi: aj: ak1,…,akn)=(进程:请求:占有序列) ;步骤2：以每个状态为一个节点；步骤3：如s1所申请资源为s2所占有，则由s1向s2画一有向边(相同进程间不画) ;步骤4：找出所有环路;步骤5：判断环路上状态是否能同时到达，如是有死锁可能性，否则无死锁可能性。⑴环路中有相同进程，不能到达；⑵环路中有相同被占有资源，不能到达。
• 可复用简单组合资源死锁的静态分析算法条件：已知各个进程有关资源的活动序列；判断：有无死锁可能性。

第57页：5.13 可复用资源死锁的静态分析例

5-7：死锁分析例子已知:R = { A，B，C，D，E，F，G }p1：c d c a b d a bp2：d e d b f e b fp3：c e e f a e 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有如下状态节点：

第58页：5.13 可复用资源死锁的静态分析根据步

3得到进程资源申请、占用状态图：p1: d:cp1: a:dp1: b:d, ap2: e:dp2: b:ep2: f:e, bp3: e:cp3: f:cp3: a:c, f出现环路可能死锁

第59页：5.13 可复用资源死锁的静态分析死锁分

：判断环路上的状态是否可以同时到达。即：p1, p2, p3三个进程是否可以同时到达红色位置。证明:假设p1, p2, p3三个进程可以同时到达红线位置,则p1, p2, p3三个进程可以同时到达蓝线位置,根据蓝线位置的资源申请情况，并考虑简单组合资源，则各进程推进到蓝线的进度为：p3先于p2, 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 fp3：c e e f a e f a

第60页：5.13 可复用资源死锁的静态分…（续）

• 4同种组合资源死锁的必要条件M :资源数量;N :使用该类资源进程的数量;→:所有进程所需要该类资源的总量；则：当→＜M + N时,一定没有死锁；当→≥M + N时,至少有一个交叉有死锁。证明:假定有死锁且n个进程参与了死锁(2≤ n ≤N),则:
  • 参与死锁进程所需资源数≥M + n ;
  • 未参与死锁进程所需资源的总量≥使用该类资源但未参与死锁的进程数=N-n ;所有进程所需资源的总量→≥M+n+N-n=M+N

第61页：5.14 同种组合资源死锁的必要条件例

5-8.M=16；N=4；P1(5); P2(6); P3(4); P4(4)→=5+6+4+4=19<M+N=20无死锁可能性。若P1(5); P2(6); P3(4); P4(5)则→=5+6+4+5=20=M+N=20有死锁可能性。死锁情况：P1：a a a aaP2：a a a a aaP3：a a aaP4：a a a aa

第62页：5.14 同种组合资源死锁的必要…（续）

4同种组合资源死锁的必要条件例.09年计算机专业综合试卷试题25题25.某计算机系统中有8台打印机，由K个进程竞争使用，每个进程最多需要3台打印机。该系统可能会发生死锁的K的最小值是A．2 B．3 C．4 D．5解：依题意，M=8, N=K, ∑=K×3。按必要条件：→≥M + N,即3K ≥8＋K成立时，可能发生死锁。K ≥ 4

第63页：5.15 死锁与饥饿的例子例

5-9.哲学家就餐问题(Dining Philosophers Problem)Proposed and solved by E.W. Dijkstra , in 1965.Roomph0ph4ph3ph2ph1f0f4f3f2f1

第64页：5.15 死锁与饥饿的例子

哲学家活动:While(1){思考;进食;}哲学家活动(包含资源活动)While(1){思考;取左叉;取右叉;进食;放左叉;放右叉;}进食:需要“叉子”；叉子:不同种组合资源，因为区别左、右叉子。

第65页：5.15 死锁与饥饿的例子（续）

Roomph0ph4ph3ph2ph1f0f4f3f2f1死锁情况：每位哲学家都拿到左叉，等待右叉。

第66页：5.15 死锁与饥饿的例子共享变量

死锁解决方法(预先分配):同时申请左、右两把叉子;哲学家状态描述(增加hungry状态):#define N 5typedef enum action { thinking, hungry, eating } ;action state [ N ] ;等待队列设置(每个哲学家一个队列) :semaphore self [ N ] ; (initial self.value = 0 ) ;

第67页：5.15 死锁与饥饿的例子

测试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:自测试不需要state [ i ] = hungry,但测试左邻右舍需要此条件。

第68页：5.15 死锁与饥饿的例子（续）

i号哲学家活动：voidphilosopher ( int i ){ while(1){ think()；pick_forks(i);eat()；put_forks(i);}}

第69页：5.15 死锁与饥饿的例子（续3）

i号哲学家放叉：void put_forks ( int i ){P ( mutex ) ;state [ i ] = thinking ;test ( ( i–1 ) % N ) ;test ( ( i + 1 ) % N ) ;V ( mutex ) ;}i号哲学家取叉：voidpick_forks ( int i ){ P(mutex);state[i]=hungry;test(i);V(mutex);P(self[i]);}

第70页：5.15 死锁与饥饿的例子（续4）

void main ( ){ for ( i= 0 ; i < N ; i ++ ){ state [ i ] = thinking ; self [ i ] . value = 0 ; }mutex . value = 1 ;cobegin philosopher(0); philosopher(1);philosopher(2); philosopher(3);philosopher(4);coend}

第71页：5.15 死锁与饥饿的例子（续5）

Roomph0ph4ph3ph2ph1f0f4f3f2f1饿死情况:某哲学家左右邻居至少有一个处于eating状态。

第72页：5.15 死锁与饥饿的例子（续6）

过河问题(1)：12n-1n……水流W→EW←EWestEestDeadlock prevention: one direction at any time.

第73页：5.15 死锁与饥饿的例子过河问题

(1)数据定义：intwest_crossing; (0)inteast_crossing; (0)intwest_wait; (0)Inteast_wait; (0)semaphorewq , eq; (0)Semaphoremutex; (1)

第74页：5.15 死锁与饥饿的例子过河问题（续）

西面过河者活动：P ( mutex ) ;if (east_crossing > 0){ west_wait ++ ;V ( mutex ) ; P ( wq );}else{ west_crossing++;V ( mutex );}

第75页：5.15 死锁与饥饿的例子过河…（续3）

过河;P ( mutex ) ;west_crossing--;if ( west_crossing == 0)while (east_wait > 0) do{ east_wait--;east_crossing ++ ;V ( eq ) ;}V ( mutex ) ;

第76页：5.15 死锁与饥饿的例子过河问题

东面过河者活动：P ( mutex ) ;if (west_crossing > 0){ east_wait ++ ;V ( mutex ) ; P ( eq );}else{ east_crossing ++ ;V ( mutex )};

第77页：5.15 死锁与饥饿的例子过河问题（续）

过河;P ( mutex ) ;east_crossing--;if (east_crossing == 0)while (west_wait > 0) do{ west_wait--;west_crossing ++ ;V ( wq ) ;};V ( mutex ) ;

第78页：5.15 死锁与饥饿的例子过河…（续3）

• 对于过河问题(1):考虑一个没有饿死情况的解法。

第79页：5.15 死锁与饥饿的例子过河问题

(2)例5-10.过河问题(2)：123水流W→EW←EWestEest875641→2→5→6→4→31←2←8←7←4←3要求:⑴无死锁;⑵无饿死;⑶并行度高。

第80页：5.15 死锁与饥饿的例子过河问题（续）

• (2)发生死锁：
• 当两个方向各有3人踏上石块；
• 当两个方向各有1人分别在1、2石块,或分别在3、4石块。死锁解决：
• 限定同时过河人数≤5。此时至少一个方向的过河人数≤2 ,可躲避到支路两石，保证另一方向过河；
• 对1,2和3,4两对石块的竞争，采用资源有序分配法。数据定义：semaphoreS, s1, s2, s3, s4, s5, s6, s7, s8;(5,1,1,1,1,1,1,1,1)

第81页：5.15 死锁与饥饿的例子过河…（续3）

W→E:P ( S ) ;P ( s1 ) ;走到1 ;P ( s2 ) ;走到2 ;V ( s1 ) ;P ( s5 ) ;走到5；V ( s2 ) ;P ( s6 ) ;走到6 ;E→W:P ( S ) ;P ( s3 ) ;走到5 ;P ( s4 ) ;走到4 ;V ( s3 ) ;P ( s7 ) ;走到7 ;V ( s4 ) ;P ( s8 ) ;走到8 ;V (s5 ) ;P ( s3 ) ;P ( s4 ) ;走到4 ;V ( s6 ) ;走到3 ;V ( s4 ) ;走到E ;V ( s3 ) ;V ( S ) ;V ( s7 ) ;P ( s1 ) ;P ( s2 ) ;走到2 ;V ( s8 ) ;走到1 ;V ( s2 ) ;走到W ;V ( s1 ) ;V ( S ) ;

第82页：5.16 系统举例

• 绝大多数系统对死锁采用“鸵鸟算法”；
• E.W.Dijkstra在THE系统中采用了避免死锁的银行家算法。