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

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

正如本杰克逊（Ben Jackson）所怀疑的那样，问题在于通用算法。标准的2进程Peterson算法满足无饥饿性质。

显然，彼得森的原始论文实际上有一个针对

N

处理器的算法。这是我刚刚用类似C ++的语言写的草图，应该是这种算法：

// Shared resourcesint pos[N], step[N];// Individual process prevoid 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

）。 。