我的编程空间,编程开发者的网络收藏夹
学习永远不晚

Java并发编程之ConcurrentLinkedQueue源码的示例分析

短信预约 -IT技能 免费直播动态提醒
省份

北京

  • 北京
  • 上海
  • 天津
  • 重庆
  • 河北
  • 山东
  • 辽宁
  • 黑龙江
  • 吉林
  • 甘肃
  • 青海
  • 河南
  • 江苏
  • 湖北
  • 湖南
  • 江西
  • 浙江
  • 广东
  • 云南
  • 福建
  • 海南
  • 山西
  • 四川
  • 陕西
  • 贵州
  • 安徽
  • 广西
  • 内蒙
  • 西藏
  • 新疆
  • 宁夏
  • 兵团
手机号立即预约

请填写图片验证码后获取短信验证码

看不清楚,换张图片

免费获取短信验证码

Java并发编程之ConcurrentLinkedQueue源码的示例分析

这篇文章给大家分享的是有关Java并发编程之ConcurrentLinkedQueue源码的示例分析的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。

一、ConcurrentLinkedQueue介绍

并编程中,一般需要用到安全的队列,如果要自己实现安全队列,可以使用2种方式:
方式1:加锁,这种实现方式就是我们常说的阻塞队列。
方式2:使用循环CAS算法实现,这种方式实现队列称之为非阻塞队列。
从点到面, 下面我们来看下非阻塞队列经典实现类:ConcurrentLinkedQueue (JDK1.8版)

ConcurrentLinkedQueue 是一个基于链接节点的无界线程安全的队列。当我们添加一个元素的时候,它会添加到队列的尾部,当我们获取一个元素时,它会返回队列头部的元素。它采用了“wait-free”算法来实现,用CAS实现了非阻塞的线程安全队列。当多个线程共享访问一个公共 collection 时,ConcurrentLinkedQueue 是一个恰当的选择。此队列不允许使用 null 元素,因为移除元素时实际是将节点中item置为null,如果元素本身为null,则跟删除有冲突

我们首先看一下ConcurrentLinkedQueue的类图结构先,好有一个内部逻辑有一个大概的印象,如下图所示: 

Java并发编程之ConcurrentLinkedQueue源码的示例分析

主要属性head节点,tail节点

// 链表头节点private transient volatile Node<E> head;// 链表尾节点private transient volatile Node<E> tail;

主要内部类Node

类Node在static方法里获取到item和next的内存偏移量,之后通过casItem和casNext更改item值和next节点

private static class Node<E> {    volatile E item;    volatile Node<E> next;         Node(E item) {        //将item存放在本节点的itemOffset偏移量位置的内存里        UNSAFE.putObject(this, itemOffset, item);//设置this对象的itemoffset位置    }    //更新item值    boolean casItem(E cmp, E val) {       //this对象的itemoffset位置存放的值如果和期望值cmp相等,则替换为val        return UNSAFE.compareAndSwapObject(this, itemOffset, cmp, val);    }     void lazySetNext(Node<E> val) {      //this对象的nextOffset位置存入val        UNSAFE.putOrderedObject(this, nextOffset, val);    }    //更新next节点值    boolean casNext(Node<E> cmp, Node<E> val) {     //this对象的nextOffset位置存放的值如果和期望值cmp相等,则替换为val        return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val);    }     // Unsafe mechanics     private static final sun.misc.Unsafe UNSAFE;    //当前节点存放的item的内存偏移量    private static final long itemOffset;    //当前节点的next节点的内存偏移量    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同样在static方法里获取到head和tail的内存偏移量:之后通过casHead和casTail更改head节点和tail节点值

static {    try {        UNSAFE = sun.misc.Unsafe.getUnsafe();        Class<?> k = ConcurrentLinkedQueue.class;        headOffset = UNSAFE.objectFieldOffset            (k.getDeclaredField("head"));        tailOffset = UNSAFE.objectFieldOffset            (k.getDeclaredField("tail"));    } catch (Exception e) {        throw new Error(e);    }} private boolean casTail(Node<E> cmp, Node<E> val) {    return UNSAFE.compareAndSwapObject(this, tailOffset, cmp, val);} private boolean casHead(Node<E> cmp, Node<E> val) {    return UNSAFE.compareAndSwapObject(this, headOffset, cmp, val);}

二、构造方法

  • 无参构造函数,head=tail=new Node<E>(null)=空节点(里面无item值)

  • 集合构造函数(集合中每个元素不能为null):就是将集合中的元素挨个链起来

//无参构造函数,head=tail=new Node<E>(null)=空节点//初始一个为空的ConcurrentLinkedQueue,此时head和tail都指向一个item为null的节点public ConcurrentLinkedQueue() {    // 初始化头尾节点    head = tail = new Node<E>(null);} //集合构造函数:就是将集合中的元素挨个链起来public ConcurrentLinkedQueue(Collection<? extends E> c) {    Node<E> h = null, t = null;    for (E e : c) {        checkNotNull(e);        Node<E> newNode = new Node<E>(e);        if (h == null)            h = t = newNode;        else {            t.lazySetNext(newNode);//可以理解为一种懒加载,  将t的next值设置为newNode            t = newNode;        }    }    if (h == null)        h = t = new Node<E>(null);    head = h;    tail = t;} private static void checkNotNull(Object v) {    if (v == null)        throw new NullPointerException();} //putObjectVolatile的内存非立即可见版本,//写后结果并不会被其他线程看到,通常是几纳秒后被其他线程看到,这个时间比较短,所以代价可以接收void lazySetNext(Node<E> val) {    UNSAFE.putOrderedObject(this, nextOffset, val);}

三、入队 

获取到当前尾节点p=tail:

  • 如果p.next=null,代表是真正的尾节点,将新节点链入p.next=newNode。此时检查tail是否还是p,如果不是p了,此时更新tail为最新的newNode(只有在tail节点后面tail.next成功添加的元素才不需要更新tail,其实更新不更新tail是交替的,即每添加俩次更新一次tail)。

  • 如果p.next=p,此时其实是p.next==p==null,此时代表p被删除了,此时需要从新的tail节点检查,如果此时tail节点还是原来的tail(原来的tail在p前面,肯定也被删除了),那就只能从head节点开始遍历了

  • 如果p.next!=null,代表有别的线程抢先添加元素了,此时需要继续p=p.next遍历获取是null的节点(此时需要如果tail变了就使用新的tail往后遍历)

public boolean offer (E e){    //先检查元素是否为null,是null则抛出异常 不是null,则构造新节点准备入队    checkNotNull(e);    final Node<E> newNode = new Node<E>(e);    //初始p指针和t指针都指向尾节点,p指针用来向队列后面推移,t指针用来判断尾节点是否改变    Node<E> t = tail, p = t;    for (; ; ) {        Node<E> q = p.next;        if (q == null) {//p.next为null,则代表p为尾节点,则将p.next指向新节点             // p is last node            if (p.casNext(null, newNode)) {                                if (p != t)                    casTail(t, newNode);  // Failure is OK.                return true;            }            // Lost CAS race to another thread; re-read next        } else if (p == q)                     p = (t != (t = tail)) ? t : head;        else                    // Check for tail updates after two hops.            p = (p != t && t != (t = tail)) ? t : q;    }}

四、出队

poll出队:
获取到当前头节点p=head:如果成功设置了item为null,即p.catItem(item,null),
如果此时被其他线程抢走消费了,此时需要p=p.next,向后继续争抢消费,直到成功执行p.catItem(item,null),此时检查p是不是head节点,如果不是更新p.next为头结点

public E poll() {    restartFromHead:    for (;;) {        // p节点表示首节点,即需要出队的节点        for (Node<E> h = head, p = h, q;;) {            E item = p.item;             // 如果p节点的元素不为null,则通过CAS来设置p节点引用的元素为null,如果成功则返回p节点的元素            if (item != null && p.casItem(item, null)) {                // Successful CAS is the linearization point                // for item to be removed from this queue.                // 如果p != h,则更新head                if (p != h) // hop two nodes at a time                    updateHead(h, ((q = p.next) != null) ? q : p);                return item;            }            // 如果头节点的元素为空或头节点发生了变化,这说明头节点已经被另外一个线程修改了。            // 那么获取p节点的下一个节点,如果p节点的下一节点为null,则表明队列已经空了            else if ((q = p.next) == null) {                // 更新头结点                updateHead(h, p);                return null;            }            // p == q,则使用新的head重新开始            else if (p == q)                continue restartFromHead;            // 如果下一个元素不为空,则将头节点的下一个节点设置成头节点            else                p = q;        }    }}

五、总结

offer:

找到尾节点,将新节点链入到尾节点后面,tail.next=newNode,

由于多线程操作,所以拿到p=tail后cas操作执行p.next=newNode可能由于被其他线程抢去而执行不成功,此时需要p=p.next向后遍历,直到找到p.next=null的目标节点。继续尝试向其后面添加元素,添加成功后检查p是否是tail,如果不是tail,则更新tail=p,添加不成功继续向后next遍历

poll:

获取到当前头节点p=head:如果成功设置了item为null,即p.catItem(item,null),

如果此时被其他线程抢走消费了,此时需要p=p.next,向后继续争抢消费,直到成功执行p.catItem(item,null),此时检查p是不是head节点,如果不是更新头结点head=p.next(因为p已经删除了)

更新tail和head:

不是每次添加都更新tail,而是间隔一次更新一次(head也是一样道理):第一个抢到的线程拿到tail执行成功tail.next=newNode1此时不更新tail,那么第二个线程再执行成功添加p.next=newNode2会判断出p是newNode1而不是tail,所以就更新tail为newNode2。

tail节点不总是最后一个,head节点不总是第一个设计初衷:

让tail节点永远作为队列的尾节点,这样实现代码量非常少,而且逻辑非常清楚和易懂。但是这么做有个缺点就是每次都需要使用循环CAS更新tail节点。如果能减少CAS更新tail节点的次数,就能提高入队的效率。

在JDK 1.7的实现中,doug lea使用hops变量来控制并减少tail节点的更新频率,并不是每次节点入队后都将 tail节点更新成尾节点,而是当tail节点和尾节点的距离大于等于常量HOPS的值(默认等于1)时才更新tail节点,tail和尾节点的距离越长使用CAS更新tail节点的次数就会越少,但是距离越长带来的负面效果就是每次入队时定位尾节点的时间就越长,因为循环体需要多循环一次来定位出尾节点,但是这样仍然能提高入队的效率,因为从本质上来看它通过增加对volatile变量的读操作来减少了对volatile变量的写操作,而对volatile变量的写操作开销要远远大于读操作,所以入队效率会有所提升。

在JDK 1.8的实现中,tail的更新时机是通过p和t是否相等来判断的,其实现结果和JDK 1.7相同,即当tail节点和尾节点的距离大于等于1时,更新tail。

Java的优点是什么

1. 简单,只需理解基本的概念,就可以编写适合于各种情况的应用程序;2. 面向对象;3. 分布性,Java是面向网络的语言;4. 鲁棒性,java提供自动垃圾收集来进行内存管理,防止程序员在管理内存时容易产生的错误。;5. 安全性,用于网络、分布环境下的Java必须防止病毒的入侵。6. 体系结构中立,只要安装了Java运行时系统,就可在任意处理器上运行。7. 可移植性,Java可以方便地移植到网络上的不同机器。8.解释执行,Java解释器直接对Java字节码进行解释执行。

感谢各位的阅读!关于“Java并发编程之ConcurrentLinkedQueue源码的示例分析”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,让大家可以学到更多知识,如果觉得文章不错,可以把它分享出去让更多的人看到吧!

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

Java并发编程之ConcurrentLinkedQueue源码的示例分析

下载Word文档到电脑,方便收藏和打印~

下载Word文档

猜你喜欢

Java并发编程之ConcurrentLinkedQueue源码的示例分析

这篇文章给大家分享的是有关Java并发编程之ConcurrentLinkedQueue源码的示例分析的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。一、ConcurrentLinkedQueue介绍并编程中,一般需
2023-06-15

Java并发编程之线程池的示例分析

这篇文章将为大家详细讲解有关Java并发编程之线程池的示例分析,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。什么是线程池是一种基于池化思想管理线程的工具。池化技术:池化技术简单点来说,就是提前保存大量的资
2023-06-20

Java面试题之并发编程的示例分析

小编给大家分享一下Java面试题之并发编程的示例分析,希望大家阅读完这篇文章之后都有所收获,下面让我们一起去探讨吧!面试题1:说一下你对ReentrantLock的理解?ReentrantLock是JDK1.5引入的,它拥有与synchro
2023-06-20

Java并发编程之LongAdder源码解析

这篇文章主要为大家介绍了Java并发编程之LongAdder源码示例解析,有需要的朋友可以借鉴参考下,希望能够有所帮助,祝大家多多进步,早日升职加薪
2023-05-18

Java并发编程之Fork/Join框架的示例分析

这篇文章主要介绍了Java并发编程之Fork/Join框架的示例分析,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。一、Fork/Join框架的理解ForkJoinTask类属
2023-06-15

Java并发编程之关键字volatile的示例分析

这篇文章给大家分享的是有关Java并发编程之关键字volatile的示例分析的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。一、作用被 volatile 修饰的变量1.保证了不同线程对该变量操作的内存可见性2.禁止
2023-06-15

Java并发编程之同步容器与并发容器的示例分析

这篇文章主要为大家展示了“Java并发编程之同步容器与并发容器的示例分析”,内容简而易懂,条理清晰,希望能够帮助大家解决疑惑,下面让小编带领大家一起研究并学习一下“Java并发编程之同步容器与并发容器的示例分析”这篇文章吧。一、同步容器 1
2023-06-15

Java之JMM高并发编程实例分析

这篇文章主要介绍“Java之JMM高并发编程实例分析”,在日常操作中,相信很多人在Java之JMM高并发编程实例分析问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”Java之JMM高并发编程实例分析”的疑惑有所
2023-07-02

Java源码解析之ConcurrentHashMap的示例分析

小编给大家分享一下Java源码解析之ConcurrentHashMap的示例分析,希望大家阅读完这篇文章之后都有所收获,下面让我们一起去探讨吧!早期 ConcurrentHashMap,其实现是基于:分离锁,也就是将内部进行分段(Segme
2023-06-15

Go并发编程的示例分析

这篇文章给大家分享的是有关Go并发编程的示例分析的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。一、goroutine定义给函数前加上go即可不需要在定义是区分是否是异步函数调度器在合适的点进行切换,这个点是有很多
2023-06-20

java并发编程之同步器代码示例

同步器是一些使线程能够等待另一个线程的对象,允许它们协调动作。最常用的同步器是CountDownLatch和Semaphore,不常用的是Barrier和Exchanger队列同步器AbstractQueuedSynchronizer是用来
2023-05-30

Spring源码解析之编程式事务的示例分析

这篇文章主要为大家展示了“Spring源码解析之编程式事务的示例分析”,内容简而易懂,条理清晰,希望能够帮助大家解决疑惑,下面让小编带领大家一起研究并学习一下“Spring源码解析之编程式事务的示例分析”这篇文章吧。一、前言在Spring中
2023-06-15

Java并发编程之线程状态实例分析

今天小编给大家分享一下Java并发编程之线程状态实例分析的相关知识点,内容详细,逻辑清晰,相信大部分人都还太了解这方面的知识,所以分享这篇文章给大家参考一下,希望大家阅读完这篇文章后有所收获,下面我们一起来了解一下吧。线程状态概述线程由生到
2023-06-30

Java源码解析之接口Collection的示例分析

小编给大家分享一下Java源码解析之接口Collection的示例分析,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!一、图示二、方法定义我们先想一想,公司如果要我
2023-06-15

Java之网络编程的示例分析

小编给大家分享一下Java之网络编程的示例分析,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!Java基础之网络编程基本概念IP:每个电脑都有一个IP地址,在局域网
2023-06-20

java并发编程工具类JUC之LinkedBlockingQueue链表队列的示例分析

小编给大家分享一下java并发编程工具类JUC之LinkedBlockingQueue链表队列的示例分析,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!java.u
2023-06-15

Java源码ConcurrentHashMap的示例分析

小编给大家分享一下Java源码ConcurrentHashMap的示例分析,希望大家阅读完这篇文章之后都有所收获,下面让我们一起去探讨吧!一、记录形式打算直接把过程写在源码中,会按序进行注释,查阅的时候可以按序号只看注释部分二、Concur
2023-06-15

编程热搜

  • Python 学习之路 - Python
    一、安装Python34Windows在Python官网(https://www.python.org/downloads/)下载安装包并安装。Python的默认安装路径是:C:\Python34配置环境变量:【右键计算机】--》【属性】-
    Python 学习之路 - Python
  • chatgpt的中文全称是什么
    chatgpt的中文全称是生成型预训练变换模型。ChatGPT是什么ChatGPT是美国人工智能研究实验室OpenAI开发的一种全新聊天机器人模型,它能够通过学习和理解人类的语言来进行对话,还能根据聊天的上下文进行互动,并协助人类完成一系列
    chatgpt的中文全称是什么
  • C/C++中extern函数使用详解
  • C/C++可变参数的使用
    可变参数的使用方法远远不止以下几种,不过在C,C++中使用可变参数时要小心,在使用printf()等函数时传入的参数个数一定不能比前面的格式化字符串中的’%’符号个数少,否则会产生访问越界,运气不好的话还会导致程序崩溃
    C/C++可变参数的使用
  • css样式文件该放在哪里
  • php中数组下标必须是连续的吗
  • Python 3 教程
    Python 3 教程 Python 的 3.0 版本,常被称为 Python 3000,或简称 Py3k。相对于 Python 的早期版本,这是一个较大的升级。为了不带入过多的累赘,Python 3.0 在设计的时候没有考虑向下兼容。 Python
    Python 3 教程
  • Python pip包管理
    一、前言    在Python中, 安装第三方模块是通过 setuptools 这个工具完成的。 Python有两个封装了 setuptools的包管理工具: easy_install  和  pip , 目前官方推荐使用 pip。    
    Python pip包管理
  • ubuntu如何重新编译内核
  • 改善Java代码之慎用java动态编译

目录