死锁

重点内容，需熟练掌握死锁的产生条件、处理策略、预防方法以及银行家算法，在选择题中会考察，偶尔也在大题中考察。

死锁产生的必要条件

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

  1. 互斥条件（Mutual Exclusion）: 指的是至少有一个资源必须处于非共享模式，也就是说，一次只有一个进程可以使用资源。如果其他进程请求该资源，那么请求的进程必须等到该资源的持有者释放该资源。
  2. 占有并等待（Hold and Wait）: 指的是一个进程因请求资源而阻塞时，对当前获得的资源保持不放。换句话说，进程至少已经持有一个资源，但又申请新的资源；由于其他进程持有这些资源，所以它现在是阻塞的。
  3. 非抢占（No Preemption）: 资源不能被抢占，也就是说，只有资源的持有者才可以释放它。资源在完全自愿的基础上被释放，不能被强行从持有进程中夺走。
  4. 循环等待（Circular Wait）：存在一个进程资源的等待链，链中的每一个进程都在等待下一个进程所持有的资源。这导致了一个循环的等待链。

为了 避免死锁，需要 破坏 上述的任意一个条件。

P1
P2
P2
P4
A
B
C
D
占有
想要

上图中的进程就处于死锁状态。每个进程都既要又要，持有的不释放，想要的也得不到，也不允许其他进程去抢占自己所占有的，所有的进程和资源之间组成一个循环链条。以上这些特点决定了系统进入了死锁状态。

死锁处理策略

处理死锁 主要包含三种策略：

  1. 死锁预防：设置限制条件，破坏产生死锁的 4 个必要条件之一。
  2. 死锁避免：在资源的动态分配过程中，用某种算法避免系统进入不安全状态。
  3. 死锁的检测和解除：允许进程在运行过程中发生死锁，通过系统检测机构及时检测出死锁的发生，然后采取某种措施解除死锁。

死锁预防

死锁预防是通过确保系统永远不会满足死锁产生的四个必要条件中的某些条件，从而避免死锁的发生：

  1. 破坏互斥条件
    • 互斥条件在某些情况下是不可避免的，例如打印机等硬件资源。但在某些场景下，通过资源复制或虚拟化技术，可以尝试减少资源的互斥使用。
  2. 破坏占有并等待
    • 要求进程在开始时一次性申请其需要的所有资源。只有当所有资源都可用时，进程才被分配资源并开始执行。这样，进程在执行期间不会等待其他资源。
    • 另一个方法是，如果进程申请新资源而被拒绝，则它必须释放所有已分配的资源，再重新申请。
  3. 破坏非抢占
    • 当一个进程需要的资源被另一个进程所占有时，它可以抢占另一个进程的资源。
  4. 破坏循环等待
    • 对进程申请资源的顺序进行限制

死锁避免

死锁避免是系统级的算法，需要对系统的资源和实体进行抽象，进行统筹规划，其中最经典的算法是 银行家算法。

银行家算法

这里首先说一下次算法的命名，为什么叫“银行家”。一般而言，银行家都具备以下特点：

  • 掌管金库（即资源），可以放贷（即满足进程申请的资源）
  • 理性地作出决策，避免银行破产（即系统进入不安全状态）

相对于银行家的就是客户（即进程），进程需要申请一定量的资源。
但是进程可能不会立即申请全部的资源，进程也许会依次申请所有请求资源中的一部分，当进程申请完全部的资源之后，它才会释放这些资源。

为了对刚刚描述的过程进行建模，我们需要定义如下的 数据结构：

  • 系统
    • Available：表示每种资源的 可用数量。
  • 进程
    • Max：表示每个进程对每种资源的 最大需求量。
    • Allocation：表示已经 分配给 每个进程的资源数量。
    • Need：表示每个进程 还需要 的资源数量，Need = Max - Allocation

系统中所有进程的资源状态可以用下表所示：

MAX
A
B
C
Allocation
Need
Available
A
B
C
A
B
C
A
B
C
P0
P1
P2
P3
P4
7
5
3
3
2
2
9
0
2
2
2
2
4
3
3
0
1
0
2
0
0
3
0
2
2
1
1
0
0
2
7
4
3
1
2
2
6
0
0
0
1
1
4
3
1
3
3
2
算法步骤
  1. 初始化：为每个进程和每种资源设置 Max、Allocation 和 Need。
  2. 当一个进程请求资源时，检查请求的资源数量是否 小于等于 Need，如果大于则请求失败。
  3. 检查请求的资源数量是否 小于等于 Available，如果大于则请求失败。
  4. 如果请求合法（满足上述两个条件），则 模拟分配 资源给该进程（预分配），即将资源从系统的 Available 减去，加到进程的 Allocation 中，并从进程的 Need 中减去相应数量的资源。
  5. 然后，进行 安全性检查，判断是否存在一种 安全分配序列，使得所有进程都能顺利执行完成。
  6. 如果存在 安全分配序列，则执行资源分配，否则拒绝请求，因为分配资源可能导致死锁，并且回收预先模拟分配的资源。
  7. 当进程完成任务时，释放已分配的资源，将它们从 Allocation 减去，加到 Available 中。

银行家 算法流程 如下图所示：

进程提出资源请求
Y
N
资源数是否 ≤
进程可拥有的最大值
分配失败
N
资源数是否 ≤
系统可分配量
系统预分配
系统执行安全性检查算法
在系统试分配的基础上，统计
系统剩余资源量
Y
Y
能否找到一个可执行
进程，执行并回收其
占用的资源
N
Y
能否找到一条
安全序列
分配成功
银行家算法
安全性检查算法
安全分配序列

安全分配序列 是进程的一个排列，它保证了对于序列中的每个进程，当这些进程都申请 Need 中的全部资源时，系统都能够满足这些需求。

如果系统存在一个 安全分配序列，则系统处于 安全状态 。

注意

不安全状态不意味着死锁，但它意味着有死锁的风险。不安全状态只是死锁的一个先兆，但不是死锁本身。

对于前图中的各进程状态，我们可以得到如下的一个 安全分配序列：

A
B
C
安全分配序列
资源
3
3
2
P1
5
3
2
P3
7
4
3
P0
7
5
3
P2
10
5
5
P4
10
5
7

具体计算过程如下：

  • 首先，available = (3, 3, 2) > P1_Need = (1, 2, 2)，分配资源给 P1 后回收 P1_Allocation = (2, 0, 0)，然后 available 增加为 (5, 3, 2)
  • 其次，available = (5, 3, 2) > P3_Need = (0, 1, 1)，分配资源给 P3 后回收 P3_Allocation = (2, 1, 1)，然后 available 增加为 (7, 4, 3)
  • …..
  • 以此类推，得到 安全序列 P1、P3、P0、P2、P4
安全性检查

安全性检查 即判断系统中是否至少存在一个 安全分配序列，其过程如下：

假设系统中存在 N 个进程的话，则最多进行 N 轮遍历，每一轮至少找到一个 need 小于或等于 available 的进程，如果可以找到的话，就回收这些进程的 allocation，并将其加入 available 中，直到回收了所有进程的资源。如果有一轮存在这种情况：剩余的进程（任务未完成的进程）中的每一个 need 都大于 available，那么则说明无法找到一个 安全分配序列，系统处于 不安全状态。

这种判断方式的背后具有这样的逻辑：因为进程必须申请完所有需要的资源（即 max）才能返还已申请的资源，所以系统在当下肯定是尽量满足那些可以返还资源的进程，因为只有回收了一些资源之后，才能满足之前可能无法满足的进程。

但是如果在某一个时刻，剩余的进程的资源一个都无法回收了，那么系统就进入了 不安全状态。

这里还要需要注意的是，在实际的算法中，我们需要用 work 替代 available 来帮助我们完成 安全性检查 的过程，因为检查只是一种“逻辑推演”，我们并不希望实际修改系统中的资源情况，具体的代码实现可以参考如下链接：

银行家算法代码实现

死锁的检测和删除

为了能对系统是否已发生了 死锁 进行检测，必须：

  1. 用某种数据结构来保存资源的请求和分配信息：
  2. 提供一种算法，利用上述信息来检测系统是否已进入 死锁 状态。

一般来说，一种简单的建模方式是使用 资源分配图：

  • 将系统中的所有资源和进程表示为图中的节点。
  • 如果进程 P1 请求资源 R1，绘制从 P1 到 R1 的有向边。
  • 如果资源 R1 分配给了进程 P2，绘制从 R1 到 P2 的有向边。

在构建完 资源分配图，可以通过使用 DFS 检查图中是否存在环路以判断是否存在死锁。