题目

现要求学生使用 swap 指令和布尔型变量 lock 实现临界区互斥。lock 为线程间共享的变量：值为 TRUE 时线程不能进入临界区，值为 FALSE 时线程能够进入临界区。

某同学编写的实现临界区互斥的伪代码如题 45(a) 图所示：

bool lock = FALSE;          // 共享变量
...

// ── 进入区 ──
bool key = TRUE;
if (key == TRUE)
    swap key, lock;         // 原子交换 key 和 lock 的值

// ── 临界区 ──
临界区;

// ── 退出区 ──
lock = TRUE;
...

题 45(b) 图给出了"两个变量值的函数 newSwap()"代码：

void newSwap(bool *a, bool *b)
{
    bool temp = *a;
    *a = *b;
    *b = temp;
}

(1) 题 45(a) 图中伪代码中哪些语句存在错误？将其改为正确的语句（不增加语句条数）。

(2) 题 45(b) 图中给出的两个变量值的函数 newSwap() 的代码是否可以用函数调用语句 newSwap(&key, &lock) 代替指令 swap key, lock 以实现临界区的互斥？为什么？

解析

（1）找出 2 处错误并改正

错误 1：进入区的 if 应改为 while

原代码：

bool key = TRUE;
if (key == TRUE)
    swap key, lock;

错在哪？swap 指令把 key 和 lock 的值互换。第一种情况：lock 原本是 FALSE（无人占用），互换后 key=FALSE、lock=TRUE，本进程顺利进入临界区。但第二种情况：lock 原本是 TRUE（有人占用），互换后 key=TRUE、lock=TRUE——此时本进程也跑进临界区了！这就破坏了互斥。

正确做法是：反复 swap 直到拿到 key=FALSE（即原来 lock=FALSE 的那一刻），所以 if 必须改成 while：

bool key = TRUE;
while (key == TRUE)
    swap key, lock;     // 自旋等待，直到 key=FALSE

编者注（易错点）：用 swap 实现的锁本质上是自旋锁——拿不到锁就一直转圈试。if 是"问一次"，while 是"问到拿到为止"，两者差一个字符但语义天差地别。

错误 2：退出区的 lock = TRUE 应改为 lock = FALSE

原代码：

lock = TRUE;     // 错！这是设置"被占用"

退出临界区时应该释放锁——把 lock 设回 FALSE，让别的进程能进。原代码把它设成 TRUE，等于"出门时反把门反锁了"，从此再没人能进临界区，死锁。

lock = FALSE;     // 正确：释放锁

编者注（易错点）：lock 的语义题面写得很清楚——TRUE = 不可进，FALSE = 可进。考场上看到自己写的代码"释放锁却赋 TRUE"，停下来核对一下变量含义，避免顺手写反。

修正后的完整进入区 / 退出区

// 进入区
bool key = TRUE;
while (key == TRUE)
    swap key, lock;

// 临界区
临界区;

// 退出区
lock = FALSE;

（2）能否用 newSwap(&key, &lock) 代替 swap key, lock？

答：不能。

核心原因：swap 是一条硬件原子指令（CPU 一个总线事务里完成"读 a → 读 b → 写 a → 写 b"，中途不会被中断、也不会被其它 CPU 插队）。而 newSwap() 是普通 C 函数，里面 temp=*a; *a=*b; *b=temp; 是 3 条独立的 store/load 语句，不具备原子性。

举一个反例（线程交错导致两个线程同时进临界区）

设初始 lock=FALSE。两个线程 T1、T2 同时执行进入区：

时刻	T1 执行	T2 执行	lock	T1 的 key	T2 的 key
t0	key = TRUE		F	T	—
t1		key = TRUE	F	T	T
t2	进 newSwap：temp = *a（temp=T）		F	T	T
t3	*a = *b（key 变 F）		F	F	T
t4		进 newSwap：temp = *a（temp=T）	F	F	T
t5		*a = *b（key 变 F）	F	F	F
t6	*b = temp（lock 变 T）		T	F	F
t7		*b = temp（lock 变 T）	T	F	F
t8	跳出 while（key=F）→ 进临界区	跳出 while（key=F）→ 进临界区	T	F	F

t8 时刻两个线程都拿到 key=FALSE，同时进入临界区——互斥失效。

编者注（易错点 / 答题套路）：

• 这类题的"标答模板"：先指出 swap 是原子指令、newSwap 是非原子函数；再举一组交错执行使两线程同时进临界区。光说"newSwap 不是原子的"只能拿一半分，构造交错时序才完整。
• 表格里 t2~t5 是关键：T1 还没把新 key 写回 lock 时，T2 就读到了还是旧 lock=F，从而也把它的 key 改成 F。这正是"中途被插入"破坏原子性的典型病灶。
• 现实中要给软件实现的 swap "续命"，必须在外层套一个真正原子的机制——禁中断（单核）/ test-and-set 指令 / 编译器 atomic 内建，newSwap() 本身不行。