考研笔记

实现临界区互斥的基本方法

本节要填的是 2.3.1 留下的空——进入区和退出区具体怎么写。

一共两类方法：软件方法（纯用普通变量和判断实现）和硬件方法（借助特殊指令）。

机制

四个软件算法：一条改错链

疑问点：四个软件算法难以记忆，且前三个本身有缺陷，是否有实际应用

四种软件实现方法容易混淆。既然前三个方法本身存在问题，它们是否曾被实际采用？

这四个算法不是四个并列的方案，而是一条”发现问题—修补—又发现新问题”的改错链。 按这个链条去记，几乎不会混。

而”是否有实际应用”这个问题的答案是：前三个从未被实际采用，它们的价值完全在于教学。每一个都精确地违反四准则中的某一条，用来演示”少考虑一点会出什么事”。所以记忆的抓手不是代码，而是每个算法违反了哪一条准则。

① 单标志法

设一个公用整型变量 turn，表示允许进入临界区的进程编号。

// P0                        // P1
while (turn != 0);           while (turn != 1);
critical section;            critical section;
turn = 1;                    turn = 0;
remainder section;           remainder section;

问题：违反”空闲让进”。

因为 turn 只能由对方在退出临界区时修改，两个进程必须严格交替进入。如果 P0 拿到了 turn = 0 却一直不进入临界区（比如它在剩余区做别的事，或者干脆结束了），那么即使临界区完全空闲，P1 也永远进不去。

一句话：它把”互斥”做成了”轮流”，管得太死。

② 双标志先检查法

设数组 bool flag[2]，flag[i] = true 表示进程 i 想进入临界区。先检查对方，再设置自己。

// Pi
while (flag[j]);      // ① 检查对方是否想进
flag[i] = true;       // ② 设置自己的标志
critical section;
flag[i] = false;

问题：违反”忙则等待”——这是最严重的错误。

关键在于① 和 ② 之间可以被中断。设想这个交错序列：

  1. P0 执行①，发现 flag[1] == false，通过
  2. 此时被切换到 P1
  3. P1 执行①，发现 flag[0] 还是 false（P0 还没来得及执行②），也通过
  4. P1 执行②，进入临界区
  5. 切回 P0，P0 执行②，也进入临界区

两个进程同时进入了临界区，互斥彻底失效。

根因是”检查”和”上锁”不是一个原子操作。这个教训极其重要——它正是后面硬件指令（TS、Swap）存在的全部理由：把”检查+上锁”合并成一条不可分割的指令。

③ 双标志后检查法

既然问题出在”先检查后上锁”，那就调换顺序：先设置自己，再检查对方。

// Pi
flag[i] = true;       // ① 先表明自己想进
while (flag[j]);      // ② 再检查对方
critical section;
flag[i] = false;

互斥实现了（不会再有两个进程同时进入），但违反”空闲让进”和”有限等待”。

新问题是：如果两个进程几乎同时执行完①，那么 flag[0] 和 flag[1] 都是 true，接着两人都在②处循环等待对方——谁也进不去，临界区却空着。

这种双方互相谦让、结果谁也过不去的状态，形象地称为**“饥饿”**（教材用语；从机制上看更接近活锁）。

④ Peterson 算法

Peterson 的思路是：把①和③的手段合起来用——既表明自己的意愿（双标志），又设一个 turn 来打破僵局。

// Pi
flag[i] = true;                    // 我想进
turn = j;                          // 但我先谦让，把机会给对方
while (flag[j] && turn == j);      // 对方想进 且 轮到对方，我才等
critical section;
flag[i] = false;

精妙之处全在 turn = j 这一句——主动把机会让给对方。

它为什么能打破③的僵局？因为当两个进程几乎同时执行时，turn 只能保存最后一次赋值的结果。假设 P0 先写 turn = 1，P1 后写 turn = 0，那么最终 turn == 0：

  • P1 的条件 flag[0] && turn == 0 成立 → P1 等待
  • P0 的条件 flag[1] && turn == 1 不成立（turn 是 0）→ P0 进入

turn 的最终值天然是唯一的，因此必有且仅有一方能通过。 僵局被打破。

Peterson 满足空闲让进、忙则等待、有限等待三条，唯一的缺陷是违反”让权等待”——进不去的进程仍在 while 里空转，属于忙等。

范围提示：Peterson 算法的正确性依赖于内存访问的顺序一致性。现代 CPU 存在指令重排和写缓冲，flag[i] = true 与 turn = j 的写入顺序可能被打乱，导致算法失效。实际系统中必须插入内存屏障才能使用。这一点超出考纲，但可以解释为什么工程上一律改用硬件原子指令。

三个硬件方法

① 中断屏蔽法

关中断;
临界区;
开中断;

关中断之后当前进程不会被切换，自然实现了互斥。这与原语的实现手段是同一个。

三个限制：

  • 只适用于单处理机。关中断只关本 CPU 的中断，另一个 CPU 上的进程照样能进临界区。
  • 不能给用户进程使用。开/关中断是特权指令，用户态执行会触发异常。若允许用户关中断，一个恶意或有 bug 的程序关掉中断后不再打开，整个系统就死了。
  • 临界区必须很短，否则严重影响系统响应和计时。

② TestAndSet 指令（TS / TSL）

用一条硬件指令完成”读出旧值 + 置为 true”，整个过程不可分割：

bool TestAndSet(bool *lock) {
    bool old = *lock;
    *lock = true;
    return old;
}
 
// 使用
while (TestAndSet(&lock));   // 上锁并检查
critical section;
lock = false;                // 解锁

这条指令直接消灭了②双标志先检查法的病根——检查和上锁在硬件层面合成了一步，无法被中断插入。

③ Swap 指令（XCHG）

用一条硬件指令交换两个变量的值：

void Swap(bool *a, bool *b) { bool t = *a; *a = *b; *b = t; }
 
// 使用
bool key = true;
do { Swap(&lock, &key); } while (key);   // 直到换出来的是 false
critical section;
lock = false;

逻辑与 TS 完全等价：把 true 换进去，把原值换出来看。原值为 false 说明之前没人上锁，可以进入。

三个硬件方法的共同缺陷都是违反”让权等待”（中断屏蔽法除外，它是直接不让出 CPU），都存在忙等。

边界

每个算法违反哪一条准则——按这个记

这张表是本节的核心，比记代码更重要：

方法空闲让进忙则等待有限等待让权等待严重程度
① 单标志法✗✓✓✗管得太死，必须交替
② 双标志先检查✓✗✓✗致命：互斥失效
③ 双标志后检查✗✓✗✗互相谦让，双方卡死
④ Peterson✓✓✓✗仅忙等，可用
中断屏蔽✓✓✓—单处理机、特权指令
TS / Swap✓✓✗✗忙等，且不保证公平

记忆抓手：“先检查”是致命的（互斥失效），“后检查”是卡死的（都进不去），Peterson 全对只差让权等待。

为什么”先检查”错而”后检查”对

这一对是本节最高频的辨析。

先检查后上锁：检查通过之后、上锁之前有一个时间窗口，别人可以在这个窗口里也检查通过。→ 两人同时进入。

先上锁后检查：自己的锁已经上好了，别人来检查时一定能看到。→ 不会两人同时进入，但可能两人都上了锁然后互相等。

一句话：先上锁保证了”不会漏判”，代价是可能”都判死”。

双标志后检查法的”饥饿”与死锁的区别

教材把③的问题称为饥饿，但要注意它与真正的饥饿不同：

  • 教材的饥饿在这里指的是”双方都进不去”，两个进程都在忙等循环里空转，仍在占用 CPU。
  • 而死锁要求进程处于阻塞态，互相等待对方持有的资源。

因为③里的进程从未阻塞、一直在跑，严格说它属于活锁（livelock）。考试按教材口径答”饥饿”即可，但要清楚它并非死锁。

硬件方法不保证”有限等待”

TS 和 Swap 只保证了互斥，没有排队机制——多个进程同时抢锁时，谁抢到完全看运气。理论上某个进程可能一直抢不到，因此不满足有限等待。

这一点常被忽略，是选择题的常见考点。

对照速查

软件方法硬件方法
依赖普通变量 + 判断特殊硬件指令
代表PetersonTS、Swap、中断屏蔽
适用处理机单/多均可（需内存屏障）TS/Swap 单多均可；中断屏蔽仅单处理机
能否用户态使用可以TS/Swap 可以；中断屏蔽不可以
共同缺陷忙等（违反让权等待）忙等（违反让权等待）

考点

  • 四个软件算法各违反哪条准则（本节第一考点）
  • 双标志先检查法违反”忙则等待”，是唯一会导致互斥失效的
  • Peterson 中 turn = j 的作用：主动谦让，靠 turn 的唯一最终值打破僵局
  • 中断屏蔽法只适用于单处理机、且是特权指令
  • TS/Swap 把”检查+上锁”合成原子操作，但不保证有限等待
  • 所有这些方法都违反让权等待（忙等）

链接

反向链接