死锁、检测与恢复¶

死锁是一组执行流永久等待彼此持有的资源，导致任何成员都无法继续。它不是“程序暂时慢”，也不是单个线程等待外部事件，而是等待关系形成了无法自行打破的闭环。

最小例子¶

线程 A 与 B 需要两把锁：

线程 A：lock(L1) -> lock(L2)
线程 B：lock(L2) -> lock(L1)

若 A 已持有 L1，B 已持有 L2，双方都等待对方释放。因为释放代码位于第二次加锁之后，它们永远到不了释放点。

四个必要条件¶

经典模型中，死锁需要四个条件同时成立：

互斥：资源不可同时共享。
占有并等待：持有部分资源时继续等待其他资源。
不可剥夺：资源不能被系统安全强制收回。
环形等待：等待关系形成环。

破坏任意一个条件都能预防该模型中的死锁。但每种破坏方式都有代价，例如让资源可剥夺可能需要回滚，要求一次申请全部资源则降低利用率。

资源分配图¶

图中有进程节点和资源节点：

进程指向资源表示请求。
资源指向进程表示已分配。

每类资源只有一个实例时，图中存在环意味着死锁。资源有多个实例时，存在环只是可能死锁，必须结合可用数量进一步分析。

对于只包含互斥锁的等待关系，也可构造 wait-for graph：节点是线程，\(A\rightarrow B\) 表示 A 等待 B 持有的锁。环表示死锁候选。

死锁处理的四条路线¶

忽略¶

若死锁极少、预防成本高，系统可能选择不做通用处理，由用户终止程序或重启服务。这不是理论上的解决，而是工程上的概率—成本权衡。

预防¶

通过设计规则破坏必要条件：

资源可共享时取消互斥。
一次申请全部资源，破坏占有并等待。
允许抢占和回滚，破坏不可剥夺。
对资源全局编号并按顺序获取，破坏环形等待。

内核和大型代码库常采用锁层级，并借助动态或静态工具检查反向加锁。

避免¶

每次分配前判断是否仍处于安全状态。安全状态表示存在某种进程完成顺序，使每个进程都能获得剩余最大需求并归还资源。

银行家算法维护：

\[ Need_i=Max_i-Allocation_i. \]

若能反复找到满足 \(Need_i\le Work\) 的进程，把它假想完成并令：

\[ Work\leftarrow Work+Allocation_i, \]

最终所有进程都能完成，则当前状态安全。

局限是系统必须提前知道最大需求，且安全性检查有成本。通用应用通常无法准确声明未来所有资源需求。

检测与恢复¶

系统允许死锁发生，周期性构造等待图或运行检测算法。发现后可以：

终止一个或多个参与者。
回滚事务并释放资源。
若资源可恢复，强制剥夺并重试。

选择受害者需考虑已完成工作、优先级、持有资源和重复失败风险。恢复机制若不公平，可能总牺牲同一任务，形成饥饿。

锁顺序：最常用的工程方法¶

定义全序 \(L_1<L_2<\cdots<L_n\)，任何线程只能按递增顺序获取。若存在环，则沿环每一步锁编号都必须严格增大，最终又回到起点，产生矛盾，因此不可能成环。

实际难点包括：

对象动态创建，如何定义稳定顺序？
回调可能隐藏地获取其他锁。
跨子系统锁层级很难统一。
有时必须反向遍历数据结构。

常见解决方式是按对象地址或唯一 ID 排序、重构为分阶段操作、使用 try-lock 后释放重试，或缩小需要同时持有多个锁的范围。

`try_lock` 是否消除死锁¶

尝试加锁失败就释放已有锁并重试，可以破坏占有并等待，却可能形成活锁：多个线程同步地获取第一把锁、第二把失败、同时释放，再同时重试。

随机退避、排队或不对称规则可降低活锁。即便如此，还需分析是否存在某个线程长期失败的饥饿问题。

死锁、活锁与饥饿¶

现象	是否持续执行	是否取得有用进展	典型原因
死锁	否	否	环形等待
活锁	是	否	相互礼让或同步重试
饥饿	系统其他部分是	某参与者否	不公平调度或竞争

三者都表现为“任务完不成”，但诊断证据不同：死锁常看到稳定等待环，活锁可能有高 CPU 和大量重试，饥饿则有持续获胜者和长期失败者。

条件变量也会形成逻辑死锁¶

死锁不只来自互斥锁。若线程 A 等待状态 X 由 B 设置，而 B 等待状态 Y 由 A 设置，即使每次等待都正确释放互斥锁，逻辑依赖仍然成环。

因此等待图中的“资源”应广义理解为锁、消息、任务完成、队列空间和外部事务，不要只搜索 mutex。

分布式死锁的联系¶

跨进程或跨机器事务也可能形成等待环。不同之处是：

全局等待图分散在多个节点。
消息延迟会让观察结果过时。
节点故障和网络分区难与慢等待区分。
恢复常依赖事务回滚、租约和超时。

超时能打破永久等待，却不能证明不存在死锁；它可能误杀只是较慢的正常操作。

诊断思路¶

确认线程状态是阻塞而非计算繁忙。
收集每个线程等待对象和持有对象。
构造等待图，寻找稳定环。
检查锁顺序和隐藏回调。
检查条件变量、future、队列和 IPC 依赖。
选择最小复现，增加调度扰动重复验证。

只看某个线程栈不够；死锁是关系属性，必须同时看整个等待集合。

权衡¶

粗粒度锁减少锁顺序数量，却增加竞争。
一次申请全部资源避免死锁，却降低资源利用率。
检测允许高利用率，却需要可恢复操作。
超时提高可用性，却可能造成重复工作和级联重试。

数据库事务常选择检测与回滚，因为数据操作有日志支持；不可回滚的设备操作则更倾向严格顺序或集中仲裁。

自测¶

四个必要条件中，锁全局排序破坏哪一个？
有环为什么在多实例资源图中不一定已经死锁？
try_lock 失败后立即重试可能产生什么问题？
安全状态是否表示所有进程可以立刻同时获得最大需求？
为什么超时不是死锁检测的充分证据？

参考思路

全局顺序破坏环形等待。多实例资源可能仍有一个实例被释放，让环中任务继续。同步重试可形成活锁。安全状态只要求存在某个可完成顺序。超时也可能来自正常长延迟，且不能提供等待环关系。