一.序言
现在并发操作中都要求高效,都在想怎么去掉直接加锁带来的线程切换的开销,这里分享自己对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 的应用,我感觉是它设计上 对几个变量的应用,保证的 前后的推进 以及判断,这个是非常厉害,不得不服啊
相关推荐
#### 四、ConcurrentLinkedQueue源码分析 ##### 类的继承关系 ```java public class ConcurrentLinkedQueue<E> extends AbstractQueue implements Queue, java.io.Serializable {} ``` `ConcurrentLinkedQueue`...
本篇文章将深入探讨`ConcurrentLinkedQueue`的设计原理、内部结构以及其源码中的关键实现细节。 首先,我们要明白`ConcurrentLinkedQueue`是Java并发包`java.util.concurrent`中的一个类,它实现了`Queue`接口,...
bitset源码Java源码分析 基础集合列表 ArrayList (done) Vector (done) LinkedList (done) Stack (done) ReferenceQueue (done) ArrayDeque (done) Set HashSet (done) TreeSet (done) LinkedHashSet (done) BitSet ...
在深入学习 Java 并发编程时,还需要关注线程安全、锁机制(如 synchronized 关键字、ReentrantLock 等)、并发容器(如 ConcurrentHashMap、ConcurrentLinkedQueue 等)、原子变量(AtomicInteger、AtomicReference...
这个"Java队列源码-article-building-queue"项目似乎包含了一篇文章的源代码,该文章探讨了如何在C++和Java之间创建高效的队列实现。在本文中,我们将深入探讨Java中的队列数据结构,以及可能涉及的跨语言接口设计。...
在"java-concurrent-master"这个项目中,我们可以期待看到以上各种并发特性的实际应用和源码分析,这将帮助我们深入理解Java并发编程的原理和实践技巧。通过马士兵老师的视频源码,我们可以跟随他的讲解,一步步地...
Java 数据结构源码分析 在Java编程中,理解数据结构是提升编程能力的关键步骤,它涉及到如何有效地存储和组织数据,以优化算法的性能。Java提供了丰富的内置数据结构,如数组、链表、栈、队列、集合、映射等,这些...
4. **源码分析** - 通常,实现线程安全队列的源码会包含如下关键部分: - **插入操作**:确保在队尾添加元素时不会与其他线程的读写操作冲突。 - **移除操作**:在队头移除元素时,确保元素只被一个线程处理一次...
Java多线程并发实战与源码分析是Java开发中至关重要的一部分,它涉及到程序性能优化、系统资源高效利用以及复杂逻辑的正确同步。本书主要聚焦于Java多线程的基础理论和实际应用,虽然书中实例和源码相对较少,但仍然...
- 分析`ArtConcurrentBook`源码中关于并发集合的实现,可以深入了解`ConcurrentHashMap`的分段锁策略,`CopyOnWriteArrayList`的写时复制策略等。 6. **线程池** - `ExecutorService`是线程池的接口,`...
源码分析是学习并发编程的宝贵资源,因为它们展示了实际应用中的最佳实践和常见问题的解决方案。在JCPCMF项目中,你可以找到如何使用并发工具类实现线程间的协调,如何优雅地处理中断,如何利用Future和Callable接口...
#### 六、JDK源码分析 深入理解JDK源码可以帮助开发者更好地理解Java语言的底层实现。 - **重要源码分析**: - List、Map、Set等集合类的实现细节。 - 多线程相关的类如`Thread`、`Lock`等。 - I/O相关的类如`...
8. **并发更新集合**:Java 8提供了新的并发集合类,如`ConcurrentHashMap`, `ConcurrentLinkedQueue`,它们在多线程环境下提供了高效且线程安全的更新操作。 9. **Parallel Collectors**:在Java 8中,`Collectors...
7. 并发集合基础知识:ConcurrentHashMap实战与原理、源码详解、ConcurrentLinkedQueue实战与原理、源码详解、ConcurrentSkipListMap实战与原理、源码详解、CopyOnWriteArrayList实战与原理、源码详解等。...
- 源码分析:通过阅读Java标准库中数据结构和算法的源码,可以深入理解其实现原理和优化技巧。 - 工具辅助:使用IDE(如Eclipse、IntelliJ IDEA)的调试功能,可以帮助分析和验证算法的执行过程。 6. **实践应用*...
本文将深入探讨`ConcurrentLinkedQueue`、`ArrayBlockingQueue`以及`LinkedBlockingQueue`这三种实现,并分析它们的设计原理与应用场景。 首先,我们来看`ConcurrentLinkedQueue`。它是基于非阻塞算法(CAS,...
在本文中,我们将关注源码分析和相关工具的使用,以帮助开发者更好地理解和应用这些技术。 首先,Java为并行计算提供了丰富的支持,其中最著名的就是Java多线程(Multithreading)。通过创建和管理线程,Java程序员...
高并发编程第三阶段11讲 AtomicXXXFieldUpdater源码分析及使用场景分析.mp4 高并发编程第三阶段12讲 sun.misc.Unsafe介绍以及几种Counter方案性能对比.mp4 高并发编程第三阶段13讲 一个JNI程序的编写,通过...
高并发编程第三阶段11讲 AtomicXXXFieldUpdater源码分析及使用场景分析.mp4 高并发编程第三阶段12讲 sun.misc.Unsafe介绍以及几种Counter方案性能对比.mp4 高并发编程第三阶段13讲 一个JNI程序的编写,通过...
9. **源码分析**:通过查看和学习提供的源码,开发者可以深入理解上述知识点的实际应用,提高自己的编程技能,包括设计模式、优化技巧以及Java语言的最佳实践。 10. **可扩展性与模块化**:优秀的聊天程序应具备...