在之前的复习中，我们简要提到过死锁。这个概念极其重要，因此需要专门用一篇文章来进行重点讲解。当两个或更多的线程/进程在互相等待对方持有的资源，从而导致都在等待而无法继续执行时，死锁(Deadlock)就出现了。维基百科^1给了一个非常生动的生活例子：当两个人在狭窄的巷道里面对面碰上，由于互不相让，都在等待对方先让开，结果两人都无法通过。

死锁的观察

资源分配图

资源分配图(Resource Allocation Graph, RAG) 用于直观地展示当前系统中资源在各个进程之间的分配情况。

rag

如上图所示：

  • 圆圈：代表进程(Process)。
  • 方框(内含小圆圈)：代表资源(Resource)及其数量。
  • 资源 $\to$ 进程的箭头：表示该进程正在使用一个单位的该资源（已分配）。
  • 进程 $\to$ 资源的箭头：表示该进程正在请求该资源（请求）。

由于资源是有限的，如果进程申请不到所需的资源，就会进入阻塞态(Blocked)。例如，图中 $R_{1}$ 只有一个单位的资源，并且该资源正在被 $P_{1}$ 使用。如果 $P_{2}$ 想要申请资源 $R_{1}$，它就会进入阻塞态，必须等待 $P_{1}$ 释放该资源后才能继续。

注：当我们讨论死锁时，我们假设进程的代码逻辑都是“正确”的。所谓正确，是指不会出现由于进程自身的逻辑错误（例如，一个进程 $P$ 正在使用某个有限资源，却又再次请求该资源，导致自己锁死自己）而引起的死锁。

死锁与可复用资源

可复用资源(Reusable Resource)是指这类资源中的每个单位都可以被不同的进程依次请求和使用，使用完毕后会被释放，供其他进程再次使用。

状态图

资源分配图可以表示某一时刻资源的分配状态。另一种可以表示资源分配变换的模型称为状态转移(State Transitions)。我们知道，进程和资源之间的操作无非就是三种：

  1. 请求资源(Request)
  2. 使用资源(Use)
  3. 释放资源(Release)

死锁状态及安全状态

如果在状态 $S$ 中，一个进程处于阻塞态，并且无论之后的状态如何改变，都无法使该进程脱离阻塞态，那么我们就称这个处于阻塞状态的进程被锁死(Deadlocked)了。

如果一个状态包含两个或两个以上的进程被锁死，我们称它为死锁状态(Deadlock State)；反之，则称之为安全状态(Safe State)。

如下图所示，因为 $P_{2}$ 和 $P_{3}$ 请求的资源都被占用了，所以它们都被锁死了。这整个图是进程和资源之间关系变化中的一种情况，我们称它为一个状态(State)。由于该状态包含了两个锁死的进程，我们称这个状态为死锁状态。

deadlock_state_process

再看下图：

  1. $S_{0}$ 是一个死锁状态，因为它包含两个阻塞的进程。
  2. 通过执行一个释放资源的操作，使 $S_{0}$ 转到 $S_{1}$。
  3. 在 $S_{1}$，再进行一个使用资源的操作，使得 $P_{2}$ 可以使用资源 $R_{3}$。

可以看出，当我们从 $S_{0}$ 变成 $S_{2}$ 时，解除了死锁进程。回顾上面的定义：一个进程在后面的状态中无论如何改变也依然处于阻塞状态才是被锁死了。因此，$S_{0}$ 中的 $P_{1}$ 并没有被锁死。

state_trans

通过穷举所有可能的状态，我们可以观察进程竞争是否有可能进入死锁状态。当然，我们不需要将它们全部画出来。上面的状态图不必将所有细节都画出来，我们只要知道 $S_{0}$ 的结构就能推导出后面的状态。所以也可以简化为这样画：

state_trans

学过自动机理论的同学可能看出来这类似于一个确定有限状态自动机(Deterministic Finite Automaton, DFA)，但这是题外话了。

死锁的检测

我们可以用一个简化算法来检查资源分配图是否存在死锁：

1
2
3
while (图中存在非阻塞进程):
  选择一个非阻塞进程 P
  将 P 及其所有相关的箭头（包括 P 的请求和分配给 P 的资源）从图中移除

移除那些进程 $P$ 后，剩下的图就能给出死锁的信息。请记住两个定理：

  1. 一个状态 $S$ 是死锁状态，当且仅当该状态对应的资源分配图无法完全简化（即不能移除所有进程）。
  2. 对于拥有相同数量进程及资源的图，完全简化后的最简资源分配图都是唯一的。

我们来简化之前例子中的资源分配图：

reduce

首先是 $P_{1}$。因为 $P_{1}$ 是非阻塞状态，我们可以移除 $P_{1}$ 及其箭头。在 $P_{1}$ 被移除之后，$P_{2}$ 变成了非阻塞状态，所以也可以被移除。
如果最简资源图里有进程处于死锁状态，这个图将无法完全简化（并非所有进程都被移除）。

连续死锁检测

如果我们采用连续的方式进行测试，死锁检测还可以更高效。我们先定义几个逻辑陈述：

$I(x)$: 状态 $x$ 是一个死锁状态。
$P(p, x)$: 请求资源 $x$ 的进程 $p$ 当前处于死锁状态。
$K(p, s)$: 执行请求的进程 $P$ 在状态 $s$ 中是阻塞态。
$C(x)$: 转向状态 $x$ 的操作是一个请求操作。

然后给出这样一个成立的定理：

$$(¬I(CurrentState) \to I(NextState)) \to (P(Process, NextState) \land C(NextState))$$

翻译一下就是：

如果当前的状态 $S$ 不是死锁状态，那么它的下一个状态 $S’$ 是一个死锁状态的充要条件是：

  1. 转向 $S’$ 的是一个请求操作。
  2. 发出请求操作的进程 $P$ 在 $S’$ 中被锁死。

连续死锁检测的步骤如下：

如果当前的操作是一个请求操作，并且发出这个请求操作的进程在下个状态中被阻塞，那么就执行状态图简化算法，直到：

  1. 该进程被从状态图中移除，或者
  2. 图中再无阻塞进程。

如果 $P$ 被移出了状态图，那么 $S’$ 就不是一个死锁状态，算法完成。我们举一个例子：

假设有这样的一个状态转移：$S_{0}$ 通过请求操作进入 $S_{1}$。此时只有一个进程被阻塞，所以该状态不是死锁状态。$S_{1}$ 通过一个请求操作进入 $S_{2}$。因为有两个进程被阻塞。

c_deadlock

根据算法，当发现有 $S_{2}$ 这样的状态出现时，我们就测试连续死锁：
移除 $P_{2}$ 及其箭头，发现 $P_{1}$ 和 $P_{3}$ 脱离了死锁状态。因此，$S_{2}$ 并非死锁状态。

单一资源的死锁检测

等待图(Wait-for Graph)是一种只包含进程的资源分配图的简化版本。在等待图中，每个进程可以拥有多个占用资源，但只能有一个请求资源。

wait-for graph

如上图所示，左边是资源分配图，右边是对应的等待图。所谓“等待”，是指某个进程请求的资源被另一个进程占用，并因此进入了阻塞状态。而且我们有一个重要定理：

在单一资源类的资源分配图中，存在环（如图中 $P_{1}$ 和 $P_{2}$ 这样相互等待）是死锁的充分必要条件。

动态地避免死锁

除了像上面一样在发现死锁之后再解决，我们还可以在死锁发生之前就将其避免。

资源需求图

最大资源需求(Maximum Claim)是指一个进程在其整个生命周期中可能需要的所有资源的最大数量。一个进程将要请求但尚未请求的资源可以用一个带虚线的箭头来表示。

资源请求图(Resource Claim Graph)在资源配置图的基础上加入了一些新的元素，包括：

  1. 目前资源在进程之间的分配。
  2. 目前的资源请求以及潜在的（最大）资源请求。

下图展示了一个资源请求图，$P_{1}$有可能在下一个状态中请求 $R_{1}$ 和 $R_{2}$。

rcg

银行家算法

银行家算法(The Banker’s Algorithm)是一个模拟银行提供贷款的算法。想一下，银行的贷款和系统的资源分配有着非常相似的操作：

银行 操作系统
贷款 资源分配
客户的信用 最大资源需求

银行家算法的步骤：

  1. 在状态 $S$ 中，当有一个资源请求时，先假设该资源请求成功。
  2. 使用简化算法将假设后的新状态 $S’$ 进行简化。
  3. 如果该图可以完全简化（即存在一个安全序列），那么就接受这个新的状态，实际进行资源分配。否则，拒绝该资源分配请求，使系统保持在状态 $S$。

定理:

如果分配资源后的状态无法完全简化（即进入不安全状态），那便拒绝该分配。这样，资源需求图将永远保持在安全状态。

banker

我们来看看上面那个例子。我们的银行家算法先假设 $P_{1}$ 的请求会成功，进入 $S’$。由于有两个进程阻塞，我们要用简化算法尝试将 $P_{1}$ 移除。发现剩下的 $P_{2}$, $P_{3}$ 可以相继被移除，因此 $P_{1}$ 的请求是可以接受的。依此类推，我们可以找出所有的安全状态。

防止死锁

相比于每一步都要检测死锁来说，从根源上消除死锁存在的可能性是更高一层的策略。我们想想看死锁是怎么产生的，它需要满足四个必要条件（通常称为 Coffman 条件）：

  1. 互斥(Mutual Exclusion)：资源一次只能被一个进程使用。
  2. 请求与保持(Hold and Wait)：某进程一边持有资源 A，一边等待资源 B。
  3. 不可剥夺(No Preemption)：已分配给进程的资源在未使用完之前，不能被强行剥夺。
  4. 循环等待(Circular Wait)：存在一个进程等待队列 ${P_1, P_2, \dots, P_n}$，其中 $P_1$ 等待 $P_2$ 持有的资源，$P_2$ 等待 $P_3$ 持有的资源， $\dots$， $P_n$ 等待 $P_1$ 持有的资源。

如果我们能打破其中任何一个条件，死锁问题是否就能解决了呢？实际上，互斥和不可剥夺条件通常很难打破，因此我们主要关注破坏“请求与保持”和“循环等待”条件。

解决“请求与保持”

有三种方法可以解决**“请求与保持”**(Hold and Wait)的问题：

  1. 静态分配策略：只允许进程拥有一种类型的操作。进程在开始执行前，必须一次性请求其所需的所有资源。如果无法全部满足，则不分配任何资源，进程等待。这种方法可能会导致资源利用率低下，但能有效避免死锁。
  2. 释放后请求策略：如果进程 $A$ 正在使用资源 1，现在需要资源 2，它必须先释放资源 1，然后再同时请求资源 1 和资源 2。这在一定程度上解决了方法 1 中的资源利用率问题。
  3. 请求前检查策略：如果进程 $A$ 在使用资源 1，现在需要资源 2，它会先检查资源 2 的使用情况。如果没有其他进程占用，它就可以直接使用资源 2；如果有其他进程占用，它就会放弃所有正在使用的资源，然后重新申请所需的全部资源。

解决“循环等待”

我们可以将系统中的所有资源进行线性排序（例如，$R_0, R_1, \dots, R_n$）。规定一个正在占用 $R_i$ 的进程不可以申请 $R_k$，其中 $k < i$。也就是说，进程只能按升序申请资源。

这样一来，就不可能形成一个环形等待链，从而解决了循环等待问题。

[^1]: 维基百科编者. 死锁[G/OL]. 维基百科, 2023(20230815)[2023-08-15]. https://zh.wikipedia.org/wiki/%E6%AD%BB%E9%94%81.