正確使用AtomicReference.compareAndSet進行堆棧實現

我正在嘗試使用java.util.concurrent並試圖解決如何正確使用AtomicReference.compareAndSet來管理對單個共享狀態的併發訪問。正確使用AtomicReference.compareAndSet進行堆棧實現

特別是：compareAndSet的正確性和安全性如下：任何陷阱？

我的測試類是一個基於節點鏈表的簡單堆棧。

public class LinkedStack<T> { 

    AtomicReference<Node<T>> topOfStack=new AtomicReference<Node<T>>(); 

    public T push(T e) { 
    while(true) { 
     Node<T> oldTop=topOfStack.get(); 
     Node<T> newTop=new Node<T>(e,oldTop); 
     if (topOfStack.compareAndSet(oldTop, newTop)) break; 
    } 
    return e; 
    } 

    public T pop() { 
    while(true) { 
     Node<T> oldTop=topOfStack.get(); 
     if (oldTop==null) throw new EmptyStackException(); 
     Node<T> newTop=oldTop.next; 
     if (topOfStack.compareAndSet(oldTop, newTop)) return oldTop.object; 
    } 
    } 

    private static final class Node<T> { 
    final T object; 
    final Node<T> next; 

    private Node (T object, Node<T> next) { 
     this.object=object; 
     this.next=next; 
    } 
    } 
    ................... 
}

來源

2011-04-05 mikera

唯一讓我暫停的不是你如何使用'AtomicReference'，而是你從'push'返回的東西。我很快就會期望'push'不會返回任何東西或者被埋沒的價值，而不是你自己推動的價值。 – 2011-04-05 14:43:18

@Mark，是的，這讓我停下了，但我只是想與Java的標準堆棧保持一致 - http://download.oracle.com/javase/1.5.0/docs/api/java/util/Stack .html＃push（E） - 承認這是一個稍微奇怪的返回定義 – mikera 2011-04-05 14:45:39

可能最好假裝該類不存在的原因很多（它不是一個接口，當它應該是，它使用從Vector的繼承而不是組成等等）。我會從[Deque]（http://download.oracle.com/javase/6/docs/api/java/util/Deque.html#push（E））接口中獲取提示，而不是其實現優於' Stack'。它是在Java 6中引入的，'Stack'的Javadoc被改爲建議在'Stack'上使用'Deque'。 – 2011-04-05 14:47:47

它的當前形式是正確的。

您的結構被稱爲Treiber's Stack。這是一個簡單的線程安全的無鎖結構，其具有單點爭用（topOfStack），因此往往會嚴重縮小（在競爭中會出現抖動，並且與MMU無法很好地協作）。如果爭用可能很低，但仍然需要線程安全性，這是一個很好的選擇。

有關定標疊加算法的更多信息，請參閱Danny Hendler，Nir Shavit和Lena Yerushalmi的「A Scalable Lock-free Stack Algorithm (pdf)」。

來源

2011-04-05 22:28:03

謝謝！特別是接受了你的答案，因爲了解這個小構造實際上叫做什麼是有趣的:-) – mikera 2011-04-14 11:03:05

是的，這正是它應該如何使用。

也許下面的語法是更優雅：

Node<T> oldTop = null; 
Node<T> newTop = null; 
do { 
    oldTop=topOfStack.get(); 
    newTop=new Node<T>(e,oldTop); 
} while (!topOfStack.compareAndSet(oldTop, newTop));

來源

2011-04-05 14:35:54 axtavt

感謝您的確認！我想按照你的建議去做，但是Java對於oldTop和newTop的範圍規則似乎不允許它...... – mikera 2011-04-05 14:38:13

是的，我與@mikera在一起，我更喜歡適當的範圍，比其他方式更奇怪的出口。但我同意你的評估。 – 2011-04-05 14:41:10

這一切看起來好（沒有什麼新的東西axtavt說的），有一件事我覺得是值得一提的是，一個失敗的流行率或者現在使用ConcurrentLinkedQueue的推送速度是現在的兩倍。當我說失敗時，我的意思是你必須再次在while循環內執行，假設另一個線程在你之前彈出或推出。

雖然這可能超出了您所要實現的範圍，但某些退避協議將有助於在高爭用情況下的性能。

來源

2011-04-05 14:49:38

正確使用AtomicReference.compareAndSet進行堆棧實現

回答

相關問題