使用TestAndSet()指令的互斥

Question

Silberschatz、加尔文和加涅的“操作系统原则”一书在关于同步的一章中包含了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);

现在，如果没有设定目标为真的条件，如何实现互斥呢？

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

我进行了一些搜索，偶然发现了一篇由Mithun和Robert (来自北卡罗莱纳州立大学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，*目标设置为TRUE

因此，另一个线程在关键区域So *target ( TRUE )中反映了应该是什么值；或者"I“现在正在进入这个关键区域，因此将*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

我认为“行动纲领”将其误解为：

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

因为明显的原因而不能正常工作。

Answer 3

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

最初*目标将是假的。(这是一个给定的)。的确，P需要通过while(TestAndSetLock(&lock)) ; // do nothing获得锁并输入关键部分。(获得锁只是一件假设的事情，如果它能够通过while循环，那么它就有了锁)

有人有锁意味着目标是真正的__，锁是自由采取的是目标是假__。一开始是这样的，

​

​

​

​

P1 (第一个调用函数就会得到幸运)，他看到目标为FALSE，并将其设置为true并返回FALSE，从而避免了while循环的等待。

​

​

​

​

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

其他P会来看看目标是真，当调用TestAndSet(boolean_ref lock)时，它总是返回TRUE，直到P1将目标设置为false为止。

​

​

​

​

​

​

​

​

​

​

​

​

​

​

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