Non-Profit, International

Spirit unsterblich.

编程语言内存模型

字数统计：16323

这是Go语言现任领队Russ Cox在2021年写的文章Programming Language Memory Models的翻译。

本文是第二篇，重点阐述了C++和Java对内存模型设计的历史，以及ECMAScript 2017的初步尝试。

（内存模型，第二部分）

发布于2021年7月6日星期二。

编程语言内存模型回答了并行程序可以依赖哪些行为在其线程之间共享内存的问题。例如，考虑这个类似C语言的程序，其中 x 和 done 初始值为0。


// Thread 1           // Thread 2
x = 1;                while(done == 0) { /* loop */ }
done = 1;             print(x);

程序尝试将 x 中的消息从线程1发送到线程2，使用 done 作为消息已准备好接收的信号。如果线程1和线程2各自在自己的专用处理器上运行，都运行到完成，则此程序是否保证按预期完成并打印1？编程语言内存模型回答了这个问题和其他类似的问题。

尽管每种编程语言在细节上有所不同，但基本上所有现代多线程语言（包括C，C++，Go，Java，JavaScript，Rust和Swift）都有一些通用答案：

  • 首先，如果 x 和 done 是普通变量，那么线程2的循环可能永远不会停止。常见的编译器优化是在变量首次使用时将其加载到寄存器中，然后尽可能长时间地重用该寄存器以供将来访问该变量。如果线程2在线程1执行之前将 done 复制到寄存器中，则它可能会在整个循环中继续使用该寄存器，而不会注意到线程1稍后修改了 done。
  • 其次，即使线程2的循环确实停止，在观察到 done == 1 之后，它仍然可能打印出 x 为0。编译器通常根据优化启发式方法重新排序程序读取和写入，甚至只是基于生成代码时最终遍历哈希表或其他中间数据结构的方式。线程1的编译代码可能最终在“完成”而不是“之前”之后写入 x ，或者线程2的编译代码可能最终在循环之前读取 x 。

在给出程序破坏的原因后，重点是如何修复它。

现代语言以原子变量或原子操作的形式提供特殊功能，以允许程序同步其线程。如果我们使done成为原子变量（或使用原子操作，在采用该方法的语言中操作它），那么我们的程序可以保证完成并打印1。使 done 原子具有许多效果：

  • 线程1编译的代码必须确保对 x 的写入已完成，并且在写入 done 变得可见之前对其他线程可见。
  • 线程2编译的代码必须在循环的每次迭代中（重新）读取 done。
  • 线程2编译的代码必须在从 done 读取后从 x 读取。
  • 编译的代码必须执行任何必要的操作来禁用可能重新引入任何这些问题的硬件优化。

使 done 原子化的最终结果是程序按照我们想要的方式运行，成功地将 x 中的值从线程1传递到线程2。

在原始程序中，在编译器的代码重新排序之后，线程1可能在线程2读取它的同时写入 x。这是一个数据竞争。在修订后的程序中，原子变量 done 用于同步对 x 的访问：现在线程1不可能在线程2读取它的同时写入 x。该程序无数据竞争。一般来说，现代语言保证无数据争用的程序始终以顺序一致的方式执行，就好像来自不同线程的操作任意但不重新排序地交错到单个处理器上。这是在编程语言上下文中采用的硬件内存模型中的DRF-SC属性。

顺便说一句，这些原子变量或原子操作更合适地称为“同步原子”。确实，这些操作在数据库意义上是原子的，允许同时读取和写入，其行为就像按某种顺序顺序运行：普通变量上的竞争在使用原子时不是竞争。但更重要的是，原子同步程序的其余部分，提供一种消除非原子数据竞争的方法。不过，标准术语是简单的“原子”，所以本文也这么使用。除非另有说明，请记住将“原子”理解为“同步原子”。

编程语言内存模型指定了程序员和编译器所需内容的确切细节，作为它们之间的契约。上面概述的一般特征基本上适用于所有现代语言，但直到最近，事情才趋于一致：在2000年代初期，变化明显更多。即使在今天，不同语言在二阶问题上也存在显着差异，包括：

  • 原子变量本身的顺序保证是什么？
  • 一个变量可以被原子操作和非原子操作访问吗？
  • 除了原子之外还有同步机制吗？
  • 是否存在不同步的原子操作？
  • 带有竞争的程序有任何保证吗？

经过一些准备工作后，本文的其余部分将研究不同的语言如何回答这些问题和相关问题，以及它们实现这一目标所采取的路径。本文还强调了这一过程中的许多错误开始，以强调我们仍然在很大程度上了解什么有效，什么无效。

硬件，litmus测试，先发生于和DRF-SC {#hw}

在我们了解任何特定语言的详细信息之前，我们需要记住硬件内存模型的经验教训的简要总结。

不同的体系结构允许不同数量的指令重新排序，因此在多个处理器上并行运行的代码可以根据体系结构具有不同的允许结果。黄金标准是顺序一致性，其中任何执行都必须表现得好像在不同处理器上执行的程序只是以某种顺序交错到单个处理器上。该模型对于开发人员来说更容易推理，但目前还没有重要的架构提供它，因为较弱的保证带来了性能提升。

比较不同的内存模型很难做出完全通用的陈述。相反，它可以帮助您专注于特定的测试用例，称为 litmus测试。如果两个内存模型对于给定的litmus测试允许不同的行为，这证明它们是不同的，并且通常可以帮助我们了解至少对于该测试用例，一个模型是否比另一个更弱或更强。例如，这是我们之前检查的程序的litmus测试形式：

litmus测试：消息传递

这个程序能观测到 r1 = 1，r2 = 0 吗？


// Thread 1           // Thread 2
x = 1                 r1 = y
y = 1                 r2 = x

在顺序一致的硬件上：否。

在x86（或其他TSO）上：否。

在ARM/POWER上：是！

在任何使用普通变量的现代编译语言中：是！

与上一篇文章一样，我们假设每个示例都以所有共享变量初始值都为0。名称 rN 表示私有存储，如寄存器或函数局部变量；其他名称如 x 和 y 是不同的、共享的（全局）变量。我们询问在执行结束时是否可以对寄存器进行特定设置。在回答硬件的litmus测试时，我们假设没有编译器来重新排序线程中发生的事情：列表中的指令直接转换为提供给处理器执行的汇编指令。

结果 r1 = 1、r2 = 0 对应于原始程序的线程2完成其循环（done 是 y），但随后打印0。在程序操作的任何顺序一致交错中都不可能出现此结果。对于汇编语言版本，在x86上不可能打印0，但由于处理器本身的重新排序优化，在ARM和POWER等更宽松的体系结构上可以打印0。在现代语言中，无论底层硬件是什么，编译期间可能发生的重新排序都使得这种结果成为可能。

正如我们前面提到的，今天的处理器不是保证顺序一致性，而是保证一个称为“无数据争用顺序一致性”或DRF-SC（有时也写为SC-DRF）的属性。保证DRF-SC的系统必须定义称为同步指令的特定指令，它提供了一种协调不同处理器（相当于线程）的方法。程序使用这些指令在一个处理器上运行的代码与另一个处理器上运行的代码之间创建“先发生于”关系。

例如，这里描述了一个程序在两个线程上的短暂执行；像往常一样，假设每个都位于其自己的专用处理器上：

我们在上一篇文章中也看到了这个程序。线程1和线程2执行同步指令S(a)。在程序的这个特定执行中，两条S(a) 指令建立了从线程1到线程2的happens-before关系，因此线程1中的W(x) 先发生于线程2的R(x)。

不同处理器上按happens-before排序的两个事件可能同时发生：确切顺序尚不清楚。我们说他们并发执行。数据争用是指对变量的写入与对该变量的读取或另一次写入同时执行。提供DRF-SC的处理器（现在的所有处理器）保证程序没有数据竞争的行为，就像它们在顺序一致的架构上运行一样。这是在现代处理器上编写正确的多线程汇编程序的基本保证。

正如我们之前看到的，DRF-SC也是现代语言所采用的基本保证，使得用高级语言编写正确的多线程程序成为可能。

编译器和优化 {#compilers}

我们已经多次提到，编译器可能会在生成最终可执行代码的过程中对输入程序中的操作重新排序。让我们仔细看看该声明以及其他可能导致问题的优化。

人们普遍认为，编译器可以几乎任意地对普通的读取和写入进行重新排序，前提是重新排序不能改变单线程执行时代码的可见行为。例如，考虑以下程序：


w = 1
x = 2
r1 = y
r2 = z

由于 w、x、y 和 z 都是不同的变量，因此这四个语句可以按照编译器认为的最佳任何顺序执行。

正如我们上面提到的，如此自由地重新排序读取和写入的能力使得普通编译程序的保证至少与ARM/POWER宽松内存模型一样弱，因为编译程序无法通过消息传递litmus测试。事实上，对已编译程序的保证较弱。

在硬件文章中，我们将一致性作为ARM/POWER架构保证的一个例子：

litmus测试：一致性

这个程序能观察到 r1 = 1, r2 = 2, r3 = 2, r4 = 1 吗？

（线程3能在 x = 1 在 x = 2 之前，并且线程4看到相反的结果吗？）


// Thread 1    // Thread 2    // Thread 3    // Thread 4
x = 1          x = 2          r1 = x         r3 = x
                              r2 = x         r4 = x

在顺序一致的硬件上：否。

在x86上（或其他TSO）：否。

在ARM/POWER上：否。

在任何使用普通变量的现代编译语言中：是！

所有现代硬件都保证了一致性，这也可以看作是单个内存位置上操作的顺序一致性。在这个程序中，其中一个写入必须覆盖另一个，整个系统必须同意一个固定顺序。事实证明，由于编译过程中的程序重新排序，现代语言甚至不提供一致性。

假设编译器对线程4中的两个读取重新排序，然后指令按以下顺序交错运行：


// Thread 1    // Thread 2    // Thread 3    // Thread 4
                                             // \(reordered\)
(1) x = 1                     (2) r1 = x     (3) r4 = x
               (4) x = 2      (5) r2 = x     (6) r3 = x

结果是 r1 = 1，r2 = 2，r3 = 2，r4 = 1，这在汇编程序中是不可能的，但在高级语言中是可能的。从这个意义上说，编程语言内存模型都比最宽松的硬件内存模型弱。

但还有一些保证。每个人都同意需要提供DRF-SC，这不允许引入新读取或写入的优化，即使这些优化在单线程代码中有效。

例如，请考虑以下代码：


if (c) {
    x++;
} else {
    ... lots of code ...
}

有一个 if 语句，else 中有很多代码，而 if 主体中只有一个 x++。减少分支并完全消除 if 主体可能会更“便宜”。我们可以通过在 if 之前运行 x++ 来做到这一点，然后如果我们错了，则在大的else主体中使用 x-- 进行调整。也就是说，编译器可能会考虑将该代码重写为：


x++;
if (!c) {
    x--;
    ... lots of code ...
}

这是安全的编译器优化吗？在单线程程序中，是的。在多线程程序中，当 c 为false时，x 与另一个线程共享，否：优化会在 x 上引入原始程序中不存在的竞争。

此示例源自Hans Boehm 2004年的论文中的一个，“线程不能作为库实现”，这使得语言不能对多线程执行的语义保持沉默。

编程语言内存模型试图准确回答这些问题：哪些优化是允许的，哪些是不允许的。通过研究过去几十年来尝试编写这些模型的历史，我们可以了解哪些有效，哪些无效，并了解事情的发展方向。

原始的Java内存模型（1996） {#java96}

Java是第一个尝试写下它对多线程程序的保证的主流语言。它包括互斥体并定义了它们隐含的内存排序要求。它还包括“易失性”原子变量：所有易失性变量的读写都需要直接在主内存中按程序顺序执行，使得对易失性变量的操作以顺序一致的方式表现。最后，Java还指定了（或至少尝试指定）具有数据竞争的程序的行为。其中一部分是要求普通变量具有某种形式的一致性，我们将在下面详细讨论。不幸的是，这种尝试在Java语言规范（1996）第一版中至少有两个严重的问题缺陷。通过事后诸葛亮和使用我们已经设定的预备知识，它们很容易解释。当时，它们远没有那么明显。

原子需要同步 {#atomics}

第一个缺陷是易失性原子变量是非同步的，因此它们无助于消除程序其余部分中的竞争。我们上面看到的消息传递程序的Java版本是：


int x;
volatile int done;

// Thread 1           // Thread 2
x = 1;                while(done == 0) { /* loop */ }
done = 1;             print(x);

因为 done 被声明为易失性，所以保证循环完成：编译器无法将其缓存在寄存器中并导致无限循环。但是，程序不保证打印1。不禁止编译器重新排序对 x 和 done 的访问，也不需要禁止硬件执行相同的操作。

由于Java易失性是非同步原子，因此您无法使用它们来构建新的同步原语。从这个意义上说，原始的Java内存模型太弱了。

一致性与编译器优化不兼容 {#coherence}

原始的Java内存模型也太强大了：强制一致性——一旦线程读取了内存位置的新值，它就不能再读取旧值了——不允许进行基本的编译器优化。之前我们研究了重新排序读取会如何破坏一致性，但您可能会想，好吧，只是不要重新排序读取。这是另一种优化可能会破坏一致性的更微妙的方式：公共子表达式消除。

考虑如下Java程序：


// p和q可能指向同一个对象，也可能不指向同一个对象。
int i = p.x;
// ...也许此时另一个线程写入p.x...
int j = q.x;
int k = p.x;

在此程序中，公共子表达式消除会注意到 p.x 被计算了两次，并将最后一行优化为 k = i 。但是，如果 p 和 q 指向同一个对象，并且另一个线程在读取 i 和 j 之间写入 p.x ，则将旧值 i 重用于 k 会违反一致性：读入 i 时看到旧值，读入 j 时看到较新的值，但随后重用 i 读入 k 时将再次看到旧值。无法优化掉冗余读取会阻碍大多数编译器，使生成的代码变慢。

硬件比编译器更容易提供一致性，因为硬件可以应用动态优化：它可以根据给定内存读取和写入序列中涉及的确切地址调整优化路径。相比之下，编译器只能应用静态优化：他们必须提前写出一个指令序列，无论涉及什么地址和值，这个指令序列都是正确的。在该示例中，编译器无法根据 p 和 q 是否碰巧指向同一对象来轻松更改发生的情况，至少在不为这两种可能性编写代码的情况下不会，从而导致大量的时间和空间开销。编译器对内存位置之间可能的混叠的了解不完整，这意味着实际提供一致性需要放弃基本的优化。

Bill Pugh在1999年的论文中指出了这个问题和其他问题 “修复Java内存模型”。

新的Java内存模型（2004） {#java04}

由于这些问题，而且原始的Java内存模型即使对于专家来说也很难理解，Pugh和其他人开始努力为Java定义一个新的内存模型。该模型成为JSR-133，并在2004年发布的Java 5.0中采用。规范参考文献是“Java内存模型” (2005)，作者：Jeremy Manson、Bill Pugh和Sarita Adve，其他详细信息请参见Manson博士的论文。新模型遵循DRF-SC方法：保证无数据竞争的Java程序以顺序一致的方式执行。

同步原子和其他操作 {#sync}

正如我们之前看到的，要编写一个无数据竞争的程序，程序员需要可以建立“先发生于”边缘的同步操作，以确保一个线程不会同时写入非原子变量，而另一个线程读取或写入它。在Java中，主要的同步操作是：

  • 线程的创建先发生于线程中的第一个操作。
  • 对互斥锁 m 的解锁先发生于任何后续对 m 的上锁。
  • 一个对易失性变量 v 的写先发生于任何后续对 v 的读。

“后续”是什么意思？Java定义所有锁定、解锁和易失性变量访问的行为就像它们在某种顺序一致的交错中发生一样，从而对整个程序中的所有这些操作给出总顺序。“后续”是指该总顺序中的稍后。也就是说：锁定、解锁和易失性变量访问的总顺序定义了后续的含义，然后使用特定执行中的happens-before边缘定义后续，然后先发生于边缘定义该特定执行是否具有数据争用。如果没有争用，则执行的行为是顺序一致的。

易失性访问必须像在存在某些总排序一样运行，这意味着在存储缓冲区litmus测试中，不能以 r1 = 0 和 r2 = 0 结束：

litmus测试：储存缓冲区

这个程序能观测到 r1 = 0, r2 = 0 吗？


// Thread 1           // Thread 2
x = 1                 y = 1
r1 = y                r2 = x

在顺序一致的硬件上：否。

在x86（或其他TSO）：是！

在ARM/POWER：是！

在Java中使用volatiles：否。

在Java中，对于易失变量 x 和 y，读取和写入不能重新排序：一个写入必须排在第二个位置，第二个写入之后的读取必须看到第一个写入。如果我们没有顺序一致的要求——比如说，如果易失性只需要连续——那么这两个读取可能会错过写入。

这里有一个重要但微妙的点：所有同步操作的总顺序与happens-before的关系是分开的。在程序中的每个锁定、解锁或易失性变量访问之间，在一个方向或另一个方向上存在一个happens-before边缘不是真的：你只能从写入到观察写入的读取获得一个happens-before边缘。例如，不同互斥锁的锁定和解锁在它们之间没有happens-before边缘，不同变量的易失性访问也没有，即使这些操作必须共同表现得像遵循单个顺序一致的交错一样。

程序的竞争语义 {#racy}

DRF-SC仅保证程序的行为顺序一致，没有数据竞争。与原始模型一样，新的Java内存模型定义了有竞争的程序的行为，原因如下：

  • 支持Java的一般安全和安全保证。
  • 使程序员更容易发现错误。
  • 使攻击者更难利用问题，因为竞争可能造成的损害更加有限。
  • 让程序员更清楚地了解他们的程序是做什么的。

新模型不再依赖于连续性，而是重用了先发生于关系（已经用于确定程序是否有竞争）来决定竞争读取和写入的结果。

Java的具体规则是，对于字大小或更小的变量，读取变量（或字段） x 必须看到通过对 x 的单个写入来存储的值。对 x 的写入可以通过读取 r 来观察，前提是 r 不会在 w 之前发生。这意味着 r 可以观察在 r 之前发生的写入（但也不会在 r 之前被覆盖），并且可以观察与 r 竞争的写入。

以这种方式使用先发生于，结合同步原子（volatiles）可以建立新的先发生于边缘，是对原始Java内存模型的重大改进。它为程序员提供了更有用的保证，并且最终允许大量重要的编译器优化。这项工作仍然是今天Java的内存模型。也就是说，它仍然不太正确：这种试图使用先发生于定义竞争程序的语义存在问题。

先发生于不排除不连续 {#incoherence}

使用先发生于定义程序语义的第一个问题与连续性有关（再次！）。（下面的例子取自Jaroslav Ševčík和David Aspinall的论文，“关于Java内存模型中程序转换的有效性”（2007）。）

这是一个包含三个线程的程序。假设已知线程1和线程2在线程3开始之前完成。


// Thread 1           // Thread 2           // Thread 3
lock(m1)              lock(m2)
x = 1                 x = 2
unlock(m1)            unlock(m2)
                                            lock(m1)
                                            lock(m2)
                                            r1 = x
                                            r2 = x
                                            unlock(m2)
                                            unlock(m1)

线程1在持有互斥锁 m1 时写入 x = 1。线程2在持有互斥锁 m2 的同时写入 x = 2。这些是不同的互斥体，所以两者写竞争。但是，只有线程3读取 x，并且在获取两个互斥体后读取。读入 r1 可以观测到任一写入：两者都先发生于它，并且都不会明确覆盖另一个。通过相同的参数，读入r2 可以观测到任一写入。但严格来说，Java内存模型中没有任何内容表明两个读取必须一致：从技术上讲，r1 和 r2 可以读取不同的 x 值。也就是说，该程序可以以 r1 和 r2 结束，保持不同的值。当然，没有真正的实现会产生不同的 r1 和 r2。互斥意味着这两个读取之间不会发生写入。它们必须获得相同的值。但是内存模型允许不同的读取这一事实表明，它在某些技术方面并没有精确地描述真正的Java实现。

情况变得更糟。如果我们在两个读取之间再添加一个指令 x = r1 怎么办：


// Thread 1           // Thread 2           // Thread 3
lock(m1)              lock(m2)
x = 1                 x = 2
unlock(m1)            unlock(m2)
                                            lock(m1)
                                            lock(m2)
                                            r1 = x
                                            x = r1   // \!\?
                                            r2 = x
                                            unlock(m2)
                                            unlock(m1)

现在，很明显，读取的 r2 = x 必须使用 x = r1 写入的值，因此程序必须在 r1 和 r2 中获得相同的值。现在保证两个值 r1 和 r2 相等。

这两个程序之间的差异意味着我们对编译器有问题。看到 r1 = x 后跟 x = r1 的编译器可能希望删除第二个赋值，这“显然”是多余的。但是这种“优化”将第二个程序（必须在 r1 和 r2 中看到相同的值）更改为第一个程序，从技术上讲，该程序的 r1 可以与 r2 不同。因此，根据Java内存模型，这种优化在技术上是无效的：它改变了程序的含义。需要明确的是，这种优化不会改变在你能想象到的任何真实JVM上执行的Java程序的含义。但不知何故，Java内存模型不允许这样做，这表明还有更多需要说的。

有关此示例和其他示例的详细信息，参见 Ševčík和Aspinall的论文

先发生于不排除因果关系 {#acausality}

最后一个例子被证明是一个简单的问题。这是一个更难的问题。考虑这个litmus测试，使用普通的（非易失性）Java变量：

litmus测试：凭空而来的竞争值

这个程序能观测到 r1 = 42 和 r2 = 42 吗？


// Thread 1           // Thread 2
r1 = x                r2 = y
y = r1                x = r2

（当然不！）

该程序中的所有变量都像往常一样从0开始，然后该程序在一个线程中有效地运行 y = x，在另一个线程中运行 x = y。x 和 y 最终会是42吗？在现实生活中，显然不是。但为什么不呢？事实证明，内存模型不允许此结果。

假设假设 r1 = x 确实读取了42。然后 y = r1 会将42写入 y，然后赛车 r2 = y 可以读到42，导致 x = r2 将42写入 x，并且用（因此可以通过）原始 r1 = x 来写竞争，似乎证明了最初的假设。在这个例子中，42被称为空气值，因为它在没有任何理由的情况下出现，但随后用循环逻辑证明自己。如果内存在当前0之前一直保持42，并且硬件错误地推测它仍然是42，该怎么办？这种猜测可能会成为一个自我实现的预言。在Spectre和相关攻击显示硬件推测是多么激进之前，这个论点似乎更牵强。即便如此，没有硬件以这种方式发明空气值。

很明显，该程序不能以 r1 和 r2 设置为42结束，但先发生于本身并不能解释为什么这不会发生。这再次表明存在一定的不完整性。新的Java内存模型花费了大量时间解决这种不完整性，稍后会讨论。

这个程序有一个竞争——x 和 y 的读取与其他线程中的写入竞争——所以我们可能会认为这是一个不正确的程序。但这里有一个没有数据竞争的版本：

litmus测试：没有竞争的空气值

这个程序能观测到 r1 = 42 和 r2 = 42 吗？


// Thread 1           // Thread 2
r1 = x                r2 = y
if (r1 == 42)         if (r2 == 42)
    y = r1                x = r2

（当然不！）

由于 x 和 y 从0开始，任何顺序一致的执行都不会执行写入，因此该程序没有写入，因此没有竞争。然而，再一次，单独先发生于并不排除这样一种可能性，假设 r1 = x 看到不完全写竞争，然后根据该假设，条件最终都为真，x 和 y 最后都是42。这是另一种空气值，但这次是在一个没有竞争的程序中。任何保证DRF-SC的模型都必须保证该程序在末尾只看到所有零，但先发生于并没有解释原因。

Java内存模型花费了很多文字，我不会深入这些词来试图排除这些非因果假设。不幸的是，五年后，Sarita Adve和Hans Boehm对这项工作有这样的看法：

以一种不禁止其他所需优化的方式禁止这种因果关系违规被证明是非常困难的。...经过许多提案和五年的激烈辩论，目前的模式被批准为最好的折衷方案。...不幸的是，这个模型非常复杂，已知有一些令人惊讶的行为，并且最近被证明有一个错误。

（Adve和Boehm, “内存模型：重新思考并行语言和硬件的案例”, August 2010）

C++11内存模型（2011） {#cpp}

让我们把Java放在一边，来看看C++。受到Java新内存模型显而易见的成功的启发，许多相同的人着手为C++定义了一个类似的内存模型，并最终在C++11中被采纳。与Java相比，C++在两个重要方面有所不同。首先，C++对具有数据竞争的程序不做任何保证，这似乎消除了Java模型中的许多复杂性。其次，C++提供了三种原子操作：强同步（“顺序一致”）、弱同步（“获取/释放”，连续一致）和无同步（“宽松”，用于隐藏竞争）。宽松原子操作重新引入了Java在定义竞态程序意义方面的所有复杂性。结果是，C++模型比Java的更复杂，但对程序员却更少有帮助。

C++11还定义了原子围栏作为原子变量的替代品，但它们不那么常用，我也不打算讨论它们。

DRF-SC和Catch Fire {#fire}

与Java不同，C++对有数据竞争的程序不提供任何保证。任何在其中任何地方存在竞争的程序都属于“未定义行为”。在程序执行的头几微秒内的竞争访问可能会在数小时或数天后导致任意的错误行为。这通常被称为“DRF-SC或Catch Fire”：如果程序没有数据竞争，它会以顺序一致的方式运行；如果有数据竞争，它可能会做任何事情，包括Catch Fire。

有关DRF-SC或Catch Fire的论点的更长篇幅展示，请参见Boehm, “Memory Model Rationales” (2007) 以及Boehm和Adve, “Foundations of the C++ Concurrency Memory Model” (2008)。

简要来说，这个观点有四个常见的理由：

  • C和C++中已经充斥着未定义行为，语言的角落里编译器优化四处横行，用户最好不要随意涉足。多一个未定义行为又有何妨？

  • 现有的编译器和库在编写时没有考虑到线程，以任意方式破坏竞争程序。找到并修复所有问题太困难了，这就是他们的论点，尽管尚不清楚这些未修复的编译器和库将如何应对松散原子操作。

  • 真的知道自己在做什么并想避免未定义行为的程序员可以使用松散原子操作。

  • 将竞争语义留作未定义允许实现检测并诊断竞争，并停止执行。

我个人认为，最后一个理由是唯一有说服力的，尽管我观察到可以说“允许竞争检测器”而不必同时说“在整数上的一个竞争可以使整个程序无效”。

以下是“内存模型原理”中的一个例子，我认为它很好地捕捉了C++方法的本质及其问题。考虑这个引用全局变量 x 的程序。


unsigned i = x;

if (i < 2) {
    foo: ...
    switch (i) {
    case 0:
        ...;
        break;
    case 1:
        ...;
        break;
    }
}

声称C++编译器可能会将 i 保存在寄存器中，但如果标签 foo 处的代码很复杂，则需要重用寄存器。与其将当前值的 i 溢出到函数栈中，编译器可能会决定在到达 switch 语句时从全局 x 中第二次加载 i。结果是在 if 主体的中途，i < 2 可能不再为真。如果编译器做了一些事情，比如使用由 i 索引的表将 switch 编译为计算跳转，则该代码将从表的末尾索引并跳转到意外的地址，这可能会任意糟糕。

从这个例子和其他类似的例子中，C++内存模型的作者得出结论，任何有竞争的访问都必须被允许对程序未来的执行造成无限的损害。个人而言，我认为在多线程程序中，编译器不应假设它们可以通过重新执行初始化它的内存读取来重新加载像 i 这样的局部变量。期望为单线程世界编写的现有C++编译器找到并修复像这样的代码生成问题可能是不切实际的，但在新语言中，我认为我们应该设定更高的目标。

题外话：C和C++未定义的行为 {#ub}

顺便说一句，C和C++坚持编译器能够任意地表现得糟糕以响应程序中的错误，这导致了真正荒谬的结果。例如，考虑这个程序，这是一个在2017年在Twitter讨论的话题：


#include <cstdlib>

typedef int (*Function)();

static Function Do;

static int EraseAll() {
    return system("rm -rf slash");
}

void NeverCalled() {
    Do = EraseAll;
}

int main() {
    return Do();
}

如果您是像Clang这样的现代C++编译器，则可以按如下方式考虑此程序：

  • 在 main 中，显然 Do 要么是null，要么是 EraseAll。
  • 如果 Do 是 EraseAll，那么 Do() 和 EraseAll() 是一样的。
  • 如果 Do 为null，则 Do() 是未定义的行为，我可以随心所欲地实现它，包括无条件地实现 EraseAll()。
  • 因此，我可以将间接调用 Do() 优化为直接调用 EraseAll()。
  • 我还不如在这里内联 EraseAll。

最终结果是Clang将程序优化为：


int main() {
    return system("rm -rf slash");
}

你不得不承认：在这个例子旁边，本地变量 i 可能会在 if (i < 2) 的主体中途突然不再小于2的可能性看起来并不奇怪。

从本质上来说，现代的C和C++编译器假设没有程序员敢于尝试未定义行为。一个程序员写了一个带有错误的程序？难以置信!

就像我说的，在新语言中，我认为我们应该有更高的目标。

获得/释放原子 {#acqrel}

C++采用了与（新的）Java的volatile变量（与C++的volatile无关）非常相似的顺序一致性原子变量。在我们的消息传递示例中，我们可以将 done 声明为

atomic<int> done;

然后像在Java中一样，将 done 当作普通变量使用。或者我们可以声明一个普通的 int done; 然后使用

atomic_store(&done, 1);

和

while(atomic_load(&done) == 0) { /* loop */ }

以访问它。无论哪种方式，对 done 的操作都会参与原子操作的顺序一致顺序，并同步程序的其余部分。

C++还添加了较弱的原子操作，可以使用附加内存排序参数的 atomic_store_explicit 和 atomic_load_explicit 进行访问。使用 memory_order_seq_cst 使显式调用等同于上面的简短调用。

较弱的原子称为acquire/release原子，其中后acquire观察到的释放会在release到acquire之间创建先发生边缘。这个术语是为了唤起互斥锁： release就像解锁一个互斥锁，而acquire就像锁定同一个互斥锁。在释放之前执行的写入必须对后续acquire之后执行的读取可见，就像在解锁互斥锁之前执行的写入必须对稍后锁定同一互斥锁后执行的读取可见一样。

要使用较弱的原子，我们可以将消息传递示例更改为使用

atomic_store(&done, 1, memory_order_release);

和

while(atomic_load(&done, memory_order_acquire) == 0) { /* loop */}

它仍然是正确的。但并非所有项目都会如此。

回想一下，顺序一致的原子要求程序中所有原子的行为与执行的某种全局交错（总顺序）一致。acquire/release原子则不会。它们只需要在单个内存位置上按顺序一致地交错操作。也就是说，它们只需要连贯性。结果是，使用具有多个内存位置的acquire/release原子的程序可能会观察到无法通过程序中所有acquire/release原子的顺序一致交错来解释的执行，这可以说是违反了DRF-SC！

为了显示差异，这里再次是store buffer示例：

litmus测试：存储缓冲

这个程序能看到 r1 = 0, r2 = 0 吗？


// Thread 1           // Thread 2
x = 1                 y = 1
r1 = y                r2 = x

在顺序一致的硬件上：否。

在x86 (或其他TSO):是！

在ARM/POWER:是！

在Java (使用volatiles): 否。

在C++11 (顺序一致原子): 否

在C++11 (acquire/release原子):是！

C++的顺序一致原子操作与Java的volatile相匹配。但是获取-释放原子操作在 x 的顺序和 y 的顺序之间不施加任何关系。特别是，程序可以表现得好像 r1=y 发生在 y=1 之前，而与此同时 r2=x 发生在 x=1 之前，允许 r1=0，r2=0，这与整个程序的顺序一致性相矛盾。这些可能仅仅存在于x86上，因为它们是免费的。

请注意，对于给定的一组特定读取观察特定写入，C++顺序一致原子操作和C++获取/释放原子操作会创建相同的前发生边。它们之间的区别在于，一些特定读取观察特定写入的集合在顺序一致原子操作中是不允许的，但在获取/释放原子操作中是允许的。一个这样的例子是在存储缓冲情况下导致 r1=0，r2=0 的集合。

获取/释放弱点的真实示例 {#cond}

获取/释放原子操作在实践中不如提供顺序一致性的原子操作有用。这里有一个例子。假设我们有一个新的同步原语，一个只有两个方法 Notify 和 Wait 的单次使用条件变量。为简便起见，只有一个线程调用 Notify，另一个线程调用 Wait。我们希望当另一个线程尚未等待时，Notify 可以无锁操作。我们可以使用一对原子整数来实现：


class Cond {
    atomic<int> done;
    atomic<int> waiting;
    ...
};


void Cond::notify() {
    done = 1;
    if (!waiting)
        return;
    // ... wake up waiter ...
}

void Cond::wait() {
    waiting = 1;
    if(done)
        return;
    // ... sleep ...
}

这段代码的重要部分在于 notify 在检查 waiting 之前设置 done，而 wait 在检查 done 之前设置 waiting，以确保 notify 和 wait 的并发调用不会导致 notify 立即返回而 wait 进入睡眠状态。但是在C++获取/释放原子操作中，它们可以。而且它们可能只会在某些时间内发生，使得这个bug非常难以重现和诊断。（更糟的是，在一些架构（比如64-bit ARM）中，最好将获取/释放原子操作实现为顺序一致的原子操作，所以你可能会编写在64-bit ARM上运行良好的代码，但在移植到其他系统时才发现它是不正确的。）

根据这种理解，“acquire/release” 对于这些原子来说是一个不幸的名字，因为顺序一致的atomic执行同样多的获取和释放。这些不同的是失去了顺序一致性。将这些称为“相干”原子可能更好。太迟了。

宽松原子 {#relaxed}

C++并没有止步于仅仅连贯的acquire/release原子。它还引入了非同步原子，称为宽松原子（memory_order_relaxed）。这些原子根本没有同步效应 — 它们不会创建先发生边 — 而且它们也根本没有排序保证。事实上，宽松原子读/写和普通读/写之间没有区别，只是宽松原子上的争用不被视为争用，不会Catch Fire。

修订后的Java内存模型的大部分复杂性来自于定义具有数据争用的程序的行为。如果C++采用DRF-SC或Catch Fire（有效地禁止具有数据争用的程序），这意味着我们可以扔掉我们之前看到的所有那些奇怪的例子，这样C++语言规范就会比Java的规范更简单，那就太好了。不幸的是，包含松散的原子最终保留了所有这些关注点，这意味着C++11规范最终并不比Java的规范简单。

与Java的内存模型一样，C++11内存模型最终也不正确。考虑前面的data-race-free程序：

litmus测试：非Racy Out Of Thin Air值

这个程序能看到 r1 = 42, r2 = 42 吗？


// Thread 1           // Thread 2
r1 = x                r2 = y
if (r1 == 42)         if (r2 == 42)
    y = r1                x = r2

（当然不！）

C++11（普通变量）：否

C++11（宽松原子）：是！

在他们的论文“Common Compiler Optimisations are Invalid in the C11 Memory Model and what we can do about it”（2015年）中，Viktor Vafeiadis等人表明，C++11规范保证，当 x 和 y 是普通变量时，该程序必须以 x 和 y 设置为零结束。但是，如果 x 和 y 是松散原子变量，那么严格来说，C++11规范并不排除 r1 和 r2 最终都变成42的可能性。（惊喜！）

有关详细信息，请参阅论文，但在高级别上，C++11规范有一些正式的规则，试图禁止凭空值，并结合一些模糊的词来阻止其他类型的有问题的值。这些正式规则是问题所在，因此C++14放弃了它们，只留下了模糊的单词。引用删除它们的理由，C++11公式被证明是“既不够的，因为它在很大程度上不可能用 memory_order_relaxed 来推理程序，而且非常有害，因为它可以说不允许在ARM和POWER等架构上所有合理的 memory_order_relaxed 实现。

回顾一下，Java尝试正式排除所有非因果执行，但失败了。然后，凭借Java的后见之明，C++11试图正式地仅排除一些非因果执行，但同样失败了。然后C++14根本没有说任何正式的话。这并没有朝着正确的方向发展。

事实上，Mark Batty和其他人在2015年的一篇题为 “The Problem of Programming Language Concurrency Semantics” 给出了这个发人深省的评价：

令人不安的是，在第一个宽松内存硬件 （IBM 370/158MP）推出40+ 年后，该领域仍然没有针对任何包含高性能共享内存并发原语的通用高级语言的并发语义提出可信的提议。

即使在定义弱排序硬件（忽略软件和编译器优化的复杂性）语义时，情况也不是很顺利。2018年，Sizhuo Zhang等人发表的论文“Constructing a Weak Memory Model”记述了更近期的事件：

Sarkar在2011年发布了POWER的操作模型，Mador-Haim等人在2012年发布了一个公理模型，该模型被证明与操作模型相匹配。然而，在2014年，Alglave等人表明原始操作模型以及相应的公理模型排除了在POWER机器上新观察到的行为。再举一个例子，在2016年，Flur等人给出了ARM的操作模型，没有相应的公理模型。一年后，ARM在其ISA手册中发布了一个修订版，明确禁止Flur模型允许的行为，这导致了另一个提议的ARM内存模型。显然，根据经验将弱内存模型形式化容易出错且具有挑战性。

在过去十年中，一直致力于定义和规范这一切的研究人员非常聪明、有才华和坚持不懈，我并不是要通过指出结果中的不足来贬低他们的努力和成就。我从这些中得出的结论是，即使没有争用，指定线程程序的确切行为的问题也非常微妙和困难。今天，即使是最优秀和最聪明的研究人员似乎也无法理解它。即使不是这样，当日常开发人员能够理解时，由编程语言定义效果最好，而无需花费十年时间研究并发程序的语义。

C, Rust和Swift内存模型 {#crust}

C11也采用了C++11内存模型，使其成为C/C++11内存模型。

Rust 1.0.0于2015年和Swift 5.3于2020年都完全采用了C/C++内存模型，包括DRF-SC或Catch Fair以及所有原子类型和原子围栏。

这两种语言都采用了C/C++模型也就不足为奇了，因为它们都是基于C/C++编译器工具链（LLVM）构建的，并强调与C/C++代码的紧密集成。

硬件题外话：高效的顺序一致性原子 {#sc}

早期的多处理器架构具有多种同步机制和内存模型，具有不同程度的可用性。在这种多样性中，不同同步抽象的效率取决于它们与架构提供的内容的映射程度。为了构建顺序一致的原子变量的抽象，有时唯一的选择是使用比绝对必要的更多且成本更高的屏障，尤其是在ARM和POWER上。

随着C、C++和Java都提供了相同的顺序一致同步原子抽象，硬件设计师有必要使这种抽象高效。ARMv8架构（包括32位和64位）引入了 ldar 和 stlr 加载和存储指令，提供了直接的实现。在2017年的一次演讲中，Herb Sutter 声称IBM已批准他这样说，他们打算在未来的POWER实现中也提供某种更高效的顺序一致原子支持，给程序员“更少的理由使用松散原子”。我不知道这是否发生了，尽管到2021年，POWER似乎已经变得比ARMv8不那么重要。

这种收敛的效果是，顺序一致的原子现在已经被很好地理解，并且可以在所有主要硬件平台上有效地实现，使它们成为编程语言内存模型的良好目标。

JavaScript内存模型 (2017) {#javascript}

您可能会认为JavaScript（一种众所周知的单线程语言）不需要担心内存模型，当代码在多个处理器上并行运行时会发生什么。我当然知道。但你我都错了。

JavaScript有web workers，允许在另一个线程中运行代码。最初设想的情况下，workers仅通过显式消息复制与主JavaScript线程通信。由于没有共享的可写内存，因此不需要考虑数据竞争等问题。然而，ECMAScript 2017（ES2017）添加了 SharedArrayBuffer 对象，使主线程和workers可以共享一块可写内存。为什么要这样做？在提案的早期草案中，列出的第一个原因是将多线程C++代码编译为JavaScript。

当然，拥有共享的可写内存还需要定义用于同步的原子操作和内存模型。JavaScript在三个重要方面与C++不同：

  • 首先，它将原子操作限制为仅按顺序一致的原子。其他原子可以编译为顺序一致的原子，可能会降低效率，但不会降低正确性，并且只有一种可以简化系统的其余部分。

  • 其次，JavaScript不采用 “DRF-SC或Catch Fire”。相反，它像Java一样，仔细定义了竞争访问的可能结果。理由与Java非常相似，特别是安全性。允许竞争读取返回任何值（可以说是鼓励）实现返回不相关的数据，这可能导致在运行时泄漏私人数据。

  • 第三，部分原因是JavaScript为竞争的程序提供了语义，它定义了当对同一内存位置使用原子和非原子操作时，以及当使用不同大小的访问访问同一内存位置时会发生什么。

精确定义竞争程序的行为会导致松散内存语义的常见复杂性，以及如何禁止out-of-air读取等。除了这些挑战（与其他地方基本相同）之外，ES2017定义还存在两个有趣的错误，这些错误是由于与新ARMv8原子指令的语义不匹配而引起的。这些例子改编自Conrad Watt等人2020年的论文“修复和机械化JavaScript宽松内存模型””。

正如我们在上一节中提到的，ARMv8添加了 ldar 和 stlr 指令，提供顺序一致的原子加载和存储。这些是针对C++的，它不定义任何具有数据竞争的程序的行为。因此，不出所料，这些指令在竞争程序中的行为不符合ES2017作者的期望，特别是它不符合ES2017对竞争程序行为的要求。

litmus测试：ES2017在ARMv8上读取

这个程序（使用原子）可以看到 r1 = 0, r2 = 1 吗？


// Thread 1           // Thread 2
x = 1                 y = 1
r1 = y                x = 2 (non-atomic)
                      r2 = x

C++：是（数据竞争，可以做任何事）

Java：无法编写程序。

ARMv8使用 ldar 和 stlr：是

ES2017:否！（与ARMv8相矛盾）

在这个程序中，所有的读取和写入都是顺序一致的原子操作，除了 x = 2：线程1使用原子存储写入 x = 1，但线程2使用非原子存储写入 x = 2。在C++中，这是数据竞争，所以一切都无法预料。在Java中，这个程序是不能写的：x 要么被声明为 volatile，要么不是；它不能只在某些时候以原子方式访问。在ES2017中，内存模型禁止 r1 = 0，r2 = 1。如果 r1 = y 读取0，线程1必须在线程2开始之前完成，在这种情况下，非原子的 x = 2 似乎发生在并覆盖 x = 1 之后，使得原子 r2 = x 读取2。这种解释看起来完全合理，但这不是ARMv8处理器的工作方式。

事实证明，对于等效的ARMv8指令序列，非原子写入 x 可以在原子写入 y 之前重新排序，因此该程序实际上会产生 r1 = 0，r2 = 1。这在C++中不是问题，因为竞争意味着程序可以做任何事情，但在ES2017中是一个问题，它将竞争行为限制在一组结果中，不包括 r1 = 0，r2 = 1。

由于ES2017的一个明确目标是使用ARMv8指令来实现顺序一致的原子操作，Watt等人报告说，他们建议的修正将在标准的下一个修订版中包括，预计会削弱竞争行为约束，使其刚好允许这种结果。（我不确定当时“下一个修订版”是指ES2020还是ES2021。）

Watt等人建议的更改还包括修复第二个错误，该错误由Watt、Andreas Rossberg和Jean Pichon-Pharabod首次发现，其中一个无数据竞争的程序在ES2017规范中没有被赋予顺序一致的语义。该程序如下：

litmus测试：ES2017无数据竞争程序

这个程序（使用原子）可以看到 r1 = 1, r2 = 2 吗？


// Thread 1           // Thread 2
x = 1                 x = 2
                      r1 = x
                      if (r1 == 1) {
                          r2 = x // non-atomic
                      }

在顺序一致的硬件上：否。

C++：我不是C++专家，无法肯定地说。（实际上，否。）

Java：无法编写程序。

ES2017：是！（与DRF-SC矛盾）。

在这个程序中，所有的读取和写入都是顺序一致的原子操作，除了标记的 r2 = x。该程序是无数据竞争的：非原子读取（必须涉及任何数据竞争）仅在 r1 = 1 时执行，这证明了线程1的 x = 1 发生在 r1 = x 之前，因此也发生在 r2 = x 之前。DRF-SC意味着程序必须以顺序一致的方式执行，因此 r1 = 1，r2 = 2 是不可能的，但ES2017规范允许它。

因此，ES2017对程序行为的规范同时过强（它不允许真实的ARMv8行为在竞争程序中发生）和过弱（它允许无竞争程序的非顺序一致行为）。如前所述，这些错误已经被修正。即便如此，这再次提醒我们，如何准确地使用前发生来指定无数据竞争和竞争程序的语义是多么微妙，以及如何使语言内存模型与底层硬件内存模型相匹配是多么微妙。

令人鼓舞的是，至少目前JavaScript避免了添加顺序一致的原子之外的任何其他原子，并抵制了“DRF-SC或Catch Fire”。结果是一个内存模型，可以作为C/C++有效编译目标，但更接近Java。

结论 {#conclusions}

看看C、C++、Java、JavaScript、Rust和Swift，我们可以做出以下观察：

  • 它们都提供了顺序一致的同步原子，用于协调并行程序的非原子部分。
  • 它们都旨在保证使用适当的同步实现无数据争用的程序的行为就像以顺序一致的方式执行一样。
  • Java直到Java 9引入 VarHandle 才引入了弱（获取/释放）同步原子操作。截至本文撰写时，JavaScript一直避免添加它们。
  • 它们都为程序提供了一种执行“有意”数据竞争的方法，而不会使程序的其余部分无效。在C、C++、Rust和Swift中，该机制是松散的、非同步的原子操作，这是一种特殊形式的内存访问。在Java中，该机制要么是普通内存访问，要么是Java 9 VarHandle “plain” 访问模式。在JavaScript中，该机制是普通内存访问。
  • 没有一种语言找到一种方法来正式禁止像out-of-air值这样的悖论，但都非正式地不允许它们。

与此同时，处理器制造商似乎已经接受了顺序一致同步原子的抽象对于高效实现很重要，并且正在开始这样做：ARMv8和RISC-V都提供了直接支持。

最后，为了理解这些系统并准确陈述它们的行为，已经进行了真正的大量验证和正式分析工作。特别令人鼓舞的是，Watt等人能够在2020年给出JavaScript重要子集的正式模型，并使用定理证明器来证明ARM、POWER、RISC-V和x86-TSO编译的正确性。

在第一个Java内存模型诞生25年后，经过几个世纪人力的研究工作，我们可能开始能够将整个内存模型正式化。也许，有一天，我们也会完全理解他们。

本系列的下一篇文章是 “更新Go内存模型”。

致谢 {#acknowledgements}

这一系列的文章从与我很幸运在Google共事的一长串工程师的讨论和反馈中受益匪浅。我感谢他们。我对任何错误或不受欢迎的观点承担全部责任。

若无特殊声明，本人原创文章以 CC BY-SA 4.0许可协议 提供。

blog