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 将共享变量锁设置为 TRUE 并进入其临界区。另一个进程 P1 在上面的 while 循环中调用 TestAndSet()，它返回 TRUE（因为 P0 有锁），同时无条件地将锁设置为 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 的书列为参考文献之一。

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

score 17 · Accepted Answer

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

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

锁定被持有（*target 为 TRUE）：返回 TRUE 并且 *target 保持 TRUE
未持有锁：返回 FALSE，*target 设置为 TRUE

所以要么另一个线程在临界区，所以 *target (TRUE) 反映了值应该是什么；或者“我”现在正在进入这个关键区域，所以将 *target 设置为 TRUE。

score 6 · Accepted Answer

所示的实现可以更清楚地写成这样：

while(TestAndSet(&lock))
{
   // spin in this loop until TestAndSet returns false
}
do_critical_section_stuff();
lock = FALSE;
// We've now left the critical section

我认为OP将其误解为：

while(TestAndSet(&lock))
{
   lock = FALSE;
}
do_critical_section_stuff();

由于明显的原因，它无法正常工作。

score 5 · Accepted Answer

啊，我也有这个问题。让我分享一下我的理解。

最初 *target 将为 FALSE。（这是给定的）。P确实需要通过while(TestAndSetLock(&lock)) ; // do nothing 才能获得锁并进入临界区。（获得锁只是一个假设的事情，如果它可以通过while循环，那么它就有了锁）

有人有锁意味着目标是TRUE，锁定是免费的，目标是FALSE。所以一开始是这样的

P1（第一个调用该函数的人会很幸运），他看到目标是 FALSE 并将其设置为 true 并返回 FALSE，这导致它避免了 while 循环等待。

现在目标是 TRUE.Other 事实是TestAndSet(boolean_ref lock) 将返回被调用的值，并且TestAndSet(boolean_ref lock)将始终将目标设置为TRUE ，因此必须在其他地方将目标设置为 FALSE（所以带有lock 可以将其设置为 FALSE）

其他 P 会看到 target 为 TRUE，并且在调用TestAndSet(boolean_ref lock)它时将始终返回 TRUE，直到 P1 将 target 设置为 false。

我从这个网站找到了这个很好的图形解释，你可以从这里下载

score 3 · Accepted Answer

您最初引用的 TestAndSet 函数仅在 target 为 false 时执行。即线程阻塞直到目标为假。我没有那本教科书，但我确定它在文中某处提到过。

请注意，TestAndSet 是一个“原子”函数，必须在操作系统的最低级别（甚至是 CPU 的指令集）中实现。如果它是在用户应用程序中实现的，则可能会在测试和集合之间发生上下文切换，从而导致损坏。

澄清：我只确定函数在 target 为 false 时执行的事实，因为在某处这些必须是阻塞的比较操作。有两种类型的TestAndSet - 一种仅在目标设置为True（阻塞）时返回，另一种可能返回False，即立即返回（一种将启用另一个线程的轮询）。我假设您引用的那个是阻塞的，因为它似乎在开始执行后立即返回，这意味着“IF”语句由较低级别的机制执行，例如 CPU 或 OS 内核。

score 1 · Accepted Answer

要使用 testAndset 方法，我们从一个名为 Lock 的变量开始，该变量设置为 false：

HdwareData lock = new HdwareData(false);

score 0 · Accepted Answer

非线性思考。您在 Silberchatz 为实现testAndSet()函数而提供的定义中指出了三个问题：

（1）您正确地指出目标无条件设置为 TRUE，并且（错误地）意识到这是一个问题。

(2) 为了解决 (1) 中的问题（不存在），您建议在将目标设置为 TRUE 之前对其进行测试。

(3) 最后，您对实现互斥的块也无条件地将result设置为 FALSE表示了担忧（这实际上并没有发生）。

我将尝试澄清这些问题。最初，请注意函数TestAndSet()所做的第一件事是将target的值复制到rv，然后才将 target无条件设置为 TRUE。现在，问题是：如果target最初为 FALSE，TestAndSet()将target设置为 TRUE 并返回 FALSE，因此进程可以进入临界区。如果原始目标值为 TRUE，则无论如何都将其设置为 TRUE（这不会造成伤害）并且TestAndSet()返回 TRUE，因此进程无法进入临界区。所以，设定目标无条件地为 TRUE 不是问题，问题 (1) 证明不存在。

关于问题（2），一旦上面证明无条件设置target为TRUE是无害的，就不需要事先测试它的值。

问题 (3) 也不存在，因为结果并没有真正无条件地设置为 FALSE。我的意思是，它是，但只有在关键区域被进程处理之后；即，当不再需要互斥时。进程一离开临界区就必须将目标设置为 FALSE（退出临界区后不应阻塞任何其他进程）。处理临界区后强制释放锁！

score 0 · Accepted Answer

通过查看TestAndSet(&lock)互斥的实现，可以肯定地说，只要TestAndSet返回true，进程(P)就不会进入其临界区。该进程将继续在其循环条件中执行，直到它（条件）失败。

只要另一个进程锁定资源，条件就会成功（TestAndSet 将返回 true）。当另一个进程对该资源进行了锁定时，lock 的值为 true。一旦其他进程释放它对资源的持有，通过设置 lock = false，TestAndSet 将返回 false。

当 TestAndSet 返回 false 时，while 循环的条件失败，因此进程 P 进入其临界区。

TestAndSet 是一个原子操作，即它的执行没有中断。这样做是为了防止与锁的竞争条件。

score 0 · Accepted Answer

在您的问题中考虑以下突出显示的部分：

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

P1（或任何进程），无论 lock 是 True 还是 False，都不会将 lock 的值设置为 False。

如果锁的值为 False，则进入临界区并将其值设置为 True，从而获取锁。
如果锁定值为 True，它什么也不做（将其值设置为 True，因此不会更改它）并等待锁定值变为 False（当拥有锁定的进程完成其关键部分的执行时会发生这种情况）。

synchronization - 使用 TestAndSet() 指令的互斥

8 回答 8

Related

Reference