Memory Barriers in A Nutshell

并发编程相关的一些代码如Linux内核有时候会遇上对内存屏障的调用,本文简单说明了下为什么会存在这个东西,会带来哪些问题以及要如何处理.

1. 什么是内存指令乱序
内存乱序是指在保证程序在单线程环境下行为正确的前提下,程序指令的实际执行顺序可以调换(相对源码).
这里行为正确是指乱序后产生的结果与不乱序的程序没有出入.
这个行为对多线程编程下操作共享变量时会产生微妙的影响,举两个例子:

//例子1
int X = 0;
int Y = 0;
int r1, r2;

//on cpu1
void threadfunc1() {
  X = 1;
  r1 = Y;
}

//on cpu2
void threadfunc2() {
  Y = 1;
  r2 = X;
}

如在thread1中,对X的赋值和Y的读取是无关的,单线程下可任意顺序执行.
但假如thread1和thread2都发生了乱序执行, 则有可能在某个时刻r1和r2赋值操作后的值同时为0.
这不是特别符合直觉和逻辑, 因为即使2个线程并发执行, r1和r2赋值后看上去应该至少有1个为1.

再来看个更实际点的例子:

int data = 0;
int dataReadyFlag = 0;

//on cpu1
void threadfunc1() {
  data = 999; 
  dataReadyFlag = 1;
}

//on cpu2
void threadfunc2() {
  if (dataReadyFlag == 1) {
    int ret = data + 100;
  }
}

这里thread1的意图是data准备好了才能设置flag对外发布,但假如两个赋值乱序了,则有可能data在thread1中
还没准备好就发布了导致thread2使用了无效的data. 这里发生了Store-Store乱序.
同样的thread2也有可能在读flag之前就去读data,于是可能读到旧的thread1初始化之前的data,而此时flag却是新的. 这里发生了Load-Load乱序.
(在这个例子中我们假设对相关int的读写操作是原子的,实际成立的前提是int内存对齐)

2. 乱序如何发生以及原因

在上述保证单线程语义正确的前提下,乱序执行可能在以下两个阶段产生:
a) 编译阶段,产生与源代码不同的指令顺序.
主要原因是编译优化策略,因此把优化开关打开后发生的概率大些.
这个阶段的乱序策略主要是ToolChain相关.

b) cpu执行内存阶段,load/store发生的顺序与指令顺序不同.
同样也是为了优化,如延迟Store. 具体策略主要和cpu平台架构相关.
如x86是所谓的强内存模型,只存在StoreLoad乱序(例子1),其他默认保序,不会发生例子2.

这里注意如果是单cpu或单核上执行多线程程序,则不会发生乱序问题,因为此时cpu只能"看到"同一线程的上下文,就好比单线程执行不存在乱序.
因此cpu执行阶段内存乱序问题只有在多核环境下才存在.

3. 什么时候需要关注
乱序看去比较普遍,但应用程序开发比较少需要直接关注乱序问题,主要是因为
a) 单线程编程,根据定义乱序没有影响.
b) 很多场景下如外部函数调用前后是自带内存屏障的.
c) 多线程编程,线程之间使用锁机制来做共享同步。而锁本身一定是蕴含了对内存乱序的处理的,否则锁保护将失效:
lock_must_enforce_order
可见我们平时只关注了锁的互斥访问功能,而忽略了其内置的内存指令顺序保证.

因此一般是多线程环境下使用无锁编程技术时要关注内存乱序问题,比如配合原子操作做同步,或者自己实现锁机制的时候,一定要考虑.
而使用无锁编程一般是为了避免锁开销,临界区一般较小,使用锁不划算. 如Linux smp内核.

4. 什么是Memory Barrier
理论上通过关编译器优化和单核运行所有线程可以避免乱序问题,但不太实际.
一般通过一类特殊指令可以改变编译器和cpu的乱序行为,即内存屏障.
比如gcc x86下:
编译器内存屏障指令:asm volatile("" ::: "memory")
cpu内存屏障指令:asm volatile("mfence" ::: "memory")
在内存屏障前后的一些种类的操作顺序是不可交换的.
具体内存屏障分为多种,如Store-Store/Load-Load/Store-Load/Load-Store/Data_Dependancy
详见这篇好文.
上面x86的mfence是一个最严格的类型,杜绝了任意指令间的乱序.

cpu屏障一般蕴含了编译器屏障,而在单cpu下一般内存屏障退化为编译器屏障.

5. AcquireLoad和ReleaseStore语义
这里考虑如何使用内存屏障来解决例子2的问题.
在thread1中我们要保证flag发布时,前面的初始化一定要先执行,因此两者之间需要Store-Store屏障.
同样在thread2中要保证的是读取flag后,data必须不能是早于flag的旧数据,因此两者间需要Load-Load屏障:

int data = 0;
int dataReadyFlag = 0;

//on cpu1
void threadfunc1() {
  data = 999; 
  STORESTORE_BARRIER();
  dataReadyFlag = 1;
}

//on cpu2
void threadfunc2() {
  if (dataReadyFlag == 1) {
    LOADLOAD_BARRIER();
    int ret = data + 100;
  }
}

这种模式在无锁编程中用于做同步时比较普遍,因此抽象出来分别叫Acquire和Rlease语义
Acquire和Release语义(Semantics)是程序语言和CPU内存模型(Memory Model)中的一个概念。以下,是截取自Preshing博客《Acquire and Release Semantics》一文中,对Acquire与Release Semantics的定义:

Acquire semantics is a property which can only apply to operations which read from shared memory, whether they are read-modify-write operations or plain loads. The operation is then considered a read-acquire. Acquire semantics prevent memory reordering of the read-acquire with any read or write operation which follows it in program order. (注:Acquire语义是一个作用于内存读操作上的特性,此内存读操作即被视为read-acquire。Acquire语义禁止read-acquire之后所有的内存读写操作,被提前到read-acquire操作之前进行。)

Release semantics is a property which can only apply to operations which write to shared memory, whether they are read-modify-write operations or plain stores. The operation is then considered a write-release. Release semantics prevent memory reordering of the write-release with any read or write operation which precedes it in program order.(注:Release语义作用于内存写操作之上的特性,此内存写操作即被视为write-release。Release语义禁止write-release之前所有的内存读写操作,被推迟到write-release操作之后进行。)

PowerPC下的一个例子图示,来自参考资料[6]:
acquire_release_sematics

6. 一个实际应用
看一个leveldb中x86下原子指针类型的实现,严格采用了AcquireLoad和ReleaseStore的方式:

inline void MemoryBarrier() {
  // See http://gcc.gnu.org/ml/gcc/2003-04/msg01180.html for a discussion on
  // this idiom. Also seehttp://en.wikipedia.org/wiki/Memory_ordering.
  __asm__ __volatile__("": : : "memory");
}

class AtomicPointer {
 private:
  void* rep_;
 public:
  AtomicPointer() { }
  explicitAtomicPointer(void* p) : rep_(p) {}
  inline void* NoBarrier_Load() const { return rep_; }
  inline void NoBarrier_Store(void* v) { rep_ = v; }
  inline void* Acquire_Load() const {
    void* result = rep_;
    MemoryBarrier();
    return result;
  }
  inline void Release_Store(void* v) {
    MemoryBarrier();
    rep_ = v;
  }
};

(1) 对齐指针类型的读写在x86下是原子的.
(2) 读操作Acquire_Load在读取指针之后插入内存屏障,保证后面访问该指针指向的内存内容是新值(不比拿到rep_时旧).
(3) 写操作Release_Store在写指针之前插入内存屏障,保证之前对指针指向内容的更改一定在指针发布之前完成.
(4) 只用了编译器屏障,因为x86是强内存模型;至于StoreLoad乱序,但leveldb在此场景下是单写多读,因而不受影响.

7. Lock Revisited
再来看Lock本身蕴含的Acquire和Release语义:
lock_acquire_release

8.参考资料
[1] memory-reordering-caught-in-the-act
[2] memory-ordering-at-compile-time
[3] memory-barriers-are-like-source-control-operations
[4] the-happens-before-relation
[5] the-synchronizes-with-relation
[6] acquire-and-release-semantics
[7] 锁的意义
[8] LevelDB: AtomicPointer

发表评论

电子邮件地址不会被公开。