死锁

0. 引言：死锁的本质

死锁（Deadlock）的本质并不是"几个进程卡住不动"，而是：

系统进入了一个不可逃逸的状态空间（Irreversible State），其内部所有进程的推进都依赖于彼此引发的事件，而这些事件永远不会发生。

从统一抽象模型看：死锁 = 等待关系图（Wait-For Graph）中出现不可消除的环路。

理解死锁要从 系统状态空间 与 资源分配图 入手，再将所有策略归纳为一套 死锁治理体系。

1. 死锁的抽象模型（核心框架）

1.1 资源分配图（RAG：Resource Allocation Graph）

系统由两类节点构成：

边表示关系：

若改写为等待图（WFG），则为：

所有死锁判定和策略都可从此图推导。

1.2 死锁的四个必要条件（从模型导出）

死锁产生要求 全部成立：

条件本质含义对应模型表现
互斥资源不可共享R 节点只有一个出边
占有并等待持有部分资源继续请求P 节点同时连接 Rout 和 Rin
不可抢占资源不能强制收回图结构不可修改
环路等待存在闭环WFG 出现环路

四条件不是规则，而是图结构的特征只要等待图中出现"闭环"，其成因必然表现为这四条。

2. 死锁的类型（从系统视角分类）

2.1 静态顺序死锁

资源顺序固定但多个线程以不同顺序请求 → 环路出现。

2.2 动态顺序死锁

资源的请求动态变化，无法保证统一顺序。

2.3 资源死锁（经典 OS 死锁）

争夺有限、不可抢占资源（锁、文件、IO）。

3. 死锁的生命周期（能力体系总览）

建议用统一治理体系理解死锁：

死锁治理体系├── 预防（Prevention）——破坏必要条件├── 避免（Avoidance）——仅进入安全状态├── 检测（Detection）——持续检测环路└── 恢复（Recovery）——打破死锁

此体系适用于：

4. 死锁预防（Prevention）：运行前避免死锁

核心思想：从根源破坏"导致死锁的必要条件"之一。

要破坏的条件对应策略原理
互斥共享资源、假脱机消除独占性
占有并等待运行前请求全部资源不形成链式请求
不可抢占允许抢占消除封闭环路
环路等待资源编号、顺序锁阻止环路形成

适用于：数据库锁顺序、两阶段加锁、资源分级、多锁策略等。

5. 死锁避免（Avoidance）：运行中确保安全状态

5.1 安全状态（Safe State）

存在至少一种进程顺序能让所有执行完毕 → 状态安全。否则→ 不安全。不安全 ≠ 死锁，但可能发展为死锁。

5.2 银行家算法（Banker's Algorithm）

通过模拟资源分配，判断是否会进入不安全状态。

核心结构：

算法思想：

  1. 找到一个需求 ≤ A 的进程
  2. 假设其结束并释放资源
  3. 更新 A
  4. 重复直到全部结束

该算法体现：

避免死锁不是避免等待，而是避免进入无法撤退的状态空间。

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 操作系统

8.2 JVM / Java

8.3 Go

8.4 数据库

8.5 分布式系统

9. 相关问题与概念边界（避免混淆）

概念特征是否死锁？
死锁所有进程都停止推进✔
活锁进程不断变化但不前进✘
饥饿某些进程永远不得资源✘
通信死锁双方等待消息，不涉及资源✔（等待图形式）
响应性慢资源分配不均衡✘

这是构建概念体系的重要部分，帮助工程中准确定位问题。

10. 典型错误示例（编程层面）

void fa(){    down(r1);    down(r2);    up(r1);    up(r2);}void fb(){    down(r2);    down(r1);    up(r1);    up(r2);}

fa 和 fb 对资源请求顺序不一致 → 静态顺序死锁。

工程解决方案：

11. 死锁治理最佳实践（统一策略）

✔ 编程层面

✔ 系统层面

✔ 分布式系统层面

12. 总结：统一心智模型

死锁不是一个孤立问题，而是"系统状态空间不可逆"的表现。所有策略都围绕"让系统进入、维持或恢复到可逆状态"展开。

核心统一框架：

抽象模型：资源分配图 / 等待图（WFG）↓四个必要条件：图结构特征↓策略体系：预防 / 避免 / 检测 / 恢复↓工程实现：OS / JVM / DB / 分布式系统↓边界概念：死锁 vs 活锁 vs 饥饿

这就是一个可复用、可迁移、跨学科的死锁知识体系。

关联内容（自动生成）