1.死锁的检测

该方法用于检测系统状态，以确定系统中是否发生了死锁。为了能对系统中是否已发生了死锁进行检测，在系统中必须：

 ① 保存有关资源的请求和分配信息；

 ② 提供一种算法，它利用这些信息来检测系统是否已进入死锁状态。

（1）资源分配图

用圆圈代表一个进程，用框代表一类资源。由于一种类型的资源可能有多个，因此用框中的一个圆代表一类资源中的一个资源。从进程到资源的有向边称为请求边，表示该进程申请一个单位的该类资源；从资源到进程的边称为分配边，表示该类资源已有一个资源分配给了该进程。

下图当前状态：

进程P1已占用两个R1资源，而且正在申请获得一个R2资源。进程P2已占用一个R1资源和一个R2资源，而且正在申请获得一个R1资源。

（2）死锁定理

资源分配图的简化

把资源分配图加以简化的方法，来检测当系统处于S状态时，是否为死锁状态。简化方法如下：

（1） 在资源分配图中，找出一个既不阻塞又非独立的进程结点 Pi。 在顺利的情况下，Pi可获得所需资源而继续运行，直至运行完毕，再释放其所占有的全部资源，这相当于消去Pi的请求边和分配边，使之成为孤立的结点。

（2） 在进行一系列的简化后，若能消去图中所有的边，使所有的进程结点都成为孤立结点，则称该图是可完全简化的；若不能通过任何过程使该图完全简化，则称该图是不可完全简化的。

对于较复杂的资源分配图，可能有多个既未阻塞又非孤立的进程结点。所有的简化顺序都将得到相同的不可简化图。S为死锁的充要条件是当且仅当S状态的资源分配图是不可完全简化的，该条件为死锁定理。

 

2.死锁的解除

一旦检测出死锁，就应立即采取相应的措施来解除死锁。死锁解除的主要方法有：

（1）剥夺资源法：挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但应防止被挂起的进程长时间得不到资源而处于资源匮乏的状态。

（2）撤销进程法：强制撤销部分甚至全部死锁进程并剥夺这些进程的资源，直到有足够的资源分配给其他进程，解除死锁状态。撤销的原则可以按进程优先级和撤销进程代价的高低进行。

（3）进程回退法：让一个或多个进程回退到足以回避死锁的地步，进程回退时自愿释放资源而不是被剥夺。要求系统保持进程的历史信息，设置还原点。

 

课后习题

 

1. 某个系统采用下列资源分配策略。若一个进程提出资源请求得不到满足，而此时没有由于等待资源而被阻塞的进程，则自己就被阻塞。而当此时已有等待资源而被阻塞的进程，则检查所有由于等待资源而被阻塞的进程。若它们有申请进程所需要的资源，则将这些资源取出并分配给申请进程。这种分配策略会导致（ ）。

A . 死锁                 B .颠簸

C . 回退                 D .饥饿

【答案】D

【解析】某个进程主动释放资源不会导致死锁，因为破坏了请求并保持条件，选项A 错。

颠簸也就是抖动，这是请求分页系统中页面调度不当而导致的现象，是下一章讨论的问题，这里权且断定选项B 是错的。

回退是指从此时此刻的状态退回到一分钟之前的状态，假如一分钟之前拥有资源X ,它有可能释放了资源X ，那就不称回到一分钟之前的状态，也就不是回退，选项C错。

由于进程过于“慷慨" ，不断把自己已得到的资源送给别人，导致自己长期无法完成，所以是饥饿，选项D对。

 

2.【2013统考真题】下列关于银行家算法的叙述中，正确的是（ ）。

A. 银行家算法可以预防死锁

B. 当系统处于安全状态时，系统中一定无死锁进程

C. 当系统处于不安全状态时，系统中一定会出现死锁进程

D. 银行家算法破坏了死锁必要条件中的“请求和保持”条件

【答案】B

【解析】银行家算法是避免死锁的方法，选项 A、D 错。

 

3. 【2011统考真题】某时刻进程的资源使用情况见下表，此时的安全序列是（ ）。

A. P1，P2，P3，P4

B. P1，P3，P2，P4

C. P1，P4，P3，P2

D. 不存在

【答案】D

【解析】本题应采用排除法，逐个代入分析。剩余资源分配给P1，待P1执行完后，可用资源数为(2,2,1), 此时仅能满足P4的需求，排除选项A、B；接着分配给P4，待P4执行完后，可用资源数为(2, 2,2),此时已无法满足任何进程的需求，排除选项C。

此外，本题还可以使用银行家算法求解(对选择题来说显得过于复杂)。

 

4. 【2012统考真题】假设5个进程P0，P1，P2，P3，P4共享三类资源R1,R2，R3, 这些资源总数分别为18，6，22。T0时刻的资源分配情况如下表所示，此时存在的一个安全序列是（ ）。

A. P0，P2，P3，P1，P3

B. P1，P0，P3，P4，P2

C. P2，P1，P0，P3，P4

D. P3，P4，P2，P1，P0

【答案】D

【解析】首先求得各进程的需求矩阵Need与可利用资源向量Available：

比较Need和Available发现，初始时进程P1与P3可满足需求，排除A、C。尝试给P1分配资源时，P1完成后Available将变为(6, 3, 6 ),无法满足P0的需求，排除B。尝试给P3分配资源时, P3完成后Available将变为(4, 3, 7 ) ，该向量能满足其他所有进程的需求。因此，以P3开头的所有序列都是安全序列。

 

5. 【2014统考真题】某系统有n台互斥使用的同类设备，三个并发进程分别需要3, 4, 5台设备，可确保系统不发生死锁的设备数死最小为（ ）。

A. 9

B. 10

C. 11

D. 12

【答案】B

【解析】三个并发进程分别需要3 ,4 ,5 台设备，当系统只有(3-1) + (4-1) + (5 - 1) = 9 台设备时，第一个进程分配2 台，第二个进程分配3 台，第三个进程分配4 台。这种情况下，三个进程均无法继续执行下去，发生死锁。当系统中再增加1台设备，即共10台设备时，最后1 台设备分配给任意一个进程都可以顺利执行完成，因此保证系统不发生死锁的最小设备数为10。

 

6. 【2016统考真题】系统中有3 个不同的临界资源R1，R2，R3，被4个P1，P2，P3，P4共享。各进程对资源的需求为：P1申请R1和P2申请R2和R3，P3申请R1和R3，P4申请R2。若系统出现死锁，则处于死锁状态的进程数至少是（ ）。

A. 1

B. 2

C. 3

D. 4

【答案】C

【解析】对于本题，先满足一个进程的资源需求，再看其他进程是否出现死锁状态。因为P4只申请一个资源，当将R2分配给P4后，P4执行完后将R2释放，这时使得系统满足死锁的条件是R1分配给P1，R2分配给P2, R3分配给P3 (或者R2分配给P1，R3分配给P2， R1分配给) 。穷举其他情况如 P1申请的资源R1和R2，先都分配给P1，运行完并释放占有的资源后，可分别将R1, R2和 R3分配给P3、P3和P2，也满足系统死锁的条件。各种情况需要使得处于死锁状态的进程数至少为3。

 

7. 【2015统考真题】若系统S1采用死锁避免方法，S2采用死锁检测方法。下列叙述中， 正确的是（ ）。

Ⅰ.S1会限制用户申请资源的顺序，而S2不会

Ⅱ.S1需要进程运行所需的资源总量信息，而S2不需要

Ⅲ.S1不会给可能导致死锁的进程分配资源，而S2会

A. 仅Ⅰ、Ⅱ

B. 仅Ⅱ、Ⅲ

C. 仅Ⅰ、Ⅲ

D. Ⅰ、Ⅱ、Ⅲ

【答案】B

【解析】死锁的处理采用三种策略：死锁预防、死锁避免、死锁检测和解除。

死锁预防采用破坏产生死锁的4个必要条件中的一个或几个来防止发生死锁。其中之一的“破坏循环等待条件”，一般采用顺序资源分配法，首先给系统的资源编号，规定每个进程必须按编号递增的顺序请求资源，即限制了用户申请资源的顺序，因此I 的前半句属于死锁预防的范畴。

银行家算法是最著名的死锁避免算法，其中的最大需求矩阵Max定义了每个进程对m 类资源的最大需求量，系统在执行安全性算法中都会检查此次资源试分配后，系统是否处于安全状态，若不安全则将本次的试探分配作废。在死锁的检测和解除中，系统为进程分配资源时不采取任何措施，但提供死锁的检测和解除手段，因此Ⅱ、Ⅲ正确。

 

8. 【2018统考真题】假设系统中有4 个同类资源，进程P1，P2，P3需要的资源数分别为4，3和1，P1，P2，P3已申请到的资源数分别为2 ,1 和 0 , 则执行安全性检测算法的结果是 （   ）。

A. 不存在安全序列，系统处于不安全状态

B. 存在多个安全序列，系统处于安全状态

C. 存在唯一安全序列P3，P1，P2系统处于安全状态

D. 存在唯一安全序列P3，P2，P1系统处于安全状态

【答案】A

【解析】由题意可知，仅剩最后一个同类资源，若将其分给P1或P2，则均无法正常执行；若分给P3, 则P3正常执行完成后，释放的这一个资源仍无法使P1，P2正常执行，因此不存在安全序列。

 

9. 【2019统考真题】下列关于死锁的叙述中，正确的是（ ）。

Ⅰ.可以通过剥夺进程资源解除死锁

Ⅱ.死锁的预防方法能确保系统不发生死锁

Ⅲ.银行家算法可以判断系统是否处于死锁状态

Ⅳ.当系统出现死锁时，必然有两个或两个以上的进程处于阻塞态

A. 仅Ⅱ、Ⅲ

B. 仅Ⅰ、Ⅱ、Ⅳ

C. 仅Ⅰ、Ⅱ、Ⅲ

D. 仅Ⅰ、Ⅲ、Ⅳ

【答案】B

【解析】剥夺进程资源，将其分配给其他死锁进程，可以解除死锁，I 正确。死锁预防是死锁处理策略 （死锁预防、死锁避免、死锁检测）中最为严苛的一种策略，破坏死锁产生的4个必要条件之一，可以确保系统不发生死锁，II正确。银行家算法是一种死锁避免算法，用于计算动态资源分配的完全性以避免系统进入死锁状态，不能用于判断系统是否处于死锁，Ⅲ错误。通过简化资源 分配图可以检测系统是否为死锁状态，当系统出现死锁时，资源分配图不可完全简化，只有两个或两个以上的进程才会出现“环”而不能被简化，IV正确。

 

10. 考虑某个系统在下表时刻的状态。

使用银行家算法回答下面的问题:

1）Need矩阵是怎么样的？

2）系统是否处于安全状态？如安全，请给出一个安全序列。

3）若从进程发来一个请求（0,4,2,0）, 这个请求能否立刻被满足？如安全，请给出一个安全序列。

【解析】

1）

2）Work向量初始化值=Available(1，5，2，0)。

系统安全性分析：因为存在一个安全序列<P0，P2，P1，P3>,所以系统处于安全状态。

3）

Request1(0, 4, 2, 0) < Need1(O, 7, 5, 0)

Request1(0, 4, 2, 0) < Available(l, 5, 2, 0)

假设先试着满足进程P i的这个请求，则 Available变为(1, 1, 0, 0)。

系统状态变化见下表：

再对系统进行安全性分析：

因为存在一个安全序列<P0，P2，P1，P3>，所以系统仍处于安全状态。所以进程的这个请求应该马上被满足。