第12章：死锁——四骑士的诅咒
元数据卡
| 属性 | 值 |
|---|---|
| 难度等级 | (进阶+) |
| 前置章节 | Ch9 并发原语、Ch11 锁实现与动态存储 |
| 后置章节 | Ch13 无锁编程 |
| 核心语言 | C |
| 差异窗口 | Java (ThreadMXBean 死锁检测) / Python (deadlock_detector) |
| 名言 | "不是在锁中消亡，就是在锁中爆发" — 每个调试过死锁的工程师 |
你在哪
"在多线程的世界里，一个经典的噩梦正在等着你——死锁。四个条件同时满足时，每个线程都在等待别人释放资源，所有人都卡在那里动弹不得。老陈很久以前提过一句：'别让互相等待困住你。'"
你刚花了一整章学会怎么正确加锁、释放锁、选对的锁。你觉得自己无敌了。
现在看看这个场景：
- 线程 A：lock(m1) → lock(m2) → 干活 → unlock(m2) → unlock(m1)
- 线程 B：lock(m2) → lock(m1) → 干活 → unlock(m1) → unlock(m2)
两个线程同时运行。A 拿到 m1，B 拿到 m2。然后 A 等 m2，B 等 m1。
——永远等下去。
欢迎进入死锁世界。你上一章学会的每一个工具，在这里都能反过来把你搞死。
别觉得这场景是编的。MySQL 在 5.7 之前的一个 bug：INSERT ... ON DUPLICATE KEY UPDATE 在特定并发模式下会形成 gap lock 的循环等待。PostgreSQL 的轻量级锁（LWLock）在 9.2 之前有已知的死锁场景，需要管理员手动 pg_cancel_backend。生产环境下的死锁不是如果、而是什么时候的问题。
再看一个经典：Java 的 String.intern() 在早期版本中从永久代搬走时需要获取一个全局锁，多个线程同时 intern 不同字符串就可能形成循环等待。HotSpot JVM 团队花了好几个版本才彻底解决。
死锁不挑语言，不挑平台，不挑你的经验水平。它只挑你不经意间形成的循环。
你的任务
本章分层
- 必读：死锁四大条件（Coffman 条件）的逐条理解；预防策略（锁顺序规范）；哲学家就餐问题与解法
- 选读：gdb 手动检测死锁的方法；lockdep 的环检测原理
- 深水区：银行家算法的数学原理与局限；分布式死锁的概念 本章不会要求你掌握
- 银行家算法的代码实现
- 分布式死锁的等待图（WFG）构建
- Livelock（活锁）与死锁的详细对比
- 徒手复现死锁并感受它
- 掌握死锁四大条件（不满足任何一个都不可能死锁）
- 理解银行家算法的思路和局限
- 区分预防、避免、检测、恢复四种策略
- 学会用 gdb 和 lockdep 抓死锁
- 看哲学家怎么把一顿饭吃到系统崩溃
遭遇战 1：死锁复现——自己写一个来体验
不要读理论。先动手。
// deadlock_demo.c — 跑一下，看它卡在哪里
#include <pthread.h>
#include <stdio.h>
#include <unistd.h>
pthread_mutex_t m1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t m2 = PTHREAD_MUTEX_INITIALIZER;
void *thread_a(void *arg) {
pthread_mutex_lock(&m1);
printf("[A] got m1, sleeping...\n");
usleep(100); // 故意让 B 有机会拿 m2
pthread_mutex_lock(&m2);
printf("[A] got m2, done\n");
pthread_mutex_unlock(&m2);
pthread_mutex_unlock(&m1);
return NULL;
}
void *thread_b(void *arg) {
pthread_mutex_lock(&m2);
printf("[B] got m2, sleeping...\n");
usleep(100);
pthread_mutex_lock(&m1);
printf("[B] got m1, done\n");
pthread_mutex_unlock(&m1);
pthread_mutex_unlock(&m2);
return NULL;
}
int main() {
pthread_t a, b;
pthread_create(&a, NULL, thread_a, NULL);
pthread_create(&b, NULL, thread_b, NULL);
pthread_join(a, NULL); // 僵在这里，永远等不到
pthread_join(b, NULL); // 和你一样
return 0;
}用 gdb 附着看线程栈：
$ gcc -g -o deadlock deadlock_demo.c -lpthread
$ ./deadlock &
$ gdb -p $(pgrep deadlock)
(gdb) info threads
Id Target Id Frame
1 Thread ... __futex_abstimed_wait...
2 Thread ... __lll_lock_wait...
(gdb) thread 1
(gdb) bt
#0 __futex_abstimed_wait ...
#1 ... __pthread_mutex_lock_full ...
#2 thread_a (arg=0x0) at deadlock_demo.c:12 ← 卡在锁 m2
(gdb) thread 2
(gdb) bt
#0 __futex_abstimed_wait ...
#1 ... __pthread_mutex_lock_full ...
#2 thread_b (arg=0x0) at deadlock_demo.c:21 ← 卡在锁 m1获得技能：死锁四大条件（Coffman 条件）
下面四个条件必须同时满足才会死锁。缺一个就破：
- 互斥（Mutual Exclusion）：资源一次只能一个线程用。
- 持有并等待（Hold and Wait）：拿着一个锁，还等另一个锁。
- 不可剥夺（No Preemption）：锁只能持有者主动释放，别人抢不走。
- 循环等待（Circular Wait）：A 等 B、B 等 A（或更长的环）。
看回上面的代码——四个全中。
Java 版使用
jstack：bash`$ jstack <pid>` "Thread-0" #12 prio=5 os_prio=0 tid=... java.lang.Thread.State: BLOCKED at deadlock.WorkerB.run(DeadlockDemo.java:25) - waiting to lock <0x...> (a java.lang.Object) - locked <0x...> (a java.lang.Object) "Thread-1" #13 prio=5 os_prio=0 tid=... java.lang.Thread.State: BLOCKED at deadlock.WorkerA.run(DeadlockDemo.java:15)Java 的
ThreadMXBean.findDeadlockedThreads()甚至能自动检测。
💡 理论旁路：银行家算法是死锁避免的经典教材案例，但在现代操作系统中已不常用（因为需要预先声明最大资源需求——这在现实中很难做到）。以下内容出于理论完整性提供，不作为主线交付要求。
遭遇战 2：资源票算法——一个"能不能分"的数学
Edsger Dijkstra 在 1965 年设计的。思想不复杂：
系统像个地心材料库的管理员。手里有有限的资源票（资源）。每个探险者（线程）告诉管理员它执行任务所需的最大资源量。管理员只在"分配之后仍然能至少满足一个探险者的全部需求"时，才批准出库。
// 极度简化的核心逻辑
#define N 5 // 进程数
#define M 3 // 资源类型数
int available[M]; // 每种资源还剩多少
int max[N][M]; // 每个进程的 max 需求
int allocation[N][M]; // 当前已分配
int need[N][M]; // need[i][j] = max[i][j] - allocation[i][j]
// 安全状态检查（O(n²·m)）
int is_safe() {
int work[M];
memcpy(work, available, sizeof(work));
int finish[N] = {0};
for (int k = 0; k < N; k++) { // 最多 N 轮
int found = 0;
for (int i = 0; i < N; i++) {
if (finish[i]) continue;
int can = 1;
for (int j = 0; j < M; j++) {
if (need[i][j] > work[j]) { can = 0; break; }
}
if (can) {
// 模拟释放
for (int j = 0; j < M; j++) work[j] += allocation[i][j];
finish[i] = 1;
found = 1;
}
}
if (!found) break; // 这一轮谁都没推进，不安全！
}
for (int i = 0; i < N; i++)
if (!finish[i]) return 0; // 有人拿不到足够资源
return 1;
}💡 问题在哪里？
- 每个进程必须预先声明最大需求——现实中多数进程不知道。
- 资源数量必须固定——文件描述符、网络连接是动态的。
- 所以：银行家算法在 OS 领域已边缘化，但在数据库事务（两阶段锁的死锁避免）中仍然活跃。
遭遇战 3：哲学家就餐——一顿饭的悲剧
五个哲学家围坐圆桌。每人两件事：思考（不需要资源）和吃饭（需要两根筷子）。每两人之间放一根筷子。
// dining_philosophers.c — 会死锁的版本
#define N 5
pthread_mutex_t chopsticks[N];
void *philosopher(void *arg) {
int id = *(int*)arg;
int left = id;
int right = (id + 1) % N;
while (1) {
think(id);
pthread_mutex_lock(&chopsticks[left]); // 拿左边
pthread_mutex_lock(&chopsticks[right]); // 拿右边
eat(id);
pthread_mutex_unlock(&chopsticks[left]);
pthread_mutex_unlock(&chopsticks[right]);
}
}5 个人同时拿左边筷子 → 全等右边 → 五个哲学家全部饿死。
获得技能：三大经典解法
解法 A：最多 N-1 个哲学家同时上桌（预防） 加一个"矿道通行灯"信号量，初始值 N-1。保证至少一个人有两根筷子。
解法 B：非对称拿筷子（打破循环等待） 奇数哲学家先左后右，偶数哲学家先右后左。不可能形成环。
解法 C：原子拿两根（避免持有并等待）
cpthread_mutex_lock(&global_mutex); pthread_mutex_lock(&chopsticks[left]); pthread_mutex_lock(&chopsticks[right]); pthread_mutex_unlock(&global_mutex);但这个方法把并行度降成了串行，矫枉过正。
系统程序员附录：以下死锁检测工具面向需要在生产环境中排查死锁问题的系统程序员。日常应用开发者只需要了解“存在这类工具”即可。
系统程序员附录：以下死锁检测工具面向需要在生产环境中排查死锁问题的系统程序员。日常应用开发者只需要了解"存在这类工具"即可。
常见陷阱：死锁检测工具和 lockdep
gdb 手动检测
前面你已经看到了基本用法。来点更狠的：
# 运行时检测所有线程
(gdb) thread apply all bt
# 或者批量查锁状态
(gdb) print m1
(gdb) print m2
# pthread_mutex_t 是 opaque 类型，但 __owner 字段能看到谁持有lockdep —— Linux 内核的死锁自动检测
lockdep 不是工具，是 内核里的一个证明系统。
// lockdep 原理极度简化：
// 记录每个锁的"获取顺序图"
// lock(m1) → lock(m2) 被记作：m1 -> m2 这条边
// 如果后来发现 m2 -> m1（反向边），报 IRRECOVERABLE DEADLOCKlockdep 每次加锁都做 O(n) 的图搜索。每个锁是一个节点；如果新加的边会形成环，它立刻打印一串恐怖的报错信息：
============================================
WARNING: possible circular locking dependency detected
--------------------------------------------
... lock A was acquired at:
... lock B was acquired at:
... lock A is already held while trying lock B!获得技能：锁顺序规范
预防死锁最实际的工程手段——全局锁顺序。
c// 坏：线程内乱序 // 好：全局约定 LOCK_ORDER enum { LOCK_USER_TABLE = 0, LOCK_ORDER_TABLE = 1, LOCK_INVENTORY = 2, LOCK_CACHE = 3 }; // 永远按编号递增加锁 // 人肉锁顺序 + 代码 review + lockdep 自动化 = 防死锁铁三角
🐍 Python 版：
python# threading 标准库本身不检测死锁 # 但你可以用 acquire(blocking=False) + try 模式放弃时机 # 或用 contextlib.ExitStack 保证释放顺序 # 社区有 deadlock_detector 库：定时 dump 线程栈
通关挑战
- 必做：修改死锁复现代码，用"锁顺序"规范修复——把 m1 永远在 m2 前加锁。
- 进阶：实现哲学家就餐的"非对称"解法。验证它不会死锁但可能饥饿（一个哲学家永远抢不到两根筷子）。
- 地狱：在 Linux 内核模块里写一个会死锁的代码，编译加载，看 lockdep 怎么喷你。然后再修复。
- 推理：下面场景会死锁吗？
- T1: lock(A); lock(B); unlock(B); lock(C); unlock(A); unlock(C)
- T2: lock(B); lock(C); unlock(C); unlock(B)
- T3: lock(C); lock(A); unlock(A); unlock(C)
验收标准
| 检查项 | 描述 |
|---|---|
| 能说出四大条件并逐条分析实际死锁场景 | 缺一个就不死锁 |
| 能用 gdb info threads + bt 定位死锁点 | 看等待的锁在哪一行 |
| 理解银行家算法为什么在 OS 中不常用 | 预先声明最大需求不现实 |
| 能写出至少一种哲学家就餐的正确解法 | 非对称 / 通行灯 / 原子取筷 |
| 知道 lockdep 的原理（路径记录 + 环检测） | 不是靠运行时超时 |
常见卡点
| 卡点 | 说明 |
|---|---|
| 为什么四个条件缺一不可？ | 互斥是锁的本质，没有互斥就不需要锁。剥夺是一种中断加锁（pthread_mutex_trylock 可用来打破）。循环等待是最常见的切入点。 |
| 银行家算法过时了为什么还讲？ | 思想影响深远——资源预留、安全状态检查在分布式事务（2PC/3PC）中被继承。 |
| lockdep 怎么做到实时检测？ | 它记录所有观察到的锁获取顺序（不是所有可能的顺序）。如果运行时撞出了冲突路径，就报警。静态分析做不到的，动态运行时能。 |
| 哲学家解法里"通行灯"和信号量是什么关系？ | 通行灯本质上是一个计数信号量，初始值 N-1。P(通行灯) 相当于申请上桌许可。 |
| 死锁检测和死锁避免的区别？ | 检测=允许死锁发生，发现了再恢复。避免=在分配资源时做安全检查，永不进死锁。 |
现在不需要理解
- 死锁恢复的精确回滚机制：检测到死锁后杀掉哪个进程？杀进程后怎么回滚共享状态？这是 DBMS 和 OS 内核的核心话题，在 Vol 4 分布式系统和 Vol 5 操作系统内核中展开。
- Livelock（活锁）：线程没死锁，但一直在让出资源，谁也跑不动。这和死锁很像但完全不同，Ch14 聊 fairness 时涉及。
- 分布式死锁：四台机器各自持有对方需要的锁，没法用单机 lockdep 画出一张图。涉及等待图（WFG）的分布式构建——Vol 4 的领域。
旅人笔记
死锁是这样的：你写一百行代码，跑一千次都没事。第一万次，卡了。你抓耳挠腮三个小时，最后发现一个线程拿了 A 等 B，另一个拿了 B 等 A——你亲手写的，你就是那个把两根绳子打结的人。
死后验尸式的死锁调试是最痛苦的调试。用 lockdep 或者锁顺序规范来预防它，比抓它容易一百倍。
而哲学家那顿饭，它的意义不是那五根筷子——它是一个比喻，告诉你如果系统设计不严谨，结局不是死机就是饿死。
→ 下一站预告
第13章——文件系统与崩溃恢复。
你在多线程世界里学会了锁和死锁，但数据最终要落地到磁盘。如果系统在写文件时突然断电怎么办？文件系统怎么保证数据不坏？日志、写时复制、崩溃恢复——下一章从内存走进磁盘的世界。