Lamport的麪包店算法

Question

do { 
    choosing[i] = true; 
    number[i] = max(number[0], number[1], …, number [n – 1])+1; 
    choosing[i] = false; 
    for (j = 0; j < n; j++) { 
    while (choosing[j]); // espera que j obtenha um bilhete 
    while ((number[j]!= 0) && (number[j],j)<(number[i],i))); 
    } 
    critical section 
    number[i] = 0; 
    remainder section 
    } while (1); 

我對這種算法有疑問，據推測當你的數字爲零時，你將無法進入臨界區。

但循環的工作方式，如果循環內條件爲真，你會卡在所述循環。

含義非零數字將是沒有達到臨界條件的權利？

這有點混淆了我，我會感激你的幫助

Greetins約翰。

Answer 1

看一看原紙：

http://research.microsoft.com/en-us/um/people/lamport/pubs/bakery.pdf

（來源：http://research.microsoft.com/en-us/um/people/lamport/pubs/pubs.html#bakery）

斷言2意味着至多一個處理器可以在其臨界 部分在任何時間。斷言1和2證明處理器按照先來先服務的原則輸入 其關鍵部分。因此，一個 單個處理器不能被阻塞，除非整個系統死鎖爲 。斷言3意味着系統只能通過處理器在其關鍵部分中暫停或處理器故障和重新輸入的無限序列被鎖死 。

這是不可能的你的電話號碼，即number[i]爲零，當你達到臨界區，因爲你是唯一一個寫它，因爲你到達循環while ((number[j]!= 0) && (number[j],j)<(number[i],i)));部分面前。

根據定義，您也不可能陷入此等待循環（L2），因爲該問題假定線程無法在關鍵部分中崩潰。因此，一旦您等待的所有其他線程退出臨界區並將它們的number[j]設置爲零，輪到您進入臨界區。