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。标志值为 1 表示进程想要进入临界区。变量turn保存当前轮到的进程的ID。如果 P1 不想进入其临界区或者 P1 通过将 Turn 设置为 0 赋予 P0 优先权，则允许进程 P0 进入临界区。

正如本·杰克逊（Ben Jackson）怀疑的那样，问题出在通用算法上。标准的 2 进程 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 and step[0] = 0然后等待。
• 接下来开始进程2，设置pos[2] = 0 and step[0] = 2然后等待。
• 进程 1 最后启动，设置pos[1] = 0 and step[0] = 1然后等待。
• 进程2是第一个注意到变化的进程step[0]如此设置j = 1, pos[2] = 1, and step[1] = 2.
• 进程 0 和 1 被阻塞是因为pos[2] is big.
• 进程2没有被阻塞，所以它设置j = 2。它逃脱了 for 循环并进入临界区。完成后就设置了pos[2] = 0但立即开始再次竞争关键部分，从而设置step[0] = 2并等待。
• 进程1是第一个注意到变化的进程step[0]并按照之前的过程2进行。
• ...
• 进程 1 和 2 轮流竞争进程 0。

参考。所有详细信息均来自论文“关于著名互斥算法的一些误解” 作者：Alagasamy。显然，Block 和 Woo 在“中提出了一种修改后的算法Peterson 互斥算法的更有效推广“这确实满足了不饥饿的要求，阿拉加萨米后来在”中改进了这一点具有最佳有界旁路的互斥算法“（通过获得最佳饥饿界限N-1).