具有测试和设置的有限等待互斥

Question

我正在阅读著名的操作系统概念书（Avi Silberschatz、Peter Baer Galvin、Greg Gagne）第 9 版：http://codex.cs.yale.edu/avi/os-book/OS9/

在进程同步章节中，"Bounded-waiting Mutual Exclusion with test_and_set"的算法如下：

do {
    waiting[i] = true;
    key = true;  // <-- Boolean variable that I do not see its utility
    while (waiting[i] && key) // <-- the value of the key variable here is always true
        key = test_and_set(&lock); // <-- it might become false here, but what is the point?
    waiting[i] = false;

    /* critical section */

    j = (i + 1) % n;
    while ((j != i) && !waiting[j]) 
        j = (j + 1) % n; 
    if (j == i) 
        lock = false; 
    else
        waiting[j] = false;

    /* remainder section */
} while (true);

我看不出布尔变量key的作用（在上面代码的第3、4、5行使用），我看我们可以去掉它，对算法，我是对的还是我漏掉了什么？

Answer 1

您可以将算法简化为：

do {
    waiting[i] = true;
    while (waiting[i] && test_and_set(&lock)) ;
    waiting[i] = false;

    /* critical section */

    j = (i + 1) % n;
    while ((j != i) && !waiting[j]) 
        j = (j + 1) % n; 
    if (j == i) 
        lock = false; 
    else
        waiting[j] = false;

    /* remainder section */
} while (true);

而且完全一样。我猜作者使用 key 是因为他们认为这会使代码更易于阅读。

如评论中所问：

通常，当使用 test_and_set 时，您只需执行 while(test_and_set(&lock)) ;。但是在这种情况下，您希望确保线程只等待有限的时间来获取锁。这是通过 waiting 数组完成的。当我们解锁时，在关键部分的末尾，我们不会简单地将 lock 设置为 false，这是您通常解锁它的方式。相反，我们尝试找到下一个正在等待锁的线程。接下来，我的意思是递增线程 ID，然后在我们点击 n（j = (j + 1) % n; 部分）时循环。如果找到这样的线程 j，我们将 waiting[j] 设置为 false 而不是 lock。

这可以防止 2 个或更多线程不断获取锁而另一个线程或线程组始终在等待的情况。例如，假设 3 个线程正在等待同一个锁（线程 0、1 和 2）。假设线程 0 释放了锁，然后线程 1 抓住了它。当线程 1 拥有锁时，线程 0 然后尝试再次获取锁，当线程 1 释放锁时，线程 0 获取它而不是线程 2。这可能会无限期地重复，并且线程 2 永远不会获取锁。

在使用 waiting 数组的边界等待算法中，不会发生这种情况。如果三个线程不断地获取锁，则根据线程 ID 的下一个线程将紧随其后，例如线程 0 将获取并释放锁，然后是线程 1，然后是线程 2。这是因为每个线程都在等待 lock 或其在 waiting 数组中的条目变为 false.如果在一个线程即将释放锁时另一个线程正在等待锁，它会设置 waiting 条目而不是 lock 仅从自旋等待中释放该线程。这防止了一个或多个线程无限期等待锁的病态情况。

具有测试和设置的有限等待互斥

Bounded-waiting Mutual Exclusion with test and set

synchronization

operating-system

locking

mutual-exclusion