Memory Ordering

Memory ordering描述了CPU访问系统内存,执行load和store的顺序。Memory ordering包括编译时编译器生成的和运行时CPU生成的。为了高效地执行指令,只要不影响单线程程序的行为,编译器和CPU常常会对指令进行memory reordering,使得访问内存的操作不会按照程序代码中指定的顺序执行。

在单线程程序中,可以忽略reordering的存在;在多线程程序中,mutex,semaphores等互斥方法会保证在相关函数的调用周围没有reordering。在多核环境下(或对称多处理器架构)下,用C、C++等编写lock-free代码时,memory reordering是可观察到的,是重点要考虑的问题。

Compiler Reordering

从源代码得到CPU指令的过程中,编译器会做很多事情,其中之一就是reordering。(例子摘自Preshing on Programming

1
2
3
4
5
6
int Value;
int IsPublished = 0;
void sendValue(int x) {
Value = x;
IsPublished = 1;
}

如果IsPublished = 1;被reordered到Value = x;之前,那么IsPublished作为flag的作用就丧失了。既是是在单线程中,也会有问题。如果该线程在两次store之间被抢占,那么其他使用Value的线程就会访问到Value的旧值,而不是新值。

Compiler Barriers

防止编译器reordering最简单的办法莫过于使用compiler barriers,在不想被reordered的两个操作(load和store)之间加入compiler Barrierasm volatile("" ::: "memory"),但在多核环境下,这并不足够。还需要下面的CPU fence来提供运行时memory barrier的保障。如果使用了CPU fence,那么fence也会作为compiler Barrier。

另一种compiler barrier是函数调用,无论函数是否包含compiler barrier,除了inline函数、声明带有pure属性的函数和使用了链接时代码生成的函数,大多数函数调用都可以作为compiler barrier。因为编译器根本不知道该函数调用是否会修改先前的值,也不知道这个值是否在函数调用返回后会被继续使用,如果进行了reordering,那么很可能会违反一开始提到的原则。而对于包含的函数,无论是不是inline的,都可以作为compiler barrier。

C/C++中,volatie会阻止编译器的优化,编译器不会volatie变量间的操作进行reordering,但是volatie对处理器的reordering是无能为力的,并没有happens-before语义。与此同时,volatie也不能阻止多个线程的并发访问。对于下面的代码,无论shared_data是不是volatiespin_lock都是必须的。

1
2
3
4
spin_lock(&the_lock);
do_something_on(&shared_data);
do_something_else_with(&shared_data);
spin_unlock(&the_lock);

代码里的spin_lock也下面将说的memory barrier。

Processor Reordering

除了编译器会进行reordering,CPU同样会。CPU的reordering仅在多核或多处理器环境下才是可见的。(例子摘自Preshing on Programming

考虑下面的一段代码,thread1Functhread2Func分别在两个线程中运行,最后r1r2的结果会是什么?为了阻止编译器的reordering,已经在store和load之间加入了compiler barrier。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int X, Y;
int r1, r2;
void *thread1Func(void *param) {
X = 1;
asm volatile("" ::: "memory")
r2 = Y;
return NULL;
};
void *thread2Func(void *param) {
Y = 1;
asm volatile("" ::: "memory")
r2 = X;
return NULL;
};

由于是并发执行,两个线程的load和store会交替执行,因此r1r2的结果可能为,

1
2
3
r1=0 r2=1
r1=1 r2=0
r1=1 r2=1

r1=0 r2=0也是完全可能的,如果重复的进行测试,那么这个结果会频繁的发生。Intel在64 and IA-32 Architectures Software Developer's Manual中的8.2.3.4指出,

At each processor, the load and the store are to different locations and hence may be reordered.

代码中每个线程的store和load是不同的内存位置,所以发生StoreLoad Reordering是完全可能的。

Memory Barrier

上述例子的reordering只是众多memory reordering中的一种,主要有四种memory reordering

  • LoadLoad
  • StoreStore
  • LoadStore
  • StoreLoad

类似compiler reordering,需要compiler barrier来阻止CPU的reordering,这里是memory barriers,也叫fence指令。Fence保证了fence之前的load或store和之后的load或store是严格有序的。针对以上四种reordering,有对应的四种barrier,#LoadLoad#StoreStore#LoadStore#StoreLoad。对于现实中CPU的fence指令的行为,通常是上述几种的融合,且还会有其他的效果。

1
Store1; #StoreLoad; Load2;

需要特别说明的是#StoreLoad,这个barrier是唯一能够保证上述例子不出现r1=0 r2=0的。#StoreLoad保证了在barrier前执行Store1对其他处理器是可见的,在barrier后执行的Load2能够得到在barrier之后最新的值(不一定是Store1的值)。#StoreLoad防止了后续的load错误的使用Store1的值,而不是其他处理器在同一内存位置store的更新的值。#StoreLoad几乎在所有现代的多处理器上都是必须的,同时也是代价最高昂的一种barrier。

除了fence指令,memory barrier还有,

  • C++11中,很多原子类型的操作;
  • pthread中,mutex,spin_lock,semaphore的操作。