如何理解 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以外的顺序关系。