深入探索并发编程系列(五)-将内存乱序逮个正着

发表于   |   分类于   |  

当用C/C++编写无锁代码时，一定要小心谨慎，以保证正确的内存顺序。不然的话，会发生一些诡异的事情。

Intel在x86/x64体系结构手册的Volume 3, §8.2.3 中列出了一些可能会发生的诡异的事情。这里介绍其中一个最简单的例子。假设在内存中有两个整型变量x和y，都初始化为0。两个处理器并行执行下面的机器码：

不要被上面的汇编代码给吓坏了。这个例子的确是阐述CPU执行顺序的最好方式。每个处理器将1写入其中一个整型变量中，然后将另一个整型变量读取到寄存器中。（r1和r2只是x86中真实寄存器-如eax寄存器-的代表符号).

现在不管哪个处理器先将1写入内存，都想当然的认为另一个处理器会读到这个值，这就意味着最后结果中要么r1=1，要么r2=1，要么这两个结果同时满足。但根据Intel手册，却不是这么回事。手册上说在这个例子里，最终r1和r2的值都有可能等于0。至少可以这么说，这个结果是不太符合大家直觉的。

可以这么理解：Intel x86/x64处理器，和大部分处理器家族一样，在保证不改变一个单线程程序执行的基础上，会根据一定的规则将机器指令对内存的操作顺序重新排序。具体来说，对于不同内存变量的写读操作，处理器保留乱序的权利注1。 结果就好像是指令就是按照下图这个顺序执行的：

指令乱序重现

能被告知这种诡异的事情会发生总是好的，但眼见才为实。这也就是我为什么要写个小程序来说明这种重新排序会发生的原因。你可以在这里下载源码。

代码样例分别包含Win32和POSIX版本。代码中会派生出两个工作线程不断重复上述的事务，主线程用来同步这些工作并检查最终结果。

下面是第一个工作线程的源码。X,Y,r1和r2都是全局变量，POSIX信号量用来协调每个循环的开始和结束。

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

int X, Y;
int r1, r2;

void *thread1Func(void *param)
{
    MersenneTwister random(1);                // Initialize random number generator
    for (;;)                                  // Loop indefinitely
    {
        sem_wait(&beginSema1);                // Wait for signal from main thread
        while (random.integer() % 8 != 0) {}  // Add a short, random delay

        // ----- THE TRANSACTION! -----
        X = 1;
        asm volatile("" ::: "memory");        // Prevent compiler reordering
        r1 = Y;

        sem_post(&endSema);                   // Notify transaction complete
    }
    return NULL;  // Never returns
};

每个事务前用一个短暂、随机的延迟用来错开线程的时间。记住，这里有两个工作线程，我们要试着将他们的指令重叠。随机延迟是用我前面文章，锁不慢；锁竞争慢 和实现递归锁的使用过的MersenneTwister来实现的。

别被上面代码中的asm volatile给吓坏了。其作用就是直接告诉GCC编译器在生成机器码的时候不要重新安排store和load操作，以防在优化期间做了手脚注2. 我们可以检查下面的汇编代码来验证这个过程。意料之中，store和load操作按照我们想要的顺序执行。之后的指令将eax寄存器中的结果写回到全局变量r1中。

1
2
3
4
5
6
7
$ gcc -O2 -c -S -masm=intel ordering.cpp
$ cat ordering.s
    ...
    mov    DWORD PTR _X, 1
    mov    eax, DWORD PTR _Y
    mov    DWORD PTR _r1, eax
    ...

主线程的源码如下。其执行所有的管理工作。初始化后，进入无限循环，在每次迭代开始工作线程之前会重新设置X和Y为0。

注意sem_post之前所有有可能发生的共享内存写操作，以及sem_wait之后所有有可能发生的共享内存读操作。工作线程在和主线程通信的过程中也要遵守同样的规则。信号量为每个平台提供了acquire和release语义。这意味着我们可以保证初始值X=0和Y=0可以完全传播到工作线程中，r1和r2的结果也会被完整传回来。换句话说，信号量阻止了乱序注3，可以让我们全心关注实验本身。

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
int main()
{
    // Initialize the semaphores
    sem_init(&beginSema1, 0, 0);
    sem_init(&beginSema2, 0, 0);
    sem_init(&endSema, 0, 0);

    // Spawn the threads
    pthread_t thread1, thread2;
    pthread_create(&thread1, NULL, thread1Func, NULL);
    pthread_create(&thread2, NULL, thread2Func, NULL);

    // Repeat the experiment ad infinitum
    int detected = 0;
    for (int iterations = 1; ; iterations++)
    {
        // Reset X and Y
        X = 0;
        Y = 0;
        // Signal both threads
        sem_post(&beginSema1);
        sem_post(&beginSema2);
        // Wait for both threads
        sem_wait(&endSema);
        sem_wait(&endSema);
        // Check if there was a simultaneous reorder
        if (r1 == 0 && r2 == 0)
        {
            detected++;
            printf("%d reorders detected after %d iterations\n", detected, iterations);
        }
    }
    return 0;  // Never returns
}

最后，关键时刻到了。这是在Intel Xeon W3520中运行Cygin的输出。

在运行期间，每6600次迭代差不多能检测到一次乱序。当我在Core 2 Duo E6300处理器Ubuntu系统中测试时，乱序的次数更少见。大家开始对这种微妙的timing bug是如何能蔓延到无锁代码中而不被检测到感到刺激。

现在，假设你想避免这种乱序，至少有两种方法可以做到。其中一种方法就是设置线程亲和力（thread affinities），以让两个工作线程能在同一个CPU核上独立运行。Pthreads中没有可移植的方法设置亲和力，但在Linux上，可以这样来实现：

1
2
3
4
5
cpu_set_t cpus;
CPU_ZERO(&cpus);
CPU_SET(0, &cpus);
pthread_setaffinity_np(thread1, sizeof(cpu_set_t), &cpus);
pthread_setaffinity_np(thread2, sizeof(cpu_set_t), &cpus);

这样修改之后，乱序就不会发生了。那是因为尽管当线程在任一时间抢占处理器并被重新调度，单个处理器绝不会让自己的操作乱序注4。当然了，将两个线程都锁到一个单独的核中，其它核就用不上了。

与此相关的是，我在Playstation 3上编译并运行了这份代码，没有检测到乱序的情况。这意味着（不能确信)在PPU里的两个硬件线程可能会充当一个单处理器，具有细粒度的硬件调度能力。

用Storeload Barrier来避免

在这个例子中，另一种阻止内存乱序的方法是在两条指令间引入一个CPU级的Memory Barrier。在这里，我们要避免store操作紧接load操作的乱序情况。用惯用的barrier行话来说， 我们需要的是一个Storeload barrier。

在x86/x64处理器中，没有特定的指令用来充当Storeload barrier,但有其它的一些指令能做到甚至更多的事情。mfence指令就是一个full memory barrier，可以避免任何形式的内存乱序。在GCC中，实现方式如下：

1
2
3
4
5
6
7
8
9
10
11
12
for (;;)                                  // Loop indefinitely
{
    sem_wait(&beginSema1);                // Wait for signal from main thread
    while (random.integer() % 8 != 0) {}  // Add a short, random delay

    // ----- THE TRANSACTION! -----
    X = 1;
    asm volatile("mfence" ::: "memory");  // Prevent memory reordering
    r1 = Y;

    sem_post(&endSema);                   // Notify transaction complete
}

同样地，可以检查下面的汇编代码来验证。

1
2
3
4
5
6
...
   mov    DWORD PTR _X, 1
   mfence
   mov    eax, DWORD PTR _Y
   mov    DWORD PTR _r1, eax
   ...

这样修改之后，内存乱序就不会发生了，并且我们依然允许两个线程分别运行在不同的CPU核中注5。

类似指令与不同平台

有趣的是，mfence并不是x86/x64平台中能唯一充当full memory barrier的指令。在这些处理器中，假设你不使用SSE指令或者写结合内存(Write-combined Memory)（例子中也并没有用到），任何带lock的指令，比如xchg，也能作为一个full memory barrier。实际上，Microsoft C++编译器在你使用MemoryBarrier时会生成xchg指令，至少Visualstudio 2008是这么做的

mfence指令是x86/x64平台独有的注6。如果你想让代码具有可移植性，可以将这种固有特性写成一个预处理的宏。Linux内核将其封装成一个叫做smp_mb的宏，以及相关的宏smp_rmb和smp_wmb宏注7，并提供了在不同架构中的不同实现方法。 例如，在PowerPC中，smp_mb宏是通过sync来实现的.

在这些不同的CPU家族中，每种CPU都有各自的指令来保证内存访问顺序，每个编译器通过不同的内置属性展现出来，每种跨平台的项目都会实现自己的可移植层。 然而，这些都不能让无锁编程变得更加简单。 这就是C++11原子库标准在最近被提出来的部分原因。这是标准化的一次尝试，可能会让写可移植性的无锁代码变得更加简单。

译者注

注1：注意，这里说的是写读乱序，而且是对不同变量的写读操作的乱序。在Intel x86/x64处理器中，读读、写写、读写、以及写读同一个内存变量，CPU是不会乱序的。

注2：asm volatile("" ::: "memory")是一条编译器级别的Memory Barrier，可以防止编译器对相邻指令进行乱序，但是它对CPU乱序是没有影响的；也就是说它仅仅束缚了编译器的乱序优化，不会阻止CPU可能的乱序执行。这么做自然是将编译器的干扰和影响降到最低，好让我们专注观察CPU的执行行为。

注3：请务必注意，这里说的阻止乱序是指防止了向sem_wait和sem_post之外的乱序，不阻止它们之间的乱序。举个例子：

1
2
3
4
mutex.lock();
a=1;
b=2;
mutex.unlock;

这里lock保证了a=1和b=2这两行代码不会被拉到lock之上执行；同理，也不会被拉到unlock之下执行。

因此，我们说lock和unlock分别提供了acquire语义和release语义。但是lock和unlock之间的代码是允许乱序的，也可能发生乱序的，而这正是这个实验的目的。

这里，lock对应文中的sem_wait，unlock对应sem_post。借此机会，读者可以对锁有更好的认识。

注4：也就是说，单核多线程、多核单线程程序不用担心memory reordering问题，只有多核多线程才需要小心谨慎。为什么呢？请看下面的注5。

注5：到目前为止，读者可能会对通篇文章里的内容有两个疑问：

1，为什么CPU要乱序执行，难道是考虑性能吗？那为什么乱序就能提升性能？

2，为什么在Intel X86/64架构下，就只有写读（Store Load）发生乱序呢？读读呢？读写呢？

要明白这两个问题，我们首先得知道cache coherency，也就是所谓的cache一致性。

在现代计算机里，一般包含至少三种角色：cpu、cache、内存。一般说来，内存只有一个；CPU Core有多个；cache有多级，cache的基本块单位是cacheline，大小一般是64B-256B。

每个cpu core有自己的私有的cache(有一级cache是共享的)，而cache只是内存的副本。那么这就带来一个问题：如何保证每个cpu core中的cache是一致的？

在广泛使用的cache一致性协议即MESI协议中，cacheline有四种状态：Modified、Exclusive、Shared、Invalid，分别表示修改、独占、共享、无效。

当某个cpu core写一个内存变量时，往往是（先）只修改cache，那么这就会导致不一致。为了保证一致，需要先把其他core的对应的cacheline都invalid掉，给其他core们发送invalid消息，然后等待它们的response。

这个过程是耗时的，需要执行写变量的core等待，阻塞了它后面的操作。为了解决这个问题，cpu core往往有自己专属的store buffer。

等待其他core给它response的时候，就可以先写store buffer，然后继续后面的读操作，对外表现就是写读乱序。

因为写操作是写到store buffer中的，而store buffer是私有的，对其他core是透明的，core1无法访问core2的store buffer。因此其他core读不到这样的修改。

这就是大概的原理。MESI协议非常复杂，背后的技术也很有意思。

注6：不建议使用这么原生(raw) 的memory barrier。在GCC下，推荐使用__sync_synchronize。

注7：X86下，smp_wmb是一个空宏，什么也不做；而smp_rmb则不是。想想看，为什么。

注8：作为练习，请读者朋友们分析以下问题，其中A、B、C的初值都是0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
thread1(void)
{
  A = 1;
  cpu_barrier();
  B = 1;
}
thread2(void)
{
  while (B != 1)
    continue;
  compiler_barrier();
  C = 1;
}
thread3(void)
{
  while (C != 1)
    continue;
  compiler_barrier();
  assert(A != 0);
}

其中，cpu_barrier是cpu级别的memory barrier，影响cpu和编译器，防止它们乱序；compiler_barrier只防止编译器乱序。

问题：thread3中的断言是否可能会失败？为什么？别急着回答，考虑平台是否是x86？考虑单核多线程、多核单线程、多核多线程？

另外，这篇流传很广的文章有错，务必小心：http://blog.csdn.net/jnu_simba/article/details/22985913

注9：注意，我们的讨论只针对普通指令，对于SSE等特殊指令，情况可能完全不同。这点读者务必注意。

Acknowledgement

本文由 Diting0x 与 睡眼惺忪的小叶先森 共同完成，在原文的基础上添加了许多精华注释，帮助大家理解。

感谢好友小伙伴-小伙伴儿 与skyline09_ 阅读了初稿，并给出宝贵的意见。

原文： http://preshing.com/20120515/memory-reordering-caught-in-the-act/

本文遵守Attribution-NonCommercial-NoDerivatives 4.0 International License (CC BY-NC-ND 4.0)
仅为学习使用，未经博主同意，请勿转载
本系列文章已经获得了原作者preshing的授权。版权归原作者和本网站共同所有

攒点碎银娶媳妇