死锁

一、定义

在一组进程发生死锁的情况下，这组死锁进程中的每一个进程，都在等待另一个死锁进程所占用的资源。或者说每个进程所等待的事件是该组中其他进程释放所占有的资源。但是由于这些进程已都无法运行，因此它们谁也不能释放资源，致使没有任何一个进程可被唤醒。这样这组进程只能无限期地等待下去。由此可以给死锁做出如下定义：

如果一组进程中的每一个进程都在等待仅由该组进程中的其他进程才能引发的事件，那么该组进程是死锁的（Deadlock）。

二、起因

死锁的起因通常是源于多个进程对资源的争夺，不仅对不可抢占资源进行争夺会引起死锁，而且对可消耗资源进行争夺时，也会引起死锁。下面列举几种常见的引起死锁的情况：

1. 竞争不可抢占资源引起死锁

例如，系统中有两个进程P1和P2，它们都准备写两个文件F1和F2，而这两者都属于可重用和不可抢占资源。如果P1打开F1，P2打开了F2，每个进程都占有了一个打开的文件，此时如果P1试图去打开F2，P2试图去打开F1，这是就会产生死锁

2. 竞争可消耗资源引起死锁

假设有P1，P2，P3三个进程，m1，m2，m3三条消息，当他们循环需要对方的消息时就会产生死锁。

3. 进程推进顺序不当引起死锁

除了系统中多个进程对资源的竞争会引发死锁外，进程在运行过程中，对资源进行申请和释放的顺序是否合法，也是在系统中是否会产生死锁的一个重要因素。

三、产生死锁的必要条件

虽然进程在运行过程中可能会发生死锁，但产生进程死锁是必须具备一定条件的。综上所述不难看出，产生死锁必须同时具备下面四个必要条件，只要其中任一个条件不成立，死锁就不会发生：

• 互斥条件：进程所分配到的资源进行排他性使用，即在*一段时间内，某资源只能被一个进程占用。如果此时还有其他进程请求该资源，则请求进程只能等待，直至占有该资源的进程用毕释放。
• 请求与保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被其他进程占用，此时请求进程被阻塞，但对自己已获得的资源保持不放。
• 不可抢占条件：进程已获得的资源在未使用完之前不能被抢占，只能在进程使用完时自己释放。
• 循环等待条件：在发生死锁时，必然存在一个进程——资源的循环链，即进程集合{P0，P1，P2，...，Pn}中的P0在等待一个P1占用的资源，P1正在等待P2占用的资源，...，Pn正在等待已被P0占用的资源。

四、处理死锁的方法

目前处理死锁的方法可归结为四种：预防死锁、避免死锁、检测死锁和解除死锁。且这四种方法按次序对死锁的防范程度逐渐削弱，但对应的是资源利用率的提高，以及进程因资源因素而阻塞的频度下降（即并发程度提高）。下来来分别展开介绍这四种方法：

4-1 预防死锁

这是一种简单和直观的事先预防方法。该方法是通过设置某些限制条件，去破坏产生死锁四个必要条件中的一个或几个来预防产生死锁。预防死锁是一种较容易实现的方法，已被广泛使用。

由于互斥条件是非共享设备所必须的，不仅不能改变，还应加以保证，因此主要是破坏产生死锁的后三个条件：

• 破坏“请求与保持”条件
  为了能破坏“请求与保持”条件，系统必须保证做到：当一个进程在请求资源时：不能持有不可抢占资源。该保证可通过如下两个协议实现：

  1. 第一种协议：
     所有进程在开始运行之前，必须一次性地申请其在整个运行过程中所需的全部资源。此时若系统有足够的资源分配给某进程，便可把其所需要的所有资源分配给它。这样，该进程在整个运行期间便不会再提出资源要求，从而破坏了“请求”条件。系统在分配资源时，只要有一种资源不满足进程的要求，即使其他资源都空闲也不分配给该进程，而让进程等待。由于该进程在等待期间未占用任何资源，于是破坏了“保持”条件。从而预防了死锁的产生。

     这种协议的优点是简单，易行且安全，但缺点是资源严重浪费，且进程经常会发生饥饿现象。

  2. 第二种协议：
     该协议是对第一种协议的改进，它允许一个进程只获得运行初期所需的资源后，便开始运行。进程运行过程中再逐步释放已分配给自己的、且已用毕的全部资源，然后再请求信的所需资源。这样不仅能使进程更快地完成任务，提高设备的利用率，还可以减少进程发生饥饿的几率。

• 破坏“不可抢占”条件
  为了能破坏“不可抢占”条件，协议中规定，当一个已经保持了某些不可抢占资源的进程，提出新的资源请求而不能得到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请。这意味着进程已占有的资源会被暂时的释放，或者说是被抢占了，从而破坏了“不可抢占”条件。

  这种方法实现起来比较复杂，且需付出很大的代价。

• 破坏“循环等待”条件
  对系统所有资源类型进行线性排序，并赋予不同的序号。然后规定每个进程必须按序号递增的顺序请求资源。如果一个进程已请求到一些序号较高的资源，后来又想请求序号低的资源时，必须先释放所有具有相同和更高序号的资源后，才能申请序号低的资源。

  这种策略比前两种的资源利用率和系统吞吐量都有较明显的改善。

4-2 避免死锁

同样属于事先预防策略，但它并不是事先采取各种限制措施，而是在资源的动态分配过程中，用某种方法防止系统进入不安全状态，从而避免产生死锁。这种方法所施加的限制条件较弱，可能获得较好的系统性能，目前常用此方法来避免发生死锁。

最有代表性的避免死锁的算法是Dijkstra的银行家算法，为了实现这个算法，系统中必须设置这样的四个数据结构，分别用来描述系统中可利用的资源（Available），所有进程对资源的最大需求（Max），系统中的资源分配（Allocation）以及所有进程还需要多少资源的情况（Need）。如果存在一个分配顺序不会导致死锁，那么就表示系统处于安全状态；否则系统处于不安全状态。（由于此算法需占用较大篇幅，所以仅简单的记录一下）

4-3 死锁的检测与解除

为了能对系统中是否已发生了死锁进行检测，在系统中必须：保存有关资源的请求和分配信息；提供一种算法，它利用这些信息来检测系统是否已进入死锁状态。

如果利用死锁检测算法检测出了在系统中已发生了死锁，则应立即采取相应的措施。常采用的解除死锁的两种方法是：

1. 抢占资源，从一个或多个进程中抢占足够数量的资源，分配给死锁进程，以解除死锁状态。
2. 终止（或撤销）进程。终止（或撤销）系统中的一个或多个死锁进程，直至打破循环环路，是系统从死锁状态中解脱出来。