彼得森的算法是否滿足飢餓？

我一直在尋找有關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

彼得森的算法是否滿足飢餓？

回答

相關問題