硬件同步
在"硬件同步"一节中，我们将探索更多解决临界区问题的方法，这些方法涵盖了应用程序员可用的硬件和软件 API 等技术。这些解决方案都基于锁定的前提;然而，此类锁定的设计可能非常复杂。
这些硬件特性可以使任何编程任务变得更容易，并提高系统效率。本文将介绍一些在许多系统上都可用的简单硬件指令，并展示如何有效地使用它们来解决临界区问题。如果我们能够在修改共享变量时阻止中断发生，那么临界区问题在单处理器环境中就可以轻松解决。通过这种方式，我们可以确保当前指令序列能够按顺序执行，而不会被抢占。由于不会运行其他指令，因此不会对共享变量进行任何意外的修改。这是非抢占式内核采用的方法。但遗憾的是，这种解决方案在多处理器环境中并不可行。由于消息会传递到所有处理器，因此在多处理器上禁用中断可能会非常耗时。
当这种消息传递延迟进入每个临界区时，系统效率会降低。此外，如果时钟通过中断保持更新，则需要考虑对系统时钟的影响。因此，许多现代计算机系统都提供了特殊的硬件指令，使我们能够测试和修改一个字的内容，或者以原子方式(即作为一个不可中断的单元)交换两个字的内容。我们可以使用这些特殊指令以相对简单的方式解决临界区问题。现在，我们抽象出这些指令类型背后的主要概念。TestAndSet() 指令的定义如下代码所示。
boolean test and set(boolean *target){
boolean rv = *target;
*target = true;
return rv;
}
test and set() 指令的定义。
该指令的核心特性是原子执行。因此，如果两个 TestAndSet (C) 指令同时执行(分别在不同的 CPU 上)，它们将以任意顺序依次执行。如果机器支持 TestAndSet () 指令，我们可以通过声明一个布尔变量 lock 来实现互斥，并将其初始化为 false。进程 P 的结构如下所示。
示例
do {
while (test and set(&lock)) ;
/* 不执行任何操作 */
/* 临界区 */
lock = false;
/* 剩余区 */
}
while (true);
使用 test 和 set() 实现互斥。
与 TestAndSet0 指令不同，SwapO 指令操作两个字的内容;它是原子执行的。如果机器支持 SwapO 指令，则可以按如下方式实现互斥。这里，声明一个全局布尔变量 lock 并将其初始化为 false。此外，每个进程都有一个局部布尔变量 key。进程 P 的结构如下图所示。
int compare_and_swap(int *val, int expected, int new val){
int temp = *val;
if (*val == expected)
*val = new val;
return temp;
}
compare and swap() 指令的定义。
do{
while (compare_and_swap(&lock, 0, 1) != 0);
/* 不执行任何操作 */
/* 临界区 */
lock = 0;
/* 剩余区 */
}
while (true);
使用 compare and swap() 指令实现互斥。
由于这些算法满足互斥要求，因此它们不满足有界等待要求。在下面的代码中，我们展示了另一种使用 TestAndSet() 指令的算法，该算法满足所有临界区要求。
do{
waiting[i] = true;
key = true;
while (waiting[i] && key)
key = test and set(&lock);
waiting[i] = false;
/* critical section */
j = (i + 1) % n;
while ((j != i) && !waiting[j])
j = (j + 1) % n;
if (j == i)
lock = false;
else
waiting[j] = false;
/* remainder section */
}
while (true);
使用 test 和 set() 实现有界等待互斥。
相同的数据结构是 boolean waiting[n]; boolean lock; 这些数据结构被初始化为 false。为了证明满足互斥要求，我们注意到进程 P; 只有在 waiting[i] == false 或 key -- false 的情况下才能进入其临界区。只有执行 TestAndSet() 时，key 的值才会变为 false。第一个执行 TestAndSet() 的进程将发现 key == false;所有其他进程都必须等待。只有当另一个进程离开其临界区时，变量 waiting[i] 才会变为 false;只有一个 waiting[i] 被设置为 false，从而保持互斥要求。
为了证明满足进度要求，我们注意到关于互斥的论点也适用于此，因为退出临界区的进程要么将 lock 设置为 false，要么将 waiting[j] 设置为 false。这两种方法都允许等待进入其临界区的进程继续进行。为了证明有界等待要求得到满足，我们注意到，当一个进程离开其临界区时，它会扫描循环顺序 (z' + 1, i + 2,..., n — 1, 0, ..., i — 1) 中的 waiting 数组。它将此顺序中第一个位于入口段 (waiting [j] =- true) 的进程指定为下一个进入临界区的进程。
因此，任何等待进入其临界区的进程都将在 n — 1 个回合内完成。遗憾的是，对于硬件设计人员来说，在多处理器上实现原子 TestAndSet() 指令并非易事。
