(learn&think)

不浮躁，不自傲，学习，思考，总结

浅谈Memory Reordering

| Comments

Memory ordering

在我们编写的 C/C++代码和它被在 CPU 上运行,按照一些规则,代码的内存交互会被乱序.内存乱序同时由编译器(编译时候)和处理器(运行时)造成,都为了使代码运行的更快.

被编译开发者和处理器制造商遵循的中心内存排序准则是:

不能改变单线程程序的行为.

因为这条规则,在写单线程代码时内存乱序被普遍忽略.即使在多线程程序中,它也被时常忽略,因为有 mutexes,semaphores 等来防止它们调用中的内存乱序.仅当 lock-free 技术被使用时,内存在不受任何互斥保护下被多个线程共享,内存乱序的影响能被看到.

下面先比较 Weak 和 Strong 的内存模型,然后分两部分,实际内存乱序如何在编译和运行时发生,并如何防止它们.

Weak VS strong Memory Models

Jeff Preshing 在 Weak vs. Strong Memory Models 中很好的总结了从 Weak 到 Strong 的类型:

非常弱 数据依赖性的弱 强制 顺序一致
DEC Alpha ARM X86/64 dual 386
C/C++11 low-level atomics PowerPC SPARC TSO Java volatile/C/C++11 atomics

弱内存模型

在最弱的内存模型中,可能经历所有四种内存乱序 (LoadLoad, StoreStore, LoadStore and StoreLoad).任何 load 或 store 的操作能与任何的其他的 load 或 store 操作乱序,只要它不改变一个独立进程的行为.实际中,这样的乱序由于编译器引起的指令乱序或处理器本身处理指令的乱序.

当处理器是弱硬件内存模式,通常称它为 weakly-ordered 或 weak ordering.或说它有 relaxed memory model. DEC Alpha 是 最具代表 的弱排序的处理器.

C/C++的底层原子操作也呈现弱内存模型,无论代码的平台是如 x86/64 的强序处理器.下面章节 Memory ordering at compile time 会演示其弱内存模型,并说明如何强制内存顺序来保护编译器乱序.

数据依赖性的弱

ARM 和 PowerPC 系列的处理器内存模型和 Alpha 同样弱,除了它们保持 data dependency ordering.它意味两个相依赖的load(load A, load B<-A)被保证顺序load B<-A总能在 load A之后.(A data dependency barrier is a partial ordering on interdependent loads only; it is not required to have any effect on stores, independent loads or overlapping loads.)

强内存模型

弱和强内存模型区别存在分歧.Preshing 总结的定义是:

一个强硬件内存模型是在这样的硬件上每条机器指令隐性的保证 acquire and release
semantics 的执行.因此,当一个 CPU 核进行了一串写操作,每个其他的 CPU 核看到这些值的改变顺序与其顺序一致.

所以也就是保证了四种内存乱序 (LoadLoad, StoreStore, LoadStore and StoreLoad) 中的 3 种,除了不保证 StoreLoad 的顺序.基于以上的定义,x86/64 系列处理器基本就是强顺序的.之后 Memory ordering at processor time 可以看到 StoreLoad 在 X86/64 的乱序实验.

顺序一致

在顺序一致 (Sequential consistency) 的内存模型中,没有内存乱序存在.

如今,很难找到一个现代多核设备保证在硬件层 Sequential consistency.也就早期的 386 没有强大到能在运行时进行任何内存的乱序.

当用上层语言编程时,Sequential consistency 成为一个重要的软件内存模型.Java5 和之后版本,用volatile声明共享变量.在 C+11 中,可以使用默认的顺序约束memory_order_seq_cst在做原子操作时.当使用这些术语后,编译器会限制编译乱序和插入特定 CPU 的指令来指定合适的 memory barrier 类型.

Memory ordering at compile time

看如下代码:

test.c
1
2
3
4
5

int A, B;
void test() {
  A = B + 1;
  B = 0;
}

不打开编译器的优化,把它编译成汇编,我们可以看到,B的赋值在A的后面,和原程序的顺序一样.

1
2
3
4
5
6

$ gcc -S -masm=intel test.c

	mov	eax, DWORD PTR B
	add	eax, 1
	mov	DWORD PTR A, eax
	mov	DWORD PTR B, 0

用O2打开优化:

1
2
3
4
5
6

$ gcc -S -O2  -masm=intel test.c

	mov	eax, DWORD PTR B
	mov	DWORD PTR B, 0
	add	eax, 1
	mov	DWORD PTR A, eax

这次编译器把B的赋值提到A的前面.为什么它可以这么做呢?内存顺序的中心没有破坏.这样的改变并不影响单线程程序,单线程程序不能知道这样的区别.

但是当编写 lock-free 代码时,这样的编译器乱序就会引起问题.看如下例子,一个共享的标识来表明其他共享数据是否更新:

1
2
3
4
5
6

int value;
int updated = 0;
void UpdateValue(int x) {
    value = x;
    update = 1;
}

如果编译器把update的赋值提到value赋值的前面.即使在单核处理器系统中,会有问题:在两个参数赋值的中间这个线程被中断,使得另外的程序通过update判断以为value的值已经得到更新,实际上却没有.

显性的 Compiler Barriers

一种方法是用一个特殊的被称为 Compiler Barrier 的指令来防止编译器优化的乱序.以下 asm volative 是 GCC 中的方法.

test_barrier.c
1
2
3
4
5
6

int A, B;
void test() {
  A = B + 1;
  asm volatile("" ::: "memory");
  B = 0;
}

经过这样的修改,打开优化,B的存储将保持在要求的顺序上.

1
2
3
4
5
6

$ gcc -S -O2  -masm=intel test.c

	mov	eax, DWORD PTR B
	add	eax, 1
	mov	DWORD PTR A, eax
	mov	DWORD PTR B, 0

隐性的 Compiler Barriers

在 C++11 中原子库中,每个不是 relaxed 的原子操作同时是一个 compiler barrier.

1
2
3
4
5
6
7

int value;
std::atomic<int> updated(0);
void UpdateValue(int x) {
    value = x;
    // reordering is prevented here
    update.store(1, std::memory_order_release);
}

每一个拥有 compiler barrier 的函数本身也是一个 compiler barrier,即使它是 inline 的.

1
2
3
4
5
6
7

int a;
int b;
void DoSomething() {
    a = 1;
    UpdateValue(1);
    b = a + 1;
}

进一步推知,大多数被调用的函数是一个 compiler barrier.无论它们是否包含 memory barrier.排除 inline 函数,被声明为pure attribution 或当 link-time code generation 使用时.因为编译器在编译时,并不知道UpdateValue的运行是否依赖于a或会改变a的值从而影响b,所以编译器不会乱序它们之间的顺序.

可以看到,有许多隐藏的规则禁止编译指令的乱序,也防止了编译器多进一步的代码优化,所以在某些场景 Why the “volatile” type class should not be used, 来让编译器进一步优化.

无缘由的存储

有隐形的 Compiler Barriers,同样 GCC 编译器也有无缘由的存储.来自这里的实例:

1
2
3
4
5
6
7
8

extern int v;

    void
    f(int set_v)
    {
      if (set_v)
        v = 1;
    }

在 i686,GCC 3.3.4–4.3.0 用O1编译得到:

1
2
3
4
5
6
7
8

        pushl   %ebp
        movl    %esp, %ebp
        cmpl    $0, 8(%ebp)
        movl    $1, %eax
        cmove   v, %eax        ; load (maybe)
        movl    %eax, v        ; store (always)
        popl    %ebp
        ret

在单线程中,没有问题,但多线程中调用f(0)仅仅只是读取 v 的值,但中断后回去覆盖其他线程修改的值.引起 data rate.在新的 C++11 标准中明确禁止了这样的行为,看最近 C+11 标准进行的 draft§1.10.22 节:

Compiler transformations that introduce assignments to a potentially shared memory location that would not be modified by the abstract machine are generally precluded by this standard.

Memory ordering at processor time

看一个简单的 CPU 乱序的简单例子,即使在强内存模型的 X86/64 也能看到.有两个整数X和Y初始是 0,另外两个变量 r1 和 r2 读取它们的值,两个线程并行运行,执行如下的机器代码:

每个线程存储 1 到一个共享变量,然后把对方变量读取到一个变量或一个寄存器中.无论哪个线程先写 1 到内存,另外个线程读回那个值,意味着最后 r1=1 或 r2=1 或两者都是.但是 X86/64 是强内存模型,它还是允许乱序机器指令.特别,每个线程允许延迟存储到读回之后.以致最后 r1 和 r2 能同时等于 0–违反直觉的一个结果.因为指令可能如下顺序执行:

写一个实例程序,实际看一下 CPU 的确乱序了指令.源码可以 Github 下载.两个读写的线程代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

sem_t begin_sem1;
sem_t begin_sem2;
sem_t end_sem;

int X, Y;
int r1, r2;

void *ThreadFunc1(void *param) {
  MersenneTwister random(1);
  for (;;) {
    sem_wait(&begin_sem1);
    // random delay
    while (random.Integer() % 8 != 0) {
    }
    X = 1;
    asm volatile("" ::: "memory");  // prevent compiler ordering
    r1 = Y;
    sem_post(&end_sem);
  }
  return NULL;
}

void *ThreadFunc2(void *param) {
  MersenneTwister random(2);
  for (;;) {
    sem_wait(&begin_sem2);
    // random delay
    while (random.Integer() % 8 != 0) {
    }
    Y = 1;
    asm volatile("" ::: "memory");  // prevent compiler ordering
    r2 = X;
    sem_post(&end_sem);
  }
  return NULL;
}

随机的延迟被插入在存储的开始处,为了交错线程的开始时间,以来达到重叠两个线程的指令的目的.随机延迟使用线程安全的MersenneTwister类.汇编代码asm volatile("" ::: "memory");如上节所述只是用来 防止编译器的乱序, 因为这里是要看 CPU 的乱序,排除编译器的乱序影响.

主线程如下,利用 POSIX 的 semaphore 同步它与两个子线程的同步.先让两个子线程等待,直到主线程初始化X=0和 Y=0.然后主线程等待,直到两个子线程完成操作,然后主线程检查r1和r2的值.所以 semaphore 防止线程见的不同步引起的内存乱序,主线程代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

int main(int argc, char *argv[]) {
  sem_init(&begin_sem1, 0, 0);
  sem_init(&begin_sem2, 0, 0);
  sem_init(&end_sem, 0, 0);

  pthread_t thread[2];
  pthread_create(&thread[0], NULL, ThreadFunc1, NULL);
  pthread_create(&thread[1], NULL, ThreadFunc2, NULL);

  int detected = 0;
  for (int i = 1; ; ++i) {
    X = 0;
    Y = 0;
    sem_post(&begin_sem1);
    sem_post(&begin_sem2);
    sem_wait(&end_sem);
    sem_wait(&end_sem);
    if (r1 == 0 && r2 == 0) {
      detected++;
      printf("%d reorders detected after %d iterations\n", detected, i);
    }
  }
  return 0;
}

在 Intel i5-2435M X64 的 ubuntu 下运行一下程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

1 reorders detected after 2181 iterations
2 reorders detected after 4575 iterations
3 reorders detected after 7689 iterations
4 reorders detected after 22215 iterations
5 reorders detected after 60023 iterations
6 reorders detected after 60499 iterations
7 reorders detected after 61639 iterations
8 reorders detected after 62243 iterations
9 reorders detected after 67998 iterations
10 reorders detected after 68098 iterations
11 reorders detected after 71179 iterations
12 reorders detected after 71668 iterations
13 reorders detected after 72417 iterations
14 reorders detected after 73970 iterations
15 reorders detected after 78227 iterations
16 reorders detected after 81897 iterations
17 reorders detected after 82722 iterations
18 reorders detected after 85377 iterations
...

差不多每 4000 次的迭代才发现一次 CPU 内存乱序.所以多线程的 bug 是多么难发现.那么如何消除这些乱序.至少有如下两种方法:

  1. 让两个子线程在同一个 CPU 核下运行.(没有可移植性方法,如下是 linux 平台的).
  2. 使用 CPU 的 memory barrier 防止它的乱序.

Lock to one processor

让两个子线程在同一个 CPU 核下运行,代码如下:

1
2
3
4
5

  cpu_set_t cpus;
  CPU_ZERO(&cpus);
  CPU_SET(0, &cpus);
  pthread_setaffinity_np(thread[0], sizeof(cpu_set_t), &cpus);
  pthread_setaffinity_np(thread[1], sizeof(cpu_set_t), &cpus);

Place a memory barrier

防止一个 Store 在 Load 之后的乱序,需要一个 StoreLoad 的 barrier.这里使用 mfence的一个全部 memory barrier,防止任何类型的内存乱序.代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

void *ThreadFunc1(void *param) {
  MersenneTwister random(1);
  for (;;) {
    sem_wait(&begin_sem1);
    // random delay
    while (random.Integer() % 8 != 0) {
    }
    X = 1;
    asm volatile("mfence" ::: "memory");  // prevent CPU ordering
    r1 = Y;
    sem_post(&end_sem);
  }
  return NULL;
  }

More

  1. University of Cambridge 整理的文档和论文
  2. Paul McKenney 概括他们做的一些工作和工具
  3. The Art of Multiprocessor Programming
  4. C++ Concurrency in Action: Practical Multithreading
  5. Is Parallel Programming Hard, And, If So, What Can You Do About It?
  6. The C++11 Memory Model and GCC

Summarization

  1. 有两种内存乱序存在:编译器乱序和 CPU 乱序.
  2. 如何防止编译器乱序.
  3. 如何防止 CPU 乱序.

Comments