死锁：当所有人都在等别人先松手

你在手机上把一笔钱从账户甲转到账户乙，另一个请求恰好在做相反方向的转账。为了防止余额被同时改乱，第一个请求先锁住账户甲，第二个请求先锁住账户乙。接下来，第一个请求还要账户乙的锁，第二个请求还要账户甲的锁。两个请求都很守规矩：拿不到锁就等，拿到的锁在事务结束前也不释放。问题是，谁都等不到“事务结束”那一刻了。

这就是死锁最有体感的样子。系统并没有崩溃，线程也没有执行非法指令；每一把锁单独看都工作正常，可它们拼在一起形成了一条闭合的等待链。链上的参与者都把继续前进的条件交给了别人，而别人也在做同一件事。

两个线程各自占着一把锁，又等待对方释放另一把锁，僵局由此形成。

死锁难查，不是因为它神秘，而是因为它依赖执行时序。同一段程序运行一千次都正常，第一千零一次只要线程切换落在两个 lock() 之间，问题就可能出现。日志里常常只剩下“一直没响应”，真正造成闭环的那几步早已发生。

这一章我们不把死锁当成一串定义来背。先从线程到底在等什么开始，再把等待关系画成图，然后讨论三类选择：事前限制资源请求、分配前检查风险、事后检测并恢复。每一种选择都能解决一部分矛盾，也都会付出利用率、运行开销或恢复成本。

先把“卡住”分清楚

程序不动了，不一定就是死锁。一次正常的锁等待、一个长期得不到调度机会的线程、两个不断互相谦让的线程，在用户眼里都可能表现为“卡住”，但处理方法完全不同。

阻塞、死锁、活锁与饥饿

• 阻塞是线程暂时不能继续，它等待的条件仍有机会被别的线程满足。比如线程甲等线程乙写完文件，线程乙写完后会释放锁，系统仍在取得进展。
• 死锁是一组参与者相互等待，组内没有任何一个参与者能先完成并释放资源。只靠继续等待，状态不会自行改变。
• 活锁里的线程没有睡眠，它们还在反复检查、释放、重试，只是彼此的动作总是同步撞在一起，做了很多事却没有完成任务。
• 饥饿通常没有闭环。某个线程一直排在别人后面，资源每次都被更高优先级或更幸运的线程拿走，于是它迟迟得不到服务，而系统整体仍在向前运行。

判断时可以先问两个问题：系统整体有没有进展？等待关系中有没有闭环？“整体没进展且存在无法自行打破的等待环”才是我们这一章关心的核心死锁。

亲手走一遍两把锁的时序

下面的实验把最关键的四步摊开：线程甲拿到锁 A，线程乙拿到锁 B，随后双方各自请求另一把锁。切换到“统一顺序”后，两个线程都先申请 A，等待链就无法首尾相接。

从资源使用流程看死锁为什么会出现

操作系统面对的资源并不只有互斥锁。文件中的一段记录、数据库行、设备控制权、内存缓冲区、连接池中的连接，都可能在某段时间内被一个执行单元独占。为了讨论方便，我们把进程和线程统称为“任务”，把它们要独占或限量使用的对象统称为“资源”。

请求、使用、释放

一个任务使用可复用资源，通常会经历三个阶段：

1. 请求资源：资源空闲时立即获得；资源不足时进入等待，或者收到“暂不可用”的返回值。
2. 使用资源：任务持有资源并修改受保护的数据。此时贸然收回资源，可能让数据停在半完成状态。
3. 释放资源：任务完成临界区或事务，归还资源，唤醒等待者。

系统需要记录每类资源有多少实例、哪些实例已经分配、每个任务还在等待什么。对于一把互斥锁，实例数就是 1；对于容量为 20 的连接池，同类资源有 20 个实例。实例数会直接影响我们对“图中有环”的判断，后面会看到这一点。

四个必要条件必须同时存在

一个已经陷入死锁的任务集合，会同时满足下面四个条件：

1. 互斥：至少有一种资源不能被相关任务同时使用。
2. 占有并等待：任务一边保留已经拿到的资源，一边等待新的资源。
3. 不可抢占：资源不能在任意时刻被系统安全地夺走，只能由持有者主动释放，或者通过回滚等受控手段恢复。
4. 循环等待：存在任务首尾相接的等待链，最后一个任务又在等待第一个任务持有的资源。

四个条件必须同时成立，少掉其中任何一个，死锁的闭环就无法建立。

这里有个常见误解：程序里允许这四种情况出现，不代表它此刻已经死锁。它只说明死锁有了生长的土壤。真正的死锁还要求某一组具体任务已经落入无法自行打破的循环。反过来说，只要系统设计能稳定破坏其中任意一个条件，死锁就不可能形成。

用图把等待关系摊在桌面上

读并发代码时，人脑很容易在多层函数调用里丢掉“谁拿着什么”。资源分配图的价值就在这里：它把分散在代码中的请求和持有关系压缩成一张有向图。

资源分配图的两类节点与两类边

图中有两类节点：任务节点和资源类型节点。任务指向资源的边叫请求边，表示任务正在等待；资源实例指向任务的边叫分配边，表示这个实例已经交给该任务。

假设线程 T1 持有 R1、请求 R2，线程 T2 持有 R2、请求 R1，路径会形成：

T1 → R2 → T2 → R1 → T1

请求边从线程指向资源，分配边从资源指向线程，图中的有向环揭示了单实例资源下的死锁。

如果每种资源都只有一个实例，资源分配图中出现环就意味着环上的任务已经死锁。因为每个请求只能等唯一的持有者，环上没有“另一个实例稍后归还”这条出口。

如果某类资源有多个实例，结论要谨慎一些。图中有环说明存在风险，但不一定已经死锁。环外的某个任务可能归还同类资源的另一个实例，让环内任务先完成，继而释放更多资源。也就是说，多实例系统不能只看形状，还要把可用数量算进去。

等待图把资源节点折叠掉

当每类资源只有一个实例时，可以把“任务 → 资源 → 持有任务”折叠成“任务 → 持有任务”。如果 T1 等待由 T2 持有的锁，就画一条 T1 → T2。这种图叫等待图。等待图里检测到有向环，就找到了死锁任务集合。

下面可以切换几组等待关系，也可以逐条勾选边。它展示的是单实例锁的当前等待图，因此环在这里可以直接判为死锁。

预防：让等待环根本闭不上

死锁预防的思路很直接：四个必要条件既然缺一不可，就设计一套规则，保证至少破坏其中一个。难点不在“能不能做到”，而在限制会不会比死锁本身更昂贵。

让资源尽量共享

只读数据可以让多个任务并发访问，排队打印也可以通过一个后台服务把“独占打印机”改造成“提交打印任务”。这类改造削弱了互斥条件。但很多临界区就是为了防止同时写入，硬把互斥去掉会带来竞态和数据破坏，因此适用范围有限。

不允许边拿边等

一种强规则是：任务开始前一次性申请全部资源，拿不齐就一把也不给。另一种规则是：申请新资源之前先释放手里已有的资源。它们都能破坏“占有并等待”，却也会让资源过早被占住或让任务反复重做。需求只有运行到一半才知道时，一次性声明也不现实。

允许抢占或回滚

如果请求新资源失败，就回收任务已经拿到的资源，让它稍后从检查点重来。CPU 上下文、可换出的内存页、能依靠日志撤销的数据库事务适合这样做。正在驱动硬件或修改复杂共享结构的临界区通常很难安全抢占，恢复成本可能比等待更高。

给所有锁规定统一顺序

工程里最常用的办法是破坏循环等待。给资源建立一个稳定的全序，所有代码都只能从“小”到“大”申请。假设锁 A 排在锁 B 前面，任何线程要同时拿两把锁，都必须先 A 后 B。这样等待边只会沿顺序向前，不可能绕一圈又回到更小的锁。

给锁规定统一顺序后，线程不能反向获取锁，循环等待因此被从结构上切断。

把开头的相反转账修成统一顺序，可以按账户编号决定加锁顺序：

void transfer(Account *from, Account *to, long amount) {
    Account *first  = from->id < to->id ? from : to;
    Account *second = from->id < to->id ? to   : from;
 
    pthread_mutex_lock(&first->lock);
    pthread_mutex_lock(&second->lock);
 

注意，排序依据必须稳定。如果账户编号在持锁期间会变化，或者不同模块各自发明一套顺序，证明就失效了。回调也要格外小心：你持有锁 A 调用一段外部代码，却不知道它会不会反过来请求更低层的锁，锁顺序就被藏进了调用栈。

避免：这次有资源，也不一定马上给

预防策略提前禁止某类请求，规则简单但可能太保守。死锁避免更灵活：每次分配前先模拟一次，只有分配后仍能保证找到“所有任务都可依次完成”的路径，才真正批准请求。

这套方法要解决一个矛盾：眼前确实还有空闲资源，马上分出去能提高利用率；但分得太痛快，可能让所有任务都只差最后一点资源，谁也无法先完成。避免算法宁可暂时让资源空着，也不走进没有退路的状态。

安全、不安全与已经死锁

安全状态是指至少存在一个任务顺序，使每个任务都能获得剩余所需资源、完成并归还已占资源。这个顺序叫安全序列。安全不要求任务真的按该顺序调度，只要系统保留着这样一条可完成路径即可。

不安全状态表示找不到这种保证。它不等于已经死锁：也许任务实际不会把声明过的最大需求全部用完，所以最后仍能完成。可系统已经无法承诺一定有出口，后续请求可能把风险变成真实死锁。

死锁状态则更进一步，当前请求和持有关系已经形成无法自行打破的等待集合。

银行家算法维护的四组数据

假设有 $n$ 个任务和 $m$ 类资源，系统维护：

• Available[m]：每类资源当前还剩多少实例。
• Max[n][m]：每个任务事先声明的最大需求。
• Allocation[n][m]：每个任务已经拿到多少实例。
• Need[n][m]：每个任务最多还可能需要多少，满足 Need = Max - Allocation。

系统先试着分配资源，只有仍能排出完整安全序列时才批准，否则让请求继续等待。

安全性检查不需要猜测所有排列。它拿一份工作向量 Work = Available，不断寻找某个尚未完成且 Need[i] <= Work 的任务。找到后，就假设该任务获得所需资源并顺利结束，把它原先占用的 Allocation[i] 加回 Work。如果最终所有任务都能被标记完成，说明至少找到了一个安全序列。

用一组数据走完安全序列

系统有三类资源 A、B、C，总量分别为 10、5、7。当前快照如下：

当前 Available = (3, 3, 2)。T1 的剩余需求 (1, 2, 2) 可以满足，假设它完成后，Work 变为 (5, 3, 2)；接着 T3 完成，Work 变为 (7, 4, 3)；再让 T4、T2、T0 依次完成，最后所有资源都回到可用集合。因此 T1 → T3 → T4 → T2 → T0 是一条安全序列。

当某个任务提出 Request[i] 时，系统还要先检查三件事：请求没有超过 Need[i]，请求没有超过当前 Available，临时扣除资源后的状态仍然安全。前两项通过只代表“现在有”，第三项才回答“给完之后还有没有收场路径”。

下面的模拟器既能逐步寻找安全序列，也能比较一个可安全批准的请求和一个“资源够但会进入不安全状态”的请求。

避免算法为什么没有到处使用

银行家算法很漂亮，但它有严格前提：任务要提前给出可信的最大需求；资源实例总量在检查期间要能明确统计；任务拿到剩余资源后会在有限时间内完成并归还。通用应用的资源需求经常由输入和运行路径决定，线程自己都无法预先知道最高会拿几把锁。每次请求都做矩阵安全性检查也会增加开销。

所以它更适合资源种类有限、上限可声明、分配由中心控制的环境。面对普通程序中的互斥锁，统一锁顺序、缩短持锁区间和运行时依赖检查通常更实际。

检测：允许死锁发生，但不能一直装作没看见

有些系统选择不过度限制资源分配，而是维护等待信息，定期检查死锁。数据库常采用这条路线：事务可以自由申请行锁；检测到等待环后，系统选一个事务回滚，让其他事务继续。

单实例资源：直接在等待图里找环

每类资源只有一个实例时，构造等待图后做有向环检测即可。深度优先搜索可以用三种颜色记录“未访问、正在当前路径、已经完成”。搜索遇到指向“正在当前路径”节点的边，就找到了环。实际诊断还会保留线程栈、等待的锁和持有的锁，帮助定位是哪条调用路径建立了反向依赖。

运行时检测通常比事后只看线程状态可靠。一个线程处于 BLOCKED 只说明它在等锁；只有把多个线程的持有与等待关系连起来，才能判断是不是死锁。某些运行时可以直接扫描监视器和可拥有同步器，返回处在等待环中的线程编号。

多实例资源：模拟谁能先完成

多实例检测需要三组数据：Available、Allocation 和当前尚未满足的 Request。算法同样用一个工作向量 Work，寻找 Request[i] <= Work 的任务，假设它完成后把 Allocation[i] 归还。最后仍无法标记完成的任务，就是检测到的死锁集合。

它和银行家安全性检查长得很像，但问题不同：

• 避免算法使用任务的最大剩余需求，问“如果未来走到上限，能不能保证收场”。
• 检测算法使用任务的当前未满足请求，问“以此刻已经发生的等待，谁还能先完成”。

检测频率也是一笔账

每次请求阻塞都立即检测，发现得快，也容易知道是哪次请求闭合了环，但高并发时开销明显。固定周期检测比较便宜，死锁任务却会在周期到来前一直占着资源。更实用的方案会根据近期死锁频率、等待时间或吞吐下降动态调整检测间隔。

恢复：打破环之后，数据还得是完整的

检测到死锁只回答“谁出不来了”。系统还要主动改变状态，让等待环断开。最直接的办法是终止任务，另一类办法是抢占资源并把任务回滚到可重试的位置。

检测到等待环后，系统选择代价合适的受害者回滚，释放资源，让其余任务继续前进。

终止全部，还是一次终止一个

终止环中全部任务一定能打破死锁，处理快，但所有已完成工作都会丢失。一次只终止一个任务，损失可能更小；每终止一个都要重新检测，因为等待图中可能有多个重叠的环。

“杀掉线程”也并不总是安全。线程可能正改写文件、更新共享链表或控制设备。进程退出能让内核回收句柄和内存，却不能自动把应用层数据恢复到一致状态。数据库之所以适合终止事务，是因为日志能撤销未提交修改，锁也会随回滚释放。

选择受害者不是随便挑一个

恢复通常会计算代价，可能考虑：任务优先级、已经运行多久、还要多久完成、持有多少资源、回滚要撤销多少修改、终止后会牵连多少外部工作。选“回滚成本最低”的任务能减少当次损失，但如果每次都选同一个短任务，它可能永远做不完。

解决办法是把历史也计入成本。任务每被选为受害者一次，下次就提高它的保护权重；或者限制连续回滚次数，让系统在吞吐量和公平之间取得平衡。

抢占需要三个配套机制

1. 受害者选择：决定从哪个任务收回哪些资源，使环以尽量低的代价断开。
2. 回滚点：任务失去资源后不能从任意指令继续，要恢复到数据一致、可以重新执行的检查点。
3. 防饥饿：同一任务不能无限次成为受害者，重试次数和等待年龄应影响后续选择。

恢复不是“把一把锁强行设为空闲”这么简单。互斥锁保护的是数据不变量。绕过锁所有者直接交接，往往把一个可见的死锁换成更隐蔽的数据损坏。

活锁与饥饿：线程在动，任务却没走远

为了避免阻塞，有人会把第二次 lock() 改成 trylock()：拿不到就释放第一把锁，然后重试。这样确实不会形成睡眠等待环，但如果两个线程步调完全一致，它们可能同时拿第一把锁、同时尝试第二把、同时失败、同时释放，再同时重来。这就是活锁。

正确使用 pthread_mutex_trylock() 时，返回 0 才表示成功；返回 EBUSY 表示当前没拿到锁。重试策略通常要加入随机抖动或指数退避，让竞争者的节奏错开：

for (unsigned attempt = 0; ; ++attempt) {
    pthread_mutex_lock(&lock_a);
 
    int rc = pthread_mutex_trylock(&lock_b);
    if (rc == 0) {
        /* 同时持有 lock_a 和 lock_b，完成工作 */
        pthread_mutex_unlock(&lock_b);
        pthread_mutex_unlock(&lock_a);
        break;
    }
 
    pthread_mutex_unlock(

退避降低重复碰撞，却不能保证公平。某个线程可能每次醒来都慢一步，于是出现饥饿。需要公平性时，还要使用排队锁、请求编号、年龄提升或明确的调度策略，确保等待足够久的任务最终能获得资源。

把死锁机制落到工程实践里

理解算法之后，真正有效的工作往往发生在设计和观测阶段。

设计阶段缩小“持有并等待”的窗口

临界区里不要做用户交互、网络请求或不可控回调。这些操作会把持锁时间从微秒拉到毫秒甚至秒，也让线程在持锁期间申请更多资源。先准备好不需要锁的数据，进入临界区只做最短的状态更新，再立即释放。

把多把锁封装在同一个模块中，也比让调用者自由组合更容易维护顺序。如果必须跨模块持锁，要把锁层级写进接口契约，而不是只藏在某段注释里。

运行时留下足够证据

出现长等待时，至少要能回答：任务在等哪一个资源，资源当前归谁，持有者又在等什么。线程转储、锁等待时长、事务死锁图和锁依赖检查都围绕这三个问题展开。只有“请求超时”一条日志，通常不足以还原环。

数据库事务要准备重试，但不能盲目重放

数据库选出死锁受害者后会回滚事务，应用收到错误需要重新提交。重试前应短暂停顿并加入随机量，给另一个事务完成的时间。重试还要满足幂等或有去重保护，尤其是事务之外已经发送消息、调用支付或写入外部系统时，不能把整个业务动作无条件执行两遍。

减少数据库死锁的几个朴素做法和线程锁相通：不同事务按相同顺序访问表和行，保持事务短小，不在事务中等待用户操作，只使用业务真正需要的隔离级别。

一张排查路线图

小练习

练习：证明统一锁顺序不会形成环

系统规定每把锁都有唯一序号，任务只能在持有较小序号锁时申请更大序号锁。请说明为什么循环等待不可能形成。

练习：手算一次安全性检查

某系统只有一种资源，共 12 个实例。三个任务的“当前占有 / 最大需求”分别是 T0：5/10，T1：2/4，T2：2/9。当前可用资源为 3。系统是否安全？给出一条安全序列。

练习：选择恢复策略

一个数据库检测到两个事务死锁。事务甲只更新了两行且可以完整回滚，事务乙已经批量更新数万行，回滚时间很长。两者优先级相同，也都没有被反复选中过。你会优先选择谁做受害者？还要提醒应用注意什么？