死锁 · 操作系统
两个程序怎么会永远互相等待，卡死在那里？
课程目录为什么需要它
死锁会让一个程序、一个数据库，甚至整个服务冻住，不报错、也不占 CPU：大家都在礼貌地等待。数据库会检测死锁并杀掉其中一个事务；在你自己的代码里，要靠设计来预防。认得出这个模式，能省下好几天的调试。
直觉理解
两个朋友，一支笔、一个本子。Ann 拿着笔，等本子；Ben 拿着本子，等笔。谁都不放手。
画一张等待图：从每个在等待的进程，画一个箭头指向持有它所需资源的进程。死锁就是这张图里的一个环。
死锁需要四个条件同时成立：资源独占、拿着不放还等别的、不能强行拿走、循环等待。打破任何一个就行。常用办法：永远按同一个全局顺序获取锁（先笔后本子），这样就形不成环。
定义
死锁 Deadlock
A set of processes each waiting for a resource held by another in the set, so none can proceed.一组进程中，每个都在等另一个持有的资源，结果谁都无法继续。
锁顺序
A rule that every thread acquires locks in the same fixed order. It removes circular waits.规定所有线程都按同一个固定顺序获取锁。它能消除循环等待。
示例
找出环
动手试试waits[p] 是 p 在等的那个进程。沿着箭头走；回到已经在路径上的进程，就是死锁。
def deadlocked(waits):
for start in waits:
seen = []
p = start
while p in waits:
if p in seen:
return seen[seen.index(p):]
seen.append(p)
p = waits[p]
return None
print(deadlocked({"A": "B", "B": "C", "C": "A"}))
print(deadlocked({"A": "B", "B": "C"}))逐步执行
- L5只要当前进程还在等别人，就继续往下走。
- L6回到了这条路径上已经出现过的进程：有环。
- L12A 等 B，B 等 C，C 等 A。
['A', 'B', 'C'] - L13C 没在等，它会完成并释放其他进程。
None
常见错误
用 sleep 来修
加个延时只是改变了时机，让 bug 藏起来了。锁的顺序还是错的，负载一高死锁就会回来。
拿着锁去调用外部代码
拿着锁去调用未知代码（回调、网络请求），等于邀请它以错误的顺序去拿别的锁。先把锁放掉。
小测验
1. 线程 1 先锁 `accounts` 再锁 `log`。线程 2 先锁 `log` 再锁 `accounts`。最简单的修法是？
查看答案
答案：A
统一的全局顺序让循环等待不可能出现。
2. 这段代码会输出什么？
order = {"pen": 1, "book": 2, "lamp": 3}
wanted = ["lamp", "pen", "book"]
print(sorted(wanted, key=order.get))查看答案
答案：A
把需要的锁按全局排名排序，就得到了获取它们的顺序。
动手练习
3 道练习，分三层：先预测程序的输出，再按新需求改程序，最后从零写一个。代码在浏览器里运行，提交马上判题。
- 预测输出谁在等谁？
准确写出这段程序的输出。
- 改需求给锁排序
lock_plan(needed)返回一个线程获取锁的顺序。现在它按列出的顺序拿锁，可能导致死锁。用RANK里的全局排名，让每个线程都按同样的顺序拿锁。 - 从零写检测死锁
写函数
has_deadlock(holds, wants)。holds把每个进程映射到它持有的资源；wants把每个进程映射到它正在等的资源（或None）。构建「谁在等谁」，有环就返回True。
本课术语
| 术语 | 中文 | 英文定义 |
|---|---|---|
| Deadlock | 死锁 | Processes waiting on each other in a cycle, so none can continue. |
| Wait-for graph | 等待图 | Arrows from each waiting process to the one it waits for. |
| Lock ordering | 锁顺序 | Always taking locks in one fixed order to prevent deadlock. |