操作系统学习笔记-10：死锁

1. 关于死锁

Deadlocks are a set of blocked processes each holding a resource and waiting to acquire a resource held by another process int the set. ——《Inners of Operating Systems》

死锁现象指的是：在并发环境下，两个或者以上的进程由于竞争资源而造成的一种互相等待（你等我，我等你）的现象，在这种情况下，A 进程拿着 A 资源，需要 B 资源，B 进程拿着 B 资源，需要 C 资源 …… 各个进程互相等待，都会被阻塞，无法继续向前推进。

2. 死锁的必要条件

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

① 互斥：

要求进程竞争的资源必须是互斥使用的资源。因为如果是可以共享使用的资源，多个进程直接同时使用就好，不会陷入等待的僵局。

② 非抢占：

要求进程占有的资源只能由进程使用完之后自己主动释放，其它进程不能抢占该资源。因为如果其它进程可以抢占资源，那么就是直接拿到资源了，也不会陷入等待的僵局。

③ 占有和请求：

要求进程是在占有（holding）至少一个资源的前提下，请求（waiting）新的资源的。由于新的资源被其它进程占有，此时，发出请求的进程就会带着自己占有的资源进入阻塞状态。假设 P1，P2 分别都需要 R1，R2 资源，如果是下面这种方式：

P1:          P2:
request(R1)  request(R2)
request(R2)  request(R1) 

如果 P1 请求到了 R1 资源之后，P2 请求到了 R2 资源，那么此后不管是哪个进程再次请求资源，都是在占有资源的前提下请求的，此时就会带着这个资源陷入阻塞状态。P1 和 P2 需要互相等待，发生了死锁。

换一种情况：

P1:          P2:
request(R1)  request(R1)
request(R2)  request(R2) 

如果 P1 请求到了 R1 资源，那么 P2 在请求 R1 的时候虽然也会阻塞，但是是在不占有资源的情况下阻塞的，不像之前那样占有 R2。所以，此时 P1 可以正常完成任务并释放 R1，P2 拿到 R1 之后再去执行任务。这种情况就不会发生死锁。

④ 循环等待：

要求存在一条进程资源的循环等待链，链中的每一个进程占有的资源同时被另一个进程所请求。

发生死锁时一定有循环等待（因为是死锁的必要条件），但是发生循环等待的时候不一定会发生死锁。这是因为，如果循环等待链中的 P1 和 链外的 P6 都占有某个进程 P2 请求的资源，那么 P2 完全可以选择不等待 P1 释放该资源，而是等待 P6 释放资源。这样就不会发生死锁了。

3. 死锁的出现场景

① 对系统资源的竞争：

各个进程对互斥的、不可抢占的资源的竞争可能会引起死锁。需要注意的是，正如我们在上面讲到的，对可抢占的资源的竞争是不会引起死锁的。比如说 CPU 就是可抢占的资源，可以借助很多种进程调度算法让进程抢占到处理机，一般不存在死锁的情况。

② 进程推进顺序不当：

比如上面的 P1，P2，R1，R2 的例子。换顺序之前，发生了死锁，两个进程都被阻塞；换顺序之后，就避免了死锁的发生。

③ 信号量使用不当：

信号量如果使用不当，也会发生死锁。这里选取在 操作系统学习笔记-6：进程同步与进程互斥（三）：经典问题 中提到过的生产者—消费者问题进行解释

死锁的处理

对于死锁，可以采取三种方式进行处理。第一种是预防死锁，核心是破坏导致死锁产生的一个或多个必要条件；第二种是避免死锁，核心是用某种方法防止系统进入不安全状态，从而避免死锁；第三种不像前面两种，它没有规避死锁的发生，但是会在死锁发生后进行检测，然后通过某种方法解除死锁。

预防和避免这两个词意思差不多，英文分别是 deadlock prevention 和 deadlock avoidance，也是差不多的。主要是处理方式不同，所以不要在意名字本身。

1. 预防死锁

前面讲到，死锁的产生需要同时满足四个条件。现在逐一看每一个条件是否有被破坏的可能。

① 破坏互斥条件

如果可以把某个互斥资源转化成共享资源，那么就不存在互相等待资源的情况了，也就不会发生死锁。借助 SPOOLing 假脱机技术，可以把互斥资源在逻辑上转化为共享资源。

在引入 SPOOLing 技术之前，进程 P1 和 P2 如果要利用打印机进行输出，那么它们是直接请求打印机资源的，比如 P1 请求并使用打印机进行输出，那么 P2 如果再请求的话就会被阻塞。

但是在引入 SPOOLing 技术之后，各个进程会把各自的输出内容放到一个新开辟的缓冲区里，缓冲区里形成一个输出内容队列，之后进程再继续向后执行。后面要利用打印机进行输出的时候，只需要读取队列上的内容即可。在整个过程中，由于各个进程面向的缓冲区是共享资源，所以轮到自己执行的时候只管把内容放到缓冲区即可，是不会发生死锁的。

② 破坏非抢占条件

如果资源是可以抢占的，那么在进程需要资源的时候，就可以直接抢占了，不存在互相等待资源的情况，也就不会发生死锁。要破坏非抢占条件，做到可抢占，可以从两个角度（方案）考虑：

• 从占有资源的进程的角度考虑，如果它请求不到新的资源，那么它必须立即释放占有的全部资源，以后需要的时候重新申请
• 从请求资源的进程的角度考虑，如果它需要请求资源，那么操作系统会帮助它抢占相关资源。比如现在有一个优先级更高的进程，如果是采用优先级调度算法，那么它将有机会在操作系统的帮助下抢占到资源。

这种做法的问题在于：

• 实现起来复杂
• 某个占有资源的进程释放占有的全部资源时，可能会导致工作进度丢失
• 反复的申请和释放资源会增加系统开销
• 可能导致饥饿

③ 破坏占有和请求条件

一般来说，资源是在进程运行的时候动态请求的，这就可能导致某个进程在占有资源的同时去请求资源，如果资源请求不到，就会带着占有的资源进入阻塞状态。所以可以考虑采用静态分配的方法，在进程运行之前就一次申请完需要的全部资源，如果资源不到位，就先不让它运行；如果资源到位，就让它带着资源运行。这样就确保了进程一定可以拿到资源执行任务，没有动态请求资源的过程，自然不会发生死锁。

该方法可能导致饥饿现象。设想有 ABC 三类进程，A 用到 a 资源，B 用到 b 资源，C 用到 ab 资源，那么 AB 会在运行前事先申请到 ab 资源，之后运行，如果 AB 源源不断进入就绪队列，那么 ab 资源就会不断被分配给 AB 进程，这样 C 进程由于没有办法在运行前拿到 ab 资源，所以迟迟无法运行，就进入了饥饿状态。

④ 破坏循环等待条件

循环等待就是 A 等 B，B 等 C，C 又回过头来等 A，形成了一个互相循环等待的闭环，从而陷入死锁。所以可以考虑“打破”这个闭环，具体做法是：给所有的资源编号，规定每个进程必须按照编号递增的顺序请求资源：必须先请求小编号资源，后请求大编号资源，请求大编号资源后，后续请求的资源只会比该资源编号更大。这样就成功打破了闭环。

以之前的例子讲解：

P1:          P2:
request(R1)  request(R2)
request(R2)  request(R1) 

这种情况下资源请求是无序的，尤其是 P2，它没有按照递增的顺序请求资源，因此很容易发生死锁。但是如果是这种情况：

P1:          P2:
request(R1)  request(R1)
request(R2)  request(R2) 

实际上，这里除了破坏“占有和请求条件”之外，更重要的是破坏了循环等待条件 —— 因为这里是按照编号递增的顺序请求资源了，不管是 P1 还是 P2，都是先请求小编号的 R1，后请求大编号的 R2，这样的话就不会发生死锁，因为此时两个进程对资源的请求并没有形成一个闭环。

也可以拿之前在 操作系统学习笔记-6：进程同步与进程互斥（三）：经典问题 提到的哲学家就餐问题解释，如下图：

最初的情况……

在最初的哲学家问题中，之所以发生死锁，本质上是因为每个哲学家都是先拿左边筷子，后拿右边筷子，由于 4 号右边的筷子是 0 号左边的筷子，最终形成了一个闭环。设想当每个哲学家都拿起左手筷子，当他们去申请右手筷子的时候，无一例外都会被阻塞，陷入死锁。

如果试图打破循环……

但是如果我们按照上图给每个筷子进行编号，规定必须按照编号递增的顺序申请资源，那么从 0 号到 3 号，它们依然会拿起左手边小编号的筷子，但是轮到 4 号的时候，情况就不一样了。因为对于 4 号来说，右手筷子编号更小，所以在拿到左手筷子之前，它会先试图拿右手筷子，又由于该筷子已经被 0 号拿走，此时 4 号被阻塞。而对于 3 号来说，没人和自己抢 4 号筷子了，所以 3 号哲学家此时可以拿到左右筷子，这样就避免了死锁。

还可以从另一个角度考虑，因为我们是按照编号递增的顺序请求资源的，设想在某一时刻，若干个进程中必定有一个进程的资源编号暂时是所有进程中最大的，那么该进程在此后申请新的资源的时候，只可能申请编号更大的资源，一方面避开了小编号、可能已经被拿走的资源（也就避开了阻塞和死锁），另一方面，大编号资源并没有被其他进程拿走，因此这个时候，该进程一定可以拿到资源，不会有死锁现象。

但这种预防死锁的方法，问题在于：

• 如何进行编号？从什么角度考虑？这是一个问题
• 如果增加资源或设备，需要重新进行编号吗？怎么编号？
• 虽然资源请求上是先小编号资源，后大编号资源，但是实际使用的时候可能是得先使用大编号资源，这就意味着小编号资源暂时用不到 —— 虽然用不到，但还是被进程占用，明显有资源浪费的问题。

2. 避免死锁

避免死锁的核心在于，如果资源在分配给某个进程后会在将来导致死锁，那么就不同意资源请求，取消资源的分配。

问题是，怎么知道将来是否会导致死锁呢？

2.1 安全序列和安全状态

• 如果系统按照某种序列分配资源，可以使得每个进程都拿到资源并顺利完成，那么这样的序列就叫做安全序列。只要至少有一个安全序列，就可以认为系统处于安全状态。
• 反之，如果这样的序列一个都没有，那么就会有进程拿不到资源，进而无法顺利完成，此时就认为系统处于不安全状态。当系统处于不安全状态的时候，有可能发生死锁。

如下图：

虽然进入不安全状态，并不一定意味着会发生死锁，但是本着以防万一的想法，我们可以设法让系统永远不会进入不安全状态，从而从根源上避免死锁的发生。这样，我们的思路就从避免死锁变成了避免不安全状态。

在确定要分配资源给进程之前，首先检测此次分配是否会导致进入不安全状态，进而导致可能发生的死锁。如果会，那么就取消此次资源的分配。

下面介绍具体的检测方法。

2.2 资源分配图算法

资源分配图算法即 Resource-Allocation Graph Algorithm，当各类资源都只有一个的时候，可以使用这种方法求解。资源分配图是描述进程和资源之间请求和分配关系的有向图，从进程指向资源的虚线代表资源需求（要使用），从进程指向资源的实线代表资源请求（申请使用），从资源指向进程的实线代表资源分配（正在使用）。

比如有 P1 P2 两个进程，它们都需要用到 R1 R2 两种资源。当前状态如下：

• 如果 P1 请求 R2 资源：那么就把 P1 到 R2 的需求边改为 R2 到 P1 的分配边，此时整个图中不存在回路，那么就认为系统处于安全状态，不会发生死锁。可以分配资源。
• 如果 P2 请求 R2 资源：那么就把 P2 到 R2 的需求边改为 R2 到 P2 的分配边，此时整个图中存在一条回路，那么就认为系统处于不安全状态，有可能发生死锁。不可以分配资源

根据前面的说法，即使进入不安全状态仅仅意味着有可能发生死锁，也要杜绝，所以 P2 不会请求到想要的资源。

2.3 银行家算法

银行家算法即 Banker’s Algorithm，当各类资源有多个的时候，可以使用这种方法求解。

银行家算法的基本思路如下：

由于涉及到了安全性算法，所以这里先解释安全性算法。安全性算法是银行家算法的一环，用于检测某个状态是安全状态还是不安全状态，并决定资源分配。

假如现在有 P0 ~ P4 共五个进程，ABC 三类资源，个数为（10,5,7）。在某一时刻，资源剩余量为（3,3,2），各个进程的最大需求量、已分配量和需求量如下图所示：

如何检测当前是否处于安全状态呢？尝试寻找安全序列：

• 当前剩余资源（3,3,2），无法满足 P0 需要的（7,4,3），所以不能首先分配给 P0；但是可以满足 P1 需要的（1,2,2），P3 需要的（0,1,1），所以可以分配给 P1 和 P3，P1 和 P3 进入安全序列。
• P1 和 P3 执行完之后，归还资源，剩余资源（3,3,2）+（2,0,0）+（2,1,1）=（7,4,3），可以满足 P0 需要的（7,4,3），P2 需要的（6,0,0），P4 需要的（4,3,1），所以 P0、P2、P4 依次进入安全序列
• 所以存在安全序列 P1->P3->P0->P2->P4 ，使得按照这个顺序分配资源后，每个进程都能拿到需要的资源并顺利完成，所以该状态是安全状态。

看另一种情况。假如现在有 P0 ~ P4 共五个进程，ABC 三类资源，个数为（10,5,7）。在某一时刻，资源剩余量为（3,3,2），各个进程的最大需求量、已分配量和需求量如下图所示：

当尝试寻找安全序列的时候，容易发现 P1 P3 可以满足，所以 P1 P3 进入安全序列，此后剩余资源为（7,4,3）。又由于 P0 P2 P4 都是无法满足的，所以实际上并不存在一个安全序列使得所有进程都能被分配资源。因此状态是不安全状态，可能发生死锁，取消资源分配。

现在来看银行家算法。

假设系统中有 n 个进程，m 种资源，规定：

• 每个进程在运行前先声明自己需要的最大资源数，用一个 n*m 的最大需求矩阵 Max 表示各个进程的需求情况，比如 Max[i][j]= K 就表示进程 i 需要 K 个 j 类型资源
• 用一个 n*m 的分配矩阵 Allocation 表示各个进程的已分配资源情况
• 用一个 n*m 的需求矩阵 Need 表示各个进程的最多还需要资源情况，Need = Max - Allocation
• 用一个 m 长度的一维数组 Avaliable 表示剩余资源数目
• 用一个 m 长度的一维数组 Request_i 表示某个进程 i 某次申请的资源数目

按照之前说过的流程图，银行家算法的工作过程是：

• 请求资源数是否超过最大资源数？Request_i[j]<=Need[i][j]，则到下一步；否则出错
• 请求资源数是否超过剩余资源数？Request_i[j]<=Available[j]，则到下一步；否则说明资源不够，进程等待
• 尝试进行资源分配。
  • 剩余资源减少：Available = Available - Request
  • 已分配资源增加：Allocation[i][j] = Allocation[i][j] + Request_i[j]
  • 需求资源减少：Need[i][j] = Need[i][j] - Request_i[j]
• 对分配后的状态通过安全性算法进行预判：
  • 安全状态：不会发生死锁，可以分配资源
  • 不安全状态：可能发生死锁，不分配资源

3. 检测和解除死锁

死锁的第三种处理策略是检测和解除死锁，与前面不同的是，这种策略没有规避死锁的发生，而是在死锁发生后进行检测，检测到死锁就将其解除。

3.1 检测死锁

检测死锁依然可以利用前面讲到的资源分配图，这里分为两种情况的死锁检测：

①各类资源只有一个

当各类资源只有一个的时候，可以把资源分配图化简为一个等待图（wait-for graph），比如说 A 进程请求 X 资源、X 资源被 B 进程占有，这个过程可以被简化为 A 进程等待 B 进程。比如说下面，左图被转化为对应的右图：

之后检测是否有回路，因为有回路，所以认为此时是存在死锁的。

②各类资源有多个

各类资源有多个的时候，我们可能需要根据给定表检测是否有死锁，还可能根据给定图检测是否有死锁。对于前者，可以沿用之前的安全性算法进行检测；对于后者，可以尝试化简资源分配图。

比如说，现在有 P0 ~ P4 共五个进程，ABC 三类资源，个数为（7,2,6）。在某一时刻，资源剩余量为（0,0,0），各个进程的最大需求量、已分配量和需求量如下图所示：

对于给定的表，可以用安全性算法检测是否处于死锁状态。因为剩余资源（0,0,0），所以 P0 P2 可执行；之后归还资源，剩余资源（3,1,3），所以 P1，P3，P4 可执行。所以存在安全序列 P0->P2->P1->P3->P4 ，此时认为该状态是安全状态，不会发生死锁。

但是如果稍微做一下改动（P2 对 C 资源的需求量加一）：

因为剩余资源（0,0,0），所以 P0 可执行；之后归还资源，剩余资源（0,1,0），此时其它四个进程都没有执行所需要的足够的资源数，因此不存在安全序列。此时认为该状态是不安全状态，一定发生死锁。并且发生死锁的进程是 P1，P2，P3，P4。

PS：这里需要注意的是，在避免死锁中使用的安全性算法，检测到不存在安全序列的时候，就认为处于不安全状态，可能发生死锁；但是在这里使用的安全性算法，一旦检测到不存在安全序列，就认为处于不安全状态，一定发生了死锁。

上面介绍的是给定表的死锁检测，如果给定的是资源分配图，应该如何检测死锁呢？以下图为例：

约定蓝色线为请求边，黑色线为分配边，资源中的一个圆点代表一个该类资源。那么 P1 占有两个 R1 资源，请求一个 R2 资源；P2 占有一个 R2 资源，一个 R1 资源，请求一个 R1 资源。

• 首先找出非阻塞非孤立的进程点。P1 P2 都不是孤立的，所谓非阻塞指的是进程请求的资源数量足够，比如说 P2 请求 R1，由于 R1 已经有两个被 P1 占有，一个被 P2 占有，无多余资源，所以 P2 请求的资源数量不够，P2 是阻塞的；而 P1 请求 R2，因为 R2 只有一个被 P2 占有，所以有多于资源，P1 请求的资源数量足够，P1 是非阻塞的。这样就找到了符合条件的进程点 P1
• 去除这样的点的所有边。那么就会去除 P1 的所有边，归还所有资源。P1 成为孤立点。
• 重复第一步和第二步。此时，因为这次 P2 请求的 R1 资源是足够的（被 P1 释放了），所以 P2 是非阻塞非孤立的点，把他的全部边去除
• 由于图中所有的边都能被消除，所以称该图可以被简化，因此它不存在死锁（如果不可简化，则存在死锁）

又比如下面这种情况：

首先还是找一个非孤立非阻塞的点，很显然只有 P3 符合要求。之后把 P3 的分配边去掉，会发现 P1 和 P2 都是非孤立阻塞的点，它们的边都无法消除。此时就说该资源分配图不能简化，因此存在死锁。

3.2 解除死锁

检测到死锁后，下一步就是解除死锁。有以下三种方法：

① 资源剥夺法：

将部分死锁的进程挂起（对换到外存上），并抢占它的资源，将这些资源分配给其它的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿。

② 撤销/终止进程法：

强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源。这种方式的优点是实现简单，但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间，已经接近结束了，一旦被终止就功亏一篑了，以后还得从头再来。

③ 进程回退法：

让一个或多个死锁进程回退到足以避免死锁的地步。这要求系统必须记录进程的历史信息，设置还原点。

无论是哪种方法，都会有进程需要做出牺牲，那么应该对谁下手呢？可以从下面这些角度考虑：

• 优先级比较低的进程做出牺牲
• 占用过多资源的进程做出牺牲
• 执行时间长的进程不做出牺牲（不然就功亏一篑了）
• 快要完成的进程不做出牺牲
• 交互式进程不做出牺牲

参考：

《王道考研》

OS CourseNotes