进程互斥的软件实现方法

学习进程互斥的软件实现方法时，我们需要关注每个方法的思想原理、在进入区、退出区都做了什么、以及他们的优缺点。

单标志法

思想：进程访问完临界资源后会把使用临界资源的权限主动转让给另一个进程。即每个进程进入临界区的权限只能被另一个进程赋予。

如下所示

进入区做的事情：判断允许进入临界区的进程是不是自己（自己是否有资源的占有权），不是则忙等。

退出区做的事情：将进入临界区的权限让给其他进程。

turn 的初值为 0，即刚开始只允许 0 号进程进入临界区。

若 P1 先上处理机运行，则会一直卡在 ⑤。直到 P1 的时间片用完，发生调度，切换 P0 上处理机运行。

代码 ① 不会卡住 P0，P0 可以正常访问临界区，在 P0 访问临界区期间如果切换回 P1，P1依然会卡在 ⑤。

只有 P0 在退出区将 turn 改为 1 后，P1才能进入临界区。

单标志法的问题在于：如果一开始允许进入临界区的进程是P0（即turn=0），但进程P0此时不需要访问临界资源而是在做别的事情，因此不会执行代码1~4。那么P1会一直被卡在代码5的循环，无法使用到资源。

因此 单标志法违背了 “空闲让进” 原则，让资源无故闲置也不分配给需要该资源的其他进程。

双标志先检查法

设置一个布尔型数组 flag[]，数组元素表示各进程想要进入临界区的意愿，每个进程在使用资源之前先检查是否有别的进程想进入临界区。如果没有则将自身对应的标志 flag[i]置为true，并开始访问临界区；有则先让其他进程使用。

由于进程P0和P1是并发执行，因此1~4和5~8 的执行顺序是无序的，因此我们需要考虑1~4和5~8 以任意顺序执行是否会引发问题。

结果若按照 ①⑤②⑥③⑦….的顺序执行，P0 和 P1 将会同时访问临界区。

因此 双标志先检查法 违反了 “忙则等待” 原则。出现这个问题的根本原因是进入区代码的“检查” 和 “上锁” 两个动作不是一气呵成的，“检查”后，“上锁”前可能发 生进程切换。

双标志后检查法

思想：和双标志先检查法的思想基本一致，不同的地方在于，后检查法是 先“上锁” 后 “检查”。

若按照 ①⑤②⑥….的顺序执行，P0 和 P1 将都无法进入临界区。

因此，双标志后检查法虽然解决了“忙则等待”的问题，但是又违背了 “空闲让进” 和 “有限等待” 原则。

两个进程都争着想进入临界区，但是谁也不让谁，最后谁都无法进入临界区。

Peterson 算法

思想：结合双标志后检查法和单标志法，本进程使用资源前，判断对方是否有想使用资源，而且资源的使用权利是否已经让出给对方，如果不是则自己使用资源，是则让对方使用资源。

Peterson算法已经遵循了空闲让进、忙则等待和有限等待原则，但未遵循让权等待的原则，会出现忙等（前3种软件方法也未遵循让权等待原则）。

进程互斥的硬件实现方法

中断屏蔽

利用 “开/关中断指令”实现互斥。关中断和开中断之间的代码就是临界区，由于关中断后CPU会屏蔽中断，而进程切换依赖于中断，因此可以保证关中断和开中断之间的临界区在执行时不会切换到其他进程，其他进程就不会访问到这个临界区，避免了资源竞争。

优点：简单、高效

缺点：关中断只能让执行关中断指令的CPU屏蔽中断，如果计算机有多个CPU，进程A1和A2在CPU1运行，进程B1和B在CPU2上运行，中断屏蔽机制只能保证 A1 和 A2之间是互斥的，B1和B2之间是互斥的，但A1和B1可能同时访问到临界区。

因此中断屏蔽作为互斥方法不适合运行在多处理机的进程；

此外，开/关中断指令只能运行在内核态（因为用户进程使用这种高权限指令不安全），所以中断屏蔽实现互斥只能用于内核进程，不能用于用户进程。

TestAndSet指令

TestAndSet指令是一个执行过程中不可中断的，用硬件方式实现互斥的指令集。简称为 TS指令或者TSL指令。

其逻辑是：检测一个lock变量判断其他进程是否已经进入临界区，无论是与否都将lock置为true（如果之前lock是false表示没有其他进程使用临界资源，因此本进程就可以使用，于是将lock置为true；如果之前lock是true表示有其他进程使用临界资源，置为true没有影响），并返回置为true之前的lock变量是true还是false。

下面是用软件代码实现的TS指令逻辑（实际上不存在这样的软件代码，该逻辑是用硬件实现的）

上锁过程由TestAndSet完成，检查资源是否被占用由用户进程判断。

之前的 双标志检查法 之所以无法完美实现互斥，就是因为 “上锁” 和 “检查” 过程不是原子操作，而TS指令则弥补了这个缺点。

优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞；适用于多处理机环境

缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU循环执行TSL指令，从 而导致“忙等”。

Swap指令

Swap指令也是一个执行过程中不可中断的指令集，其作用是交换两个变量的值，可以用于实现互斥，也可以用在其他地方。在实现互斥上，其逻辑和TestAndSet指令一样，优缺点也和TS指令一样。

old = true 表示，一开始本进程假设临界区已经被占用。

如果 临界区已经被占用，则循环内就不停更新当前临界区的占用状态，再检测一次。

更多内容请关注微信公众号