synchronization - 使用 TestAndSet() 指令进行互斥

Question

Silberschatz、Galvin 和 Gagne 所著的《操作系统原理》一书在同步章节中包含以下 TestAndSet() 指令的定义:

boolean TestAndSet(boolean *target) {
    boolean rv = *target;
    *target = TRUE;
    return rv;
}

还提供了使用上述指令的互斥的实现，如下:

do {
    while(TestAndSetLock(&lock))
        ; // do nothing
        // critical section
    lock = FALSE;
        // remainder section
} while(TRUE);

现在，如果没有条件将target设置为TRUE，如何实现互斥呢？

考虑以下情况，进程 P0 将共享变量 lock 设置为 TRUE 并进入其临界区。另一个进程 P1 在上面的 while 循环中调用 TestAndSet()，它返回 TRUE(因为 P0 拥有锁)，同时无条件将 lock 设置为 FALSE。在 while 循环中第二次调用 TestAndSet() 时，它将返回 FALSE，并且 P1 进入其临界区，即使 P0 位于其临界区中。这样就违反了互斥。

我做了一些搜索，偶然发现了 Mithun Acharya 和 Robert Funderlic(北卡罗来纳州立大学计算机系)的论文，其中包含 TestAndSet() 的以下替代定义:

   boolean Test-and-Set(boolean target)
    begin
        if(target == false):
            target = true;
        return target;
    end

这对我来说更有意义，我将其纳入是为了进行比较，也是因为该论文将 Silberschatz 的书列为引用文献之一。

我只是不明白如何使用我在教科书中找到的定义(我首先提供的定义)来实现互斥，有人可以帮忙吗？

Answer 1

这是一种直观地思考原子 TestAndSet 的方法。

线程在进入临界区之前使用它。只有两种情况:

1. 锁定已被持有(*目标为 TRUE):返回 TRUE 并且*目标保持 TRUE
2. 未持有锁:返回 FALSE，并且 *target 设置为 TRUE

因此，另一个线程位于临界区域，因此 *target (TRUE) 反射(reflect)了该值应该是什么；或“我”现在正在进入这个关键区域，因此将 *target 设置为 TRUE。