一篇文章带你深度剖析高效读写的队列：ConcurrentLinkedQueue类

ゝ一纸荒年。 2022-12-26 05:00 73阅读 0赞

队列Queue也是常用的数据结构之一。在JDK中提供了一个`ConcurrentLinkedQueue`类用来实现高并发的队列。从名字可以看到，这个队列使用链表作为其数据结构。有关`ConcurrentLinkedQueue`类的性能测试大家可以自行尝试，这里限于篇幅就不再给出性能测试的代码了。

大家只要知道`ConcurrentLinkedQueue`类应该算是在高并发环境中性能最好的队列就可以了。它之所以能有很好的性能，是因为其内部复杂的实现

作为一个链表，自然需要定义有关链表内的节点，在`ConcurrentLinkedQueue`类中，定义的节点Node核心如下：

private static class Node<E>{ 
    	volatile E item;
    	volatile Node<E> next;
    }

其中item是用来表示目标元素的。比如，当列表中存放String时，item就是String类型。字段next表示当前Node的下一个元素，这样每个Node就能环环相扣，串在一起了。图3.14显示了`ConcurrentLinkedQueue`类的基本结构。

![在这里插入图片描述][20201203160625712.png]  
对Node进行操作时，使用了CAS。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg_size_16_color_FFFFFF_t_70]  
方法casItem()表示设置当前Node的item值。它需要两个参数，第一个参数为期望值，第二个参数为设置目标值。当当前值等于cmp期望值时，就会将目标设置为val。同样casNext()方法也是类似的，但是它用于设置next字段，而不是item字段。

ConcurrentLinkedQueue类内部有两个重要的字段，head和tail，分别表示链表的头部和尾部，它们都是Node类型。对于head来说，它永远不会为null，并且通过head及succ()后继方法一定能完整地遍历整个链表。对于tail来说，它自然应该表示队列的末尾。

但`ConcurrentLinkedQueue`类的内部实现非常复杂，它允许在运行时链表处于多个不同的状态。以tail为例，一般来说，我们期望tail总是为链表的末尾，但实际上，tail的更新并不是及时的，可能会产生拖延现象。图3.15显示了插入时tail的更新情况，可以看到tail的更新会产生滞后，并且每次更新会跳跃两个元素。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg_size_16_color_FFFFFF_t_70 1]  
可以看到tail并不总是在更新。下面就是在`ConcurrentLinkedQueue`类中向队列中添加元素的offer()方法（本节中使用JDK 7u40的代码，不同版本的代码可能存在差异）。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg_size_16_color_FFFFFF_t_70 2]  
首先值得注意的是，这个方法没有任何锁操作。线程安全完全由CAS操作和队列的算法来保证。整个方法的核心是for循环，这个循环没有出口，直到尝试成功，这也符合CAS操作的流程。当第一次加入元素时，由于队列为空，因此p.next为null。程序进入第8行，并将p的next节点赋值为newNode，也就是将新的元素加入队列中。此时p==t成立，因此不会执行第12行的代码更新tail末尾。如果casNext()方法成功，则程序直接返回，如果失败，则再进行一次循环尝试，直到成功。因此，增加一个元素后，tail并不会被更新。

当程序试图增加第2个元素时，由于t还在head的位置上，因此p.next指向实际的第一个元素，因此第6行的q!=null表示q不是最后的节点。由于往队列中增加元素需要最后一个节点的位置，因此，循环开始查找最后一个节点。于是，程序会进入第23行，获得最后一个节点。此时，p实际上是指向链表中的第一个元素，而它的next为null，故在第2个循环时，进入第8行。p更新自己的next，让它指向新加入的节点。如果成功，由于此时p!=t成功，则会更新t的所在位置，将t移动到链表最后。

第17行处理了p==q的情况。这种情况是由于遇到了哨兵（sentinel）节点导致的。所谓哨兵节点，就是next指向自己的节点。这种节点在队列中的存在价值不大，主要表示要删除的节点，或者空节点。当遇到哨兵节点时，由于无法通过next取得后续的节点，因此很可能直接返回head，期望通过从链表头部开始遍历，进一步找到链表末尾。一旦在执行过程中发生tail被其他线程修改的情况，则进行一次“打赌”，使用新的tail作为链表末尾（这样就避免了重新查找tail的开销）。

如果大家对Java不是特别熟悉，则可能会对类似下面的代码产生疑惑（第20行）：

p = (t !=(t=tail)) ? t:head;

这句代码虽然只有短短一行，但是包含的信息比较多。首先“!=”并不是原子操作，它是可以被中断的。也就是说，在执行“!=”时，程序会先取得t的值，再执行t=tail，并取得新的t的值，然后比较这两个值是否相等。在单线程时，t!=t这种语句显然不会成立。但是在并发环境中，有可能在获得左边的t值后，右边的t值被其他线程修改。这样，t!=t就可能成立了，这里就是这种情况。如果在比较过程中，tail被其他线程修改，当它再次赋值给t时，就会导致等式左边的t和右边的t不同。如果两个t不相同，表示tail在中途被其他线程篡改。这时，我们就可以用新的tail作为链表末尾，也就是这里等式右边的t。但如果tail没有被修改，则返回head，要求从头部开始，重新查找尾部。

作为简化问题，我们考察`t!=t`的字节码（注意这里假设t为静态整形变量）。

![在这里插入图片描述][20201203161816118.png]

可以看到，在字节码层面，t被先后取了两次，在多线程环境下，我们自然无法保证两次对t的取值是相同的，图3.16显示了这种情况。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg_size_16_color_FFFFFF_t_70 3]  
下面我们来看一下哨兵节点是如何产生的。

![在这里插入图片描述][20201203161859930.png]  
上述代码第3行弹出队列内的元素，其执行过程如下：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg_size_16_color_FFFFFF_t_70 4]  
可以看到，在updateHead中将p作为新的链表头部（通过casHead()实现），而原有的head就被设置为哨兵（通过lazySetNext()方法实现）。

这样一个哨兵节点就产生了，而由于此时原有的head头部和tail实际上是同一个元素。因此，再次用offer()方法插入元素时，就会遇到这个tail，也就是哨兵。这就是offer()代码中，第17行的判断的意义。

通过这些说明，大家应该可以明显感觉到，不使用锁而单纯地使用CAS操作会要求在应用层面保证线程安全，并处理一些可能存在的不一致问题，大大增加了程序设计和实现的难度。它带来的好处就是可以使性能飞速提升，因此，在有些场合也是值得的

[20201203160625712.png]: /images/20221120/e698cb52f64d47018d0b083d5cee2d43.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg_size_16_color_FFFFFF_t_70]: /images/20221120/eda470dc17304f398c0c5b7b0c3f3890.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201203160933396.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201203161241835.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg==,size_16,color_FFFFFF,t_70
[20201203161816118.png]: https://img-blog.csdnimg.cn/20201203161816118.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20201203161835619.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg==,size_16,color_FFFFFF,t_70
[20201203161859930.png]: https://img-blog.csdnimg.cn/20201203161859930.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20201203161927412.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg==,size_16,color_FFFFFF,t_70