杰峰的博客

浅谈Memory barrier

Contents

浅谈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

浏览量: 3,021

已发布

分类

来自

jeff

标签：

,