java并发之ConcurrentLinkedQueue

在并发编程中，我们可能经常需要用到线程安全的队列，java为此提供了两种模式的队列：阻塞队列和非阻塞队列。

注：阻塞队列和非阻塞队列如何实现线程安全？

• 阻塞队列可以用一个锁（入队和出队共享一把锁）或者两个锁（入队使用一把锁，出队使用一把锁）来实现线程安全，JDK中典型的实现是BlockingQueue；
• 非阻塞队列可以用循环CAS的方式来保证数据的一致性，来达到线程安全的目的。

接下来我们就来看看JDK是如何使用非阻塞的方式来实现线程安全队列ConcurrentLinkedQueue的。

ConcurrentLinkedQueue源码分析

ConcurrentLinkedQueue是一个基于链接节点的无界线程安全队列，遵循队列的FIFO原则，队尾入队，队首出队。我们先来看下队列的基础数据结构以及初始化相关源码实现。

队列基础数据结构Node及初始化

• Node实现
  

  Node实现
  从源码可以看出，Node有两个私有属性item和指向下一个节点的next，为了降低开销，item和next都被声明成volatile类型，同时，它们使用CAS来保证更新的线程安全。

• ConcurrentLinkedQueue数据结构
  

  ConcurrentLinkedQueue私有属性
  ConcurrentLinkedQueue由head和tail节点组成，节点与节点之间通过next连接，从而来组成一个链表结构的队列。

• 队列初始化
  ConcurrentLinkedQueue有两个私有属性，head和tail：
  

  ConcurrentLinkedQueue私有属性
  接下来我们来看看ConcurrentLinkedQueue是如何初始化的。
  ConcurrentLinkedQueue初始化
  从源码可以看出，当初始化一个ConcurrentLinkedQueue对象时，会创建一个item和next都为null的节点，并让head和tail都指向该节点，初始化后的队列结构如下：
  初始化后结构图

看完数据结构及初始化后，接下里我们就该来看看队列的两个重要实现：入队和出队。

ConcurrentLinkedQueue入队

offer实现

入队的实质就是在队尾做节点插入，具体的执行流程如下：

1. 调用checkNotNull方法判断待入队元素是否为null，如果为null则抛出空指针异常；

2. 创建一个待入队节点；

3. 循环执行队尾插入：

   • 情况1：如果tail节点的下一个节点q为null，通过p.casNext(null, newNode)将p节点的next节点设置为待入队节点：

     • CAS设置成功：比较p和t，如果p不等t，将tail节点设置为待入队节点，入队成功，返回true，如果p等于t，直接返回true；
     • CAS设置不成功，表明有其他的线程对tail节点有所更改，那么，继续执行for循环，直到入队成功。

   • 情况3：变换一下顺序，先说最后一种情况，改写一下代码，就比较容易理解了：

     
     更改后代码
     

     可以看出来，如果p和t相等，则将p指向q，否则，判断tail节点是否发生变化，如果没有发生变化，将p指向q，如果发生变化，设置p为尾节点；

   • 情况2：通过情况3的操作，p和q相等的情况就可能会出现了，此时，若tail节点没有发生变化，那么应该就是head节点发生了变化，设置p为head节点，从头开始遍历队列，如果是tail节点发生变化，设置p为tail节点。

到这里为止，入队的源码分析差不多，说实在的，还是很懵，大家心里可能可能还在纠结，第一，入队的过程到底是什么样子的呀？第二，入队直接CAS更新tail节点就可以了，为什么还要那么费劲的分情况处理？

针对第一个问题，给出一个图，大家就能完全明白了：

队列入队结构变化图.jpg

1. 添加节点1，此时tail节点的next节点为null，符合上述代码中的情况1，更新队列的tail节点的next节点为元素1，由于初始化是head节点等于tail节点，所以此时head和tail的next节点均指向节点1；

2. 添加节点2，此时tail节点的next节点不为null，同时p也不等于q，符合上述代码中的情况3，首先执行情况3将p指向tail节点的next节点，再执行情况1相关逻辑，设置节点1的next节点为元素2，此时p不等于t，更新tail节点，将tail节点指向元素2；

节点3和4入队过程与1和2入队一致，在这里我就不再做赘述。需要注意的是：tail节点并不一定是指向队列的最后一个节点，它可能指向最后一个节点的前一个节点！！！

针对第二个问题，我们来尝试换一种方式思考，假如我们每次就让tail节点作为队尾节点，每次的入队所要做的事情其实就是将入队节点设置成尾节点，代码可以简化成这样：

tail为队尾节点的入队
上述代码量确实非常少，而且逻辑非常清楚和易懂，但是这样做有个缺点就是每次入队都需要循环CAS更新tail节点。
如果能减少更新tail节点的次数，那么就能提高入队的效率，所以，Doug Lea并没有让tail节点作为队尾节点，只有tail节点与队尾节点之间的距离等于1的时候才需要更新tail节点。但是，这样就可能导致当队列长度越长的时候每次入队定位尾节点的时间就会越长，即便是这样，它仍然可以提高入队效率，因为从本质上来看，volatile变量的写操作的开销要远远大于读操作的。

分析完入队，接下来我们来看看ConcurrentLinkedQueue的出队。

ConcurrentLinkedQueue出队

poll实现

出队的实质就是情况表头节点的引用并返回表头节点的值，具体的之行逻辑如下：

1. 获取头结点的元素；

2. 如果表头节点的元素不为null，并且调用p.casItem(item, null)设置表头节点数据为null成功：

   • 如果p不等于head节点，此时表头发生了变化，调用updateHead方法更新表头节点，然后返回删除节点item；
   • 否则，不更新表头节点，直接返回删除节点item。

3. 如果步骤2条件不成立并且表头节点的next节点q为null，那么此时队列只有一个为null的节点，调用updateHead方法更新表头节点为p，然后返回null；

4. 如果步骤2和3的条件均不成立并且p等于q，跳转到restartFromHead标记重新执行；

5. 步骤2，3，4均不成立，将p指向q；

6. 循环执行上述步骤；

源码其实就这么多，为了方便理解出队的过程，还是照样给一个图：

队列出队结构变化图

1. 节点1出队，此时head的item为null，执行上述代码逻辑中的步骤5，p指向节点1，此时p的item域不为空，执行步骤2，将节点1的item设置为null，此时p不等于h，更新头结点（如果p的next节点不为null，将头结点指向q，否则指向p），返回节点1的item，head执行节点2；

2. 节点2出队，此时head的item不为null，执行上述代码逻辑中步骤2，将节点2的item设置为null，此时p等于h，直接返回节点2的item，head仍然指向节点2；

节点3和4出队过程与1和2出队一致，在这里我就不再做赘述。需要注意的是head节点并不一定是指向队列的第一个有效节点，它可能指向有效节点的前一个节点！！！

注：这里的有效节点是指从head节点向后遍历可达的节点当中，item不为null的节点。

当然，为什么head节点不总是指向队列的第一个有效节点，其原因跟入队是一样的，这么做的最主要也是减少CAS更新head节点的次数，从而提高出队效率。