Mutual Exclusion Implementations

同步与互斥

并发进程有异步性：各进程以各自独立、不可预知的速度推进。异步本身不是错误，但如果进程之间存在共享数据、共享设备或先后依赖，操作系统就要提供同步互斥机制。

同步解决先后顺序问题。互斥保证不能同时访问的资源访问不出问题。

概念	关注点	典型问题	制约关系
进程同步	进程之间的执行先后	B 必须等 A 产生数据后才能继续处理	直接制约
进程互斥	同一资源不能同时访问	A 使用打印机时，B 不能同时使用同一打印机	间接制约

同步的关键是某个动作必须发生在另一个动作之后。例如进程 A 先对缓冲区数据预处理并写回，进程 B 再读取处理后的数据。若 B 提前读取，就会得到旧数据或未处理数据。

互斥的关键是同一时刻最多一个进入。例如打印机、摄像头、某些共享变量、内存缓冲区，都可能在一个时间段内只允许一个进程使用。

临界资源与临界区

临界资源是一个时间段内只允许一个进程使用的资源。它可以是物理设备，也可以是共享变量、共享数据结构或缓冲区。

临界区是进程中访问临界资源的那段代码，也称临界段。

一次互斥访问在逻辑上分为四段：

Pi 进程：
entry section;
{                    // 进入区
	critical section; // 临界区
}    
exit section;        // 退出区
remainder section;   // 剩余区

部分	作用
进入区	检查是否可以进入临界区；若可以进入，设置正在访问临界资源的标志
临界区	真正访问临界资源的代码
退出区	清除访问标志，释放临界资源
剩余区	不访问该临界资源的其他代码

Warning

进入区、退出区不是临界区的一部分。它们是为了实现互斥而设置的控制代码；临界区才是真正访问临界资源的代码。

普通临界区与内核临界区

普通临界区不等于禁止调度；内核程序临界区才是不能调度与切换的典型场景。

类型	访问对象	是否能进行进程调度	原因
普通临界区	普通临界资源，如打印机、摄像头、用户共享缓冲区	可以	这些资源通常不直接影响操作系统内核的调度数据结构
内核程序临界区	内核数据结构，如就绪队列、PCB 队列	通常不能	调度程序本身可能也要访问这些内核数据结构

普通临界区中可以发生调度。比如进程正在等待打印机完成，如果一直不允许调度，CPU 可能长期空闲。

内核程序临界区通常不能随便调度。比如内核代码正在修改就绪队列，还没解锁就切换到调度程序，而调度程序也需要访问就绪队列，就会影响内核管理工作的正确性。因此内核临界区应尽快执行完，再允许调度。

互斥原则

原则	含义	违反后的问题
空闲让进	临界区空闲时，请求进入的进程应能立即进入	资源空着却没人能用
忙则等待	已有进程在临界区时，其他进程必须等待	多个进程同时访问临界资源
有限等待	请求进入临界区的进程应在有限时间内进入	进程可能饥饿
让权等待	不能进入临界区时，应释放处理机(效率考虑，实现互斥非必须遵循)	忙等浪费 CPU

互斥实现

1. 进入区做什么：如何检查临界区是否可进入，如何表达“我要进入”。
2. 退出区做什么：如何释放临界区，如何让其他进程继续。
3. 是否违反某原则：空闲让进、忙则等待、有限等待、让权等待中哪条做不到。

软件方法完全依靠普通变量和程序执行顺序。硬件方法把某些关键动作做成不可中断的原子操作。

下面均以两个进程 $P_0$、$P_1$ 竞争同一个临界资源为例。

软件实现方法

方法	共享变量	进入区核心动作	退出区核心动作	主要问题
单标志法	turn	只允许 turn == i 的进程进入	把 turn 改成对方编号	必须轮流进入，违反空闲让进
双标志先检查法	flag[2]	先检查对方意愿，再设置自己意愿	清除自己意愿	检查后、上锁前可被切换，违反忙则等待
双标志后检查法	flag[2]	先设置自己意愿，再检查对方意愿	清除自己意愿	双方都先上锁时会互相等待，违反空闲让进和有限等待
Peterson 算法	flag[2]、turn	先表达意愿，再主动谦让，再检查	清除自己意愿	前三条原则满足，但仍忙等，违反让权等待

单标志法

单标志法使用一个共享变量 turn，表示当前允许哪个进程进入临界区。

P0 进程：
while (turn != 0);
critical section;     // 临界区
turn = 1;             // 退出区
remainder section;    // 剩余区

P1 进程：
while (turn != 1);
critical section;     // 临界区
turn = 0;             // 退出区
remainder section;    // 剩余区

如果 turn 初值为 0，那么 $P_0$ 可以先进入。$P_0$ 退出时把 turn 改成 1，于是下一次只能 $P_1$ 进入。

它能保证同一时刻最多一个进程进入临界区，但代价是必须严格轮流。若 turn == 0，而 $P_0$ 暂时不想进入临界区，$P_1$ 即使想进入也只能等待。临界区明明空闲，却不允许请求者进入，所以违反空闲让进。

双标志先检查法

双标志先检查法用 flag[i] 表示 $P_i$ 是否想进入临界区。进入区先检查对方是否想进入；若对方不想进入，再把自己的 flag 置为 true。

P0 进程：
while (flag[1]);
flag[0] = true;
critical section;     // 临界区
flag[0] = false;      // 退出区
remainder section;    // 剩余区

P1 进程：
while (flag[0]);
flag[1] = true;
critical section;     // 临界区
flag[1] = false;      // 退出区
remainder section;    // 剩余区

问题出在“检查”和“上锁”不是一个原子动作。

↻ + −

一种可能的交错执行顺序是：

1. $P_0$ 检查 flag[1] == false，通过检查。
2. 还没来得及执行 flag[0] = true，发生进程切换。
3. $P_1$ 检查 flag[0] == false，也通过检查。
4. 两个进程随后分别把自己的 flag 置为 true，并进入临界区。

因此，双标志先检查法可能让两个进程同时进入临界区，违反忙则等待。

双标志后检查法

双标志后检查法把顺序反过来：先进场声明“我要进入”，再检查对方是否也想进入。

P0 进程：
flag[0] = true;
while (flag[1]);
critical section;     // 临界区
flag[0] = false;      // 退出区
remainder section;    // 剩余区

P1 进程：
flag[1] = true;
while (flag[0]);
critical section;     // 临界区
flag[1] = false;      // 退出区
remainder section;    // 剩余区

这种做法避免了“检查通过后还没上锁”的漏洞，但会出现另一个问题：双方都先把自己的 flag 置为 true。

↻ + −

当 $P_0$ 设置 flag[0] = true 后被切换，$P_1$ 又设置 flag[1] = true。此后 $P_0$ 检查到 flag[1] == true，$P_1$ 检查到 flag[0] == true，双方都在等待对方清除标志。

此时临界区没有任何进程在使用，却没有进程能进入，所以违反空闲让进；若双方长期卡住，也违反有限等待。

Peterson 算法

Peterson 算法把双标志法的“表达意愿”和单标志法的“谦让”结合起来。

P0 进程：
flag[0] = true;
turn = 1;
while (flag[1] && turn == 1);
critical section;     // 临界区
flag[0] = false;      // 退出区
remainder section;    // 剩余区

P1 进程：
flag[1] = true;
turn = 0;
while (flag[0] && turn == 0);
critical section;     // 临界区
flag[1] = false;      // 退出区
remainder section;    // 剩余区

进入区的含义是：

• flag[i] = true：我想进入临界区。
• turn = j：如果对方也想进入，我愿意让对方先进入。
• while (flag[j] && turn == j)：对方确实想进入，而且最后一次谦让是我做出的，那我等待。

↻ + −

为什么Peterson算法能避免前面算法的问题？

Peterson 算法不会让两个进程同时进入，关键在于 turn 是单个共享变量。双方都想进入时，flag[0] 和 flag[1] 都为 true，但 turn 最终只能等于 0 或 1。

• 若 turn == 1，$P_0$ 的等待条件 flag[1] && turn == 1 成立，$P_0$ 等待；$P_1$ 的等待条件 flag[0] && turn == 0 不成立，$P_1$ 进入。
• 若 turn == 0，$P_1$ 等待，$P_0$ 进入。
  因此，两个等待条件不可能同时为假，两个进程不可能同时越过进入区；也不可能同时为真，因为 turn 不可能同时等于 0 和 1。

若只有 $P_0$ 想进入，flag[1] == false，$P_0$ 不会等待，满足空闲让进。若 $P_0$、$P_1$ 都想进入，后写入 turn 的进程相当于最后一次表示谦让，它会等待；另一个进程可以进入。因此 Peterson 算法能满足空闲让进、忙则等待、有限等待。

但等待者仍然停在 while 循环中反复检查条件，占用 CPU，所以不满足让权等待。

硬件实现方法

软件方法的根本困难是：普通语句之间可能发生进程切换。硬件方法让某些关键指令在执行期间不可被中断，从而得到原子性。

中断屏蔽方法

中断屏蔽方法在进入临界区前关中断，退出临界区后开中断。

关中断;
critical section;     // 临界区
开中断;
remainder section;    // 剩余区

关中断后，当前处理机不会因为中断而转入中断处理程序，也就不会在临界区中发生由中断引起的进程切换。这样能保证当前进程完整执行临界区。

这种方法简单、高效，但限制很明显：

• 不适用于多处理机。一个处理机关中断，并不能阻止其他处理机上的进程访问同一临界资源。
• 不适用于用户进程。开中断、关中断属于特权指令，不能让用户程序随意执行。

TestAndSet / TSL 指令

TestAndSet 也称 TS、TSL 或 TestAndSetLock。它把“读取旧锁值”和“设置新锁值”合成一个不可分割的硬件动作。

TestAndSet(lock):
	old = lock;
	lock = true;
	return old;

用 TSL 实现互斥时，lock == false 表示临界区未上锁，lock == true 表示临界区已上锁。

while (TestAndSet(lock))
	;
critical section;     // 临界区
lock = false;         // 退出区
remainder section;    // 剩余区

若 lock 原来是 false，TSL 返回 false，循环结束，进程进入临界区。同时 TSL 已经把 lock 改成 true，后续进程会被挡住。

若 lock 原来是 true，TSL 返回 true，进程继续在 while 中循环等待。

TSL 的优点是实现简单，并且适用于多处理机；缺点是等待者会持续占用 CPU，属于忙等，不满足让权等待。

Swap / XCHG 指令

Swap 也称 Exchange 或 XCHG。它的原子动作是交换两个变量的值。

Swap(a, b):
temp = a;
a = b;
b = temp;

用 Swap 实现互斥时，进程先准备一个局部变量 key = true，然后不断把 key 与共享锁变量 lock 交换。

key = true;
while (key == true)
    Swap(lock, key);
critical section;     // 临界区
lock = false;         // 退出区
remainder section;    // 剩余区

若 lock 原来是 false，交换后 key 变成 false，循环结束；同时 lock 变成 true，临界区被上锁。若 lock 原来是 true，交换后 key 仍为 true，进程继续忙等。

从互斥效果看，Swap 与 TSL 的作用类似：都用硬件原子动作完成“检查并上锁”。因此它同样实现简单、适用于多处理机，也同样不满足让权等待。

互斥锁与自旋锁

互斥锁把“进入区申请锁、退出区释放锁”封装成acquire(lock)和release(lock)两个操作

acquire(lock);
{
	critical section;     // 临界区
}
release(lock);
remainder section;    // 剩余区

如果 acquire(lock) 在锁已被占用时反复循环检查，而不是阻塞当前进程，这种锁就是自旋锁。TSL、Swap 这类硬件原语常用来实现自旋锁。

自旋锁的特点是：

• 等待期间不发生进程阻塞和唤醒，也就没有上下文切换开销。
• 等待者会一直占用 CPU，违反让权等待。
• 在多处理器系统中，如果临界区很短，一个处理器自旋等待，另一个处理器很快释放锁，代价可能低于阻塞和唤醒。
• 在单处理机系统中，自旋通常不合适。等待者占着处理机反复检查，而持锁进程无法运行并释放锁。

互斥锁不一定都采用忙等。若锁不可用时，系统让进程阻塞并把 CPU 让给其他进程，这类实现就符合让权等待；代价是需要进程切换、阻塞队列管理和唤醒。

方法对比

方法	能否保证互斥	是否让权等待	适用特点
单标志法	能	否	逻辑简单，但强制轮流，资源空闲也可能进不去
双标志先检查法	不能稳定保证	否	检查和上锁之间可被切换
双标志后检查法	能避免同时进入	否	可能双方都等待，临界区空闲也进不去
Peterson 算法	能	否	软件算法中较完整，但仍忙等
中断屏蔽	能，限单处理机内核场景	不适用	简单高效，但不能给用户进程使用
TSL / Swap	能	否	原子检查并上锁，适合多处理机，但忙等
阻塞式互斥锁	能	是	等待时释放 CPU，但有上下文切换开销