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

我一直在寻找有关Peterson's algorithm的信息，但曾经遇到过有关它不满足饥饿但只有僵局的参考文献。这是真的？如果有的话可以有人详细说明为什么它不？彼得森的算法是否满足饥饿？

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通过将其设置为0而赋予P0优先级，则进入临界区的进入P0。

来源

2010-10-27 IZI_Shadow_IZI

如果您提出问题，请为那些不熟悉您所谈论主题的人提供更多背景。它是什么样的算法？它能做什么？你确切的问题是什么？如果你这样做，社区将非常感激。 – 2010-10-27 13:29:12

正如本杰克逊怀疑的那样，问题在于广义算法。标准的两进程彼得森算法满足无饥饿特性。

显然，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。
由于pos[2]很大，因此处理0和1被阻止。
过程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）中得到改进。

来源

2010-10-28 07:32:35

我希望我有机会获得学术论文。：/ – Brent 2012-11-18 00:14:16

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

快速谷歌出现this paper其中包括伪代码。正如你所看到的，通用版本要复杂得多（而且代价昂贵）。

来源

2010-10-27 22:48:17

链接不可用。 – SAbbasizadeh 2014-05-22 15:07:37

雷克斯对于死锁情况是错误的。
（作为一个侧面说明：正确的说法是饥饿的情况下，因为对于死锁有被“卡住”看到维基至少需要两个线程：deadlock和starvation）

随着工艺2和1进入级别0，步骤[0]被设置为1或2，因此由于step[0] == 0为假而使得进程0的前进条件为假。

两个过程的peterson算法有点简单，并且可以防止饥饿。

彼得森算法n个过程要复杂得多

要有一个过程开始挨饿的条件step[j] == i and some_pos_is_big(i, j)必须是真实的永远的情况。这意味着没有其他进程进入同一级别（这会使得step[j] == i为假），并且至少有一个进程总是与我在同一级别或更高级别上（以保证some_pos_is_big(i, j)保持为真）

此外，只有一个进程可以在此级别上死锁j。如果两人陷入僵局，那么其中一人step[j] == i将是虚假的，因此不会陷入僵局。因此，这意味着没有进程不能进入同一级别，并且必须始终有一个级别在上面的进程。

由于没有其他进程可以加入上述进程（因为它们不能进入级别j，因此不能进入上级列表j）至少有一个进程必须死锁，否则临界区进程不会释放关键部分。

如果我们假设临界区中的进程在有限时间后终止，那么只有上述进程中的一个必须死锁。

但是对于那个死锁，上面的另一个必须是死锁等然而，上面只有有限的过程，所以最终的过程最终不会死锁，因为它会一旦临界区免费赠送。

因此n进程的peterson算法可以防止饥饿！

来源

2012-03-28 19:56:40 DevBen

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

回答

相关问题