ConcurrentLinkedQueue原理探究

ConcurrentLinkedQueue是线程安全的无界非阻塞队列，其底层数据结构使用单向链表实现，对于入队和出队操作使用CAS来实现线程安全。下面我们来看具体实现。

类图结构

为了能从全局直观地了解ConcurrentLinkedQueue的内部构造，先简单介绍ConcurrentLinkedQueue的类图结构。

ConcurrentLinkedQueue内部的队列使用单向链表方式实现，其中有两个volatile类型的Node节点分别用来存放队列的首、尾节点。从下面的无参构造函数可知，默认头、尾节点都是指向item为null的哨兵节点。新元素会被插入队列末尾，出队时从队列头部获取一个元素。

在Node节点内部则维护一个使用volatile修饰的变量item,用来存放节点的值；next用来存放链表的下一个节点，从而链接为一个单向无界链表。其内部则使用UNSafe工具类提供的CAS算法来保证出入队时操作链表的原子性。

ConcurrentLinkedQueue原理介绍

先介绍ConcurrentLinkedQueue的几个主要方法的实现原理。

offer操作

offer操作是在队列末尾添加一个元素，如果传递的参数是null则抛出NPE异常，否则由于ConcurrentLinkedQueue是无界队列，该方法一直会返回true。

另外，由于使用CAS无阻塞算法，因此该方法不会阻塞挂起调用线程。下面具体看下实现原理。

下面结合图来讲解该方法的执行流程。

1. 首先看当一个线程调用offer(item)时的情况。首先代码(1)对传参进行空检查，如果为null则抛出NPE异常，否则执行代码(2)并使用item作为构造函数参数创建一个新的节点，然后代码(3)从队列尾部节点开始循环，打算从队列尾部添加元素，当执行到代码(4)时队列状态如图所示。
   

   这时候节点p、t、head、tail同时指向了item为null的哨兵节点，由于哨兵节点的next节点为null,所以这里q也指向null。

   代码(4)发现q==null则执行代码(5),通过CAS原子操作判断p节点的next节点是否为null,如果为null则使用节点newNode替换p的next节点，然后执行代码(6),这里由于p=t所以没有设置尾部节点，然后退出offer方法，这时候队列的状态如下图所示。
   

2. 上面是一个线程调用offer方法的情况，如果多个线程同时调用，就会存在多个线程同时执行到代码(5)的情况。

   假设线程A调用offer(item1),线程B调用offer(item2),同时执行到代码(5)p.casNext(null,newNode)。

   由于CAS的比较设置操作是原子性的，所以这里假设线程A先执行了比较设置操作，发现当前p的next节点确实是null,则会原子性地更新next节点为item1,这时候线程B也会判断p的next节点是否为null,结果发现不是null(因为线程A已经设置了p的next节点为item1),则会跳到代码(3),然后执行到代码(4),这时候的队列分布如图所示。
   
   根据上面的状态图可知线程B接下来会执行代码(8),然后把q赋给了p。
   
   然后线程B再次跳转到代码(3)执行，当执行到代码(4)时。
   
   由于这时候q=null,所以线程B会执行代码(5),通过CAS操作判断当前p的next节点是否是null,不是则再次循环尝试，是则使用item2替换。

假设CAS成功了，那么执行代码(6),由于p!=t,所以设置tail节点为item2,然后退出offer方法。这时候队列分布如图所示。

分析到现在，就差代码(7)还没走过，其实这一步要在执行poll操作后才会执行。这里先来看一下执行poll操作后可能会存在的一种情况。

下面分析当队列处于这种状态时调用offer添加元素，执行到代码(4)时的状态图。

这里由于q节点不为空并且pq所以执行代码(7),由于ttail所以p被赋值为head,然后重新循环，循环后执行到代码(4),这时候队列状态如图所示。

这时候由于q==null,所以执行代码(5)进行CAS操作，如果当前没有其他线程执行offer操作，则CAS操作会成功，p的next节点被设置为新增节点。

然后执行代码(6),由于p!=t所以设置新节点为队列的尾部节点，现在队列状态如图所示。

需要注意的是，这里自引用的节点会被垃圾回收掉。

可见，offer操作中的关键步骤是代码(5),通过原子CAS操作来控制某时只有一个线程可以追加元素到队列末尾。

进行CAS竞争失败的线程会通过循环一次次尝试进行CAS操作，直到CAS成功才会返回，也就是通过使用无限循环不断进行CAS尝试方式来替代阻塞算法挂起调用线程。

相比阻塞算法，这是使用CPU资源换取阻塞所带来的开销。

add操作

add操作是在链表末尾添加一个元素，其实在内部调用的还是offer操作。

poll操作

poll操作是在队列头部获取并移除一个元素，如果队列为空则返回null。下面看看它的实现原理。

同样，也结合图来讲解代码执行逻辑。

poll操作是从队头获取元素，所以代码(2)内层循环是从head节点开始迭代，代码(3)获取当前队列头的节点，队列一开始为空时队列状态如图7-12所示。

由于head节点指向的是item为null的哨兵节点，所以会执行到代码(6),假设这个过程中没有线程调用offer方法，则此时q等于null,这时候队列状态如图所示。

所以会执行updateHead方法，由于h等于p所以没有设置头节点，poll方法直接返回null。

假设执行到代码(6)时已经有其他线程调用了offer方法并成功添加一个元素到队列，这时候q指向的是新增元素的节点，此时队列状态如图所示。

所以代码(6)判断的结果为false,然后会转向执行代码(7),而此时p不等于q,所以转向执行代码(8),执行的结果是p指向了节点q,此时队列状态如图所示。

然后程序转向执行代码(3),p现在指向的元素值不为null,则执行p.casltem(item,null)通过CAS操作尝试设置p的item值为null,如果此时没有其他线程进行poll操作，则CAS成功会执行代码(5),由于此时p!=h所以设置头节点为p,并设置h的next节点为h自己，poll然后返回被从队列移除的节点值item。此时队列状态如图所示。

这个状态就是在讲解offer操作时，offer代码的执行路径(7)的状态。

假如现在一个线程调用了poll操作，则在执行代码(4)时队列状态如图所示。

这时候执行代码(6)返回null。

现在poll的代码还有分支(7)没有执行过，那么什么时候会执行呢?下面来看看。假设线程A执行poll操作时当前队列状态如图所示。

那么执行p.casltem(item,null)通过CAS操作尝试设置p的item值为null,假设CAS设置成功则标记该节点并从队列中将其移除，此时队列状态如图所示。

然后，由于p!=h,所以会执行updateHead方法，假如线程A执行updateHead前另外一个线程B开始poll操作，这时候线程B的p指向head节点，但是还没有执行到代码(6),这时候队列状态如图所示。

然后线程A执行updateHead操作，执行完毕后线程A退出，这时候队列状态如图所示。

然后线程B继续执行代码(6),q=p.next,由于该节点是自引用节点，所以p==q,所以会执行代码(7)跳到外层循环restartFromHead,获取当前队列头head,现在的状态如图所示。

peek操作

peek操作是获取队列头部一个元素(只获取不移除),如果队列为空则返回null。下面看下其实现原理。

size 操作

计算当前队列元素个数，在并发环境下不是很有用，因为CAS没有加锁，所以从调用size 函数到返回结果期间有可能增删元素，导致统计的元素个数不精确。

remove操作

如果队列里面存在该元素则删除该元素，如果存在多个则删除第一个，并返回true,否则返回false。

contains操作

判断队列里面是否含有指定对象，由于是遍历整个队列，所以像size操作一样结果也不是那么精确，有可能调用该方法时元素还在队列里面，但是遍历过程中其他线程才把该元素删除了，那么就会返回false。

小结

ConcurrentLinkedQueue的底层使用单向链表数据结构来保存队列元素，每个元素被包装成一个Node节点。

队列是靠头、尾节点来维护的，创建队列时头、尾节点指向一个item为null的哨兵节点。

第一次执行peek或者first操作时会把head指向第一个真正的队列元素。

由于使用非阻塞CAS算法，没有加锁，所以在计算size时有可能进行了offer、poll或者remove操作，导致计算的元素个数不精确，所以在并发情况下size函数不是很有用。

如图所示，入队、出队都是操作使用volatile修饰的tail、head节点，要保证在多线程下出入队线程安全，只需要保证这两个Node操作的可见性和原子性即可。

由于volatile本身可以保证可见性，所以只需要保证对两个变量操作的原子性即可。

offer操作是在tail后面添加元素，也就是调用tail.casNext方法，而这个方法使用的是CAS操作，只有一个线程会成功，然后失败的线程会循环，重新获取tail,再执行casNext方法。

poll操作也通过类似CAS的算法保证出队时移除节点操作的原子性。