时间: 2020-09-03 00:08:26 人气: 2305 评论: 0
关键词：内存模型, Memory Model, Memory Ordering, Memory Consistency
seeing things in order 是 Computer Science 中一个很棘手的问题，no matter in distributed systems or in multicore CPUs. 对于后者，定义一套明确的 Memory Model 有助于解决这个问题。如果想要实现 lock-free 队列，理解内存模型也是一个必须跨过的门槛。文尾简单介绍了一下内存模型在 C++11 中的支持。
现代 CPU 是由多核(Core)、多级缓存(Cache)结构组成的，如下图：
CPU 的每个 Core 可以有自己独立的 L1、L2 Cache(容量小速度快)，以及共享的 L3 缓存(容量大速度慢)。每个 Core 还有紧密集成在 core 内的 on-core buffer，是比 L1 速度更快的缓存。Main Memory(主存) 是例如我们在某宝买的笔记本内存条，相对于 L3 来说，它的容量更大，但是存取速度更慢。
Cache 的概念这里就不详细介绍了，大体意思是：例如 Core 1 写 一个全局变量 g = 某值 (称为 STORE 操作：把 CPU 寄存器中的值 store 到内存地址 &g中)，该值会首先被写到 on-core buffer 中，再被刷到 L1 中，再被刷到 L2 中，再被刷到 L3 中，最后被刷到 Main Memory 中，这一过程需要花费的时间根据不同的硬件架构和不同的缓存控制算法、映射方法而不同。
如果 Core 2 要 读 该全局变量 g (称为 LOAD 操作：把内存地址 &g 中的值 load 到 CPU 寄存器中)，则首先检查 on-core buffer 中有没有它的拷贝，如果没有，则再看 L1 中有没有它的拷贝；如果 L1 没有，则去 L2 中找；如果 L2 中没有，则再去 L3 去找；如果 L3 中没有，则最后去 Main Memory 中找；而一旦这条路打通了，伴随着也建立了一连串从主存到 on-core buffer 的映射关系，则下次读 g 时，如果没有人修改过 g，那只需要从离 Core 最近的存储位置读取就可以了。
那么，从 Core 1 对 g 写的值最终反映到 Core 2 读到该值，其中涉及到的一系列复杂的问题，称为 缓存一致性(Cache Coherence/Cache Consistency) 问题。
Cache Consistency 是操作系统需要操心的问题，在应用层，我们并不能控制 Core 1 写 g 以后，明确要求在 Core 2 必须读到 g 的最新值。
而 Memory Consistency(内存一致性) 是应用层需要操心的问题：
在了解 "内存一致性" 之前，我们先看一个 "内存不一致" 的例子：
上面的代码打印的结果可能是 (0,0), (2,1), (0,1), 甚至有可能是 (2,0)。这取决于 A 和 B 所在缓存的位置，和 S1 和 S2 执行的相对时间。
其中 (2,0) 的结果是最反直觉的：因为 B 是在 A 之前打印的，而 A 是在 B 之前写的，如果 B 已经被反映是 2，那 A 一定是 1 才对啊？但实际中复杂的多级缓存结构足以让 (2,0) 这一打印结果成为事实。这种问题就称为 Memory Consistency 问题：即如何保证写在前面的指令的执行效果一定最先被反映出来，如何保证写在后面的指令的执行效果一定最后被反映出来。应用层正是通过 memory_order 来控制这种 相对关系 的。
重点(1)——注意到上面提到了 Core 1 执行的代码段 S1，和 Core 2 执行的代码段 S2，反映在应用层可以认为是两个线程，分别跑在 Core 1 和 Core 2 上面。因此 memory order 的概念和多线程/并发是紧密联系的。两个线程就像两个人一样，他们看待这个世界(主存)的角度是不同的，因此得到的结论也可能是不同的，但并不是说有一个人是错的。他们都是对的，他们也都是错的。
重点(2)——并且留意到，上面 Core 1 和 Core 2 使用到了相同的内存位置 &A, &B，也就说，只有多个线程之间操作共享数据(例如全局变量 A,B)才会引起 memory ordering 的问题。
重点(3)——对一个内存地址的操作无非只有两种：读(Load)和写(Store)。把这两个操作组合起来，例如上例 Core 1 的操作是 先写A，再写B，称为 STORE-STORE(SS) 操作。类似的还有 STORE-LOAD(SL), LOAD-LOAD(LL), LOAD-STORE(LS) 操作，这四种组合也对应着 四种乱序(LL,LS,SS,SL)，可能使得实际执行效果和"预期"(代码书写和执行)的顺序正好相反：
store 1 to [X]; load [Y] into %r1;，其中 [X] 表示变量 X 的内存地址，[Y] 表示变量 Y 的内存地址。最后执行的效果，完全有可能变量 Y 中的值首先被加载到了寄存器 %r1 中，过了N个CPU Cycle 后数值1才被写入变量 X 中。这种LL,LS,SS,SL都会发生乱序的现象也被称为 Memory Reordering。X = 1; r1 = Y; 编译后的机器指令，可能变成了和 r1 = Y; X = 1;等价！这一现象被称为 Compiler ReorderingC/C++ 语言最终是被编译成机器语言来交给 CPU 执行的，在机器指令级别，实现 memory_order 控制的机器指令就是 Memory Barriers，或者称为 Fences。
根据上文提到的 Load，Store 组成的排列组合一共只有 4 种情况，那么 memory barriers 也有四种：
举一个例子，例如 Core 1 的线程 tA 执行下面的代码：
Value = x; // Publish some data STORESTORE_FENCE(); IsPublished = 1; // Set shared flag
Value 是一个多线程共享的变量(内存)，tA 写 Value 的值为 x；写好之后，再写一个共享的 Flag IsPublished 为 1，表示 Value 的内容我已经写好了，其他线程可以读了。
这里的 StoreStore Fence，可以保证 主存 中 Value 的 写 一定是比 Flag 的 写 先发生(become globally visible)的。因此其他线程在读到该 Flag 是 1 后，Value 中的内容一定是被修改之后的值 x。
也就是说，StoreStore Fence 的存在，保证了 代码书写的顺序(也就是代码执行的顺序) 和其 实际发生在主存中的顺序(也就是 become globally visible 的顺序) 是一致的，实现了 所见即所得。如果没有这个 Fence，编译器和 CPU 都有可能做一些非常"疯狂"的事情：各种 reordering。
接上，只要写的时候保证顺序就足够了吗？NO！读的时候也必须保证顺序！假设 Core 2 的线程 tB 执行下面的代码：
if (IsPublished) // Load and check shared flag { LOADLOAD_FENCE(); // Prevent reordering of loads return Value; // Load published value }
这里的 LoadLoad Fence，可以保证 主存 中 Value 的 读 一定是比 Flag 的 读 先 发生 的。
如果不加这个 Fence，有可能先读到了 Value，过了N个CPU Cycle，才读到了 Flag。
同样，可以理解为，Fence 的存在，保证了代码书写的顺序和其实际发生在主存中的顺序是一致的。
LS 的例子后文的 Release-Acquire Semantics 一节
下面是一个稍微复杂但非常经典的例子：
其中 [X] 表示变量 X 的内存地址，[Y] 表示变量 Y 的内存地址。%r1 表示寄存器 r1。
或者和它相同含义的另一种阐述：
上面的代码没有任何 fence 的保护，是有可能出现 (X,Y)=(0,0) 的打印结果的。这是因为前面的 store 和后面的 load 操作在主存中发生的顺序有可能是相反的。
如果加以 StoreLoad Fence，则可以避免 (0,0) 这种结果的出现：
在真实世界的 CPU 中，有些 CPU 天生就能保证所有读写指令执行的顺序和发生在主存的顺序是完全一致的，不需要任何 memory barriers 的保护。这类 CPU 称为 Sequentially Consistent Ordering (所见即所得，代码写的是啥样，执行的结果就是啥样)，其内存模型也称为 the Strongest Memory Model。这种类型的 CPU 现在已经极其少见了。
有些 CPU 天生能保证所有的 LL(LoadLoad)，LS(LoadStore)，SS(StoreStore) 操作一定是按照其执行顺序在主存中产生效果的。但是 SL(StoreLoad) 操作仍然有可能发生 memory reordering。这类 CPU 对应的内存模型也被归为 Strong Memory Model。常见的 x86,x64 架构的 CPU(例如 intel i3,i5,i7) 一般都属于这种类型。
TSO(Total Store Ordering)：一般 Strong Memory Model 都满足 TSO 性质。满足 TSO 的 CPU 天生地能保证 SS 顺序。Total Store Ordering means that there is always a single, global order of writes to shared memory from all cores. 也就是说，CPU 内所有 S 指令严格依据执行时间先后顺序在主存中产生效果。
题外话：为什么 StoreLoad 如此特殊？因为如果要保证 StoreLoad Ordering，是要牺牲很大的 性能 的！为什么这么呢？
原因：Store 相对于 Load 是很慢的
下图更详细地解释了为什么上文的例子会有 (X,Y)=(0,0) 的反直觉结果。
(这个例子隐含了"the target CPU allows StoreLoad memory reordering"的先决条件，这也是符合当前绝大多数 CPU 的情况的。)
The only shared memory between the two cores is all the way back at the L3 cache, which often takes upwards of 90 cycles to access.
With TSO, instruction (2) print(B) could start immediately after putting (1) A=1 into the on-core store buffer, rather than waiting for it to reach the L3 cache. At some time in the future, the cache hierarchy will pull the write from the store buffer and propagate it through the caches so that it becomes visible to other threads.
As we execute (2) print(B) on core 1, which is going to read the value of B. It first inspects its local on-core store buffer, but there's no value of B there, so it reads B from memory and gets the value 0.
而一旦在 (1) A=1 后面放置了 StoreLoad_Fence，则 CPU 在把 (1) A=1 放到 on-core store buffer 后，足足要等到 A=1 被 propagated to the L3 cache，才会继续执行 Load 指令，这可能足足已经过去了 90 个 CPU cycle 了。而如果 CPU 在把 (1) A=1 放到 on-core store buffer 后立马开始执行 Load，则这条 Store 指令相当于只花费了几个 CPU cycle，剩下的事情就交给 cache hierarchy 来做就好了。这是大约十倍的性能差距。
in the Weakest memory model CPU, 四种 memory reordering(LL,LS,SS,SL) 都被允许发生。这种 CPU 的内存顺序也被称为 Relaxed Ordering
还有一些 CPU，(LL,LS,SS,SL) 的顺序都不被保证，但是有一种特殊的 LL 的顺序被保证：例如一个全局指针 int* gptr：
load(gptr); // load gptr if (gptr) { r = *gptr; // load *gptr }
这种 LL 顺序叫做 Data Dependency Ordering，也称为 Consume Ordering。其特殊在于：前面一个 Load 得到的值，是要做后面一个 Load 的地址，也就是说后面一个 Load 是依赖于前面一个 Load 的。
对于 Weakest Memory Model，这种乱序也是被允许的，于是会产生不太好的结果：例如 gptr 的初值是 NULL，第一个 load 加载到了一个非零的 gptr 值，在执行 r = *gptr(第二个 load) 时，该指令中拿到的 gptr 却仍然是 0，因此会引发程序异常。
能够保证 Data Dependency Ordering 的 CPU，其内存模型也称为 Weak Memory Model with Data Dependency Ordering。我们用的安卓、苹果手机的 CPU 一般都是这种模型。
上面介绍的四种 Strong/Weak Memory Model 如下图所示：
上面已经提到了三种 Memory Ordering：
还有两种很常用的 Memory Ordering：
注意看 Acquire Ordering 的定义：LL 和 LS 的内存顺序得到保证。也就是说：如果先执行一个 读(L) 操作，再执行一个任意的内存操作(读(L)或写(S))，内存的先后顺序都会得到保证。
对于 Strong Memory Model，这种特性是被 CPU 天生就保证的。
而对于 Weak Memory Model，想实现这种特性，需要在 L 和 后面的L/S 之间加 Fence 指令，对应的 Fence 指令也叫做 Acquire Semantics Fence，简称 acquire fence。
注意看 Release Ordering 的定义：SS 和 LS 的内存顺序得到保证。也就是说：如果先执行一个任意的内存操作(读(L)或写(S))，再执行一个 写(S) 操作，内存的先后顺序都会得到保证。
对于 Strong Memory Model，这种特性是被 CPU 天生就保证的。
而对于 Weak Memory Medel，想实现这种特性，需要在 S 和 前面的L/S 之间加 Fence 指令，对应的 Fence 指令也叫做 Release Semantics Fence，简称 release fence。
同时再强调一点：正如上文 StoreStore Fence 必须和 LoadLoad Fence 成对使用一样，Acquire Fence 和 Release Fence 必须成对使用才有意义。
Release-Acquire Semantics 应用最典型的例子就是 锁/mutex 的实现。
为了实现锁，还需要一种 compare and set 原子操作：int compare_set(&flag)，它首先会读 flag：
并且，这个 compare_set 方法必须是在多个核之间是 同步/synchronized/满足synchronizes-with关系 的，例如两个核同时执行 compare_set 操作，只有一个可以成功。(在 x86/64 CPU 中它对应是一条机器指令 cmpxchg，其 synchronizes-with 特性是被 CPU 保证的)。关于 synchronizes-with 关系 的解释见后文补充。
"In fact, this is where the names come from: acquiring a lock implies acquire semantics, while releasing a lock implies release semantics! All the memory operations in between are contained inside a nice little barrier sandwich, preventing any undesireable memory reordering across the boundaries."
"Here, acquire and release semantics ensure that all modifications made while holding the lock will propagate fully to the next thread that obtains the lock. Every implementation of a lock, even one you roll on your own, should provide these guarantees. Again, it's all about passing information reliably between threads, especially in a multicore or multiprocessor environment."
happens-before 关系，一般指两条指令产生"实际效果"的先后关系：例如 Strong Memory Model CPU 的 LoadLoad, StoreStore, LoadStore 天生的是 happens-before 关系。Weak Memory Model CPU 在指令之间增加 Fences 才能得到 happens-before 关系。
synchronizes-with 关系，一般指两个线程之间的关系：
On x86/64 CPU，实现 mutex 时，只需要防止 compiler reordering，就可以实现 acquire fence 和 release fence 了，这是因为, every load on x86/64 already implies acquire semantics and every store implies release semantics. This is why x86/64 is often said to be strongly ordered. 并且 x86/64 也是天生保证 Data Dependency Ordering 的。
前面介绍了四种 Fences: LL, LS, SS, SL。然而这些都是很理想的情况，真实世界中的 Fence 指令会复杂很多，根据不同的 CPU 而不同。这里只列举两种。
SFENCE: store fence. 既然 x86/64 是 Strong Memory Model，所以 SS 顺序是天然被 CPU 保证的，那么 sfence 指令是多余的吗？一般情况下 sfence 都是多余的，写了和没写一样。但是也有特殊情况，毕竟 x86/64 是支持某些 weakly-ordered store 的(例如 movnt streaming stores)，这时候这个指令会有用，但是非常 rare。LFENCE: load fence. 既然 x86/64 是 Strong Memory Model，所以 LL 顺序是天然被 CPU 保证的，那么 lfence 指令是多余的吗？一般情况下 lfence 都是多余的，写了和没写一样。但是也有特殊情况，毕竟 x86/64 是支持某些 weakly-ordered load 的，这时候这个指令会有用，但是非常 rare。lfence 还有其他用途，在此就不展开了。MFENCE: memory fence. It guarantees that every load and store instruction that precedes the MFENCE instruction in program order becomes globally visible before any load or store instruction that follows the MFENCE instruction. 这种 fence 也称为 Full Memory Barrier。也就是说，在两个内存操作之间加入 mfence 指令就实现了 Sequentially Consistent。DMB: Data Memory Barrier. 一般做为 Full memory barrier. It ensures that all explicit memory accesses that appear in program order before the DMB instruction are observed before any explicit memory accesses that appear in program order after the DMB instruction.DSB: Data Synchronization Barrier. 比 DMB 严格：No instruction in program order after this instruction executes until 前面的指令对主存的 L/S 操作完成.ISB: Instruction Synchronization Barrier. 最严格：它会清空 pipeline in the processor, so that all instructions following the ISB are fetched from cache or memory, after the instruction has been completed.C++11 这个版本引入的最重要的概念，不是 move 语义，智能指针，std::function 等具体的语法和功能实现，而是随着 std::thread 的引入带来的 memory_order
理解了前面几章内容，再来理解 C++11 的 memory_order，就比较容易了。
C++11 定义了 6 种内存顺序(memory order)：
用例(一)：单独作为 Fences
int A, B; void threadA() { A = 1; std::atomic_thread_fence(std::memory_order::seq_cst); print(B); } void threadB() { B = 1; std::atomic_thread_fence(std::memory_order::seq_cst); print(A); }
用例(二)：结合 atomic 类型使用
std::atomic<int> A, B; void threadA() { A.store(1, std::memory_order::seq_cst); print(B.load(std::memory_order::relaxed); } void threadB() { B.store(1, std::memory_order::seq_cst); print(A.load(std::memory_order::relaxed)); }
注意 C++ 是跨平台的通用语言，memory_order 的含义是：编译得到的机器代码的 memory order 至少要比指定的 memory_order 要强。因此这些 memory_order 对某些 CPU 可能会产生实际的 Fence 机器指令，对某些 CPU 可能不产生实际的机器代码。
同时，C++ 的野心不止于此，为了追求通用性，它还"发明"了机器指令中暂不支持的语义：例如 ，memory_order_release 单独作为 Fences 时，隔离了上面的所有内存操作和下面的所有的 S 操作；而 memory_order_release 结合 atomic 类型使用时，隔离的是上面所有的内存操作和本条 atomic Store 操作。然而编译成 ARM 机器指令后，产生的机器代码是一样的。也就是说某些情况下 C++ 的语义可能要比实际 CPU 支持的汇编指令更丰富一点。
对于 x86/64 来说，CPU 天生保证 acquire semantics, release semantics, consume semantics, and TSO semantics，因此 memory_order_acquire, memory_order_consume, memory_order_release, memory_order_acq_rel 在 x86/64 下不会编译生成额外的 fence 机器指令。同时注意 memory_order_relaxed 也不会特意编译生成机器代码来允许 weak store/load 的发生(即使 x86/64 下用 movnt 可以实现 weak store/load)。从这个角度来看，某些情况下汇编指令的语义又要比 C++ 的语义更丰富。
当前(201908) 官媒(is it?) cppreference 中 atomic_thread_fence 章节存在几个问题：
atomic_thread_fence imposes stronger synchronization constraints than an atomic store operation with the same std::memory_order. While an atomic store-release operation prevents all preceding writes(should be memory operations, i.e. including reads and writes) from moving past the store-release (the complete sentence should be: the store-release operation itself), an atomic_thread_fence with memory_order_release ordering prevents all preceding writes(should be memory operations, i.e. including reads and writes) from moving past all subsequent stores.
RMW操作：前面提到，对一个内存地址的操作无非只有两种：读(Load)和写(Store)。此外还有一种复合操作：先读某内存地址的值，再执行修改，然后再写回去该内存地址，并且这个操作是"原子"的，就是说在"一个操作"中完成，这种操作叫做"读-修改-写"操作(Read-Modify-Write, RMW)。上文提到的
compare_set操作就是一种 RMW 操作。
std::atomic 类型表示一个原子的变量，该原子变量的读(Load)+写(Store)操作是原子的。再加上 RMW 操作，原子变量一般支持下面三种操作，这些操作本身可以同时结合一个 memory_order：
Store 可结合 3 种 memory_order：
Load 可用 4 种 memory_order：
RMW 可用 6 种 memory_order：
