今天上午的分布式系统课程内容中包含了可线性化（Linearizability）和序列一致（Sequential Consistent）的内容，不知不觉联想到了 C++11 中新引入的六种 memory order。我又阅读了若干文章和文献（文章和文献来源主要是知乎 / Stack Overflow / 相关论文等）加深了一下对 memory order 的理解。我将在这篇文章中谈一谈 C++ 的 memory order 相关内容。

本文的逻辑结构是这样的：

首先我会在第一节中给出 C++ memory order 需要解决的问题，以及相关的背景知识；
接着我会在第二节中给出 C++ 标准中对 memory order 的定义和解释，以及实现 memory order 的方法；
最后我会在第三节中对本文所有内容进行简单的总结。

C++ Abstract Machine, Thread of Execution and Memory Order

所有的高级通用程序语言都是基于特定的 abstract machine（抽象机）进行定义的。可以将 abstract machine 想象为可以直接执行对应的语言的源代码的通用计算机。从 abstract machine 的角度来说，编译器的任务则是将语言源代码翻译为一组真实的计算机能够识别并执行的指令序列，这组指令序列能够在真实的计算机上模拟出当 abstract machine 直接执行源代码时的行为。程序语言的设计关注 abstract machine 的行为，程序语言的实现则关注语言编译器和运行时支持库的行为。

C++11 标准为 C++ abstract machine 引入了 thread of execution（ToE）的概念。C++ abstract machine 的 ToE 的概念与我们熟知的真实计算机的线程的概念几乎完全一致：一个 ToE 是一个能够独立于其他 ToE 而进行的程序控制流，并且同一个程序的所有 ToE 有访问程序中所有对象的能力。

C++ 是除 C 外最靠近硬件的高级程序语言。因此，C++ 的 abstract machine 并没有完全屏蔽底层实现上需要考虑的细节。Memory order 便是一个因为底层硬件限制而引入到 C++ abstract machine 的一个特性。为了理解 memory order 的设计动机，我们不妨先看一个例子：

// Both a and b are initialized to 0.
int a;
int b;

// Thread 1
b = 10;
a = 1;

// Thread 2
while (a != 1)
  ; // Wait until a becomes 1
int c = b;
printf("%d\n", c);

在上述的例子中，程序中包含两个全局变量 a 和 b，可以同时被两个线程所访问；线程 1 首先将 b 置为 10，然后将 a 置为 1；线程 2 在一个“自旋锁”中等待 a == 1 这个条件为真，然后读出 b 的值并输出。请大家思考两个问题：

线程 2 中的自旋锁能否退出？
如果线程 2 中的自旋锁确实退出，那么线程 2 输出的值是否为 10？

对于第一个问题（其实第一个问题与 memory order 关系不大，仅为了完整性而补充），有两个因素决定了其答案：

编译器是否为 a 在线程 2 的本地分配了寄存器。如果编译器决定为 a 在线程 2 的本地分配寄存器，那么如果线程 2 早于线程 1 中对 a 的赋值开始执行，那么线程 2 将陷入死循环；
假设编译器没有为 a 在线程 2 的本地分配寄存器，那么线程 2 是否能够读到线程 1 写入的值。这个问题看起来比较愚蠢，但是其实涉及到计算机存储器的设计。已有的所有的存储器设计均可以保证，线程 2 最终可以读到线程 1 写入的值。注意“最终”这个词，这个词意味着从线程 1 写入 a 完毕开始到线程 2 读到被线程 1 写入的 a 的值为止，这段时间可能是可以观测到的。即从线程 2 的角度来看，线程 1 对 a 的写入不是立即可见的，可能会有一定的延迟。

第二个看起来更加愚蠢的问题则与 memory order 的设计动机紧密相关。在线程 2 退出自旋锁后，线程 2 紧接着读取 b 的值，读到的值难道会不为 10 吗？其实这是完全有可能的。原因有如下几点：

编译器可能会重排线程 1 中的两条语句，使得线程 1 首先对 a 赋值，然后再对 b 赋值。如果此时线程 2 在线程 1 对 b 赋值前运行，则线程 2 输出的 b 的值将是 b 的初始值；
CPU 乱序执行可能会重排线程 1 中的两次写操作，然后以与上一条同样的原理使线程 2 读到错误的值；
编译器和 CPU 乱序执行都可能会重排线程 2 中的语句，使得对 b 的读取操作早于 while 循环发生；
存储器在硬件设计上导致了线程 1 看到的内存操作顺序和线程 2 看到的内存操作顺序不同。线程 1 看到的自己的内存操作顺序是 b=10 然后 a=1，但线程 2 看到的线程 1 的内存操作顺序是 a=1 然后 b=10。

那么如何保证线程 2 在退出自旋锁后一定会输出 10？这时就需要 memory order 的帮助了。

Memory Order

Atomic Operations

在正式介绍 memory order 前，我们还需要补充一些 C++11 引入的原子操作的相关内容，因为 memory order 与原子操作紧密相关。我们仔细观察在上一节中介绍的例子，可以发现两个线程是在利用变量 a 进行线程同步（Synchronization）的操作。C++11 规定，线程同步只有两种方式：通过原子变量进行同步、通过锁（Mutex）进行同步。我们称读写原子变量、获取释放锁等操作为同步操作（Synchronization Operations）。因此，我们不妨首先对上一节中的例子进行改造，改造的方式是将 a 重新定义为原子变量：

std::atomic<int> a;
int b;

// Thread 1
b = 10;
a.store(1);

// Thread 2
while (a.load() != 1)
  ; // Wait until a becomes 1
printf("%d\n", b);

将 a 改造成原子变量后，我们解决了第一节中的第一个问题，即此时线程 2 将一定会退出自旋锁。第二个问题则需要在我们理解 memory order 后才能解决。

Memory Order

Memory order 最根本的设计动机是规定一个线程中的写操作何时能够被其他线程看见。注意这里的用词是“写操作”而不是“原子写操作”。仔细研究该定义，由于 memory order 涉及到多个线程，因此 memory order 是围绕一些关键的 线程同步节点 进行定义的，这些关键的线程同步节点就是原子访问操作以及获取释放锁操作。具体地来说，memory order 以不同的粒度规定了，如果线程 A 和线程 B 通过某个原子变量或者锁建立了线程同步关系，那么其中一个线程在线程同步节点之前的全部或某些写操作必须能够被另一个线程在线程同步节点之后的读操作看到。这里的“粒度”是指线程同步节点之前的写操作 有多少 能够被其他线程看到，以及线程同步节点之后的读操作 能够看到多少 其他线程写入的值。

以上一节中的例子为例。我们在线程 1 中有一个原子写操作，在线程 2 中有一个原子读操作。这两个操作都是线程同步节点，且是对同一个原子变量的操作，因此线程 1 和线程 2 建立了线程同步关系。我们希望分别为这两个原子操作指派一个 memory order，使得：

对于线程 1，我希望在对 a 的原子写操作结束后，在源程序中排在对 a 赋值之前的对 b 的（非原子）写操作能保证被线程 2 所看到；
对于线程 2，我希望在对 a 的原子读操作结束且发现读到的值为线程 1 写入的值之后，我能够看到线程 1 在写入 a 之前的写操作。也就是说，我希望能够看到 b 确实被线程 1 写入了 10，即线程 2 确实能输出 10。

按照粒度和原子操作类型（读或写）进行划分，C++11 规定了六种不同的 memory order，定义在 std::memory_order 枚举中：

Relaxed，定义为 std::memory_order_relaxed；
Consume，定义为 std::memory_order_consume；
Acquire，定义为 std::memory_order_acquire；
Release，定义为 std::memory_order_release；
Acquire-Release，定义为 std::memory_order_acq_rel；
Sequential Consistent，定义为 std::memory_order_seq_cst。

在执行原子操作时，可以传入一个 std::memory_order 枚举，指明这个原子操作需要满足的 memory order。如果没有传入 std::memory_order，则默认的 memory order 为 Sequential Consistent。例如，上一节中改造后的代码片段中，对 a 的 store 和 load 操作均满足 sequential consistent 这一 memory order。传入 memory order 的具体方式请参见 std::atomic 的文档。

接下来我将分别介绍这六种 memory order。这六种 memory order 按照顺序，限制条件依次增强。为叙述方便，我们不妨简称具有 memory order X 的原子操作为 X 操作。

Relaxed

Relaxed 是最弱的 memory order。事实上，relaxed 应该称为“没有 memory order”：如果某个原子操作使用 relaxed 作为其 memory order，那么这个原子操作将退化为一个单纯的原子操作，不再具有线程同步节点的作用。即：

在一个 relaxed 写操作之前的写操作将不保证能被其他也执行对同一个原子变量的 relaxed 读操作的线程看到；
在一个 relaxed 读操作之后的读操作也不保证能看到其他对同一个原子变量的 relaxed 写操作之前的写操作。

如果我们将前文中的例子中对 a 的 store 和 load 操作均使用 relaxed 作为 memory order，那么线程 1 将不能保证线程 2 能读到在写 a 变量之前对 b 的写入，线程 2 也不能保证在退出自旋锁能够读到线程 1 对 b 写入的值。

需要注意到的是，即使使用 relaxed 这一最弱的 memory order，原子变量的操作仍然是原子操作，这一事实不因 memory order 的改变而改变。因此，relaxed 非常适合于单纯的、不具有线程同步语义的原子操作，例如对引用计数的原子递增或原子递减。

Consume

Consume 这一 memory order 仅对原子读操作有效。Consume 操作规定：

为理解上述定义，我们首先需要理解一个重要概念：什么是“两个操作之间具有数据依赖”？翻看 C++11 标准可知，对于操作 A 和操作 B，如果操作 A 先于操作 B 发生，则有三种情况会使得操作 B 数据依赖于 操作 A：

操作 B 有一个操作数用到了操作 A 的结果；（有特殊情况，参见 C++ 标准或 cppreference）；
操作 A 向某个标量对象 M 写入了值，操作 B 从 M 中读出了值；
存在第三个操作 X 数据依赖于操作 A，操作 B 又数据依赖于操作 X。

因此，在前文的例子中，线程 1 中对 a 的原子写操作并不数据依赖于对 b 的写操作。但是，如果将线程 1 的代码更改为如下形式，则对 a 的原子写操作依赖于对 b 的写操作：

// Thread 1
b = 1;
a.store(b);

在原来的例子中，如果我们令 store 操作为 release 操作、令 load 操作为 consume 操作，则线程 2 将无法保证能够在退出自旋锁后读到线程 1 向 b 写入的值，因为线程 1 中对 a 的原子写并不数据依赖于对 b 的写操作。但是，如果线程 1 的代码如上述修改后所示，即线程 1 中对 a 的原子写数据依赖于对 b 的写操作，那么线程 2 将保证能够读到线程 1 向 b 写入的值。

Acquire

Acquire 这一 memory order 仅对原子读操作有效。Acquire 与 consume 唯一的区别是 acquire 要求线程 B 能够看到线程 A 中在 release 操作之前的所有写操作，而不仅仅是与写原子变量具有数据依赖关系的写操作。因此，如果我们令线程 1 中对 a 的原子写操作为 release 操作、令线程 2 中对 a 的原子读操作为 acquire 操作，则线程 2 将保证读到线程 1 中对 b 写入的值。

Release

Release 这一 memory order 仅对原子写操作有效。Release 操作通常是与 consume 或 acquire 操作配对的。当某个线程执行 release 操作后，其他对同一原子变量执行 consume 或 acquire 操作的线程将以相应的粒度看到该线程 release 操作之前的写操作。

Acquire-Release

在一个原子操作内可能既有读操作也有写操作，例如原子性的 compare-and-swap 操作和原子性的 read-modify-write 操作。Acquire-Release 这一 memory order 则指明了这样的原子操作将既是一个 acquire 操作、也是一个 release 操作。

Sequential Consistent

Sequential Consistent 是最强的 memory order。这个 memory order 规定：

对于一个原子读操作，该操作都是 acquire 操作；
对于一个原子写操作，该操作是 release 操作；
对于一个既有读又有写的原子操作，该操作既是 acquire 操作也是 release 操作；
程序内所有线程在使用 sequential consistent 这一 memory order 操作原子变量时，必须以一致的顺序看到程序内的所有 sequential consistent 操作。

前面三点与 acquire-release 基本一致，因此我们重点关注最后一点。考虑如下的示例程序：

std::atomic<int> x;
std::atomic<int> y;
std::atomic<int> z;

constexpr static const auto seq_cst = std::memory_order_seq_cst;
constexpr static const auto relaxed = std::memory_order_relaxed;

int main() {
  std::thread a([]() { x.store(1, seq_cst); });
  std::thread b([]() { y.store(1, seq_cst); });
  std::thread c([]() {
    while (x.load(seq_cst) != 1)
      ; // Wait while x becomes 1
    if (y.load(seq_cst) == 1) {
      z.fetch_add(1, relaxed);
    }
  });
  std::thread d([]() {
    while (y.load(seq_cst) != 1)
      ; // Wait while y becomes 1
    if (x.load(seq_cst) == 1) {
      z.fetch_add(1, relaxed);
    }
  });

  a.join();
  b.join();
  c.join();
  d.join();

  // Can this assertion fail?
  assert(z.load(relaxed) != 0);

  return 0;
}

上述示例程序启动了四个线程，分别进行如下的工作：

线程 a 使用 sequential consistent 这一 memory order 向 x 中原子写入值 1；
线程 b 使用 sequential consistent 这一 memory order 向 y 中原子写入值 1；
线程 c 首先自旋等待 x 被置为 1，然后检查 y 的值；若 y 也被置为 1，则递增 z 计数器；
线程 d 首先自旋等待 y 被置为 1，然后检查 x 的值；若 x 也被置为 1，则递增 z 计数器。

请思考：main 函数中的 assert 是否会失败？

显然，要让 assert 失败，则线程 c 和线程 d 中的两个 if 条件必须同时为假才行。而导致这样的情形出现只能有一种情况：线程 c 和线程 d 以不同的顺序观察到了其他线程向 x 和 y 的写操作。对于线程 c，观察到的顺序是 x=1 然后 y=1；对于线程 d，观察到的顺序是 y=1 然后 x=1。

Sequential consistent 的作用则在这个例子中体现出来了。同一个程序中，所有的线程在执行 sequential consistent 操作时，各个线程将观察到一致的 sequential consistent 操作顺序。上面所说的情况则不会存在：不会有一个线程观察到的操作顺序是 x=1 然后 y=1，而另一个线程观察到的操作顺序是 y=1 然后 x=1。因此，在上述的示例程序中， main 函数中的 assert 检查将永不失败。

Implementation

在上一节中我们介绍了 memory order 在设计层面的的定义和解释。在这一节中，我们将充当语言实现者的角色，考虑如何在编译器中实现 memory order。我们暂且只考虑如何在 x86_64 平台上实现 memory order。

总的来说，在实现的角度看，memory order 对编译器提出了如下的限制：

编译器将无法像之前一样“自由地”重新排布程序中的操作；
编译器需要利用硬件支持（如 fence 指令、 lock 指令前缀等）让 memory order 的条件得到满足。

Relaxed

由于 relaxed 操作本质上是一个没有线程同步功能的原子操作，因此编译器生成 relaxed 操作的方法非常简单。事实上，在 x86_64 平台上，对于以 relaxed memory order 原子读写一个标量类型，编译器只需要生成一个简单的内存读写指令即可。例如：

std::atomic<int> a;
a.store(1, std::memory_order_relaxed);

编译器将生成：

mov DWORD PTR a[rip], 1

这是因为 x86_64 平台上对标量类型的内存读写本身便是一个原子操作。

Consume

对于 relaxed 以外的 memory order，编译器需要保证在线程同步节点之后的操作能够看到其他线程在线程同步节点之前的某些写操作。编译器主要是依靠限制线程同步节点前后的代码重排来保证这一点的。

在 consume 操作中，处在 consume 操作后的、与 consume 操作具有数据依赖关系的读操作必须能够看到另一个线程在相同原子变量上执行 release 操作之前的、与 release 操作具有数据依赖关系的写操作。因此，编译器必须按照如下方式限制 consume 操作和 release 操作附近的代码重排：

在 release 操作附近，所有的在 release 操作之前的、与 release 操作具有数据依赖关系的写操作不能被移动到 release 操作之后；
在 consume 操作附近，所有的在 consume 操作之后的、与 consume 操作具有数据依赖关系的读操作不能被移动到 consume 操作之后。

在真实的实现中，consume 这一操作只会影响到进行代码重排的编译优化，而不会让编译器生成某种特定的代码。

Acquire

在 acquire 操作中，处在 acquire 操作后的所有读操作必须能够看到另一个线程在相同原子变量上执行 release 操作之前的所有写操作。因此，编译器必须按照如下方式限制 acquire 操作和 release 操作附近的代码重排：

在 release 操作附近，所有的在 release 操作之前的写操作不能被移动到 release 操作之后；
在 acquire 操作附近，所有的在 acquire 操作之后的读操作不能被移动到 acquire 操作之前。

与 consume 操作相同，在真实的实现中，acquire 这一操作只会影响到代码重排的编译优化，而不会让编译器生成某种特定的代码。

Release

Release 操作对编译器的影响已经在 consume 和 acquire 操作中进行了说明。在实际的实现中，编译器不会去分析 release 操作之前的、与 release 操作具有数据依赖的操作，而是直接限制所有在 release 操作之前的写操作均不能被移动到 release 操作之后。这样便可以使 release 操作同时满足 consume 和 acquire 操作的要求。

Acquire-Release

Acquire-release 操作既是一个 acquire 操作、也是一个 release 操作。因此它对编译器的影响是 acquire 操作和 release 操作对编译器的影响的叠加：

在 acquire-release 操作附近，所有的在 acquire-release 操作之前的写操作不能被移动到 acquire-release 操作之后；
在 acquire-release 操作附近，所有的在 acquire-release 操作之后的读操作不能被移动到 acquire-release 操作之前。

Sequential Consistent

Sequential consistent 比较特殊，因为它还限制了所有的线程以一致的顺序看到程序内所有的 sequential consistent 操作。在 x86_64 平台上，需要分三种情况讨论 sequential consistent 操作的实现：

原子读操作；
原子写操作；
原子读写操作（例如 compare-and-swap、read-modify-write 等）。

对于原子写操作，如果直接生成一个简单的内存写指令，虽然能够保证原子性，但无法保证多个线程以相同的顺序观察到所有操作；因此在实际实现中，编译器一般生成 xchg 指令。翻阅 Intel 手册可知，在执行 xchg 指令时，如果指令的一个操作数是内存操作数，那么处理器内部的 LOCK# 信号将自动被拉起。因此 xchg 等效于一个带 lock 前缀的内存写指令。

对于原子读写操作，编译器则始终生成带 lock 前缀的操作指令，例如：

std::atomic<int> a;
a.fetch_add(1, std::memory_order_seq_cst);

将导致编译器生成：

lock add DWORD PTR [rip + a], 1

在 x86_64 平台上，LOCK# 信号将确保当前执行的指令的所有操作是原子性的，且所有的带有 lock 前缀的指令的执行结果以一个一致的顺序被所有的核心所看见，从而实现了 sequential consistent 的要求。

Conclusion

本文详细介绍了 C++11 引入的 memory order。具体介绍了如下内容：

Memory order 的设计动机是规定一个线程的写操作何时能够被其他线程所看见；
六种 memory order 在 C++ 标准中的定义和解释；
在 x86_64 平台上的主流编译器如何实现 memory order。编译器主要依靠限制原子操作附近的代码重排以及利用硬件特性来确保 memory order 的准确实现。

理解 C++ 的六种 Memory Order

C++ Abstract Machine, Thread of Execution and Memory Order

Memory Order

Atomic Operations

Memory Order

Relaxed

Consume

Acquire

Release

Acquire-Release

Sequential Consistent

Implementation

Relaxed

Consume

Acquire

Release

Acquire-Release

Sequential Consistent

Conclusion

发表回复取消回复

理解 C++ 的六种 Memory Order

C++ Abstract Machine, Thread of Execution and Memory Order

Memory Order

Atomic Operations

Memory Order

Relaxed

Consume

Acquire

Release

Acquire-Release

Sequential Consistent

Implementation

Relaxed

Consume

Acquire

Release

Acquire-Release

Sequential Consistent

Conclusion

发表回复 取消回复

发表回复取消回复