8

我一直在搜索有关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 进入临界区。

4

3 回答 3

9

正如本杰克逊所怀疑的那样，问题出在广义算法上。标准的 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 在“ A more Effective generalization of Peterson's互斥算法”中提出了一种改进的算法，该算法确实满足无饥饿，Alagarsamy 后来在“具有最佳有界绕过的互斥算法”中改进了该算法（通过获得最佳饥饿界限N-1） .

于 2010-10-28T07:32:35.390 回答
2

A Rex is wrong with the deadlock situation.
(as a side note: the correct term would be starvation scenario, since for a deadlock there are at least two threads required to be 'stuck' see wikipedia: deadlock and starvation)

As process 2 and 1 go into level 0, step[0] is set to either 1 or 2 and thus making the advance condition of process 0 false since step[0] == 0 is false.

The peterson algorithm for 2 processes is a little simpler and does protect against starvation.

The peterson algorithm for n processes is much more complicated

To have a situation where a process starves the condition step[j] == i and some_pos_is_big(i, j) must be true forever. This implies that no other process enters the same level (which would make step[j] == i false) and that at least one process is always on the same level or on a higher level as i (to guarantee that some_pos_is_big(i, j) is kept true)

Moreover, only one process can be deadlocked in this level j. If two were deadlocked then for one of them step[j] == i would be false and therefor wouldn't be deadlocked. So that means no process can't enter the same level and there must always be a a process in a level above.

As no other process could join the processes above (since they can't get into level j and therefor not above lelel j) at least one process must be deadlocked too above or the process in the critical section doesn't release the critical section.

If we assume that the process in the critical section terminates after a finite time, then only one of the above processes must be deadlocked.

But for that one to be deadlocked, another one above must be deadlocked etc. However, there are only finite processes above, so eventually the top process can't be deadlocked, as it'll advance once the critical section is given free.

And therefor the peterson algorithm for n processes protects against starvation!

于 2012-03-28T19:56:40.177 回答
0

我怀疑关于饥饿的评论是关于一些广义的 N 进程彼得森算法。可以构建一个有界等待的 N 进程版本，但是如果没有一个特别讨论的版本，我们不能说为什么这个特定的泛化可能会受到饥饿的影响。

一个快速的谷歌找到了这篇包含伪代码的论文。如您所见，通用版本要复杂得多（且昂贵）。

于 2010-10-27T22:48:17.343 回答