第6章 死锁（资源竞争的困境）
一、导读
1.1 本章学习目标
理解死锁的定义、特征和对系统的影响
掌握死锁产生的四个必要条件及其含义
了解死锁预防的四种策略及其对系统性能的影响
掌握银行家算法（Banker's Algorithm）的原理和安全性检查过程
理解死锁检测的算法和资源分配图的使用方法
掌握死锁恢复的常见策略及其优缺点
了解实际操作系统中处理死锁的方法和策略选择
理解资源分配图（Resource Allocation Graph）的构建和分析
1.2 为什么本章如此重要
死锁是并发系统中最棘手的问题之一。当多个进程相互等待对方持有的资源而无法继续执行时，系统就陷入了死锁状态。死锁不仅导致相关进程无法完成，还可能影响整个系统的性能——被死锁进程占用的资源无法被其他进程使用，系统的资源利用率和吞吐量显著下降。在极端情况下，死锁可能导致系统完全瘫痪。
从历史角度看，死锁问题在早期操作系统中频繁出现，促使研究者发展出系统的理论和方法。Dijkstra的银行家算法是第一个系统化的死锁避免方案，开创了死锁研究的先河。死锁问题的研究推动了资源管理理论、形式化验证和分布式系统一致性等领域的发展。
在现代计算环境中，死锁问题变得更加复杂。多核处理器、分布式系统、数据库事务和微服务架构都面临死锁的威胁。数据库系统使用锁管理器检测和解决死锁，分布式系统使用超时和两阶段提交协议处理死锁，Java虚拟机提供死锁检测工具。理解死锁的原理和处理策略，对于设计可靠的并发系统和编写健壮的并发程序至关重要。
1.3 核心问题引导
死锁产生的四个必要条件是什么？为什么四个条件必须同时满足？
为什么破坏互斥条件通常不可行？哪些资源的互斥性是固有的？
银行家算法如何判断系统是否处于安全状态？安全状态和不安全状态有什么区别？
死锁检测的开销有多大？检测频率应该如何设定？
为什么大多数通用操作系统（如Linux、Windows）选择不处理死锁？
资源分配图中的环路是否一定意味着死锁？什么情况下环路不等于死锁？
鸵鸟算法（忽略死锁）在什么情况下是合理的策略？
二、核心概念详解
2.1 死锁的定义与特征
死锁（Deadlock）是一组进程中的每个进程都在等待一个事件，而该事件只能由这组进程中的另一个进程触发，导致所有进程都无法继续执行的状态。死锁的特征是：没有外部干预，死锁进程永远无法自行解除。
死锁产生的四个必要条件（Coffman条件）必须同时满足才会发生死锁。互斥条件（Mutual Exclusion）：资源一次只能被一个进程使用，其他进程必须等待。请求与保持条件（Hold and Wait）：进程持有至少一个资源，同时请求另一个被其他进程持有的资源。不可剥夺条件（No Preemption）：资源只能由持有者主动释放，不能被强制剥夺。循环等待条件（Circular Wait）：存在一组进程{P1, P2, ..., Pn}，P1等待P2持有的资源，P2等待P3持有的资源，...，Pn等待P1持有的资源，形成环路。
值得注意的是，循环等待条件隐含了请求与保持和不可剥夺条件。如果四个条件中任何一个不满足，死锁就不会发生。死锁处理策略的核心思想就是破坏其中一个或多个条件。
2.2 死锁预防
死锁预防（Deadlock Prevention）通过确保四个必要条件中至少一个不成立来防止死锁发生。
破坏互斥条件：将互斥资源转换为可共享资源。例如，使用假脱机（spooling）技术将打印机转换为共享设备——所有进程的输出先写入磁盘上的假脱机文件，由守护进程统一打印。但很多资源的互斥性是固有的（如文件的写操作），无法消除。
破坏请求与保持条件：要求进程在开始执行前一次性申请所有需要的资源。如果所有资源都可用则分配，否则进程等待。这种方案的缺点是资源利用率低——进程可能长时间持有某些资源而不使用，其他进程无法访问。还可能导致饥饿——某些资源需求大的进程可能永远无法获得所有资源。
破坏不可剥夺条件：允许抢占进程的资源。如果进程P持有资源R并请求资源S（被进程Q持有），则P被抢占资源R。P必须等待S和R都可用时才能恢复执行。这种方案适用于状态容易保存和恢复的资源（如CPU、内存），但不适用于打印机等状态难以恢复的资源。
破坏循环等待条件：对所有资源类型定义全序关系，要求进程按递增顺序请求资源。如果进程已持有资源Ri，则只能请求Rj（j > i）。这种方案通过消除环路来防止死锁，但要求程序员严格遵守资源请求顺序，增加了编程复杂度。
2.3 死锁避免与银行家算法
死锁避免（Deadlock Avoidance）允许四个必要条件存在，但在每次资源分配前检查系统是否处于安全状态。如果分配后系统进入不安全状态，则拒绝分配并让进程等待。
安全状态是指存在至少一个安全序列（Safe Sequence）——一种进程执行顺序，使得每个进程都能获得所需资源并顺利完成。不安全状态是指不存在安全序列，但不一定已经死锁——不安全状态可能导致死锁，也可能不会（如果进程提前释放资源）。
银行家算法（Banker's Algorithm）由Dijkstra提出，是最经典的死锁避免算法。算法维护以下数据结构：Available[j]——资源类型Rj的可用数量；Max[i][j]——进程Pi对资源Rj的最大需求；Allocation[i][j]——进程Pi当前持有的Rj数量；Need[i][j] = Max[i][j] - Allocation[i][j]——进程Pi还需要的Rj数量。
当进程请求资源时，算法执行安全性检查：假设分配请求的资源，检查是否存在安全序列。安全性算法维护一个工作向量Work（初始等于Available）和完成标志Finish。重复寻找满足Finish[i]=false且Need[i] <= Work的进程Pi，如果找到则假设Pi完成，释放其资源（Work += Allocation[i]，Finish[i]=true）。如果所有进程的Finish都为true，则系统处于安全状态，可以分配资源；否则拒绝分配。
银行家算法的局限性：需要预先知道每个进程的最大资源需求，这在实际中很难确定；进程数量固定，不支持动态创建进程；资源数量固定；算法开销为 O(n²·m)，在大规模系统中可能成为瓶颈。
2.4 死锁检测与恢复
死锁检测（Deadlock Detection）允许死锁发生，定期运行检测算法检查系统是否处于死锁状态。检测算法维护每个资源类型的可用向量和每个进程的分配/请求矩阵，通过类似银行家算法的安全性检查寻找死锁进程。
资源分配图（Resource Allocation Graph, RAG）是死锁检测的可视化工具。图中有进程节点（圆圈）和资源节点（方框），请求边从进程指向资源，分配边从资源指向进程。如果图中没有环路，则系统没有死锁。如果图中有环路，对于单实例资源类型，环路等价于死锁；对于多实例资源类型，环路是死锁的必要条件但不充分。
死锁恢复策略包括：终止所有死锁进程——简单但代价大；逐个终止死锁进程直到死锁解除——每次终止后重新检测，代价较小但需要多次检测；抢占资源——从死锁进程中抢占资源分配给其他进程，但抢占可能导致进程状态不一致；回滚进程——将进程回滚到之前的安全状态，需要维护检查点信息。选择终止哪个进程时考虑：进程优先级、已运行时间、已使用资源、剩余需求、交互进程数量等因素。
三、深入分析与讨论
3.1 死锁处理策略的选择
实际系统中选择哪种死锁处理策略取决于应用特点。鸵鸟算法（忽略死锁）适用于死锁频率极低且死锁代价可接受的场景。大多数通用操作系统（如Linux、Windows）对用户进程采用这种策略——如果进程死锁，用户可以手动终止。数据库系统通常采用死锁检测，因为事务死锁较常见且检测开销可接受。实时系统通常采用死锁预防，因为实时系统不能容忍不确定的延迟。
死锁预防简单但过于保守，可能拒绝实际上不会导致死锁的资源请求。死锁避免（银行家算法）更精确但需要预知最大需求。死锁检测允许死锁发生后再处理，适用于死锁频率低的系统。实际系统通常结合多种策略——对关键资源使用预防，对一般资源使用检测。
3.2 分布式系统中的死锁
分布式系统中的死锁比单机系统更复杂。每个节点只有局部信息，无法直接构建全局资源分配图。分布式死锁检测算法包括：集中式算法——一个协调器收集所有节点的局部等待图，合并后检测全局环路；分布式算法——节点之间交换等待信息，通过扩散算法检测全局环路；层次化算法——节点按层次组织，每层汇总下层信息后检测。
分布式死锁检测面临的主要挑战包括：消息延迟导致的信息不一致、节点故障导致的误判、检测算法本身的消息开销。两阶段锁协议（Two-Phase Locking）在分布式事务中广泛使用，但可能增加死锁概率。超时策略是分布式系统中最常用的死锁处理方法——如果一个事务等待超过阈值时间，则假设发生死锁并回滚。
四、实践案例
4.1 数据库系统的死锁处理
现代数据库系统（如MySQL、PostgreSQL、Oracle）使用死锁检测处理事务死锁。数据库维护事务的等待图（Wait-for Graph），当事务请求被其他事务持有的锁时添加等待边，当锁释放时删除等待边。检测算法定期（或在每次锁请求时）搜索等待图中的环路。
MySQL的InnoDB引擎在检测到死锁时选择一个"代价最小"的事务进行回滚（代价基于回滚的数据量和已执行的操作数）。被回滚的事务收到死锁错误，应用程序需要重试。PostgreSQL使用类似的机制，但在高并发场景下可能采用锁超时作为补充。Oracle使用超时策略而非死锁检测，等待超过一定时间的事务被回滚。
4.2 Java程序中的死锁检测
Java虚拟机提供内置的死锁检测工具。jstack命令可以生成线程转储（Thread Dump），其中会标识死锁的线程和它们持有的锁。jconsole和VisualVM等图形化工具可以实时监测死锁。ThreadMXBean.findDeadlockedThreads()方法允许程序在运行时检测死锁。
Java的synchronized关键字可能导致死锁——两个线程以不同顺序获取多个对象的内置锁。解决方案包括：固定锁获取顺序、使用tryLock()带超时的ReentrantLock、使用java.util.concurrent中的高级同步工具。Java的并发包提供了许多无锁或低死锁风险的数据结构和算法。
五、常见误区与注意事项
不安全状态不等于死锁：不安全状态只是可能导致死锁，如果进程提前释放资源或按安全序列执行，系统可以从不安全状态恢复。银行家算法拒绝所有不安全状态的分配请求，可能过于保守。
资源分配图中的环路不一定意味着死锁：对于单实例资源类型，环路与死锁等价。但对于多实例资源类型，环路只是死锁的必要条件，还需要检查是否有足够的可用资源打破环路。
银行家算法不是万能的：银行家算法需要预知最大资源需求，这在实际中往往不可能。进程的运行时行为是动态的，最大需求可能随输入数据变化。银行家算法更适合资源需求可预测的嵌入式或实时系统。
死锁预防不一定比死锁检测好：死锁预防可能显著降低资源利用率和系统吞吐量。在死锁频率低的系统中，死锁检测加恢复的总开销可能小于持续预防的开销。
忽略死锁不等于死锁不会发生：虽然大多数操作系统对用户进程不处理死锁，但内核内部的死锁（如锁顺序错误）可能导致系统崩溃。内核开发者必须严格遵守锁排序协议。
六、本章小结
本章深入探讨了死锁问题的本质和处理策略。死锁是多个进程相互等待资源而无法继续执行的状态，产生的四个必要条件（互斥、请求与保持、不可剥夺、循环等待）必须同时满足。死锁预防通过破坏必要条件防止死锁，但可能降低系统性能。死锁避免如银行家算法在分配前进行安全性检查，保证系统始终处于安全状态，但需要预知资源需求。死锁检测允许死锁发生后通过资源分配图检测环路并恢复，适用于死锁频率低的系统。实际系统根据应用特点选择合适的策略，通常结合多种方法。
七、思考题与练习
给出一个具体的死锁场景，分析其满足的四个必要条件。
解释为什么破坏互斥条件通常不可行，举出可以破坏互斥条件的例子。
使用银行家算法判断给定的资源分配状态是否安全，如果是则给出安全序列。
分析破坏循环等待条件的资源有序分配法，讨论其在实际编程中的应用。
比较死锁预防、避免和检测三种策略的优缺点，说明各自的适用场景。
构建一个包含多实例资源的资源分配图，说明环路与死锁的关系。
讨论分布式系统中死锁检测的主要挑战和解决方案。
设计一个实验，在Java程序中制造死锁并使用工具检测它。