彼得森算法是否满足饥饿问题？

Question

我一直在搜索Peterson算法的信息，但是遇到了一些引用说它不能解决饥饿问题，只能解决死锁问题。这是真的吗？如果是，有人可以详细说明为什么吗？

Peterson算法：

flag[0]   = 0;
flag[1]   = 0;
turn;

P0: flag[0] = 1;                                       
    turn = 1;                                               
    while (flag[1] == 1 && turn == 1)                        
    {                                                       
           // busy wait                                             
    }                                                                                      
    // critical section                                     
       ...                                                     
    // end of critical section                              
    flag[0] = 0;   

P1: flag[1] = 1;                                       
    turn = 0;                                               
    while (flag[0] == 1 && turn == 0)                        
    {                                                       
           // busy wait                                             
    }                                                                                      
    // critical section                                     
       ...                                                     
    // end of critical section                              
    flag[1] = 0;

算法使用两个变量，flag和turn。flag值为1表示进程想要进入临界区。变量turn保存了该轮到哪个进程执行的进程ID。如果P1不想进入其临界区或者P1通过将turn设置为0来优先考虑P0，则允许P0进入临界区。

- IZI_Shadow_IZI

---

如果您正在提问，请为那些不熟悉您所谈论的主题提供更多背景信息。这是什么样的算法？它是做什么的？您的确切问题是什么？如果您这样做，社区将非常感激。 - Tomasz Kowalczyk

Answer 1

正如Ben Jackson所怀疑的那样，问题出在一个泛化算法上。标准的2进程Peterson算法满足无饥饿属性。

显然，Peterson的原始论文实际上有一个N处理器的算法。这里是我刚写的一个类似C ++语言的草图，据说是这个算法：

// Shared resources
int pos[N], step[N];

// Individual process code
void process(int i) {
    int j;
    for( j = 0; j < N-1; j++ ) {
        pos[i] = j;
        step[j] = i;
        while( step[j] == i and some_pos_is_big(i, j) )
            ; // busy wait
    }
    // insert critical section here!
    pos[i] = 0;
}

bool some_pos_is_big(int i, int j) {
    int k;
    for( k = 0; k < N-1; k++ )
        if( k != i and pos[k] >= j )
            return true;
    }
    return false;
}

以下是关于 N = 3 的死锁场景：

• 进程 0 最先启动，设置 pos[0] = 0 和 step[0] = 0，然后等待。
• 接着进程 2 启动，设置 pos[2] = 0 和 step[0] = 2，然后等待。
• 最后进程 1 启动，设置 pos[1] = 0 和 step[0] = 1，然后等待。
• 进程 2 首先注意到 step[0] 的更改，因此设置 j = 1，pos[2] = 1 和 step[1] = 2。
• 进程 0 和 1 被阻塞，因为 pos[2] 较大。
• 进程 2 没有被阻塞，因此它设置 j = 2。然后进入临界区并完成后，它设置 pos[2] = 0，但立即开始争夺临界区，从而设置 step[0] = 2 并等待。
• 进程 1 是第一个注意到 step[0] 更改的进程，并像进程 2 一样继续执行。
• ...
• 进程 1 和 2 轮流超过进程 0。

参考文献。所有细节来自 Alagarsamy 的论文 "Some myths about famous mutual exclusion algorithms"。显然，Block 和 Woo 在《A more efficient generalization of Peterson's mutual exclusion algorithm》中提出了一种修改后的算法，该算法确实满足无饥饿。Alagarsamy 后来在 "A mutual exclusion algorithm with optimally bounded bypasses" 中对其进行了改进（通过获得最优饥饿界限 N-1）。

- A. Rex

---

我希望我能够获取学术论文。 :/ - Brent

Answer 2

一个Rex在死锁情况下是错误的。
（顺便说一句：正确的术语应该是饥饿场景，因为死锁需要至少两个线程被“卡住”，请参见维基百科：deadlock和starvation）。

当进程2和1进入级别0时，步骤[0]设置为1或2，从而使进程0的先决条件失效，因为step[0]==0是错误的。

对于2个进程的Peterson算法要简单一些，并且确实可以防止饥饿。

对于n个进程的Peterson算法要复杂得多。

要出现一个进程饥饿的情况，必须永远满足条件step[j]==i and some_pos_is_big(i,j)。这意味着没有其他进程进入相同的级别（这将使step[j]==i为false），并且至少有一个进程始终处于与i相同的级别或更高的级别（以保证some_pos_is_big(i,j)保持为真）。

此外，在这个级别j中只能有一个进程处于死锁状态j。如果有两个进程处于死锁状态，那么其中一个step[j]==i将为false，因此不会出现死锁状态。这意味着没有其他进程能够进入相同的级别，并且总是必须有一个进程在高于i的级别或同一级别上（以保证some_pos_is_big(i,j)保持为真）。

另外，只有一个进程可以在这个级别j中被死锁。如果有两个进程处于死锁状态，那么其中一个step[j]==i将为false，因此不会出现死锁状态。这意味着没有其他进程能够进入相同的级别，并且总是必须有一个进程在高于i的级别或同一级别上（以保证some_pos_is_big(i,j)保持为真）。

由于没有其他进程能够加入以上进程（因为它们无法进入级别j，因此不能进入级别j以上），因此至少有一个进程必须在级别j以上也处于死锁状态，或者在临界区中的进程不释放临界区。

如果我们假设在有限时间内进入临界区的进程终止，则只有一个以上的进程必须处于死锁状态。

但是，对于其中一个进程处于死锁状态，必须存在另一个进程也处于死锁状态等等。

但是，以上只有有限的进程，因此最终顶部进程无法处于死锁状态，因为一旦临界区被释放，它将前进。

因此，Peterson算法对n个进程进行保护，防止饥饿！

- user1299070

Answer 3

我怀疑关于饥饿的评论是关于一些广义的、N进程的Peterson算法。可以构造一个有界等待的N进程版本，但如果没有特定的版本来讨论，我们就无法说出为什么这个特定的泛化可能会导致饥饿。

快速搜索谷歌找到了this paper，其中包括伪代码。正如您所看到的，广义版本要复杂得多（也更昂贵）。

- Ben Jackson

---

链接不可用。 - SAbbasizadeh