1 死锁的概念

在多线程编程中，我们为了防止多线程竞争共享资源而导致数据错乱，都会在操作共享资源之前加上互斥锁，只有成功获得到锁的线程，才能操作共享资源，获取不到锁的线程就只能等待，直到锁被释放。

那么，当两个线程为了保护两个不同的共享资源而使用了两个互斥锁，那么这两个互斥锁应用不当的时候，可能会造成两个线程都在等待对方释放锁，在没有外力的作用下，这些线程会一直相互等待，就没办法继续运行，这种情况就是发生了死锁。

死锁只有同时满足以下四个条件才会发生：

• 互斥条件；
• 持有并等待条件；
• 不可剥夺条件；
• 环路等待条件；

1.1 互斥条件

互斥条件是指多个线程不能同时使用同一个资源。

比如下图，如果线程 A 已经持有的资源，不能再同时被线程 B 持有，如果线程 B 请求获取线程 A 已经占用的资源，那线程 B 只能等待，直到线程 A 释放了资源。

1.2 持有并等待条件

持有并等待条件是指，当线程 A 已经持有了资源 1，又想申请资源 2，而资源 2 已经被线程 C 持有了，所以线程 A 就会处于等待状态，但是线程 A 在等待资源 2 的同时并不会释放自己已经持有的资源 1。

1.3 不可剥夺条件

不可剥夺条件是指，当线程已经持有了资源 ，在自己使用完之前不能被其他线程获取，线程 B 如果也想使用此资源，则只能在线程 A 使用完并释放后才能获取。

1.4 环路等待条件

环路等待条件指的是，在死锁发生的时候，两个线程获取资源的顺序构成了环形链。

比如，线程 A 已经持有资源 2，而想请求资源 1， 线程 B 已经获取了资源 1，而想请求资源 2，这就形成资源请求等待的环形图。

https://www.xiaolincoding.com/os/4_process/deadlock.html#环路等待条件

一、资源问题

在系统中有许多不同类型的资源，其中可以引起死锁的主要是，需要采用互斥访问方法的、不可被抢占的资源，即临界资源。系统中这类资源有很多，如打印机、数据文件、队列、信号量等。

1.1 可重用性资源和消耗性资源

1.1.1 可重用性资源

可重用性资源是一种可供用户重复使用多次的资源
待补充115

1.2 可抢占性资源和不可抢占性资源

1.2.1 可抢占性资源

可把系统中的资源分成两类，一类是可抢占性资源，是指某进程在获得这类资源后，该资源可以再被其他进程或系统抢占。例如优先级高的进程可以抢占优先级低的进程的处理机。又如可把一个进程从一个存储区转移到另一个存储区，在内存紧张时，还可将一个进程从内存调出到外存上，即抢占该进程在内存的空间。可见，CPU和主存均属于可抢占性资源，对于这类资源是不会引起死锁的

1.2.2 不可抢占性资源

另一类资源是不可抢占性资源，即一旦系统把某资源分配给该进程后，就不能将它强行收回，只能在系统用完后自行释放。例如，当一个进程已开始刻录光盘时，如果突然将刻录机分配给另一个进程，其结果必然会损坏正在刻录的光盘，因此只能等刻好光盘后由进程自己释放刻录机。另外磁带机、打印机等也都属于不可抢占性资源。

二、计算机系统中的死锁

死锁的起因，通常是源于多个进程对资源的争夺，不仅对不可抢占资源进行争夺时会引起死锁，而且对可消耗资源进行争夺时，也会引起死锁。

2.1 竞争不可抢占性资源引起死锁

通常系统中拥有的不可抢占性资源其数量不足以满足多个进程运行的需要，使得进程在运行过程中，会因争夺资源而陷入僵局。我们可以将这个问题利用资源分配图进行描述，用方块代表可重用的资源（文件），用圆圈代表进程，如下图所示：

当箭头从进程指向文件时，表示进程请求资源（打开文件）；当箭头从资源指向进程时，表示该资源已经被分配给该进程（已被进程打开）。从中可以看出，这时在$P_1$、$P_2$及$R_1$和$R_2$之间，已经形成了一个环路，说明已进入死锁状态。

2.2 竞争可消耗资源引起死锁

下图给出了一个例子，在三个进程之间，在利用消息通信机制进行通信时所形成的死锁情况。图中，图中，$m_1$、$m_2$和$m_3$是可消耗资源，在利用消息通信机制进行通信时所形成的死锁情况。进程$P_1$一方面产生消息$m_1$，利用$send(P_2,m_1)$原语将它发送给$P_2$；另一方面，它又要求从$P_3$接收消息$m_3$。而进程$P_2$一方面产生消息$m_2$，利用$send(p_3,m_2)$原语将它发送给$P_3$；另一方面，它又需要接收进程$P_1$所产生的消息$m_1$。类似地，进程
待补充/117

三、死锁的定义、必要条件和处理方法

3.1 死锁的定义

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

3.3 处理死锁的方法

目前处理死锁的方法可以归结为四种：

• 预防死锁：这是一种较简单和直观的事先预防方法。该方法是通过设置某些限制条件，去破坏产生死锁四个必要条件中的一个或几个来预防产生死锁。预防死锁是一种较易实现的方法，已被广泛使用。
• 避免死锁：同样是属于事先预防策略，但它并不是事前采取各种限制措施，去破坏产生死锁的四个必要条件，而是在资源的动态分配过程中，用某种方法防止系统进入不安全状态，从而可以避免发生死锁。
• 检测死锁：这种方法无需事先采取任何限制性措施，允许进程在运行过程中发生死锁。但可通过检测机构及时的检测出死锁的发生，然后采取适当措施，把进程从死锁中解脱出来。
• 解除死锁：当检测到系统中已发生死锁时，就采取相应措施，将进程从死锁状态中解脱出来。常用的方法是撤销一些进程，回收它们的资源，将它们分配给已处于阻塞状态的进程，使其能继续运行。

上述的四种方法，从1到4对死锁的防范程度逐渐减弱，但对应的是资源利用率的提高，以及进程因资源因素而阻塞的频度（即并发程度提高）。

2.3 进程推进顺序不当引起死锁

待补充/117

四、预防死锁：

预防死锁的方法是通过破坏产生死锁的四个必要条件中的一个或几个，以避免发生死锁。由于互斥条件是非共享设备所必须的，不仅不能改变，还应加以保证，因此主要是破坏产生死锁的后三个条件。

4.1 破坏请求和保持条件

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

4.1.1 第一种协议

该协议规定，所有进程在开始运行之前，必须一次性地申请其在整个过程中所需的全部资源。此时若系统有足够的资源分配给某进程，便可把其所需的所有资源分配给它。这样，该进程在整个运行期间，遍不会再提出资源要求，从而破坏了“请求”条件。系统在分配资源时，只要有一种资源不能满足进程的要求，即使其他所需的各资源都空闲也不分配给该进程，而让该进程等待。由于该进程在等待期间未占有任何资源，于是破坏了“保持”条件，从而可以预防死锁的发生。
第一种协议的优点是简单、易行且安全，但缺点也极其明显：
资源被严重浪费，严重地恶化了资源的利用率。进程在开始运行时就一次性地占用了整个运行过程所需的全部资源，其中有些资源可能仅在运行初期或运行快结束时才使用，甚至根本不使用。

使进程经常会发生饥饿现象。因为仅当进程在获得了其所需的全部资源后才能开始运行，这样就可能由于个别资源长期被其他进程占用，而致使等待该资源的进程迟迟不能开始运行，而个别资源有可能仅在进程运行到最后才需要，如打印机就是如此。

4.1.2 第二种协议

该协议是对第一种协议的改进，它允许一个进程只获得运行初期所需的资源后，便开始运行。进程运行过程中再逐步释放已分配给自己的、且已用毕的全部资源。然后再请求新的所需资源。

4.2 破坏不可抢占条件

为了能破坏“不可抢占”条件，协议中规定，当一个已经保持了某些不可被抢占资源的进程，提出新的资源请求而不能得到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请。这意味着进程已占用的资源会被暂时地释放，或者说是被抢占了，从而破坏了“不可抢占”条件。
该方法实现起来比较复杂，且需付出很大的代价。因为一个不可抢占的资源如打印机等在一段时间后被抢占，可能会造成进程前一阶段工作的失效，即使是采取了某种防范措施，也还会使进程前后运行的信息不连续。这种策略还可能因为反复地申请和释放资源致使进程的执行被无限地延迟，这不仅延长了进程的周转时间，而且也增加了系统开销，降低了系统吞吐量。

4.3 破坏循环等待条件

一个能保证“循环等待”条件不成立的方法是，对系统所有资源类型进行线性排序，并赋予不同的序号。设$R=(R_1,R_2,R_3,\dots ,R_n)$为资源类型的集合，为没个资源类型赋予唯一的序号。如果系统中有磁带驱动器、硬盘驱动器、打印机、则函数F可按如下形式来定义：
$F(diskdrive)=5$
$F(printer)=12$
在对系统所有资源类型进行线性排序后，便可采用这样的预防协议：规定每个进程必须按序号递增的顺序请求资源。一个进程在开始时，可以请求某类型资源$R_1$的单元。以后，当且仅当$F(R_j)>F(R_i)$时，进程才可以请求资源$R_j$的单元。如果需要多个同类资源单元，则必须一起请求。例如，当某进程需要同时使用打印机和磁带机时，由于磁带机序号低，而打印机序号高，故必须先请求磁带机，再请求打印机。假如某一进程已请求到一些序号较高的资源，后来它又想请求也给序号低的资源时，它必须先释放所有具有相同和更高序号的资源后，才能申请序号低的资源。在采用这种策略后所形成的资源分配图中，不可能再出现环路，因为破坏了“循环等待”条件。事实上，总有一个进程占用了较高序号的资源，此后它继续申请的资源必然是空闲的，因而进程可以一直向前推进。

在采用这种策略时，应如何来规定每种资源的序号是十分重要的。通常应根据大多数进程需要资源的先后顺序来确定。一般情况下，进程总是先输入程序和数据，继而进行运算，最后将计算结果输出。故可以为输入设备规定较低的序号，如前面是将磁带机定为1；为输出设备规定较高的序号，如把打印机定为12…

这种预防死锁的策略与前两种策略比较，其资源利用率和系统吞吐量都有较明显的改善，但也存在下述问题：
首先，为系统中各类资源所规定的序号必须相对稳定，这就限制了新类型设备的增加
其次，尽管在为资源的类型分配序号时，已经考虑到了大多数作业在实际使用这些资源时的顺序，但也经常会发生这种情况：作业使用各类资源的顺序与系统规定的顺序不同，造成对资源的浪费
第三，为方便客户，系统对用户在编程时所施加的限制条件应尽量少，然而这种按规定次序申请资源的方法比然会限制用户简单、自主地编程。

五、避免死锁

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

5.1 系统安全状态

在死锁避免方法中，把系统的状态分为安全状态和不安全状态。当系统处于安全状态时，可避免发生死锁。反之，当系统处于不安全状态时，则可能进入到死锁状态。

5.1.1 安全状态

在该方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，才可将资源分配给进程，否则，令进程等待。所谓安全状态，是指系统能按某种进程推进顺序$(P_1,P_2,\dots ,P_n)$为每个进程$P_i$分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。此时称$(P_1,P_2,\dots ,P_n)$为安全序列。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。虽然你并非所有不安全状态都比然会转化为死锁状态，但当系统进入不安全状态后，就有可能进入死锁状态。反之，只要系统处于安全状态，系统便不会进入死锁状态。因此，避免所的实质在于，系统在进行资源分配时，应使系统不进入不安全状态。

六、死锁的检测与解除

如果在系统中，既不采取死锁预防措施，也未配有死锁避免算法，系统很可能会发生死锁，在这种情况下，系统应当提供里那个算法：
死锁检测算法：该方法用于检测系统状态，以确定系统中是否发生了死锁
死锁解除算法：当认定系统中已经发生了死锁，利用该算法可将系统从死锁中解脱出来。

死锁的检测

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

资源分配图

系统死锁，可利用资源分配图来描述。该图是由一组节点N和一组边E所组成的一个对偶$G=(N,E)$，它具有下述形式的定义和限制。

待补充126