死锁

形式陈述 ​

死锁是系统到达某个状态后，一组非空参与者 $D$ 的每个成员都在等待只能由 $D$ 中其他成员引发的事件，因而在没有外部恢复时，$D$ 中没有参与者能够完成当前操作。它是活性公理库安全性与活性Safety and liveness · Correctness properties把系统正确性分为坏事永不发生与好事最终发生两类性质。失败：系统可以继续调度、计时或处理与 $D$ 无关的工作，被困操作却不再取得目标进展。

在资源分配模型中，经典 Coffman 分析列出死锁同时存在的四个必要条件：

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

这些条件是特定资源模型下的结构分析，不是任意并发协议的完整定义。建立 wait-for 有向图公理库有向图Directed graph · Digraph边具有方向、可表示为顶点有序对集合的图。 $G=(P,E)$：顶点为参与者，若 $p$ 的继续执行需要 $q$ 释放资源或产生事件，则加入边 $p\to q$。当每类资源只有一个实例、请求不可被其他路径满足且资源不可抢占时，图中有环与相应参与者死锁等价。存在多个同类资源、可替代响应、超时或复杂消息条件时，一个环可能只是风险信号，充分性需按模型重新证明。

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

直觉 ​

死锁的关键不是“大家都停了”，而是等待形成封闭依赖。线程 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 加回退，或运行时检测；这些方法分别改变占有条件、等待方式或恢复路径。

死锁与活锁公理库活锁Livelock · 活跃锁参与者持续响应并改变状态，却在无限执行中不再产生规格所要求完成事件的进展失败。、饥饿公理库饥饿与公平性Starvation and fairness · 调度公平性 · 无饥饿用调度与服务选择的公平假设刻画持续请求者是否可能永久得不到完成机会。都让某些工作不完成，却有不同结构：死锁参与者无法采取解除依赖的有效步骤，活锁参与者不断采取步骤但目标不完成，饥饿则是系统持续服务别人而长期略过某个请求。正确诊断决定应调整锁序、退避协议还是公平策略。

参考资料

• 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, deadlocks chapter。
• Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann, 1996，关于等待与分布式执行的相关章节。