题目

下表给出了整型信号量 S 的 wait() 和 signal() 操作的功能描述，以及采用开/关中断指令实现信号量操作互斥的两种方法。

功能描述

Semaphore S;

wait(S) {
    while (S <= 0);
    S = S - 1;
}

signal(S) {
    S = S + 1;
}

方法 1

wait(S) {
    关中断;
    while (S <= 0);
    S = S - 1;
    开中断;
}

signal(S) {
    关中断;
    S = S + 1;
    开中断;
}

方法 2

wait(S) {
    关中断;
    while (S <= 0) {
        开中断;
        关中断;
    }
    S = S - 1;
    开中断;
}

signal(S) {
    关中断;
    S = S + 1;
    开中断;
}

请回答下列问题：

(1) 为什么在 wait() 和 signal() 操作中对信号量 S 的访问必须互斥执行？

(2) 分别说明方法 1 和方法 2 是否正确。若不正确，请说明理由。

(3) 用户程序能否使用开/关中断指令实现临界区互斥？为什么？

解析

（1）为什么 wait/signal 中对 S 的访问必须互斥？

S 是多个进程共享的变量，wait() 中要做"判断 + 减 1"两步、signal() 中要做"加 1"，这些都不是原子操作。如果两个进程同时执行：

• 进程 A 读到 S = 1，准备减 1
• 进程 B 也读到 S = 1，准备减 1
• A 写回 S = 0
• B 写回 S = 0

→ 实际上 wait 被调用了 2 次，但 S 只减了 1（应该减到 -1）。这会导致竞态条件：本应阻塞的进程"漏掉"了阻塞、本应通过的进程错过了机会。

所以 wait/signal 内部对 S 的读写必须互斥执行。

编者注（这就是"原子性"的需求）：

wait/signal 本身是用来实现互斥的工具，所以 wait/signal 内部不能再用 wait/signal 来保护 S（自指悖论）。必须用更底层的机制——如开/关中断、test-and-set 硬件指令、禁止抢占等。本题考的就是用"开/关中断"来实现这个底层互斥。

（2）方法 1 vs 方法 2

方法 1：错误

致命问题：当 S ≤ 0 时，进入 while (S <= 0); 死循环——而此时中断已经被关掉了。

由于中断关闭：

• 时钟中断不会发生 → 当前进程不会被换下 CPU
• 其他进程没有机会运行 → 没有机会调用 signal(S) 让 S > 0
• → S 永远不会变 → while 永远循环 → 整个系统死锁

方法 2：正确

方法 2 的关键改动：循环体内开了一次中断、又关回去。

while (S <= 0) {
    开中断;     // ← 这一行是救命的
    关中断;
}

虽然在"开中断"和"关中断"之间只有极短的窗口，但这个窗口足够让：

• 时钟中断进来 → 触发调度 → 切换到其他进程
• 其他进程执行 signal(S) → S 增加
• 切回本进程 → 重新检查 while 条件 → 退出循环

这样就避免了方法 1 的死锁问题。

方法 1 vs 方法 2 对比

	方法 1	方法 2
关中断范围	整个 wait/signal	关键代码段 + 循环外
S ≤ 0 时	死锁：CPU 占着不让	给中断窗口，能切换
是否正确	❌	✅

编者注（关键理解）：方法 2 的"开 + 立即关"看似冗余，实际是给中断处理一个原子瞬间的精妙设计。这种"刻意留窗口"的技巧在并发编程里很常见——比如自旋锁的 yield、活锁的 sleep 等。

（3）用户程序能否用开/关中断指令实现互斥？

答：不能。

理由：

1. 开/关中断是特权指令（privileged instruction）——CPU 设计上只允许在内核态执行
2. 用户程序运行在用户态，CPU 会拦截特权指令、触发特权违例异常
3. 如果允许用户开/关中断会带来灾难：
   • 恶意用户程序关中断 → 系统失去时钟中断 → 永远死循环，整个系统瘫痪
   • 恶意用户程序长时间关中断 → 影响其他进程响应、影响 I/O

所以临界区互斥在用户态必须用其他机制：

• POSIX semaphores（系统调用进入内核态实现）
• futex / pthread_mutex（混合：无竞争时用户态自旋，有竞争时陷内核）
• test-and-set / compare-and-swap 等原子指令（用户态可用的 CPU 原子指令）

编者注（特权指令小集合）：408 常考的特权指令包括：

• 开 / 关中断（CLI / STI）
• 加载 PSW（程序状态字）
• I/O 端口读写（IN / OUT）
• 修改页表基址寄存器（CR3 / TTBR）
• 加载 IDT / GDT 等描述符表

共同点：都会影响整个系统的状态或安全，所以必须由内核（也就是操作系统）独占。用户态调用这些指令的代码无法运行——这是 CPU 硬件强制的"两态分离"机制。