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

编写lock-free C/C++程序时，在保证memory ordering正确性上要非常小心，否则，奇怪的事就来了。Intel在《x86/64 Architecture Specification》Volume 3, §8.2.3一节中列出了一些可能发生的“怪事”。来看一个小例子：X，Y两个变量均被初始化为0， 编写如下汇编代码，由两个处理器(processor)执行：

为了清楚的阐述CPU ordering，此处使用了汇编指令。每个处理器将一个变量赋值为1(store)，并读取另外一个变量(load)，此处的r1、r2代表寄存器。正常情况下，不管处理器的执行顺序如何，r1，r2所有可能的结果为：

r1==0, r2 ==1 
r1==1, r2==0
r1==1, r2==1

不可能的结果为:

r1==0, r2==0。

按Intel文档中的描述， 上述结果是有可能的，这就是本文所要讲述的“怪事”（至少是违反直觉的）。
Intel x86/x64处理器和大多数处理器家族一样，在不影响单个线程执行结果的前提下，允许对内存交互指令进行重排(reorder)。特别指出：处理器允许将store动作延迟到任何load动作之后,只要load、store的操作的不是同一块内存。因此，您编写的汇编代码在执行时可能变成了这样：

来，试试！

“好好好，你说这事可能发生，但我从来没见过，叫我如何相信？”
那...叫我们来试试如何：源码在这。
这份代码包括win32、POSIX两个版本，由两个派生线程重复执行上述transaction代码，并由主线程核对执行结果。
第一个工作线程源码如下：x, y, r1, r2为全局变量，两个POSIX semaphores用于和主线程的并发处理：

第二个线程处理类似，只需将r1换成r2，beginSema1换成beginSema2

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来实现的，例如在测量锁争用 时以及验证递归的Benaphore是否工作时。别被asm volatile这行代码唬到，这只是告诉GCC编译器在生成机器码时，不要重排store和load，以防GCC在编译优化时又想出了什么“歪点子”。

来看编译后的汇编代码：

$ 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
    ...

Store和load的顺序和预期的一致，先执行X=1，随后执行r1=Y。

下面是主线程代码，职责如下：初始化后，进入无限循环，重置x，y为0，通过信号量触发两个线程运行。
需要注意的是：所有写入共享内存的方式都是在sem_post之前发生的，所有从共享内存读取的数据都是在sem_wait之后发生的。在与主线程通信时，工作线程遵循相同的规则。信号量给我们在每个平台上获取和释放语义。这意味着我们保证X = 0和Y = 0的初始值将正确传递到工作线程，并且r1和r2的结果值将从工作线程传递到主线程。换句话说，信号量避免在框架中出现内存重排序，让我们完全专注于实验本身！

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、Cygwin环境下运行的结果：

这下你总算信了吧！运行过程中，内存重排序大约每6600次检测到一次。当我在Core 2 Duo E6300、Ubuntu 环境下测试时，出现的概率甚至更低。你已经开始意识到， bugs在未被发现的情况下蔓延到lock-free代码中。现在，你可能在想：“我不需要这该死的reording”。OK，至少有两种方法。
一种是将两个线程绑定到同一个CPU core上，pthread并未提供相应的结构，但linux上可以这样做：

   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);

这样一来，重排序消失了。因为单个处理器上是保序的，哪怕线程在任意时候被抢占并重新调度。当然，将两个线程绑定到一个核上，致使其它CPU Core未被有效利用(由此看来，这并不是个好办法)。
我在Playstation 3上编译、运行，并未检测到内存重排。这表明（但不确认）PPU内的两个硬件线程可能会有效地作为单个处理器，具有非常细粒度的硬件调度。

采用StoreLoad Barrier避免memory reordering

另一种避免memory reordering的方法是：在两条指令间引入CPU屏障(CPU Barrier)。本例中，我们要阻止Store和随后的Load指令发生重排，引入的CPU Barrier通常称为StoreLoad Barrier。

在X86/X64处理器上，没有专门的StoreLoad barrier指令，但有一些指令可完成另丰富的功能。Mfence指令为full memory barrier指令，它可以避免任何情况的内存重排。GCC中的实现方式如下：

   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
   }

查看编译生成的汇编代码来验证效果：

    ...
    mov    DWORD PTR _X, 1
    mfence
    mov    eax, DWORD PTR _Y
    mov    DWORD PTR _r1, eax
    ...

修改后，内存重排消失了， 两个线程可运行在两个不同的CPU cores上。

类似的指令和不同的平台

其实，mfence不是x86/x64下唯一的full memory barrier。在这些处理器上，任何locked指令，如xchg均属于full memory barrier - 只要您不使用SSE指令或write-combined memory，像本示例一样。实际上，如果你使用MemoryBarrier指令时，Microsoft C++编译器会生成xchg指令(至少VS2008如此)。

Mfence指令适用于x86/x64，如果想编写可移植的代码，可以采用预处理宏技术。Linux内核提供了一组宏：smp_mb、smp_rmb、smp_wmb，并提供了一组实现alternate implementations on different architectures. 如在PowerPC上，smp_mb被实现为sync.

不同的CPU家族有其自己的memory ordering指令集，编译器根据自身喜好提供此类功能，而跨平台项目则为此封装自己的抽象层...而这些对简化lock-free编程毫无益处。这也是为何C++11引入C++11 atomic library标准的原因，标准化、更为方便的编写lock-free的可移植代码。

译注：

1. Memory Reordering准确的理解应该是和Memory相关的机器指令的重排序。
2. Memory Reordering将其认定同类的或访问相同内存的CPU指令尽可能的放到一起执行。
3. Memory Reording的原则在于：重排前后，单个线程上的行为保持一致，前述例子中，每个程序单独运行时其结果是一致的，也可以理解为“保序”。
4. 在编写多线程程序时，我们通常通过添加mutex、semaphores 等方式执行并发保护，而非lock-free程序。这类锁按本文的描述均属于full memory barrier，程序当然不会出现memory reordering问题。