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

上篇。在写完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)状态只可能有一个线程,可能场景如下:

Read More

raspberry pi 3 b+ cross compile on macos mojave

本文记录了如何在mojave上构建raspberry pi 3 b+的交叉编译环境。交叉编译的原因最主要的还是速度,当然还有目标平台没有直接的编译工具链等。在构建交叉编译环境之前,最好确认目标平台的相关信息,能直接确认目标平台的工具链是最好的,因为从CPU判断可能并不准确。

比如raspebrry pi 3 b+,自带gcc,相关信息如下

注意其中target为arm-linux-gnueabihf。假如从raspberry pi 3 b+的CPU(Broadcom BCM2837 64bit CPU)判断的话,armv8,aarch64貌似都可以用,但实际用aarch64架构编译出来的程序无法在raspberry pi,准确来说是安装了raspbian上的raspberry pi上执行,这点请注意(假如想在raspberry pi 3 b+上执行aarch64架构的程序的话,个人觉得可能要换raspbian以外的系统,或者修改内核编译选项,这块等自己有空尝试并成功了再发出来)。

Read More

Compile and install valgrind on macOS Mojave (10.14.2)

本文是给想在Mojave上编译安装valgrind的人一个参考。

个人因为《Hands on concurrency with Rust》这本书的原因,需要安装valgrind。但是现在(2019/2/9)稳定版本的valgrind尚未支持Mojave,即不能通过Homebrew安装。valgrind的bug tracker里有这个问题的追踪, 但是看状态估计离正式发布还需要时间(开源项目常有的事情,缺少资源,哎)。对话中给了一个github上的commit,看起来可以使用。

下载对应的repository,checkout到修改版的branch上

按照valgrind自身网站上的说明,接下来是常规的compile install。

如果你按照顺序执行的话,在make可能会碰到如下两个问题,所以在执行之前,建议先看一下可能碰到的问题

1. No rule to make target `/usr/include/mach/mach_vm.defs’

简单来说,就是没有找到定义文件。按照stackoverflow上一个问题的说法,你可以通过

解决,但是答案针对的不是Mojave,所以Mojave除了通过上述命令安装XCode之外,还需要解答中另外一个解决方案,即修改coregrind/Makefile(此文件在./configure之后生成)中mach_vm.defs的路径,具体如下

也就是在原本 /usr/include/mach/mach_vm.defs 等文件前加上 /Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX10.14.sdk 前缀,你可以 ls 一下看一下文件是否存在。

2. vgpreload_core_x86_darwin_so-vg_preloaded.o ld: symbol(s) not found for architecture i386

这个问题比较隐蔽,google搜不出来什么东西。直接看错误信息的话,大概知道MacOS下无法链接i386的程序,因为比较新的MacOS基本上只有x86_64。直接的解决方法是不让valgrind去编译i386架构的程序。

如果你留意了 ./configure 最后的输出的话,可以看到Secondary build arch

假如Secondary build arch不像上面那样为空的话,比如是i386,那么make时会出现以上问题。

在 configure 文件中,valgrind的注释提到在MacOS下会同时编译i386和x86_64,这是问题的根本原因,或者说valgrind在Mojave下编译的坑。幸好 configure 提供了只编译64位的选项,不需要修改 configure 文件。

总结一下,你要做的是

小结

老实说很后悔升级到了Mojave,MacBook的睡死,突然mic不能使用等问题,现在又来一个valgrind……

不管怎么说,希望本文对你有所帮助。

 

 

如何理解 C++11 原子变量(Atomic)的 Memory Order

最近几天在学习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。

Read More

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

XnnYygn的2018年小结

如果没记错的话,这次是自己第一次写年度小结。为什么突然想写小结?可能主要是因为自己觉得在2018年里技术有比较大的进步吧。

2018年上半年抱着自己实现一个MQ的想法,空闲时间收集相关资料,学习Netty,每天看看《开发者头条》。

2018年中期,Netty学得差不多了,决定在实现MQ之前,找一个东西练手,结果把Raft实现了一遍。虽然不够完美,但是第一次接触了分布式领域的论文。之后又阅读了GOSSIP相关论文,基于自己的理解,实现了基于GOSSIP的集群管理(动态加入和退出)。

如果对上述代码有兴趣,欢迎到github上阅读和关注。

https://github.com/xnnyygn/xraft

https://github.com/xnnyygn/xgossip

代码开发中,觉得自己的并发编程技术有所欠缺,在寻找并发编程资料时,发现了《the art of multiprocessor programming》。这本书绝对是我从学编程开始找到的最好的一本书。开始看了之后就一发不可收拾,花了几个月看完第一遍之后,现在看第二遍中。最近每周一篇的Java并发库的分析,之后有机会的话准备写一本《如何自己写并发库》相关的书。

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