正确使用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进行堆栈实现

回答

相关问题