怎样处理死锁

复习

• 信号量：用计数管理有限资源与线程协作
• 读者与写者：并发读取时如何协调写入与公平性
• 死锁是怎样形成的：四个必要条件与环形等待

TL;DR

• 对付死锁有四种策略：预防、避免、检测并恢复、直接忽略
• 预防：从设计上破坏某个必要条件，最常用的是“统一加锁顺序”
• 避免：运行时判断，若分配会导致死锁就不分配
• 检测并恢复：允许发生，发现后回滚或强制释放
• 现实中最省事的，往往是“统一加锁顺序 + 忽略极端情况”

正文

　　既然死锁要同时满足四个条件，那“处理死锁”就有了四条不同的思路。

预防：破坏条件

　　预防是最直接的思路：从设计上让四个必要条件之一永远不成立。

• 破坏 互斥：很难，很多资源天生就该独占
• 破坏 持有并等待：要求线程一次申请全部资源，拿不齐就一个都不拿
• 破坏 不可抢占：允许系统强行收回资源（实现复杂，很多场景不适用）
• 破坏 循环等待：给所有锁规定一个全局顺序，谁都按同一顺序加锁

　　第四条最实用。回到上一章的僵局：如果规定“永远先锁 A、再锁 B”，那么两个线程的加锁顺序就一致了，不可能再出现“你拿 A 等我 B、我拿 B 等你 A”的环。统一顺序，环就凑不出来。

避免：运行时躲避

　　避免不改变加锁方式，而是在每次分配资源前先“算一卦”：如果这次分配会让系统进入可能死锁的状态，就暂不分配。

　　最著名的算法叫银行家算法：把资源想象成银行的钱，每个线程预先声明最多需要多少。分配前先检查“假使借出去，还能否保证所有线程最终都能拿到所需”，能才借。

　　它理论上很漂亮，但要求预先知道每个线程的最大需求，现实中很难满足，因此主要用于教学和特殊系统。

检测并恢复

　　干脆不预防，让死锁偶尔发生，但定期检测：检查等待图里有没有环，一旦发现，就采取恢复措施——比如中止某个线程、强行收回它的资源。

　　“允许出错再补救”，代价是要写一套检测和恢复机制，而且中止线程可能丢失工作。

现实怎么选

　　现实系统里，完全杜绝死锁往往代价太高。更常见的组合是：

• 主用预防：统一加锁顺序、缩小锁范围，把循环等待从源头掐掉
• 对少数确实难以避免的场景，选择忽略，靠超时、重启等兜底

　　一句话：预防为主，避免为辅，检测恢复兜底，实在不行就忽略。 到底选哪种，还是那句老话——看你能接受多大的风险和代价。

思考题

　　“统一加锁顺序”为什么能破坏循环等待？如果所有线程都必须按同一顺序拿锁，还可能凑出“你等我、我等你”的环吗？

小结

知识点

• 处理死锁的四种策略：预防、避免、检测恢复、忽略
• 预防：破坏四个必要条件之一
• 统一加锁顺序可破坏循环等待，最实用
• 避免：银行家算法等运行时判断
• 检测恢复：发现环后回滚或中止

参考资料

1. Wikipedia(zh)：死锁预防：处理死锁的方法
2. Wikipedia(zh)：银行家算法：死锁避免
3. Wikipedia(zh)：循环等待：加锁顺序

思考题答案（仅供参考）

　　因为循环等待要求有一条“我持有 X 等 Y、你持有 Y 等 X”的环。如果大家都按同一个全局顺序拿锁，比如都给锁编号、只允许从小到大申请，那么每个线程持有的锁在顺序上都小于它正在等的锁。沿着“等待”这条链一路走，编号只会单调递增，永远回不到起点——环就凑不出来了。既然不存在环，死锁最核心的那个条件被破坏，死锁也就不可能发生。

协议

　　本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

封面图

设计师 | 南国微雪