Appearance
同步互斥实现方法
考情分析
同步互斥实现方法在 408 真题中常以选择题考查各方法的优缺点。属于 🔥🔥 中高频考点。
上一篇定义了临界区的四个访问原则，这一篇看人们是怎么一步步实现这些原则的——从最初的错误尝试，到 Peterson 算法，再到硬件指令，每一步都在修复上一步的漏洞。
软件实现方法
单标志法
设一个公共变量 turn 表示允许进入临界区的进程编号：
// 进程 P0 // 进程 P1
while (turn != 0); while (turn != 1);
临界区; 临界区;
turn = 1; turn = 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;问题：破坏「互斥」——按①③②④的顺序执行时，两个进程都检查到对方标志为 false、以为对方没有要进入，于是同时进入临界区。根源是「检查对方」和「设置自己」两步不是原子的；教材「忙则等待」准则（已有进程进入临界区时，其它进程必须等待，以保证对临界资源的互斥访问）正是在这里失守。
双标志后检查法
先标记自己要进入，再检查对方：
// 进程 P0 // 进程 P1
flag[0] = true; ① flag[1] = true; ③
while (flag[1]); ② while (flag[0]); ④
临界区; 临界区;
flag[0] = false; flag[1] = false;问题：违反「空闲让进」和「有限等待」——如果按①③②④的顺序，两个进程互相等待对方释放标志，产生死锁（饥饿）。
Peterson 算法 🔥🔥🔥
结合单标志法和双标志法，既用 flag[] 表达意愿，又用 turn 谦让：
// 进程 P0
flag[0] = true; // 我想进入
turn = 1; // 但我让你先
while (flag[1] && turn == 1);
临界区;
flag[0] = false;
// 进程 P1
flag[1] = true; // 我想进入
turn = 0; // 但我让你先
while (flag[0] && turn == 0);
临界区;
flag[1] = false;Peterson 算法满足空闲让进、忙则等待、有限等待，但不满足让权等待（while 循环是忙等待）。
硬件实现方法
中断屏蔽法
关中断;
临界区;
开中断;| 优点 | 缺点 |
|---|---|
| 简单有效 | 只适用于单处理机 |
| 关中断是特权指令，只能在内核态使用 | |
| 关中断时间过长影响系统效率 |
TestAndSet（TSL）指令
硬件提供的原子指令：
c
// 硬件原子执行，不可中断
bool TestAndSet(bool *lock) {
bool old = *lock;
*lock = true;
return old;
}
// 使用
while (TestAndSet(&lock)); // 忙等待
临界区;
lock = false;Swap（XCHG）指令
c
// 硬件原子执行
void Swap(bool *a, bool *b) {
bool temp = *a;
*a = *b;
*b = temp;
}
// 使用
bool key = true;
while (key) Swap(&lock, &key); // 忙等待
临界区;
lock = false;各方法对比
| 方法 | 空闲让进 | 忙则等待 | 有限等待 | 让权等待 |
|---|---|---|---|---|
| 单标志法 | ✗ | ✓ | ✓ | ✗ |
| 双标志先检查 | ✓ | ✗ | — | ✗ |
| 双标志后检查 | ✗ | ✓ | ✗ | ✗ |
| Peterson | ✓ | ✓ | ✓ | ✗ |
| 中断屏蔽 | ✓ | ✓ | ✓ | ✓ |
| TSL/Swap | ✓ | ✓ | ✓ | ✗ |
让权等待
除中断屏蔽法外，其他方法都存在忙等待（busy waiting）问题——进程在 while 循环中空转消耗 CPU。信号量机制通过阻塞/唤醒解决了这个问题。
本文对应考点
- 🔥🔥🔥 Peterson 算法的原理和它满足哪些原则
- 🔥🔥🔥 各软件方法分别违反了哪个原则
- 🔥🔥 TSL 和 Swap 的特点（原子性、忙等待）
- 🔥🔥 中断屏蔽法的适用范围（单处理机、内核态）
- 🔥 所有硬件方法都不满足让权等待
软件方法和硬件指令都有忙等待的问题。下一篇看锁如何在"忙等"和"阻塞"两条路线上提供更实用的互斥方案。