内存一致性模型详解：从SC到TSO
内存一致性模型详解：从SC到TSO
内存一致性模型是计算机体系结构中的一个重要概念，它定义了多处理器系统中内存读写操作的执行顺序。本文将详细介绍各种内存一致性模型及其在不同硬件架构下的应用，帮助读者更好地理解计算机内存管理机制。
1. 前言
从硬件的角度来看，最初对内存的访问过程大概是这样：
CPU <--> 内存
相对于 CPU 的执行频率，直接访问内存速度较慢，于是引入存储速度比内存更快、但更贵、更小容量的 CPU cache，用于缓存最近访问的内存数据，硬件拓扑结构如下图（不考虑多级 cache 情形）：
于是访问内存的过程变成了这样：
1. cache 命中，直接从 cache 中读取
CPU <--> CPU cache
2. cache 未命中，从内存加载到 cache ，再从 cache 读取
CPU <--> CPU cache <--> 内存
有了 CPU cache，速度上得到了很大提升，但人的追求永无止境，为了更快的速度，在 CPU 和 cache 之间，又加入了更快更贵更小容量的 store buffer 存储。此时硬件拓扑如下：
在有 store buffer 缓存的情形下，写操作数据写入到 store buffer，在需要的时候再写入到 cache。
说了这么多，这和引入内存一致性模型有什么关系？来看一个例子：
其中：
. t1 和 t2 代表两个线程，t1 绑定在 CPU 0 上运行，t2 绑定在 CPU 1 上运行；
. 变量 x 和 y 被两个线程共享，初始值为 0。
那么，最终 a 和 b 的值分别是多少呢？在没有引入内存一致性模型前，对这个问题无法讨论，接下来一一介绍几个常见的内存一致性模型。我们将在后文讨论的各种内存一致性模型下讨论这个例子。
2. 为什么需要内存一致性模型
内存一致性模型包括硬件层面的模型（由硬件负责）和语言的内存模型（由编译器负责，如 DRFx）。本文只讨论硬件层面的模型，后文出现的内存一致性模型专指硬件层面的模型。
内存一致性模型就是对内存读写(load/store)的以下 4 种存储顺序进行定义：
store-load
store-store
load-load
load-store
以 store-load 来说，以代码中某个点为分界，在编程顺序(program order)上，一些写操作(stores)在分隔点之前，另一些读操作(loads)在分隔点之后，如下：
stores
[分界]
loads
给定的内存一致性模型，定义了读写操作将按哪些可能的不同先后顺序执行。后文将描述在不同的内存一致性模型下，本小节示例的代码的可能的执行顺序和结果。
3. 各种内存一致性模型
3.1 顺序一致性(SC: Sequential Consistency)模型
所有提到的 4 种存储操作，（在同一 CPU 上）严格按照编程顺序(program order)执行。也就是说，在 CPU 在顺序一致性(SC: Sequential Consistency)模型下，在 CPU 0 上，1. 必定在 2. 之前执行，在 CPU 1 上，3. 必定在 4. 之前执行，而 CPU 0 和 1 之间的执行顺序，则是没有保证，即 1. 2. 3. 4. 的执行顺序可能是下列之一：
1., 2., 3., 4. // a=0, b=1
1., 3., 2., 4. // a=1, b=1
1., 3., 4., 2. // a=1, b=1
3., 4., 1., 2. // a=1, b=0
3., 1., 4., 2. // a=1, b=1
3., 1., 2., 4. // a=1, b=1
示例代码中 a, b 的值最终可能出现如下 3 种结果：
a = 0, b = 1
a = 1, b = 0
a = 1, b = 1
要注意的是，不要把多个 CPU 相互之间执令执行顺序的不确定性，和存储乱序混淆，它们不是同一回事。
3.2 完全存储定序(TSO: Total Store Order)模型
在完全存储定序(TSO: Total Store Order)模型下，写操作(store)不会将数据立即写入内存，而是先写到按严格先入先出(FIFO)的 store buffer 队列。提到的 4 种存储操作，允许 store-load 的写读存储操作乱序，其它操作保序。但要了解的是，这种乱序是指不同 CPU 之间的乱序：因为数据写到 CPU 自身的 store buffer，而直到将 CPU 自身 store buffer 中的数据刷出之前，CPU 自身 store buffer 中的数据不会被其它 CPU 看到；但是如果是 CPU 自身发起的读操作(load)，则是可以看到写入到 store buffer 的最新值。
CPU 何时将 store buffer 中的数据刷出，从目前了解的资料，都没有一个明确的界定。
了解了完全存储定序(TSO: Total Store Order)模型，我们来分析示例中 a,b 最终值得一种可能的情形：
其中：
. 左边第 1 列表示指令执行顺序序列
. t1, t2 列分别表示绑定在 CPU 0,1 中执行的线程
. WB1 为 CPU 0 的 store buffer ，WB2 为 CPU 1 的 store buffer
WBx 列 中的形如 [(x,1)] 表示 store buffer 队列中，缓存的变量 (x的地址，x的值1) 的二元组
. Main Memory 复合列表示各变量 (x,y,a,b) 在内存中的值
我们看到，在执行步骤 6 中，t1 (CPU 0) 将 store buffer 中的 (x,1) 出队，即将 x 的值 1 写入内存(Main Memory)，但很可惜，执行步骤 5 时，t2 (CPU 1) 从内存读取的 x 值是 0 (这时候 CPU 0 的 store buffer 缓存的 x 值 1 不被 CPU 1 看到)，导致了 b 读取的 x 值为 0；类似的，a 读到的 y 的值也为 0。但无论如何，上面分析的值只是 TSO 模型下，a, b 值的其中一种可能性。由于 CPU store buffer 中数据出列时间的不确定性，所以 a, b 最终值，从理论上分析，可能组合包括 (a=0,b=0), (a=1,b=0), (a=0,b=1), (a=1,b=1) 这 4 种可能性。
本文对 TSO 模型的介绍到此为止，如果想了解更多关于 TSO 模型的细节，可参考文章《Taming TSO Memory Consistency with Models》。
3.3 部分存储定序(PSO: Part Store Order)模型
提到的 4 种存储操作，允许 store-load，store-store 的存储操作乱序，其它操作保序。由于 PSO 允许 store-store 乱序，所以可能出现如下执行序列：
2., 1., 4., 3. // a=0, b=0
因此，示例代码中 a, b 的最终值可能出现如下 4 种结果：
a = 0, b = 1
a = 1, b = 0
a = 1, b = 1
a = 0, b = 0
3.4 宽松存储(RMO: Relax Memory Order)模型
提到的 4 种存储操作，允许所有4种操作乱序。由于 RMO 允许 store-store 乱序，所以可能出现如下执行序列：
2., 1., 4., 3. // a=0, b=0
因此，示例代码中 a, b 的最终值可能出现如下 4 种结果：
a = 0, b = 1
a = 1, b = 0
a = 1, b = 1
a = 0, b = 0
3.5 各硬件架构下内存一致性模型一览
4. 内存屏障(memory barrier)
为了解决内存操作乱序引入的问题，引入了内存屏障 (memory barrier)。如 ARM 的 DMB, DSB, ISB 指令等，更多关于内存屏障 (memory barrier) 的细节将不在此处展开，感兴趣的读者可查找相关资料。
5. 参考资料
[1]《perfbook.2018.12.08a.pdf》
[2]Sequential consistency
[3]《Taming TSO Memory Consistency with Models》
[4]Memory Ordering in Modern Microprocessors, Part I
[5]Memory Ordering in Modern Microprocessors, Part II
[6]https://zhuanlan.zhihu.com/p/422848235
[7]https://en.wikipedia.org/wiki/Consistency_model#Types
[8]https://en.wikipedia.org/wiki/Memory_ordering#Runtime_memory_ordering
[9]https://blog.csdn.net/anyegongjuezjd/article/details/125954805