Appearance
同步互斥实现方法
2026 大纲 二（三）2 基本的实现方法，补充说明点名「软件方法，硬件方法」两类。
进入区到底该怎么写
上一节把问题定死了：代码切成四段，关键是进入区和退出区怎么写， 写出来的方案再拿四条准则去评。这一节就是各种写法的展览。
先看软件方法。最朴素的想法是设一个"有没有人在里面"的标志， 进去前检查、出来时清掉。可这个想法本身有个致命的空档： 检查和设置之间也可能被切走——两个进程同时检查到"没人"，然后都进去了。
于是有了一条修补链：先检查后设置漏互斥 ⇒ 那就先设置再检查 ⇒ 可两个都先设置就都进不去了（僵持）⇒ 再加一个"轮到谁"的变量打破对称 ⇒ Peterson 算法。
⚠️ 这条链共用一条判据："检查"和"设置"哪个在前。 设置在后漏互斥，设置在前会僵持——两者失守的准则正好错开， 所以修补是在两个方向之间来回调，直到 Peterson 才同时站住。
软件方法能走到这一步已经不容易，但它有个共同的天花板：全都是忙等。 道理很简单——让出处理机需要 block() 原语，而原语是 OS 提供的， 纯软件方法凭自己变不出来。
硬件方法换了个思路：别用软件去凑原子性，让硬件直接给一条原子指令。 TS 与 Swap 就是这么来的——它们把"检查 + 设置"合成一条不可分割的指令， 上面那个空档从根上不存在了。
⚠️ 但硬件指令卖的只有原子性，不卖让权等待——它们照样是忙等。 唯一四条准则全过的是中断屏蔽法，可它的适用边界最窄 （单处理机 + 内核态 + 短临界区），而且多核上关中断挡不住另一个核。
一、软件方法：四步修补链
第一步：单标志法
公共变量 turn 表示允许进入临界区的进程编号：
// 进程 P0 // 进程 P1
while (turn != 0); while (turn != 1);
临界区; 临界区;
turn = 1; turn = 0;互斥是牢靠的（turn 任一时刻只有一个值，两个 while 条件不可能同时为假），但进入权由对方指定：P0 只能把 turn 置成 1，自己没法置回 0。P0 进完一次后再也不来，P1 用完一次就再也进不去——两个进程被强制严格交替，哪怕另一方压根没有进入需求。症结是"进入权由对方指定"，补法是给每人一个变量。
第二步：双标志先检查法
flag[i] 表示进程 i 是否想进入，进入前先看对方举手没有：
// 进程 P0 // 进程 P1
while (flag[1]); ① while (flag[0]); ③
flag[0] = true; ② flag[1] = true; ④
临界区; 临界区;
flag[0] = false; flag[1] = false;强制交替解决了（只要 P1 没举手，P0 连进十次都行），但按 ①③②④ 执行时两个进程都在对方举手之前完成了检查，于是双双进入临界区——「检查对方」和「设置自己」是两条独立指令，教材的「忙则等待」准则正是在这道缝隙里失守。缝隙的方向很清楚：检查在前、设置在后，所以对方"看不见我"。补法是把设置提前。
第三步：双标志后检查法
// 进程 P0 // 进程 P1
flag[0] = true; ① flag[1] = true; ③
while (flag[1]); ② while (flag[0]); ④
临界区; 临界区;
flag[0] = false; flag[1] = false;互斥保住了，但按 ①③②④ 执行时两个 flag 都为 true、两个 while 都不结束，而降标志的代码在临界区之后，谁也走不到——临界区空着却谁也进不去。僵持的成因是对称：两个进程状态完全一样，没有任何信息能决定"该谁进"。要打破对称，就得引入一个只能有一个值的变量，而这样的变量第一步就有过，它叫 turn。
第四步：Peterson 算法
// 进程 P0 // 进程 P1
flag[0] = true; // 我想进入 flag[1] = true;
turn = 1; // 但我让你先 turn = 0;
while (flag[1] && turn == 1); while (flag[0] && turn == 0);
临界区; 临界区;
flag[0] = false; flag[1] = false;（a）互斥性。 假设两个进程同时在临界区，那么必然 flag[0] == flag[1] == true，于是两个 while 的条件要为假只能靠 turn 那一半：P0 通过需要 turn != 1，P1 通过需要 turn != 0。而 turn 是单个变量，两个条件不可能同时成立。矛盾 ⇒ 不可能同时进入。关键在"谦让"这一步：两人都把 turn 写成对方的编号，后写的那次赋值覆盖前一次，turn 最终停在的值恰好放行另一个进程。
（b）不会僵持。 假设 P0 卡在 while 里，说明 flag[1] == true 且 turn == 1；此时 P1 的条件 flag[0] && turn == 0 因 turn == 1 而为假，P1 一定能进去，出临界区时执行 flag[1] = false，P0 的条件随即变假。因此 P0 至多等 P1 一次临界区。
（c）不满足让权等待。 while 是空转，进程占着处理机什么也不做。
Peterson 的逐拍交错，以及把 turn 写成自己编号后互斥怎么当场失效（想在时间轴上看清 turn 如何裁决时展开）
正确写法：两个进程几乎同时到达，看 turn 如何裁决。
| 节拍 | P0 执行 | P1 执行 | flag[0] | flag[1] | turn | 谁能进 |
|---|---|---|---|---|---|---|
| 1 | flag[0]=true | true | false | – | ||
| 2 | flag[1]=true | true | true | – | ||
| 3 | turn=1 | true | true | 1 | ||
| 4 | turn=0 | true | true | 0 | ← 后写的覆盖前写的 | |
| 5 | 判 flag[1]&&turn==1：true&&false=假 | true | true | 0 | P0 进入 | |
| 6 | 判 flag[0]&&turn==0：true&&true=真 | true | true | 0 | P1 自旋 | |
| 7 | 出临界区，flag[0]=false | false | true | 0 | ||
| 8 | 判 flag[0]&&turn==0：false&&…=假 | false | true | 0 | P1 进入 |
节拍 3、4 是全表的枢纽：P1 后写 turn，于是 P1 让步。 若把 3、4 对调，进入的就是 P1——结论对称，但任一次执行中只可能有一个人进去。
错误写法 turn = 自己 的反例，只要四拍就破。
| 节拍 | P0 | P1 | flag[0] | flag[1] | turn |
|---|---|---|---|---|---|
| 1 | flag[0]=true; turn=0; | true | false | 0 | |
| 2 | 判 flag[1]&&turn==1：false&&… = 假 → 进入临界区 | true | false | 0 | |
| 3 | flag[1]=true; turn=1; | true | true | 1 | |
| 4 | 判 flag[0]&&turn==0：true&&false = 假 → 也进入临界区 | true | true | 1 |
根子在于那次赋值把自己的循环条件推向真还是推向假。原版写对方编号，后写的人把自己的条件推成真、把自己挡住——"已经有人在里面、新来的人进不去"正是靠这一条；改成写自己编号后，后写的人把自己的条件推成假、把自己放行，而先到的那位早就凭"对方还没举手"通过了检查，两人于是同时在临界区里。指令级穷举也印证：原版的可达状态里"两进程同时在临界区"为 0，改成 turn = 自己 后确实出现了这种状态。
用同一条交错打三种方法。 记 P0 的两条语句为 a₁、a₂，P1 的为 b₁、b₂，序列固定为 a₁ → b₁ → a₂ → b₂（比较方案必须控制变量，这是最"坏"的一条交错）：
| 方法 | a₁ / b₁ | a₂ / b₂ | 序列走完后的状态 | 结论 |
|---|---|---|---|---|
| 双标志先检查 | 检查对方（都读到 false，都跳出） | 举手（flag=true） | 两人都已跳出循环 | 双双进入临界区 → ① 忙则等待失守 |
| 双标志后检查 | 举手（flag=true） | 检查对方（都读到 true） | 两个 while 都不结束 | 双双卡死 → ②③ 失守 |
| Peterson | flag=true | turn=对方 | turn 只剩一个值 | 恰好一人通过 → 前三条全过 |
指令级穷举全部交错的结果与上表一致：双标志先检查法存在 2 个"两进程同时处于临界区"的可达状态；双标志后检查法有 1 个全体卡死的状态、0 个互斥失效状态；Peterson 算法 32 个可达状态中互斥失效 0、卡死 0。
二、硬件方法：买来一个原子性
软件方法失败的根源全都一样——"检查"与"设置"之间可以被打断。软件手里只有普通的读、写指令，无论怎么排列组合都消不掉这道缝隙。硬件方法的做法很直接：造一条指令，把读和写焊死在一起。 教材对这条路线的概括是把标志看作一把锁："锁开"进入、"锁关"等待；为防止多个进程同时测试到锁为打开的情况，测试和关锁操作必须是连续的，不允许分开进行。
中断屏蔽法
关中断;
临界区;
开中断;进程切换的触发点是中断（时钟中断触发调度、I/O 中断唤醒进程）。关掉中断，处理机就不响应中断，也就不会引发调度，进程在临界区执行期间不可能被切换出去——"测试和关锁"的连续性因此得到保证。
三条缺点里第③条最能说明问题：关中断关的是"本处理机不被打断"，而多处理机上的另一个核根本不需要打断本核，它一直在并行地跑。 互斥要挡住的是"另一个执行流"，而关中断只能挡住"本执行流被换掉"。
TestAndSet（TS / TSL）与 Swap（XCHG）
c
// 由硬件保证整体不可中断
boolean TestAndSet(boolean *lock) {
boolean old = *lock;
*lock = TRUE;
return old;
}
// 使用
while (TestAndSet(&lock)); // 拿到旧值 false 才算上锁成功
临界区;
lock = FALSE;读出的旧值 false 说明"我来之前锁是开的，而且我已经把它关上了"——判断与占有一次完成，缝隙消失。
c
// 由硬件保证整体不可中断
void Swap(boolean *a, boolean *b) {
boolean temp = *a;
*a = *b;
*b = temp;
}
// 使用
boolean key = TRUE;
do {
Swap(&lock, &key); // 把 TRUE 换进 lock，把 lock 的旧值换进 key
} while (key); // key 为 false 说明原来锁是开的
临界区;
lock = FALSE;两条指令的能力等价，用哪一条写出来的方案性质完全相同，差别只在形式：TS 操作一个共享变量、旧值作返回值、写入的新值固定是 TRUE；Swap 操作两个变量、旧值换到私有变量 key 里、写入值由私有变量决定。互相模拟也很直接：TS(lock) ≡ key=TRUE; Swap(&lock,&key); return key;。
至于为什么它们仍不满足让权等待——硬件只卖给我们原子性这一样能力，没有卖给我们"把自己挂起来"这样能力。要放弃处理机必须调用 block() 把进程从运行态移入阻塞队列，那是操作系统的原语，不是一条指令能做的事。
考点速记
- 软件四步是一条修补链而非并列方案，共用一条判据："检查"和"设置"哪个在前——设置在后漏互斥（先检查法），设置在前会僵持（后检查法），两者失守的准则正好错开。
- Peterson
flag[]表意愿turn打破对称。互斥性靠"turn是单个变量，两个while条件不能同时为假"。 - ⚠️Peterson 的记法：
turn归属谁，谁就得等。 进入区要写turn = 对方（把机会让给对方），写成turn = 自己会让后写者放行自己，互斥当场失效。 - 硬件只卖原子性：TS 与 Swap 能力等价、可互相模拟，靠"写回值是否固定"分辨（TS 固定写
TRUE，Swap 是交换）。 - ⚠️TS、Swap、Peterson 全都不满足让权等待——它们都是忙等，消除忙等只能靠
block()/wakeup()原语（见信号量）。 - ⚠️中断屏蔽法是唯一四条准则全过的方法，但适用边界最窄：单处理机 + 内核态 + 短临界区。多核上关中断挡不住另一个核（与进程的组织与控制速记第二条同一条）。
这一节在真题里被考过的形式：
两道选择题 + 两道大题，全部围绕"这个写法对不对、倒在哪一条准则上"。
- 给一段 Peterson 算法的伪代码，判断它满足哪些准则（2010-27）。⚠️ 这类题的做法是逐条对照四条准则，而不是通读一遍凭感觉。重点看进入区里
turn赋的是谁——赋给对方才对（速记第三条）；再看它是不是忙等（一定是），所以让权等待必然不满足。 - 给 TSL 指令实现互斥的伪代码，判断它的性质（2016-27）。⚠️ 答案落在它不满足让权等待上——
while (TSL(&lock));是典型的自旋忙等。这道题与 2018-32（问哪种机制能让权等待）互为正反面。 - 用
swap指令和布尔变量实现临界区互斥（2023-45，大题）。要求写出进入区与退出区并说明满足哪些准则，判据同上。 - 给整型信号量
wait/signal的实现，分析它的问题（2021-45，大题）。⚠️ 落点是整型信号量不满足让权等待（等不到时执行while忙等），以及开关中断保证原子性在多核上失效。
复习优先级：必须拿满，且要能动手写。 第三条（turn 赋给对方）是 Peterson 唯一会写错的地方；第五、六条（谁能让权等待、中断屏蔽的边界）是选择题的固定落点。 大题要求写代码并逐条对照准则，把四条准则当成检查清单逐项过一遍即可。
易错：Peterson 进入区把
turn赋给自己。必须赋给对方——turn归属谁谁就得等。
易错：认为 TS 或 Swap 指令满足让权等待。硬件只卖原子性，它们照样是忙等。
易错：认为中断屏蔽法在多处理机上也能保证互斥。关中断只挡得住本 CPU。
易错：把 TS 和 Swap 当成能力不同的两条指令。两者等价、可互相模拟，差别只在写回值是否固定。
易错：判方案时只看"能不能互斥"。要四条准则逐条查，倒在第四条上仍然是正确方案。
教材出处
- 关中断的三条缺点取自汤小丹《计算机操作系统》2.4.2 节"硬件同步机制"，印刷 p51：「① 滥用关中断权力可能导致严重后果；② 关中断时间过长，会影响系统效率，限制了处理器交叉执行程序的能力；③ 关中断方法也不适用于多 CPU 系统，因为在一个处理器上关中断并不能防止进程在其它处理器上执行相同的临界段代码。」这三条里没有"不满足让权等待"。
- "不符合让权等待"是写给 TS／Swap 的：同书印刷 p53 开头，「利用上述硬件指令能有效地实现进程互斥，但当临界资源忙碌时，其它访问进程必须不断地进行测试，处于一种'忙等'状态，不符合'让权等待'的原则」——"上述硬件指令"指的正是前一页的 TS 与 Swap。
- 「测试和关锁操作必须是连续的，不允许分开进行」与 TS 指令的代码形式见同书印刷 p51。