ConcurrentLinkedQueue并发原理分析

ConcurrentLinkedQueue是线程安全的队列，它适用于“高并发”的场景

之前知道concurrentHashMap是使用了分段锁的机制来更好的控制细粒度，但是ConcurrentLinkedQueue却是使用了一种非阻塞算法来实现的，在搜索了很久还是不理解的情况下，对着源码苦啃1小时终于有了点眉目。。膜拜Doug Lea大师啊。。

 

首先要先知道ConcurrentLinkedQueue中标识尾节点的tail引用使用的是volatile，每当一个线程的值修改了它都会对其它线程可见。。并且tail节点并不是都是指向的是最后一个尾节点。。后面我们会详细介绍到

 

先上代码

public boolean offer(E e) {
        checkNotNull(e);
        final Node<E> newNode = new Node<E>(e);

        for (Node<E> t = tail, p = t;;) {
            Node<E> q = p.next;
            if (q == null) {                                                // A
                // p is last node
                if (p.casNext(null, newNode)) {                             //B
                    // Successful CAS is the linearization point
                    // for e to become an element of this queue,
                    // and for newNode to become "live".
                    if (p != t) // hop two nodes at a time                  //C
                        casTail(t, newNode);  // Failure is OK.
                    return true;
                }
                // Lost CAS race to another thread; re-read next
            }
            else if (p == q)                                                //D
                // We have fallen off list.  If tail is unchanged, it
                // will also be off-list, in which case we need to
                // jump to head, from which all live nodes are always
                // reachable.  Else the new tail is a better bet.
                p = (t != (t = tail)) ? t : head;
            else                                                           //E
                // Check for tail updates after two hops.
                p = (p != t && t != (t = tail)) ? t : q;
        }
    }

 总体来说 整个offer代码 （添加一个元素到队列尾端）的核心思想就是找到队列的尾节点，然后将新的节点插入到尾节点中。而在并发的情况下对于怎么每次都找到尾节点有点复杂

 

假设有2个线程，线程1和线程2都同时的执行这段加入元素的代码。

假设此时 tail节点指向的就是尾节点。

p指向的是tail，而q则是空

线程1执行到A处，还未执行到B处时；线程2执行到进入了B。那么此时线程1中的p.casNext(null, newNode)便会失败，于是线程1便会退出重新循环加入。这时候就要分看线程1和线程2中的执行情况了。

 

线程2执行完p.casNext(null, newNode)后，执行C，而此时线程2中的p和t是相等的，所以它并没有将新加入的节点修改为尾节点，而是交给了后续的节点来修改。。（其实这么做是为了加快执行效率，这就是很多资料中说的tail节点与尾节点的hop值还在给定的阈值内，所以不修改） 于是线程2就执行完了 退出。

 

线程1刚刚在B处失败了，于是它重新判断，q此时并不是null了，所以它运行到了E出，而E出的代码中，重新将p的引用向前推进，因为可能在这个过程中tail的值会被另一个线程3改变，所以t=tail，赋值。因为tai是个volatile类型的，所以它会重新定义t的指向，但是总体方法就是使P向前推进！！找到尾节点

 

至于什么时候p==q，只有当这个队列是空的时候，刚初始化。所以P和Q都是空，于是还是按照核心思想往前推荐，可能是P的引用指向head节点。。

 

doug lea使用hops变量来控制并减少tail节点的更新频率，并不是每次节点入队后都将 tail节点更新成尾节点，而是当 tail节点和尾节点的距离大于等于常量HOPS的值（默认等于1）时才更新tail节点，tail和尾节点的距离越长使用CAS更新tail节点的次数就会越少，但是距离越长带来的负面效果就是每次入队时定位尾节点的时间就越长，因为循环体需要多循环一次来定位出尾节点，但是这样仍然能提高入队的效率，因为从本质上来看它通过增加对volatile变量的读操作来减少了对volatile变量的写操作，而对volatile变量的写操作开销要远远大于读操作，所以入队效率会有所提升...

 

对照理解的时候最好是画个队列图 比较详细。。。。

小白刚研究 说错了 希望各位大牛轻拍~

 

今天就先分析offer函数，关于poll后面在分析~~