上一节是一个基于软件的临界区问题的解决方案。

所有这些解决方案都基于锁的前提，即通过使用锁保护临界区。如我们所见，这种锁的设计相当复杂。

通过要求临界区用锁来保护，就可以避免竞态条件。即一个进程在进入临界区之前必须得到锁，而在退出临界区后要释放锁。

在单核环境下，临界区问题比较好解决：在修改共享变量时禁止中断出现。这样，就可以保证当前指令序列可以顺序的执行，而不会被强占。而由于其他指令不可能执行，所以共享变量不会被意外修改。这种方法常为非抢占式内核采用。

上述方案在多核系统中是不可行的。在多处理器上因为消息需要传递给所有的处理器，所以禁用中断可能会耗费大量时间。这种消息传递消导致进入每个临界区都会延迟，进而降低系统效率。而且该方法影响了系统时钟（如果时钟是通过终端来加以更新的话）。

现代计算机系统提供了特殊的硬件指令以允许原子的（不可中断地）检查和修改字的内容患者交换两个字的内容

允许我们测试和修改一个字的内容，或者将两个字的内容以原子的方式交换——即，作为一个不可中断的单元。我们可以用这些特殊的指令，以相对简单的方式解决临界区问题。我们并不讨论特定机器的特定指令，而是通过描述test_and_set()和compare_and _swap()指令来抽象这些类型指令背后的主要概念。

test_and_set()

compare_and_swap()

boolean test and set(boolean *target) {
    boolean rv = *target;
    *target = true;
    return rv;
}
图5-3 test_and_set()指令的定义

do {
    while (test and set(&lock))
        ; /* do nothing */
    /* critical section */
    lock = false;
    /* remainder section */
} while (true);
图5-4 使用test_and_set()指令实现互斥

test_and_set()指令可以像图5.3这样定义。该指令的重要特征是它是原子执行的。因此，如果两个test_and_set()指令同时执行(每个指令都在不同的CPU上)，它们将按顺序依次执行。如果机器支持test_and_set()指令，那么我们可以通过声明布尔变量锁来实现互斥，该布尔变量初始化为false。过程Pi的结构如图5.4所示。

int compare and swap(int *value, int expected, int new value) {
    int temp = *value;
    if (*value == expected)
        *value = new value;
    return temp;
}
图5-5 compare_andswap()指令的定义

do {
    while (compare and swap(&lock, 0, 1) != 0)
        ; /* do nothing */
    /* critical section */
    lock = 0;
    /* remainder section */
} while (true);
图5-6 使用compare_andswap()指令实现互斥锁

与test_and_set()相比，compare_andswap()操作两个数据，其定义如图5-5所示。只有在表达式(*value == exected)为真时，操作数值才被设置为new_value。无论如何，compare_and_swap()总是返回变量值的原始值。就像test_and_set()指令，compare_and_swap()也是原子执行的。互斥可以像下面这样实现：一个全局变量(lock )被声明并初始化为0。调用compare_and_swap()的第一个进程将lock设置为1。然后它会进入它的临界区，因为lock变量原来的值等于0。随后对compare_and_swap()的调用将不会成功，因为锁现在不等于期望值0。当一个进程退出它的临界区时，它将lock设置回0，这允许另一个进程进入它的临界区。过程Pi的结构如图5.6所示。

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);
Figure 5.7 使用test_and_set()实现具有限界等待额互斥锁

虽然这些算法满足了互斥的要求，但它们不能满足限界等待。在图5.7中，我们提出了另一种算法，它使用test_and_set()指令来满足临界区的所有需求。共用的数据结构是：

boolean waiting[n];
boolean lock;