正着问：最少要多少资源
3 个进程，每个最多要 4 台打印机。
3 × (4 − 1) + 1 = 10 台。9 台时可能每人 3 台全卡住。
几个进程各自攥着一部分资源，又都在等别人手里的那一份，谁也不肯先放，于是一起卡死。这一章讲两件事：死锁是怎么凑出来的（四个必要条件），以及操作系统在“限制得多严”和“出事后赔多少”之间怎么取舍（预防、避免、检测解除、不管）。
定义：多个进程因竞争资源而造成的一种互相等待，若无外力作用，这些进程都将无法向前推进。三个关键词：多个、互相等待、无外力就推进不了。
| 死锁 | 饥饿 | 死循环 | |
|---|---|---|---|
| 是什么 | 多个进程互相等对方手里的资源 | 某进程长时间得不到想要的资源（如短进程优先下的长进程），一直无法推进 | 进程执行时一直跳不出某个循环 |
| 是否必然多个进程 | 是 至少 2 个，才能“互相”等 | 否 可能只有 1 个进程饥饿 | 否 1 个进程就能死循环 |
| 是否可能处于就绪态 | 否 死锁进程一定都在阻塞态 | 可能 等 CPU 时在就绪态，等 I/O 设备时在阻塞态 | 可能 它能上 CPU 运行，时间片用完回到就绪态 |
| 是否是管理者的问题 | 是 OS 资源分配策略不当 | 是 OS 资源分配策略不公平 | 否 被管理者（程序员）写的代码逻辑错误 |
| OS 能否自己发现 | 能（死锁检测） | 较难，要看等待时间 | 不能，是程序自身的 bug |
系统里不可剥夺资源（磁带机、打印机）数量不够多个进程同时用，大家各拿一部分，都在等剩下的。
对可剥夺资源（CPU、主存）的竞争不会引起死锁：OS 随时能把它收回来给别人。
请求和释放资源的顺序不当。下面两个进程单独跑都没问题，交替执行到各自的第二行就卡死：
// P1 P(R1); P(R2); // 等 P2 放 R2 ... V(R2); V(R1);
// P2 P(R2); P(R1); // 等 P1 放 R1 ... V(R1); V(R2);
信号量使用不当也属于这一类，比如生产者–消费者里两个 P 操作颠倒顺序。
记法：前三条是“资源和进程的性质”，第四条是“这些性质凑到一起形成的局面”。前三条成立只是具备了死锁的可能，循环等待出现才可能真正卡住。
资源一段时间内只能被一个进程占用。能同时共享的资源（如只读文件）不会让人等。
进程拿到的资源在用完之前不能被别人强行夺走，只能由自己主动释放。
进程已经占着至少一个资源，又去申请新资源；新资源被别人占着，它阻塞，但手里的也不放。
存在一条“进程–资源”的循环等待链：链中每个进程占着的资源，正被下一个进程请求。
同类资源数大于 1 时，有循环等待不一定死锁；每类资源都只有 1 个时，循环等待（资源分配图有环）就是死锁的充分必要条件。
预防是静态的：在系统设计阶段就定好规矩，运行时不用判断。规矩越死，死锁越不可能，资源也越浪费。
| 破坏哪个条件 | 方法 | 为什么有效 | 缺点 |
|---|---|---|---|
| 互斥 | 把独占资源改造成可共享，如 SPOOLing 技术把独占的打印机在逻辑上变成共享设备 | 进程把数据交给输出井就返回，不用等打印机 | 不普适 很多资源没法改造，而且很多场合必须保护互斥 |
| 不剥夺 | ① 占着资源的进程申请新资源失败时，释放手里所有资源，以后再重新申请；② 所需资源被别人占着时，由 OS 按优先级强行剥夺 | 资源可以被收回，等待链就断了 | 代价大 实现复杂；前一阶段的工作可能作废，只适合 CPU 这类易保存恢复状态的资源；反复申请释放增加开销；方案 ① 可能导致饥饿 |
| 请求并保持 | 静态分配：进程运行前一次申请完它需要的全部资源，没凑齐就不投入运行；运行中不再申请 | 运行中不再申请，就不会“占着又等” | 浪费 + 饥饿 有的资源只在开头或结尾用一下，却被占满全程；个别资源长期被占，等它的进程迟迟开始不了 |
| 循环等待 | 顺序资源分配法：给资源编号，进程必须按编号递增的顺序申请，同类资源一次申请完 | 占着大号资源的进程不可能回头申请小号资源，等待链只能单向延伸，成不了环 | 不灵活 编号要相对稳定，不便增加新设备；实际使用顺序和编号顺序不一致时，要提前占着大号资源，造成浪费；编程麻烦 |
避免不拆任何条件，而是在每次分配前动态判断。它依赖一个概念：安全状态。
安全序列：按这个顺序 ⟨P1, P2, …, Pn⟩ 给进程分资源，每个进程都能拿到它的最大需求、顺利跑完并归还资源。
安全状态：至少存在一个安全序列。安全序列可以不止一个。
不安全状态：一个安全序列都找不到。
银行家算法的思路：不安全虽然不一定死锁，但不冒这个险，只允许系统停在安全状态。
// 进程 Pi 发出请求向量 Request // 向量比较 a ≤ b：每个分量都 ≤ if (Request > Need[i]) error(); // ① 超过它声明的最大需求：出错 if (Request > Available) wait(); // ② 资源不够：Pi 阻塞等待 // ③ 试探分配 Available -= Request; Allocation[i] += Request; Need[i] -= Request; // ④ 安全性检查 if (!Safe()) { 撤销③的三行; // 恢复原状态 wait(); // Pi 等待 } // 安全：正式分配
bool Safe() { int Work[m] = Available; bool Finish[n] = {false}; while (存在 i: !Finish[i] && Need[i] <= Work) { Work += Allocation[i]; // Pi 跑完，归还资源 Finish[i] = true; } return 所有 Finish[i] 都为 true; } // 为什么是 Work += Allocation 而不是 += Max？ // Pi 先拿 Need 再全部归还： // Work − Need + Max = Work + Allocation
表格可以直接改数字，Need 自动算。“安全性检查”一步步展示 Work 的变化；“资源请求”按 ①②③④ 判断能不能分。本页约定：每一轮从 P0 往后扫，选编号最小的、满足 Need ≤ Work 的进程。考试里写出任意一个合法的安全序列都算对。
检测不需要知道最大需求，只看“现在谁占着什么、谁在等什么”。工具是资源分配图。
死锁定理：状态 S 为死锁 ⇔ S 的资源分配图不可完全简化。消不掉的边所连的进程就是死锁进程。
约定：每步从 P1 往后找，消去编号最小的可消去进程。化简结果与消去顺序无关。
检测算法和银行家的安全性算法长得几乎一样，区别在于：检测用的是进程当前的请求（Request），不是最大需求剩下的 Need；并且没占任何资源的进程直接记为 Finish = true。
挂起某些死锁进程，抢占它们的资源分给其他死锁进程。
要防止被挂起的进程长时间拿不回资源而饥饿。
强制撤销部分甚至全部死锁进程，收回它们的资源。可按优先级和撤销代价挑选。
实现简单，但代价可能很大：快跑完的进程一撤销就前功尽弃。
让一个或多个进程回退到足以回避死锁的地步，回退时自愿释放资源，而不是被剥夺。
要求系统保存进程的历史信息，设置还原点。
选谁开刀，一般看：优先级、已执行多久、还要多久完成、已占多少资源、交互式还是批处理。
n 个进程，每个最多需要 k 个同类资源。最坏的情况：资源被平均分掉，每个进程都拿到 k − 1 个，都还差 1 个，谁也跑不完，这时用掉了 n(k − 1) 个。
只要再多 1 个，就一定能让某个进程凑满 k 个跑完，它释放 k 个，其他进程接着都能完成。
各进程需求不同时同理：最少资源数 = Σ(ki − 1) + 1。
3 个进程，每个最多要 4 台打印机。
3 × (4 − 1) + 1 = 10 台。9 台时可能每人 3 台全卡住。
有 m 个资源，每个进程最多要 k 个。解不等式 n(k − 1) + 1 ≤ m，得 n ≤ (m − 1) ÷ (k − 1)，向下取整。
例：m = 8，k = 3 → n ≤ 3.5 → 最多 3 个进程（4 个时 4 × 2 + 1 = 9 > 8）。
m 个资源、n 个进程，求 k 的最大值：k ≤ (m − 1) ÷ n + 1，向下取整。
例：m = 10，n = 3 → k ≤ 4 → k 最大为 4（k = 5 时要 13 个）。
直接比较 m 和 n(k − 1) + 1：m ≥ 它就不可能死锁；m 更小就可能死锁（不是一定）。
| 策略 | 时机 | 分配资源的态度 | 主要手段 | 优点 | 缺点 |
|---|---|---|---|---|---|
| 预防 | 事前 · 静态 | 保守，宁可资源闲置 | 一次申请全部、剥夺、按编号顺序分配 | 不会死锁；适合做突发式处理的进程；静态分配时不必剥夺 | 效率低，进程初始化时间长；剥夺次数多；不便灵活申请新资源 |
| 避免 | 事前 · 动态 | 折中，运行时判断是否可能死锁 | 银行家算法，找安全序列 | 不必剥夺；比预防限制少，资源利用率更高 | 必须事先知道最大需求；进程不能被长时间阻塞；每次分配都要计算 |
| 检测与解除 | 事后 | 宽松，只要资源够就分 | 化简资源分配图；剥夺、撤销、回退 | 不延长进程初始化时间，允许对死锁现场处理 | 检测有开销；解除要剥夺或撤销，造成损失 |
| 鸵鸟策略 | 不处理 | 完全不管 | 忽略死锁 | 零开销 | 死锁发生只能人工处理（重启） |