Month: December 2018

  • Java并发研究 ConcurrentSkipListMap与HM Linked List

    本文是Java并发博客的第四篇。按照同步器和并发数据结构交替的顺序,本次是并发数据结构相关。之前介绍ConcurrentLinkedQueue的时候也提到过,并发数据结构不涉及同步器特有的问题,所以相对简单一些。分析的重点在于数据结构本身。 这次的主题是ConcurrentSkipListMap。老实说个人一开始也不知道这个类,既然有ConcurrentHashMap为什么还要有ConcurrentSkipListMap?单线程环境下的TreeMap用的次数本来就不多,并发环境下带排序的Map用得就更少了。话虽这么说,但在阅读了《the art of multiprocessor programming》第14章之后,个人发现ConcurrentSkipListMap是一个非常好的学习范本,特别是Java下HM Linked List(或者叫Harris Linked List)的实际产品代码。 如果你阅读过一些分析ConcurrentSkipListMap代码的文章的话,你可能会知道SkipList,因为名字里面就包括SkipList嘛。但实际上ConcurrentSkipListMap中维护正确性的不是SkipList,而是最底下的那一层HM Linked List。换句话说核心是在HM Linked List上,而不是帮助快速访问的SkipList。 个人建议在阅读ConcurrentSkipListMap的代码之前,了解以下内容 HM Linked List HM Linked List基于marker节点的优化方式 普通的(非并发环境下的)SkipList

  • Java并发研究 Exchanger以及背后的dual data structure

    在CLQ(ConcurrentLinkedQueue)之后,想了一下继续分析什么类比较好。 想到的是《the art of multiprocessor programming》11章中EliminationStack。当然Java的并发库里面没有这个Stack。EliminationStack是书中为了解决TreiberStack的串行特性提出的方案。TreiberStack虽然是比较简单的无锁并发数据类型,但是由于所有请求都在一个地方(top节点)上CAS,在高并发下,性能并不理想。书中认为这是TreiberStack或者说Stack本身的串行特性导致的(相对的,队列可以通过队首与队尾两个节点来分离请求),所以提出一种方案:dual stack,即在TreiberStack的基础上,push和pop两个请求配对。实际代码中先尝试常规的CAS push或者pop,如果失败,转而使用push和pop配对方式。这样做一方面把并发的请求分布到了不同的地方,另一方面提高了Stack的并发度。 为了实现push和pop请求配置,书中创建了一种Exchanger同步器,即线程A把数据给线程B,线程B把数据给线程A。(如果你奇怪pop可以给push什么数据的话,想想看pop把null给push,而push不使用pop给的数据)正好,Java的类库里也有一个叫做Exchanger的同步器,而且在注释中提到了dual data structure。所以,我想比较一下两者的实现细节。 Java类库中的Exchanger,作者除了Doug Lea还有Bill Scherer和Michael Scott,其中Michael Scott是写了dual data structure论文的两人之一(不确定Bill Scherer是不是William N. Scherer III)。这三人其实还写了SynchronousQueue,即CSP中用做channel的那种同步器,其实SynchronousQueue也是dual data structure的一种典型用法。dual data structure论文的名字是Nonblocking concurrent data structures with condition synchronization,完整的引用如下: Scherer, William N., and Michael L. Scott. “Nonblocking concurrent data structures with condition synchronization.” International Symposium on Distributed Computing. Springer, Berlin, Heidelberg, 2004.…

  • Java并发学习 ConcurrentLinkedQueue以及被魔改的M&S算法

    前面分析了FutureTask,一个同步器,下面分析一个经典的数据结构:队列。并发环境下的队列实现有很多,针对的问题和使用场景也有所不同。这里分析一个比较基础的lock free unbounded queue:ConcurrentLinkedQueue。 按照《the art of multiprocessor programming》里的定义,ConcurrentLinkedQueue属于total类型。即enqueue与dequeue不会阻塞。不阻塞就代表这个类不需要考虑同步器需要考虑的逻辑,专注于数据结构本身的实现上。 注意,本文并不会详细介绍M&S,也就是Michael & Scott算法,如果你有兴趣,请自行阅读论文 Michael, Maged M., and Michael L. Scott. Simple, fast, and practical non-blocking and blocking concurrent queue algorithms. No. TR-600. ROCHESTER UNIV NY DEPT OF COMPUTER SCIENCE, 1995. 或者《the art of multiprocessor programming》第10章。 ConcurrentLinkedQueue在注释中提到自己是M&S的变体,但是当你看了核心代码offer与poll(分别对应enqueue与dequeue)之后你不会认为这是个变体,因为改得面目全非了。M&S算法最有名的helping在offer没有直接体现,enqueue时的二次CAS被改成了一次,最让人不可思议的是tail可以在某种情况下指向head之前的节点,也就是说数据结构,甚至queue本身的不变条件都被修改了。所以如果你想分析ConcurrentLinkedQueue的话,建议把M&S算法放在一边,以一种新算法的角度来分析和阅读。

  • Java并发学习 类FutureTask分析与改进

    大约两个月没有写博客了,原因是最近自己一直在看《The Art of Multiprocessor Programming》。这本书从理论到实践介绍了多核编程,给出的数据结构和算法都有相应的论文。如果你想好好学习多核编程,而不是某种语言的并发机制介绍的话,非常推荐这本书。同时这本书里介绍的算法,在Java的并发库里面都能找到影子。作为继续深入学习的一部分,个人打算逐个分析典型的并发类,并且基于个人理解给出一些改进或者变化。 Java的并发库里面,从版本1.5(Java 5)开始引入了接口Future和实现类FutureTask。与其他Synchronizer(同步类)不同,FutureTask并没有依赖AQS,所以是相对简单的一个并发类。FutureTask包含执行Task和同步结果两块主要功能。这里主要分析如何同步结果。 注意,本文并不会逐行代码分析FutureTask。为了学习如何设计并发类,本文以个人理解的原型类开始,逐渐修改成为接近实际FutureTask甚至超过FutureTask的代码。