死锁

真题练习

本节需要区分死锁的必要条件、预防、避免、检测与解除，并能按向量逐步执行银行家算法的安全性检查。

死锁产生的必要条件

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

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

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

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

死锁处理策略

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

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

死锁预防

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

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

死锁避免

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

银行家算法

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

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

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

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

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

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

算法步骤

1. 初始化：为每个进程和每种资源设置 Max、Allocation 和 Need。

2. 当进程 $P_i$ 请求资源向量 $\mathbf{Request}_i$ 时，逐分量检查 $\mathbf{Request}_i\le\mathbf{Need}_i$；否则说明请求超过其事先声明的最大需求。

3. 再逐分量检查 $\mathbf{Request}_i\le\mathbf{Available}$；否则当前资源不足，进程必须等待。

4. 两项均满足时进行 模拟分配：

   $$\begin{aligned} \mathbf{Available}&\leftarrow\mathbf{Available}-\mathbf{Request}_i,\\ \mathbf{Allocation}_i&\leftarrow\mathbf{Allocation}_i+\mathbf{Request}_i,\\ \mathbf{Need}_i&\leftarrow\mathbf{Need}_i-\mathbf{Request}_i. \end{aligned}$$

5. 然后，进行安全性检查，判断是否存在一种 安全分配序列，使得所有进程都能顺利执行完成。

6. 如果存在 安全分配序列，则执行资源分配，否则拒绝请求，因为分配资源可能导致死锁，并且回收预先模拟分配的资源。

7. 当进程完成任务时，释放已分配的资源，将它们从 Allocation 减去，加到 Available 中。

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

安全分配序列

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

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

注意

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

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

具体计算过程如下：

• 初始 $\mathbf{Work}=(3,3,2)$，且 $\mathbf{Need}_1=(1,2,2)\le\mathbf{Work}$。模拟 P1 完成并回收 $\mathbf{Allocation}_1=(2,0,0)$，得到 $\mathbf{Work}=(5,3,2)$。
• $\mathbf{Need}_3=(0,1,1)\le(5,3,2)$。回收 $\mathbf{Allocation}_3=(2,1,1)$，得到 $\mathbf{Work}=(7,4,3)$。
• $\mathbf{Need}_0=(7,4,3)\le(7,4,3)$。回收 $\mathbf{Allocation}_0=(0,1,0)$，得到 $\mathbf{Work}=(7,5,3)$。
• $\mathbf{Need}_2=(6,0,0)\le(7,5,3)$。回收 $\mathbf{Allocation}_2=(3,0,2)$，得到 $\mathbf{Work}=(10,5,5)$。
• $\mathbf{Need}_4=(4,3,1)\le(10,5,5)$。回收 $\mathbf{Allocation}_4=(0,0,2)$，最终 $\mathbf{Work}=(10,5,7)$。

因此可得到安全序列 $\langle P_1,P_3,P_0,P_2,P_4\rangle$。每一步的“$\le$”都是对每种资源分别比较，不能比较向量元素之和。

安全性检查

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

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

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

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

还需要注意：在实际算法中，用 Work 的副本替代 Available 来完成安全性检查。检查只是逻辑推演，不能实际修改系统资源；只有请求通过检查后，才提交前面的试分配。

// 返回 1 表示存在安全序列；safe[] 记录该序列。
int findSafeSequence(const int available[],
                     const int maximum[][RESOURCES],
                     const int allocation[][RESOURCES],
                     int safe[]) {
    int work[RESOURCES];
    int finish[PROCESSES] = {0};
    int count = 0;

    for (int j = 0; j < RESOURCES; j++) work[j] = available[j];

    while (count < PROCESSES) {
        int chosen = -1;
        for (int i = 0; i < PROCESSES && chosen < 0; i++) {
            int j = 0;
            for (; j < RESOURCES; j++) {
                int need = maximum[i][j] - allocation[i][j];
                if (finish[i] || need > work[j]) break;
            }
            if (j == RESOURCES) chosen = i;
        }
        if (chosen < 0) return 0;      // 没有任何剩余进程可完成：不安全

        for (int j = 0; j < RESOURCES; j++) {
            work[j] += allocation[chosen][j];  // 模拟完成后归还资源
        }
        finish[chosen] = 1;
        safe[count++] = chosen;
    }
    return 1;
}

死锁的检测和解除

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

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

资源分配图

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

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

构建 资源分配图 后，可以用 DFS 检查环路，但结论取决于资源实例数：

• 每类资源只有一个实例时，图中存在环是死锁的充分必要条件；
• 某类资源有多个实例时，存在环只是死锁的必要条件，不能据此直接判死锁，还需使用基于 Available、Allocation 和 Request 的检测算法。

检测到死锁后，可通过终止一个或多个进程、抢占并回滚资源等方式解除；选择受害者时需考虑优先级、已执行时间、占有资源量与回滚代价。