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

Question

我一直在搜索关于彼得森算法的信息,但是已经遇到过参考文献,说明它不满足饥饿但只是死锁.这是真的？若有,有人可以详细说明为什么不呢？

彼得森的算法:

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通过将转到0设置为P0优先级,则允许进程P0进入临界区.

Answer 1

正如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和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 的论文" 关于着名互斥算法的一些神话 ".显然Block和Woo在" 更有效的Peterson互斥算法的推广 "中提出了一种改进算法,它确实满足了非饥饿,Alagarsamy后来在" 具有最佳有界旁路的互斥算法 "(通过获得最佳饥饿界限N-1)中进行了改进. .