第3章 死锁（资源竞争的困境） Deadlock
一、导读
1.1 本章学习目标
准确定义死锁（Deadlock）的概念，理解其对系统可用性的严重影响
掌握死锁产生的四个必要条件（Coffman 条件），并能分析具体场景中的死锁成因
理解死锁预防（Prevention）的基本策略及其对系统性能的影响
深入理解死锁避免（Avoidance）的原理，掌握银行家算法（Banker's Algorithm）的工作过程
掌握死锁检测（Detection）与恢复（Recovery）的算法和策略
理解资源分配图（Resource Allocation Graph）在死锁分析中的应用
了解实际操作系统中处理死锁的策略选择和工程实践
能够识别和避免并发编程中常见的死锁模式
1.2 为什么本章如此重要
死锁是并发系统中最棘手的问题之一。当两个或多个进程无限期地等待对方持有的资源时，系统便陷入了死锁状态。受影响的进程既无法继续执行，也无法释放已占有的资源，只能永远等待下去。死锁不仅会导致相关进程停滞，还可能引发连锁反应，影响整个系统的稳定性和可用性。
在数据库系统中，死锁表现为两个事务互相等待对方释放锁；在网络协议中，死锁表现为两个节点互相等待对方的确认帧；在操作系统中，死锁表现为多个进程竞争有限的系统资源。死锁的普遍性使得理解和处理死锁成为每一个系统开发者的必备技能。
从理论角度来看，死锁问题与计算理论中的不可判定性有着深刻的联系。一般性的死锁预测问题被证明是不可判定的——不存在一个算法能够在有限步骤内判定任意程序是否会进入死锁状态。这一理论结论决定了我们只能采用保守的策略（预防、避免）或事后处理（检测与恢复）来应对死锁。
从工程实践角度来看，死锁的处理策略选择体现了系统设计中的核心权衡。预防死锁可能降低资源利用率和系统吞吐量；避免死锁需要预知资源的最大需求，这在许多场景中不现实；检测死锁允许死锁发生但需要付出检测和恢复的开销。不同的系统根据其可靠性要求和性能目标选择不同的策略。例如，数据库系统通常采用死锁检测与回滚策略，而实时系统则倾向于死锁预防以确保确定性行为。
1.3 核心问题引导
什么是死锁？死锁与饥饿（Starvation）有什么区别和联系？
死锁产生的四个必要条件分别是什么？为什么必须同时满足才会发生死锁？
如何通过破坏四个必要条件来预防死锁？每种策略的代价是什么？
银行家算法的核心思想是什么？安全状态与死锁-free 状态之间是什么关系？
资源分配图如何帮助检测死锁？图中环路的含义是什么？
检测到死锁后有哪些恢复策略？各自的优缺点是什么？
为什么大多数通用操作系统（如 Linux、Windows）选择"鸵鸟算法"来处理死锁？
在多线程编程中，如何避免由锁的获取顺序不当导致的死锁？
二、核心概念详解
2.1 死锁的定义与必要条件
死锁（Deadlock）是指两个或多个进程因竞争资源而陷入相互等待的状态，导致这些进程都无法继续向前推进。形式化地描述：设有一组进程 {P1, P2, ..., Pn}，其中每个进程 Pi 都持有一个资源 Ri，并且正在等待另一个进程 Pj 所持有的资源 Rj，那么这组进程就处于死锁状态。
1971 年，E. G. Coffman 提出了死锁产生的四个必要条件（也称为 Coffman 条件），只有当这四个条件同时满足时，系统才可能进入死锁状态。
第一个条件是互斥条件（Mutual Exclusion）。资源在同一时刻只能被一个进程占用。如果另一个进程请求该资源，则请求者必须等待直到资源被释放。互斥是资源的固有属性——打印机、写锁等可写资源天然具有互斥性，而只读文件等资源则不具有互斥性。
第二个条件是请求与保持条件（Hold and Wait）。进程已经持有了至少一个资源，同时又提出了对新资源的请求，而该资源已被其他进程占有。此时进程阻塞在请求操作上，但对自己已持有的资源保持不释放。
第三个条件是不可剥夺条件（No Preemption）。进程已获得的资源不能被强制剥夺，只能由持有者主动释放。如果允许资源被强制剥夺，那么系统可以在检测到潜在死锁时强行回收资源来打破死锁。
第四个条件是循环等待条件（Circular Wait）。存在一个进程等待链：P1 等待 P2 持有的资源，P2 等待 P3 持有的资源，...，Pn 等待 P1 持有的资源，形成一个闭合的环路。循环等待是前三个条件同时成立的必然结果，也是死锁最直观的表现形式。
这四个条件是死锁的必要条件而非充分条件。也就是说，死锁发生时这四个条件一定同时成立，但即使四个条件同时成立，也不一定会发生死锁（取决于时序和资源请求的具体模式）。
2.2 死锁预防策略
死锁预防（Deadlock Prevention）的目标是通过破坏四个必要条件中的至少一个来确保死锁永远不会发生。这种策略最为保守，但可能导致资源利用率下降和系统吞吐量降低。
破坏互斥条件：理论上可以通过将互斥资源改造为可共享资源来消除互斥。例如，使用只读文件代替排他锁，或使用 Spooling 技术将打印机改造为可共享设备。然而，并非所有资源都可以去互斥化——临界区操作的语义本身就要求互斥执行。
破坏请求与保持条件：要求进程在开始执行前一次性申请其所需的全部资源。如果系统能够满足全部资源需求，则分配所有资源让进程执行；否则一个资源也不分配。这种策略的问题在于：进程往往无法预先知道其全部资源需求；资源在进程执行的某些阶段可能暂时不需要，强制提前分配会造成浪费。
破坏不可剥夺条件：当一个进程请求资源失败时，强制其释放已持有的所有资源。进程下次需要执行时，必须重新申请所有资源。这种策略实现较为复杂，且可能导致进程反复申请和释放资源，产生饥饿问题。
破坏循环等待条件：对系统中的所有资源类型进行线性排序，规定进程只能按照序号递增的顺序请求资源。这种策略的优点是实现简单，缺点是需要为所有资源定义一个全局的线性序，且可能限制进程的资源使用模式。在编程实践中，按固定顺序获取锁是避免死锁的最常用技巧。
2.3 死锁避免与银行家算法
死锁避免（Deadlock Avoidance）允许四个必要条件存在，但在每次资源分配前进行安全性检查，确保分配后系统仍处于安全状态。如果分配会导致不安全状态，则拒绝此次分配。
安全状态是指系统至少存在一种资源分配序列（称为安全序列），使得所有进程都能顺利完成。形式化地，如果存在进程序列 <P1, P2, ..., Pn>，使得对于每个 Pi，其尚需的资源能够由当前可用资源加上所有排在 Pi 前面的进程已持有的资源来满足，则系统处于安全状态。安全状态保证不会发生死锁；不安全状态则不保证，但也不一定就会发生死锁。
银行家算法（Banker's Algorithm）由 Dijkstra 于 1965 年提出，是最经典的死锁避免算法。其名称来源于银行家的贷款决策：银行家在批准贷款前会检查剩余资金是否仍能满足至少一个客户的最大需求，从而确保所有客户最终都能得到满足。
银行家算法需要维护以下数据结构：Available（可用资源向量）、Max（每个进程的最大需求矩阵）、Allocation（当前分配矩阵）、Need（每个进程的剩余需求矩阵，Need = Max - Allocation）。当一个进程请求资源时，算法首先检查请求是否超过其 Need，然后检查请求是否超过 Available，最后模拟分配并执行安全性检查算法。安全性检查算法尝试找到一个安全序列：从当前可用资源出发，依次找到 Need 不超过可用资源的进程，假设其完成并释放资源，直到所有进程都能完成（安全）或找不到这样的进程（不安全）。
银行家算法的局限性在于：需要预知每个进程的最大资源需求，这在实际中往往难以实现；进程数量必须是固定的，不允许有新进程动态加入；算法的时间复杂度为 O(m*n^2)，在大规模系统中可能影响性能。
2.4 死锁检测与恢复
死锁检测（Deadlock Detection）允许死锁发生，但通过定期运行检测算法来发现死锁的存在，然后采取恢复措施。这种策略的优点是不需要预防或避免的保守限制，资源利用率较高。
检测算法的核心是检查资源分配图中是否存在环路。对于每种资源类型只有一个实例的情况，可以通过简化版的等待图（Wait-for Graph）来检测——将资源节点消除，如果进程之间仍然存在等待关系并形成环路，则存在死锁。对于每种资源类型有多个实例的情况，需要使用类似于银行家算法的安全性检查方法来检测死锁。
检测到死锁后，系统需要采取恢复措施来打破死锁。常见的恢复策略包括以下几种。
进程终止（Process Termination）：终止一个或多个死锁进程以释放资源。最简单的方法是终止所有死锁进程；更精细的方法是逐个终止进程，每次终止后重新检测死锁是否已解除。终止进程时的考虑因素包括进程优先级、已执行时间、剩余资源需求等。
资源抢占（Resource Preemption）：从死锁进程那里强制剥夺某些资源，分配给其他进程使用。被抢占资源的进程需要回滚到之前的安全状态。选择抢占哪个资源时需要考虑资源的价值、进程的计算进度等因素。
回滚（Rollback）：将死锁进程回滚到某个检查点（Checkpoint），在检查点处释放其占有的资源。检查点机制需要在进程执行过程中定期保存状态信息，回滚后从检查点重新开始执行。
三、深入分析与讨论
3.1 鸵鸟算法的工程合理性
在大多数通用操作系统中（包括 Linux 和 Windows），对死锁的处理策略是著名的"鸵鸟算法"（Ostrich Algorithm）——假装问题不存在。这种看似不负责任的做法实际上有其深刻的工程合理性。
首先，死锁在通用操作系统中发生的频率相对较低。现代操作系统提供了丰富的同步原语和库函数，大多数开发者能够遵循正确的锁使用规范。即使出现死锁，通常也只影响少数进程，不会导致系统整体崩溃。
其次，死锁的预防、避免和检测都需要付出显著的代价。预防策略会降低资源利用率；避免策略需要预知资源需求，这在通用系统中不现实；检测策略需要周期性地运行检测算法，消耗 CPU 资源。对于通用操作系统而言，这些代价可能超过死锁本身带来的损失。
第三，通用操作系统的设计理念是"尽力而为"（Best Effort）。当死锁发生时，用户可以手动终止相关进程来解决问题。操作系统提供了 kill 命令等工具来帮助用户处理这种情况。
然而，在某些特定领域中，鸵鸟算法是不可接受的。数据库系统必须处理死锁，因为事务之间的锁竞争非常频繁。实时系统必须避免死锁，因为死锁可能导致灾难性的后果。分布式系统需要特殊的死锁处理机制，因为死锁可能跨越多个节点。
3.2 分布式系统中的死锁问题
在分布式系统中，死锁问题变得更加复杂。多个节点上的进程可能通过消息传递和资源交换形成跨节点的死锁环路，这种死锁无法通过单个节点的本地检测来发现。
分布式死锁检测的主要方法包括集中式检测和分布式检测。集中式方法指定一个协调节点收集所有节点的资源分配信息，构建全局等待图并检测环路。这种方法实现简单，但协调节点可能成为瓶颈和单点故障。分布式方法让每个节点维护本地等待图的一部分，通过节点之间的消息交换来协作检测全局环路。
分布式死锁的恢复也面临独特挑战。终止远程节点上的进程需要跨节点的协调，可能涉及分布式事务的回滚。网络延迟和分区（Partition）可能导致死锁检测算法产生误判或漏判。
四、实践案例
4.1 数据库系统中的死锁处理
数据库系统是死锁处理策略应用最为成熟的领域之一。在关系型数据库中，多个事务并发执行时可能因争夺行锁、表锁等资源而发生死锁。
MySQL 的 InnoDB 存储引擎采用死锁检测与回滚策略。InnoDB 维护着一个事务等待图，当事务 A 等待事务 B 持有的锁时，在等待图中添加一条从 A 到 B 的边。每次添加新边时，InnoDB 都会检查等待图中是否形成了环路。如果检测到死锁，InnoDB 会选择回滚"代价最小"的事务——通常是被写入日志量最少的事务，即回滚成本最低的事务。
PostgreSQL 也采用了类似的死锁检测机制。当检测到死锁时，PostgreSQL 会终止当前正在等待锁的那个事务（而非最早开始的事务），以最小化对系统的影响。PostgreSQL 还提供了 deadlock_timeout 参数来控制死锁检测的频率，避免过于频繁的检测带来性能开销。
Oracle 数据库同样使用死锁检测和回滚策略。Oracle 的实现中，死锁检测是在事务等待锁超过一定时间后才触发的，这避免了在正常情况下不必要的检测开销。
4.2 多线程编程中的锁顺序死锁
在实际的多线程编程中，最常见的死锁类型是由锁的获取顺序不一致导致的。当多个线程以不同的顺序获取多个锁时，就可能形成循环等待条件。
经典的"哲学家就餐问题"就是锁顺序死锁的抽象模型。五个哲学家围坐在圆桌旁，每人左右各有一支筷子，进餐需要同时持有两支筷子。如果所有哲学家同时拿起左边的筷子，就会形成循环等待——每个人都在等待右边的人放下筷子。
解决锁顺序死锁的最有效方法是规定所有线程以相同的顺序获取锁。例如，如果所有线程都先获取锁 A 再获取锁 B，那么就不可能形成循环等待。在 Java 中，可以通过 System.identityHashCode() 为锁定义全局顺序；在 C++ 中，可以使用 std::lock() 同时获取多个锁以避免死锁。
另一个实用技巧是使用超时机制。线程在尝试获取锁时设置超时时间，如果超时未能获取则释放已持有的锁，等待随机时间后重试。这种策略虽然不能完全避免死锁，但可以将死锁转化为活锁（Livelock），在大多数情况下系统最终能够取得进展。
五、常见误区与注意事项
误区：没有死锁检测工具就意味着系统不会发生死锁。 死锁是并发程序的逻辑问题，无论是否有检测工具，只要满足四个必要条件就可能发生。开发者应当在编码阶段就注意避免死锁。
误区：银行家算法可以解决所有死锁问题。 银行家算法要求预知进程的最大资源需求，且进程数量固定，这些假设在许多实际场景中不成立。银行家算法更多是理论价值，实际应用中较少直接使用。
误区：破坏互斥条件是预防死锁的最佳策略。 互斥是许多资源的固有属性，强行消除互斥可能破坏数据的正确性。在实践中，破坏循环等待条件（按序获取锁）是最常用的预防策略。
注意事项：避免在持有锁时调用外部函数或回调。 外部函数可能尝试获取其他锁，而你无法控制其锁的获取顺序，这极易引入死锁风险。
注意事项：死锁与饥饿是不同的问题。 死锁是所有相关进程都无法推进；饥饿是某些进程长期得不到资源但并非被死锁。使用公平调度策略（如 FIFO 资源分配）可以避免饥饿，但不能避免死锁。
六、本章小结
本章深入分析了死锁这一并发系统中的核心问题。死锁产生的四个必要条件——互斥、请求与保持、不可剥夺和循环等待——为理解和处理死锁提供了理论框架。死锁预防通过破坏必要条件来确保死锁永不发生，但可能降低系统性能。死锁避免（以银行家算法为代表）通过安全性检查来动态决策资源分配，但需要预知资源需求。死锁检测与恢复允许死锁发生后通过终止进程或抢占资源来解除，适用于死锁频率较低的系统。在实际工程中，数据库系统普遍采用死锁检测与回滚策略，多线程编程中则通过规定锁的获取顺序来预防死锁。大多数通用操作系统选择鸵鸟算法，因为死锁发生的频率较低且处理代价较高。理解死锁的本质和处理策略，对于设计可靠的并发系统至关重要。
七、思考题与练习
给出一个具体的死锁场景，验证其满足死锁的四个必要条件。然后分别说明如何通过破坏每个条件来预防该死锁。
假设系统有 3 个同类资源，4 个进程各需要 2 个资源。请问系统是否会发生死锁？如果每个进程各需要 3 个资源呢？请使用银行家算法进行分析。
比较死锁预防、死锁避免和死锁检测三种策略的优缺点。为一个银行交易系统和一个在线游戏服务器分别推荐最合适的死锁处理策略，并说明理由。
实现一个简化版的银行家算法。输入为 Available 向量、Max 矩阵和 Allocation 矩阵，输出为当前状态是否安全，如果安全则给出一个安全序列。
分析以下代码片段中的死锁风险，并提出修复方案：线程 1 先获取锁 A 再获取锁 B，线程 2 先获取锁 B 再获取锁 A。
研究 Linux 内核中的死锁检测机制。内核提供了哪些工具来帮助开发者发现潜在的死锁？lockdep 子系统是如何工作的？
什么是两级锁协议（Two-Phase Locking, 2PL）？它如何保证数据库事务的可串行化？它与死锁有什么关系？
在分布式系统中，设计一个集中式死锁检测算法。分析该算法的时间复杂度、通信开销和单点故障风险，并提出改进方案。