`
student_lp
  • 浏览: 436532 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

java高并发编程:5--ConcurrentLinkedQueue的实现原理分析

阅读更多

1. 引言

    在并发编程中我们有时候需要使用线程安全的队列。如果我们要实现一个线程安全的队列有两种实现方式:一种是使用阻塞算法,另一种是使用非阻塞算法。使用阻塞算法的队列可以用一个锁(入队和出队用同一把锁)或两个锁(入队和出队用不同的锁)等方式来实现,而非阻塞的实现方式则可以使用循环CAS的方式来实现,本文让我们一起来研究下Doug Lea是如何使用非阻塞的方式来实现线程安全队列ConcurrentLinkedQueue的,相信从大师身上我们能学到不少并发编程的技巧。

2. ConcurrentLinkedQueue的介绍

    ConcurrentLinkedQueue是一个基于链接节点的无界线程安全队列,它采用先进先出的规则对节点进行排序,当我们添加一个元素的时候,它会添加到队列的尾部,当我们获取一个元素时,它会返回队列头部的元素。它采用了“wait-free”算法来实现,该算法在Michael & Scott算法上进行了一些修改, Michael & Scott算法的详细信息可以参见参考资料一。

3. ConcurrentLinkedQueue的结构

    我们通过ConcurrentLinkedQueue的类图来分析一下它的结构。

 

    ConcurrentLinkedQueue由head节点和tair节点组成,每个节点(Node)由节点元素(item)和指向下一个节点的引用(next)组成,节点与节点之间就是通过这个next关联起来,从而组成一张链表结构的队列。默认情况下head节点存储的元素为空,tair节点等于head节点。

private transient volatile Node<E> tail = head;

 4. 入队列

    入队列就是将入队节点添加到队列的尾部。为了方便理解入队时队列的变化,以及head节点和tair节点的变化,每添加一个节点我就做了一个队列的快照图。


  • 第一步添加元素1。队列更新head节点的next节点为元素1节点。又因为tail节点默认情况下等于head节点,所以它们的next节点都指向元素1节点。
  • 第二步添加元素2。队列首先设置元素1节点的next节点为元素2节点,然后更新tail节点指向元素2节点。
  • 第三步添加元素3,设置tail节点的next节点为元素3节点。
  • 第四步添加元素4,设置元素3的next节点为元素4节点,然后将tail节点指向元素4节点。

    通过debug入队过程并观察head节点和tail节点的变化,发现入队主要做两件事情,第一是将入队节点设置成当前队列尾节点的下一个节点。第二是更新tail节点,如果tail节点的next节点不为空,则将入队节点设置成tail节点,如果tail节点的next节点为空,则将入队节点设置成tail的next节点,所以tail节点不总是尾节点,理解这一点对于我们研究源码会非常有帮助。

    上面的分析让我们从单线程入队的角度来理解入队过程,但是多个线程同时进行入队情况就变得更加复杂,因为可能会出现其他线程插队的情况。如果有一个线程正在入队,那么它必须先获取尾节点,然后设置尾节点的下一个节点为入队节点,但这时可能有另外一个线程插队了,那么队列的尾节点就会发生变化,这时当前线程要暂停入队操作,然后重新获取尾节点。让我们再通过源码来详细分析下它是如何使用CAS算法来入队的。

public boolean offer(E e) {
    if (e == null) throw new NullPointerException();
    //入队前,创建一个入队节点
    Node<E> n = new Node<E>(e);
    retry:
    //死循环,入队不成功反复入队。
    for (;;) {
        //创建一个指向tail节点的引用
        Node<E> t = tail;
        //p用来表示队列的尾节点,默认情况下等于tail节点。
        Node<E> p = t;
        for (int hops = 0; ; hops++) {
        //获得p节点的下一个节点。
            Node<E> next = succ(p);
        //next节点不为空,说明p不是尾节点,需要更新p后在将它指向next节点
            if (next != null) {
               //循环了两次及其以上,并且当前节点还是不等于尾节点
                if (hops > HOPS && t != tail)
                    continue retry; 
                p = next;
            } 
            //如果p是尾节点,则设置p节点的next节点为入队节点。
            else if (p.casNext(null, n)) {
              //如果tail节点有大于等于1个next节点,则将入队节点设置成tair节点,更新失败了也
没关系,因为失败了表示有其他线程成功更新了tair节点。
                if (hops >= HOPS)
                    casTail(t, n); // 更新tail节点,允许失败
                return true;  
            } 
           // p有next节点,表示p的next节点是尾节点,则重新设置p节点
            else {
                p = succ(p);
            }
        }
    }
}

   从源代码角度来看整个入队过程主要做二件事情。第一是定位出尾节点,第二是使用CAS算法能将入队节点设置成尾节点的next节点,如不成功则重试。

    第一步定位尾节点。tail节点并不总是尾节点,所以每次入队都必须先通过tail节点来找到尾节点,尾节点可能就是tail节点,也可能是tail节点的next节点。代码中循环体中的第一个if就是判断tail是否有next节点,有则表示next节点可能是尾节点。获取tail节点的next节点需要注意的是p节点等于p的next节点的情况,只有一种可能就是p节点和p的next节点都等于空,表示这个队列刚初始化,正准备添加第一次节点,所以需要返回head节点。获取p节点的next节点代码如下

final Node<E> succ(Node<E> p) {
         Node<E> next = p.getNext();
         return (p == next) ? head : next;
     }

   第二步设置入队节点为尾节点。p.casNext(null, n)方法用于将入队节点设置为当前队列尾节点的next节点,p如果是null表示p是当前队列的尾节点,如果不为null表示有其他线程更新了尾节点,则需要重新获取当前队列的尾节点。

    hops的设计意图。上面分析过对于先进先出的队列入队所要做的事情就是将入队节点设置成尾节点,doug lea写的代码和逻辑还是稍微有点复杂。那么我用以下方式来实现行不行?

public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        Node<E> n = new Node<E>(e);
        for (;;) {
            Node<E> t = tail;
            if (t.casNext(null, n) && casTail(t, n)) {
                return true;
            }
        }
    }

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

private static final int HOPS = 1;

   还有一点需要注意的是入队方法永远返回true,所以不要通过返回值判断入队是否成功。

5. 出队列

    出队列的就是从队列里返回一个节点元素,并清空该节点对元素的引用。让我们通过每个节点出队的快照来观察下head节点的变化。

    从上图可知,并不是每次出队时都更新head节点,当head节点里有元素时,直接弹出head节点里的元素,而不会更新head节点。只有当head节点里没有元素时,出队操作才会更新head节点。这种做法也是通过hops变量来减少使用CAS更新head节点的消耗,从而提高出队效率。让我们再通过源码来深入分析下出队过程。

public E poll() {
    Node<E> h = head;
   // p表示头节点,需要出队的节点
    Node<E> p = h;
    for (int hops = 0;; hops++) {
        // 获取p节点的元素
        E item = p.getItem();
        // 如果p节点的元素不为空,使用CAS设置p节点引用的元素为null,如果成功则返回p节点的元素。
        if (item != null && p.casItem(item, null)) {
            if (hops >= HOPS) {
                //将p节点下一个节点设置成head节点
                Node<E> q = p.getNext();
                updateHead(h, (q != null) ? q : p);
            }
            return item;
        }
        // 如果头节点的元素为空或头节点发生了变化,这说明头节点已经被另外一个线程修改了。那么获取p节点的下一个节点 
        Node<> next = succ(p);
        // 如果p的下一个节点也为空,说明这个队列已经空了
        if (next == null) {
          // 更新头节点。
            updateHead(h, p);
            break;
        }
        // 如果下一个元素不为空,则将头节点的下一个节点设置成头节点
        p = next;
    }
    return null;
}

   首先获取头节点的元素,然后判断头节点元素是否为空,如果为空,表示另外一个线程已经进行了一次出队操作将该节点的元素取走,如果不为空,则使用CAS的方式将头节点的引用设置成null,如果CAS成功,则直接返回头节点的元素,如果不成功,表示另外一个线程已经进行了一次出队操作更新了head节点,导致元素发生了变化,需要重新获取头节点。

 转子:http://www.infoq.com/cn/articles/ConcurrentLinkedQueue

  • 大小: 36.9 KB
  • 大小: 44.8 KB
  • 大小: 45.5 KB
分享到:
评论

相关推荐

    汪文君高并发编程实战视频资源下载.txt

     高并发编程第三阶段21讲 Exchanger工具的使用以及常见问题分析-上_.mp4  高并发编程第三阶段22讲 Exchanger工具的使用以及常见问题分析-下_.mp4  高并发编程第三阶段23讲 Semaphore工具的介绍以及借助于...

    JAVA并发编程实践JavaConcurrencyinPractice-中文-高清-带书签-完整版(Doug Lea)

    6. **并发集合**:分析了ConcurrentHashMap、CopyOnWriteArrayList、ConcurrentLinkedQueue等并发集合的实现和使用,这些集合在多线程环境下提供了高性能的并发访问。 7. **并发设计模式**:介绍了如双检锁/双重...

    高并发编程实战1,2,3阶段

    ### 高并发编程实战1,2,3阶段 #### 知识点概览 本系列教程分为三个阶段,旨在帮助开发者全面理解并掌握高并发编程技术。通过理论讲解与实战演练相结合的方式,深入剖析了多线程编程的核心原理及其在实际项目中的...

    汪文君高并发编程实战视频资源全集

     高并发编程第三阶段21讲 Exchanger工具的使用以及常见问题分析-上_.mp4  高并发编程第三阶段22讲 Exchanger工具的使用以及常见问题分析-下_.mp4  高并发编程第三阶段23讲 Semaphore工具的介绍以及借助于...

    java并发编程艺术

    5. **线程安全的数据结构**:介绍Java中线程安全的集合类,如ConcurrentHashMap、CopyOnWriteArrayList、ConcurrentLinkedQueue等,以及它们在并发编程中的应用。 6. **线程间的通信**:讲解wait()、notify()和...

    java并发编程艺术源码-ArtConcurrentBook:JAVA并发编程的艺术

    《Java并发编程艺术》是一本深入探讨Java多线程与并发编程的经典著作,它涵盖了Java并发编程的基础到高级主题,旨在帮助开发者掌握在Java平台上进行高效并发编程的技术和最佳实践。源码ArtConcurrentBook提供了书中...

    Java-jdk10-最新最全多线程编程实战指南-核心篇

    通过阅读《Java-jdk10-最新最全多线程编程实战指南-核心篇》这本书,开发者不仅可以理解Java多线程编程的基础知识,还能掌握高级并发编程技巧,从而在实际项目中实现高性能、高并发的程序设计。对于Java开发者来说,...

    java并发编程-构建块

    在Java编程领域,并发编程是不可或缺的一部分,尤其是在大型系统或高并发应用中。"java并发编程-构建块"这个主题涵盖了使程序能够同时处理多个任务的关键概念和技术。在这个主题下,我们将深入探讨Java中用于构建...

    java高并发源码-java-concurrent:Java高并发,JUC,相关源码。1、马士兵高并发视频源码(听课时练习)

    在"java-concurrent-master"这个项目中,我们可以期待看到以上各种并发特性的实际应用和源码分析,这将帮助我们深入理解Java并发编程的原理和实践技巧。通过马士兵老师的视频源码,我们可以跟随他的讲解,一步步地...

    ConcurrentLinkedQueue源码分析.rar

    在Java并发编程领域,`ConcurrentLinkedQueue`是一个非常重要的数据结构,它是线程安全的无界队列,基于链接节点实现,性能高效。本篇文章将深入探讨`ConcurrentLinkedQueue`的设计原理、内部结构以及其源码中的关键...

    java并发编程实践 张孝翔 讲义

    5. **并发工具类**:包括`ExecutorService`、`Future`、`Callable`等,它们是Java并发编程的重要组成部分。这些工具可以帮助我们更好地管理和控制线程,避免资源浪费,提高程序效率。 6. **并发模式**:书中还会...

    java面试——厦门-中软国际-Java中级.zip

    - 了解集合的并发处理:CopyOnWriteArrayList、ConcurrentLinkedQueue等。 4. **设计模式**: - 熟悉常见的设计模式,如单例、工厂、抽象工厂、建造者、适配器、装饰器、代理、观察者、状态、策略、模板方法等。 ...

    java并发编程 PDF

    《Java并发编程》这本书是Java开发者深入理解和掌握并发编程的重要参考资料。并发编程是现代多核处理器环境下提升程序性能的关键技术,对于大型系统和高并发应用的开发至关重要。Java平台提供了丰富的并发工具和机制...

    java 并发视频教程

    本教程将基于“Java并发视频教程”这一资源,详细解析Java并发编程的基础概念与核心API,帮助读者全面理解Java并发机制。 #### 一、并发与并行 - **并发**(Concurrency):指在同一时间间隔内,多个任务交替执行...

    聊聊并发(6)ConcurrentLinkedQueue的

    【标题】:“聊聊并发(6)ConcurrentLinkedQueue的实现原理分析” 【正文】: 并发编程是现代软件开发中的重要组成部分,特别是在多核处理器和分布式系统中,有效地处理并发能够显著提升系统的性能和响应能力。...

    Java Concurrency in Practice中文版

    6. **第六章:并发集合** - 讨论java.util.concurrent包下的并发安全集合,如ConcurrentHashMap、CopyOnWriteArrayList和ConcurrentLinkedQueue,以及它们在高并发环境下的优势。 7. **第七章:线程池** - 解析...

    java精通程度应该会什么

    - `ConcurrentHashMap`: 高并发场景下的高效实现,采用了锁分段技术提高并发性。 - **Set**: 包括`HashSet`等,用于存储无序且不重复的元素。 - **其他集合**: 如`CopyOnWriteArrayList`(写时复制列表)、`Queue...

    java 高级理论-10

    2. **集合框架**:深入理解List、Set、Queue等接口以及它们的实现类,如ArrayList、LinkedList、HashSet、HashMap等,特别是对于并发安全的集合(ConcurrentHashMap、ConcurrentLinkedQueue等)的理解和使用。...

    C++和JAVA面试题

    - **并发编程**:线程池(ExecutorService),原子类(AtomicInteger, AtomicReference等),并发容器(ConcurrentHashMap, ConcurrentLinkedQueue等)。 - **反射机制**:如何通过反射创建对象,调用方法,访问...

    java多线程并发实战和源码

    这些容器内部实现了线程安全的算法,能够在高并发环境下提供高效的数据访问。 此外,Java并发工具类(java.util.concurrent包)提供了许多实用的工具,如ExecutorService、Future、CountDownLatch、CyclicBarrier和...

Global site tag (gtag.js) - Google Analytics