C++ Memory Order

reordering 现象

首先简要介绍下编译器和 CPU 的 reordering 现象。这也被叫做程序的乱序执行。

乱序是指代码的执行过程和代码的书写过程不一样，其中一些指令的顺序会被编译器或 CPU 调整。目的是为了提高程序的运行效率。

编译器的 reordering 优化

典型的就是通过调整指令顺序，在不改变程序语义的前提下，尽可能地减少寄存器的读取、存储次数，充分复用寄存器的存储值

我们知道 C/C++ 源代码会通过编译汇编变成机器码。这里就可能产生 reordering 现象。例如：

假设有 3 条指令：

  1. 计算变量 A 和 B 的值，并把结果 C 保存到寄存器 ax 中
  2. 指令需要用到 ax 寄存器，因此把 C 从 ax 中取出另存
  3. 指令使用 C 的值且与第二条指令无关

按照上面描述的，如果不进行 reordering 优化，程序的执行顺序是这样：C 在第一条指令被执行过后存入寄存器 ax；在第二条指令执行时 C 不再存在于 ax 中；第三条指令执行时 C 被重新读入寄存器 ax 中。

而如果按照乱序执行呢？就可以出现这样的情况：C 在第一条指令被执行过后存入寄存器 ax；由于第二条指令与第三条指令不想关，因此先执行第三条指令，再执行第二条指令，这样就少了一次寄存器 ax 的读写操作，降低了重复读取的开销。

CPU 的乱序执行优化

当 C/C++ 源码编译汇编成机器码后，CPU 取机器码的顺序也可能是乱序的！也就是说，如果有两个线程 A 和 B，这两个线程执行同一份代码的指令顺序都可能不同，甚至于同一个线程，多次运行同一段代码，每次执行的指令顺序都可能不同，这就是 CPU 层面的 reordering 导致的。为什么呢？

CPU 的执行原理

现在的 CPU 采用流水线来执行指令。一条指令的执行被分为：取指、译码、访存、执行、写回等若干个阶段（具体可以看 [CSAPP]）。多条指令可以同时存在于流水线中，同时被执行。特别是，当代 CPU 的 IPC （每时钟执行指令数）一般都远大于 1，也就是所谓的多发射，很多命令都是并行执行的。比如，当代 CPU 当中（一个核心）一般会有 2 套以上的整数 ALU（加法器），2 套以上的浮点 ALU（加法器），往往还有独立的乘法器，以及，独立的 Load 和 Store 执行器。Load 和 Store 模块往往还有 8 个以上的队列，也就是可以同时进行 8 个以上内存地址（cache line）的读写交换。

例如现在有 3 条指令：

1
2
3
a++;
b = f(a); //不是指函数，而仅仅是指 b 依赖于 a；函数要更加复杂，函数会由更多条指令构成；
c++

那么可以画出它们的流水线：

由于 b = f(a) 这条指令依赖于前面 a++ 这条指令的执行结果，所以 b = f(a) 将在执行阶段被阻塞，直到 a++ 写回阶段结束才能继续，这样就多出了空等时间。但是 c++ 是不依赖于前面两天指令的，如果把 c++ 移到第二条指令处，是不是可以先去执行 c++ 而不用阻塞 b = f(a) 指令了，这提高了程序的执行效率。

除此之外，由于现在是多核时代，每个核一般都有自己独立的 L1 Cache 和 L2 Cache 以及多核共享的 L3 Cache。一个线程在代码中对多个变量的一次修改，可能会以不同的次序同步到另一个线程所在的核心上。不同线程对数据的需求不同，按需同步也会导致 CacheLine 的读序和写序不同。

如果其中第一个变量扮演了开关的作用，控制对后续变量的访问。那么当这些变量被一起同步到其他核心时，更新顺序可能变了，第一个变量未必是第一个更新的，然而其他线程还认为它代表着其他变量有效，去访问了实际已被删除的变量，从而导致未定义的行为。比如下面的代码片段：

1
2
3
4
5
6
7
8
9
// Thread 1
// ready was initialized to false
p.init();
ready = true;

// Thread2
if (ready) {
    p.bar();
}

从人的角度，这是对的，因为线程 2 在 ready 为 true 时才会访问 p，按线程 1 的逻辑，此时 p 应该初始化好了。但对多核机器而言，这段代码可能难以正常运行：

  • 线程 1 中的 ready = true 可能会被编译器或 cpu 重排到 p.init() 之前，从而使线程 2 看到 ready 为 true 时，p 仍然未初始化。这种情况同样也会在线程 2 中发生，p.bar() 中的一些代码可能被重排到检查 ready 之前
  • 即使没有重排，ready 和 p 的值也会独立地同步到线程 2 所在核心的 cache，线程 2 仍然可能在看到 ready 为 true 时看到未初始化的 p

六种内存序

C++ 有六种内存序：

std::memory_order 定义于头文件 

1
2
3
4
5
6
7
8
typedef enum memory_order {
    memory_order_relaxed,
    memory_order_consume,
    memory_order_acquire,
    memory_order_release,
    memory_order_acq_rel,
    memory_order_seq_cst
} memory_order;

可以分为四大类：

  1. 宽松顺序
  2. 释放获得顺序
  3. 释放消费顺序
  4. 序列一致顺序

下面详细介绍下这四大类。

宽松顺序 (Relaxed Ordering)

带标签 memory_order_relaxed 的原子操作无同步操作；它们不会在共时的内存访问间强加顺序。它们只保证原子性和修改顺序一致性。

1
2
3
4
5
6
7
8
std::atomic<int> x = 0; // global variable
std::atomic<int> y = 0; // global variable
// thread 1:
r1 = y.load(std::memory_order_relaxed); // A
x.store(r1, std::memory_order_relaxed); // B
// thread 2:
r2 = x.load(std::memory_order_relaxed); // C 
y.store(42, std::memory_order_relaxed); // D

之前在对 reordering 现象的介绍中已经说了，那些没有相互依赖的指令可能会被编译器或（和）CPU reorder。那么看上面的代码，thread 1 中 A 和 B 相互依赖并且是原子的，对的，有时候load和store都需要原子地进行，例如：

1
2
3
4
5
6
int64_t i = 0; // global variable

//Thread-1:
i = 100;
//Thread-2:
std::cout << i;

C++ 并不保证 i = 100 是原子操作，因为在某些 CPU Architecture 中，写入 int64_t 需要两个 CPU 指令，所以 Thread-2 可能会读取到 i 在赋值过程的中间状态。

继续话题。因此 A 和 B 必定按照代码书写的顺序执行。再看 C 和 D，它们是原子的但是并不相互依赖，所以编译器或 CPU 可能对它们进行 reorder，这里加的标签是 memory_order_relaxed，它只保证原子性和修改顺序一致性，不保证同步操作。因此执行完上面的程序，可能出现r1 == r2 == 42。理解这一点并不难，因为编译器允许调整 C 和 D 的执行顺序。如果程序的执行顺序是 D -> A -> B -> C，那么就会出现r1 == r2 == 42。

总结：对于 memory_order_relaxed 来说，无关系依赖的指令仍旧有可能被编译器或 CPU reorder！

释放获得顺序 (Release-Acquire Ordering)

若线程 A 中的一个原子存储带标签 memory_order_release ，而线程 B 中来自同一变量的原子加载带标签 memory_order_acquire ，则从线程 A 的视角先发生于原子存储的所有内存写入（非原子及宽松原子的），在线程 B 中成为可见副效应，即一旦原子加载完成，则保证线程 B 能观察到线程 A 写入内存的所有内容。

什么意思呢？

  1. 首先 store() 是使用标签 memory_order_release 的，而 load() 是使用标签 memory_order_acquire 的，这其实是遵循先 release 再 acquire（即先写再读）的规则
  2. 可见副效应是指，在 B 线程中原子加载后面的指令，它们能看到 A 线程在执行完原子存储后对内存产生的所有变化，这是什么意思？难道原来不加 release-acquire 标签就看不到吗？是的，可能由于 reorder 导致原先在 A 线程原子存储前的指令被换到了原子存储后，这样线程 B 就看不到本应看到的内存变化了。
  3. 注意第 2 条说的B 线程中原子加载后面的指令，也就是说 B 线程原子加载后面的指令也不能被 reorder 到原子加载前面，因为如果有指令被移到了前面，那该条指令就看不到 A 线程对内存产生的变化了。

总结：在这种模型下，store() 使用 memory_order_release，而 load() 使用 memory_order_acquire。这种模型有两种效果，第一种是可以限制 CPU 指令的重排:

  • 在 store() 之前的所有读写操作，不允许被移动到这个 store() 的后面。
  • 在 load() 之后的所有读写操作，不允许被移动到这个 load() 的前面。

看下面的例子：

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
#include <thread>
#include <atomic>
#include <cassert>
#include <string>
 
std::atomic<std::string*> ptr;
int data;
 
void producer()
{
    std::string* p  = new std::string("Hello");             // A
    data = 42;                                              // B
    ptr.store(p, std::memory_order_release);                // C
}
 
void consumer()
{
    std::string* p2;
    while (!(p2 = ptr.load(std::memory_order_acquire)))     // D
        ;
    assert(*p2 == "Hello"); // 绝无问题                      // E
    assert(data == 42); // 绝无问题                          // F
}
 
int main()
{
    std::thread t1(producer);
    std::thread t2(consumer);
    t1.join(); t2.join();
}

让我们分析下整个过程：

  • 这是 Release-Acquire Ordering
  • A B 不允许移到 C 后面，E F 不允许被移到 D 前面
  • while 循环直到 C 执行完后才会出循环，而一旦 C 执行完了，那么 data = 42，*ptr = “Hello” 是肯定的了
  • 因此 E 和 F 的 assert 必定为真

注意：虽然 Release-Acquire Ordering 规定 store 前的指令不能移到 store 后面，但是 store 前的可以被 reorder！也就是 A 和 B 可能会乱序执行（虽然在这里好像没什么必要这么做）

释放消费顺序 (Release-Consume Ordering)

若线程 A 中的原子存储带标签 memory_order_release 而线程 B 中来自同一对象的读取存储值的原子加载带标签 memory_order_consume ，则线程 A 视角中先发生于原子存储的所有内存写入（非原子和宽松原子的），会在线程 B 中该加载操作所携带依赖进入的操作中变成可见副效应，即一旦完成原子加载，则保证线程B中，使用从该加载获得的值的运算符和函数，能见到线程 A 写入内存的内容。

这个内存序只是在上面 Release-Acquire Ordering 的内存序的基础上放开了一点约束：携带依赖

也就是说保证那些跟原子加载操作相依赖的指令不会被 reorder 到原子加载前面。

看下面的例子：

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
#include <thread>
#include <atomic>
#include <cassert>
#include <string>
 
std::atomic<std::string*> ptr;
int data;
 
void producer()
{
    std::string* p  = new std::string("Hello");                     // A
    data = 42;                                                      // B
    ptr.store(p, std::memory_order_release);                        // C
}
 
void consumer()
{
    std::string* p2;
    while (!(p2 = ptr.load(std::memory_order_consume)))             // D
        ;
    assert(*p2 == "Hello"); // 绝无出错： *p2 从 ptr 携带依赖         // E
    assert(data == 42); // 可能也可能不会出错： data 不从 ptr 携带依赖 // F
}
 
int main()
{
    std::thread t1(producer);
    std::thread t2(consumer);
    t1.join(); t2.join();
}

让我们分析一下：

  • 这是 Release-Consume Ordering
  • store 前面的保证不会出现在 store 后面，因此 A B 必定在 C 前面（但 A B 还是 B A 就不知道了）
  • load 后面与 ptr 相依赖的指令不会出现在 load 前面，因此 E（*p2 依赖 ptr） 必定在 store 后面，而 F 可能出现在 D 前面

序列一致顺序 (Sequential Consistency Ordering)

带标签 memory_order_seq_cst 的原子操作不仅以与 Release-Acquire Ordering 相同的方式排序内存（在一个线程中先发生于存储的任何结果都变成进行加载的线程中的可见副效应），还对所有带此标签的内存操作建立单独全序。

这句话的前半句只要理解了 Release-Acquire Ordering 就明白了，就是说的 store 前的指令不允许出现在 store 后，load 后的指令不允许出现在 load 前；而后半句表示所有使用 seq_cst 的指令有严格的全序关系

brpc 对这个也做了不错的介绍！

参考

  1. 乱序执行 cnblog
  2. cppreference
  3. brpc
  4. 知乎
  5. http://senlinzhan.github.io/2017/12/04/cpp-memory-order/