死锁是怎样形成的
复习
- 生产者与消费者：用互斥和等待通知串起一个完整例子
- 信号量：用计数管理有限资源与线程协作
- 读者与写者：并发读取时如何协调写入与公平性
TL;DR
- 两个线程各持一把锁，又都去等对方手里的锁，就会死锁
- 死锁的四个必要条件：互斥、持有并等待、不可抢占、循环等待
- 这四个条件同时满足，才可能死锁；破坏任一个，就能避免
- 死锁不一定每次出现，取决于时序，因此更隐蔽
正文
并发里最让人头疼的，不是算错，而是大家全停下、谁也不动。这叫死锁（deadlock）。
一个经典的僵局
假设有两把锁 A 和 B，两个线程各自这样写：
线程 1： 线程 2：
lock(A) lock(B)
lock(B) lock(A)
...
如果刚好这样执行：
线程 1：拿到 A
线程 2：拿到 B
线程 1：想要 B —— 但 B 在别人手里，等
线程 2：想要 A —— 但 A 在别人手里，等
于是：线程 1 攥着 A 等 B，线程 2 攥着 B 等 A，谁也不肯先放手。两个线程永远卡在原地，程序就此僵住。这就是死锁。
四个必要条件
死锁的发生，需要同时满足四个条件：
- 互斥：资源同一时刻只能被一个线程占用
- 持有并等待：拿着手里的资源不放，同时去申请别的
- 不可抢占：资源不能被强行夺走，只能由持有者主动释放
- 循环等待：存在一条“你等我、我等你”的环形等待链
上面那个例子，四个条件全占了：A、B 互斥；两个线程都持有并等待；锁不能被抢；等待链形成了环（1 等 2、2 等 1）。
为什么它难缠
关键在于：四个条件同时满足才可能死锁，而且往往还要凑巧的时序。大多数时候，线程 1 先拿完两把锁再轮到线程 2，一切正常；只有刚好交错到那个坏顺序，才会卡死。
于是死锁又成了一个“幽灵问题”：测试时好好的，偶尔才复现一次，还极难定位。
出路在哪
不过，这四个条件也给了我们抓手：只要破坏其中任意一个，死锁就不可能发生。 剩下来的问题就是——怎么破坏、破坏哪一个，代价又有多大。这正是下一章要讨论的。
思考题
死锁的四个必要条件里，哪些是“资源本身的性质”（比如锁天生互斥），哪些是“程序写法造成的”？如果只能改程序，你会先动哪一个？
小结
知识点
- 死锁：互相持有并等待对方资源，导致全员停滞
- 四个必要条件：互斥、持有并等待、不可抢占、循环等待
- 四者同时满足才可能死锁，破坏其一即可避免
- 死锁依赖时序，难以复现
参考资料
- Wikipedia(zh)：死锁：deadlock
- Wikipedia(zh)：死锁的必要条件：四个条件
思考题答案（仅供参考）
“互斥”多半是资源本身的性质——像一把锁，本质就是同一时刻只许一个；“不可抢占”也有很强的硬件/语义色彩，锁通常不能被别人强行夺走。“持有并等待”和“循环等待”则主要是程序写法造成的：如果每个线程都一次把需要的锁全申请好，或者大家都按同一顺序申请，环就凑不出来。所以最容易动手的，是先破坏“循环等待”（比如统一加锁顺序），这也是下一章最推荐的做法。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪