Skip to content

死锁的原因是什么，如何解决死锁

1. 死锁产生的原因和必要条件

在并发系统中，死锁（Deadlock）指：一组进程/线程彼此等待对方占有的资源（或等待对方发出的事件），导致所有参与者都无法继续推进，且这种等待不会自动消失。

一个典型例子（两把锁的交叉获取）：

// T1
lock(A);
lock(B); // 等待 T2

// T2
lock(B);
lock(A); // 等待 T1

死锁的产生并非偶然，它必须同时满足以下四个必要条件，缺一不可：

  1. 互斥条件 (Mutual Exclusion)：指一个资源在同一时刻只能被一个进程所使用。 如果其他进程请求该资源，则必须等待，直到资源被释放。这是许多资源（如打印机、处理器）固有的特性，通常无法破坏。

  2. 请求与保持条件 (Hold and Wait)：指进程已经至少保持了一个资源，但又提出了新的资源请求，而该资源已被其他进程占用，此时请求进程被阻塞，但对自己已获得的资源保持不放。

  3. 不可剥夺条件 (No Preemption)：指进程已获得的资源，在未使用完之前，不能被其他进程强行剥夺，只能由获得该资源的进程自己释放。

  4. 循环等待条件 (Circular Wait)：在发生死锁时，必然存在一个进程—资源的环形链，即进程集合{P0, P1, …, Pn}中的 P0 正在等待一个 P1 占用的资源；P1 正在等待 P2 占用的资源，……，Pn 正在等待已被 P0 占用的资源。

除了这四个必要条件，导致死锁的具体原因还包括：

  • 资源竞争：当系统中可供多个进程共享的资源不足时，进程会因争夺资源而陷入僵局。
  • 进程推进顺序不当：进程在运行过程中，请求和释放资源的顺序不当，也可能导致死锁。

补充区分：

  • 死锁：大家都“等着不动”，必须靠外力（重试、回滚、杀进程、剥夺资源）打破。
  • 活锁：大家都在“动”，但总在互相让步/重试导致一直做无用功，系统没有实质进展。
  • 饥饿：某个线程长期拿不到资源（一直被更高优先级/更幸运者抢走），但系统整体仍在推进。

2. 如何解决死锁

解决死锁的方法通常分为四大类：死锁预防、死锁避免、死锁检测与解除，以及忽略该问题（如鸵鸟算法）。

2.1 死锁预防 (Deadlock Prevention)

死锁预防的核心思想：在设计/实现层面施加“静态规则”，让系统从机制上不可能同时满足四个必要条件，从而“从根上”杜绝死锁。

它通常会牺牲一定的并发性或增加实现复杂度，因此工程上常见做法是：

  • 对关键路径、内核路径、基础库使用更强的预防规则（例如锁顺序）。
  • 对业务层并发使用较轻量策略（例如 try-lock + 回退、超时 + 重试），并配合检测/观测工具。

下面按“四个必要条件”逐类讲清楚常见的预防策略/算法、适用前提与利弊。

2.1.1 破坏互斥条件：让资源“可共享/可复制/可虚拟化”

互斥来自资源的天然属性：例如互斥锁、写文件锁、某些硬件设备、临界区等。完全破坏互斥通常不现实，但可以通过“资源形态改造”减少必须互斥的部分：

1) 只读共享、读写分离

  • 将“读操作”从互斥资源中剥离：读写锁（RWLock）、RCU、Copy-on-Write（CoW）等。
  • 本质是把“独占的写”缩小到更短时间窗口，让大多数并发变成共享读。

2) 虚拟化/假脱机（Spooling）

  • 经典例子：打印机不可并发，但可以把打印请求写入磁盘队列（spooler），由后台单线程顺序输出。
  • 这样进程不再直接独占打印机，而是把请求提交到一个“可并发访问的队列”里。

3) 无锁/低锁数据结构

  • 通过原子操作（CAS）、环形队列、并发哈希等减少互斥锁使用。
  • 注意：这更多是“降低互斥”而非完全“破坏互斥”；且正确性、ABA、内存模型成本更高。

2.1.2 破坏请求与保持条件：不允许“拿着旧资源再等新资源”

请求与保持条件（Hold and Wait）是工程里最常见的死锁导火索：线程先拿到 A，又去等 B；另一个线程先拿到 B，又去等 A。

常见预防算法/策略：

1) 一次性申请（All-or-Nothing / 一次性分配所有资源）

  • 规则：进程在进入执行阶段前，一次性声明并申请“本次任务所需的全部资源”。要么全部拿到并开始执行，要么一个也不拿、等待重试。
  • 优点：简单、从机制上杜绝“持有 + 等待”。
  • 缺点：需要提前知道资源需求；资源利用率低；容易造成饥饿（一直凑不齐就一直等）。

2) 尝试获取 + 回退（try-lock + rollback）

  • 规则：按固定策略尝试获取多个锁；如果获取失败，则释放已持有的锁，等待一段随机退避时间后重试。
  • 本质：把“阻塞等待”变成“失败回退”，从而减少形成稳定环路的机会；但严格来说它更像工程化的“规避/缓解”，不一定能数学保证“永不死锁”（要看策略是否引入全序/是否允许阻塞）。
  • 常见写法（配合锁顺序更稳）：
lock(A)
if !try_lock(B):
    unlock(A)
    backoff()
    retry
// got A and B
...
unlock(B); unlock(A)

2.1.3 破坏不可剥夺条件：让资源可被“抢占/回收”

不可剥夺（No Preemption）强调：拿到的资源只能自愿释放。若我们允许系统在某些条件下“强制回收”，就能打破死锁成立的必要前提。

1) 资源可抢占（Preemptable Resources）

  • 适用资源：CPU（时间片轮转）、内存页/页框（通过换出）、网络带宽配额等。
  • 不适用资源：正在进行的 I/O 设备独占、不可中断的临界操作、不可回滚的外部副作用等。

2) 请求失败则强制释放已占资源

  • 规则：进程已持有一组资源 R。若它请求新资源 r 且无法立即获得，则系统要求其释放 R，并稍后重新申请。
  • 直觉：既然你要等，那就别“占着不放”，把资源让出去。
  • 风险：需要能安全回滚/重做；否则会出现一致性问题或巨大性能损耗。

3) 基于时间戳/优先级的抢占策略

  • 思路：为每个事务分配时间戳（越小越“老”）或优先级。冲突时让“老事务”更有权利推进，从而避免形成环路。
  • Wait-Die：老事务等待年轻事务；年轻事务遇到老事务则回滚“die”。（等待方向单一，减少环路）
  • Wound-Wait：老事务“伤害”年轻事务，让年轻事务回滚；年轻事务只能等待老事务。
  • 这类策略在操作系统里不一定原样使用，但非常适合说明“抢占/回滚”如何从机制上破坏不可剥夺。

2.1.4 破坏循环等待条件：建立“资源全序”，禁止反序获取（最常用）

循环等待（Circular Wait）是死锁在图论层面的核心：只要等待图出现环，就可能死锁。最常用、最工程化、也最容易落地的预防算法就是 资源有序分配法（Lock Ordering / Resource Ordering）。

1) 资源有序分配法（全序/偏序）

  • 做法：为每类资源（或每把锁）分配一个全局序号/层级（rank/level），规定：
  • 只能按序号递增的顺序申请资源
  • 释放顺序任意（通常逆序释放更利于阅读/排错，但不是必要条件）
  • 证明直觉：如果所有等待边都“指向更高序号”，就不可能回到更低序号形成环。

2) 锁层级（Hierarchical Locking）与“锁等级校验”

  • 把锁按层级分组：例如 L0(最外层) → L1 → L2(最内层)。
  • 线程进入更内层前必须持有外层锁，且不能在内层再去申请外层锁。
  • 工程实践中常配合静态分析/运行时断言（debug build）：
  • 每个线程记录当前已持有的最高层级；
  • 新锁的层级必须 ≥ 当前层级，否则直接报错（帮助早期发现反序获取）。

2.1.5 预防策略对比

破坏的必要条件 常见策略/算法 优点 主要代价/风险
互斥 读写分离、资源复制、spooling、无锁化 并发度高、减少锁竞争 实现复杂、额外内存/一致性成本、并非对所有资源适用
请求与保持 一次性申请、请求前先释放、保守 2PL、try-lock 回退 思路直观、容易解释 需要预知资源集合/浪费资源/可能饥饿或活锁
不可剥夺 可抢占资源、请求失败则释放、基于时间戳的回滚策略 能打破僵局、提升系统可恢复性 需要回滚/重做机制，不适用于不可中断副作用
循环等待 资源有序分配、锁层级、按对象 id 排序加锁 最工程化、可严格保证不死锁 需要全局规则与长期治理；跨模块容易破坏

2.2 死锁避免 (Deadlock Avoidance)

死锁预防的策略通常会降低系统的并发性。死锁避免则是一种更动态的方法，它在资源分配过程中，通过算法来判断本次分配是否会导致系统进入不安全状态，从而避免死锁的发生。

  • 安全状态：系统处于安全状态是指系统能按某种进程顺序(P1, P2, …, Pn)来为每个进程分配其所需的资源，直至最大需求，使每个进程都可以顺利地完成。
  • 银行家算法 (Banker's Algorithm)：这是最著名的死锁避免算法。在分配资源之前，系统会检查这次分配是否会导致系统从安全状态转变为不安全状态。如果是，则不予分配，让进程等待。

2.3 死锁检测与解除 (Deadlock Detection and Recovery)

这种策略允许死锁的发生，但系统会不断地监测，判断死锁是否真的发生了。一旦检测出死锁，就会采取措施来解除它。

  • 死锁检测：
    • 资源分配图：通过检测资源分配图中是否存在环路来判断是否发生了死锁。 系统会定期运行一个算法来检测这个图。
  • 死锁解除：一旦检测到死锁，可以采取以下措施：
    • 资源剥夺法：挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。
    • 撤销进程：强制撤销部分甚至全部死锁进程，并剥夺这些进程的资源。
    • 进程回滚：让一个或多个进程回退到足以避免死锁的地步。

2.4 忽略死锁

在某些系统中，死锁发生的概率很低，而用于预防、避免或检测和解除死锁的开销又很大。在这种情况下，可以采取“鸵鸟算法”，即假装问题从未发生过。 如果真的发生了死锁，可以通过重启系统来解决。

3. 预防 / 避免 / 检测：怎么选

  • 预防：靠规则“保证不可能死锁”，但会限制并发、需要统一约束（锁顺序/一次性申请/可抢占）。
  • 避免：靠算法在运行时判定“是否安全”（典型银行家），需要已知最大需求，开销高，现实 OS 中较少直接使用。
  • 检测与解除：允许死锁，定期检测（等待图/资源分配图），再用回滚/剥夺/杀进程解除；适合系统复杂、难以强约束的场景。
策略 描述 优点 缺点
死锁预防 通过破坏死锁产生的四个必要条件之一来防止死锁。 简单，从根本上防止死锁。 限制了并发性，降低了资源利用率。
死锁避免 在资源分配时动态判断是否会进入不安全状态，从而避免死锁。 相比预防并发性/利用率更高（在“安全”前提下分配）。 通常需要预知最大资源需求/声明上限，且算法开销较大。
死锁检测与解除 允许死锁发生，但通过检测机制及时发现并采取措施解除。 资源利用率和并发性较高。 检测和解除死锁的开销可能很大。
忽略死锁 假定死锁不会发生，不采取任何措施。 无系统开销。 系统可能因死锁而挂起，需要手动干预（如重启）。