1. 死锁的定义#

在多道程序系统中，进程的并发执行显著提高了系统资源的利用率和整体效率。然而，这种并发性也带来了新的问题——死锁。所谓死锁，是指多个进程因竞争资源而陷入相互等待的僵局：每个进程都在等待其他进程所占有的资源，而这些资源又不会被释放，从而形成一个循环等待链。结果，所有涉及的进程都被永久阻塞；若无外部干预，它们将无法继续推进。

下面通过实例说明死锁现象。

先看一个生活中的类比。假设有一条狭窄的小巷，仅容一辆车通行。若有两辆汽车分别从巷子的两端同时驶入，且双方都坚持前行而不愿倒车，则两车将在巷中对峙，彼此阻挡，谁也无法通过。这种互相等待、互不让步的情形，恰如计算机系统中的死锁。

在计算机系统中，死锁的表现更为典型。例如，某系统中仅配备一台打印机和一台扫描仪。进程 $P_1$ 当前正占有扫描仪，并请求使用打印机；与此同时，进程 $P_2$ 正占有打印机，并请求使用扫描仪。由于每个进程都持有对方所需的资源，且都不主动释放，两个进程便陷入无限期的相互等待之中，无法继续执行。此时，系统就处于死锁状态。

2. 死锁与饥饿#

一组进程处于死锁状态，是指其中每个进程都在等待某个事件的发生，而该事件只能由组内另一个进程触发，通常表现为等待对方释放其所占有的资源。

与死锁密切相关但本质不同的另一个问题是饥饿，是指某个进程因资源分配策略的不公平性，长期得不到所需资源，从而无法推进其执行。产生饥饿的主要原因是：当多个进程同时竞争同一类资源时，若系统采用的分配策略不能保证“等待时间有上界”（无法确保每个等待进程最终都能获得服务），则某些进程就可能被无限期推迟。例如，当多个进程需要打印文件时，若系统采用“最短作业优先”的打印调度策略，则长文件的打印请求可能因不断有新的短文件到达而始终无法获得服务，最终陷入饥饿状态。需要注意的是，饥饿并不等同于死锁：系统可能仍在正常运行，其他进程可以顺利执行，只是个别进程被持续忽略。

死锁与饥饿的共同点如下：相关进程都无法顺利向前推进。二者的主要区别如下：

1. 涉及的进程数量不同，饥饿可以只影响单个进程；而死锁必须涉及两个或更多的进程，且它们之间存在循环等待关系。
2. 进程所处的状态不同，处于饥饿状态的进程可能处于就绪态（例如，在SPF调度算法中长期得不到CPU），也可能处于阻塞态（例如，长期等待某个I/O设备）；而处于死锁状态的进程则必定处于阻塞态，因为它们正在等待已被其他死锁进程占有的资源。

3. 死锁产生的原因#

4. 死锁产生的必要条件#

死锁的发生必须同时满足以下四个条件；只要其中任一条件不成立，死锁就不可能发生。

1. 互斥条件。进程对所分配的资源（如打印机）要求排他性使用，即在一段时间内，某资源只能被一个进程占有；若有其他进程请求该资源，则必须等待。
2. 不可剥夺条件。进程已获得的资源在使用完毕之前，不能被其他进程强行剥夺，只能由该进程主动释放。
3. 请求并保持条件。进程在持有至少一个资源的同时，又提出新的资源请求；若该资源已被其他进程占有，则请求进程被阻塞，但对其已占有的资源仍保持不放。
4. 循环等待条件。存在一个进程集合 $\{P_1, P_2, \cdots, P_n\}$，其中每个进程 $P_i$ 等待的资源正被下一个进程 $P_{(i+1)\bmod n}$ 占有，从而形成一个循环等待链，如图2.14所示。

直观上看，循环等待条件似乎与死锁的定义相同，实则不然。

资源分配图中存在环，并不必然意味着死锁。其根本原因在于：当某类资源有多个实例时，即使图中存在环，系统仍可能通过资源重分配打破僵局。例如，在图2.15中，若输出设备有两个实例，进程 $P_0$ 和 $P_K$($K \notin \{0, 1, \cdots, n\}$) 各持有一台。当 $P_n$ 请求一台输出设备时，只要 $P_0$ 或 $P_K$ 任一释放其所持有的设备，$P_n$ 即可获得所需资源，从而解除等待环。

因此，只有当系统中每类资源均仅有一个实例时，资源分配图中的环才成为死锁的充分必要条件；否则，环的存在仅表明系统处于潜在风险状态，未必实际发生死锁。

区分不可剥夺条件与请求并保持条件，通过以下例子说明：若你手中持有一个苹果，他人不能强行将其拿走（使你暂时不吃），这体现了不可剥夺条件；若你已持有一个苹果，又去请求第二个苹果，但在获得第二个苹果前拒绝放下第一个，则体现了请求并保持条件。

5. 死锁的处理策略#

处理死锁主要有三种策略：一是通过协议预防或避免死锁，确保系统永不进入死锁状态；二是允许死锁发生，但能检测并恢复；三是完全忽略死锁问题，假定其不会出现。其中，第一种策略包含预防死锁和避免死锁两种方法；第二种策略包含检测及解除死锁方法；第三种策略被大多数通用操作系统（如Linux 和 Windows）所采用。下面简要介绍这些处理方法。

1. 预防死锁。通过设置严格的限制条件，破坏死锁的四个必要条件中的一个或多个，从根本上杜绝死锁的可能。
2. 避免死锁。在资源动态分配过程中，通过特定算法判断分配后系统是否仍处于安全状态，仅当安全时才允许分配，从而避免进入可能导致死锁的不安全状态。
3. 检测及解除死锁。不施加任何预防性限制，允许进程自由申请资源；系统定期运行检测算法，一旦发现死锁，便采取相应措施（如终止部分进程或剥夺其资源）予以解除。

预防与避免死锁均属于事前防范策略。死锁预防的限制条件较为严格，实现相对简单，但往往导致系统效率和资源利用率较低；死锁避免的限制条件相对宽松，但需在每次资源分配前通过算法判断系统是否仍处于安全状态，实现较为复杂。各类策略的对比如表2.5所示。

表2.5 死锁处理策略的比较

1. 破坏互斥条件#

若将原本只能互斥使用的资源改造为允许多个进程共享访问，则可避免死锁。然而，许多资源（如打印机、磁带机等临界资源）本质上不支持并发访问，否则会导致数据不一致或设备冲突。因此，互斥性通常是保障系统正确性的基本要求，破坏该条件在实践中并不可行。

2. 破坏不可剥夺条件#

当一个已占有某些不可剥夺资源的进程请求新资源而无法满足时，系统强制释放其已占有的所有资源，待后续需要时再重新申请。这意味着，资源被临时剥夺，从而破坏不可剥夺条件。

该策略实现复杂且代价高昂：对于打印机等不可剥夺的外部设备，强制释放可能导致已完成的工作失效，甚至引发设备状态混乱。此外，频繁的申请与释放会显著增加系统开销，延长进程周转时间，降低系统吞吐量。因此，该方法在实际系统中极少采用。

3. 破坏请求并保持条件#

要求进程在请求新资源时不得持有任何不可剥夺资源。可通过以下方式实现。

1. 静态资源分配：进程在运行前一次性申请所需全部资源。若系统无法满足，则进程暂不投入运行。运行期间不再提出新请求，从而避免“请求并保持”行为。
2. 动态释放后申请：作为对方法一的改进，进程在获得初期所需资源后即可开始执行；但在运行过程中，必须先释放所有已使用完毕的资源，才能申请新资源。

方法一的优点是实现简单，但存在明显缺点：

1. 资源浪费严重：进程在运行初期即占有全部所需资源，其中部分资源可能仅在运行末期才使用，甚至从未被使用，导致长期闲置；
2. 易引发饥饿现象：由于某些资源长期被其他进程占有，等待这些资源的进程可能迟迟无法启动。

4. 破坏循环等待条件#

采用资源有序分配法：为系统中每类资源赋予唯一的编号，并规定进程必须按编号递增的顺序请求不同类资源，且同类资源须一次性申请。换言之，进程只有在未持有任何资源，或仅持有较小编号的资源时，才被允许申请更大编号的资源。按此规则，任何已持有大编号资源的进程都无法再申请小编号资源，从而确保资源分配图中不可能出现环，从根本上杜绝死锁。

该方法的缺点：

1. 资源编号需相对稳定，不利于新增设备类型。
2. 尽管在编号时已尽量考虑大多数进程使用资源的顺序，但实际使用资源的顺序仍可能与编号次序不一致，导致资源提前占用而长期闲置，造成浪费。
3. 强制按固定次序申请资源，增加了用户编程的复杂性。

1. 系统安全状态#

在死锁避免机制中，系统允许进程动态申请资源，但在进行资源分配前，必须先评估此次分配的安全性：若分配后系统仍处于安全状态，则允许分配；否则，进程需等待。

所谓安全状态，是指系统存在某个进程执行序列 $\{P_1, P_2, \cdots, P_n\}$，使得对于序列中的每个进程 $P_i$，在其之前的所有进程执行完毕并释放所占资源后，系统仍有足够的可用资源满足 $P_i$ 的尚需资源量（最大需求减去已分配量），从而保证 $P_i$ 能顺利完成。这样的序列称为安全序列（可能存在多个）。若系统无法找到任何一个安全序列，则称系统处于不安全状态。

假设系统中有三个进程 $P_1$、$P_2$ 和 $P_3$，共有12台磁带机。各进程的最大需求分别为：$P_1$ 需10台，$P_2$ 需4台，$P_3$ 需9台。在 $T_0$ 时刻，各进程已分配资源及系统可用资源如表2.6所示。

表2.6 资源分配

在 $T_0$ 时刻，系统处于安全状态，因为存在安全序列 $\{P_2, P_1, P_3\}$：若按此顺序推进进程，每个进程在其轮次均可获得所需资源并顺利完成。具体而言，当前可用资源为3，$P_2$ 尚需2台，可立即满足，$P_2$ 完成后释放其全部4台资源，可用资源变为5；$P_1$ 尚需5台，恰好可满足，$P_1$ 完成后释放10台，可用资源增至10；$P_3$ 尚需7台，可被满足，最终顺利完成。

若在 $T_0$ 时刻之后，系统将1台分配给 $P_3$，则 $P_3$ 已分配量变为3，可用资源降为2。此时，系统进入不安全状态，因为无法再找到任何安全序列。例如，若将剩余的2台分配给 $P_2$（其尚需2台），$P_2$ 可完成并释放4台，可用资源变为4。然而，$P_1$ 尚需5台，$P_3$ 尚需6台（因已分配3台），均无法满足。两个进程相互等待对方释放资源，陷入僵局，最终导致死锁。

系统处于安全状态时，一定不会发生死锁；而处于不安全状态时，死锁可能发生，但并非必然发生。换言之，死锁发生时，系统必定处于不安全状态，但不安全状态不一定会演变为死锁。

2. 利用银行家算法避免死锁#

银行家算法是最著名的死锁避免算法。其基本思想是：将操作系统视为银行家，系统管理的资源视为银行资金，进程请求资源相当于用户申请贷款。每个进程在运行前需声明其对各类资源的最大需求量（且该最大需求量在整个生命周期内不得更改，否则银行家算法的安全性保证失效），且该总量不得超过系统资源总量。当进程在运行中申请资源时，系统首先检查当前是否有足够资源可供分配；若有，则进一步试探：若将这些资源分配给该进程，系统是否仍处于安全状态。只有在确保安全的前提下，才正式分配资源；否则，就让进程等待。

1
Available[j] = Available[j] - Request_i[j]          #减少系统可用资源，反映资源已被分配
2
Allocation[i,j] = Allocation[i,j] + Request_i[j]    #增加 P_i 已分配的资源量
3
Need[i,j] = Need[i,j] - Request_i[j]                #减少 P_i 尚需的资源量

1
Finish[i] == false  #尚未加入安全序列
2
Need[i] <= Work     #其尚需的各类资源数均不超过当前可用资源

1
Work = Work + Allocation[i] #释放其已分配的各类资源
2
Finish[i] = true            #将其加入安全序列

3. 安全性算法举例#

假定系统中有5个进程 $\{P_0, P_1, P_2, P_3, P_4\}$ 和3类资源{A, B, C}，各类资源的总量分别为10, 5, 7，在 $T_0$ 时刻的资源分配情况见表2.7。现利用安全性算法，判断系统此时是否处于安全状态。

表2.7 $T_0$ 时刻的资源分配表

1. 首先，由题目给出的 Max 矩阵和 Allocation 矩阵，可计算出 Need 矩阵：

Max - Allocation = Need 7 5 3 0 1 0 7 4 3 3 2 2 2 0 0 1 2 2 9 0 2 3 0 2 6 0 0 2 2 2 2 1 1 0 1 1 4 3 3 0 0 2 4 3 1

由此得到各进程的尚需资源数。

2. 初始化工作向量 Work = Available = (3, 3, 2)。将 Work 与 Need 矩阵的各行进行比较，寻找满足 Need[i] <= Work（各分量均不超过）且 Finish[i] = false 的进程。初始时：

进程 $P_1$ 和 $P_3$ 均满足条件。此处选择 $P_1$（也可选择 $P_3$）作为安全序列的第一个进程。

3. 将 $P_1$ 加入安全序列，并模拟其顺利完成：释放其所占资源，更新工作向量：

同时，标记 Finish[1] = true。

以更新后的 Work = (5, 3, 2) 重复上述过程，继续查找下一个可执行的进程。以此类推，整个分析过程如表2.8所示（表中“Work+Allocation”列即为下一步的Work值），最终构造出一个完整的安全序列 $\{P_1, P_3, P_4, P_2, P_0\}$，表明系统在 $T_0$ 时刻处于安全状态。

表2.8 $T_0$ 时刻的安全序列的分析

4. 银行家算法举例#

安全性算法是银行家算法的核心。在典型考题中，通常会给出某个进程的资源请求向量。读者只需执行银行家算法的前三个步骤，即可得到更新后的 Allocation 和 Need 矩阵，再参照上例的安全性算法判断系统是否仍处于安全状态，从而决定是否批准该请求。假设当前系统资源分配及剩余情况如表2.7所示($T_0$ 时刻的状态)。

1. 进程 $P_1$ 发出请求向量 $Request_1(1, 0, 2)$，系统按银行家算法进行如下检查。

   1. 合法性检查：$Request_1(1, 0, 2) \le Need_1(1, 2, 2)$，成立。

   2. 资源可用性检查：$Request_1(1, 0, 2) \le Available_1(3, 3, 2)$，成立。

   3. 试探性分配：系统尝试为 $P_1$ 分配资源，并修改相关数据结构：

      $Available = Available - Request_1 = (2, 3, 0)$

      $Allocation_1 = Allocation_1 + Request_1 = (3, 0, 2)$

      $Need_1 = Need_1 - Request_1 = (0, 2, 0)$

      由此形成的资源变化情况如表2.7中的圆括号所示。

   4. 安全性检查：令 Work = Available = (2, 3, 0)，执行安全性算法，过程如表2.9所示。

表2.9 $P_1$ 申请资源时的安全性检查

由表可知，存在安全序列 $\{P_1, P_3, P_4, P_0, P_2\}$，系统处于安全状态。因此，可以正式将 $P_1$ 所请求的资源分配给它。分配后系统的资源状态如表2.10所示。

表2.10 为 $P_1$ 分配资源后的有关资源数据

2. $P_4$ 发出请求向量 $Request_4(3, 3, 0)$，系统按银行家算法进行检查：

   1. 合法性检查：$Request_4(3, 3, 0) \le Need_4(4, 3, 1)$，成立。
   2. 资源可用性检查：$Request_4(3, 3, 0) > Available(2, 3, 0)$，不成立，让 $P_4$ 等待。

3. $P_0$ 发出请求向量 $Request_0(0, 2, 0)$，系统按银行家算法进行检查：

   1. 合法性检查：$Request_0(0, 2, 0) \le Need_0(7, 4, 3)$，成立。

   2. 资源可用性检查：$Request_0(0, 2, 0) \le Available(2, 3, 0)$，成立。

   3. 试探性分配：系统尝试为 $P_0$ 分配资源，并修改相关数据结构：

      $Available = Available - Request_0 = (2, 1, 0)$

      $Allocation_0 = Allocation_0 + Request_0 = (0, 3, 0)$

      $Need_0 = Need_0 - Request_0 = (7, 2, 3)$

      结果如表2.11所示。

      表2.11 为 $P_0$ 分配资源后的有关资源数据

      资源情况	Allocation			Need			Available
      进程名	A	B	C	A	B	C	A	B	C
      $P_0$	0	3	0	7	2	3	2	1	0
      $P_1$	3	0	2	0	2	0
      $P_2$	3	0	2	6	0	0
      $P_3$	2	1	1	0	1	1
      $P_4$	0	0	2	4	3	1

   4. 安全性检查：此时 Available(2, 1, 0)，无法满足任何进程的尚需资源，系统进入不安全状态，因此拒绝 $P_0$ 的请求，撤销试探性分配，并恢复各数据结构至分配前状态。

1. 死锁检测#

区分死锁避免与死锁检测。死锁避免要求在进程运行过程中始终确保系统不会进入死锁状态，因此需要预先知道进程从开始到结束的全部资源需求。死锁检测则仅判断当前时刻系统是否已发生死锁，无须预知进程未来的资源请求，只需依据当前的资源分配和请求情况。

通常采用资源分配图来检测系统是否处于死锁状态。在资源分配图中：圆圈表示进程，矩形框表示一类资源；若某类资源有多个实例，则在框内用多个圆点表示；请求边（从进程指向资源）表示该进程申请一个单位的该类资源；分配边（从资源指向进程）表示该类资源的一个实例已分配给该进程。进程 $P_1$ 已获得两个 $R_1$ 资源，并请求一个 $R_2$；$P_2$ 已获得一个 $R_1$ 和一个 $R_2$，并请求一个 $R_1$。系统中存在环，但尚未确定是否死锁。

通过简化资源分配图可判断系统是否处于死锁状态。简化步骤如下。

1. 在资源分配图中，找出当前可继续执行的进程 $P_i$（其所有资源请求均可被当前空闲资源满足）。空闲资源数量等于该类资源总数减去已分配实例数（资源节点发出的分配边数量）。例如，在图2.16(a)中，$R_1$ 总数为3，出度为3，故无空闲资源；$R_2$ 总数为2，出度为1，故有1个空闲。$P_1$ 仅请求1个 $R_2$，而 $R_2$ 有1个空闲，因此 $P_1$ 可继续执行。将其所有请求边和分配边删除，使之成为孤立节点。
2. $P_1$ 释放的资源可能使其他阻塞进程的请求得以满足，从而转为可执行状态。例如，$P_1$ 释放其占有的 $R_1$ 资源后，$P_2$ 的 $R_1$ 请求即可满足，因而也能继续执行。重复上述过程，若最终能删除图中所有边，则称该图可完全简化。

死锁定理：系统处于死锁状态，当且仅当其资源分配图不可完全简化。

2. 死锁解除#

一旦检测出死锁，系统应立即采取措施予以解除。主要方法包括如下几种。

1. 资源剥夺法。挂起部分死锁进程，抢占其资源并重新分配给其他死锁进程，以打破死锁环路；但需防止被挂起的进程因长期得不到所需资源而陷入饥饿。

NOTE

在资源分配图中，经死锁定理化简后，仍有边相连的进程即为死锁进程。

2. 撤销进程法。强制终止部分或全部死锁进程，并回收其所占资源。终止顺序可依据进程优先级或撤销代价（如资源占有量等）确定。该方法实现简单，但代价可能较高，尤其当进程已接近完成时，一旦被终止，已完成的工作将全部丢失，后续需从头执行。
3. 进程回退法。令一个或多个死锁进程回退到之前某个足以回避死锁的状态，并在回退过程中自愿释放其所占资源。系统需记录进程的历史状态并设置还原点，实现较复杂。