有限等待互斥与测试和设置

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.

这可以防止两个或多个线程不断抓取锁定而另一个线程或一组线程始终在等待的情况.例如,假设3个线程正在等待相同的锁(线程0,1和2).假设线程0释放锁定,然后线程1抓住它.虽然线程1具有锁定线程0然后尝试再次获取锁定,并且当线程1释放锁定线程时0抓取它而不是线程2.这可能无限重复并且线程2永远不会获得锁定.

在此边界等待算法中,通过使用该waiting数组,不会发生此行为.如果三个线程不断地抓住锁,那么线程ID下一个线程就会接下来,例如线程0将获取并释放锁,然后是线程1,然后是线程2.这是因为每个线程都在等待lock或者它在waiting阵列中的入口成为false.如果另一个线程在线程即将释放锁定时正在等待锁定,则它会设置该waiting条目,而不是lock仅从旋转等待中释放该线程.这可以防止一个或多个线程无限期地等待锁定的病态情况.