死锁

写作时间：2026-03-04 首次提交，2026-07-13 最近修改
当前字符：7098

同步原语用锁保护共享不变量，但一条执行流可能同时需要多项资源。只分析每把锁是否正确互斥还不够，还必须分析多把锁之间的依赖关系是否允许所有参与者继续推进。

来看两个线程和两把 mutex。线程 $T_{1}$ 已持有 A，准备获取 B；线程 $T_{2}$ 已持有 B，准备获取 A：

text

T1: lock(A) -> wait for B
T2: lock(B) -> wait for A

两者都只能由持有者主动解锁，但持有者又在等待对方。线程没有崩溃，CPU 也可能继续运行其他任务，这两个线程却无法再到达解锁语句。这种 A 后取 B、B 后取 A 的关系通常称为 ABBA 锁序反转。

本课先从这组关系中提取 死锁条件，再用 资源分配图把持有与等待转换为图问题。识别风险后，通过 死锁处理比较预防、避免、检测和恢复；并发系统即使没有线程永久阻塞，也可能出现 活锁与饥饿。最后用 并发缺陷区分死锁、原子性违规、顺序违规和数据竞争的检测边界。

死锁条件

死锁(deadlock)是一组执行流中的每个成员都在等待只能由组内其他成员触发的事件，因而没有成员能够继续推进的状态。

ABBA 示例可以还原成下面的等待状态：

时刻	$T_{1}$	$T_{2}$	A	B
1	获取 A		$T_{1}$ 持有	空闲
2		获取 B	$T_{1}$ 持有	$T_{2}$ 持有
3	等待 B		$T_{1}$ 持有	$T_{2}$ 持有
4		等待 A	$T_{1}$ 持有	$T_{2}$ 持有

死锁形成必须同时具备四个必要条件：

条件	定义	ABBA 中的表现
互斥	至少一个资源实例不可共享，同一时刻只能由一个参与者使用	A、B 各只能由一个线程持有
持有并等待(hold and wait)	参与者持有至少一项资源，同时等待其他资源	$T_{1}$ 持 A 等 B， $T_{2}$ 持 B 等 A
非抢占(no preemption)	已分配资源不能在任意时刻被系统安全夺走	mutex 只能由协议规定的持有者释放
循环等待(circular wait)	存在首尾相接的等待链	$T_{1} \to T_{2} \to T_{1}$

“必要条件”表示缺少任意一项就不会形成这种死锁，不表示一个允许四项条件存在的系统此刻必然已经死锁。多数 mutex 系统同时具有互斥、持有并等待和非抢占，只有某次执行真正形成循环等待时，相关线程才进入死锁状态。

资源也不只包括 mutex。数据库记录锁、有限设备、内存缓冲区、文件锁和等待另一个线程结束，都可能进入依赖关系。关键判断不是资源名称，而是参与者能否在不获得所等待资源的情况下释放已有资源或完成操作。

同一线程再次获取自己持有的非递归 mutex 会形成自死锁。POSIX 的 error-checking mutex 可以对此返回 EDEADLK，普通 mutex 不承诺检测，更无法自动检测任意多个线程组成的全局环。

资源分配图

资源分配图(Resource-Allocation Graph, RAG)是用有向图表示执行流对资源的请求与分配关系的模型。

图中包含两类节点和两类边：

元素	含义
执行流节点 $T_{i}$	请求和持有资源的线程、进程或事务
资源节点 $R_{j}$	一类资源；节点内可记录实例数量
请求边 $T_{i} \to R_{j}$	$T_{i}$ 正在等待 $R_{j}$ 的一个实例
分配边 $R_{j} \to T_{i}$	$R_{j}$ 的一个实例已经分配给 $T_{i}$

ABBA 对应的图是：

text

T1 -> B -> T2 -> A -> T1

其中 $A \to T_{1}$ 与 $B \to T_{2}$ 是分配边，另外两条是请求边。A、B 都只有一个实例，因此图中的环表示每个资源都只能由环内等待者释放，此时“有环”与“死锁”等价。

判据必须区分资源实例数量：

资源模型	图中无环	图中有环
每类资源单实例	没有死锁	存在死锁
某类资源多实例	没有死锁	可能死锁，需要继续分析

多实例场景中，环外参与者可能释放一个额外实例，使环内请求得到满足。例如 R 有两个实例， $T_{1}$ 和 $T_{3}$ 各持有一个；S 有一个实例，由 $T_{2}$ 持有。若 $T_{1}$ 等 S、 $T_{2}$ 等 R，图中存在 $T_{1} \to S \to T_{2} \to R \to T_{1}$ ，但不等待任何资源的 $T_{3}$ 可以完成并释放 R。随后 $T_{2}$ 获得 R、完成并释放 S， $T_{1}$ 也能继续，因此这个环没有构成死锁。

对于单实例资源，可以去掉资源节点，把“ $T_{i}$ 等待 $T_{j}$ 持有的资源”压缩为 $T_{i} \to T_{j}$ ，得到等待图(wait-for graph)。等待图中的环就是死锁。多实例资源则需要结合每类资源的可用数、已分配数和剩余请求量执行矩阵算法，不能只做环检测。

资源图把一个重要事实显式化：单看线程栈只能知道它正阻塞在哪个接口，只有把所有持有边与请求边合并，才能判断是否形成闭合依赖。

死锁处理

死锁处理是系统在资源分配前、分配时或形成等待后，降低死锁可能性并恢复进展的一组策略。

四类策略介入的时机不同：

策略	介入时机	核心做法	主要代价
预防(prevention)	设计协议时	保证至少一个必要条件不能成立	可能降低并发度或增加编码约束
避免(avoidance)	每次申请资源时	只允许系统停留在安全状态	需要预知最大需求并反复计算
检测(detection)	资源已经分配后	建图或统计等待关系，寻找死锁	检测有开销，且死锁已经可能影响服务
恢复(recovery)	检测到死锁后	回滚、终止参与者或抢占可恢复资源	可能丢失工作，需恢复一致状态

预防最常见的做法是破坏循环等待。为锁建立全局顺序，例如规定 A 的等级小于 B，并要求所有路径只能按等级递增获取；这样可以存在 A 后取 B，却不能再出现 B 后取 A。顺序需要覆盖嵌套函数和错误路径，解锁通常按相反顺序进行。

其他必要条件也可以被针对：只读取的数据无需互斥；一次取得全部资源或失败后释放已有资源，可以避免持续持有并等待；可回滚事务可以允许资源被抢占。通用 mutex 保护任意内存不变量，系统无法在不知道恢复协议的情况下强行夺锁，因此锁排序通常比“抢走 mutex”更可行。

pthread_mutex_trylock() 可以在第二把锁不可用时立即返回，让线程主动释放第一把锁再重试。它避免永久阻塞，却没有自动保证进展；多个线程若同步地获取、失败、释放和重试，可能转成活锁。trylock 是构造协议的工具，不是单独的死锁证明。

避免策略中的银行家算法把“安全状态”定义为存在至少一个完成顺序，使每个参与者都能获得其声明的最大剩余需求、完成并释放资源。设一种资源共有 10 个实例：

进程	已分配	最大需求	还需要
$P_{0}$	4	7	3
$P_{1}$	2	4	2
$P_{2}$	2	9	7

当前可用 2 个实例。 $P_{1}$ 可以先满足并完成，释放其原有 2 个后可用量变成 4；随后 $P_{0}$ 完成，可用量变成 8；最后 $P_{2}$ 完成，所以 $⟨ P_{1}, P_{0}, P_{2} ⟩$ 是安全序列。

若先把 1 个可用实例分给 $P_{2}$ ，可用量只剩 1，而三个进程的剩余最大需求分别是 3、2、6，没有任何一个能够保证完成。这个状态是不安全的，银行家算法会拒绝分配。不安全不等于当前已经死锁；它表示无法保证所有参与者在未来最大请求下完成。算法要求事先知道最大需求，因此很少用于动态、需求未知的普通 mutex，但适合解释避免策略与安全状态。

检测策略可以周期性检查等待图。Linux 内核的 lockdep 是运行时锁依赖验证器：当某条已执行路径在持有锁类 A 时获取锁类 B，它记录依赖 A $\to$ B；若后续观察到的依赖使锁类图形成可导致阻塞的环，lockdep 报告潜在锁序错误。锁类是遵循同一锁规则的一组实例，例如某结构体每个实例中的同一成员锁。

lockdep 不需要真实 ABBA 交错已经发生，只需组成环的各段锁序分别被执行过；但未运行过的代码路径不会贡献依赖，它也不分析任意用户态资源。它是预先暴露潜在内核锁环的动态验证器，不是死锁发生后自动解锁的恢复机制。

恢复取决于资源是否支持一致回滚。数据库可以选择一个受害事务回滚，释放其记录锁；操作系统可以终止进程，释放由内核生命周期管理的资源。但强制终止一个持有普通用户态 mutex 的线程，可能留下只更新一半的内存不变量。健壮互斥锁(robust mutex)能在持有者死亡后向新持有者返回 EOWNERDEAD，要求应用修复状态；它检测的是持有者死亡，也不能自动修复循环等待。

活锁与饥饿

活锁(livelock)是执行流持续改变状态却没有完成有效工作；饥饿是系统整体持续推进，但某个执行流长期得不到所需资源。

三种活性故障可以并列比较：

故障	线程是否执行	系统是否有有效进展	典型原因
死锁	环内线程通常阻塞	环内没有	循环等待
活锁	持续执行或被唤醒	没有	参与者不断礼让、撤销和同步重试
饥饿	受害线程可能反复等待	其他线程有	不公平选择、持续插队或优先级策略

两个线程用 trylock 获取 A、B 时，可能同时各得一把、同时发现第二把不可用、同时释放，再同时重试。锁的所有者一直变化，CPU 也在执行指令，但业务临界区从未进入。加入带上限的随机或指数退避，可以降低参与者再次同步碰撞的概率；给请求分配唯一顺序或改用阻塞队列，则能从协议上消除对称重试。

饥饿不要求循环。读者优先的读写锁若持续有新读者进入，写者可能永远等不到读者数降为零；不公平 mutex 也可能让刚到达的线程反复越过较早等待者。先进先出(First-In, First-Out, FIFO)等待队列、配额和老化可以改善公平性，但更严格的公平通常增加队列管理和缓存迁移成本。

随机退避只提高活锁结束的概率，不能自动提供严格有限等待。若接口需要可证明的公平或截止期限，就必须把顺序、配额或时间界限写进同步协议，而不是依赖“下一次大概会错开”。

并发缺陷

并发缺陷是由多个执行流的交错、可见顺序或资源依赖违反程序正确性要求而产生的问题。

可以先按安全性与活性分类。安全性要求“坏状态永远不发生”，原子性违规、顺序违规和数据竞争通常属于这一类；活性要求“期望事件最终发生”，死锁、活锁和饥饿属于这一类。一个程序可能同时违反多项，例如数据竞争既破坏数据，又可能使等待循环永不结束。

类型	被违反的假设	示例
原子性违规	一组步骤应当不可被其他操作插入	检查余额与扣款之间释放锁
顺序违规	操作 A 必须先于操作 B	工作线程在配置初始化完成前开始处理请求
数据竞争	冲突访问之间必须有 happens-before	两线程无同步读写同一非原子对象
死锁	等待最终能够完成	持有资源形成闭环
活锁	重试最终会成功	所有参与者同步撤销并重试
饥饿	每个请求者最终获得机会	不公平策略长期跳过同一线程

原子性违规可以在没有数据竞争时发生。假设每次访问 balance 都持有 mutex，但线程先加锁读取余额、解锁执行审批，再重新加锁按旧值扣款；所有内存访问都有 happens-before，数据竞争检测器不会报警，两个线程却可能都基于同一个旧余额批准转账。应把检查与扣款放在同一临界区，或使用带版本验证的事务协议。

顺序违规关注先决关系。例如工作线程只能在配置初始化成功后处理请求，程序就需要用 join、条件变量或 release/acquire 状态发布建立顺序。仅仅因为初始化代码写在源文件前面，或者某次测试中它总是先运行，都不是跨线程顺序保证。

ThreadSanitizer(TSan)是通过编译期插桩和运行时元数据检测数据竞争的工具；它能发现缺少 happens-before 的冲突内存访问，但不知道“余额不能为负”或“初始化必须先完成”这样的业务语义。lockdep 擅长已执行内核路径中的锁依赖，TSan 擅长内存访问关系，设计审查与不变量测试仍要覆盖工具无法推断的竞态条件。

因此，并发调试不能只问“有没有加锁”。需要分别检查共享访问是否有 happens-before、复合操作是否保持原子、前置事件是否建立顺序，以及等待图和重试策略是否保证活性。

小结

概念	说明
死锁条件	互斥、持有并等待、非抢占和循环等待必须同时存在
资源分配图	用请求边和分配边表示执行流与资源的依赖
等待图	单实例资源下去掉资源节点形成的线程等待图
死锁预防	在协议设计中保证至少一个必要条件不能成立
死锁避免	只批准仍能保持安全状态的资源分配
银行家算法	根据最大需求、已分配和可用资源寻找安全序列
死锁检测与恢复	发现等待环后回滚、终止或抢占可恢复资源
lockdep	根据运行时观察到的内核锁类顺序检查潜在依赖环
活锁	参与者持续执行和改变状态，却没有有效进展
饥饿	其他参与者继续推进，而某一请求长期得不到资源
并发缺陷	包括原子性、顺序、数据竞争与活性违规

死锁分析的核心不是记住一个 ABBA 示例，而是把资源协议转换成依赖关系，再分别证明安全性与活性：没有冲突访问不代表没有逻辑竞态，没有等待环也不代表每个线程都能公平完成。

Linux 源码与接口入口：

Runtime locking correctness validator：lock class、依赖边与环检查
kernel/locking/lockdep.c：lockdep 图维护与验证实现
include/linux/lockdep_types.h：锁类与依赖数据结构
pthread_mutex_lock(3p)：mutex 类型、EDEADLK 与 robust 错误语义
pthread_mutexattr_setrobust(3)：owner death 与一致性恢复协议
ThreadSanitizer：数据竞争检测范围与编译器插桩

死锁 ​

死锁条件 ​

资源分配图 ​

死锁处理 ​

活锁与饥饿 ​

并发缺陷 ​

小结 ​

死锁

死锁条件

资源分配图

死锁处理

活锁与饥饿

并发缺陷

小结