滚雪球学Java(69)：深入浅出Java中高效的ConcurrentLinkedQueue队列底层实现与源码分析

2024-02-24 01:36
文章标签 java 分析 实现 源码 高效 深入浅出 队列 底层 69 concurrentlinkedqueue 滚雪球

本文主要是介绍滚雪球学Java(69)：深入浅出Java中高效的ConcurrentLinkedQueue队列底层实现与源码分析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

  咦咦咦，各位小可爱，我是你们的好伙伴——bug菌，今天又来给大家普及Java SE相关知识点了，别躲起来啊，听我讲干货还不快点赞，赞多了我就有动力讲得更嗨啦！所以呀，养成先点赞后阅读的好习惯，别被干货淹没了哦~

在这里插入图片描述

🏆本文收录于「滚雪球学Java」专栏，专业攻坚指数级提升，助你一臂之力，带你早日登顶🚀，欢迎大家关注&&收藏！持续更新中，up！up！up！！

环境说明：Windows 10 + IntelliJ IDEA 2021.3.2 + Jdk 1.8

文章目录

  • 前言
  • 摘要
  • ConcurrentLinkedQueue
    • 概述
    • 源代码解析
      • offer方法
      • poll方法
    • 应用场景案例
    • 优缺点分析
      • 优点
      • 缺点
    • 类代码方法介绍
      • Node类
      • ConcurrentLinkedQueue类
    • 测试用例
      • 测试代码演示
      • 测试结果
      • 测试代码分析
    • 小结
  • 总结
    • 附录源码
  • ☀️建议/推荐你
  • 📣关于我

前言

  多线程开发已成为现代软件开发的基础。在多线程开发中，线程之间的通信和数据同步是非常重要的，而队列是实现线程间通信和数据同步的重要工具。本文将介绍Java中高效的ConcurrentLinkedQueue队列的底层实现和源码分析。

摘要

  本文将介绍ConcurrentLinkedQueue队列的底层实现和源码分析，包括应用场景案例、优缺点分析、类代码方法介绍和测试用例。通过阅读本文，读者可以了解Java中高效的ConcurrentLinkedQueue队列的原理和使用方法。

ConcurrentLinkedQueue

概述

  ConcurrentLinkedQueue是Java并发包中的一个线程安全的无界队列实现，使用CAS（Compare And Swap）算法实现线程安全。ConcurrentLinkedQueue是一个基于链表结构的队列，它可以保证在多线程环境下的高效性和安全性。在多线程并发的场景中，ConcurrentLinkedQueue是一个非常好的选择。

源代码解析

public class ConcurrentLinkedQueue<E> extends AbstractQueue<E>implements Queue<E>, java.io.Serializable {/*** Head of linked list.* Invariant: head.item == null*/private transient volatile Node<E> head;/*** Tail of linked list.* Invariant: last.next == null*/private transient volatile Node<E> tail;public ConcurrentLinkedQueue() {head = tail = new Node<E>(null);}private void updateHead(Node<E> h, Node<E> p) {if (h != p && casHead(h, p))h.lazySetNext(p);}private void updateTail(Node<E> t, Node<E> p) {if (t != p && casTail(t, p))t.lazySetNext(p);}public boolean offer(E e) {checkNotNull(e);final Node<E> newNode = new Node<E>(e);for (Node<E> t = tail, p = t;;) {Node<E> q = p.next;if (q == null) {if (p.casNext(null, newNode)) {if (p != t)updateTail(t, newNode);return true;}} else if (p == q) {p = (t != (t = tail)) ? t : head;} else {p = (p != t && t != (t = tail)) ? t : q;}}}public E poll() {restartFromHead:for (;;) {for (Node<E> h = head, p = h, q;;) {E item = p.item;if (item != null && p.casItem(item, null)) {if (p != h) // hop two nodes at a timeupdateHead(h, ((q = p.next) != null) ? q : p);return item;} else if ((q = p.next) == null) {updateHead(h, p);return null;} else if (p == q) {continue restartFromHead;} else {p = q;}}}}private static class Node<E> {volatile E item;volatile Node<E> next;Node(E item) {// assert item != null;this.item = item;}boolean casItem(E cmp, E val) {return UNSAFE.compareAndSwapObject(this, itemOffset, cmp, val);}void lazySetNext(Node<E> val) {UNSAFE.putOrderedObject(this, nextOffset, val);}boolean casNext(Node<E> cmp, Node<E> val) {return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val);}private static final sun.misc.Unsafe UNSAFE;private static final long itemOffset;private static final long nextOffset;static {try {UNSAFE = sun.misc.Unsafe.getUnsafe();Class<?> k = Node.class;itemOffset = UNSAFE.objectFieldOffset(k.getDeclaredField("item"));nextOffset = UNSAFE.objectFieldOffset(k.getDeclaredField("next"));} catch (Exception e) {throw new Error(e);}}}
}

  ConcurrentLinkedQueue的底层实现是基于链表结构的。
  它有两个重要的属性：head和tail。其中head是链表的头节点，tail是链表的尾节点。当ConcurrentLinkedQueue中没有元素的时候，head和tail是同一个节点。当ConcurrentLinkedQueue中有一个元素的时候，head是链表的头节点，tail是链表的尾节点。当ConcurrentLinkedQueue中有多个元素的时候，tail指向的是最后一个元素所在的节点。

代码分析

  这段代码实现了一个线程安全的队列 ConcurrentLinkedQueue，它是基于链表实现的。它包含两个成员变量 head 和 tail，分别表示链表的头和尾。当队列为空时，head 和 tail 指向同一个节点，该节点的 item 域为 null。

  offer 方法用于在队列的尾部添加新元素，它首先创建一个新的节点 newNode，然后使用一个 for 循环，不断尝试将 newNode 添加到队列的尾部。循环中的变量 t 表示当前节点的 tail，p 表示要添加 newNode 的前一个节点。首先，通过 p 节点的 next 指针找到 p 的后继节点 q，如果 q 为 null，则说明 p 是队列的最后一个节点，此时可以通过 CAS 操作将 newNode 添加到 p 的 next 指针上。如果 CAS 操作成功，则更新 tail 指针。否则，说明有另一个线程已经修改了 p 的 next 指针，那么当前线程需要重新获取节点的 tail 和 p。如果 p 和 t 不相等，则更新 t 的指针并重新获取节点的 tail 和 p。

  poll 方法用于从队列的头部移除一个元素并返回它。它首先通过一个无限循环从 head 节点开始遍历链表，尝试找到第一个不为 null 的节点 p，然后使用 CAS 操作将 p 的 item 值设置为 null，表示该节点已经被移除。如果 CAS 操作成功，则判断 p 是否为队列的头节点 h，如果不是，则说明队列中间有一个或多个节点已经被移除，需要将这些节点也移除并更新 head 指针。如果 p 是队列的头节点，则直接返回 p 的 item 值。如果 p 的 next 指针为 null，则说明队列已经为空，直接返回 null。如果 p 和 p 的后继节点相同，则说明队列正在被修改，需要重新从 head 节点开始遍历链表。

  Node 类是链表节点的实现。它包含一个 item 值和一个 next 指针，分别表示节点的元素和后继节点。该类使用了 CAS 操作来保证多线程情况下链表节点的修改是安全的。它还包含了一些静态变量和代码块，用于获取 item 和 next 字段的偏移量，以及获取 UNSAFE 对象。这些变量和方法通常不需要我们关注，是为了实现 CAS 操作而引入的。

  如下是部分源码截图：

在这里插入图片描述

offer方法

offer方法用于添加元素到队列中。它采用了一个基于自旋锁的算法。

  • 首先，通过checkNotNull(e)方法检查元素是否为null。
  • 然后，通过尾节点tail获取当前的节点p。
  • 如果当前节点p的下一个节点q是null，说明当前节点是链表的尾节点。
  • 如果当前节点p的下一个节点q不是null，则说明当前节点不是链表的尾节点，需要重新找到尾节点。
  • 如果节点p的下一个节点q是null，则尝试使用CAS算法将新节点添加到链表中。
  • 如果CAS操作成功，更新尾节点tail的指针。
  • 如果CAS操作失败，则重新回到第2步。

poll方法

poll方法用于从队列中弹出一个元素。它采用了一个基于自旋锁的算法。

  • 首先，获取链表的头节点head和当前节点p。
  • 如果p不是null，且p的item不是null，说明当前节点p是要被弹出的节点。
  • 如果CAS操作成功，更新头节点的指针。如果当前节点p不是头节点，则需要调用updateHead方法更新头节点的指针。
  • 如果当前节点p是头节点，则直接更新头节点的指针。
  • 如果p的下一个节点q是null，则说明队列已经为空，直接返回null。
  • 如果p的下一个节点q就是头节点head，则说明其他线程正在修改链表，需要重新从头节点开始操作。
  • 如果p的下一个节点q既不是null，也不是头节点head，则说明其他线程正在修改链表，需要直接跳到节点q继续操作。

应用场景案例

  ConcurrentLinkedQueue适用于多线程并发的场景中，例如生产者消费者模式，线程池等。

  在生产者消费者模式中，ConcurrentLinkedQueue可以作为任务队列使用。生产者线程向队列中添加任务，消费者线程从队列中取出任务并执行。

  在线程池中，ConcurrentLinkedQueue可以作为任务队列使用。线程池中的线程从队列中取出任务并执行。

优缺点分析

优点

  • 线程安全：ConcurrentLinkedQueue是线程安全的，可以在多线程并发的环境中使用。
  • 高效性：ConcurrentLinkedQueue采用了基于链表结构和CAS算法的实现方式，使其在多线程并发的场景中具有较高的效率。
  • 无界队列：ConcurrentLinkedQueue是一个无界队列，可以动态地添加元素，不需要事先确定队列的大小。

缺点

  • 不支持阻塞操作：ConcurrentLinkedQueue不支持阻塞操作，无法在队列为空时等待元素。

类代码方法介绍

Node类

Node类是ConcurrentLinkedQueue的内部类，表示链表中的一个节点。它具有以下属性：

  • item：表示节点的元素。
  • next：表示节点的下一个节点。

Node类定义了以下方法：

  • casItem(E cmp, E val)：比较并交换节点的元素。
  • lazySetNext(Node val)：无锁操作设置节点的下一个节点。
  • casNext(Node cmp, Node val)：比- compare And Swap节点的下一个节点。

在这里插入图片描述

ConcurrentLinkedQueue类

ConcurrentLinkedQueue类是ConcurrentLinkedQueue的主要实现类，它继承自AbstractQueue类和实现Queue、Serializable接口。它具有以下属性：

  • head：表示链表的头节点。
  • tail：表示链表的尾节点。

ConcurrentLinkedQueue类定义了以下方法：

  • offer(E e)：将元素添加到队列中。如果添加成功，则返回true，否则返回false。
  • poll()：从队列中弹出一个元素。如果队列为空，则返回null。
  • updateHead(Node h, Node p)：更新头节点指针。
  • updateTail(Node t, Node p)：更新尾节点指针。

在这里插入图片描述

测试用例

为了验证ConcurrentLinkedQueue的功能和性能，我们可以编写如下测试用例：

测试代码演示

package com.demo.javase.day69;import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;/*** @Author bug菌* @Date 2023-11-06 16:00*/
public class ConcurrentLinkedQueueTest {public static void main(String[] args) throws InterruptedException {final int THREAD_COUNT = 1000;final int ELEMENT_COUNT = 100;ExecutorService executorService = Executors.newFixedThreadPool(THREAD_COUNT);ConcurrentLinkedQueue<Integer> queue = new ConcurrentLinkedQueue<>();// testAddfor (int i = 0; i < ELEMENT_COUNT; i++) {executorService.execute(() -> {for (int j = 0; j < ELEMENT_COUNT; j++) {queue.offer(j);}});}executorService.shutdown();executorService.awaitTermination(10, TimeUnit.SECONDS);assert ELEMENT_COUNT * ELEMENT_COUNT == queue.size();// testPollexecutorService = Executors.newFixedThreadPool(THREAD_COUNT);for (int i = 0; i < ELEMENT_COUNT; i++) {queue.offer(i);}for (int i = 0; i < THREAD_COUNT; i++) {executorService.execute(() -> {for (int j = 0; j < ELEMENT_COUNT; j++) {Integer element = queue.poll();assert element != null;}});}executorService.shutdown();executorService.awaitTermination(10, TimeUnit.SECONDS);System.out.println("queue.size() = " + queue.size()); //0}
}

  测试用例中，testAdd方法模拟了1000个线程同时向队列中添加100个元素的场景，并校验队列中元素的数量是否正确。testPoll方法模拟了1000个线程同时从队列中取出100个元素的场景，并校验队列中元素的数量是否正确。通过执行这些测试用例，可以验证ConcurrentLinkedQueue的功能和性能。

测试结果

  根据如上测试用例，本地测试结果如下，仅供参考，你们也可以自行修改测试用例或者添加更多的测试数据或测试方法，进行熟练学习以此加深理解。

在这里插入图片描述

测试代码分析

  根据如上测试用例，在此我给大家进行深入详细的解读一下测试代码，以便于更多的同学能够理解并加深印象。

  该代码为测试并发队列 ConcurrentLinkedQueue 的使用，主要包含两个测试方法：

  1. testAdd：测试并发添加元素。开启多个线程向队列中添加元素；
  2. testPoll：测试并发取出元素。先将若干元素添加到队列中，然后开启多个线程同时取出元素。

  在测试添加元素的过程中，多个线程同时向队列中添加元素，由于 ConcurrentLinkedQueue 内部采用 CAS 算法保证并发的安全性，因此不需要额外的加锁操作，可以保证多线程安全的同时高效地添加元素。

  在测试取出元素的过程中，多个线程同时从队列中取出元素，同样由于 ConcurrentLinkedQueue 内部采用 CAS 算法保证并发的安全性，因此不需要额外的加锁操作，可以保证多线程安全地同时取出元素。

小结

  本文主要介绍了Java中高效的ConcurrentLinkedQueue队列的底层实现和源码分析，包括应用场景案例、优缺点分析、类代码方法介绍和测试用例。ConcurrentLinkedQueue是基于链表结构的队列，使用CAS算法实现线程安全，能够保证多线程并发环境下的高效性和安全性。它适用于多线程并发场景中，如生产者消费者模式，线程池等。本文还提供了测试用例，验证了ConcurrentLinkedQueue的功能和性能。

总结

  本文介绍了Java并发包中的ConcurrentLinkedQueue队列，包括其基于链表的底层实现和源码分析，应用场景案例，优缺点分析，以及类代码方法介绍和测试用例。ConcurrentLinkedQueue是一个线程安全的无界队列实现，在多线程并发的场景中具有高效性和安全性。它适用于生产者消费者模式和线程池等多线程并发的场景中。ConcurrentLinkedQueue的优点是线程安全、高效性、无界队列，不足之处在于不支持阻塞操作。本文给出了测试用例，验证了ConcurrentLinkedQueue的功能和性能。

  …
  好啦，这期的内容就基本接近尾声啦，若你想学习更多，可以参考这篇专栏总结《「滚雪球学Java」教程导航帖》，本专栏致力打造最硬核 Java 零基础系列学习内容，🚀打造全网精品硬核专栏，带你直线超车；欢迎大家订阅持续学习。

附录源码

  如上涉及所有源码均已上传同步在「Gitee」，提供给同学们一对一参考学习，辅助你更迅速的掌握。

☀️建议/推荐你

  无论你是计算机专业的学生，还是对编程有兴趣的小伙伴，都建议直接毫无顾忌的学习此专栏「滚雪球学Java」，bug菌郑重承诺，凡是学习此专栏的同学，均能获取到所需的知识和技能，全网最快速入门Java编程，就像滚雪球一样，越滚越大，指数级提升。

  最后，如果这篇文章对你有所帮助，帮忙给作者来个一键三连，关注、点赞、收藏，您的支持就是我坚持写作最大的动力。

  同时欢迎大家关注公众号:「猿圈奇妙屋」 ，以便学习更多同类型的技术文章，免费白嫖最新BAT互联网公司面试题、4000G pdf电子书籍、简历模板、技术文章Markdown文档等海量资料。

📣关于我

  我是bug菌，CSDN | 掘金 | infoQ | 51CTO 等社区博客专家，历届博客之星Top30，掘金年度人气作者Top40，51CTO年度博主Top12，华为云 | 阿里云| 腾讯云等社区优质创作者，全网粉丝合计15w+ ；硬核微信公众号「猿圈奇妙屋」，欢迎你的加入！免费白嫖最新BAT互联网公司面试题、4000G pdf电子书籍、简历模板等海量资料。

这篇关于滚雪球学Java(69)：深入浅出Java中高效的ConcurrentLinkedQueue队列底层实现与源码分析的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/740538。

相关文章

JVM 的类初始化机制

JVM 的类初始化机制

前言 当你在 Java 程序中new对象时，有没有考虑过 JVM 是如何把静态的字节码（byte code）转化为运行时对象的呢，这个问题看似简单，但清楚的同学相信也不会太多，这篇文章首先介绍 JVM 类初始化的机制，然后给出几个易出错的实例来分析，帮助大家更好理解这个知识点。 JVM 将字节码转化为运行时对象分为三个阶段，分别是：loading 、Linking、initialization
阅读更多...
Spring Security 基于表达式的权限控制

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权，允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true （Spring security默认会带有ROLE_前缀）,去
阅读更多...
浅析Spring Security认证过程

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程，特意画了如下的类图，包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口，接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti
阅读更多...
Spring Security--Architecture Overview

Spring Security--Architecture Overview

1 核心组件 这一节主要介绍一些在Spring Security中常见且核心的Java类，它们之间的依赖，构建起了整个框架。想要理解整个架构，最起码得对这些类眼熟。 1.1 SecurityContextHolder SecurityContextHolder用于存储安全上下文（security context）的信息。当前操作的用户是谁，该用户是否已经被认证，他拥有哪些角色权限…这些都被保
阅读更多...
Spring Security基于数据库验证流程详解

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明（认真看哦） AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证，则会调用 #attemptAuthentica
阅读更多...
Spring Security 从入门到进阶系列教程

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门（一）：登录与退出》 《Spring-Security-入门（二）：基于数据库验证》 《Spring-Security-入门（三）：密码加密》 《Spring-Security-入门（四）：自定义-Filter》 《Spring-Security-入门（五）：在 Sprin
阅读更多...
Java架构师知识体认识

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物
阅读更多...
Java进阶13讲__第12讲_1/2

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
hdu1180（广搜+优先队列）

hdu1180（广搜+优先队列）

此题要求最少到达目标点T的最短时间，所以我选择了广度优先搜索，并且要用到优先队列。 另外此题注意点较多，比如说可以在某个点停留，我wa了好多两次，就是因为忽略了这一点，然后参考了大神的思想，然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2