死锁

难度：⭐ | 高频指数：🔥🔥🔥

面试回答

常见问法

• 什么是死锁？死锁的四个必要条件是什么？
• 如何预防死锁？如何避免死锁？
• 银行家算法是什么？
• 工程中怎么避免死锁？
• 死锁检测和恢复怎么做？

回答

死锁是指多个进程（或线程）互相等待对方持有的资源，导致所有相关进程都无法继续执行的状态。

死锁的四个必要条件（缺一不可）：

1. 互斥条件：资源一次只能被一个进程使用
2. 持有并等待：进程持有至少一个资源，同时等待获取其他资源
3. 不可剥夺：已获得的资源不能被强行夺走，只能主动释放
4. 循环等待：存在进程等待环路，A 等 B，B 等 C，C 等 A

处理死锁的四种策略：

• 预防：破坏四个必要条件之一，从设计上杜绝死锁
• 避免：运行时判断是否安全（银行家算法），不安全就不分配
• 检测：允许死锁发生，定期检测并恢复
• 忽略：鸵鸟策略，认为死锁概率极低不处理（很多实际系统的做法）

追问

1. 怎么破坏四个条件？

2. 银行家算法简述？

银行家算法是一种死锁避免算法。每次资源请求时，假设分配后检查系统是否仍处于安全状态（即存在一个安全序列能让所有进程完成）。如果安全就分配，不安全就拒绝。

实际系统很少用银行家算法，因为：

• 需要预先知道每个进程的最大资源需求
• 计算开销大
• 进程数和资源数动态变化

3. 工程中怎么避免死锁？

• 固定加锁顺序：所有线程按相同顺序获取锁
• 使用 try_lock + 超时：获取不到就放弃已有锁，重试
• 减少锁粒度：持锁时间尽量短
• 避免嵌套锁：尽量不要在持有一把锁时去获取另一把
• 使用 std::scoped_lock：C++17 一次性获取多把锁

---

原理展开

1. 死锁的经典例子

进程 A：持有资源 1，请求资源 2
进程 B：持有资源 2，请求资源 1

A → 等待 B 释放资源 2
B → 等待 A 释放资源 1
形成环路，死锁！

对应到代码：

std::mutex m1, m2;

// 线程 1
void thread1() {
    std::lock_guard<std::mutex> lk1(m1);
    std::this_thread::sleep_for(1ms);  // 增加死锁概率
    std::lock_guard<std::mutex> lk2(m2);
}

// 线程 2
void thread2() {
    std::lock_guard<std::mutex> lk2(m2);
    std::this_thread::sleep_for(1ms);
    std::lock_guard<std::mutex> lk1(m1);
}

2. 预防死锁——破坏循环等待

方法：对资源编号，强制按编号从小到大获取

std::mutex m1, m2, m3;  // 编号 1, 2, 3

// 所有线程都按 m1 → m2 → m3 的顺序加锁
void safe_thread() {
    std::lock_guard<std::mutex> lk1(m1);
    std::lock_guard<std::mutex> lk2(m2);
    // 永远不会出现 A 持有 m2 等 m1 的情况
}

实际工程中的排序策略：

• 按对象地址排序
• 按业务 ID 排序
• 按模块层级排序（底层锁先获取）

3. 预防死锁——破坏持有并等待

方法：一次性申请所有需要的资源

std::mutex m1, m2;

void safe() {
    std::scoped_lock lock(m1, m2);  // 一次性获取
    // 业务逻辑
}

std::scoped_lock 内部使用死锁避免算法（类似 try-and-back-off），保证不会因为获取顺序不同而死锁。

4. 预防死锁——破坏不可剥夺

方法：用 try_lock，获取不到就释放已有资源

std::mutex m1, m2;

void safe_with_retry() {
    while (true) {
        m1.lock();
        if (m2.try_lock()) {
            // 成功获取两把锁
            break;
        }
        m1.unlock();  // 释放已有资源，避免死锁
        std::this_thread::yield();  // 让出 CPU
    }
    // 业务逻辑
    m2.unlock();
    m1.unlock();
}

注意：这种方式可能导致活锁（两个线程不断重试但都拿不到）。

5. 银行家算法

核心思想：

系统状态：
- Available[j]：系统当前可用的第 j 类资源数量
- Max[i][j]：进程 i 对第 j 类资源的最大需求
- Allocation[i][j]：进程 i 当前已分配的第 j 类资源
- Need[i][j] = Max[i][j] - Allocation[i][j]

安全性检查：
1. 找一个 Need[i] <= Available 的进程 i
2. 假设它执行完毕，回收资源：Available += Allocation[i]
3. 重复直到所有进程都能完成（安全）或找不到这样的进程（不安全）

面试中不需要写完整代码，能说清思路即可：每次分配前模拟一下，看剩余资源能否让所有进程依次完成。

6. 死锁检测

资源分配图法：

• 节点：进程和资源
• 边：请求边（进程→资源）和分配边（资源→进程）
• 如果图中存在环路，则存在死锁

检测时机：

• 每次资源请求时检测（开销大）
• 定期检测（可能延迟发现）
• CPU 利用率下降时检测

7. 死锁恢复

检测到死锁后的处理方式：

1. 终止进程：杀死环路中的一个或多个进程
2. 资源抢占：强制回收某个进程的资源
3. 回滚：将进程回滚到某个检查点

选择牺牲者的考虑因素：

• 进程优先级
• 已执行时间
• 已使用资源量
• 完成还需要多少资源

8. 工程实践中的死锁处理

实际系统（如数据库）的做法：

MySQL InnoDB 死锁处理：
1. 使用等待图（wait-for graph）检测死锁
2. 检测到死锁后，选择代价最小的事务回滚
3. 被回滚的事务收到错误，由应用层重试

C++ 工程中的最佳实践：

// 1. 固定锁顺序
// 2. 使用 std::scoped_lock
// 3. 缩短临界区
// 4. 使用超时锁

std::timed_mutex m;
if (m.try_lock_for(std::chrono::milliseconds(100))) {
    std::lock_guard<std::timed_mutex> lk(m, std::adopt_lock);
    // 业务逻辑
} else {
    // 超时处理：记录日志、降级、重试
}

---

易错点

• 只会背四个条件，不会说怎么破坏——面试官一定会追问”怎么预防”。
• 混淆”预防”和”避免”——预防是设计时破坏条件，避免是运行时判断安全性。
• 认为银行家算法实际系统都在用——实际很少用，因为需要预知最大需求。
• 忘记活锁——try_lock 重试可能导致活锁，需要加随机退避。
• 说”加锁就会死锁”——单把锁不会死锁（除非递归加锁非递归 mutex），死锁需要多个资源。
• 不知道实际系统怎么处理——数据库用等待图检测+回滚，操作系统大多用鸵鸟策略。

---

记忆技巧

• 四个条件口诀：互持不循（互斥、持有等待、不可剥夺、循环等待）
• 四种策略：防（预防）、避（避免）、检（检测）、忽（忽略）
• 破坏循环等待：编号排序，小号先拿
• 银行家一句话：分配前模拟，看能不能让所有人都完成
• 工程三板斧：锁顺序 + scoped_lock + try_lock 超时

---

面试速答版

死锁是多个进程互相等待对方资源导致都无法继续。四个必要条件：互斥、持有并等待、不可剥夺、循环等待。预防死锁就是破坏其中一个条件，最常用的是破坏循环等待（固定加锁顺序）和破坏持有并等待（一次性获取所有锁，如 std::scoped_lock）。银行家算法是死锁避免策略，每次分配前检查是否安全，但实际系统很少用。工程中最实用的做法是：统一锁顺序、用 scoped_lock 同时获取多锁、try_lock 加超时避免永久等待、缩短持锁时间。数据库用等待图检测死锁并回滚代价最小的事务。