使用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);

现在,如果没有将目标设置为TRUE的条件,如何实现互斥？

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

我做了一些搜索,偶然发现了Mithun Acharya和Robert Funderlic(北卡罗来纳州立大学CS系)的论文,其中包含以下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)) ; // do nothing 才能获得锁并进入临界区。（获取锁只是假设的事情，如果能通过while循环就拥有了锁）

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

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

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

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

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

Answer 4

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

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

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