死锁四条件与资源分配图
基于通用操作系统概念 · 核于 2026-08
速查
- 四必要条件（Coffman）：互斥、占有并等待、不剥夺、循环等待——全部满足才死锁，破坏任一即预防。
- 互斥：资源排他，同一时刻只能一个进程用（打印机、写锁）。可共享资源（只读文件）不引发互斥等待。
- 占有并等待：进程占有资源的同时申请新资源——持有不放又伸手要。破坏法：一次性申请全部资源。
- 不剥夺：资源不可强行夺走，只能持有者主动释放。破坏法：申请不到就释放已占资源（或允许抢占）。
- 循环等待：存在
{P0→P1→...→Pn→P0}的等待环。破坏法：资源有序分配（给资源编号，按升序申请，最实用的预防法）。 - 资源分配图（RAG）：进程→资源（请求边）、资源→进程（分配边）的有向图。
- 判环规则：每类资源只有 1 个实例时，图中有环 ⇔ 死锁；资源有多实例时，有环不一定死锁，需用图化简算法（逐步删除能完成的进程）判定。
- 图化简：找当前请求能满足的进程 → 删掉它（归还它占的资源）→ 重复，直到删不动。若所有进程都被删掉则无死锁；若还有进程删不掉则这些进程死锁。
- 预防对应：破坏互斥（共享资源，难）、破坏占有等待（一次性分配）、破坏不剥夺（可抢占）、破坏循环等待（有序分配）。
一、四条件详解
死锁发生的充要条件是 Coffman 四条件同时成立。下面逐条剖析"它是什么、为什么导致死锁、如何破坏"。
| 条件 | 含义 | 直觉 | 破坏方法（=预防策略） |
|---|---|---|---|
| ① 互斥 | 资源排他，同时只能给一个进程 | 打印机不能两人同时打印 | 改用可共享资源（如只读文件/无锁数据结构），但很多资源天然互斥，难破坏 |
| ② 占有并等待 | 拿着资源不放，同时申请新资源 | 占着茅坑不拉屎，还要去占下一个 | 一次性申请全部所需资源（用前全申请，拿不全就不持有任何资源） |
| ③ 不剥夺 | 资源不能被强抢，只能主动释放 | 不能从别人手里硬抢 | 申请不到新资源就主动释放已占资源；或允许系统抢占（如 CPU 调度） |
| ④ 循环等待 | 存在进程间的环形等待链 | A 等 B、B 等 C、C 等 A | 资源有序分配：给资源编号，进程只能按升序申请，打破环 |
- 互斥与不剥夺是资源的固有属性（打印机天然互斥、锁天然不可抢），改起来伤功能；占有等待与循环等待可通过协议人为破坏——这就是为什么预防策略主要从这两条下手。
- 破坏循环等待最实用：给每类资源一个全局编号，进程申请资源必须按编号递增顺序（如先申请编号小的 R1，再申请编号大的 R2）。这样不可能形成"升序请求的环"，循环等待被杜绝。代价是：可能要先申请暂时用不上的资源、编号顺序未必符合使用顺序（资源浪费）。
二、资源分配图（RAG）：用图论识别死锁
资源分配图（Resource Allocation Graph，RAG）把"进程—资源—请求/分配关系"画成有向图，用图的结构判断是否死锁：
请求边（进程想要资源）
┌──────────┐
▼ │
●─────▶ ◎ ◀─────● ● = 进程（P）
P1 R1 P2 ◎ = 资源（R），◎内的点 = 资源实例
▲ │ (每个点代表 1 个可用实例)
└──────────┘
分配边（资源已分给进程）- 节点：进程（圆圈
●）与资源类（方框内圆圈◎）。资源框内有几个小点，代表该资源有几个实例。 - 请求边
P→R：进程 P 申请资源 R，但还没分到。 - 分配边
R→P：资源 R 的一个实例已分给进程 P。 - 死锁判定：
- 资源每类只有 1 个实例：图中有环 ⇔ 死锁（环上的进程都死锁）。
- 资源有多实例：有环不一定死锁——因为多实例可能让环上某个进程的请求满足，环就消了。此时必须化简图判定。
三、图化简算法：多实例时的死锁判定
当资源有多实例时，"有环"不再等价于死锁，需要用图化简（graph reduction）：
1. 找一个"请求能被当前可用资源满足"的进程 P
2. 假设 P 顺利运行完毕，释放它占有的全部资源（归还到可用池）
3. 删掉 P 节点及其相连的所有边
4. 回到步骤 1，直到没有这样的进程可删
5. 若所有进程都被删掉 → 无死锁
若还有进程删不掉 → 这些删不掉的进程死锁- 直观理解：能"跑完"的进程会归还资源，归还后别的进程可能就能跑了——只要能一路删到底，系统是安全的；删不动了，剩下的进程彼此等待、谁也等不到，就是死锁。
- 与银行家算法同源：图化简本质就是找一个安全序列（能依次完成的进程顺序）。能化简到底 = 存在安全序列 = 安全状态；化简不动 = 不安全状态（可能死锁）。
四、预防：破坏哪个条件
| 破坏条件 | 方法 | 优点 | 缺点 |
|---|---|---|---|
| 互斥 | 改用共享/无锁资源 | 从根本上消除等待 | 很多资源天然互斥（打印机/写锁），不可行 |
| 占有并等待 | 一次性申请全部资源 | 简单，绝不死锁 | 资源利用率低（提前占用暂不用的）、可能饿死（一次性要太多拿不到） |
| 不剥夺 | 申请不到就释放已占资源 | 灵活 | 实现复杂、释放已做了一半的工作会回滚代价大、可能反复申请释放（活锁） |
| 循环等待 | 资源有序分配（按编号升序申请） | 有效且较实用 | 编号难设计、可能被迫提前申请暂不用的资源、与使用顺序不符 |
结论：预防策略以牺牲资源利用率与并发度换取"绝对不死锁"，只适用于资源种类少、需求可预知的场景（如嵌入式/实时系统）。通用 OS 因代价过大而极少采用。
下一步
四条件与资源分配图是死锁的"诊断工具"，下一步进入死锁的四种处理策略——死锁处理：预防、避免、检测（预防的工程代价、银行家算法如何避免、检测恢复、主流 OS 为何选鸵鸟）。