Category: Multiprocessor

接上篇。在写完ReentrantLock之后，其实可以基于ReentrantLock写一个ReadWriteLock，《the art of multiprocessor programming》第八章有介绍。但是，本着不完全AQS（AbstractQueuedSynchronizer）介绍的系列主题，这里从零开始重新写一个ReentrantReadWriteLock。

按照ReadWriteLock的定义，任何时候都满足

1. 没有线程持有锁
2. 有1~n个线程持有共享锁（Read）
3. 有1个线程持有独占锁（Write）

中的一个。

其次公平的ReadWriteLock要求新来的Read或者Write线程必须在队列中等待，非公平的ReadWriteLock允许新来的Read或者Write比队列中等待的线程先获取锁。关于非公平锁这里多说一句，理论上的非公平锁类似一群人哄抢的现象，但是实现多半是只允许新来和线程队列最前面的线程抢占锁。ReadWriteLock也是一样。如果你想要完全非公平的锁的话，可能AQS和这里的实现不满足你的需求。

为了实现ReadWriteLock的定义，你需要分别记录读写状态。考虑到独占（Write）状态只可能有一个线程，可能场景如下：

Continue reading “Java并发研究 自己写ReentrantLock和ReentrantReadWriteLock（4）”

最近几天在学习Rust，把Rust官网附带的The Rust Programming Language看完，开始尝试用Rust实现自己学习过的并发数据结构。首先碰到的问题是，如何理解Rust所基于的LLVM的atomics模型。因为LLVM的原子变量模型基本可以对应于C++11开始的原子变量，除了没有consume memory order。所以任务就变成了如何理解C++11的原子变量。

C++原子变量本身并不难理解，但是理解memory order很难。网上找了很多资料，都没有很清晰得解释memory order到底是什么。今天重新看了《C++ Concurrency in Action》关于memory order的部分，对照着 std::memory_order 的介绍，突然明白了这是怎么一回事。

答案是memory order就只是一个order。

Continue reading “如何理解 C++11 原子变量（Atomic）的 Memory Order”

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

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

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

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

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

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

Continue reading “Java并发研究 自己写ReentrantLock和ReentrantReadWriteLock（3）”

接着上篇，本篇主要介绍如何添加限时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中由于可能是非公平模式，不知道前序节点是谁，也就无法简单复用了。

Continue reading “Java并发研究 自己写ReentrantLock和ReentrantReadWriteLock（2）”

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

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

Continue reading “Java并发研究 自己写ReentrantLock和ReentrantReadWriteLock（1）”

本文是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

Continue reading “Java并发研究 ConcurrentSkipListMap与HM Linked List”

在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

Continue reading “Java并发研究 Exchanger以及背后的dual data structure”

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

Continue reading “Java并发学习 ConcurrentLinkedQueue以及被魔改的M&S算法”