algorithm - 彼得森的算法是否满足饥饿？

Question

我一直在搜索有关 Peterson's algorithm 的信息但遇到过引用，指出它不能满足饥饿而只能满足僵局。这是真的？如果可以，有人可以详细说明为什么不可以吗？

彼得森算法:

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 可以进入临界区。

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。它逃脱了 for 循环并进入临界区。完成后，它设置 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)。