ConcurrentLinkedQueue原理探究

发布时间:2024年01月09日

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的算法保证出队时移除节点操作的原子性。

文章来源:https://blog.csdn.net/zhuyufan1986/article/details/135475320
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。