死锁
0. 引言：死锁的本质
死锁（Deadlock）的本质并不是"几个进程卡住不动"，而是：
系统进入了一个不可逃逸的状态空间（Irreversible State），其内部所有进程的推进都依赖于彼此引发的事件，而这些事件永远不会发生。
从统一抽象模型看： 死锁 = 等待关系图（Wait-For Graph）中出现不可消除的环路。
理解死锁要从 系统状态空间 与 资源分配图 入手，再将所有策略归纳为一套 死锁治理体系。
1. 死锁的抽象模型（核心框架）
1.1 资源分配图（RAG：Resource Allocation Graph）
系统由两类节点构成：
- 进程 P
- 资源 R
边表示关系：
R → P：资源被某进程持有P → R：进程正在请求资源
若改写为等待图（WFG），则为：
P1 → P2: P1 等待 P2 所持资源
所有死锁判定和策略都可从此图推导。
1.2 死锁的四个必要条件（从模型导出）
死锁产生要求 全部成立：
| 条件 | 本质含义 | 对应模型表现 |
|---|---|---|
| 互斥 | 资源不可共享 | R 节点只有一个出边 |
| 占有并等待 | 持有部分资源继续请求 | P 节点同时连接 Rout 和 Rin |
| 不可抢占 | 资源不能强制收回 | 图结构不可修改 |
| 环路等待 | 存在闭环 | WFG 出现环路 |
四条件不是规则，而是图结构的特征 只要等待图中出现"闭环"，其成因必然表现为这四条。
2. 死锁的类型（从系统视角分类）
2.1 静态顺序死锁
资源顺序固定但多个线程以不同顺序请求 → 环路出现。
2.2 动态顺序死锁
资源的请求动态变化，无法保证统一顺序。
2.3 资源死锁（经典 OS 死锁）
争夺有限、不可抢占资源（锁、文件、IO）。
3. 死锁的生命周期（能力体系总览）
建议用统一治理体系理解死锁：
死锁治理体系
├── 预防（Prevention）——破坏必要条件
├── 避免（Avoidance）——仅进入安全状态
├── 检测（Detection）——持续检测环路
└── 恢复（Recovery）——打破死锁
此体系适用于：
- 操作系统
- 数据库
- 分布式系统
- JDK、Go、Rust 等语言运行时
4. 死锁预防（Prevention）：运行前避免死锁
核心思想：从根源破坏"导致死锁的必要条件"之一。
| 要破坏的条件 | 对应策略 | 原理 |
|---|---|---|
| 互斥 | 共享资源、假脱机 | 消除独占性 |
| 占有并等待 | 运行前请求全部资源 | 不形成链式请求 |
| 不可抢占 | 允许抢占 | 消除封闭环路 |
| 环路等待 | 资源编号、顺序锁 | 阻止环路形成 |
适用于： 数据库锁顺序、两阶段加锁、资源分级、多锁策略等。
5. 死锁避免（Avoidance）：运行中确保安全状态
5.1 安全状态（Safe State）
存在至少一种进程顺序能让所有执行完毕 → 状态安全。 否则→ 不安全。不安全 ≠ 死锁，但可能发展为死锁。
5.2 银行家算法（Banker's Algorithm）
通过模拟资源分配，判断是否会进入不安全状态。
核心结构：
- E：资源总量向量
- A：当前可用向量
- C：当前已分配资源矩阵
- R：最大需求矩阵
算法思想：
- 找到一个需求 ≤ A 的进程
- 假设其结束并释放资源
- 更新 A
- 重复直到全部结束
该算法体现：
避免死锁不是避免等待，而是避免进入无法撤退的状态空间。
6. 死锁检测（Detection）：发现环路
6.1 单实例资源：等待图环路检测
使用 DFS 或 Tarjan 算法检查环路。 复杂度：O(V + E)
6.2 多实例资源：资源分配矩阵检测
检测是否存在一个进程可获满足请求，若所有都不能则死锁。
适用系统：数据库、OS、线程调度器。
7. 死锁恢复（Recovery）：从死锁中走出
策略按破坏成本排序：
7.1 抢占（Preemption）
从某进程强制拿走资源 → 恢复可行性。
7.2 回滚（Rollback）
回到检查点 → 放弃部分计算 → 常见于事务系统。
7.3 终止进程（Kill）
选择"牺牲者（victim）"终止。数据库常用。
牺牲者选择策略可按代价模型（cost model）优化：已运行时间、持有资源数量、优先级等。
8. 工程视角：现代系统中的死锁
8.1 操作系统
- mutex、semaphore
- IO 资源竞争
- 内核锁（如 Linux Big Kernel Lock 历史）
8.2 JVM / Java
- synchronized 死锁
- ReentrantLock + tryLock 作为死锁规避
- 通过 Thread Dump 查看 WFG
8.3 Go
- goroutine + channel 死锁（运行时直接 panic）
- select + timeout 避免通信死锁
8.4 数据库
- 行锁 / 表锁
- 两阶段锁协议（2PL）
- 死锁检测器（等待图）
8.5 分布式系统
- 分布式锁（Redis/ZK）死锁风险更高
- 因网络分区导致"伪死锁"
- 租约（Lease）、超时、心跳是核心策略
9. 相关问题与概念边界（避免混淆）
| 概念 | 特征 | 是否死锁？ |
|---|---|---|
| 死锁 | 所有进程都停止推进 | ✔ |
| 活锁 | 进程不断变化但不前进 | ✘ |
| 饥饿 | 某些进程永远不得资源 | ✘ |
| 通信死锁 | 双方等待消息，不涉及资源 | ✔（等待图形式） |
| 响应性慢 | 资源分配不均衡 | ✘ |
这是构建概念体系的重要部分，帮助工程中准确定位问题。
10. 典型错误示例（编程层面）
void fa(){
down(r1);
down(r2);
up(r1);
up(r2);
}
void fb(){
down(r2);
down(r1);
up(r1);
up(r2);
}
fa 和 fb 对资源请求顺序不一致 → 静态顺序死锁。
工程解决方案：
- 固定资源顺序（资源编号法）
- tryLock + 超时
- 两阶段锁协议
11. 死锁治理最佳实践（统一策略）
✔ 编程层面
- 固定资源获取顺序（资源编号法）
- 尽量减少锁的粒度和持有时间
- 使用 tryLock / select+timeout
- 尽量使用无锁结构
✔ 系统层面
- 运行时死锁检测器
- 线程转储分析
- 资源监控与报警
✔ 分布式系统层面
- 分布式锁需带超时避免永久死锁
- 使用租约（lease）而非永久锁
- 心跳 + 强制回收
12. 总结：统一心智模型
死锁不是一个孤立问题，而是"系统状态空间不可逆"的表现。 所有策略都围绕"让系统进入、维持或恢复到可逆状态"展开。
核心统一框架：
抽象模型：资源分配图 / 等待图（WFG）
↓
四个必要条件：图结构特征
↓
策略体系：预防 / 避免 / 检测 / 恢复
↓
工程实现：OS / JVM / DB / 分布式系统
↓
边界概念：死锁 vs 活锁 vs 饥饿
这就是一个可复用、可迁移、跨学科的死锁知识体系。