Appearance
死锁检测与解除
2026 大纲 二（四）4 死锁检测和解除。
干脆不管，等出事了再说
预防太保守（从条件上堵死），避免要每次试算（还得预先知道每个进程的资源总需求）。 如果死锁本来就很少发生呢？ 那为它付的这些代价就都不划算。
于是有了第三条路：平时什么都不管，让进程随便申请， 定期检查一下系统是不是已经死锁了；死了再处理。
检查靠资源分配图。它有两类结点（进程用圆圈、资源类用方框、方框里的点是实例） 和两类边，而这两类边的画法不同，是有理由的：
⚠️请求边指向方框本身，分配边却始于方框中的一个点。 进程提出请求时说的是"我要这类资源里的一个，哪个实例都行"，所以边只能落到方框； 而资源一旦分配出去，占的就是具体某一个实例，所以边必须从那个点出发。
多实例资源之所以不能只看有没有环、必须靠化简，根子也在这里—— 环上那类资源可能还有别的实例是空闲的。
化简的实质是模拟"如果不再有新请求，系统靠现有空闲资源能不能自己把所有进程推完"： 找得出一个能跑完的进程，就让它归还全部资源去撬动下一个。
死锁定理把这件事划上了等号：图不可完全简化
⚠️ 它与银行家算法的唯一分界是：这里用 Request（这次实际要什么）， 银行家用 Need（总共还差什么）——因为检测不预先知道总需求。
交互可视化
一、资源分配图
画法约定是：进程用圆圈、资源类用方框、方框里的点表示该类资源的各个实例。这里只说清一处容易画错的地方：请求边指向方框本身，分配边却始于方框中的一个点。这不是随手定的——进程提出请求时说的是"我要一类资源里的一个，哪个实例都行"，所以边只能落到方框；而资源一旦分配出去，占的就是具体某一个实例，所以边必须从那个点出发。多实例资源之所以要靠化简而不能只看有没有环，根子也在这里：环上那类资源可能还有别的点是空闲的。
图中 P1 持有 R1 请求 R2、P2 持有 R2 请求 R1 → 环路，且环上每种资源仅 1 个实例 → 死锁。
二、化简与死锁定理
化简的实质是模拟"如果不再有新请求，系统靠现有空闲资源能不能自己把所有进程推完"——找得出一个能跑完的进程，就让它归还全部资源去撬动下一个。死锁定理——图不可完全简化
两个化简示例：能消干净与消不干净只差一条请求边（想看清"选谁、为什么能选它、消完剩多少"的逐步过程时展开）
示例一：能消干净。 R1 总量 2、R2 总量 1；P1 持有 R1×1 请求 R2×1，P2 持有 R2×1 请求 R1×1，P3 持有 R1×1、无请求。
| 步骤 | 当前空闲 | 选谁 | 为什么能选它 | 消去后空闲 |
|---|---|---|---|---|
| 1 | R1=0, R2=0 | P3 | 它没有请求边，非阻塞 | R1=1, R2=0 |
| 2 | R1=1, R2=0 | P2 | 它请求 R1×1，恰好有 1 个空闲 | R1=2, R2=1 |
| 3 | R1=2, R2=1 | P1 | 它请求 R2×1，有 1 个空闲 | 全部边消去 |
结论：图可完全简化 → 不存在死锁。
示例二：消不干净。 只把 P3 改成也请求 R2×1，其余不变：
| 进程 | 请求 | 当前空闲 R1=0, R2=0 | 能否推进 |
|---|---|---|---|
| P1 | R2 ×1 | R2 空闲 0 | ✗ 阻塞 |
| P2 | R1 ×1 | R1 已全部分给 P1、P3 | ✗ 阻塞 |
| P3 | R2 ×1 | R2 空闲 0 | ✗ 阻塞 |
一个都选不出来 → 图不可完全简化 → 按死锁定理，存在死锁，死锁进程集 = {P1, P2, P3}。
对比两例可以看清化简的实质：P3 从"不请求"变成"请求 R2"，就把最后一个能启动的进程也堵死了。
三、死锁检测算法（矩阵法）
图适合人看，程序跑的是矩阵。数据结构与银行家算法类似，只有第三行不同：
| 结构 | 含义 |
|---|---|
| Available（1×m） | 每一类资源的可用数目 |
| Allocation（n×m） | 每个进程已占有的各类资源数 |
| Request（n×m） | 每个进程当前实际提出的请求（不是 Need） |
| L 表 | 已被证明"能跑完"的进程集合，对应图上被化简成孤立结点的进程 |
1. Work = Available
L = { P_i | Allocation_i = 0 且 Request_i = 0 } // 本来就孤立的结点先记入
2. 从进程集合中找一个满足下述两条的进程 P_i：
P_i ∉ L 且 Request_i <= Work
找到就：
Work = Work + Allocation_i // 化简该结点，释放出它占的资源
把 P_i 记入 L
回到步骤 2
3. 若最终不能把所有进程都记入 L，
便表明系统状态 S 的资源分配图是不可完全简化的 → 系统发生死锁；
未进入 L 的那些进程构成死锁进程集。这段代码的每一步都对应图上的一个动作——把它们逐项对上，两种方法就合成了一种：
| 矩阵法这边 | 图化简那边 |
|---|---|
Request_i ≤ Work | |
Work = Work + Allocation_i | 消去 |
| 把 | |
| 最终不能把所有进程记入 L | 图不可完全简化 |
所以矩阵法和图化简不是两个算法，是同一件事的两种记法：图适合人一眼看出环在哪，矩阵适合程序跑、也更不容易在多实例资源上判漏。理解了这张对应表，图化简那边的"先选谁不影响结论"直接可以搬过来用——因为 Work 只增不减，某个进程此刻过得了 Request ≤ Work，以后也一定过得了。
矩阵法走一遍：从 Allocation 反推 Available，到判出死锁进程集（想看清每轮 Work 怎么变、什么时候能立即停手时展开）
系统有 A、B、C 三类资源，总量 (7, 4, 6)，4 个进程当前状态：
| 进程 | Allocation (A,B,C) | Request (A,B,C) |
|---|---|---|
| P0 | 1, 1, 0 | 0, 0, 1 |
| P1 | 2, 0, 2 | 2, 0, 0 |
| P2 | 3, 0, 3 | 2, 0, 1 |
| P3 | 1, 2, 0 | 2, 0, 0 |
第 1 步：算 Available。 题面常只给 Allocation、Request 和总量，Work 的初值要自己算。
第 2 步：初始化 L。 本例中没有进程同时满足 Allocation = 0 且 Request = 0，所以 L = ∅，Work = (0, 1, 1)。
第 3 步：迭代。
| 轮次 | Work | 逐个试 Request ≤ Work | 选中 | Work += Allocation |
|---|---|---|---|---|
| 1 | 0, 1, 1 | P0 (0,0,1) ≤ (0,1,1) ✓ | P0 | (0,1,1)+(1,1,0) = 1, 2, 1 |
| 2 | 1, 2, 1 | P1 (2,0,0)：A 2 > 1 ✗ P2 (2,0,1)：A 2 > 1 ✗ P3 (2,0,0)：A 2 > 1 ✗ | 无 | — |
只要某一轮里所有未入 L 的进程都过不了 Request ≤ Work，迭代就再也不可能推进（Work 不会自己变大），可以立即停下判定。
第 4 步：判定。 L = {P0}，P1、P2、P3 未能记入 L → 资源分配图不可完全简化 → 按死锁定理，系统发生死锁，死锁进程集 = {P1, P2, P3}。
第 5 步：看清根因。 三个未完成进程的 Request 在 A 类上都是 2，而 P0 跑完后 A 类只攒到 1——A 类资源被 P1、P2、P3 三家瓜分完了，谁也凑不齐启动所需的量。
第 6 步：反过来看一遍——把 P1 的 Request 从 (2,0,0) 改成 (1,0,0)，其余不变。
| 轮次 | Work | 选中 | 理由 | Work += Allocation |
|---|---|---|---|---|
| 1 | 0, 1, 1 | P0 | (0,0,1) ≤ (0,1,1) | 1, 2, 1 |
| 2 | 1, 2, 1 | P1 | (1,0,0) ≤ (1,2,1) | 3, 2, 3 |
| 3 | 3, 2, 3 | P2 | (2,0,1) ≤ (3,2,3) | 6, 2, 6 |
| 4 | 6, 2, 6 | P3 | (2,0,0) ≤ (6,2,6) | 7, 4, 6 |
四个进程全部记入 L → 可完全简化 → 无死锁。自检：末态 Work = (7,4,6) = 资源总量 ✓。
把这一正一反两轮并排看，就能读出检测算法真正的判据：死不死锁不取决于谁占得多（两例的 Allocation 完全相同），而取决于有没有一个进程的当前请求能被现有空闲资源满足——只要能撬动一个，它归还的资源就可能撬动下一个，连锁推完；一个都撬不动，Work 就再也不会变大。
四、与银行家算法的分界
| 对比 | 银行家算法（避免） | 死锁检测算法 |
|---|---|---|
| 用哪个需求量比较 | Need（Max − Allocation） | Request（当前实际提出的请求） |
| 时机 | 分配前检查 | 分配后周期性检查 |
| 乐观程度 | 保守（按最坏情况，考虑最大需求） | 乐观（只看眼下这一笔） |
| 判定的问题 | 分配后是否仍能保证所有进程跑完 | 系统当前是否已经死锁 |
| 结论的后果 | 不安全 → 拒绝请求 | 死锁 → 进入解除流程 |
| 会不会误伤 | 会——拒掉一些其实不会死锁的请求 | 不会，但要等到死锁真的发生 |
两者的迭代形态完全相同（找一个需求能被满足的进程 → 让它跑完并归还资源 → 看能不能把所有进程推完），唯一的分界就是第一行。记住这一行，两个算法就都会写了。
五、死锁的解除
最简单的处理是通知操作员以人工方法处理；自动处理常用两种方法：
| 方式 | 做法 | 代价 |
|---|---|---|
| 终止所有死锁进程 | 把死锁进程集里的进程全部终止 | 最简单，但代价可能很大——有些进程可能已接近结束，一旦被终止便"功亏一篑" |
| 逐个终止进程 | 按某种顺序逐个终止，直至打破循环环路 | 🔴 每终止一个进程，都需要用死锁检测算法确定死锁是否已解除，未解除还需再终止 |
| 抢占资源 | 夺走资源但保留进程 | 要处理三件事：抢谁（按代价最小挑）、被抢者回滚（退回一个此前保存过的一致状态）、防饥饿（不能总挑同一个下手） |
选谁下手的四条依据：优先级、已执行与还需时间、已用与还需资源、交互式还是批处理式。一句话：优先终止"已投入少、还需资源多、优先级低、非交互"的进程。
回滚回到哪里，取决于有没有检查点（Check Point）：没有就只能完全回滚（杀掉从头重来，代价与终止进程相同）；有就只需退回最近一个检查点——进程运行期间每隔一定时间把当前状态（已修改的数据、执行位置）写到稳定存储器并留下一个〈检查点〉记录。检查点越密，一次回滚重做的工作越少，但平时保存快照的累计开销越大，两者要权衡——与自旋锁与互斥锁的选型同类。
六、检测的时机
| 策略 | 说明 | 判据 |
|---|---|---|
| 每次资源请求时检测 | 实时性最好，死锁一出现就发现 | 检测算法约 |
| 定时检测 | 每隔固定时间跑一次 | 折中；周期越长，死锁存在的时间越长，被卷入的进程越多 |
| 资源利用率下降时检测 | 处理机利用率掉到某个阈值以下才查 | 按需检测，开销最小 |
第三种的成因：死锁进程全部阻塞、不占用处理机，所以外部征兆是"处理机利用率异常下降而就绪队列并不长"。🔴 它只是征兆不是判据——利用率下降也可能是 I/O 密集型负载所致，定论仍要跑检测算法。
考点速记
- 资源分配图的两类边画法不同，是有理由的：⚠️请求边指向方框本身（"这类资源里哪个实例都行"），分配边始于方框中的一个点（占的是具体某个实例）。
- ⚠️多实例资源不能只看有没有环，必须靠化简——环上那类资源可能还有别的实例空闲。只有每类资源都只有一个实例时，"有环"才等价于"死锁"。
- 化简的实质：模拟"如果不再有新请求，系统靠现有空闲资源能不能自己把所有进程推完"——找得出能跑完的进程，就让它归还全部资源去撬动下一个。
- 死锁定理：图不可完全简化
系统死锁，图上剩下的即死锁进程集。 - ⚠️矩阵法与图化简是同一件事：
Request ≤ Work不阻塞、 Work += Allocation消边释放。 - ⚠️与银行家算法的唯一分界是用
Request还是Need：检测用Request（这次实际要什么），避免用Need（总共还差什么）。因为检测不预先知道资源总需求——这也正是 2015-26 的考点。 - 解除靠两条：抢占资源与终止进程。⚠️逐个终止时每终止一个都要重跑一次检测（可能已经解开了）。抢占要解决三件事：抢谁、回滚到哪（有无检查点决定）、怎么防饥饿。
这一节在真题里被考过的形式：
死锁检测本身没有单独的计算题（deadlock 那 13 道计算题全是银行家算法）， 本页下方练习区渲染的是整个 deadlock 标签下的题，范围比本节宽，属正常。 它落在一道对照题上：
- 比较死锁避免（S1）与死锁检测（S2）（2015-26，与死锁的概念与预防共享）。⚠️ 关键差别是速记第六条——S1 需要进程运行所需的资源总量信息（
Need），S2 不需要。而"S1 会限制用户申请资源的顺序"是错的——限制顺序的是预防（资源有序分配法），避免并不限制顺序，它只在每次分配前做安全性检查。 - 另有一处会作为判断素材：死锁可以通过剥夺（抢占）进程资源来解除（2019-30，速记第七条）。
复习优先级：读懂即可，重点是第六条那个分界。 "检测用 Request、避免用 Need" 这一句是唯一被直接考过的点。第二条（多实例必须化简、单实例才能只看环） 在做资源分配图题时用得上；第五条（矩阵法与图化简等价）说明你只需要会一种做法。
易错：认为有环就一定死锁。只有每类资源都只有一个实例时才等价；多实例必须化简。
易错：把请求边也画成从方框里的点出发。请求边指向方框本身——请求的是"这类里的任意一个"。
易错：把检测算法用
Need去比。检测用Request，Need是银行家（避免）才用的。
易错：认为死锁避免会限制资源申请顺序。限制顺序的是预防；避免只做安全性检查。
易错：逐个终止进程解除死锁时一口气全终止。每终止一个都要重跑检测——可能已经解开了。
教材出处
- 检测与解除的定位、资源分配图的形式定义：汤小丹《计算机操作系统》3.8、3.8.1 节，印刷 p115——"如果在系统中，既不采取死锁预防措施，也未配有死锁避免算法，系统很可能会发生死锁"；
的定义、请求边 与分配边 ；"我们用圆圈代表一个进程，用方框代表一类资源……用方框中的一个点代表一类资源中的一个资源"。 - 化简规则与死锁定理：同书印刷 p116——"找出一个既不阻塞又非独立的进程结点
……这相当于消去 的请求边和分配边，使之成为孤立的结点"；"若能消去图中所有的边……则称该图是可完全简化的"；"所有的简化顺序都将得到相同的不可简化图"；"S 为死锁状态的充分条件是：当且仅当 S 状态的资源分配图是不可完全简化的。该充分条件被称为死锁定理"。 - 检测算法的数据结构与步骤：同书印刷 p116——Available；"把不占用资源的进程（向量 Allocation=0）记入 L 表"；"从进程集合中找到一个
的进程……① 将其资源分配图简化，释放出资源，增加工作向量 ；② 将它记入 L 表中"；"若不能把所有进程都记入 L 表中，便表明系统状态 S 的资源分配图是不可完全简化的"。 - 死锁解除的两种方法与终止进程的四条依据：同书 3.8.2 节，印刷 p117——"常采用解除死锁的两种方法是：(1) 抢占资源……(2) 终止(或撤消)进程"；终止所有死锁进程"一旦被终止真可谓'功亏一篑'"；逐个终止"每终止一个进程，都需要用死锁检测算法确定系统死锁是否已经被解除"；四条选择依据（优先级、已执行与还需时间、已使用与还需资源、交互式还是批处理式）。
- 检查点机制：同书 8.5.2 节，印刷 p273——检查点的作用与"每隔一定时间"把当前记录表与所有已修改数据输出到稳定存储器、再写入〈检查点〉记录的做法。该节讲的是文件系统的事务恢复，死锁解除中的回滚沿用同一机制。
本节两个化简示例与矩阵法算例的数据均为自行构造。