Java并发研究 自己写ReentrantLock和ReentrantReadWriteLock(3)

本系列是基于经验设计原型,然后不断优化最终达到和AQS(AbstractQueuedSynchronizer)类似的设计。最终结果不一定和AQS完全一致,基于个人理解会有修改,可以作为理解AQS的不完全参考。

上篇。本篇主要介绍Condition即条件变量的实现,ReentrantLock中最后一块需要实现的内容。

在实现条件变量之前,考虑一下条件变量的一些特性。

  1. 条件变量依赖锁,而且是独占锁
  2. 执行await方法后释放锁,当前线程进入睡眠状态,等待满足条件后被其他线程signal/signalAll唤醒,被唤醒后会尝试重新获取锁
  3. 唤醒可以选择一个也可以全部

注意第一条特性,条件变量依赖的是独占锁,所以类似读锁这种共享锁是不支持条件变量的,ReentrantReadWriteLock中ReadLock#newCondition的实现是直接抛错。

按照第二条特性,可以得到如下的执行过程

Read More

Java并发研究 自己写ReentrantLock和ReentrantReadWriteLock(2)

接着上篇,本篇主要介绍如何添加限时tryLock方法。介绍完之后,ReentrantLock除了condition之外都会实现,而且基本和实际ReentrantLock代码接近。上篇也提到过,实际ReentrantLock依赖AQS,但是本文不会直接介绍AQS,只是AQS的一个不完全分析。

顺便提一下,“自己写ReentrantLock和ReentrantReadWriteLock”由于篇幅比较长,预计会分成3到4篇左右。

在进入限时tryLock方法的介绍之前,考虑一个问题:上篇中FairLock1和UnfairLock1是否可以复用Node?

为什么要问这个问题?因为C++代码比较关注对象的生命周期。使用C++实现锁的话必须关注何时可以回收Node的内存。如果你了解CLHLock的话,可以知道CLHLock是可以复用Node的,最多是N个(线程)+1个(哨兵)Node,理论上不需要回收。所以和CLHLock基本一致的FairLock1,同样可以用类似CLHLock的方式,即复用前序节点为自己的当前节点(CLHLock是复用前序节点的,至于为什么可以参阅CLHLock的介绍)。UnfairLock1中由于可能是非公平模式,不知道前序节点是谁,也就无法简单复用了。

Read More

Java并发研究 自己写ReentrantLock和ReentrantReadWriteLock(1)

最近个人在研究如何实现Transaction Memory,这其实也是受《the art of multiprocessor programming》最后一章的影响。作为研究的一部分,个人需要一个类似ReadWriteLock语义的同步器,于是分析了一下现有ReentrantLock和ReentrantReadWriteLock。在分析之前我其实知道ReentrantLock和ReentrantReadWriteLock都是基于AbstractQueuedSynchronizer,所以本篇也可以作为AbstractQueuedSynchronizer的不完全分析。

首先从ReentrantLock开始分析。最简单的不公平模式,无等待(SPIN,PARK)的锁。

Read More

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的代码之前,了解以下内容

  1. HM Linked List
  2. HM Linked List基于marker节点的优化方式
  3. 普通的(非并发环境下的)SkipList

Read More

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.

示例代码dualstack和dualqueue可以看这里。

http://www.cs.rochester.edu/research/synchronization/pseudocode/duals.html

Read More

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算法放在一边,以一种新算法的角度来分析和阅读。

Read More

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

大约两个月没有写博客了,原因是最近自己一直在看《The Art of Multiprocessor Programming》。这本书从理论到实践介绍了多核编程,给出的数据结构和算法都有相应的论文。如果你想好好学习多核编程,而不是某种语言的并发机制介绍的话,非常推荐这本书。同时这本书里介绍的算法,在Java的并发库里面都能找到影子。作为继续深入学习的一部分,个人打算逐个分析典型的并发类,并且基于个人理解给出一些改进或者变化。

Java的并发库里面,从版本1.5(Java 5)开始引入了接口Future和实现类FutureTask。与其他Synchronizer(同步类)不同,FutureTask并没有依赖AQS,所以是相对简单的一个并发类。FutureTask包含执行Task和同步结果两块主要功能。这里主要分析如何同步结果。

注意,本文并不会逐行代码分析FutureTask。为了学习如何设计并发类,本文以个人理解的原型类开始,逐渐修改成为接近实际FutureTask甚至超过FutureTask的代码。

Read More

自适应分布式速率限制(distributed rate limiter)

本文是针对xratelimiter的算法说明。

https://github.com/xnnyygn/xratelimiter

首先对rate limiter做一下简单介绍。

rate limiter主要用在限流,比如希望网站的访问在一定的量的时候,对于API有调用量限制,作为云服务商限制访问用户网站的流量等等。

常见的rate limiter算法有token bucket。具体算法这里不作展开。一般实现中,会有一个记录最后添加了token的时间戳,还有一个记录当前token数的变量。由于有两个变量,在使用redis实现集中式的token bucket时无法原子修改。

Read More

基于GOSSIP的集群成员管理-成员的加入和退出

本文是对于以下项目的算法说明。

https://github.com/xnnyygn/xgossip

首先简单介绍一下GOSSIP。

GOSSIP据说最早见于论文《Epidemic Algorithms for Replicated  Database Maintenance》,对于GOSSIP有兴趣的人建议阅读一下此论文。

GOSSIP算法如论文标题是一种epidemic algorithm,可以理解为传染病的传播。有三个人A,B,C。A是传染源,当A传染给B,B传染给C之后,所有人都被传染了。在分布式系统中,可以把传染病类比为更新,当所有参与的节点都获取到了更新之后,集群达到最终一致状态。从这个角度来说,GOSSIP是一种弱一致性,或者说最终一致性算法。

Read More