以下根据附件《第16讲 同步原语III.md》整理生成。

第16讲：同步原语 III 学习指南

本讲讨论的是：同步原语本身可能带来的问题。

前面学习的互斥锁、条件变量、信号量、读写锁、RCU 都是为了让多个线程安全共享资源。但只要线程开始“持有资源”“等待资源”，系统就可能出现新的并发问题：

• 死锁
• 活锁
• 优先级反转

❗ 本节核心结论：
同步原语解决了共享资源竞争的正确性问题，但如果资源申请顺序、等待方式和调度优先级设计不好，就会产生死锁、活锁、优先级反转等问题。

1. 本章知识地图

  flowchart TD
    A[同步原语] --> B[多个线程竞争多个资源]
    B --> C[死锁 Deadlock]
    C --> D[检测与恢复]
    C --> E[死锁预防]
    C --> F[死锁避免]
    
    E --> G[破坏四个必要条件]
    F --> H[银行家算法]
    
    E --> I[trylock 方案]
    I --> J[活锁 Livelock]
    
    A --> K[锁 + 优先级调度]
    K --> L[优先级反转]
    L --> M[优先级继承协议]
  

这张图的主线是：同步原语不是问题的终点，而是并发控制的起点。一旦线程开始持有锁、等待锁，就必须处理死锁、活锁和调度优先级问题。

2. 死锁：线程互相等待，系统无法推进

2.1 死锁是什么？

死锁是指：

一组线程或进程互相等待对方持有的资源，导致所有相关线程都无法继续执行。

典型例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

void proc_A(void) {
    lock(A);
    lock(B);
    // 临界区
    unlock(B);
    unlock(A);
}

void proc_B(void) {
    lock(B);
    lock(A);
    // 临界区
    unlock(A);
    unlock(B);
}

可能发生：

1
2

proc_A 已经拿到锁 A，等待锁 B
proc_B 已经拿到锁 B，等待锁 A

于是：

• A 等 B
• B 等 A
• 两个线程都无法继续执行

这就是死锁。

2.2 哲学家问题中的死锁

哲学家问题中，每个哲学家需要同时拿到左右两支筷子才能吃饭。

如果所有哲学家都执行：

1
2

先拿左手筷子
再等右手筷子

那么可能出现：

• 每个人都拿到了左边筷子
• 每个人都在等待右边筷子
• 右边筷子又被旁边的人拿着
• 所有人都无法吃饭

这就是一个环形等待。

2.3 死锁的四个必要条件

死锁产生必须同时满足四个条件：

❗ 本节核心结论：
死锁的本质不是“等得久”，而是形成了循环等待。解决死锁的核心思路，就是破坏四个必要条件中的至少一个。

3. 死锁检测与恢复

3.1 基本思想

死锁检测与恢复的思路是：

不提前禁止死锁，而是在系统运行中检测死锁；一旦发现死锁，再采取恢复措施。

这是一种“出问题后处理”的方案。

3.2 资源分配图

资源分配图中有两类节点：

有两类边：

例如：

  flowchart LR
    P1[P1] --> O2[O2]
    O2 --> P3[P3]
    P3 --> O3[O3]
    O3 --> P4[P4]
    P4 --> O1[O1]
    O1 --> P1
  

这个环表示：

1
2
3
4
5
6

P1 等 O2
O2 被 P3 持有
P3 等 O3
O3 被 P4 持有
P4 等 O1
O1 被 P1 持有

于是形成循环等待。

3.3 如何恢复？

检测到死锁后，常见恢复方式有三种：

检测与恢复的问题是：恢复成本通常很高。

❗ 本节核心结论：
死锁检测与恢复允许死锁发生，再通过资源分配图找环并处理。但它更像事故处理机制，代价通常较大。

4. 死锁预防：提前破坏死锁条件

死锁预防的核心思想是：

让死锁四个必要条件不可能同时成立。

因为死锁需要四个条件同时满足，所以只要破坏其中一个，就可以避免死锁。

4.1 破坏互斥访问

思路是：

不让多个线程直接竞争资源，而是让代理线程统一执行临界区。

普通锁模式：

1

线程自己进入临界区，直接修改共享资源

代理执行模式：

1
2
3

线程提交请求
代理线程统一执行临界区代码
再把结果返回给对应线程

这种方式可以减少直接竞争，但代价是：

• 程序结构需要大改
• 不是所有临界区都适合代理执行
• 工程适用范围有限

4.2 破坏持有并等待

思路是：

要么一次性拿到所有资源，要么一个都不拿。

典型做法是 trylock()。

1
2
3
4
5
6
7
8
9
10
11
12

while (true) {
    if (trylock(A) == SUCC) {
        if (trylock(B) == SUCC) {
            // 临界区
            unlock(B);
            unlock(A);
            break;
        } else {
            unlock(A);
        }
    }
}

这里的关键是：

• 如果拿到了 A，但拿不到 B，就立刻释放 A。
• 线程不会一直“持有 A 等待 B”。
• 因此破坏了“持有并等待”。

但这个方法可能引出新问题：活锁。

4.3 破坏资源非抢占

思路是：

如果线程等不到资源，系统可以从其他线程那里抢回资源。

但这在普通锁里很难，因为：

• 被抢占的线程可能已经修改了一半共享状态。
• 系统必须能保存、回滚、恢复线程状态。
• 很多临界区操作不可安全回滚。

所以资源抢占更适合某些可以回滚的资源管理场景，不适合简单粗暴地用于所有锁。

4.4 破坏循环等待

这是最常见、最实用的方法。

思路是：

给所有资源编号，所有线程必须按照统一顺序申请资源。

例如规定：

1

A < B < C < D

所有线程必须按：

1

A → B → C → D

这个顺序加锁，不能有人先拿 B 再拿 A。

这样等待关系只能从小编号资源指向大编号资源，无法绕回去形成环。

  flowchart LR
    A[锁 A] --> B[锁 B]
    B --> C[锁 C]
    C --> D[锁 D]
  

只要所有线程都按递增顺序拿锁，就不会出现 D 等 A 这种回边，因此无法形成循环等待。

❗ 本节核心结论：
工程上最常用的死锁预防方法，是统一规定加锁顺序。它通过打破循环等待条件来避免死锁。

5. 死锁避免：银行家算法

5.1 死锁避免是什么？

死锁避免不是固定禁止某种行为，而是在每次资源分配时动态判断：

如果现在把资源分配出去，系统未来是否仍然存在一种安全执行顺序？

如果存在，就允许分配。

如果不存在，就暂时拒绝分配，让线程等待。

5.2 银行家算法的直觉

银行家算法可以类比银行贷款：

银行不能只看：

1

现在有没有钱借给这个客户？

还要看：

1

借出去之后，银行是否仍然有能力让所有客户最终完成项目并还钱？

对应到操作系统：

• 银行的钱 = 系统资源
• 客户 = 线程 / 进程
• 借钱 = 申请资源
• 还钱 = 线程执行完成后释放资源

5.3 银行家算法需要的数据

关键公式：

1

Need = Max - Allocation

5.4 安全性检查流程

银行家算法的安全性检查可以这样理解：

  flowchart TD
    A[创建 Work = Available] --> B[寻找未完成且 Need <= Work 的线程]
    B --> C{找到了吗?}
    C -- 是 --> D[假设该线程执行完成]
    D --> E[释放它的 Allocation 给 Work]
    E --> B
    C -- 否 --> F{所有线程都完成了吗?}
    F -- 是 --> G[安全状态]
    F -- 否 --> H[非安全状态]
  

具体步骤：

1. 令 Work = Available。
2. 找一个还没完成、且 Need <= Work 的线程。
3. 假装它可以执行完成。
4. 执行完成后，它释放已经占有的资源。
5. 更新 Work = Work + Allocation。
6. 重复寻找下一个可完成线程。
7. 如果所有线程都能完成，说明存在安全序列。
8. 如果中途找不到任何可执行线程，说明状态不安全。

5.5 安全状态、非安全状态、死锁状态

这三个概念很容易混淆。

关键区别：

非安全状态不等于已经死锁。

非安全状态只是说明：

• 当前系统无法保证一定能避免死锁。
• 如果继续随意分配资源，可能走向死锁。

❗ 本节核心结论：
银行家算法的核心不是“当前资源够不够”，而是“分配之后系统是否仍然安全”。安全性的判断标准是是否存在安全序列。

6. 活锁：一直在动，但没有进展

6.1 活锁是什么？

活锁是指：

线程没有阻塞，也一直在运行、释放、重试，但系统整体没有实际推进。

它和死锁不同。

死锁是：

1

线程阻塞不动，等待资源

活锁是：

1

线程一直动，但不断互相让步 / 重试，始终无法完成

6.2 trylock 为什么可能导致活锁？

前面说过，trylock() 可以避免“持有并等待”。

但如果两个线程总是同步地执行：

1
2
3
4

拿 A
拿 B 失败
释放 A
重试

另一个线程也同步执行：

1
2
3
4

拿 B
拿 A 失败
释放 B
重试

那么它们虽然没有阻塞，却一直无法进入临界区。

这就是活锁。

6.3 活锁和死锁对比

解决活锁的常见办法是：

• 加入随机退避
• 打破所有线程同时重试的节奏
• 限制重试次数
• 改变资源申请策略

❗ 本节核心结论：
活锁不是“卡住不动”，而是“一直在动但没有推进”。trylock 可以避免死锁，但如果所有线程同步重试，就可能产生活锁。

7. 优先级反转

7.1 优先级反转是什么？

优先级反转是指：

高优先级线程因为等待低优先级线程持有的锁，反而被中优先级线程间接阻塞。

典型场景：

执行过程：

1. P1 获得锁 I。
2. P3 启动，想获得锁 I。
3. 但锁 I 被 P1 持有，所以 P3 阻塞。
4. P2 是中优先级线程，不需要锁 I。
5. 调度器让 P2 抢占 P1。
6. P1 不能运行，就不能释放锁。
7. P3 虽然优先级最高，却一直等不到锁。

结果是：

1

P2 间接阻塞了 P3

这就是优先级反转。

7.2 为什么这不是调度器简单出错？

调度器并不是故意不执行高优先级线程。

真正原因是：

• P3 因为等锁而阻塞。
• P1 才是释放锁的关键线程。
• 但 P1 优先级低，被 P2 抢占。
• 所以 P3 被 P2 间接拖住。

本质上，这是：

锁依赖关系和优先级调度机制发生冲突。

7.3 优先级继承协议

解决思路是：

如果低优先级线程持有了高优先级线程等待的锁，那么低优先级线程临时继承高优先级线程的优先级。

在上面的例子中：

1. P1 持有锁 I。
2. P3 等待锁 I。
3. 系统发现：高优先级 P3 被低优先级 P1 阻塞。
4. P1 临时继承 P3 的高优先级。
5. P1 获得调度机会，尽快执行完临界区。
6. P1 释放锁 I。
7. P3 获得锁并继续执行。
8. P1 恢复原来的低优先级。

  sequenceDiagram
    participant P1 as P1 低优先级
    participant P2 as P2 中优先级
    participant P3 as P3 高优先级
    P1->>P1: 获得锁 I
    P3->>P1: 请求锁 I，发现被 P1 持有
    P3->>P3: 阻塞等待
    P1->>P1: 临时继承 P3 优先级
    P1->>P1: 继续运行并释放锁 I
    P3->>P3: 获得锁 I，继续执行
    P1->>P1: 恢复原优先级
  

❗ 本节核心结论：
优先级反转的本质是：高优先级线程被低优先级持锁线程阻塞，而低优先级线程又被中优先级线程抢占。优先级继承通过临时提高持锁线程优先级来缓解这个问题。

8. 三类问题总对比

9. 死锁处理方式总对比

10. 最容易混淆的点

10.1 死锁不是“等很久”

一个线程等锁很久，不一定是死锁。

死锁强调的是：

1

多个线程形成互相等待闭环

10.2 有环和死锁的关系要看资源实例数

如果每类资源只有一个实例：

1

资源分配图有环 ⇒ 死锁

如果每类资源有多个实例：

1

有环不一定必然死锁，但说明存在风险

10.3 死锁预防和死锁避免不同

10.4 非安全状态不等于死锁状态

非安全状态只是说明：

1

不能保证未来一定不死锁

死锁状态则是：

1

已经无法继续推进

10.5 trylock 避免死锁，但可能活锁

trylock 失败后释放已持有资源，可以避免“持有并等待”。

但如果多个线程总是同步重试，就可能：

1

一直运行，一直失败，一直释放，一直重试

这就是活锁。

10.6 优先级反转不是高优先级真的变低了

高优先级线程并没有被调度器主动降级。

它是因为：

1

等待低优先级线程手里的锁

而低优先级线程又被中优先级线程抢占，导致高优先级线程间接受阻。

11. 本讲一句话总结

同步原语虽然能保证共享资源访问的正确性，但也会带来资源等待关系。死锁来自互相等待闭环，处理方式包括检测恢复、预防和避免；银行家算法通过安全序列判断资源分配是否安全；trylock 可能避免死锁但引出活锁；优先级反转则来自锁依赖和优先级调度的冲突，需要用优先级继承缓解。

12. 自测题

1. 为什么说同步原语解决了共享资源竞争问题，但也可能引入新的问题？
2. 用 proc_A 先拿 A 再拿 B、proc_B 先拿 B 再拿 A 的例子解释死锁如何产生。
3. 死锁的四个必要条件分别是什么？
4. 每个死锁必要条件在“锁”的场景中如何体现？
5. 为什么哲学家问题中“所有人都先拿左手筷子”可能导致死锁？
6. 资源分配图中的线程节点、资源节点、请求边、分配边分别表示什么？
7. 为什么资源分配图中出现环可以帮助判断死锁？
8. 死锁检测与恢复有哪些恢复方式？各自代价是什么？
9. 死锁预防为什么可以理解为“破坏死锁的必要条件”？
10. trylock 为什么能破坏“持有并等待”？
11. trylock 为什么又可能引出活锁？
12. 为什么允许资源抢占时必须考虑回滚和恢复？
13. 为什么统一规定所有线程按资源编号递增申请锁，可以打破循环等待？
14. 什么是安全序列？
15. 为什么存在安全序列就说明系统处于安全状态？
16. 银行家算法中的 Available、Max、Allocation、Need 分别表示什么？
17. 为什么“非安全状态”不等于“已经死锁”？
18. 活锁和死锁的区别是什么？
19. 用一个例子说明优先级反转如何发生。
20. 优先级继承协议为什么能缓解优先级反转？

最终总结

本讲可以压缩成一条主线：

多线程同步不仅要保证共享数据正确，还要保证系统能持续推进。

具体来说：

• ❗ 死锁：线程互相等待资源，形成循环等待闭环。
• ❗ 死锁检测与恢复：允许死锁发生，之后通过检测环、kill 或回滚恢复。
• ❗ 死锁预防：提前破坏死锁四个必要条件之一。
• ❗ 死锁避免：运行时判断资源分配后是否仍存在安全序列。
• ❗ 银行家算法：通过模拟线程完成顺序，判断系统是否安全。
• ❗ 活锁：线程一直运行、释放、重试，但没有实际进展。
• ❗ 优先级反转：高优先级线程被低优先级持锁线程间接阻塞。
• ❗ 优先级继承：让持锁的低优先级线程临时继承高优先级，尽快释放锁。