开发者

Java中的ConcurrentLinkedQueue松散队列解析

目录
  • 一、为什么叫松散队列?
  • 二、如何实现线程安全?
    • add入队操作
    • poll出队操作
  • 三、优缺点

    一、为什么叫松散队列?

    唯一一个使用cas实现的线程安全并发效率高的集合。

    链表是松散的,链表节点并不都是有效的,允许存在无效节点val=null,但是只有最后一个节点才能next=null 为什么线程安全需要把链表做成松散的。就是因为入队分为两步,cas设置最后一个节点的next,和cas设置tail,两个操作之间并无原子性,所以可能并发操作了多个cas设置next,才设置tail。tail滞后很多。 出队的时候,也需要分为两步,cas将值设编程置成null。cas移动head。head也会滞后很多。所以会有很多节点已经出队为null,但是依然可以遍历到。因此叫做松散队列。

    二、如何实现线程安全?

    add入队操作

    tail节点并不是最后一个节点

    1、从 tail 节点开始遍历到尾节点,若定位到尾节点(p.next == null),则入队。

    2、遍历过程中,如果遍历到无效节点(p.next == p)说明p已经并发出队,需要重新从有效节点(tail 或 head)开始遍历。

    3、遍历过程中,时刻关注 tail 节点是否无效。若无效了需要重新从最新的 tail(如果tail失效,从head) 开始遍历,否则继续遍历当前的下一个节点。

    4、找到最后一个节点后,进行入队操编程客栈作,使用cas将next修改为新节点,如果tail->next!=null,需要使用cas将tail设置为新节点。

    cas设置next,和cas设置tail,两个操作之间并无原子性,所以可能并发操作了多个cas设置next,才设置tail。tail滞后很多。

    如下图B节点已经被poll了,tail还在B节点前面。tail失效了,从tail无法遍历到最后一个节点。

    Java中的ConcurrentLinkedQueue松散队列解析

    poll出队操作

    1、从 head 节点开始遍历找出首个有效节点(p.item != null),返回该节点的数据(p.item)。

    2、遍历过程中,如果遍历到尾节点(p.next == null),则返回空。

    3、遍历过程中,如果遍历到无效节点(p.next == p),说明其他线程修改了 head,需要重新从有效节点(新的 head)开始遍历。

    4、cas将值设置成null。cas移动head。

    5、更新head,需要注意的是,并不是每次出队时都执行 updateHead() 更新 head 节点: 当 head 节点里有元素时,直接弹出 head 节点里的元素,设置为null,而不会更新 head 节点。

    Java中的ConcurrentLinkedQueue松散队列解析

    只有当 head 节点里没有元素时,出队操作才会更新 head 节点。

    Java中的ConcurrentLinkedQueue松散队列解析

    三、优缺点

    从它的入队编程出队机制就可以看出,优缺点非常明显。

    优点: 1、并发效率高,入队出队不需要加锁进行线程同步,全程使用cas操作

    缺点: 1、入队出队都分为两步cas,cas之间是控制不了的,所以会产生tail滞后,tail失效,链表节点poll了,还可以继续访问没有释放,内存是松散的,无效节点占用内存,内存开销大。

    2、由于head和tail都不是严格指向头尾,每次poll,add都需要遍历,浪费时间效率。concurrentLinkedQueue存的元素越多,效率越低。因此只适合高并发小容量的场景使用。

    3、size获取大小也要遍历所有节点才行

    到此这篇关于Java中的ConcurrentLinkedQueue松散队列解析的文章就介绍到这了,更多相关ConcurrentLinkedQueue松散队列内容请搜索编程客编程客栈栈(www.devze.com)以前的文章或继续浏览下面的相关文章php希望大家以后多多支持编程客栈(www.devze.com)!

    0

    上一篇:

    下一篇:

    精彩评论

    暂无评论...
    验证码 换一张
    取 消

    最新开发

    开发排行榜