并发编程牛刀小试:SeqLock

Sequential lock,简称seq lock,是一种有点特殊的“读写锁”,Linux内核从2.6版本开始引入,是一种非常简单轻量保护共享数据读写的方法。

基本原理


Sequential lock的原理非常简单,其核心就是通过维护一个序号(sequence)来避免读者(Reader)读到错误的数据,而写者(Writer)在加锁和解锁的过程中递增序号,多个写者之间需要借助于额外的互斥锁来保证互斥关系。

具体来讲,序号初始化为0,读者和写者的流程如下:

  • 写者开始修改临界区中的数据时,首先获取写者间互斥锁,然后递增序号(奇数),开始修改数据,修改数据完成后会再次递增序号(偶数),然后释放写者间互斥锁。
  • 对读者来说,在修改数据的过程中读者可能会读到错误的数据,但读者在读数据前后会分别获取一次序号,对两次获取的序号进行比较,如果不相同则说明在读取过程中有写者进入了临界区,需要重试;如果序号相同但是是奇数,说明读者开始读取到结束读取的这段时间写者占有了临界区,同样也需要重试。
SeqLock时序示意

SeqLock时序示意

看个例子就明白了,如上图所示,是不是非常简洁明了。

继续阅读:

Hazard Pointer

上一篇文章中实现了一个lock-free的队列,但是有一个问题:内存无法被安全的回收。那么,这次就来把这缺失的一环补上:hazard pointer,一种lock-free对象的内存回收机制。

hazard pointer

hazard pointer

PS:因为hazard pointer完整代码略有些长,不适合贴在文章内部,完整代码可以在这里找到。

继续阅读:

用户态同步之自旋锁

最近花了一些时间研究如何在用户态实现自旋锁,这里简单的总结一下。本文的所有代码以及配套的测试用代码都可以在我的github上找到。

问题在哪


首先明确问题,我们需要一种用户态实现的线程同步机制,正确性当然是最重要的。本文的目的是实现正确的自旋锁(自旋锁比较简单轻量,但了解了原理后实现互斥锁并不困难,自行维护等待关系并通过 futex 对线程执行挂起、唤醒操作就可以了)。

概念上这个问题很简单啊,是不是我们只要用一个线程共享的变量做互斥,然后在线程获得和释放锁时修改这个变量就行了?比如像下面这样:

然而事情没这么简单,因为对这个变量的操作不是原子的,所以会导致这个锁无法正确的运行(即使在单核环境也如此),因此我们需要利用硬件提供的原子操作来实现锁(FYI. 一种不需要原子操作的锁实现方法见前文中提到过的Dekker算法,非常漂亮,但通用性不足)。

除此之外,另一个问题是多核争用的性能问题,这一点我会在后文中提到。

另外由于在用户态实现锁对硬件体系结构提供的一致性保证非常相关,所以必须注明,本文中所有实现针对于x86体系结构也就是acquire-release语义TSO内存模型),不具备可移植性

继续阅读:

探索C++虚函数在g++中的实现

本文是我在追查一个诡异core问题的过程中收获的一点心得,把公司项目相关的背景和特定条件去掉后,仅取其中通用的C++虚函数实现部分知识记录于此。

在开始之前,原谅我先借用一张图黑一下C++:

“无敌”的C++

“无敌”的C++

如果你也在写C++,请一定小心…至少,你要先有所了解:当你在写虚函数的时候,g++在写什么?

继续阅读:

C++中实现多线程安全的单体类

最近看了一些算是比较高大上的C++代码,被内力震伤了,赶紧记录下来!最最基础的就是这个:单体类。单体是面向对象中一种非常流行的设计模式,C++的实现百度一下可以找到一坨,但这个稍稍有点特殊——多线程安全。

普通版本的单体类实现如下:

乍一看似乎完全没有问题,不过如果这个单体类运行在多线程环境中,将会有可能创建多个实例。临界区出现在Instance()函数中创建单体对象的部分,即静态变量m_Instance!当访问该变量判断单体是否已被创建时,如果不进行临界区保护,很有可能会造成多个线程同时进入临界区,创建了多个Singleton对象,Boom…

继续阅读: