operating-system - 带测试和集合的有界等待互斥

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

我看不到 bool 变量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仅从自旋等待中释放该线程。这可以防止一个或多个线程无限期等待锁的病态情况。