主题
第四章 并发控制：同步、互斥与死锁
1. 并发问题的根源：竞态条件
第二章说过，线程的卖点是共享内存。这一章讲共享的代价。
看一个最小的例子：两个线程都执行 count++，count 初值为 0，直觉上结果应该是 2。但 count++ 在 CPU 上不是一步完成的，它是三条指令：
- 把 count 从内存读进寄存器（读）
- 寄存器加 1（改）
- 把寄存器写回内存（写）
如果线程 A 刚执行完第 1 步，时钟中断来了，切换到线程 B 把三步全做完（count 变 1），再切回 A——A 的寄存器里还是旧值 0，加 1 后写回，count 最终是 1 而不是 2。一次加法凭空丢了。
这种"结果取决于线程恰好怎样交错"的现象叫竞态条件（race condition，白话：谁跑得巧谁说了算，结果像抽奖）。它的可怕之处在于不确定性：一万次运行可能九千九百次正确，专挑演示的时候出错。
根源总结成一句话：共享数据 + 至少一方在写 + 操作不是原子的（原子：要么整个做完、要么完全没做，中间不可能被打断），三者同时成立就会出竞态。所有并发控制手段，本质都是破坏这三条中的某一条。
2. 临界区与四个准则
把"访问共享资源的那段代码"称为临界区（critical section）。上例中 count++ 的三条指令就是临界区。解决竞态的思路是：保证任一时刻至多一个线程在临界区内，这个要求叫互斥。
顺带区分一对高频概念：
- 互斥：多方抢同一资源，谁先谁后无所谓，但不能同时。是一种"间接制约"。
- 同步：多方协作有先后依赖，如"B 必须等 A 产出数据后才能加工"。是一种"直接制约"。
任何一个合格的临界区方案必须满足四个准则：
| 准则 | 白话解释 |
|---|---|
| 空闲让进 | 没人在临界区时，想进的人应能立即进，不许故意空着 |
| 忙则等待 | 有人在临界区时，其他人必须等 |
| 有限等待 | 等待的人在有限时间内必须能进去，不能饿死 |
| 让权等待 | 进不去就应让出 CPU，别占着 CPU 空转干等 |
前两条保证正确性，第三条保证公平性，第四条保证效率（让权等待是"应当"而非"必须"，自旋锁就不满足它，但仍算可用方案）。
3. 互斥的实现层次：从关中断到管程
实现互斥的手段是分层次演进的，每一层都在弥补上一层的缺陷。
| 手段 | 思路 | 局限 |
|---|---|---|
| 关中断 | 进临界区前关闭中断，没人能切走我 | 只对单 CPU 有效；用户程序不能被信任去关中断；关太久系统失聪 |
| 锁（如自旋锁） | 用硬件原子指令（测试并设置）实现"抢钥匙" | 拿不到锁就原地空转，浪费 CPU，违背让权等待 |
| 信号量 | 拿不到就睡眠，被释放时唤醒；计数能力还可表达同步和资源计数 | 正确使用全靠程序员自觉，P V 忘写、写反都会酿祸 |
| 管程 | 语言级封装：进出管程自动加锁解锁，配条件变量 | 需要编程语言支持，如 Java 的 synchronized |
一句话点透：软件方法（如 Peterson 算法）证明了纯软件也能互斥但太脆弱，真正实用的互斥都建立在硬件原子指令之上。
4. 信号量与 PV 操作
信号量（semaphore）是一个带等待队列的整数变量 S，只能通过两个原子操作访问：
- P 操作（wait，申请）：
S = S - 1；若 S < 0，调用者阻塞，进入该信号量的等待队列。 - V 操作（signal，释放）：
S = S + 1；若 S <= 0，说明有人在等，唤醒队列中一个进程。
理解信号量的钥匙是读懂 S 的值：S > 0 时，S 表示还剩多少资源可用；S < 0 时，S 的绝对值表示有多少进程在排队等。
两种典型用法：
| 用法 | 初值 | 效果 |
|---|---|---|
| 互斥信号量 mutex | 1 | P 进临界区，V 出临界区，同一时刻至多一人在内 |
| 同步信号量 | 0 | 后行者先 P（等信号），先行者完成后 V（发信号），实现"你做完我才动" |
同步的固定句式值得背下来："等消息的一方 P，发消息的一方 V，信号量初值为 0"。
5. 经典问题一：生产者-消费者
场景：生产者把产品放进容量为 N 的缓冲区，消费者从中取走。约束有三：缓冲区满时生产者必须等；空时消费者必须等；缓冲区本身是共享数据，存取要互斥。
三个信号量：mutex = 1（互斥访问缓冲区）、empty = N（空位数量）、full = 0（产品数量）。
text
生产者： 消费者：
while true: while true:
生产一个产品 P(full) // 等一个产品，没有就睡
P(empty) // 等一个空位 P(mutex) // 抢缓冲区使用权
P(mutex) // 抢缓冲区使用权 从缓冲区取出产品
把产品放入缓冲区 V(mutex) // 归还使用权
V(mutex) // 归还使用权 V(empty) // 空位多了一个
V(full) // 产品多了一个 消费该产品逐行看关键点：P(empty) 在问"还有空位吗"，V(full) 在喊"来货了"——资源信号量成对地跨进程呼应：生产者 P 的是 empty、V 的是 full，消费者正好相反。
最重要的考点：两个 P 的顺序不能颠倒。 若生产者先 P(mutex) 再 P(empty)：缓冲区满时，生产者已握着 mutex 却在等空位；消费者想取货腾空位，却在 P(mutex) 上等生产者——互相等，死锁。而两个 V 的顺序无所谓，V 不会阻塞。口诀：先申请资源信号量，再申请互斥信号量；释放顺序随意。
6. 经典问题二：读者-写者
场景：一份共享数据，读者之间可以同时读（读不改数据，互不干扰），但写者必须独占——写与写互斥，写与读也互斥。
读者优先版方案：rw = 1（对数据的独占权），mutex = 1（保护读者计数器），count = 0（当前读者数）：
text
写者： 读者：
P(rw) // 独占数据 P(mutex) // 保护 count
写数据 count = count + 1
V(rw) // 释放 if count == 1: P(rw) // 第一个读者替全体占门
V(mutex)
读数据
P(mutex)
count = count - 1
if count == 0: V(rw) // 最后一个读者交还门
V(mutex)精髓在两个 if：只有第一个进门的读者去抢 rw，只有最后一个离开的读者去还 rw，中间的读者搭顺风车直接读。这就实现了"读读共享、读写互斥"。
代价：读者络绎不绝时 rw 永远还不回去，写者饥饿。改成"写者优先"或"公平读写"可解决，考试通常只要求看懂读者优先版并指出饥饿问题。
7. 死锁：四个必要条件
死锁：一组进程互相等待对方手里的资源，谁都无法推进。最小模型：A 持有资源 1 等资源 2，B 持有资源 2 等资源 1。
死锁发生必须四个条件同时成立，缺一不可：
| 条件 | 白话例子 |
|---|---|
| 互斥 | 一支话筒同一时刻只能一个人用——资源本身不能共享 |
| 占有且等待 | 手里攥着话筒，还赖着不放地等音响——拿着一部分等另一部分 |
| 不可剥夺 | 没人能从别人手里硬抢话筒——资源只能自愿交出 |
| 循环等待 | 我等你的音响，你等我的话筒——等待关系围成一个圈 |
注意措辞：这是必要条件——死锁了则四条必然全成立；反过来四条成立也不一定死锁（只是可能）。破坏任意一条，死锁就不可能发生，这正是"预防"的思路。
8. 死锁处理的四条路线
| 路线 | 时机 | 思路 | 代价 |
|---|---|---|---|
| 预防 | 事前，定死规则 | 破坏四个必要条件之一，如资源按序号申请（破坏循环等待）、一次性申请全部资源（破坏占有且等待） | 资源利用率低、限制太死 |
| 避免 | 事中，每次分配前算一算 | 只在"分配后系统仍安全"时才批准，代表是银行家算法 | 需预知最大需求，计算开销大 |
| 检测 | 事后，定期体检 | 平时随便分配，定期检查是否已死锁 | 死锁已发生，还需配合解除 |
| 解除 | 检测出后收拾残局 | 撤销进程或剥夺资源，打破循环 | 被撤销进程的工作作废 |
记忆抓手：预防最保守，避免走钢丝，检测加解除最放任。鸵鸟策略（假装死锁不存在）是第五种"不处理"，通用系统里其实很常见。
9. 银行家算法手算例题
思想：把操作系统看成银行家，进程是贷款客户。每次有人申请资源，先假装批准，然后检查：剩下的钱能否让所有客户按某个顺序逐个满足最大需求并还清？能找到这样的顺序（安全序列）就真批准，找不到就让申请者等。系统处于安全状态是"存在安全序列"的同义词。
例题：系统有 A、B、C 三类资源，当前可用 Available = (3, 3, 2)。
| 进程 | 已分配 Allocation | 最大需求 Max | 还需 Need = Max − Allocation |
|---|---|---|---|
| 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 |
安全性检查，规则：找一个 Need ≤ 当前可用 的进程，让它跑完并归还其 Allocation，可用量增加，重复直到所有进程完成或无人可选。
| 步骤 | 可用量 | 谁的 Need 放得下 | 选它跑完后归还 | 新可用量 |
|---|---|---|---|---|
| 1 | 3 3 2 | P1 需 1 2 2 可满足 | 归还 2 0 0 | 5 3 2 |
| 2 | 5 3 2 | P3 需 0 1 1 可满足 | 归还 2 1 1 | 7 4 3 |
| 3 | 7 4 3 | P4 需 4 3 1 可满足 | 归还 0 0 2 | 7 4 5 |
| 4 | 7 4 5 | P2 需 6 0 0 可满足 | 归还 3 0 2 | 10 4 7 |
| 5 | 10 4 7 | P0 需 7 4 3 可满足 | 归还 0 1 0 | 10 5 7 |
全部进程可依次完成，安全序列为 P1 → P3 → P4 → P2 → P0（安全序列不唯一，如 P1 → P3 → P4 → P0 → P2 也行），系统处于安全状态。
若此时 P1 再申请 (1, 0, 2)：先试分配，Available 变 (2, 3, 0)，P1 的 Allocation 变 (3, 0, 2)、Need 变 (0, 2, 0)，重新做上述检查仍能找到安全序列，故可以批准。若 P0 申请 (0, 2, 0)，试分配后 Available = (3, 1, 2)，检查发现除 P1、P3 外后续无法全部满足时则拒绝并回滚。手算题就是反复执行这套"试分配 + 找安全序列"。
易错提醒：不安全状态 ≠ 已死锁，它只是"存在走向死锁的可能"；银行家算法保证系统永不进入不安全状态，从而避免死锁。
10. 本章要点回顾
| 主题 | 必须记住的结论 |
|---|---|
| 竞态条件 | 共享 + 有写 + 非原子，三者齐了结果就看交错运气 |
| 互斥 vs 同步 | 互斥管"不能同时"，同步管"必须有先后" |
| 四个准则 | 空闲让进、忙则等待、有限等待、让权等待 |
| 实现层次 | 关中断→锁→信号量→管程，逐层弥补上层缺陷 |
| 信号量 | S 为负时绝对值 = 等待进程数；同步用法初值为 0 |
| 生产者-消费者 | mutex=1、empty=N、full=0；先 P 资源量再 P 互斥量，反了会死锁 |
| 读者-写者 | 第一个读者占门、最后一个读者还门；读者优先会饿死写者 |
| 死锁四条件 | 互斥、占有且等待、不可剥夺、循环等待——必要条件 |
| 四条路线 | 预防破坏条件、避免算安全性、检测定期查、解除撤进程 |
| 银行家算法 | 属于"避免"；核心是找安全序列；不安全不等于死锁 |
11. 做题提醒
- P、V 操作本身必须是原子的（由内核用更底层的手段保证），否则信号量自己就有竞态。
- 信号量 S = -3 表示有 3 个进程在等待；问"最多几个进程在临界区"看互斥信号量初值。
- 生产者-消费者代码排序题：盯住两个 P 的顺序，
P(mutex)在P(empty)/P(full)之后才对。 - "破坏四个必要条件之一"属于死锁预防；"银行家算法"属于死锁避免，两者在选择题里经常互相冒充。
- 死锁四条件是必要不充分：四条全成立未必死锁，但少一条必定不死锁。
- 安全状态判定题按"试分配→算 Need→找安全序列"三步走，找不到序列就拒绝分配并恢复原状，别忘了回滚。