Lecture 7: 死锁（Deadlock）
Lecture 7: 死锁（Deadlock）
概述
当系统使用多把锁（细粒度锁、模块化设计）时，线程经常需要同时持有多把锁——这引入了死锁风险。本讲定义死锁、给出其四个必要条件，并用”资源-线程图”的环（circularity）直观解释，最后讨论检测（数据库常用）与预防（消除任一必要条件，实践中常用全局锁序）两种对策。
核心概念与系统机制图解
死锁（Deadlock）
- 定义：一组线程全部阻塞，每个线程都在等待另一个线程持有的资源；由于所有线程都阻塞，谁也无法释放资源 → “相互阻塞导致无法进展”。
- 直观解释：两个人都拿着对方要用的钥匙，谁也不肯先放手 → 双双卡死。
经典死锁示例
线程 A: 线程 B:
m1.lock(); m2.lock();
m2.lock(); ← 等待B释放m2 m1.lock(); ← 等待A释放m1
... ...
m2.unlock(); m1.unlock();
m1.unlock(); m2.unlock();
→ A 持有 m1 等 m2, B 持有 m2 等 m1 → 环 → 死锁
死锁的四个必要条件（全部满足才可能死锁）
| # | 条件 | 含义 | 消除途径 | | :— | :— | :— | :— | | 1 | 有限访问（互斥） Mutual Exclusion | 资源不能被共享 | 让线程永不需要等待（资源足够多）——对锁不现实 | | 2 | 不可抢占 No Preemption | 资源一旦给出不能被夺走 | 把资源抢走——对 CPU 可行，对锁不可行 | | 3 | 多重独立请求（持有并等待） Hold & Wait | 线程持有一个资源时再请求另一个 | 一次请求全部资源——难以实现且易过度分配 | | 4 | 循环等待 Circular Wait | 请求-持有图中有环 | 全局锁序：所有线程按同一顺序加锁 ← 最常用 |
资源-线程图（可视化环）
无环(安全) 有环(死锁!)
R1 ◄── T1 R1 ◄── T2
│ │
└──► R2 ◄── T2 R2 ◄── T1
│ │
└──► R3 ◄── T3 └──► R3 ◄── T3
"持有"(owned by) 与 "等待"(waiting for) └──────► R4 ──► T2 ...(闭环)
死锁检测（Detection）
- 确定系统是否死锁，然后终止其中一个线程打破死锁。
- 对操作系统通常不实用，但数据库系统常用：事务可被中止并重试。
死锁预防（Prevention）——重点
- 消除条件 4（循环等待）是最实用的途径：给每把锁分配一个编号（锁的”等级/rank”），所有线程都按递增（或递减）顺序加锁。运行时可校验加锁顺序是否违反。
- 案例：两个进程执行 mv 命令
进程1: mv a/x b/y 需要锁住目录 a 和 b 进程2: mv b/z a/q 需要锁住目录 b 和 a 按"参数顺序加锁" → 进程1锁a等b, 进程2锁b等a → 死锁 按"全局固定顺序"(先锁 a 再锁 b) → 进程2也先锁a, 不会与进程1交叉 → 无死锁
设计洞见
- 死锁是全局设计问题：它打破模块化——需要所有模块就加锁顺序达成一致；修改系统时很容易重新引入死锁。
代码示例与系统调用解说
示例：用”全局锁序”避免死锁（锁等级）
#include <mutex>
#include <stdexcept>
std::mutex m1, m2; // 规定: 永远先锁 m1, 再锁 m2 (lock rank 1 < 2)
void transfer_ab(std::mutex& first, std::mutex& second) {
// 防止调用方以任意顺序传参: 按地址排序, 保证全局一致的加锁顺序
if (&first < &second) { // 先锁地址较小的锁
first.lock();
second.lock();
} else {
second.lock();
first.lock();
}
// ... 转账等临界区操作 ...
second.unlock();
first.unlock();
}
【代码做了什么？】 无论调用者以何种顺序传入两把锁，函数内部都按”地址排序”固定加锁顺序，从结构上消除循环等待。
【系统机制透视】
- 预防死锁的关键不是”不要同时持有多把锁”，而是”所有线程以相同全局顺序获取它们”——这样请求-持有图中不可能出现环。
- 如果两个线程以相反顺序加锁，即使只差一把锁，也可能形成等待环；锁序规则把”环”这种全局属性变成”局部可检查”的属性（每个加锁点只需检查等级单调递增）。
- 现实中（如 Linux 内核）用锁等级 + 静态/动态检查（lockdep）来发现违反锁序的代码路径。
关键要点
- 死锁四条件：互斥、不可抢占、持有并等待、循环等待；全部满足才死锁。
- 最实用的预防手段：全局锁序（所有线程按同一顺序获取锁）。
- 死锁检测（终止线程）在数据库事务中常用，在操作系统中不常用。
- 死锁是全局设计问题，破坏模块化；引入新锁时必须与既有锁序保持一致。
- 死锁不仅限于锁：任何”等待”（内存耗尽、网络消息、分布式系统）都可能形成死锁。
常见陷阱与注意事项
- 加锁顺序不一致：两个线程用不同顺序获取同一组锁 → 最经典的死锁来源。
- 回调/嵌套调用中加锁：A 持锁调用 B，B 又尝试锁 A 持有的锁。
- 多个互斥锁未分层：新代码随意加锁而不检查全局顺序。
- 忙等也能死锁：两个线程互相自旋等待对方释放自旋锁（饥饿与死锁的边界）。
思考题
- 问题：只有三个必要条件而没有循环等待，会死锁吗？
- 答案：不会。循环等待是形成”全体阻塞”的最后一环；没有环，等待图有向无环，总有一个线程能获得所需资源并最终释放。
- 问题：为什么数据库系统偏好”死锁检测+回滚”而非预防？
- 答案：数据库事务的访问模式动态多变，难以预先规定全局锁序；而事务具有可回滚性（undo log），检测到死锁后中止并重试一个事务代价可控，比限制所有事务的加锁模式更灵活。
- 问题：
mv a/x b/y与mv b/z a/q若都按”参数顺序”锁目录会死锁，如何修？- 答案：改为全局固定的目录锁序（例如按目录 i-number 或路径字典序加锁），两个进程都以相同顺序获取目录锁，消除环。