彼得森的算法满足饥饿吗？

  • Z时代
  • 2024-01-10
  • 分类：问答

我一直在搜索有关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;

该算法使用两个变量，标志和转弯。标志值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和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）。 。

以上是 彼得森的算法满足饥饿吗？ 的全部内容， 来源链接： utcz.com/qa/404922.html

回到顶部