這種互斥排除僞代碼是如何工作的？

Question

bool flag[2] = {false, false} 
process p(i): // i in { 0, 1 } 
while (flag[1-i]) { 
    // do nothing 
} 
flag[i] = true 
while (flag[1-i]) { 
    // do nothing 
} 
<critical section> 
flag[i] = false 

此代碼讓我發瘋。它是爲解決兩個程序（0,1）之間的互斥而構建的代碼。 有人可以解釋我如何將標記更改爲每個程序0和1時，將其放入代碼。

Answer 1

2個布爾值的陣列，flag，必須在共享內存中才能有工作的機會。對於流程而言，這至關重要;如果這些是線程，則不需要共享內存。

最初，進程0或1都沒有將其flag的值設置爲true。

假設進程i = 0試圖訪問關鍵部分。第一個忙碌循環（while循環）等待，直到flag[1]爲false（此時它是錯誤的）;那麼代碼集flag[0] = true。代碼現在進入第二個忙碌循環; flag[1]仍然是false，所以它會繼續進行並安全地進入臨界區，因爲知道其他進程不在臨界區內。

假設當進程0位於臨界區時，進程1也嘗試進入。它在第一個忙碌循環中被阻止，因爲flag[0]爲真。它仍然是這樣，直到進程0離開並將flag[0]設置回false。當進程0離開時，進程1將flag[1]設置爲true，進入第二個忙循環，然後由於flag[0]爲假而離開;它現在處於關鍵部分。

爲什麼這兩個繁忙循環？因爲可能發生這兩個進程同時在多個核心上運行，並且兩者都可能同時進入第一個繁忙循環。他們都會看到對方的旗幟是假的，退出循環並將自己的旗幟設置爲真，並重新檢查對方的旗幟仍然是假的。大多數時候，其中一人會看到對方是錯誤的，會進入關鍵部分。有時候，他們可能都會發現對方是真的（因爲他們在鎖步中工作太多），然後雙方都進入第二個忙碌循環，並且都不會退出 - 死鎖。

所以，我不相信代碼是一個萬無一失的互斥機制，儘管它需要運氣不好纔會陷入僵局。但是，如果嘗試了足夠的嘗試，就會發生運氣不好的情況 - 長時間運行的流程無法承擔風險。