Java中的Peterson算法？

Question

在Java中互相排斥Peterson算法是否有示例實現？

Answer 1

這裏沒有人提供了Java中該算法的正確/安全實現。我不確定John W的解決方案應該如何工作，因爲它缺少部分內容（即ThreadLocals的聲明以及他的陣列中原本應該是什麼的解釋 - 原始碼booleans沒有get()和set()）。

Chapter 17 of the Java Language Specification解釋Java內存模型。特別感興趣的是Section 17.4.5，其描述發生在之前的順序。在單個線程中思考很容易。考慮片段：

int x, y, z, w; 
x = 0; 
y = 5; 

z = x; 
w = y; 

每個人都會同意，在這個片段的最後，雙方x和z等於0兩者y和w等於5。忽略的聲明，我們有六個行動在這裏：

1. 寫入到x
2. 寫入到y
3. 一個從x
4. 讀取寫入到z
5. 一個從y
閱讀
6. 寫給w

因爲它們全都出現在同一個線程中，所以JLS說這些讀寫都保證顯示出這樣的順序：上述每個動作n（因爲動作在單個線程中）與all actions m，m>n。

但是不同的線程呢？ 對於正常的字段訪問，線程之間沒有發生任何事前關係。這意味着線程A可以遞增共享變量，並且線程B可能讀取該變量，但看不到新值。在JVM中執行程序時，線程A的寫入傳播可能已被重新排序以在線程B讀取之後發生。

事實上，線程A會寫信給一個變量x，然後給一個變量y，建立線程A.但是線程B內的兩個動作之間的之前發生關係可以讀取x和y，它是合法的B得到新值y之前新值x出現。細則中指出：

更具體地說，如果兩個動作 份額的之前發生關係， 他們不一定出現 已經發生的順序，以任何 代碼與它們不共享 發生之前的關係。

我們如何解決這個問題？對於正常的字段訪問，所述volatile關鍵字是不夠的：

於揮發性可變 （§8.3.1.4）V的寫入同步，與所有後續 任何線程 （其中隨後根據限定的讀出的v的 到同步順序）。

同步，與是個要強的條件比之前發生，而且由於之前發生的傳遞，如果線程A希望線程B看到其寫入x和y，它只是需要寫入在寫入x和y後變量變量z。線程B需要在讀取z之前閱讀x和y，它將保證看到新的值x和y。

在Gabriel的解決方案中，我們看到這種模式：寫入發生到in，這對其他線程不可見，但是寫入發生到turn，所以其他線程保證只要讀取就看到兩個寫入首先是turn。

不幸的是，while循環的條件是反向：保證線程沒有看到過時的數據爲in，while循環應該從turn首先閱讀：

// ... 
    while (turn == other() && in[other()]) { 
     // ... 

用此修復程序記住，大部分解決方案的其餘部分是可以的：在關鍵部分，我們不關心數據的過時問題，因爲我們正處於關鍵部分！最後唯一的缺陷是：Runnable將in[id]設置爲新的值並退出。另一個線程是否可以保證看到in[id]的新值？細則中指出NO：

在一個線程T1 最後的動作同步，在 採取任何檢測T1 已終止另一個線程T2。 T2可以通過調用T1.isAlive（）或 T1.join（）來完成 。

那麼我們該如何解決？而就在該方法的末尾添加一次寫turn：

// ... 
    in[id] = false; 
    turn = other(); 
} 
// ... 

由於我們重新排序while循環，其他線程將保證看到的in[id]新的錯誤值，因爲在寫in[id]之前發生的寫入turn發生在從turn讀取之前發生 - 在從in[id]讀取之前。

不用說，如果沒有公制ton的評論，這種方法是脆弱的，有人可以來，改變一些事情，巧妙地打破了正確性。僅定義數組volatile不夠好：由比爾·普格（該lead researchers用於Java的內存模型之一）解釋in this thread，聲明數組volatile使得更新到陣列參考其他線程可見。數組元素的更新不一定是可見的（因此我們只需通過使用另一個volatile變量來防止對數組元素的訪問就可以跳過所有的循環）。

如果您希望自己的代碼清晰簡潔，請將它保持原樣並將in更改爲AtomicIntegerArray（使用0表示false，1表示true;不存在AtomicBooleanArray）。這個類就像一個數組，其元素都是volatile，所以我們很好地解決了所有的問題。或者，您可以聲明兩個易失性變量，即boolean in0和boolean in1，並更新它們而不是使用布爾數組。

Answer 2

我無法找到一個在網絡上我，所以我決定嘗試寫它：

public class Peterson implements Runnable { 

    private static boolean[] in = { false, false }; 
    private static volatile int turn = -1; 

    public static void main(String[] args) { 
     new Thread(new Peterson(0), "Thread - 0").start(); 
     new Thread(new Peterson(1), "Thread - 1").start(); 
    } 

    private final int id; 

    public Peterson(int i) { 
     id = i; 
    } 

    private int other() { 
     return id == 0 ? 1 : 0; 
    } 

    @Override 
    public void run() { 
     in[id] = true; 
     turn = other(); 
     while (in[other()] && turn == other()) { 
      System.out.println("[" + id + "] - Waiting..."); 
     } 
     System.out.println("[" + id + "] - Working (" 
       + ((!in[other()]) ? "other done" : "my turn") + ")"); 
     in[id] = false; 
    } 
} 

隨意評論，但可以理解的:)

Answer 3

除非你有特殊需要對於彼得森的算法（當使用像Java這樣的高級語言工作時會很奇怪），我建議你看一下這種語言的同步設施。

例如，您可能會發現在Java「的競爭條件和 互斥」有用這本書的章節：http://java.sun.com/developer/Books/performance2/chap3.pdf

在particlar：

Java提供了內置支持 等待這個「改變狀態「通過 條件的概念。 的條件有點用詞不當，但是， ，因爲它完全由用戶 決定是否實際發生條件 。此外，條件 不一定是特別真實或 錯誤。要使用條件，一是必須 熟悉三個主要方法Object類的 ：

•等待（）：此 方法用於等待的條件。 當某個特定的（共享的） 對象被鎖定時，它被調用。

•notify（）：此方法爲 ，用於通知單個線程 條件已（可能）已更改。 同樣，當某個 特定對象目前被鎖定時，會調用此方法。由於 這個調用的結果，只有一個 線程可以被喚醒。

•notifyAll（）：此方法 用於通知多個線程 條件已（可能） 已更改。所有在調用此方法時運行 的線程都會通知 。

Answer 4

你應該看看這本書的藝術多處理器編程。他非常詳細地介紹了不同的鎖定實現（旋轉和阻塞）。他還介紹了其他不同類型的併發算法（例如跳過列表）。這裏是他的書中關於Peterson Lock算法的片段

Class Peterson implements Lock{ 
    private final boolean []flag = new boolean[2]; 
    private volatile int victim; 

    public void lock(){ 
     int i = ThreadID.get(); // ThreadID is a ThreadLocal field 
     int j= 1 - i; 
     flag[i] = true; // I'm Interested 
     victim = i;  // You go first 
     while(flag[j] && victim == i){}; //wait 
    } 
    public void unlock(){ 
     int i = ThreadID.get(); 
     flag[i] = false;  //Not interested anymore 
    } 
} 

Answer 5

雖然不是paterson算法，但AtomicBoolean和Atomic *類使用無鎖，繁忙循環來更新共享數據。它們可能適合您的要求。