关于无锁原子操作的基础内容

浅谈Memory barrier

1. 内存乱序

我们常规思维下,代码的执行是按照我们撰写的顺序来执行的,类似如下的方式:

1. 读取程序计数器PC指向的指令
2. PC指向下一条指令
3. CPU执行当前指令
4. 重复上述过程直到程序执行完成

这是很原始的,类比小学课本里面的泡茶问题,我们泡茶有几个步骤:洗水壶、烧开水、洗茶壶、洗杯子、拿茶叶、泡茶;聪明的孩子一般都不会顺序执行,合理的方式是在不违背处理的先后逻辑的基础上,适当打乱操作顺序,压缩执行所需要的时间。这种改变执行顺序的方式叫做乱序执行,也叫memory reordering,内存乱序。

CPU有两类操作,计算操作与读写内存操作,例如下面简单的例子,语句1主要是一个计算操作,CPU执行的速度很快,语句2执行过程中,需要从静态内存区读取字符串常量,读取内存的过程中,CPU的等待周期远大于计算周期;因而同样一条语句,两者的执行时间显然不同。那么编译器、CPU就会根据这些特点,打乱指令的执行顺序。分别是编译期重排和运行期重排。因此效率更高的方式是先把没有数据依赖的操作提前进行(当PC指针还没变动时),等实际要执行这条指令的时候就可以快速得到结果。这就和小学时候的如何最快泡茶问题殊途同归了。但是实际上的代码指令的调整要复杂的多,很难进行预测。

// 1
a = 3*3;
// 2
b = "string";

为了降低读写内存带来的时间消耗,自然而然的引入了寄存器、多级缓存的技术,通过将使用概率更高的数据放入缓存的方式,减轻对主存的读写需求,对应的概念就是内存命中率,也就是程序的内存连续性;举个例子,程序运行时,会一次性加载一段连续的内存到缓存中,那么在读取一段连续的内存的数据的时候,极有可能会在下一个缓存位置命中我们所需的数据,避免再次读写主存,相反,如果读取数据的随机性、跨度较大,执行过程中就会频繁的读主存,刷新缓存,效率就会很低。C++的对象模型的设计就尽可能的遵守了这样的原则。

在单核单线程的情况下,这种背后暗戳戳的优化不会有任何有感的缺陷,但是在多核多线程的场景中,问题就复杂了。有两个因素:

  • 缓存未必是共享的,每个核有自己独有的缓存;
  • 每个核执行的指令都是重排后的

基于这样的情况,就会产生一个内存可见性的问题,原本单核情况下,缓存与主存具有一致性,但是多核情况下,A核对主存的修改,不会也无法去与B核中的缓存进行同步。问题的根源就在于内存同步上,多核只是引发这类问题的一个因素,类似的还有DMA区域,CPU与外设驱动都拥有DMA区域的写入权限,就会带来竞争。

Java和C语言中,有关键字Voliate,用于标记变量直读主存,避免内存的不可见性带来的影响。可见,在享受缓存带来的便利的时候,仍然需要付出两个代价:

  • 缓存未命中时,还是需要访问主存
  • 多处理器情况下,需要通过某种方式实现共享内存的一致性协议

可以想到,如果能够规范代码执行过程,将某个变量或者某段代码的所有权限定一个时间内只能有一个线程,不会被打断,那么自然不会有竞争,这样的操作就是原子性的(atomic),或者我们限定编译器与CPU对某个变量的读写与内存访问行为,把存在互相依赖关系的内存操作以特定的顺序执行,禁止CPU和编译器的乱序,内存屏障就是这样的一种干预手段,它们会给屏障两侧的内存操作强加一个偏序关系。

2. 锁机制

首先明确原子操作的定义,原子是某一种物质的非常小的组成单元,原子操作意涵类似,即粒度很细,不可分割、无法被其他执行者打断的操作。例如,读一个变量的操作可以看作是原子的,写一个变量的操作也是,但是读变量,然后再写,这样的过程就不是原子的,在写之前,内存可能已经发生了变化。

所有代码最终会被编译成CPU可以理解的指令,所以我们可以粗浅的认为,一个汇编操作指令就是最低限度的原子操作,是可以被分割的最低限度了。原子操作的缺点是只能保证一个指令,一句代码的不可打断;操作系统基于CPU的原子指令,实现锁机制,软件通过锁机制,实现代码段的同步与互斥。通过锁机制,能够保证在多核多线程环境中,在某一个时间点上,只能有一个线程进入临界区代码,从而保证临界区中操作数据的一致性。

有两个CPU的原子指令很关键:test and set和compare and swap,

test-and-set(TS)操作可以理解为如下伪代码:

boolean Test_and_Set( boolean memory[m] )
{ 
    if( memory[m] )        // lock 失败
        return True;
    else {                 // lock 成功
        memory[m] = True;
        return False;
    }
}

即,用来写入内存,并返回内存的旧值,如果多个处理器试图访问同一段内存,只会有一个处理器能唯一的执行,其余处理器只能等待。用TS实现的锁,类似如下伪代码:

function Lock(boolean *lock) {
    while (test_and_set(lock) == 1);
}

这样的锁被称为自旋锁spinlock,自旋,很形象,自己原地疯狂旋转,即使拿不到锁,也要反复主动尝试,也就是忙等待。这是比较简化的原理,实际现代CPU要复杂的多,涉及到多个核的时候,TS操作并不意味着完全互斥,有时候需要借助锁内存总线的方式来实现完全的互斥,毕竟,哪怕核有很多个,但是bus只有一个。

compare-and-swap(CAS)比较目标内存地址的值P与期望值E是否相等,如果相等,就修改P的值为N,可以用如下伪代码表示;

function cas(p : pointer to int, old : int, new : int) returns bool {
    if *p ≠ old {
        return false
    }
    *p ← new
    return true
}

CAS常用来实现同步原语类似mutex或者信号量,除此以外,也会利用其来实现一些无锁程序。CAS和TS的操作几乎可以看作是一致的,根据http://pic.dhe.ibm.com/infocenter/tpfhelp/current/index.jsp?topic=%2Fcom.ibm.ztpf-ztpfdf.doc_put.cur%2Fgtpc3%2Ftasinst.html的描述,两者区别在于,TS操作一个bit,而CAS操作一个32bit的区域。那我们完全可以当作是一样的…..后来,人们发现,CAS还会有ABA问题,然后人们又引入了DCAS等等解决方案,所以以上所述纯粹是最简单最理想的部分。爱较真的可以去维基百科上再翻翻资料。

基于TS和CAS,操作系统提供了最基本的线程同步原语,各个语言在操作系统的基础上实现种类繁多的同步机制,应用程序则进一步根据应用场景,实现粒度不同的锁。同步之道,真是一以贯之。

3. 内存屏障

终于进入正题了,这个故事太曲折。

众所周知,合理的并发可以提高多核CPU的处理能力,但是同步操作会降低执行效率,多处理器的上下文频繁切换也会降低执行效率;如果可以不用粗粒度的锁,就能实现对内存操作的同步,那么似乎就是一个终南山捷径了,内存屏障(Memory Barrier,Membar)就不得不提。

我们对内存的操作可以简化到最基本,就是读、写,也就是load和store操作,假定p是一个指针,指向某块内存,*p = 2就是一个写操作,store一个值进内存,相反的,从p中读取值就是load内存;

我们简单的组合这两种操作,得到了四种内存操作模型:

  • Load-Load: 连续的两个load操作
  • Load-Store: load之后store
  • Store-Load: store之后load内存
  • Store-Store: 连续的两个store操作

如http://g.oswego.edu/dl/jmm/cookbook.html中所阐述,实际的运行情况必然复杂的多,但是不会违背上述的四种情况,连续的内存操作必然属于其中一种。那么对应的四种membar应运而生,他们的诞生,就是为了阻止四种操作的乱序,举例,Load-Load型的membar的作用就是,阻止编译器与CPU试图打乱Load-Load的reordering操作。从这里开始有点绕人了。值得注意的是,不同的CPU之间差别很大,有的硬件平台是强内存序的,有的是弱内存序的,以防万一,程序中利用membar指定内存序,是稳妥的。

  • Load-Load

举个例子,如下代码:

if (我饿了) {
    LOADLOAD_FENCE();
    return 做饭了吗;
}

我饿了做饭了吗的值都需要从内存中load,才知道答案,并且,先要知道我饿了没,才能去判断饭有没有做的逻辑,反之是不符合我们的期望逻辑的,因此,LOADLOAD_FENCE就对两者进行了限定,防止编译器和CPU先判断饭做了没,再去问我饿不饿。

  • Store-Store

STORE-STORE类型的membar用来明确两个写内存之间的顺序,例如:

// thread A
技能 = 唱跳rap篮球;
STORESTORE_FENCE();
我 = 一名合格的练习生;
// thread B
if (我 == 一名合格的练习生) {
    print 技能.鸡你太美;
}

如果不会唱跳rap,练习时长肯定不足两年半,就一定不是一个合格的练习生;假定此时线程A中没有STORESTORE_FENCE,就可能会出现乱序,造成线程B的未定义行为,值得注意的是,线程A只负责写,线程B只负责读,一般意义上,两者不会造成冲突,但是当线程之间的逻辑耦合较多的时候,依然会出现未定义行为,此时,使用内存屏障可以很好的避免。

  • Load-Store

LOAD-STORE型的membar的工作场景可以理解为:对于这样的语句Load1; LoadStore; Store2,在Store2及后续写入操作被刷出前,保证Load1要读取的数据被读取完毕。

  • Store-Load

对于这样的语句Store1; StoreLoad; Load2,在Load2及后续所有读取操作执行前,保证Store1的写入对所有处理器可见。它的开销是四种屏障中最大的。在大多数处理器的实现中,这个屏障是个万能屏障,兼具其它三种内存屏障的功能。Store-Load乱序也是X86这类强内存序CPU上唯一允许的内存乱序。

PS:Java中的Volatile关键字就执行了严格的内存屏障:在每个volatile写操作前插入StoreStore屏障,在写操作后插入StoreLoad屏障;在每个volatile读操作前插入LoadLoad屏障,在读操作后插入LoadStore屏障;

所有以上种种,都是为了处理数据竞争,锁机制相对简单好用,内存屏障用于无锁情况,适用于颗粒比较细的竞争场景,实现原子操作。之所以我会总结这么多枯燥的东西,是为了实际需求铺垫,C++11中引入了六种内存序,levelDB在这样的机制下,实现了无锁一写多读的KV数据库,核心就是原子操作实现的SkipList,一切都是为了更好的研读Jeff Dean的代码做准备……

4. 参考

https://www.kernel.org/doc/Documentation/memory-barriers.txt
https://www.modernescpp.com/index.php/fences-as-memory-barriers
http://www.informit.com/articles/article.aspx?p=1832575&seqNum=3
https://preshing.com/20120710/memory-barriers-are-like-source-control-operations/
http://pic.dhe.ibm.com/infocenter/tpfhelp/current/index.jsp?topic=%2Fcom.ibm.ztpf-ztpfdf.doc_put.cur%2Fgtpc3%2Ftasinst.html
http://g.oswego.edu/dl/jmm/cookbook.html