死锁：僵局的形成与化解

本篇对应王道第二章收尾（原 11 篇）。上一章管好了同步互斥，这一章处理极端情况：多个进程互相等待，谁也动不了。

一、死锁是什么

定义：多个进程因竞争资源而造成的一种僵局（相互等待），若无外力作用，这些进程都将无法向前推进。

独木桥比喻：河上一座窄桥，一次只能过一辆车。左右两端各驶上一辆车——左边车占着左半段，要等右边车让出右半段；右边车占着右半段，要等左边车让出左半段。双方都只肯向前，谁也过不去。

计算机里的对应版本：系统只有一台打印机和一台输入设备。P1 占着输入设备，又要申请打印机；打印机正被 P2 占着，而 P2 在释放打印机之前又申请输入设备。两个进程无休止地互相等待，都执行不下去了。

死锁产生的原因

1. 系统资源的竞争：不可剥夺资源数量不足以满足多个进程需要，争夺陷入僵局（磁带机、打印机等）。只有对不可剥夺资源的竞争才可能死锁——可剥夺资源（CPU、内存）抢了也就是被抢走，不会等
2. 进程推进顺序非法：请求和释放资源的顺序不当。P1、P2 分别持有 R1、R2，又互相申请对方的——经典交叉
3. 信号量使用不当：进程 A 等 B 的消息，B 又等 A 的消息——不是竞争同一资源，而是在等对方，一样死锁

二、四个必要条件

产生死锁必须同时满足以下四条；任意一条不成立，死锁就不会发生。

苹果例子区分两对概念：

• 你手里拿着一个苹果，即使你不打算吃，别人也不能从你手上拿走——这是不剥夺（别人不能抢）
• 你左手拿着一个苹果，允许你右手再去拿另一个苹果——这是请求并保持（自己不放手）

循环等待 ≠ 死锁（高频辨析）

循环等待看起来和死锁定义一样，其实死锁要求的条件更严：它要求 Pi 等待的资源必须由 Pi+1 满足，循环等待没有这个限制。

反例：系统两台输出设备，P0 占一台，Pk 占一台（Pk 不在等待环里），Pn 也占一台。Pn 等一台输出设备，可以从 P0 获得，也可能从 Pk 获得。虽然 Pn、P0 等形成了循环等待，但 Pk 释放一台设备就能打破循环——没死锁。

所以：资源分配图含圈而系统不一定死锁，原因是同类资源数大于 1；若每类资源只有一个，含圈才是死锁的充分必要条件。

三、三种处理策略

四、死锁预防：逐个破坏必要条件

破坏互斥条件

把资源改成可共享就不会死锁——但有些资源天生不能共享（打印机只能互斥使用，其实用 SPOOLing 虚拟化可以实现共享），且有的场合应该保护互斥性。不太可行。

破坏不剥夺条件

进程请求新资源得不到满足时，必须释放已保持的全部资源，以后再重新申请。已占有的资源被暂时剥夺。

实现复杂，释放已获得的资源可能导致前一阶段工作失效，反复申请释放也增加开销、降低吞吐量。适用于状态易保存恢复的资源（CPU 寄存器、内存），不能用于打印机——第一行打印了文档 A、第二行打印文档 B……全乱了。

破坏请求并保持条件

预先静态分配：运行前一次性申请完所有资源，不满足就不投入运行；一旦运行，资源全归它，不再提新请求。

实现简单，缺点明显：资源被严重浪费（有的资源只在运行初期或快结束时用，甚至不用，却一直被占着）；还会饥饿（个别资源长期被占，等待它的进程迟迟不能开始）；而且有些资源是运行中才发现要用的，事先根本不知道。

破坏循环等待条件

顺序资源分配法：给所有资源编号，进程必须按编号递增的顺序请求（同类一次申请完）。申请了 Ri 以后就只能申请编号大于 Ri 的——环画不出来了。

问题：编号必须相对稳定，限制新设备的增加；作业实际使用顺序可能与规定顺序不同，造成浪费；给编程带来麻烦。

五、死锁避免：安全状态与银行家算法

不事先破坏条件，而是每次分配前算一笔账：这次分配会不会让系统进入不安全状态？会就不给，让进程等。

安全状态

系统能按某种进程推进顺序，为每个进程分配所需资源直到满足其最大需求，使每个进程都可顺序完成——这个顺序就是安全序列。找不到安全序列 = 不安全状态。

磁带机例子：三个进程 P1、P2、P3，共 12 台磁带机。P1 总共需要 10 台，P2 需要 4 台，P3 需要 9 台。T0 时刻 P1、P2、P3 已分别获得 5、2、2 台，剩 3 台空闲。

T0 是安全的，安全序列 P2 → P1 → P3：3 台全给 P2（满足最大需求 4），P2 完成归还后系统有 5 台；再给 P1 凑满 10，P1 完成归还后剩 10 台；最后给 P3 凑 9 台，全部顺利完成。

若此刻多分 1 台给 P3，系统剩 2 台——不安全了：剩下 2 台给 P2，P2 完成只能释放 4 台，既不满足 P1（还差 5）也不满足 P3（还差 7），全都推进不了，僵住。

关键结论：

• 并非所有不安全状态都是死锁状态，但不安全状态可能导致死锁
• 反过来，处于安全状态就一定不会死锁

银行家算法

最著名的死锁避免算法。思想：把 OS 当银行家，资源当资金，进程申请资源相当于贷款。规则：进程运行前先声明最大需求量；执行中再申请时，先测试"已占有 + 本次申请"是否超过声明值（超过 → 拒绝），再测试系统现存资源能否满足它尚需的最大量（能 → 分配；不能 → 推迟）。

四个数据结构（n 个进程、m 类资源）：

流程：进程请求 → 超过 Need 或超过 Available？拒绝 → 否则试探分配（Available 减、Allocation 加、Need 减）→ 跑安全性算法 → 安全则正式分配，不安全则撤回试探分配让进程等待。

安全性算法：

1. Work = Available；Finish[i] = false
2. 找一个 Finish[i]=false 且 Need[i] ≤ Work 的进程
3. 假定它执行完并释放资源：Work += Allocation[i]，Finish[i] = true
4. 重复 2-3，直到找不到这样的进程
5. 所有 Finish 都为 true → 安全

例子图：

银行家算法举例：

自己实现的 C 版（经典五进程三资源数据）：

#include <stdio.h>
#include <stdbool.h>

#define P 5  // 进程数量
#define R 3  // 资源种类数量

// 计算需求矩阵 Need = Max - Allocation
void calculateNeed(int need[P][R], int max[P][R], int allot[P][R]) {
    for (int i = 0; i < P; i++)
        for (int j = 0; j < R; j++)
            need[i][j] = max[i][j] - allot[i][j];
}

// 检查系统是否安全
bool checkSystemSafety(int processes[], int avail[], int max[][R], int allot[][R]) {
    int work[R];
    for (int i = 0; i < R; i++) work[i] = avail[i];
    bool finish[P] = {false};

    while (true) {
        bool found = false;
        for (int i = 0; i < P; i++) {
            if (!finish[i]) {
                int j;
                for (j = 0; j < R; j++)
                    if (need[i][j] > work[j]) break;
                if (j == R) {                       // Need[i] <= Work
                    for (int k = 0; k < R; k++)
                        work[k] += allot[i][k];     // 假定执行完，回收资源
                    finish[i] = true;
                    found = true;
                }
            }
        }
        if (!found) break;
    }

    for (int i = 0; i < P; i++)
        if (!finish[i]) return false;
    return true;
}

int main() {
    int avail[] = {3, 3, 2};
    int max[P][R] = {
        {7, 5, 3}, {3, 2, 2}, {9, 0, 2}, {2, 2, 2}, {4, 3, 3}
    };
    int allot[P][R] = {
        {0, 1, 0}, {2, 0, 0}, {3, 0, 2}, {2, 1, 1}, {0, 0, 2}
    };
    int need[P][R];
    calculateNeed(need, max, allot);
    if (checkSystemSafety(NULL, avail, max, allot))
        printf("The system is currently in a safe state.\n");
    else
        printf("The system is not safe.\n");
    return 0;
}

六、死锁检测和解除

前面两招都是事前限制；若系统分配资源时不采取任何措施，就得提供事后检测和解除手段。

资源分配图

圆圈 = 进程，方框 = 一类资源（框内圆点 = 该类资源中的一个实例）。

• 请求边：进程 → 资源，表示申请一个单位
• 分配边：资源 → 进程，表示已分配一个单位

图中：P1 已分得两个 R1，又请求一个 R2；P2 分得一个 R1 和一个 R2，又请求一个 R1。

死锁定理：图简化

简化资源分配图可以检测系统 S 是否处于死锁状态：

1. 找出既不阻塞又不孤立的进程 Pi——与它相连的所有请求边，申请数量都 ≤ 系统中该资源的空闲数量，则它能运行到完成，消去它的所有边（释放全部资源）
2. Pi 释放的资源可能唤醒原本阻塞的进程，继续按同样方法简化
3. 一系列简化后能消去图中所有边 → 图可完全简化，无死锁

💡 判断某资源有没有空闲：资源总数 − 该资源在图中的出度。比如 R1 资源数 3、出度 3 → 没空闲；R2 资源数 2、出度 1 → 有 1 个空闲。

死锁定理：S 为死锁状态 当且仅当 S 状态的资源分配图是不可完全简化的。

死锁解除

检测出死锁后，三种解除办法：

1. 资源剥夺法：挂起某些死锁进程，抢占它的资源分给别的死锁进程。要防止被挂起的进程长期得不到资源而饥饿
2. 撤销进程法（终止进程法）：强制撤销部分甚至全部死锁进程并剥夺资源。撤销原则：按进程优先级和撤销代价高低
3. 进程回退法：让一个（或多个）进程回退到足以回避死锁的地步，回退时自愿释放资源而非被剥夺。代价：系统必须保持进程的历史信息、设置还原点

七、盲点总复习

1. 只有不可剥夺资源的竞争才可能死锁；CPU、内存这类可剥夺资源不会
2. 信号量也能造成死锁：互相等对方的消息
3. 四条件是必要条件，缺一不可；破坏任意一个即可预防
4. 不剥夺（别人不能抢）vs 请求并保持（自己不肯放）——苹果例子
5. 循环等待 ≠ 死锁：同类资源 >1 时含圈不一定死；每类资源只有 1 个时含圈才是充要条件
6. 安全状态 ⇒ 不会死锁；死锁 ⇒ 不安全；不安全 ⇏ 死锁（只是可能）
7. 银行家算法四矩阵，核心：Need = Max − Allocation；试探分配 + 安全性检查 + 不安全就撤回
8. 图简化判断空闲资源 = 总数 − 出度
9. 死锁定理：不可完全简化 ⇔ 死锁
10. 解除三法：剥夺、撤销、回退——回退是自愿释放，撤销是被剥夺

思维导图源件

• 2.4死锁.xmind（XMind 源文件，可用 XMind 打开继续编辑）

内存是另一座大头：装不下怎么办？下一章讲内存管理 → 06-内存管理

⬅️ 🏠 00-操作系统总览 ➡️ 06-内存管理