死锁 | Codeboy's Blog

形式陈述

死锁是系统到达某个状态后，一组非空参与者 $D$ 的每个成员都在等待只能由 $D$ 内参与者引发的事件（可包括等待者自身），因而在没有外部恢复时， $D$ 中没有参与者能够完成当前操作。它是活性失败：系统可以继续调度、计时或处理与 $D$ 无关的工作，被困操作却不再取得目标进展。

在有限参与者、有限资源种类的经典资源分配模型中，Coffman 分析列出死锁同时存在的四个必要条件：

互斥占有：至少一种资源一次只能由一个参与者使用；
持有并等待：参与者持有已分配资源，同时请求额外资源；
不可抢占：资源只能由持有者主动释放，系统不能安全夺回；
循环等待：存在 $p_1,\ldots,p_k$ ，使 $p_i$ 等待 $p_{i+1}$ 持有的资源，且 $p_k$ 等待 $p_1$ 持有的资源。

这些条件是特定资源模型下的结构分析，不是任意并发协议的完整定义。建立参与者集合 $P$ 上的等待关系 $E\subseteq P\times P$ ：若 $p$ 的继续执行需要 $q$ 释放资源或产生事件，就令 $(p,q)\in E$ 。参与者有限时，可把它画成 wait-for 有向图，选用该条目允许环的变体；保留 $p\to p$ ，才能表示自己等待自己释放资源的情形。当每类资源只有一个实例、请求不可被其他路径满足且资源不可抢占时，图中有环与相应参与者死锁等价。存在多个同类资源、可替代响应、超时或复杂消息条件时，一个环可能只是风险信号，充分性需按模型重新证明。

处理策略也有不同目标。预防通过破坏至少一个必要条件，例如规定全局锁序来排除循环等待；避免在每次分配前检查新状态是否仍安全，银行家算法是典型例子；检测与恢复允许死锁形成，再分析等待关系并中止、回滚或抢占参与者。三者不能混成“发现环就解决”，因为各自依赖的资源声明、运行开销与可恢复性不同。

直觉

死锁的关键不是“大家都停了”，而是等待形成封闭依赖。线程 A 手里有 B 需要的东西，线程 B 手里有 A 需要的东西；任何一方想遵守协议继续，都必须先等对方。调度器即使给它们无限 CPU 时间，也只能让它们反复确认条件尚未满足。

因此单个线程阻塞并不够。它可能正在等待磁盘，而磁盘控制器能够独立完成请求；也可能等待另一个仍可运行的线程。只有当完成路径被等待集合自身封闭，且模型中没有超时、抢占或故障恢复打破闭环时，才得到死锁结论。

三个线程各持有一个资源并等待下一线程持有的资源，等待边闭合成无人可自行打破的环 — 封闭等待环形成死锁

例子与边界

线程 $T_1$ 先取得锁 A，再请求锁 B；线程 $T_2$ 先取得 B，再请求 A。若两者都完成第一次获取，wait-for 图含 $T_1\to T_2\to T_1$ ，四个 Coffman 条件同时成立。规定所有线程始终按 A、B 的统一顺序获取，便从结构上消除这条循环等待；给第二次获取加超时并回退则允许恢复，但还要处理回退时共享状态是否可安全撤销。

一个线程等待网络响应并不自动死锁。只要远端或 I/O 子系统仍能独立产生响应，等待依赖没有在本地线程集合中闭合，状态只是阻塞或高延迟。反过来，消息协议即使没有任何 mutex，也可能死锁：服务 A 在回复前等待 B 的确认，B 又在确认前等待 A 的回复，协议级事件依赖同样形成闭环。

可重入与故障假设会改变图。非递归 mutex 上，线程再次请求自己已经持有的锁，可形成自环并自死锁；递归锁允许该请求，却要维护递归计数。持锁线程崩溃让其他线程永久等待时，现象像死锁，但其原因包含故障进程而非一组仍遵循协议的循环等待；是否归类以及怎样恢复，必须先声明资源和故障模型。

推论与应用

多锁程序最便于审计的预防方式通常是为资源建立严格全序，只允许沿同一方向获取。若所有等待边都从较小资源指向较大资源，有限图不可能成环。动态资源集合无法预先排序时，可采用一次性申请、可失败的 try_lock 加回退，或运行时检测；这些方法分别改变占有条件、等待方式或恢复路径。

死锁与活锁、饥饿都让某些工作不完成，却有不同结构：死锁参与者无法采取解除依赖的有效步骤，活锁参与者不断采取步骤但目标不完成，饥饿则是系统持续服务别人而长期略过某个请求。正确诊断决定应调整锁序、退避协议还是公平策略。

Wait-die与wound-wait在事务请求冲突锁时按稳定年龄决定等待或中止，使活动等待边保持同一方向。重试保留年龄、中止清理后才释放、持有者变化后复查已有待请求，都是完整协议的一部分；无环仍不等于公平或确定等待上界。

参考资料

Edward G. Coffman, Melanie Elphick, and Arie Shoshani, “System Deadlocks,” ACM Computing Surveys 3(2), 1971, pp. 67–78。
Abraham Silberschatz, Peter B. Galvin, and Greg Gagne, Operating System Concepts, 10th ed., Wiley, 2018, deadlocks chapter。
Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann, 1996，关于等待与分布式执行的相关章节。

形式陈述 ​

反向链接

形式陈述