死锁（Deadlock）是并发系统中一类经典而且代价高昂的故障：多个进程或线程因相互等待对方持有的资源，而全部陷入永久阻塞。与竞态条件不同，死锁不会破坏数据完整性，但它会让系统"冻结"在某一点，服务完全丧失可用性。本文从 Coffman 四条件出发，遍历经典案例、处理策略、银行家算法，并延伸到 Linux lockdep 等工程实践，帮助你建立对死锁的系统认知。
1. 死锁产生的四个必要条件（Coffman Conditions）
1971 年，Coffman、Elphick 和 Shoshani 归纳出死锁同时满足的四个必要条件。必须强调的是，它们是必要条件而非充分条件：四者同时成立不一定导致死锁，但死锁一旦发生，四者必定全部成立；反过来说，只要打破其中任意一条，死锁就不可能发生。
1.1 互斥条件（Mutual Exclusion）
资源一次只能被一个进程占用。如果资源可被共享（如只读文件），就不会因争夺而发生死锁。
1.2 占有并等待（Hold and Wait）
进程已经持有至少一个资源，同时又提出新的资源请求，并在请求失败时阻塞等待，而不是释放已占有的资源。
1.3 不可抢占（No Preemption）
已分配给进程的资源不能被强制剥夺，只能由持有者显式释放。如果操作系统可以在必要时强制回收资源并重新分配，死锁链就会被打断。
1.4 循环等待（Circular Wait）
存在一个进程集合 {P1, P2, …, Pn}，使得 P1 等待 P2 占有的资源，P2 等待 P3 占有的资源，……，Pn 等待 P1 占有的资源，形成闭环。
理解这四条定律的价值在于：它直接给出了预防和避免死锁的四种切入角度。
2. 经典死锁案例
2.1 双线程双锁（最常见）
线程 A 先拿锁 L1、再拿 L2；线程 B 先拿锁 L2、再拿 L1。两者几乎同时执行时，A 持有 L1 等待 L2，B 持有 L2 等待 L1，死锁形成。
#include <stdio.h>
#include <pthread.h>
pthread_mutex_t lock_a = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t lock_b = PTHREAD_MUTEX_INITIALIZER;
void* thread1(void* arg) {
pthread_mutex_lock(&lock_a);
printf("Thread 1: acquired lock_a\n");
// 刻意引入延迟，提高死锁触发概率
struct timespec ts = {0, 100000000};
nanosleep(&ts, NULL);
pthread_mutex_lock(&lock_b);
printf("Thread 1: acquired lock_b\n");
pthread_mutex_unlock(&lock_b);
pthread_mutex_unlock(&lock_a);
return NULL;
}
void* thread2(void* arg) {
pthread_mutex_lock(&lock_b);
printf("Thread 2: acquired lock_b\n");
struct timespec ts = {0, 100000000};
nanosleep(&ts, NULL);
pthread_mutex_lock(&lock_a);
printf("Thread 2: acquired lock_a\n");
pthread_mutex_unlock(&lock_a);
pthread_mutex_unlock(&lock_b);
return NULL;
}
int main() {
pthread_t t1, t2;
pthread_create(&t1, NULL, thread1, NULL);
pthread_create(&t2, NULL, thread2, NULL);
pthread_join(t1, NULL);
pthread_join(t2, NULL);
return 0;
}
编译运行后，两个线程大概率会卡在各自的第二次 pthread_mutex_lock 调用上，程序永远挂起。
2.2 数据库事务死锁
事务 T1 先更新账户 A，再更新账户 B；事务 T2 先更新账户 B，再更新账户 A。当两段更新操作并发执行时，数据库层面的行锁同样会产生死锁。主流数据库（MySQL、PostgreSQL、SQL Server）的死锁检测器会自动发现这种环并选择牺牲者回滚，释放资源。但牺牲者的事务失败会抛异常，应用层必须做好重试逻辑。
2.3 哲学家就餐问题（Dining Philosophers）
五位哲学家围坐在圆桌旁，每人左右各有一支筷子。哲学家只有同时拿到左右两支筷子才能吃饭。如果五位哲学家同时拿起左手边的筷子，那么每人都在等待右边哲学家的筷子，形成完美的循环等待，所有人一起饿死。这个经典模型深刻揭示了循环等待条件的危害——它在多节点、对称拓扑的系统中尤其危险。
一种简单解法是引入"编号"：给每支筷子编号，哲学家必须按编号从小到大的顺序取筷子。这样循环等待被打破，死锁不可能发生。另一种做法是限制同时就餐的哲学家数量（例如最多四人），利用鸽巢原理保证至少有一位哲学家能拿到两只筷子。
3. 死锁处理策略
操作系统和分布式系统对死锁的处理可归纳为四种策略。
3.1 预防（Prevention）：打破 Coffman 四条件
预防是在系统设计阶段就消除死锁的可能性，核心思路是破坏四条件中的至少一条：
- 打破互斥：让资源可共享。这只适用于少数场景（只读数据），对写操作独占资源无能为力。
- 打破占有并等待：要求进程一次性申请所有资源，申请不到就不执行。这种方式资源利用率极低，现实中很少使用。
- 打破不可抢占：如果进程申请新资源失败，必须释放已持有的全部资源，再重新申请。实现复杂，且可能导致活锁（livelock）和大量回滚开销。
- 打破循环等待：定义全局的资源获取顺序，所有进程严格按顺序申请。这是工程中最常用、最可靠的预防手段。
3.2 避免（Avoidance）：银行家算法
避免策略不限制资源申请方式，而是在每次分配前进行安全性检查，确保系统不会进入不安全状态。最著名的算法是 Dijkstra 于 1965 年提出的银行家算法（Banker’s Algorithm）。
3.3 检测与恢复（Detection & Recovery）
系统不预防也不避免死锁，而是定期或在资源紧张时运行检测算法。一旦发现死锁，通过终止进程或抢占资源来恢复。检测的代价通常较高（图算法），恢复又可能引发数据不一致，因此需要权衡。
3.4 鸵鸟算法（Ostrich Algorithm）
直接忽略死锁问题。这是 Unix/Linux、Windows 等现代操作系统对用户态线程锁的默认态度：死锁是小概率事件，而全面预防和检测带来的性能与复杂度开销不可接受。应用层的死锁由开发者负责。这种"无为而治"的策略看似不负责任，但在工程中非常理性——它把死锁风险从内核推到了更可控的应用层。
4. 银行家算法详解
银行家算法之所以得名，是因为它模拟了银行家的放贷逻辑：银行不会把所有资金贷给任何一个客户，而是保留一部分作为储备，确保即使所有客户同时要求最大额度，银行也不会破产。
4.1 核心数据结构
设有 n 个进程，m 类资源：
Available[m]：当前每类可用资源的数量。Max[n][m]：每个进程对每类资源的最大需求。Allocation[n][m]：每个进程当前已分配的资源数量。Need[n][m]：每个进程还需要的资源数量，Need[i][j] = Max[i][j] - Allocation[i][j]。
4.2 安全性算法
安全性算法判断当前状态是否"安全"，即是否存在一种进程执行顺序，使得每个进程都能顺利完成。
Work = Available
Finish[i] = false for all i
while exists i such that Finish[i] == false and Need[i] <= Work:
Work = Work + Allocation[i]
Finish[i] = true
if all Finish[i] == true:
system is in SAFE state
else:
system is in UNSAFE state
若系统处于安全状态，则必然无死锁；若处于不安全状态，则可能发生死锁（注意是不安全而非一定死锁）。
4.3 资源请求算法
当进程 Pi 请求资源 Request[i] 时，系统按以下步骤处理：
- 若
Request[i] > Need[i]，报错（请求超出声明的最大需求）。 - 若
Request[i] > Available，Pi 必须等待。 - 尝试分配，更新状态：
Available = Available - Request[i]Allocation[i] = Allocation[i] + Request[i]Need[i] = Need[i] - Request[i]
- 运行安全性算法检查新状态是否安全。
- 若安全，正式分配；若不安全，回滚此次尝试，Pi 继续等待。
4.4 一个完整示例
假设系统有 3 类资源 {A, B, C}，总数量为 (10, 5, 7)。当前状态如下：
| 进程 | Allocation | Max | Need |
|---|---|---|---|
| P0 | (0, 1, 0) | (7,5,3) | (7,4,3) |
| P1 | (2, 0, 0) | (3,2,2) | (1,2,2) |
| P2 | (3, 0, 2) | (9,0,2) | (6,0,0) |
| P3 | (2, 1, 1) | (2,2,2) | (0,1,1) |
| P4 | (0, 0, 2) | (4,3,3) | (4,3,1) |
Available = (3, 3, 2)
执行安全性算法：
- 初始
Work = (3, 3, 2) - P1 的 Need (1,2,2) <= Work，可满足。执行后
Work = (5, 3, 2) - P3 的 Need (0,1,1) <= Work，可满足。执行后
Work = (7, 4, 3) - P4 的 Need (4,3,1) <= Work，可满足。执行后
Work = (7, 4, 5) - P0 的 Need (7,4,3) <= Work，可满足。执行后
Work = (7, 5, 5) - P2 的 Need (6,0,0) <= Work，可满足。执行后
Work = (10, 5, 7)
安全序列为 <P1, P3, P4, P0, P2>，系统处于安全状态。
假设 P1 请求 (1, 0, 2)，检查后发现小于 Available (3, 3, 2)，尝试分配后运行安全性算法仍能得到安全序列，因此允许分配。这就是银行家算法的完整决策流程。
4.5 为什么银行家算法只是"理论武器"
尽管银行家算法优雅且正确，现代操作系统几乎不直接使用它，原因有三：
- 需要预先知道最大需求：进程在运行前很难准确预测自己需要多少资源。
- 进程数量动态变化：系统不断创建和销毁进程，静态的 Max 矩阵难以维护。
- 算法复杂度高：每次资源请求都要执行 O(m * n^2) 的安全检查，代价太高。
因此，银行家算法更多是教学工具，而非生产系统方案。
5. 工程中的死锁检测
5.1 资源分配图（Resource Allocation Graph, RAG）
死锁检测最直观的模型是 RAG。图中有两类节点：
- 进程节点（圆形）
- 资源节点（矩形，每个实例用小圆点表示）
两种有向边：
- 分配边：资源实例指向进程，表示该资源已被分配给该进程。
- 请求边：进程指向资源，表示进程正在请求该资源。
关键定理：如果资源分配图中不存在环，则系统一定无死锁；如果存在环，且环中每类资源只有一个实例，则死锁一定存在；如果资源有多个实例，环只是死锁的必要条件，还需进一步分析。
检测算法本质上是图上的环检测，可用深度优先搜索（DFS）实现。
5.2 分布式系统中的 Wound-Wait 与 Wait-Die
在分布式数据库中，锁分布在不同节点，RAG 的全局构建成本极高。基于时间戳（timestamp）的乐观方案被广泛采用：
- Wait-Die（老等少，少杀老）：当老事务请求被少事务持有的锁时，老事务等待（wait）；当少事务请求被老事务持有的锁时，少事务自杀（die）并回滚。老事务永不等待少事务，避免循环。
- Wound-Wait（老抢少，少等老）：当老事务请求被少事务持有的锁时，老事务"伤害"（wound）少事务，迫使其回滚；当少事务请求被老事务持有的锁时，少事务等待。
两种方案都保证时间戳的偏序关系不会形成环，区别在于Wait-Die 中老事务可能饿死，而 Wound-Wait 中事务一旦回滚就会被赋予新时间戳，最终能前进。
6. Linux lockdep：运行时的锁序检测
6.1 什么是 lockdep
lockdep（lock dependency validator）是 Linux 内核中一个强大的静态锁依赖检查器。它不是真正"静态"地分析源码，而是在运行时动态追踪所有锁的获取顺序，构建锁的依赖图，并在发现潜在的死锁循环时即时报警。lockdep 能发现的那种 bug，即使实际运行中千次万次都不会触发死锁，但只要存在锁顺序上的逻辑矛盾，它就能报告出来。
6.2 启用与编译
使用 lockdep 需要在内核编译时开启配置：
CONFIG_DEBUG_KERNEL=y
CONFIG_LOCKDEP=y
CONFIG_LOCK_STAT=y
CONFIG_DEBUG_LOCK_ALLOC=y
在启用 lockdep 的内核上，每次锁操作时都会记录调用栈和锁的依赖关系。对性能有明显影响，因此只用于调试和测试环境。
6.3 触发与读取 lockdep 报告
假设内核代码中存在如下锁顺序冲突：
// 路径 A：先拿 lock_a，再拿 lock_b
mutex_lock(&lock_a);
mutex_lock(&lock_b); // lockdep 记录：a -> b
// 路径 B：先拿 lock_b，再拿 lock_a
mutex_lock(&lock_b);
mutex_lock(&lock_a); // lockdep 记录：b -> a，与 a->b 冲突！
lockdep 会在第二次交叉发生时在 dmesg 中输出报告，核心信息包括：
======================================================
WARNING: possible circular locking dependency detected
------------------------------------------------------
caller/1 is trying to acquire lock:
(&lock_a){+.+.}, at: [<...>] some_function+0x...
but task is already holding lock:
(&lock_b){+.+.}, at: [<...>] another_function+0x...
which lock already depends on the new lock.
报告会完整展示依赖链条的栈回溯，开发者可以直接定位到冲突的两个代码路径。这是调试内核并发问题最强大的工具之一。
7. 死锁预防最佳实践
理论归理论，工程中的死锁预防需要可执行、可审查的规范。
7.1 全局锁排序（Global Lock Ordering）
为系统中所有锁定义一个全序关系（如按内存地址或按业务层次）。任何代码获取多个锁时，必须严格按此顺序。这是预防循环等待最直接的方法。在大型项目中，应有文档或代码注释明确每种锁在层级中的位置。
7.2 锁层级文档
在代码库中维护一个 LOCKING 文件或头文件注释，列出所有锁及其允许的获取顺序。例如 Linux 内核中就有一份详细的锁层级文档，新贡献者在引入新锁时必须说明它插入到层级中的哪个位置。
7.3 带超时与回退的 Try-Lock
不要无限期阻塞等待锁。使用 pthread_mutex_timedlock 或在 Go 中使用 context.WithTimeout 配合 select。如果超时，释放已持有的所有锁，短暂延迟后重试。这打破了"占有并等待"条件，同时避免活锁的一个技巧是引入随机回退（randomized backoff）。
struct timespec ts;
clock_gettime(CLOCK_REALTIME, &ts);
ts.tv_sec += 1; // 1 秒超时
if (pthread_mutex_timedlock(&lock_b, &ts) != 0) {
pthread_mutex_unlock(&lock_a); // 释放已持锁
usleep(rand() % 1000); // 随机回退
goto retry;
}
7.4 避免不必要的嵌套锁
嵌套锁是死锁的温床。审视设计：是否可以用更粗粒度的单一锁替代多锁？是否可以改用无锁数据结构（lock-free data structures）？Channel 通信有时候比共享内存加锁更简洁安全。
7.5 RAII 自动释放
利用语言特性确保锁在作用域结束时自动释放。C++ 的 std::lock_guard/std::unique_lock、Rust 的 MutexGuard、Python 的 with threading.Lock()，都遵循 RAII 原则。这至少能消除"忘记 unlock 导致资源永久持有"这一类问题，虽然不能直接防止循环等待，但能减少死锁的触发面。在 C 语言中，可以用 __attribute__((cleanup)) 或宏包装模拟 RAII。
总结
死锁不是不可战胜的幽灵，而是一类条件明确、机理清晰的并发故障。Coffman 四条件为我们提供了分析框架：互斥、占有并等待、不可抢占、循环等待，缺一不可。从哲学家就餐问题到双线程双锁，死锁的模式重复出现；从银行家算法到 Wound-Wait，理论工具为系统设计提供了安全保证；而 lockdep 和全局锁排序则是落地工程的具体手段。
在实际项目中，你最可能采取的策略是"鸵鸟算法 + 预防"：不追求绝对的形式化安全，而是通过全局锁序、try-lock 超时、RAII 自动释放等手段，把死锁概率压到足够低，并保留诊断和快速修复的能力。记住，死锁的预防成本必须与风险相匹配——过度设计同样是一种工程债务。
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。