`
greemranqq
  • 浏览: 975420 次
  • 性别: Icon_minigender_1
  • 来自: 重庆
社区版块
存档分类
最新评论

源码分析-ConcurrentLinkedQueue

阅读更多

一.序言

     现在并发操作中都要求高效,都在想怎么去掉直接加锁带来的线程切换的开销,这里分享自己对concurrentLinkedQueue  的部分代码的理解,看看他无锁的原因,了解大神的设计思路。

关于 它的工作流程 参考JDK1.6 :http://ifeve.com/concurrentlinkedqueue/ 

本文分析基于JDK 1.7.0_79

 

二.源码分析

    1.介绍:concurrentlinkedqueue 设计有head  和 tail 两个节点,以及节点类 Node,主要看Node 部分

      

  

 private static class Node<E> {
        // Node 里面包含了 item 节点值  以及 下一个节点 next
        // item 和 next 都是valatile  可见性保证了
        volatile E item;
        volatile Node<E> next;

        private static final sun.misc.Unsafe UNSAFE;
        // 并且初始化的时候 就会获得item 和 next 的偏移量
        // 这为后面的cas 做了准备,如何使用继续看下面
        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);
            }
        }
    }

}

    

 

   2.从常规的 offer 方法进入,因为并发的主要也是offer 和 remove 上的竞争。

     

public boolean offer(E e) {
        checkNotNull(e);// 检查,为空直接异常
        // 创建新节点,并将e 作为节点的item
        final Node<E> newNode = new Node<E>(e);
        // 这里操作比较多,将尾节点tail 赋给变量 t,p
        for (Node<E> t = tail, p = t;;) {
            // 并获取q 也就是 tail 的下一个节点
            Node<E> q = p.next;
            // 如果下一个节点是null,说明tail 是处于尾节点上
            if (q == null) {
                // 然后用cas 将下一个节点设置成为新节点
                // 这里用cas 操作,如果多线程的情况,总会有一个先执行成功,失败的线程继续执行循环。
                // 关于casNext 的分析,跳转 1.1
                // <A> 
                if (p.casNext(null, newNode)) {
                    // 如果p.casNext有个线程成功了,p=newNode 
                    // 比较 t (tail) 是不是 最后一个节点
                    if (p != t) 
                        // 如果不等,就利用cas将,尾节点移到最后
                        // 如果失败了,那么说明有其他线程已经把tail移动过,也是OK的
                        <B>
                        casTail(t, newNode);  
                    return true;
                }
                // 如果<A>失败了,说明肯定有个线程成功了,
                // 这时候失败的线程,又会执行for 循环,再次设值,直到成功。
            }
            else if (p == q) 
                // 有可能刚好插入一个,然后P 就被删除了,那么 p==q
                // 这时候在头结点需要从新定位。
                p = (t != (t = tail)) ? t : head;
            else
                // 这里是为了当P不是尾节点的时候,将P 移到尾节点,方便下一次插入
                // 也就是一直保持向前推进
                p = (p != t && t != (t = tail)) ? t : q;
        }
    }

  

 

   1.1 casNext 分析

    

// 对应上面的 Node<E> q = p.next;p.casNext(null,newNode)
// 他是一个Node 内的方法,
boolean casNext(Node<E> cmp, Node<E> val) {
            // 可以看到,它是用p.next (null) 未偏移量,设置新值的
            // cas 是可以根据内存中的偏移量 改变值,详细这里不解释
            return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val);
}
// 既然是可以并发执行,那么当多个线程同一时间执行到这里的时候,必然只有1个 成功,后面的都失// 败。关于成功和失败的处理 继续回到上面 1 

   

    3.poll 方法解释

    

public E poll() {
        // 设置起始点
        restartFromHead:
        for (;;) {
            for (Node<E> h = head, p = h, q;;) {
                E item = p.item;
                // 利用cas 将第一个节点,设置未null
                if (item != null && p.casItem(item, null)) {
                    // 和上面类似,p的next被删了,
                    // 然后然后判断一下,目的为了保证head的next不为空
                    if (p != h) // hop two nodes at a time
                        updateHead(h, ((q = p.next) != null) ? q : p);
                    return item;
                }
                else if ((q = p.next) == null) {
                    // 有可能已经被另外线程先删除了下一个节点
                    // 那么需要先设定head 的位置,并返回null
                    updateHead(h, p);
                    return null;
                }
                else if (p == q)
                    // 这个一般是删完了(有点模糊)
                    continue restartFromHead;
                else
                    // 和offer 类似,这历使用保证下一个节点有值,才能删除
                    p = q;
            }
        }
    }

 

 

   4.remove 方法

    

public boolean remove(Object o) {
        if (o == null) return false;
        Node<E> pred = null;
        // 这里是从head 开始的,中间还涉及到head 的判断等从操作
        // 跟一般for 循环类似,要遍历的- -,这样的操作o 很靠后的时候,会慢- -!
        // - -不太喜欢这方法,了解作用
        for (Node<E> p = first(); p != null; p = succ(p)) {
            E item = p.item;
            if (item != null &&
                    o.equals(item) &&
                    p.casItem(item, null)) {
                Node<E> next = succ(p);
                if (pred != null && next != null)
                    pred.casNext(p, next);
                return true;
            }
            pred = p;
        }
        return false;
    }

 

   5.size 分析

    

public int size() {
        int count = 0;
        // 很纠结的是,这里依然用循环获取,判断节点是否有值。然后累加
        // 比较伤,可能作者是考虑offer poll 等操作开始计算,难以控制,用这种原始的方法
        // 比较伤- -,做为了解
        for (Node<E> p = first(); p != null; p = succ(p))
            if (p.item != null){
                // Collection.size() spec says to max out
                if (++count == Integer.MAX_VALUE)
                    break;
            }
        return count;
    }

 

   

   6.contains 方法

     

// 这个方法 也是用线性 遍历 比较的,也不多说了  
public boolean contains(Object o) {
        if (o == null) return false;
        for (Node<E> p = first(); p != null; p = succ(p)) {
            E item = p.item;
            if (item != null && o.equals(item))
                return true;
        }
        return false;
    }

 

三.小结

    1. 这个东东,方法很多,就没一一分析了,主要是了解他的 构成和主要的代码逻辑,当然我没吃透他- -,毕竟写不出来,或者很好的该进,有问题还请指出啦,谢谢。

   2.关于这个东东的应用,可能更倾向于offer 和poll 的高并发场景,而且你会发现每次都要创建node,cas 在竞争很激烈的情况,CPU会拉高,我觉得吧 可以采用,JDK1.8 Long 原子类增加的方法,多几个cell 减少cas 的问题。

   3.像size,remove 等方法,这个我是比建议大量使用的,毕竟每个类的特点,不能照顾全部的优势,用就要用她的优势吧,其他地方的话,可以适当改写,当然~。~还是等 完全掌握了才行吧~。~

   4.这个类的精华并不是cas 的应用,我感觉是它设计上 对几个变量的应用,保证的 前后的推进 以及判断,这个是非常厉害,不得不服啊

       

 

0
0
分享到:
评论
1 楼 谁说长得帅就不爷们 2016-08-22  
什么情况下会有 p!=t ?

相关推荐

    Java 多线程与并发(15-26)-JUC集合- ConcurrentLinkedQueue详解.pdf

    #### 四、ConcurrentLinkedQueue源码分析 ##### 类的继承关系 ```java public class ConcurrentLinkedQueue&lt;E&gt; extends AbstractQueue implements Queue, java.io.Serializable {} ``` `ConcurrentLinkedQueue`...

    ConcurrentLinkedQueue源码分析.rar

    本篇文章将深入探讨`ConcurrentLinkedQueue`的设计原理、内部结构以及其源码中的关键实现细节。 首先,我们要明白`ConcurrentLinkedQueue`是Java并发包`java.util.concurrent`中的一个类,它实现了`Queue`接口,...

    javabitset源码-JerrySoundCode:杰瑞声码

    bitset源码Java源码分析 基础集合列表 ArrayList (done) Vector (done) LinkedList (done) Stack (done) ReferenceQueue (done) ArrayDeque (done) Set HashSet (done) TreeSet (done) LinkedHashSet (done) BitSet ...

    并发编程、juc工具包源码分析笔记

    在深入学习 Java 并发编程时,还需要关注线程安全、锁机制(如 synchronized 关键字、ReentrantLock 等)、并发容器(如 ConcurrentHashMap、ConcurrentLinkedQueue 等)、原子变量(AtomicInteger、AtomicReference...

    Java队列源码-article-building-queue:文章“在C++和Java之间建立快速队列”的源代码

    这个"Java队列源码-article-building-queue"项目似乎包含了一篇文章的源代码,该文章探讨了如何在C++和Java之间创建高效的队列实现。在本文中,我们将深入探讨Java中的队列数据结构,以及可能涉及的跨语言接口设计。...

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

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

    java数据结构源码-java-datastructures:按源版本划分的Java数据结构实现细节

    Java 数据结构源码分析 在Java编程中,理解数据结构是提升编程能力的关键步骤,它涉及到如何有效地存储和组织数据,以优化算法的性能。Java提供了丰富的内置数据结构,如数组、链表、栈、队列、集合、映射等,这些...

    java队列源码

    4. **源码分析** - 通常,实现线程安全队列的源码会包含如下关键部分: - **插入操作**:确保在队尾添加元素时不会与其他线程的读写操作冲突。 - **移除操作**:在队头移除元素时,确保元素只被一个线程处理一次...

    java多线程并发实战和源码

    Java多线程并发实战与源码分析是Java开发中至关重要的一部分,它涉及到程序性能优化、系统资源高效利用以及复杂逻辑的正确同步。本书主要聚焦于Java多线程的基础理论和实际应用,虽然书中实例和源码相对较少,但仍然...

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

    - 分析`ArtConcurrentBook`源码中关于并发集合的实现,可以深入了解`ConcurrentHashMap`的分段锁策略,`CopyOnWriteArrayList`的写时复制策略等。 6. **线程池** - `ExecutorService`是线程池的接口,`...

    java并发编程源码-JCPCMF:Java并发编程核心方法和框架Maven源代码

    源码分析是学习并发编程的宝贵资源,因为它们展示了实际应用中的最佳实践和常见问题的解决方案。在JCPCMF项目中,你可以找到如何使用并发工具类实现线程间的协调,如何优雅地处理中断,如何利用Future和Callable接口...

    java精通程度应该会什么

    #### 六、JDK源码分析 深入理解JDK源码可以帮助开发者更好地理解Java语言的底层实现。 - **重要源码分析**: - List、Map、Set等集合类的实现细节。 - 多线程相关的类如`Thread`、`Lock`等。 - I/O相关的类如`...

    java8源码-java8:java8新特性

    8. **并发更新集合**:Java 8提供了新的并发集合类,如`ConcurrentHashMap`, `ConcurrentLinkedQueue`,它们在多线程环境下提供了高效且线程安全的更新操作。 9. **Parallel Collectors**:在Java 8中,`Collectors...

    JAVA后端架构师.pdf

    7. 并发集合基础知识:ConcurrentHashMap实战与原理、源码详解、ConcurrentLinkedQueue实战与原理、源码详解、ConcurrentSkipListMap实战与原理、源码详解、CopyOnWriteArrayList实战与原理、源码详解等。...

    数据结构与算法分析 Java语言描述 读书笔记

    - 源码分析:通过阅读Java标准库中数据结构和算法的源码,可以深入理解其实现原理和优化技巧。 - 工具辅助:使用IDE(如Eclipse、IntelliJ IDEA)的调试功能,可以帮助分析和验证算法的执行过程。 6. **实践应用*...

    实战Concurrent-BlockQueue

    本文将深入探讨`ConcurrentLinkedQueue`、`ArrayBlockingQueue`以及`LinkedBlockingQueue`这三种实现,并分析它们的设计原理与应用场景。 首先,我们来看`ConcurrentLinkedQueue`。它是基于非阻塞算法(CAS,...

    并行计算框架的Java实现--系列二

    在本文中,我们将关注源码分析和相关工具的使用,以帮助开发者更好地理解和应用这些技术。 首先,Java为并行计算提供了丰富的支持,其中最著名的就是Java多线程(Multithreading)。通过创建和管理线程,Java程序员...

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

     高并发编程第三阶段11讲 AtomicXXXFieldUpdater源码分析及使用场景分析.mp4  高并发编程第三阶段12讲 sun.misc.Unsafe介绍以及几种Counter方案性能对比.mp4  高并发编程第三阶段13讲 一个JNI程序的编写,通过...

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

     高并发编程第三阶段11讲 AtomicXXXFieldUpdater源码分析及使用场景分析.mp4  高并发编程第三阶段12讲 sun.misc.Unsafe介绍以及几种Counter方案性能对比.mp4  高并发编程第三阶段13讲 一个JNI程序的编写,通过...

    java聊天程序(带界面,带源码)

    9. **源码分析**:通过查看和学习提供的源码,开发者可以深入理解上述知识点的实际应用,提高自己的编程技能,包括设计模式、优化技巧以及Java语言的最佳实践。 10. **可扩展性与模块化**:优秀的聊天程序应具备...

Global site tag (gtag.js) - Google Analytics