Appearance
同步与互斥基本概念
2026 大纲 二（三）1 同步与互斥的基本概念。
能交替执行，就会互相踩
到这里，进程能被创建、能在状态间转、能被调度切换了。可"能被切换"这件事本身带来了新麻烦。
看一个最小的例子：两个进程都执行 x = x + 1。这一行在机器上是三条指令—— 取到寄存器、加一、存回内存。如果 P1 刚取完就被切走，P2 完整跑了一遍， P1 再切回来接着用它那个旧值加一存回去——P2 的那次加一就被抹掉了。
根源在一句话：高级语言里的一条语句，在机器上不是原子的。 而调度可以发生在任意两条机器指令之间。
操作系统基本概念里说过，异步逼出的底线是 结果的可再现性——同样的输入必须算出同样的结果。上面这个例子就把它破坏了。
要守住这条底线，办法只有一个：把那段不能被打断的代码人为地包装成"原子的"， 让它一次只允许一个进程进去。这段代码就叫临界区， 而整个执行流被切成四段：进入区 → 临界区 → 退出区 → 剩余区。
这一章剩下的全部内容——软件方法、硬件指令、锁、信号量、管程—— 都是在回答同一个问题：进入区和退出区该怎么写。
而评价它们写得对不对，有四条准则。⚠️ 这四条不在同一层级： 空闲让进 + 忙则等待保正确、有限等待保可用、让权等待保不浪费。 判一个方案时按这个次序查，只倒在第四条上的方案仍然是正确的，只是浪费 CPU。
一、并发为什么会出错：一个共享变量就够了
缓冲池里有一个计数器 count，生产者放入产品后执行 count++，消费者取走后执行 count--。在高级语言里这两行看着是"一步"，编译成机器指令后各是三步：
count++ → R1 = count; R1 = R1 + 1; count = R1;
count-- → R2 = count; R2 = R2 - 1; count = R2;设 count 当前是 5，两个进程按下面的次序交错：
| 时刻 | 生产者 | 消费者 | 内存中的 count |
|---|---|---|---|
| ① | R1 = count → R1=5 | 5 | |
| ② | R2 = count → R2=5 | 5 | |
| ③ | R1 = R1+1 → R1=6 | 5 | |
| ④ | R2 = R2−1 → R2=4 | 5 | |
| ⑤ | count = R1 | 6 | |
| ⑥ | count = R2 | 4 |
一放一取，count 本该还是 5，结果成了 4；把 ⑤⑥ 对调又变成 6。推导链就在这里成形：
并发进程共享变量 ⇒ 高级语句不是原子的，能被打断 ⇒ 打断点落在"读—改—写"中间时结果被覆盖 ⇒ 必须有办法把这段代码变成"要么整段做完、要么还没开始" ⇒ 这就是临界区的由来。
二、临界区与四段结构
要让临界区互斥执行，就必须在进入之前判断"现在能不能进"、在离开之后告诉别人"我出来了"。这两件事都不属于访问资源本身，于是自然分离出两段协调代码，再加上与该资源无关的剩余代码，共四段：
// 进程 P_i 的通用结构
while (true) {
进入区（Entry Section）; // 检查并"上锁"
临界区（Critical Section）; // 访问临界资源的代码
退出区（Exit Section）; // "解锁"，通知其他进程
剩余区（Remainder Section）; // 与该临界资源无关的其他代码
}剩余区的存在是"互斥只应作用在必要的最小范围上"这条设计原则的体现——后面讲锁的粒度、讲读者-写者问题里"读操作不放进 mutex"，用的都是同一条原则。
三、四条准则是怎么被逼出来的
汤小丹教材把这四条并列给出，但它们并不在同一层级。按"这条不满足会坏掉什么"来分，恰好分成两组：
| 准则 | 教材表述 | 不满足会怎样 | 它是被什么逼出来的 |
|---|---|---|---|
| ① 忙则等待 | 已有进程进入临界区时，其它试图进入的进程必须等待 | 两个进程同时改共享变量，结果不确定 | 这就是互斥的定义本身，是底线 |
| ② 空闲让进 | 临界资源空闲时，应允许一个请求进程立即进入 | 明明没人用却进不去，资源被白白闲置 | 只满足 ① 的最简方案是"永远不让任何人进"——它正确但无用，所以必须补一条反向约束 |
| ③ 有限等待 | 应保证在有限时间内能进入自己的临界区，以免陷入"死等" | 某个进程被无限期推迟（饥饿） | ①② 只管"当下这一刻"，管不了"总有人插队"。③ 把要求从单点扩展到时间轴 |
| ④ 让权等待 | 不能进入临界区时，应立即释放处理机，以免陷入"忙等" | 进程占着 CPU 空转，系统吞吐下降 | ①②③ 满足后方案已经正确了，④ 管的是效率 |
为什么"让权等待"单独成一档
前三条不满足，程序会算错或卡住；第四条不满足，程序结果完全正确，只是白烧 CPU。所以教材里凡是说"某方法不满足让权等待"，说的都不是它有错，而是它有代价。
一个用共享变量 busy 的方案倒在哪条准则上：逐拍构造反例序列（想学会怎么判一个陌生互斥方案时展开）
某系统用一个共享变量 busy 保护一台绘图仪，两个进程的代码写成：
// 进程 A // 进程 B
while (busy != 0) ; while (busy != 0) ;
busy = 1; busy = 1;
使用绘图仪; 使用绘图仪;
busy = 0; busy = 0;第 1 步：先查 ① 忙则等待。 查法是找一条能让两个进程同时进临界区的执行序列。构造反例的固定手法是把"检查"和"修改"之间的缝隙撑开——让两个进程都在对方写 busy 之前完成读取。
| 时刻 | 进程 A | 进程 B | busy |
|---|---|---|---|
| ① | while(busy!=0) 读到 0，跳出循环 | 0 | |
| ② | while(busy!=0) 读到 0，跳出循环 | 0 | |
| ③ | busy = 1 | 1 | |
| ④ | busy = 1 | 1 | |
| ⑤ | 进入临界区 | 进入临界区 | 1 |
序列存在 ⇒ ① 不满足。① 是底线，构造出一条反例序列就可以直接判否，不必再看其余三条。
第 2 步：确认根因。 while 读 busy 与 busy = 1 是两条独立指令，中间可被调度打断，因此"判断资源空闲"与"占住资源"不是一个原子动作。
第 3 步：其余三条。 ② 空闲让进满足（busy==0 时谁都能进）；③ 有限等待——因为 ① 已失效，进程实际上不会长期被拦住，但这不是它做对了什么，而是它根本没在拦；④ 让权等待不满足（while 空转占 CPU）。
结论：该方案倒在 ① 上，属于无效方案。修复方向只有一个——让"检查 + 上锁"合成一个不可打断的动作，这正是硬件指令要解决的事。
考点速记
- 并发出错的根源是"高级语句不是原子的"：
x = x + 1在机器上是取数、加一、存回三条指令，调度可以插在任意两条之间。临界区的本质就是把非原子操作人为包装成原子操作。 - 代码切成四段：进入区 → 临界区 → 退出区 → 剩余区。
- ⚠️两种制约关系的分辨只有一句：打乱执行顺序结果照样对，是互斥（间接制约，约束来自资源）；结果会错，是同步（直接制约，约束来自事件）。
- 临界区按"访问哪份资源"划分——一份临界资源的多段临界区必须共用同一把锁。
- ⚠️四条准则不在同一层级：① 空闲让进 + ② 忙则等待保正确；③ 有限等待保可用（不饥饿）；④ 让权等待保不浪费。判方案按此次序查，只倒在 ④ 上的方案仍然正确。
- ⚠️**"必须遵循"的只有前三条——让权等待是改善性**要求，不满足它只是忙等浪费 CPU，互斥本身仍然成立。
- ④ 之所以最难满足，是因为放弃处理机需要
block()原语，纯软件方法和纯硬件指令都给不出——所以 Peterson、TSL、Swap 全都不满足让权等待，只有信号量（及基于它的锁与管程）能满足。 - Bernstein 条件（两个进程能并发执行的充要条件）：
、 、 。⚠️读集与读集可以相交（都只读不冲突），要求不相交的是"读写"与"写写"三对。
这一节在真题里被考过的形式：
sync-mutex-concepts 挂了 18 道题，其中大半是信号量的应用大题 （在信号量与三个经典同步问题里讲）， 本页练习区渲染的题比本节内容宽，属正常。落在本节的按问法分三类：
- ① 问实现临界区互斥必须遵循哪些准则（2020-32）。答前三条（不能同时进入、允许访问空闲的临界资源、等待时间有限），⚠️**"不能进入临界区的进程立即放弃 CPU"（让权等待）不是必须遵循的**——它是改善性要求（速记第六条）。这道题就是速记第五条那个分层的直接考法。
- ② 问哪种同步机制可以实现让权等待（2018-32）。答信号量方法。⚠️ Peterson、
swap指令、TestAndSet指令全都是忙等——它们没有block()原语，做不到让出处理机（速记第七条）。 - ③ 给两段并发的机器指令，问共享变量可能的取值（2011-32）。做法是枚举两段指令的交错方式，看"取数—计算—存回"如何互相覆盖。⚠️ 判据是速记第一条——只要两个进程各自的"取"和"存"之间插进了对方的完整操作，就会丢失一次更新。
- ④ 判断两个进程能否并发执行（2026-27，Bernstein 条件）。答三个交集为空的条件是
、 、 。⚠️** 不必为空**——两个进程同时读同一个变量没有任何问题。
复习优先级：必须拿满。 速记第五、六条（四条准则的分层、哪三条是必须的） 与第七条（只有信号量能让权等待）是两道选择题的直接答案，务必背准。 第八条 Bernstein 条件是 2026 年新出现的，记住"读读不冲突，读写和写写才冲突"即可。 第三条那个互斥与同步的分辨在写 PV 操作时天天用到。
易错：把"让权等待"当成必须遵循的准则。必须遵循的只有前三条，让权等待是改善性要求。
易错：认为 Peterson 或 TSL 指令能实现让权等待。它们都是忙等——没有
block()原语。
易错：认为 Bernstein 条件要求读集也不相交。读读不冲突，只有读写、写写三对要求为空。
易错：把互斥和同步搞混。打乱顺序结果还对是互斥（争资源），结果会错是同步（等事件）。
易错：认为一份临界资源的不同代码段可以用不同的锁。必须共用同一把锁，否则互斥不成立。
教材出处
- 四条准则的表述取自汤小丹《计算机操作系统》2.4.1 节"同步机制应遵循的规则"，印刷 p51：空闲让进"应允许一个请求进入临界区的进程立即进入"、忙则等待"以保证对临界资源的互斥访问"、有限等待"以免陷入'死等'状态"、让权等待"应立即释放处理机，以免进程陷入'忙等'状态"。
- "互斥可用一个初值为 1 的信号量实现"见同书 2.4.4 节，印刷 p56：mutex 初值为 1，取值范围为 (−1, 0, 1)。
相关知识
进程与线程的基本概念｜同步互斥实现方法｜信号量｜生产者-消费者问题