使用 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. 锁被持有（*target 为 TRUE）：返回 TRUE 并且 *target 保持 TRUE
2. 锁未被持有：返回 FALSE，并且 *target 设置为 TRUE

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

Answer 2

显示的实现可以写得更清楚，如下所示：

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();

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

Answer 3

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

最初 *target 将为 FALSE。（这是给定的）。
确实，P 需要通过 while(TestAndSetLock(&lock)) ； // 什么都不做
获得锁并进入临界区。 （获得锁只是一个假设的事情，如果能通过while循环那就拥有锁）

有人拥有锁意味着target是TRUE，
如果目标为FALSE，则可以自由获取锁定。
所以一开始是这样的，

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

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

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

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

Answer 4

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

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

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

Answer 5

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

HdwareData lock = new HdwareData(false);

Answer 6

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

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

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

TestAndSet 是一个原子操作，即它的执行不会中断。 这样做是为了防止锁出现竞争情况。

Answer 7

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

(1) 您正确地指出 target 无条件设置为 TRUE，并且实现了（错误地）这是一个问题。

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

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

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

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

问题 (3) 也不存在，因为 result 并未真正无条件设置为 FALSE。 我的意思是，确实如此，但只有在此之后，该进程才处理了关键区域； 即，当不再需要互斥时。 进程一旦离开临界区就必须将 target 设置为 FALSE（退出临界区后不应该阻止任何其他进程）。 处理完临界区后强制释放锁！

Answer 8

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

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

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

• 如果lock is value为False，则进入临界区并将其值设置为True，从而抢到锁。

  如果lock is value为False，

• 如果锁值为 True，则不执行任何操作（将其值设置为 True，从而不更改它）并等待锁值变为 False（当拥有锁的进程完成其关键操作时会发生这种情况）部分）。