OS-4 死锁

这一部分为什么存在？

OS-3 用信号量让进程学会了“等”，但等待引入了新风险：P1 持有资源 A 等待资源 B，P2 持有 B 等待 A——双方都在做“正确”的互斥，却谁也走不下去。并发 + 互斥 + 按需申请的组合，使一组进程可能陷入永久互相等待。

如果没有死锁的理论与对策：

• 系统会在运行中无声地“卡死”一部分进程，资源被永久占用，吞吐率下降甚至整机停摆；
• 程序员无法回答“我的 PV 设计会不会死锁”（2019 年 43 题哲学家 + 碗的设计约束正源于此）。

本模块的主线是一个三段式追问：死锁为什么发生（四条件）→ 能不能不让它发生（预防）→ 能不能边运行边躲开（避免）→ 已经发生了怎么发现和收拾（检测与解除）。

flowchart TD
    A["并发进程互斥使用资源<br/>+ 按需逐步申请"] --> B["死锁四必要条件<br/>互斥 / 请求并保持<br/>不可剥夺 / 循环等待"]
    B --> C["死锁 = 存在进程集合<br/>每个进程都在等集合内另一进程占有的资源"]
    C --> D1["预防：破坏四条件之一<br/>（静态，保守）"]
    C --> D2["避免：银行家算法<br/>每次分配前检查安全状态<br/>（动态，需预知最大需求）"]
    C --> D3["检测与解除：资源分配图化简<br/>+ 剥夺 / 撤销 / 回退<br/>（放任发生，事后处理）"]

核心概念：

1. 死锁发生的形式化判定（小计算题模板）

同类资源 $m$ 个，$n$ 个进程，每进程最多需 $k$ 个：最坏情况是每个进程都已持有 $k-1$ 个且都还差 1 个，此时只要系统还剩 $\geq 1$ 个资源就必有一个进程能完成（完成即释放，连锁解除）。故：

$m \geq n(k-1) + 1 \ \Rightarrow\ \text{不会死锁};\qquad m < n(k-1)+1\ \Rightarrow\ \text{可能死锁}$

• 2009 年 25 题：8 台打印机、每进程最多 3 台，$8 < 2K+1 \Rightarrow K \geq 4$，$K$ 最小 = 4。
• 2014 年 24 题：进程分别需 3、4、5 台，$n_{min} = (3-1)+(4-1)+(5-1)+1 = 10$。
• 2021 年 31 题：$n$ 个进程各需 2 个 → 至少 $n+1$ 个。

来源：复习资料 P3 §六。

2. 预防：静态破坏四条件

预防“确保不发生死锁”（2019 年 30 题 II 正确），但都以降低并发度或利用率为代价。

3. 避免：银行家算法

思想：不禁止任何申请，但每次分配前先假装分给他，再跑安全性检查；若结果不安全就拒绝此次分配（把进程挂起）。它“避免”而非“预防”——不破坏任何必要条件（2013 年 32 题：A、D 均错）。

安全性检查步骤（来源：复习资料 P3 §六算例，资源 A=10,B=5,C=7）：

1. 计算 $\text{Need} = \text{Max} - \text{Allocation}$；$\text{Available} = \text{总量} - \sum \text{Allocation}$；
2. 找 $\text{Need}_i \leq \text{Available}$ 的进程，假设其跑完：$\text{Available} \mathrel{+}= \text{Allocation}_i$；
3. 重复直到所有进程完成（安全，记录序列为安全序列）或无进程可推进（不安全）。

算例：Available 初始 (3,3,2) → P1 → (5,3,2) → P3 → (7,4,3) → P4 → (7,4,5) → P0 → (7,5,5) → P2，安全序列 P1→P3→P4→P0→P2。

真题变体：2011 年 27 题（无安全序列）；2012 年 27 题（安全序列 P3,P4,P2,P1,P0）；2018 年 26 题（4 资源、需求 4/3/1、已分配 2/1/0 → Available=1，仅 P3 可推进，之后 P2、P1 连锁完成，存在唯一安全序列 P3,P2,P1）；2020 年 27 题（A、B 各 6 个的资源表判安全）；2022 年 26 题（数安全序列个数 = 2）。

4. 检测与解除：放任之后的补救

• 检测：资源分配图化简——找一个既不阻塞也不孤立的进程（其全部申请当前可满足），消去它的所有边（视为跑完释放）；反复进行。边能消尽 = 无死锁；消不尽 = 死锁（2016 年 25 题即用此思想：R1、R2、R3 与 4 进程的申请关系中，出现死锁时至少 2 个进程处于死锁状态）。
• 解除：剥夺资源（从别的进程抢）、撤销进程（逐个杀到死锁消失）、进程回退。2019 年 30 题 I：剥夺资源可以解除死锁（正确）。
• 与避免的关系：避免是“事前每个分配都审查”，检测是“事后定期体检”——2015 年 26 题：采用避免的 S1 不会给可能导致死锁的进程分配资源，采用检测的 S2 会（分配后才查）。

演化逻辑：预防最稳但最浪费 → 避免用“预知最大需求”换利用率 → 现实中最大需求难预知，于是检测+解除用“允许死锁偶尔发生”换最高利用率。408 只考三种策略的思想、判别和银行家/化简两个算法。

死锁 vs 饥饿（易混对，深入版）：为什么易混——都表现为“进程长期得不到执行”。本质区别——死锁的等待构成闭环（等的东西在同组人手里），饥饿是开环（等资源在系统手里，只是总轮不到我）；死锁必涉 ≥2 进程且涉及互斥资源，饥饿 1 个进程即可发生（如低优先级进程在纯优先级调度下）。判别线索：题目出现“低优先级总被抢占/短任务不断到达”→ 饥饿（2011 年 23 题、2014 年 23 题考调度算法的饥饿）；出现“各持一部分资源互相申请”→ 死锁。

形态一：死锁判定小计算（“最少多少资源不会死锁 / 最少几进程可能死锁”）：2009-25、2014-24、2021-31，套 $n(k-1)+1$ 公式或资源分配图推理（2016-25：死锁进程数至少 2 个）。

形态二：银行家算法 / 安全性检查：2011-27、2012-27、2018-26、2020-27、2022-26。得分点是 Need 矩阵与 Available 的逐步更新过程；变体是数安全序列个数（2022-26）。

形态三：概念辨析：2013-32（银行家是避免不是预防、安全⇒无死锁、不安全≠死锁）、2015-26（避免 vs 检测的分配策略差异）、2019-30（死锁解除手段、预防确保不发生、死锁必然 ≥2 进程阻塞）。

形态四：与 PV 大题结合：2019-43（哲学家 + 碗：“防止死锁”是硬性约束，标准解法是限制同时取筷人数或一次性申请全部资源——正对应破坏“循环等待”与“请求并保持”）。

做题触发词：看到“最多需要 k 个/至少几台”→ $n(k-1)+1$；看到“Max/Allocation/Available 表格”→ 银行家安全性检查；看到“是否处于死锁状态”→ 注意银行家只能判安全不能判死锁（2019-30 III 为错误项）；看到“互斥资源 + 环路”→ 资源分配图化简。

来源：真题markdown/2009-2024统考真题.md 对应题号；复习资料 P3 §六。

• 向前依赖：OS-1 进程状态（阻塞是死锁的存在形式）；OS-3 同步互斥（互斥与保持等待正是 P/V 使用方式引入的；哲学家问题是两者的交汇）。
• 向后引出：
  • 死锁预防中的 Spooling 思想 → OS-8 I/O 管理；
  • 资源抽象（设备、内存、文件都可死锁）→ 各资源管理章节；
  • 调度算法中的饥饿 → OS-2（2016 年 45 题大题要求设计避免饥饿的动态优先级，把 nice/cpuTime/waitTime 综合——死锁与饥饿问题在调度处的合流）。

1. 为什么解决了互斥还会出新问题？（等待可能成环）
2. 死锁的四个必要条件是什么？为什么缺一不可？
3. 如何用公式快速判断“最少多少资源不死锁”？（$n(k-1)+1$）
4. 预防死锁的四种破坏手段各牺牲什么？
5. 银行家算法为什么不属于预防？它每次分配前做什么？（试分配 + 安全性检查）
6. 安全状态的定义？安全、不安全、死锁三者什么关系？（安全⇒无死锁；不安全≠死锁）
7. 安全性检查怎么一步步做？Need 和 Available 怎么更新？
8. 已经死锁了怎么发现？（资源分配图化简：消得尽吗）
9. 发现后怎么解除？（剥夺/撤销/回退）
10. 死锁和饥饿怎么区分？（闭环互等 vs 开环被冷落）
11. 哲学家问题的标准解法分别破坏了哪个必要条件？（接 OS-3）