ConcurrentLinkedQueue

ConcurrentLinkedQueue

内部类Node的类图如下:

Node类图

算法

此类的实现基于算法Michael & Scott algorithm,论文:

Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms

offer

 1public boolean offer(E e) {
 2    //如果元素为null,那么抛出NPE
 3    checkNotNull(e);
 4    final Node<E> newNode = new Node<E>(e);
 5    for (Node<E> t = tail, p = t;;) {
 6        //volatile读
 7        Node<E> q = p.next;
 8        if (q == null) {
 9            // p is last node
10            if (p.casNext(null, newNode)) {
11                if (p != t) // hop two nodes at a time
12                    casTail(t, newNode);  // Failure is OK.
13                return true;
14            }
15            //casNext竞争失败,再次读取p.next,此时(即q)不为空
16        }
17        else if (p == q)
18            // We have fallen off list.  If tail is unchanged, it
19            // will also be off-list, in which case we need to
20            // jump to head, from which all live nodes are always
21            // reachable.  Else the new tail is a better bet.
22            p = (t != (t = tail)) ? t : head;
23        else
24            //每插入两个新节点时才会重新设置尾节点
25            p = (p != t && t != (t = tail)) ? t : q;
26    }
27}

注意,由于ConcurrentLinkedQueue为无界队列,所以offer方法永远返回true。为什么说插入两个节点之后才会尝试重新设置尾节点呢?

假设我们的线程执行casNext失败,那么说明此时tail/p指针的next指向必定不为空(即另外一个线程已经插入了一个节点),节点状态可用下图来表示:

新节点插入

在下面的代码中将p指向新节点或重新读取tail:

1p = (p != t && t != (t = tail)) ? t : q;

那么为什么不能每插入一个节点便更新一次tail指针呢,因为出于降低CAS线程竞争(空转)的考虑。

结尾

此类不再向下继续展开,直接参考"Java并发编程实战"一书的272页内容即可,书中对其使用的算法进行了一针见血的说明。

问题

在debug的过程中发现了一个非常奇怪的问题,所以提出了知乎上的这个问题:

Java ConcurrentLinkedQueue疑问?

但是没有得到回答,在Stack Overflow上也有一个同样的问题:

What exactly UNSAFE.compareAndSwapObject does?

但是同样没有回答。