Memory Consistency Models

type

status

date

slug

summary

让线程达成一致

一致性模型关注的是，多个线程（或工作线程、节点、副本等）如何“看到”世界。请看这个简单的程序，它运行两个线程，且初始时 A 和 B 都为 0：

线程 1

A = 1

print(B)

线程 2

3. B = 1

4. print(A)

要理解这个程序可能输出什么，我们需要考虑这些事件发生的顺序。直观来看，这个程序有两种明显的执行顺序：

(1) → (2) → (3) → (4)：第一个线程先运行它的两个操作，然后第二个线程才开始，所以程序会输出 0 1。

(3) → (4) → (1) → (2)：第二个线程先运行它的两个操作，然后第一个线程才开始，所以程序依然输出 0 1。

还有一些不那么直观的顺序，也就是两个线程的指令交错执行的情况：

(1) → (3) → (2) → (4)：每个线程的第一条指令都先执行，然后两个线程的第二条指令才执行，这样程序会输出 1 1。

(1) → (3) → (4) → (2)：第一个线程的第一条指令执行后，接着两个线程的第二条指令依次执行，最后再执行第一个线程的第二条指令，程序依然会输出 1 1。

还有一些其它顺序，但效果是一样的。

不应该发生的事情

直觉上，这个程序不可能输出 00。对于第 (2) 行要打印出 0，我们必须让 (3) 行写入 1 之前，(2) 行就先读取了 B。我们可以用一条箭头把这个关系表示出来：

图一（省略）：(2) 必须发生在 (3) 之前

一条从操作 x 指向操作 y 的箭头，表示要获得我们关心的行为，x 必须发生在 y 之前。同理，如果要让 (4) 行打印出 0，那么这个打印必须发生在 (1) 行写入 A 为 1 之前，所以我们也把这条边加到图上：

图二（省略）：(4) 必须发生在 (1) 之前

最后，当然，每个线程内的事件应该按顺序发生——也就是 (1) 在 (2) 之前，(3) 在 (4) 之前——这也是我们对命令式程序的基本预期。所以我们也要把这些箭头加进去：

图三（省略）：(1) → (2), (3) → (4)，以及跨线程的依赖箭头

但现在我们遇到了问题。如果我们从 (1) 开始，按照箭头依次走到 (2)，然后到 (3)，再到 (4)，然后……又回到了 (1)！请记住，这些箭头代表哪些事件必须发生在其他事件之前。所以如果我们从 (1) 出发，最后又回到 (1)，那么这个图就说明 (1) 必须发生在自己之前！除非出现物理学上的重大突破（比如时空穿越），否则这是不可能发生的。

由于这种执行顺序需要“时间旅行”，我们可以得出结论：这个程序不可能输出 00。你可以把这看作是一种反证法：假设这个程序可能输出 00，那么所有我们刚才列举的顺序规则都必须成立，但这些规则导致了自相矛盾（某个事件必须发生在自己之前）。所以这个假设是错误的。

顺序一致性：一种直观的并行模型

架构师和编程语言设计者认为我们刚才探讨的这些规则对程序员来说是直观的。其核心思想是：多个并行运行的线程都在操作同一块主内存，因此所有操作都必须有序发生。这里不存在“两个事件可以同时发生”的概念，因为它们都在访问同一块主内存。

需要注意的是，这条规则并没有说明具体事件会以什么顺序发生——它只要求这些事件以某种顺序发生。这个直观模型的另一部分，是要求同一线程内的事件必须按照程序顺序发生：即线程内的事件按照它们被写入的顺序执行。这也是程序员所期望的：如果我的程序允许在没有检查钥匙是否拧开之前就发射导弹，那肯定会出大问题。

这两条规则——单一主内存和程序顺序——共同定义了顺序一致性（sequential consistency）。定义顺序一致性是 Leslie Lamport 的众多成就之一，他也因此在 2013 年获得了图灵奖。

顺序一致性是我们遇到的第一个内存一致性模型的例子。内存一致性模型（通常简称“内存模型”）定义了多处理器系统中多个线程允许出现的各种操作顺序。例如，在上面的程序中，顺序一致性禁止任何会导致输出 00 的顺序，但允许输出 01 和 11 的某些顺序。

内存一致性模型是硬件和软件之间的一种契约。硬件承诺只会以模型允许的方式重新排序操作，作为交换，软件也要承认所有这些可能的重排序，并且需要正确应对它们。

顺序一致性的问题

可以把顺序一致性想象成一个开关。每个时间点，开关选择一个线程来运行，并把该线程的下一个事件完整执行完。这个模型遵循顺序一致性的规则：所有事件都在访问同一个主内存，因此它们以某种顺序发生；并且每次只从某个线程选取下一个事件执行，因此每个线程内部的事件都按程序顺序发生。

但这种模型的问题在于它极其、灾难性地慢。我们每次只能执行一条指令，因此失去了多线程并行运行所带来的大部分好处。更糟的是，每一条指令必须等到它的效果对其他线程可见后，才允许执行下一条指令——也就是说，只有等当前指令“完成”并对所有线程都可见，才可以继续运行其它指令。

一致性（Coherence）

有时候，这种必须等待的要求是有意义的。比如，考虑有两个线程都要写同一个变量 A，而另一个线程要读 A：

线程 1

A = 1

线程 2

2. A = 2

线程 3

3. print(A)

如果我们放弃“单一主内存”的理念，允许 (1) 和 (2) 并行执行，就突然不清楚 (3) 这条指令到底该读到哪个值。单一主内存保证每个变量最终只有一次写入“胜出”——也就是说，对每个变量的最后一次写入只有一个。如果没有这个保证，在 (1) 和 (2) 都执行后，(3) 可能读到 1，也可能读到 2，这就让人很困惑。

我们把这种保证称为一致性（coherence），它要求对同一位置的所有写操作，对所有线程来说必须以相同的顺序可见。它并不规定实际的执行顺序（(1) 或 (2) 谁先发生都可以），但它要求每个人都看到同一个“胜者”。

弱化（宽松）内存模型

在一致性（coherence）之外，通常并不需要单一主内存。再来看这个例子：

线程 1

(1) A = 1

(2) print(B)

线程 2

(3) B = 1

(4) print(A)

其实，没有理由要求执行事件 (2)（从 B 读取）时，必须等到事件 (1)（写 A）完成。它们之间完全没有互相影响，因此应该允许并行执行。尤其是事件 (1) 很慢，因为它是一次写操作。这意味着如果采用单一主存的观点，(2) 只能等到 (1) 对所有其他线程都可见之后才能运行。在现代 CPU 上，由于缓存层级结构，这种等待非常昂贵：

（图示：Core 1 / Core 2，各有 L1、L2，底部共享 L3 Cache）

两个核心之间唯一共享的内存是在 L3 缓存这一层，而访问 L3 缓存通常需要 90 个时钟周期以上。

总存储顺序（TSO, Total Store Ordering）

与其等待写操作 (1) 变得“可见”，我们可以把它放入一个存储缓冲区（store buffer）：

这样，在把 (1) 放入存储缓冲区之后，(2) 就可以立刻开始执行，而无需等到数据被写入 L3 Cache。由于存储缓冲区位于核心内部，访问速度非常快。未来的某个时刻，缓存层级系统会把写操作从存储缓冲区拉出，传播到各级缓存，最终让它对其它线程可见。存储缓冲区让我们能够隐藏通常需要等待写入操作对所有线程可见的延迟。

存储缓冲区的好处在于它保留了单线程的预期行为。例如，考虑下面这个简单的单线程程序：

线程 1

(1) A = 1

(2) print(A)

（插图略，解释：A=1 写入 Core 1 的 store buffer）

对于这个程序来说，(2) 必须能看到 (1) 写入的值，才能保持预期的单线程行为。写操作 (1) 还没有真正写入内存——它只是停在 core 1 的存储缓冲区里——所以如果 (2) 只是从内存中读取，它将会得到旧值。但由于程序运行在同一个 CPU 上，(2) 实际上可以直接访问存储缓冲区，看到里面有写入的新值，并直接使用这个新值。因此，即便使用了存储缓冲区，这个程序依然可以正确打印 1。

一种流行的允许存储缓冲区的内存模型叫做总存储顺序（TSO）。TSO 在很大程度上保留了与顺序一致性（SC）相同的保证，只是它允许使用存储缓冲区。这些缓冲区能够隐藏写入延迟，使得程序执行显著加快。

潜在的问题

存储缓冲区听起来像是很棒的性能优化，但有一个陷阱：TSO 允许出现顺序一致性（SC）下不会出现的行为。换句话说，运行在 TSO 硬件上的程序，可能会出现让程序员意想不到的行为。

让我们重新来看最开始的那个例子，不过这次是在带有存储缓冲区的机器上运行。首先，我们执行 (1) 和 (3)，它们都把数据写入各自的存储缓冲区，而不是立即写回主内存：

（图示：A=1 写入 Core 1 的 store buffer，B=1 写入 Core 2 的 store buffer，主内存 A=0，B=0）

接下来，我们在 core 1 上执行 (2)，需要读取 B 的值。它首先检查本地的存储缓冲区，但里面没有 B 的值，于是它从内存读取 B，得到的是 0，并打印 0。最后，在 core 2 上执行 (4)，需要读取 A 的值。core 2 的存储缓冲区里也没有 A，所以也只能从内存读取 A，得到的还是 0，然后打印 0。在将来的某个不确定时刻，缓存层级会把两个存储缓冲区里的内容刷新到主内存，完成写入。

在 TSO 下，这个程序可以输出 00。而之前我们证明过，顺序一致性模型下是显式禁止这种行为的！所以存储缓冲区会导致一些程序员意想不到的行为。

有没有架构愿意采用这种与直觉相悖的优化呢？答案是：有！事实上，几乎所有现代架构都包含存储缓冲区，所以它们的内存模型至少都不强于 TSO。

尤其是经典的 x86 架构，其内存模型非常接近 TSO。无论是 Intel（x86 的发明者）还是 AMD（x86-64 的发明者），都用像 litmus test 这样的示例测试来说明内存模型（和上面类似的程序），用来描述小程序的可观察到的结果。不幸的是，描述复杂系统的行为只靠几个例子会留下模糊空间。剑桥大学的研究人员投入了大量精力，形式化了 x86-TSO，以便明确 x86 的 TSO 实现的预期行为（尤其是和本文介绍的 store buffer 模型有何不同）。

变得更弱

尽管 x86 放弃了顺序一致性，但在允许的“怪异行为”方面，它其实是最守规矩的体系结构之一。大多数其他体系结构实现了更弱的内存模型，这意味着它们允许出现更多让人难以直觉理解的行为。这类模型有完整的光谱——比如 SPARC 架构就允许程序员在运行时选择三种不同的内存模型。

其中值得一提的是 ARM 架构（很可能你的智能手机就是它驱动的）。ARM 的内存模型出了名的规范不清，但本质上属于**弱排序（weak ordering）**的一种，几乎不提供什么保证。弱排序允许几乎任意操作被重排序，这使得硬件可以进行各种优化，但在底层编程时也成为了梦魇。

通过屏障逃逸

幸运的是，所有现代体系结构都包含同步操作，可以在必要时控制其宽松的内存模型。最常见的操作就是屏障（barrier）（或称栅栏 fence）。屏障指令要求在它之前的所有内存操作都完成后，才允许之后的内存操作开始。也就是说，屏障指令在程序执行的某个点上临时恢复了顺序一致性。

当然，这恰恰是我们引入存储缓冲区和其它优化时试图避免的行为。屏障其实是个不得已时的“逃生门”，应该谨慎使用，因为它可能带来数百个周期的开销。屏障的正确使用也非常微妙，尤其是在与含糊的内存模型定义结合时。有一些更易用的原语，比如原子 compare-and-swap，但直接用底层同步操作其实应尽量避免。真正的同步库会让你少受很多痛苦。

编程语言也需要内存模型

不仅仅是硬件会重排内存操作——编译器也经常这么做。看下面这个程序：

这个程序总是打印出 100 个 1 的字符串。当然，循环内部对 X 的赋值其实是多余的，因为没有其他代码改变 X 的值。标准的**循环不变代码提升（loop-invariant code motion）优化会把赋值移到循环外，以避免重复操作，而死代码消除（dead store elimination）**则会直接把 X = 0 删掉，最终变成：

这两个程序在单线程下完全等价，输出也完全一样。

但现在假设有另一个线程与我们的程序并行运行，并且会对 X 执行一次写操作：

当这两个线程并行运行时，第一个程序的行为会改变：现在它可能打印出像 111011111... 这样的字符串，只要有且仅有一个 0（因为下一次迭代又会把 X 赋值为 1）。而第二个程序的行为也会变化：它可以打印出 111100000... 这样的字符串，一旦开始输出 0 就不会再回到 1。

但这两种行为并不对称：第一个程序永远不会打印 111100000...，而第二个程序也不可能打印 111011111...。这意味着在存在并行的情况下，编译器优化不再保证生成等价程序。

这个例子表明，在程序级别也需要“内存一致性”这个概念。编译器优化实际上就是一种重排序：它以程序员可能无法预见的方式重排（或删除）一些内存访问。因此，为了保持直观的行为，编程语言也需要自己的内存模型，为程序员提供一种契约，明确说明它们的内存操作将如何被重排序。如今，语言设计领域越来越重视这个问题。例如，最新版的 C++ 和 Java 都对内存模型有严格的定义。

计算机坏掉了吗！

所有这些重排序看起来都令人疯狂，没有人能完全理清这些逻辑。但另一方面，回顾你的编程经历，会发现“内存一致性”这个问题其实你可能很少遇到，甚至几乎没碰到过（除非你是底层内核黑客）。那么，怎么调和这两种极端的感觉呢？

诀窍在于：我上面提到的每个例子都涉及数据竞争（data race）。数据竞争指的是两个或多个线程对同一内存位置进行访问，其中至少有一个是写操作，而且没有通过同步手段进行排序。如果没有数据竞争，那么这些重排序行为就无关紧要，因为所有“不直观”的重排序都会被同步机制阻止。注意，这并不意味着没有竞争的程序就是确定性（deterministic）的：不同的线程在每次执行时仍然有可能“赢得”不同的竞态。

实际上，像 C++ 和 Java 这样的语言都提供了一种保证，叫做无数据竞争程序的顺序一致性（sequential consistency for data-race-free programs，简称 “SC for DRF”）。这种保证的意思是，如果你的程序没有数据竞争，编译器就会自动插入所有必要的屏障（fence），来确保表现出顺序一致性。如果你的程序确实存在数据竞争，那一切都不保证，编译器可以自由地做任何事情。直觉上，有数据竞争的程序很可能本身就是有 bug 的，所以也没必要为这种有问题的程序提供强一致性保证。如果一个程序有故意设计的数据竞争，那说明程序员很可能知道自己在做什么，那么内存顺序问题也应该由他们自己负责。

使用同步库

既然你已经看到了这么多乱七八糟的细节，最重要的经验就是：你应该使用同步库。同步库会帮你处理那些丑陋的重排序问题。操作系统本身通常也经过了大量优化，确保在特定平台上只进行必要的同步。但现在，你已经知道了当这些库和内核在处理各种微妙同步问题时，底层究竟发生了什么。

如果你出于某种原因，想要了解更多关于计算机体系结构带来的各种可怕内存模型，Morgan & Claypool 的合成讲座在计算机体系结构部分有一篇很不错的入门材料，专门讲内存一致性和一致性（coherence）。