箱猫日和

如何理解 C++11 原子变量（Atomic）的 Memory Order

最近几天在学习Rust，把Rust官网附带的The Rust Programming Language看完，开始尝试用Rust实现自己学习过的并发数据结构。首先碰到的问题是，如何理解Rust所基于的LLVM的atomics模型。因为LLVM的原子变量模型基本可以对应于C++11开始的原子变量，除了没有consume memory order。所以任务就变成了如何理解C++11的原子变量。

C++原子变量本身并不难理解，但是理解memory order很难。网上找了很多资料，都没有很清晰得解释memory order到底是什么。今天重新看了《C++ Concurrency in Action》关于memory order的部分，对照着 std::memory_order 的介绍，突然明白了这是怎么一回事。

答案是memory order就只是一个order。

这么说有点太简单，具体一点：C++11认为并发程序不能正确执行是因为顺序问题，所以规定了顺序就可以正确执行并发程序。

以那个有名的42与true/false程序为例。

int data = 0;
bool flag = false;

void thread1() {
    data = 42;
    flag = true;
}

void thread2() {
    while (!flag) {
    }
    assert(data == 42);
}

这其实是一个典型的publication的例子，翻译过来就是“发布”，thread1想要发布通过设置flag发布data。

这里的问题是在并发执行下，thread1可能不能正确发布data。原因在于现代CPU所采用的一致性模型。这里不会展开讨论有哪些一致性模型，重点在于

  1. 现代CPU保证单个CPU看到自己的执行顺序和代码的顺序是一致的
  2. CPU之间看到其他CPU的执行顺序和代码的顺序可能不一致

如何理解第二点？原因在于硬件设计。这里有同步代价的考虑。现在CPU利用L1缓存，命令的提前执行，缓存一致性协议等多种技术，虽然能保证单线程程序按照代码顺序执行，但是默认不保证多线程之间的执行顺序关系。

具体来说，并发执行下，thread2有可能看到thread1执行顺序为先写入flag再写入data，当然thread1看到自己肯定是先data再flag。如何理解这种平行世界一样的执行？

可以考虑thread1，thread2所在CPU各自有缓存，thread1把data和flag都写入后，flag先同步到thread2所在CPU的缓存，但是thread2读取自己缓存的data发现是0，过了一段时间，data同步到了thread2的CPU缓存，但是为时已晚。

这里的解决方法不是说保证先data然后flag的顺序同步（BTW，TSO，Total Store Order模型下不会出现这个问题，所以x86下上述程序不会有问题），这是CPU设计者需要考虑的问题。对于程序员来说，需要一种能够保证顺序的手段，即memory order。

如何仔细分析上述程序，可以得到三个依赖关系

  1. thread1: data = 42 -> flag = true
  2. thread1 flag = true -> thread 2 load flag(loop)
  3. thread2: load flag -> load data

注意，第一条和第三条看起来已经满足了，因为单线程下就是按照这种顺序执行，但是现在是多线程，要求thread 1和2都能看到这种顺序。

如何满足上面顺序要求？

首先可以采用sequentially consistent模型。SC模型保证所有线程看到的执行顺序都是一致的，考虑到thread 1和2看到自己的执行顺序就是代码顺序，所以1和3是满足的。加上2实际是一个循环，所有条件都被满足（thread 2一开始可能获取到的flag是false，一定时候后获取到flag为true并推出循环）。

#include <atomic>

std::atomic<int> data;
std::atomic<bool> flag;

void thread1() {
    data.store(42, std::memory_order_seq_cst);
    flag.store(true, std::memory_order_seq_cst);
}

void thread2() {
    while (!flag.load(std::memory_order_seq_cst)) {
    }
    assert(data.load(std::memory_order_seq_cst) == 42);
}

注意现在不要尝试查看上述代码对应的汇编代码，memory order是一个顺序模型，无法直接和汇编代码中的指令对应起来。看了汇编可能只会影响你理解顺序模型，个人经验。

SC是一个比较严格的模型，刚才也提到“保证所有线程看到的顺序都是一致的”。在publication这类程序中，要求是三个偏序关系而不是一种全局（多变量）顺序关系。对此，memory order提供了一种基于同一变量的acquire/release关系。

#include <atomic>

std::atomic<int> data;
std::atomic<bool> flag;

void thread1() {
    data.store(42, std::memory_order_relaxed);
    flag.store(true, std::memory_order_release);
}

void thread2() {
    while (!flag.load(std::memory_order_acquire)) {
    }
    assert(data.load(std::memory_order_relaxed) == 42);
}

上面代码中flag在store时使用了release，在load时使用了acquire。基于同一变量的acquire/release会构成一个 release -> acquire 的偏序关系。这里不是说store执行完成之前，load完全不能执行，这里指的是flag.store之后执行的flag.load会发现flag被设置为true了。再强调一遍，memory order认为顺序问题是并发程序不正确的原因，其中包括thread 2发现不了thread 1设置的值，即可见性问题，所以memory order的模型中要求release写之后的acquire读可以发现写入的值。相对的，假如读先执行，发现不了之后写入的值。

同时，这里还有两个偏序关系（请不要在意relaxed）。data.store -> flag.store，flag.load -> data.load。这是release与之前的读写操作和acquire与之后的读写操作的偏序关系。

https://en.cppreference.com/w/cpp/atomic/memory_order

memory_order_acquire

A load operation with this memory order performs the acquire operation on the affected memory location: no reads or writes in the current thread can be reordered before this load. All writes in other threads that release the same atomic variable are visible in the current thread

memory_order_release

A store operation with this memory order performs the release operation: no reads or writes in the current thread can be reordered after this store. All writes in the current thread are visible in other threads that acquire the same atomic variable (see Release-Acquire ordering below) and writes that carry a dependency into the atomic variable become visible in other threads that consume the same atomic (see Release-Consume ordering below).

基于同一变量的acquire/release是memory order中主要的偏序模型。除去consume其他还有relaxed，acq_rel以及刚才介绍的seq_cst。

relaxed与relaxed并无偏序关系，上面的说明也提到，relaxed与acquire满足acquire后的relaxed不会在acquire前执行（即使是不同变量），relaxed不会在release之后执行。relaxed和acq_rst在代码中是什么顺序，实际执行就是什么顺序。和seq_cst也是一样。

了解了上述顺序关系，再回头来看C++11的原子变量，原子变量的特点是操作是原理。这其实是废话，但是和memory order一起理解时会有困难。load/store可以用acquire/release，那么fetch_add该用什么memory order?

回答是看情况。部分网站说RMW（Read-Modify-Write）操作要用acq_rel，但是我们讨论的是C++11 memory model模型下的原子变量，只要保证了order，不管你用relaxed还是什么，原子变量的操作都不会有可见性问题。

举个例子，std::shared_ptr中增加引用计数时，使用的是fetch_add(relaxed）。这里理论上多个线程可以同时fetch_add，但是因为是原子变量，操作只可能是原子的，所以实际是乱序执行，relaxed这里表示不限制顺序。

同样是std::shared_ptr，在减少引用计数时使用了acq_rel。acq_rel比较好理解。代码顺序上relaxed在acq_rel之前，实际执行时relaxed也在acq_rel之前，也不存在删除的代码被乱序到acq_rel之前执行。即增加引用 -> relaxed -> 减少引用 -> acq_rel -> 删除的偏序关系。

你可能会问，假如开始删除了，此时增加引用会怎么样？对于shared_ptr或者arc来说，这是不可能的。原因是使用场景上限定你只能在还未删除的时候增加引用。

boost在减少引用时使用了release+acquire fence的方法，效果是类似的：增加引用 -> relaxed -> 减少引用 -> release -> acquire -> 删除。

www.boost.org/doc/libs/1_55_0/doc/html/atomic/usage_examples.html

再考虑一个CAS的问题

https://en.cppreference.com/w/cpp/atomic/atomic/compare_exchange

new_node->next = head.load(std::memory_order_relaxed);
while(!head.compare_exchange_weak(new_node->next, new_node,
                                        std::memory_order_release,
                                        std::memory_order_relaxed))

我们只关注这里使用的memory order。compare_exchange_weak有两个memory_order，一个是成功，一个是失败时候的memory order，后者我理解是设置new_node->next最新值时使用的memory order，所以和之前的load应该是同一个。成功时的memory  order这里用了release，可以理解为load操作不能和compare_exchange_weak乱序。如果连续失败，会是relaxed -> release -> relaxed -> release … 的顺序关系。

最后强调一下memory order只是一个order，不要联系到汇编代码，也不要联系到可见性之类问题。原子变量的操作永远是原子的，不管你用什么memory order。以及在撰写并发代码时，先用默认的seq_cst，在厘清顺序关系之后才考虑用seq_cst以外的顺序关系。

xnnyygn