# 第 6 章 同步、锁与死锁
> 同步问题的本质不是"加不加锁"，而是哪些操作不可分割、等待时该自旋还是睡眠、以及死锁为什么防不住。
## 学习目标
读完本章，你应当能够：
1. 用"结果依赖不可控的时序"定义竞态条件（race condition），并验证临界区三条件中哪一条被违反。
2. 推导 CAS 的语义与 ABA 的成因，说明 LL/SC 为何天然抗 ABA，以及 `lock` 前缀在 x86 上锁的是什么。
3. 用"临界区长度 vs 一次挂起唤醒开销"给出自旋锁与互斥锁的判据，说出约 1 μs 分界的来源与三条限制。
4. 说明 ticket lock 与 MCS 队列锁各自消除了哪一部分缓存行争抢，解释单核上自旋锁为什么无意义，以及 RCU 为何能免锁。
5. 写出条件变量的正确模式，说清必须用 `while` 的理由，并指出"丢失唤醒"真正的成因。
6. 完整推导死锁四条件及其"必要而非充分"的含义，逐条给出破坏手段，用银行家算法算安全序列，用等待图判环。
7. 辨析活锁与饥饿、无锁与无等待、优先级反转与优先级继承。
### 前置知识检查
| 你需要知道 | 在哪一节补齐 |
|---|---|
| 缓存层次与延迟量级、MESI 四态与伪共享成因 | 见第 1 章 1.4、1.5 节 |
| 上下文切换的开销构成与量化 | 见第 5 章 5.5 节 |
| 单核/多核与调度器的基本行为 | 见第 5 章 5.1 节 |
| JMM、`volatile`、锁升级（本章只需知道"存在这一层抽象"） | 见第 30 章 30.2 节 |
## 6.1 竞态条件与临界区三条件
**竞态条件（race condition）**：程序的输出依赖于两个或多个控制流（线程、中断处理程序、信号处理器）在同一段共享状态上的**不可控的相对时序**。两个关键词缺一不可：**共享状态**——若两个线程只操作各自的局部变量，时序怎么变结果都不变，这不是竞态；**不可控**——时序由调度器、中断到达时刻与缓存一致性协议共同决定。反过来说，**只要有共享可变状态 + 并发访问且无同步，就存在竞态**，不管这次测试有没有复现；把竞态说成"偶发 bug"是常见错误，其实它是"必然存在的可能性，只是触发概率低"。
```c
/* count++ 为什么不是原子的：它在机器层被拆成"读-改-写"三步，中间任何一处都可被抢占 */
void *worker(void *arg) {
for (long i = 0; i < 1000000; i++) {
count++; /* 等价于 tmp = count; tmp = tmp + 1; count = tmp; 三步 */
}
return NULL;
}
```
两个线程各执行 100 万次，`count` 的最终值可能落在 100 万到 200 万之间**任意一个值**上：不是"总是小于 200 万"，而是"每次运行都可能不同"——这才是"依赖不可控时序"。对临界区（critical section）问题，一个正确解法必须同时满足下表三条。
| 条件 | 严格表述 | 违反了会怎样 | 属于哪类属性 |
|---|---|---|---|
| 互斥（mutual exclusion） | 任何时刻至多一个线程处于临界区内 | 数据被破坏，正确性问题 | 安全性（safety） |
| 进展（progress） | 临界区空闲且有线程想进入时，**必须在有限时间内选定**一个进入者，选择不能无限推迟 | 所有线程都卡在门外，系统停摆 | 活性（liveness） |
| 有限等待（bounded waiting） | 一个线程发出进入请求后，**在它之前允许其他线程进入的次数有上界** | 某线程无限期饥饿 | 活性（liveness） |
> [!IMPORTANT] 进展与有限等待极易混为一谈，但量化对象不同：**进展关心"系统整体还在动"（每次都有人能进），有限等待关心"某一个具体线程能进"**。一个允许"总是让刚到的线程插队"的算法满足进展（系统一直有人进出），却违反有限等待（先来的老线程被无限插队）。后者正是非公平锁的语义。
```text
三条件的失效场景对照（两个线程 T1、T2 争一把锁）
违反互斥 : T1 |----CS----| 两者同时在 CS，数据被破坏
T2 |----CS----|
违反进展 : T1 申请 ─┐
T2 申请 ─┴─▶ 选择器不表态，CS 空着谁都不许进
（活锁：大家都在动，没有进展）
违反有限等待 : T1 申请 ──▶ 一直被后来的 T3、T4、T5… 插队
（系统有进展，T1 被饿死）
```
**非公平互斥锁**（如 Java 默认的 `ReentrantLock`、Linux 的 `mutex`）主动放弃有限等待换吞吐；**ticket lock**（6.3.4）则用取号把有限等待变成 FIFO 保证。
## 6.2 硬件原语：从 CAS 到内存屏障
### 6.2.1 CAS 的语义与 ABA
**比较并交换（compare-and-swap, CAS）** 的语义可以完整写成下面几行，三个细节都是面试追问的落点。
```text
CAS(addr, expected, new) :
old = *addr // 原子地读
if (old == expected) // 原子地比较
*addr = new // 原子地写
return old // 无论成功失败都返回"操作前的值"
```
① **返回旧值而非布尔值**（C11 的 `atomic_compare_exchange_weak` 就是这种形式）：失败时直接拿到当前值，可立刻改 `expected` 再试一次，省掉一次读取。② **弱版本允许虚假失败（spurious failure）**：即使 `*addr == expected` 也可能返回失败，接口因此强制写成循环；`cmpxchg` 风格几乎没有虚假失败，LL/SC 架构上则很常见。③ **成功即写入，失败什么也不做**——CAS 不"部分成功"。
**ABA 问题**：CAS 只比较**值**，不比较**版本**；若某地址的值经历 `A → B → A`，CAS 看到 A 就认为"期间没人动过"，而这是假的。
```text
ABA 在无锁栈上的真实破坏力
初始栈: top ─▶ [A] ─▶ [B] ─▶ [C]
T1: old = top = A ; 读到 next = B ; ⏸ 被抢占
T2: pop A ; pop B ; push A （B 已被回收）
现在 top ─▶ [A] ─▶ [C]
T2: 把 B 的那块内存重新分配出去（例如又压入一个 B'）
T1 恢复: CAS(top, A, B) 成功！因为 top 当前确实等于 A
⟹ 新栈变成 top ─▶ [B]（可能已失效的对象）─▶ ??? ← 结构被撕裂
关键：CAS 成功，但 T1 所基于的"世界状态"已经不存在了。
```
### 6.2.2 LL/SC 与 CAS 的差异：谁更抗 ABA
**加载链接 / 条件存储（load-linked / store-conditional, LL/SC）** 成对使用：`LL(addr)` 读 `*addr`，同时在硬件里对该地址的"监视粒度"打一个独占标记；`SC(addr, new)` 只在标记仍然有效时写入并返回成功，否则不写入并返回失败。任何对该粒度的写入、上下文切换、缓存行丢失都会使标记失效。
| 维度 | CAS | LL/SC |
|---|---|---|
| 语义粒度 | 单条指令一次完成，天然的读-改-写 | 两条指令之间构成一个"事务窗口" |
| ABA 抗性 | **不抗**：只看值是否相等，值绕回来检测不到 | **天然抗**：检测"期间对该地址有没有任何写入"，值绕回来照样发现 |
| 虚假失败 | `cmpxchg` 基本没有 | **常见**：任何对该监视粒度的写入、中断、缓存行迁移都可能导致 SC 失败 |
| 代码约束 | 无 | LL 与 SC 之间不能有复杂操作（不能有嵌套内存操作、函数调用、系统调用） |
| 典型实现 | x86 `cmpxchg` | ARM `LDREX`/`STREX`、RISC-V `LR`/`SC`、PowerPC `lwarx`/`stwcx.` |
> [!WARNING] "LL/SC 更抗 ABA"只说对了一半，另一半是它的代价。**抗 ABA 的来源是"监视标志"覆盖了整个窗口，因此任何对该位置的写入都会让 SC 失败——包括与你的逻辑无关的写入（伪冲突）**，于是 LL/SC 的循环在高竞争下重试次数可能远超 CAS。工程取舍是：CAS 需要额外手段补 ABA 防护，LL/SC 需要接受虚假失败带来的重试放大。
### 6.2.3 `xchg` 与 x86 的 `lock` 前缀
**交换（exchange, `xchg`）** 原子地交换寄存器与内存操作数。x86 有一条特殊规则：**`xchg` 只要带内存操作数就隐式含锁语义，不需要写 `lock` 前缀**，这使它成为实现 TAS 自旋锁最直接的指令。`lock` 前缀的作用随硬件世代变化，必须说清。
```text
lock 前缀的两种实现（按硬件世代）
── 早期（486 及之前）：锁总线 ──
CPU 拉低 LOCK# 信号，独占内存总线整个操作周期
▸ 所有核的所有内存访问都被阻塞，代价与"总线宽度 × 操作周期"成正比
── Pentium Pro 及之后：锁缓存行 ──
操作数已在本核缓存且缓存行处于 Exclusive/Modified ⟹ 不碰总线，缓存内部完成
读-改-写，靠 MESI 保证原子性；缓存行不在本核（Shared/Invalid）⟹ 发 RFO
（read-for-ownership）把该行独占过来再本地完成，只有此时才近似锁总线
▸ 结论：lock 的代价 ≈ 一次缓存行所有权转移，而不是一次总线独占
── 附带语义 ──
lock 前缀同时是一条完整的全屏障（Intel SDM 明确其具有栅栏语义），
所以 lock cmpxchg / lock xadd 之后不需要再补 mfence
```
**原子操作的三个实现层级。** 一个原子操作要三层共同保证，任何一层缺失都会得到错误行为。
| 层级 | 保证什么 | 缺失后的症状 |
|---|---|---|
| 编译器 / 语言层（`std::atomic`、`AtomicInteger`） | 不把操作拆成多条指令、不把值缓存进寄存器、不跨调用重排 | 循环条件被提升到循环外，读到永不变化的旧值 |
| CPU 指令层（`cmpxchg`、LL/SC、`xchg`） | 该操作对目标地址不可分割 | 读-改-写被另一个核插入，丢失更新 |
| 内存屏障层（`mfence`、`dmb`、`fence`） | 操作的**可见顺序**与其他地址的读写顺序 | 值最终会一致，但关键窗口内读到旧的；无锁算法的状态机被撕裂 |
> [!NOTE] 面试官追问的下一层通常是："既然 `lock cmpxchg` 自带全屏障，为什么还需要 `std::atomic_thread_fence`？"答案是：**普通变量的读写不受原子指令保护**。无锁算法里"更新一个指针"和"填充该指针指向的数据"是两件独立的事，缺屏障就会出现"指针已可见、数据还没写完"的发布错误。第 30 章 30.3 节给出这一层在 JMM 中的映射。
## 6.3 自旋锁、队列锁与判据
### 6.3.1 test-and-set 实现自旋锁
```c
/* TAS 自旋锁：用 xchg 抢占 0 → 1 的所有权 */
typedef struct { volatile int locked; } tas_lock_t;
static inline void tas_lock(tas_lock_t *l) {
/* 为什么写成 while(xchg(...)) 而不是先读再 xchg：
读操作不改变状态，从读到 0 到执行 xchg 之间仍可能被别人抢走，
所以"是否拿到锁"必须由原子操作本身来回答，不能由普通读来预判 */
while (__atomic_exchange_n(&l->locked, 1, __ATOMIC_ACQUIRE) != 0) {
/* 空转；真实实现会在这里插 PAUSE（见 6.3.3） */
}
}
static inline void tas_unlock(tas_lock_t *l) {
/* 释放只需"临界区内的写先于 locked=0 可见"，所以普通写 + release 就够，
不必再用一次原子 RMW，省掉一次独占缓存行的开销 */
__atomic_store_n(&l->locked, 0, __ATOMIC_RELEASE);
}
```
成本账：**无竞争时**一次 `xchg` 加一次普通写，约 20 ns 量级；**有竞争时**每个失败者都在反复执行带 `lock` 前缀的 RMW，而 RMW 要求独占缓存行，于是所有自旋者把该缓存行在核间来回"乒乓"，总线流量与重试次数成正比。
### 6.3.2 自旋锁还是互斥锁：以约 1 μs 为分界
**判据**：比较"临界区执行时间 `T_cs`"与"一次挂起加唤醒的完整开销 `T_switch`"。
```text
决策不等式
自旋胜出 : T_cs < T_switch
互斥（睡眠）胜出 : T_cs > T_switch
数字口径（本书全书统一使用）
T_switch ≈ 1 ~ 5 μs
= 陷入内核（约 0.1~1 μs）+ 调度决策与队列操作
+ 两次上下文切换的寄存器/栈/地址空间相关开销（见第 5 章 5.5 节）
⟹ 工程上取分界 ≈ 1 μs：
T_cs 在 100 ns ~ 1 μs 量级 ⟹ 自旋
T_cs 在 10 μs 以上 ⟹ 睡眠
中间地带 ⟹ "先短自旋再挂起"的自适应策略（Linux futex、Java 轻量级锁都走这条路）
```
> [!TIP] 把判据说成"临界区短就自旋"只能算及格，**必须补三个限定**：①自旋线程要真的在另一个核上跑（多核）；②临界区时间要**稳定**——若 P50 是 100 ns 而 P999 是 5 ms，1% 的长尾就贡献了约 `0.001 × 5 ms = 5 μs` 的期望自旋成本，直接吃掉全部收益；③必须有自旋次数上界或让出机制，否则自旋锁等于 CPU 消耗器。
### 6.3.3 单核上自旋锁为什么无意义
在单核（或自旋线程与持有者共享同一个 CPU）上，自旋线程占着 CPU，**持有者拿不到 CPU 就无法释放锁**，自旋只是在等着被调度器切走。这正是内核在单核配置下把 `spin_lock` 退化成"仅关抢占/关中断"的原因——此时它的真实作用不是互斥，而是**关闭抢占以保护 `per-CPU` 数据**。但"单核"在工程上还有第三种形态：**线程数超过核数**，此时即使机器是多核，持有者被换出后自旋者仍可能陪跑整个时间片。
```text
单核上 TAS 自旋锁的完整时间线（T1 持有锁，T2 自旋）
时间 ─────────────────────────────────────────────────────────▶
CPU [T1 进入CS ....] [T1 被抢占] [T2 运行并自旋 ......] [T1 恢复] [释放锁]
▲ ▲
│ │
调度器选中 T2 T2 已烧掉近一个时间片
T2 在这整段时间里执行的指令：全是 xchg，产出为零
```
### 6.3.4 ticket lock：先用"取号"解决公平性
**ticket lock** 用两个计数器和一次 `fetch_add` 把申请顺序固定下来：`lock()` 时 `my = fetch_add(&next_ticket, 1)` 原子取号，然后自旋等待 `now_serving == my`；`unlock()` 时 `fetch_add(&now_serving, 1)` 叫下一个号。结果是严格 FIFO，**有限等待有上界**（最多等"前面已取号的人数"次）。但它解决了**公平性**，没有解决**争抢**：所有等待者自旋读的是**同一个 `now_serving`**，该变量所在的缓存行是共享行；释放时做一次写，按 MESI 协议会让所有核的副本失效（Invalid），于是 N 个核同时发读请求重新拉取——这就是第 1 章 1.5 节所说的缓存行争抢（cache-line ping-pong），只是从"写争抢"变成"读风暴"。争抢没有消失，只是换了位置。
### 6.3.5 MCS / CLH 队列锁：把自旋点分散到各自本地
**MCS 锁（Mellor-Crummey & Scott）** 的核心思想：**每个等待者在自己的、本地缓存着的节点上自旋**，前驱释放时只写后继的节点。
```text
MCS 锁结构：一个原子 tail 指针 + 每个等待者一个栈上节点
tail ─▶ [node3] ─▶ [node2] ─▶ [node1] ─▶ (holder 的节点)
locked=1 locked=1 locked=0
lock(qnode):
qnode->next = NULL ; qnode->locked = 1 // 先把自己标成"未获锁"
pred = xchg(&tail, qnode) // 原子地把 tail 指向自己，拿到前驱
if (pred != NULL) {
pred->next = qnode // 告诉前驱"我排在你后面"
while (qnode->locked) pause; // ★ 自旋在【自己的】节点上
}
unlock():
if (qnode->next == NULL) { // 后继可能还没挂链，需处理这个竞态窗口
if (CAS(&tail, qnode, NULL)) return;
while (qnode->next == NULL) pause;
}
qnode->next->locked = 0 // 只写【后继】的节点，唤醒它
```
为什么它消除了争抢：**每个自旋者的 `qnode->locked` 在它自己的缓存行里**，唯一会写它的是其前驱，于是该行长期处于本核的 Shared/Exclusive、命中 L1；释放时的写只让**一个**核的缓存行失效，其余核完全不受打扰；队列变长时总线流量近似 `O(1)` 而非 ticket lock 的 `O(N)` 突发。**CLH 锁** 是同一思路的另一形态：节点记录前驱状态，自旋读**前驱节点**（通常已被本核缓存），释放时写自己的节点供后继读，第 31 章 31.4 节的 AQS 队列就是它的变体。
> [!IMPORTANT] 队列锁把"争抢"从一个共享变量转移到了一串**私有**变量，因此同时解决了互斥、缓存行争抢与公平性三个问题。这就是"**所有等待者自旋在同一地址**"与"**各自自旋在自己的地址**"之间的数量级差异，也是"如何优化高并发锁"的标准第一答案。
## 6.4 信号量、条件变量与屏障
### 6.4.1 信号量与互斥锁的本质区别
**信号量（semaphore）** 是一个带阻塞能力的整数计数器，只有两个原子操作：**P 操作**（proberen，也叫 `wait`/`down`）执行 `S = S − 1`，若 `S < 0` 则调用者阻塞入等待队列；**V 操作**（verhogen，也叫 `signal`/`up`）执行 `S = S + 1`，若有等待者则唤醒其中一个。
| 维度 | 互斥锁（mutex） | 二元信号量（binary semaphore） | 计数信号量 |
|---|---|---|---|
| 是否有所有者 | **有**：谁加锁谁解锁 | 无 | 无 |
| 能否跨线程 | 不能（释放时校验所有者） | **能**：A 线程 P，B 线程 V | 能 |
| 能否跨进程 | 可以（共享内存中的 pthread mutex） | 可以（POSIX 命名信号量、System V） | 可以 |
| 可重入 | 由实现决定（`ReentrantLock` 可重入） | 不可重入，重入即自锁 | 不适用 |
| 语义重心 | **保护临界区**（互斥） | 两者皆可 | **控制并发度 / 顺序** |
**信号量能实现互斥，但互斥锁不能替代信号量的全部用途**，因为信号量表达的是"资源计数 + 顺序"，不是"所有权"。顺序控制是它最有价值也最容易被忽略的用法。
```c
/* 用信号量把"先 A 后 B"的顺序强制出来，而不是靠 sleep 猜时间 */
sem_t s_ab;
void *thread_a(void *_) {
do_a();
sem_post(&s_ab); /* V：告诉 B "轮到你了"；初值为 0 意味着 B 会先阻塞 */
return NULL;
}
void *thread_b(void *_) {
sem_wait(&s_ab); /* P：A 没发信号就阻塞在这里 */
do_b(); /* 这里的先后关系由计数器保证，与调度顺序无关 */
return NULL;
}
```
二元信号量做互斥与互斥锁的**行为差异**有三点，必须能说出：①无所有权 → 任何线程都能"解锁"，也就无法检测误用；②不可重入 → 同一线程重复 P 会把自己锁死；③无法实现优先级继承等高级特性。工程上"该用 mutex 却用了信号量"的典型症状就是**偶发自死锁**与**无法定位的误释放**。
### 6.4.2 条件变量：为什么必须配对，为什么必须用 while
**条件变量（condition variable）** 只做一件事：让线程在条件不成立时**原子地释放锁并睡眠**，被唤醒后**原子地重新获得锁**。它必须与互斥锁配对，原因有两条，且都是"否则必然出错"级别的：**条件本身是被并发修改的共享状态**（判断"队列是否为空"必须读队列，不加锁就与生产者的入队构成 6.1 节的竞态）；**"检查条件"与"开始等待"必须原子**，否则会出现：消费者检查发现队列空 → 释放锁 → 生产者入队并发信号 → 消费者才去睡眠 → 信号被丢失、消费者永久沉睡。
```c
/* 错误模式：用 if 只检查一次，醒来后径直认为条件成立 */
pthread_mutex_lock(&m);
if (!queue_empty(&q)) { /* ✗ 只检查一次 */
item = queue_pop(&q);
pthread_mutex_unlock(&m);
return item;
}
pthread_cond_wait(&cv, &m); /* ✗ 醒来后没有回到上面重新判断 */
item = queue_pop(&q); /* 队列可能仍是空的 → 取到垃圾/越界 */
pthread_mutex_unlock(&m);
/* 正确模式：while 每次唤醒都重新判断条件 */
pthread_mutex_lock(&m);
while (queue_empty(&q)) { /* 不把"被唤醒"等同于"条件成立" */
pthread_cond_wait(&cv, &m); /* 原子地释放 m 并入等待队列；返回时已重新持有 m */
}
item = queue_pop(&q);
pthread_mutex_unlock(&m);
return item;
```
**必须用 `while` 的两条独立理由**：**虚假唤醒（spurious wakeup）**——POSIX 明确规定 `pthread_cond_wait` 允许在没有线程调用 signal/broadcast 的情况下返回（这是为给实现留自由度），所以把"返回"理解为"条件成立"的代码都是错的；**唤醒后条件可能再次为假**——`broadcast` 唤醒 N 个消费者但队列只有 1 个元素，第一个取走后其余 N−1 个必须重新判断并继续等待，这不属于虚假唤醒，而是"条件被多方竞争修改"。
> [!CAUTION] 一个极常见的错误归因："用 `if` 会造成**丢失唤醒**。"这是错的。**丢失唤醒的根因是"等待没有与条件检查构成原子"**（典型样本是无锁条件下 `if (!cond) wait()`，或先检查条件、再到另一个临界区里等待）——即使把 `if` 换成 `while`，这种结构照样丢信号。`while` 解决的是**虚假唤醒与条件二次变假**这两件事。面试里把这两个概念混答，会被连续追问到答不出来。
### 6.4.3 同步原语速查
| 原语 | 状态 | 等待时行为 | 语义重心 | 典型误用 |
|---|---|---|---|---|
| 自旋锁（spinlock） | 一个标志位（或号） | 忙等，占 CPU | 极短临界区、不可睡眠的上下文 | 临界区里做 I/O 或睡眠 |
| 互斥锁（mutex） | 标志位 + 等待队列 | 挂起，让出 CPU | 保护临界区，有所有权 | 锁内做耗时操作（`T_cs` 巨大） |
| 二元信号量 | 计数器 0/1 | 挂起 | 互斥或"让路" | 当作可重入锁 → 自死锁 |
| 条件变量 | 无状态，必须配锁 | 挂起并重新获取锁 | **条件等待**，不能单独表达互斥 | 用 `if` 检查；signal 时未持锁 |
| 屏障（barrier） | 到达计数 | 挂起直到全员到齐 | 分阶段并行计算的对齐 | 线程数与屏障参与者数不一致 → 挂死 |
| 读写锁 | 读者计数 + 写者标志 | 挂起或自旋 | 读多写少，允许读并发 | 写者饥饿；读者临界区内再申请写锁 |
> [!NOTE] 条件变量不保存任何状态，所以 **signal 时若不持有配对的锁，就可能落在"等待者尚未入队"的窗口里而丢失信号**——这是"必须在持锁状态下修改条件、并在持锁状态下 signal"这条规则的实际来源。追问方向是"`signal` 与 `unlock` 谁先谁后"：先 `unlock` 再 `signal` 通常能减少等待者"醒来却拿不到锁又睡回去"的颠簸，但前提是条件已在本临界区内改好。
### 6.4.4 屏障与 RCU 简介
**屏障（barrier）** 的语义是"到齐才能继续"：每个线程到达后计数加一，最后一个到达者唤醒所有等待者；它的正确性前提是**参与者数量固定**，多一个或少一个都会永久挂死。**RCU（read-copy-update）** 是"读多写极少"场景的免锁方案，它能免锁的原因不是"读操作没有同步"，而是把同步成本**移出了读路径**。
```text
RCU 的三条规则（以链表中删除一个节点为例）
① 发布/替换：写者先构造新版本，再用【单个原子指针赋值】把它发布出去，
读者始终看到"某个完整版本"，绝不会看到半成品（配合 release 屏障完成发布）
② 读侧不加锁：读者进入临界区只需禁用抢占，不做任何原子 RMW，
因此读路径的可扩展性与核数近似无关
③ 延迟释放：写者不能立刻 free 旧节点，必须等所有"在发布之前就已开始
的读者"全部离开临界区（synchronize_rcu 等待宽限期 grace period 结束）
┌── 宽限期 ──────────────────────────────────────────┐
│ 旧读者: [====临界区====] │
│ 旧读者: [====临界区====] │
│ 新读者: [==] [==] [==] │ ← 新读者只会看到新版本
└────────────────────────────────────────────────────┘
▲ 所有旧读者离开后，旧节点才可安全释放
⟹ 读侧零原子操作、零写共享行 ⟹ 无缓存行争抢、无锁等待、无死锁
```
代价必须一起说清：写者要付出"等待宽限期"的延迟与内存回收的复杂性；读者临界区里**不能睡眠**（否则宽限期无限延长）；RCU 适合"读远多于写"且能容忍读到略有滞后的数据（路由表、配置、内核对象引用），不适合需要强一致读写的计数器。
## 6.5 内存屏障的硬件层
**x86-TSO 的弱序在哪里。** x86 的内存模型是 **TSO（total store order）**，它只对一种重排留了口子：**StoreLoad**。原因在硬件——写操作进入**写缓冲（store buffer）** 后即被认为"已提交"，CPU 不等缓存行真正到手就继续执行；读操作可以**越过（bypass）** 自己尚未落地的写，先去读别的地址。
```text
x86-TSO 下的 StoreLoad 重排（为什么 mfence 是 x86 上唯一必需的通用屏障）
线程1 线程2
───────────────────── ─────────────────────
X = 1; Y = 1;
r1 = Y; ← 可能读到 0 r2 = X; ← 可能读到 0
直觉上两个 r 不可能同时为 0（谁先写谁就该被读到），但 TSO 允许：
- 线程1 的 X=1 还躺在【线程1 的写缓冲】里没进缓存，r1 读 Y 直接越过它
- 线程2 同理 ⟹ r1 == 0 && r2 == 0 是合法结果
⟹ TSO 保持的三种顺序：LoadLoad、LoadStore、StoreStore
⟹ TSO 唯一不保持的：StoreLoad
```
| 指令 / 手段 | 约束的顺序 | x86 上是否必需 | 何时用 |
|---|---|---|---|
| `lfence` | 后续指令不得越过它提前执行（序列化指令流） | 很少见于内存排序目的 | 需要"前序指令全部完成后才继续"的场合（历史上的 MMIO、某些推测执行缓解路径） |
| `sfence` | 之前的**写**全部对其他核可见后，后续写才可见（StoreStore） | TSO 已保证，通常不需要 | 主要是弱序存储（`movnt` 非临时写）之后需要排序时 |
| `mfence` | 全屏障：所有更早的**读与写**都先于其后的读与写 | 实现 StoreLoad 时必需 | 需要"我的写已可见"那类握手；也可由 `lock` 前缀指令替代 |
| 编译器屏障（`asm volatile("" ::: "memory")`） | 只阻止**编译器**跨它重排访存 | 与 CPU 无关，任何平台都需要 | 编译器可能把普通变量的读写搬过原子操作时 |
> [!WARNING] 最常见的混淆是把 `lfence` 当"读屏障"、`sfence` 当"写屏障"，再以为二者合起来等于 `mfence`。**在 TSO 上这个等号不成立**：`lfence` 的名字虽来自 Load Fence，它做的却是**指令流序列化**，不是"读操作排序"；缺 StoreLoad 语义时 `sfence` + `lfence` 也替代不了 `mfence`。另一个混淆是"编译器屏障能替代 CPU 屏障"——它只约束编译器，硬件的乱序执行与写缓冲完全不受影响。
## 6.6 死锁：四条件、谱系与算例
### 6.6.1 四条件的完整推导，以及"必要不等价于充分"
**死锁（deadlock）**：一组线程中的每一个都在等待一个只能由组内其他线程释放的资源，且都不主动放弃已持有的资源，于是全体永久阻塞。四条件用"反推"得到：想让死锁发生，**必须**依次凑齐下面四条，缺一条就死不了。
| 条件 | 含义 | 为什么必须是它 |
|---|---|---|
| 互斥（mutual exclusion） | 资源在任一时刻只能被一个线程占用 | 若资源可共享（如只读数据），大家都能拿，无从互相等待 |
| 持有并等待（hold and wait） | 线程持有至少一个资源，同时又去申请新的资源 | 若从不"边拿边要"（要么一次拿全、要么全都不要），不存在等待链 |
| 不可抢占（no preemption） | 资源只能由持有者主动释放，不能被强行夺走 | 若能抢占，系统直接把资源收回来给等待者，链条断裂 |
| 循环等待（circular wait） | 存在线程到资源的等待环：T1 等 R2、R2 被 T2 持有、T2 又在等 R1 | 若等待关系构成无环偏序，必有一个"最大者"不需要等别人，它终将完成 |
> [!IMPORTANT] **四条同时满足是死锁的必要条件，不是充分条件。** 单线程不可能死锁就是最有说服力的反例：它递归申请一把不可重入锁时，形式上"互斥 + 持有并等待 + 不可抢占 + 自己等自己"全都成立，但我们不把它叫死锁——**死锁的严格定义要求"一组控制流互相等待"，环至少需要两个参与者**。 更贴近工程的表述是：**四条件满足只说明"存在一条导致死锁的执行交错"，不说明"每次运行都死锁"**。两个线程各持一把锁再去申请对方那把，只有调度恰好让两者都完成第一个 `lock` 之后才轮到第二个 `lock` 才会死锁；若调度让某一线程连续完成两次加锁，就完全无事。这就是死锁"偶发、压测才复现"的根源——**它是必要条件加一个恰好坏的时序**。
### 6.6.2 死锁处理的四类策略与逐条破坏方法
| 策略 | 做法 | 时机 | 代价 |
|---|---|---|---|
| 预防（prevention） | 静态地破坏四条件中的至少一条 | 设计期 | 牺牲资源利用率或并发度 |
| 避免（avoidance） | 每次分配前判断"分配后系统是否仍处于安全状态" | 每次资源请求 | 需预知最大需求，每次分配都要算，开销高 |
| 检测与恢复（detection & recovery） | 允许死锁发生，周期性找环，找到后中止或回滚 | 运行期 | 需要回滚能力与检测开销 |
| 鸵鸟策略（ostrich） | 假装不会发生，靠重启与超时兜底 | —— | 线上真的死锁时只能重启 |
| 被破坏的条件 | 破坏手段 | 现实中的形态 |
|---|---|---|
| 互斥 | 把资源改成可共享 | 只读副本、MVCC 快照读（见第 22 章）、`ReadWriteLock` 允许读并发 |
| 持有并等待 | 要求**一次性申请全部资源**，申请不到就全都不要 | 统一加锁顺序下的"预取"；代价是利用率低、可能饿死 |
| 不可抢占 | 允许系统强制回收 | 数据库检测到死锁后回滚牺牲者（见第 24 章）；`tryLock(timeout)` 失败则释放已持有的锁并退避重试 |
| 循环等待 | **给资源定全序，一律按序号递增申请** | 固定加锁顺序最实用（如"先锁账户 ID 小的、再锁大的"）；代价是要全局维护序号约定 |
> [!TIP] 工程上绝大多数死锁预防就是"固定加锁顺序 + 短事务 + `tryLock` 超时退避"三条。回答"怎么预防死锁"时先给这三条、再展开四条件，顺序反过来会显得只会背课本。逐条破坏里"破坏互斥"最难（大多数资源本来就不可共享），"破坏循环等待"最便宜，这个取舍要能说出来。
### 6.6.3 避免：银行家算法与安全序列算例
**安全状态（safe state）**：存在一个进程序列，按此序列逐个满足每个进程的最大需求并让其完成，则系统安全；该序列叫**安全序列（safe sequence）**。**不安全状态不等于死锁**，它只表示"系统已经失去了保证不发生死锁的能力"。
```text
银行家算法算例（单一资源类型，共 12 个实例）
进程 已分配 Alloc 最大需求 Max 仍需 Need = Max − Alloc
P1 2 6 4
P2 3 8 5
P3 4 7 3
已分配合计 = 2 + 3 + 4 = 9 ⟹ Available = 12 − 9 = 3
── 判安全：找安全序列 ──
Available = 3：P1 需 4 > 3 跳过；P2 需 5 > 3 跳过；P3 需 3 ≤ 3 ✓
P3 跑完释放 Alloc + Need = 4 + 3 = 7 ⟹ Available = 0 + 7 = 7
Available = 7：P1 需 4 ≤ 7 ✓ 跑完释放 2 + 4 = 6 ⟹ Available = 7 − 4 + 6 = 9
Available = 9：P2 需 5 ≤ 9 ✓
⟹ 安全序列存在：P3 → P1 → P2，当前状态【安全】
── P3 提出新请求 Request = 3（Available 3 → 0）──
只有 P3 的 Need 变成 0 能完成，释放 0 + 7 = 7 ⟹ Available = 7
再检查：P1 需 4 ≤ 7 ✓ ⟹ Available = 9；P2 需 5 ≤ 9 ✓
⟹ 新状态仍安全，【批准 Request = 3】
── 若 P1 改请求 Request = 1（Available 3 → 2）──
所有 Need 都 > 2（P1 剩 3、P2 需 5、P3 需 3）⟹ 找不到任何一个能完成的进程
⟹ 无安全序列 ⟹ 【拒绝】
注意：此时资源明明够用，拒绝的理由是"分配后将进入不安全状态"，
这正是银行家算法与"资源够就给"的朴素做法最关键的区别
```
银行家算法的**边界**要能说清：需要预先知道每个进程的**最大需求**（工程上难以准确预知）；每次分配都要跑一次安全性检查，是 `O(n² × m)` 级别开销；它换来的是"避免死锁"，代价是并发度下降（保守拒绝）。所以它主要出现在教学与少数实时/批处理系统中，不是通用服务的默认策略。
### 6.6.4 检测与恢复：等待图与环检测
**等待图（wait-for graph）**：节点是线程（或进程、事务），若 Ti 正在等待 Tj 持有的资源，则有一条有向边 `Ti → Tj`。
```text
两把锁上的经典死锁 ⟹ 等待图恰好是一条 2-环
资源视角 等待图视角
┌──────────┐ ┌──────────┐
│ 锁 A │◀──持有── T1 │ T1 │
└──────────┘ │ └──────────┘
▲ │等待 │ 等待 B
│ ▼ ▼
等待 A ┌──────────┐ ┌──────────┐
│ │ 锁 B │ │ T2 │
└──── T2 ───┴──────────┘ └──────────┘
▲ │
└────┘ T2 等待 A ⟹ 环
单实例资源：环 ⟺ 死锁（充要）
多实例资源：环只是必要条件，需用"资源分配图可完全化简"来判定
```
检测有两个工程问题：**多实例资源**不能用单纯的环检测，做法是反复找"`Request` 能被当前 `Available` 满足"的进程，假设它完成并释放资源（化简），若最终仍有进程无法化简则存在死锁——这与 6.6.3 的安全序列判定是同一个算法，只是问法相反；**检测频率**是纯粹的成本权衡，太频繁则环检测本身要遍历等待边并加锁保护等待图，太稀疏则系统带着一堆被阻塞的线程白等很久。**恢复**手段按代价排序：中止全部死锁线程 → 逐个中止直到环消失 → 回滚到检查点（需要 `undo` 能力）→ 抢占资源（对有状态资源常常不可行）；牺牲者的选择通常基于"已做的工作量最少""持有资源最少""已回滚次数最少"三条。
> [!NOTE] 通用操作系统的内核通常**不做全局死锁检测**（等待图规模太大、检测频率无法取优），而是靠"不在内核里嵌套持锁 + 固定锁顺序"的设计纪律。真正把检测与恢复做成工业级机制的是数据库：InnoDB 的等待图与牺牲者回滚、`innodb_lock_wait_timeout`（默认 50 s）作为兜底，见第 24 章 24.3 节。这个"OS 不做、DB 做"的对比是很好的加分点。
### 6.6.5 活锁、饥饿与优先级反转
| 概念 | 线程在做什么 | 系统整体有进展吗 | 谁被卡住 |
|---|---|---|---|
| 死锁 | 全部**阻塞**，不消耗 CPU | 无 | 环内全部线程 |
| 活锁（livelock） | 全部**在运行**，不断重试、退避、再重试 | 无（无有效进展） | 全部相关线程 |
| 饥饿（starvation） | 幸运者在推进，受害者反复申请被拒 | **有** | 特定线程（通常是低优先级者） |
判别信号很直接：**`top` 里 CPU 很高但任务毫无进展 → 先怀疑活锁，不是死锁**（死锁的线程处于阻塞状态，不占 CPU）。活锁的典型来源是"**对称的冲突解决策略**"：两个线程检测到冲突后都退避相同时间，于是永远同时重试、同时失败；修法是让退避**随机化**或引入优先级，打破对称性。**优先级反转（priority inversion）**：低优先级线程 L 持有高优先级线程 H 需要的锁，L 被中优先级线程 M 抢占而无法运行，于是 H 被 M "间接压住"。
```text
优先级反转的经典时序（H > M > L）
时刻 L (低) M (中) H (高) 结果
─────────────────────────────────────────────────────────────
t0 持锁 ──▶
t1 申请锁 ──▶ 阻塞 H 等 L
t2 就绪 ──▶ 抢占！ L 被挤下 CPU
t3 长时间运行 ──▶ L 拿不到 CPU
t4 仍在阻塞 ★ H 被 M 无限期延迟
（H 优先级最高，却等最久）
```
**优先级继承（priority inheritance）** 的解法：当 H 阻塞在 L 持有的锁上时，**临时把 L 的优先级提升到 H 的级别**，使 M 无法抢占 L；L 释放锁后优先级回退。变体是**优先级天花板（priority ceiling）**：预先给每个锁设定"可能使用它的最高优先级"，持有者立即提升到天花板，从而在加锁那一刻就避免反转，还能顺带防止死锁。
> [!NOTE] 火星探路者（Mars Pathfinder）是优先级继承最著名的案例：机载实时系统出现看门狗复位重启，最终定位为"低优先级任务持有共享总线的互斥量，被中优先级任务抢占，导致高优先级任务无法在时限内完成"，修法是启用互斥量的优先级继承属性。**引用此案例只讲机制与因果链，不编造任务名、时长、日期等细节。** 追问方向是"优先级继承与天花板各有什么取舍"：继承只在冲突发生时提升、开销小但反转窗口仍存在；天花板提前提升、更安全，但需要静态分析每个锁的优先级上界，且可能造成不必要的提升。
### 6.6.6 无锁与无等待
| 进展保证 | 定义 | 单个线程会被无限延迟吗 | 典型例子 |
|---|---|---|---|
| 阻塞（blocking） | 一个线程的挂起会导致其他线程无法推进 | 会 | 互斥锁保护的临界区 |
| 无锁（lock-free） | **系统整体**始终能推进：每时每刻至少有一个线程能完成操作 | 会（某个线程可能一直重试失败） | CAS 循环、`AtomicInteger.incrementAndGet` |
| 无等待（wait-free） | **每个**线程都能在**有界步数**内完成 | 不会 | RCU 的读侧、`fetch_add`、`LongAdder` 的写（近似） |
> [!WARNING] 把"用了 CAS"说成"无锁"是最常见的错答。**无锁要求的是系统级进展保证，不是"没用锁"这个形式特征**：一个 CAS 循环若靠无限重试等待另一个线程先完成某个不可回退的动作，就既不阻塞也不是无锁。另一个反直觉点是**无等待比无锁强得多**，因此现实中大多数数据结构只能做到无锁。
| ABA 的解法 | 做法 | 代价 / 边界 |
|---|---|---|
| 版本号 / 标签（tagged pointer） | 把"指针 + 单调递增计数器"打包成一次更宽的 CAS（x86-64 用 `cmpxchg16b` 一次比较 128 位） | 需要平台支持双宽度 CAS；版本计数器仍会回绕（只是把窗口拉得极长） |
| LL/SC 风格 | 用"期间无任何写入"的语义替代"值相等"，值绕回来也能检测 | 依赖架构支持；虚假失败带来重试放大 |
| **延迟回收 / 安全内存回收** | 保证"被移除的节点在无人引用之前绝不被复用或释放"：hazard pointer、RCU 宽限期、epoch-based reclamation、或依赖 GC | 需要一套回收协议；这是**最彻底**的解法，因为 **ABA 有害的根因是"节点被释放并在别处复用"**，节点永不复用则 `A→B→A` 不再危险 |
**CAS 循环在高竞争下的退化**：N 个线程同时 CAS 同一个变量，一次只有 1 个成功，其余 N−1 个失败后**重新加载缓存行并重试**；而 RMW 要求独占缓存行，于是每次成功都让其他核的副本失效、缓存行在核间来回迁移，有效吞吐可能随核数上升而**下降**。这是"加锁反而比无锁快"的常见原因，也是第 31 章 31.4 节 AQS 用 CLH 队列把竞争收敛到队首、`LongAdder` 用分段计数打散热点的动机。
## 本章小结
| 关键结论 | 一句话表述 | 常见错误 |
|---|---|---|
| 竞态与三条件 | 输出依赖不可控时序；互斥是安全性，进展看系统、有限等待看个体 | 说成"偶发 bug"；把进展与有限等待混答 |
| CAS 与 LL/SC | CAS 只比值、不抗 ABA；LL/SC 检测"期间无写入"、天然抗 ABA 但会虚假失败 | 只答"LL/SC 更抗 ABA"，漏掉虚假失败与代码约束 |
| `lock` 前缀 | P6 以后锁的是缓存行（经 MESI 取独占权），未命中才退化到锁总线；同时自带全屏障 | 答"lock 就是锁总线"；以为它只保原子性不保顺序 |
| 自旋还是睡眠 | 判据是 `T_cs` 与 `T_switch ≈ 1~5 μs` 的比较，分界约 1 μs | 用固定"锁等待阈值"当普适判据；忘记单核与超配场景 |
| 队列锁的价值 | 把"所有人在同一地址自旋"变成"各自在私有节点自旋"，消除缓存行争抢 | 以为 ticket lock 已解决争抢（它只解决公平性） |
| 信号量 vs 互斥锁 | 信号量无所有权、可跨线程、不可重入；互斥锁有所有权 | 用二元信号量当可重入锁 → 自死锁 |
| 条件变量必须 `while` | 理由是虚假唤醒与"唤醒后条件再次变假"；丢失唤醒的根因是非原子的等待 | 答"用 `if` 会丢失唤醒"，两个概念串味 |
| 屏障的位置 | x86-TSO 唯一弱序是 StoreLoad，通用屏障是 `mfence`；`lfence` 是序列化不是"读排序" | 以为 `sfence + lfence = mfence`；以为编译器屏障能替代 CPU 屏障 |
| 死锁四条件 | 是必要条件而非充分条件；单线程自锁不算死锁 | 背完四条却答不出"为什么不是充分条件"、举不出反例 |
| 活锁 vs 饥饿 | 活锁：所有人在跑，系统零进展；饥饿：系统有进展，特定线程被饿死 | 把活锁当死锁（"CPU 高 + 无进展"可区分） |
## 自测题
**Q1**（辨析）某次运行两个线程各对 `count` 加 100 万次得到 187 万，这能说明"没有竞态条件"吗？给 `count` 加 `volatile` 能解决吗？
答案与解析
不能，而且 187 万本身就是竞态生效的证据：正确结果是 200 万，少的 13 万次更新被覆盖了。竞态的定义是"结果依赖不可控时序"，**不是"结果一定错"**；反过来某次恰好得到 200 万也不能证明不存在竞态，只说明这次调度没在危险窗口里抢占。`volatile` 解决不了：它保证每次访问都真的读写内存、不把值缓存进寄存器、不被编译器优化掉，但**不保证"读-改-写"三步的原子性**，两个线程仍可能读到同一个旧值、各自加一后写回。错在哪：把"竞态"与"必现的错误结果"绑定，或把 `volatile` 当同步原语（第 30 章 30.3 节反复强调的坑）。追问方向是"`volatile` 到底保证什么"，要落到"可见性 + 禁止重排，但不保证原子性"，并用 `AtomicInteger.incrementAndGet`（底层 CAS 循环）作对照。
答案与解析
按均值算 `T_cs ≈ 100 ns` 远小于 `T_switch ≈ 1~5 μs`，纯均值口径下自旋划算；但**自旋的代价与等待时间的分布成正比，而不是与均值成正比**。粗算 1% 概率的 5 ms 长尾：每 1000 次操作里有 1 次是 5 ms，期望自旋成本 ≈ `0.001 × 5 ms = 5 μs`，**已超过 `T_switch` 的上界**，长尾一项就把收益吃光；还没算自旋者占着 CPU 挤占持有者时间片（核数接近线程数时尤甚），可能进一步拉长持有时间形成正反馈。结论：**不应无条件自旋，应用"先短自旋（几百到几千次 `pause`）再挂起"的自适应策略，并先把 5 ms 长尾找出来**——临界区里出现毫秒级停顿通常意味着缺页、I/O、`malloc` 或大对象拷贝，属于应在架构层消除的问题，锁策略补偿不了。错在哪：只用均值回答"临界区短所以自旋"。追问方向是"你怎么知道 5 ms 是什么造成的"——用 `perf` 抓栈、看缺页与 I/O 计数，归类后再定锁策略；P999 重要是因为等待时间对服务时间方差极度敏感（第 3 章 3.5 节的尾延迟放大），长尾会沿调用链串行放大。
答案与解析
两条独立理由。**虚假唤醒（spurious wakeup）**：POSIX 规范明确允许 `pthread_cond_wait` 在没有线程调用 signal/broadcast 的情况下返回，这是为给实现留自由度，所以"返回"不能解释为"条件已成立"。**条件再次为假**：`broadcast` 唤醒 3 个消费者但队列只有 1 个元素，第一个取走后另外两个必须重新判断并继续等待；这不属于虚假唤醒，而是"多个等待者竞争同一条件"的必然结果。而"用 `if` 会丢失唤醒"错在**把两个独立缺陷合并成一个**：丢失唤醒的根因是"检查条件"与"进入等待"没有被锁或没有被原子地串在一起，典型样本是无锁保护的 `if (!cond) wait();`——**这种情况下把 `if` 改成 `while`，信号照样会丢**；`while` 修的是"醒来后条件未必成立"。错在哪：把"虚假唤醒导致判断失效"与"丢失唤醒导致永久阻塞"当成同一件事。追问方向是"signal 应在 unlock 之前还是之后"：必须在持锁状态下修改条件；先 `unlock` 再 `signal` 通常能减少"醒来又拿不到锁再睡回去"的颠簸，但要确认条件已改好且没有路径能在其间改回去。
答案与解析
`Need = Max − Alloc` 分别为 4、5、3；`Alloc` 合计 9 ⟹ `Available = 12 − 9 = 3`。判安全：只有 P3 的 `Need = 3` 可满足，P3 完成释放 `4 + 3 = 7` ⟹ `Available = 7`；P1 需 4 可满足、完成释放 `2 + 4 = 6` ⟹ `Available = 9`；P2 需 5 可满足，故**安全序列 P3 → P1 → P2 存在，当前状态安全**。P1 请求 1：先做前提检查（1 ≤ 4 ✓、1 ≤ 3 ✓）再试探分配，`Available = 2`；此时 P1 剩 3、P2 需 5、P3 需 3，**没有任何进程的 `Need ≤ 2`**，找不到第一个能完成的进程 ⟹ 无安全序列 ⟹ 新状态**不安全**，**拒绝该请求**。"资源够用却拒绝"正是银行家算法的本质：它做的不是"够不够"的即时判断，而是"分配之后还能不能保证所有进程都跑完"的前瞻判断；不安全的当下并没有死锁，只是系统丧失了"保证不死锁"的能力——**不安全 ≠ 死锁**。错在哪：只答"1 ≤ 3 所以批准"，丢掉安全性检查；或把"不安全状态"直接说成"已死锁"。追问方向是工程上为何很少用：需预知 `Max`、每次分配都要跑 `O(n² × m)` 检查、保守拒绝降低并发度。
答案与解析
ticket lock 的所有等待者自旋读**同一个 `now_serving`**，它通常还与 `next_ticket` 同处一个缓存行。问题链条是：①等待者的副本由 MESI 保持为 Shared，纯读自旋不产生总线流量；②持有者 `unlock` 时的写让**所有核**的该行副本失效（Invalid）；③N 个核几乎同时发读请求重新拉取，形成突发流量与缓存行迁移；④每张票的 `fetch_add(&next_ticket)` 本身也是需要独占该行的 RMW。结果是**排队越长、核数越多，每次解锁被放大的流量越大**，吞吐随核数下降。MCS 把每个等待者放到**自己的节点**上（`qnode->locked` 通常在申请者栈上、由本核独占），自旋读的是本核缓存行 ⟹ 自旋期间零总线流量；释放时**只写后继的一个节点** ⟹ 只让一个核的缓存行失效；队列变长时流量近似 `O(1)`，且天然 FIFO，同时解决公平性与争抢。与伪共享的关系：这是**真共享**（大家确实读写同一变量），但硬件事件与伪共享同类——多个核反复竞争同一缓存行；伪共享是"逻辑上不共享但物理同一行"，ticket lock 是"逻辑上也共享且物理同一行"，两者的修法思路一致：**把热点变量按缓存行隔离或分散到各核私有**，这正是第 1 章 1.5 节 padding/`@Contended` 与本章队列锁的共同本质。错在哪：只答"ticket lock 不公平"（它恰恰公平），或答"MCS 用了链表所以快"而不指出**自旋点从共享地址搬到了私有地址**。追问方向是"MCS 在单核上还成立吗"——此时线程不可能真正并行自旋，私有自旋的优势消失，必须改成"释放时直接唤醒后继"（本质是阻塞队列），这正是 Linux futex 与 AQS 都"自旋一小段后转入内核阻塞"的原因（见第 31 章 31.4 节）。
答案与解析
第一句错。四条件是**必要**条件：死锁发生时它们必然成立，但成立不等于死锁必然发生。反例一：单线程递归申请一把不可重入锁，"互斥 + 持有并等待 + 不可抢占 + 自己等自己"形式上都满足，但死锁的严格定义要求一组控制流互相等待，环至少需要两个参与者。反例二（更工程）：两个线程按"T1 先 A 后 B、T2 先 B 后 A"申请锁，只有调度恰好让两者都先拿到第一把、之后才申请第二把时才死锁；若调度让某一线程连续完成两次加锁则完全无事。所以四条件满足只说明**存在一条导致死锁的执行交错**。第二句只在**单实例资源**下成立（环 ⟺ 死锁，充要）；**多实例资源**下环只是必要条件，必须用资源分配图的化简判定：反复找 `Request` 能被当前 `Available` 满足的进程，假设其完成并释放资源，若最终仍有进程无法化简才是死锁；而且"等待关系成环"与"实际互相阻塞"还要落到实例层面——T1 等 R1 的某个实例、T2 等 R2 的某个实例，若被等的实例其实空闲，环并不构成实际阻塞。错在哪：把必要条件当充要条件，把"可能死锁"讲成"必然死锁"；或只记"有环即死锁"而不区分单/多实例资源。追问方向是"既然四条件不充分，预防为什么还按四条件破坏"——破坏任一条就**消除了死锁的可能性**（把"存在坏交错"变成"不存在"），预防针对的是可能性，不是某次必然事件。