multithreading - 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); 

我对这个算法有疑问，据说当你的数字为零时你将无法进入临界区。

但是如果循环内的条件为真，循环的工作方式将陷入所述循环。

意思是非零数将是未达到临界条件的数，对吧？

这让我有点困惑，我会很感激你的帮助

问候约翰。

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)

Assertion 2 implies that at most one processor can be in its critical section at any time. Assertions 1 and 2 prove that processors enter their critical sections on a first-come-first-served basis. Hence, an individual processor cannot be blocked unless the entire system is deadlocked. Assertion 3 implies that the system can only be deadlocked by a processor halting in its critical section, or by an unbounded sequence of processor failures and re-entries.

您的号码不可能，即 number[i]当你到达关键部分时为零，因为你是唯一写入它的人，并且因为你在到达循环之前设置它 while ((number[j]!= 0) && (number[j],j)<(number[i],i)));部分。

根据定义，您也不可能陷入此等待循环 (L2)，因为该问题假定线程不会在临界区崩溃。因此，一旦您正在等待的所有其他线程退出临界区并设置它们的 number[j]为零，轮到你进入临界区。