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无法遍历到最后一个节点。

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 节点。

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

三、优缺点

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

优点： 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)！