鎖定空閒隊列中的錯誤在哪裏？

我寫了一個Java lock free queue實現。它有一個併發錯誤。我找不到它。這段代碼並不重要。我只是擔心我無法解釋與揮發性變量相關的觀察行爲。鎖定空閒隊列中的錯誤在哪裏？

該錯誤是由異常（「空頭」）可見的。這是不可能的狀態，因爲存在保持當前隊列大小的原子整數。隊列中有一個存根元素。它規定讀者線程不會改變尾部指針，並且編寫器線程不會改變頭部指針。

隊列長度變量保證鏈表永遠不會爲空。這是一個信號量。

take方法的行爲就像它被盜的長度值。

class Node<T> { 
    final AtomicReference<Node<T>> next = new AtomicReference<Node<T>>(); 
    final T ref; 
    Node(T ref) { 
     this.ref = ref; 
    } 
} 
public class LockFreeQueue<T> { 
    private final AtomicInteger length = new AtomicInteger(1); 
    private final Node stub = new Node(null); 
    private final AtomicReference<Node<T>> head = new AtomicReference<Node<T>>(stub); 
    private final AtomicReference<Node<T>> tail = new AtomicReference<Node<T>>(stub); 

    public void add(T x) { 
     addNode(new Node<T>(x)); 
     length.incrementAndGet(); 
    } 

    public T takeOrNull() { 
     while (true) { 
      int l = length.get(); 
      if (l == 1) { 
       return null; 
      } 
      if (length.compareAndSet(l, l - 1)) { 
       break; 
      } 
     } 
     while (true) { 
      Node<T> r = head.get(); 
      if (r == null) { 
       throw new IllegalStateException("null head"); 
      } 
      if (head.compareAndSet(r, r.next.get())) { 
       if (r == stub) { 
        stub.next.set(null); 
        addNode(stub); 
       } else { 
        return r.ref; 
       } 
      } 
     } 
    } 

    private void addNode(Node<T> n) { 
     Node<T> t; 
     while (true) { 
      t = tail.get(); 
      if (tail.compareAndSet(t, n)) { 
       break;  
      } 
     } 
     if (t.next.compareAndSet(null, n)) { 
      return; 
     } 
     throw new IllegalStateException("bad tail next"); 
    } 
}

來源

2013-12-20 Daneel S. Yaitskov

當沒有使用鎖定機制時，此代碼如何防止數據競爭？你爲什麼不想使用鎖？ – Chriss

你什麼時候看到問題？您是在單一閱讀器線程中獲得它，還是在看到問題之前需要多個閱讀器？我懷疑這個問題是圍繞在takeOrNull的第二個while循環中的多個讀者線程。 –

這不是生產代碼。對待這個練習。 –

我覺得這是你如何使用takeOrNull（）計數器，當您刪除存根，你減1距離的誤差，但在加入存根回來時，不要再增加它最後，因爲你使用addNode（）而不是add（）。比方說，你成功地添加的元素，讓你的隊列是這樣的：

Length is 2 
STUB -> FIRST_NODE -> NULL 
^  ^
|   | 
Head  Tail

所以現在有一個線程開始做takeOrNull（），長度減小到1，頭移動到FIRST_NODE，而且由於這是STUB節點，它被重新添加到最後，所以現在你有：

Length is 1 
FIRST_NODE -> STUB -> NULL 
^   ^
|    | 
Head   Tail

你看到了嗎？現在長度是1！在下一個takeOrNull（）函數中，即使FIRST_NODE仍在隊列中並且從未返回，您也將獲得NULL值......您只是（暫時）丟失了一段數據。此外，你現在可以重複這個廣告，並開始累積節點。就像添加三個節點一樣，Length是4，並且您有FIRST，STUB，NEW1，NEW2，NEW3。如果你做了三次takeOrNull（），你最終會得到NEW2，NEW3，STUB和Length 1. 所以這樣你最終失去了元素，但我承認並不完全確定這會如何觸發異常。讓我吃，再想一想。 ;-)

編輯：好的食物做了我很好，我想出了一個序列，觸發頭空例外。讓我們先從一個有效的隊列與一個元素像以前一樣：

Length is 2 
STUB -> FIRST_NODE -> NULL 
^  ^
|   | 
Head  Tail

現在我們有四個線程，二是儘量takeOrNull（）和兩個是加（）兼任。兩個添加線程都正確地移動了尾指針，第一個將尾從FIRST移到SECOND，然後暫停。第二個添加線程隨後從SECOND移動到THIRD，然後更新舊尾部（SECOND）的下一個指針，然後遞增計數器並退出。我們留下了：

Length is 3 
STUB -> FIRST_NODE -> NULL   SECOND_NODE -> THIRD_NODE -> NULL 
^             ^
|              | 
Head             Tail

現在兩個takeOrNull線程醒來並執行，因爲長度爲3，雙方將能夠得到一個元素！第一個將STUB的頭部移動到FIRST，第二個將頭部從FIRST移動到NULL。現在HEAD爲空，每當takeOrNull（）被調用時，EXCEPTION！

來源

2013-12-20 19:19:29 llongi

鎖定空閒隊列中的錯誤在哪裏？

回答

相關問題