Non-Blocking and Blocking Concurrent Queue Algorithm 高效的非阻塞队列实现
import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;/** * Created by luochao on 14-1-4. */public class ConcurrentQueue<Content> { private volatile Node<Content> head; private volatile Node<Content> tail; private final static AtomicReferenceFieldUpdater<ConcurrentQueue,Node> HEAD_UPDATER = AtomicReferenceFieldUpdater.newUpdater(ConcurrentQueue.class,Node.class,"head"); private final static AtomicReferenceFieldUpdater<ConcurrentQueue,Node> TAIL_UPDATER= AtomicReferenceFieldUpdater.newUpdater(ConcurrentQueue.class,Node.class,"tail"); private boolean casHead(final Node<Content> expect,final Node<Content> update){ return HEAD_UPDATER.compareAndSet(this,expect,update); } private boolean casTail(final Node<Content> expect,final Node<Content> update){ return TAIL_UPDATER.compareAndSet(this,expect,update); } public ConcurrentQueue(){ Node node = new Node(null,null); this.head = node; this.tail = node; } public void enqueue(Content content){ Node newNode = new Node(null,content); while (true){ Node t = tail; Node next = t.next; if(t == tail){//判断tail是否被修改 已经next一致性 if(next == null){ //从队列末尾入列 if(t.casNext(null, newNode)){ casTail(tail,newNode); return; } }else { casTail(tail,next); } } } } public boolean dequeue(Content content){ Node h = head; Node t = tail; Node next = h.next; while (true){ if(h == head){//double check 检查head是否一致 if(h == t){//判断是否为空队列 Is queue empty or Tail falling behind? if (next == null){ return false; } //Tail is falling behind. Try to advance it casTail(t,next); return true; }else{ if (casHead(h,next)){ return true; } } } } } private static class Node<Content>{ volatile Node next; Content value; Node(Node next, Content value) { this.next = next; this.value = value; } private boolean casNext(Node<Content> expect,Node<Content> update){ return NEXTUPDATE.compareAndSet(this,expect,update); } //字段更新器 param 1 字段所在类 2 更新字段的值 3 字段名称 基于cas private static final AtomicReferenceFieldUpdater<Node,Node> NEXTUPDATE = AtomicReferenceFieldUpdater.newUpdater(Node.class,Node.class,"next"); }}??Simple, Fast, and Practical Non-Blocking and Blocking ?Concurrent Queue Algorithms
?refer:http://www.cs.rochester.edu/u/michael/PODC96.html