Go
by smallnest

[译]编程语言内存模型

这是Russ Cox的第二篇Programming Language Memory Models。

如果你已经阅读了前一篇硬件内存模型,以及如果有Java内存模型或者C++内存模型的经验，本文还好理解，如果你没有相关经验，可能阅读起来比较费劲，建议先阅读一下相关的材料。论文有些词句比较难以理解，本人才学疏浅，有翻译不当之处欢迎批评指正。

编程语言内存模型回答了并行程序可以依靠什么行为以便它们的线程之间可以共享内存的问题。例如，考虑下面这个类似C语言的程序，其中x和done都从零开始：

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

程序试图通过变量x从线程1向线程2发送一条消息(x)，使用done作为信号，通知线程2消息已经准备好被接收。如果线程1和线程2都运行在自己的专用处理器上，并且都运行完成，那么这个程序是否保证能够按照预期完成并打印1？编程语言内存模型回答了这个问题，以及其它类似问题。

Although each programming language differs in the details, a few general answers are true of essentially all modern multithreaded languages, including C, C++, Go, Java, JavaScript, Rust, and Swift:

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

  • 首先，如果x和done是普通变量，那么线程2的循环可能永远不会停止。一种常见的编译器优化是在变量首次使用时将其加载到寄存器中，然后尽可能长时间地重用该寄存器，以便将来访问该变量。如果线程2在线程1执行之前将done复制到一个寄存器中，它可能会在整个循环中一直使用该寄存器，永远不会注意到线程1后来修改了done。
  • 其次，即使线程2的循环会停止，也就是观察到done == 1，它仍然可能打印x的值为0。编译器通常会根据优化试探法甚至是生成代码时使用哈希表或其他中间数据结构的方式，对程序读写进行重新排序。线程1的编译代码可能在done赋值之后而不是之前写入x，或者线程2的编译代码也可能在循环前读取x。

既然这个程序有并发问题，那么问题是如何修复它。

现代语言以原子变量(atomic variable)或原子操作(atomic operation)的形式提供特殊能力，允许程序同步其线程。如果我们使用一个原子变量实现done(或者用原子操作来操作它)，那么我们的程序保证会执行完成并打印1。使用原子变量或者原子操作会产生很多效果：

  • 线程1的编译代码必须确保对x的写入完成，并且在对done的写入可见之前对x的写入对其他线程可见。
  • 线程2的编译代码必须在循环的每次迭代中(重新)读取done。
  • 线程2的编译代码必须在读取done之后才读取x。
  • 编译后的代码必须做任何必要的事情来禁用可能会重新引入这些问题的硬件优化

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

在最初始的程序中，在编译器的代码重新排序之后，线程1可能会在线程2读取x的同时写x。这是data race问题。在修改后的程序中，原子变量done用于同步对x的访问:线程1现在不可能在线程2读取x的同时写入x。这个程序没有数据竞争。一般来说，现代语言保证了无数据竞争的程序总是以顺序一致（sequentially consistent）的方式执行，就好像来自不同线程的操作被随意地但没有重新排序地转移到单个处理器上一样。这是硬件内存模型的DRF-SC属性，在编程语言环境中采用。

另外，这些原子变量或原子操作更恰当应该称之为“同步原子”(synchronizing atomic)，在数据库的意义上，操作是原子的，允许同时进行读和写，就像以某种顺序按顺序运行一样:当使用原子时，普通变量上的竞争不是竞争。但更重要的是，atomic同步了程序的其余部分，提供了一种消除非原子数据竞争的方法。标准术语就是“atomic”，也就是这篇文章使用的属于。除非另有说明，请记住将“原子”理解为“同步原子”。

编程语言内存模型规定了程序员和编译器所需的额外细节，作为他们之间的约定。上面谈到的通用特征基本上适用于所有现代语言，但直到最近，事情才收敛到一点:在21世纪初，有明显更多的变种。即使在今天，各种语言在更多的排序问题上也有显著的差异，包括:

  • 原子变量们本身的排序保证是什么？
  • 变量是否既可以原子访问，有可以非原子访问？
  • 除了原子之外是否还有其它同步机制？
  • 是否存在不同步的原子操作？
  • 有数据竞争的程序有什么保证？

在做了一些准备之后，这篇文章的剩余部分将探讨不同的语言如何回答这些相关的问题，以及它们解决这些问题之道。这篇文章介绍探索路上的许多错误初始设计，强调我们仍然在学习啥是有效的方案，啥是无效的方案

硬件、Litmus Tests、Happens Before 和 DRF-SC

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

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

很难对不同的内存模型做出完全通用的比较。反过来我们可以关注特定的测试用例，称为Litmus Test。如果两个内存模型通过Litmus Test有不同的行为，那么可以证明它们是不同的，并且通常可以帮助我们判断，至少对于那个测试用例，一个模型比另一个模型是弱还是强。例如，这是我们之前检查的程序的Litmus Test:

1
2
3
4
5
6
7
8
9
10
Litmus Test: Message Passing
Can this program see r1 = 1, r2 = 0?
// Thread 1           // Thread 2
x = 1                 r1 = y
y = 1                 r2 = x
On sequentially consistent hardware: no.
On x86 (or other TSO): no.
On ARM/POWER: yes!
In any modern compiled language using ordinary variables: yes!

和前一篇文章一样，我们假设每个例子一开始所有共享变量都为零。rN这个名字表示私有存储，如寄存器或函数变量；像x和y这样的名称是共享(全局)变量。我们问在执行结束时，寄存器的特定设置是否存在可能。在回答硬件的litmus test时，我们假设没有编译器对线程中发生的事情进行重新排序:清单中的指令被直接翻译成汇编指令，交给处理器执行。

结果r1 = 1，r2 = 0代表原始程序的线程2完成了循环(这里简化了循环，而是简单的使用y进行赋值)，但随后打印0。这个结果在程序操作的任何顺序一致的交替执行中是不可能的。对于汇编语言版本，在x86上打印0是不可能的，尽管由于处理器本身的重新排序优化，在ARM和POWER等更宽松的架构上打印0是可能的。在现代语言中，编译期间可能发生的重新排序使得这种结果成为可能，不管底层硬件是什么。

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

例如，这里描述了一个程序在两个线程上的短暂执行；像以前一样，假设每个处理器都有自己的专用处理器:

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

不同处理器上的两个事件，如果不是按照happens-before的顺序排序，可能会同时发生:确切的顺序搞不清楚。我们说它们同时执行。数据竞争（data race）是指对一个变量的写操作与对同一变量的读操作或写操作同时执行。提供DRF-SC的处理器保证没有数据竞争的程序行为就像它们在一个顺序一致的架构上运行一样。这是在现代处理器上编写正确的多线程汇编程序的基本保证。

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

编译器和优化

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

人们普遍认为，编译器几乎可以任意地对普通的内存读写进行重新排序，前提是重新排序不能改变观察到的单线程代码执行的效果。例如，考虑这个程序:

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

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

如上所述，如此自由地重新排序读写的能力使得普通编译程序的保证至少和ARM/POWER宽松内存模型一样弱，因为编译程序无法通过消息传递的litmus test。事实上，编译程序的保证更弱。

在上一篇硬件内存模型的文章中，我们将一致性（coherence）看作是ARM/POWER架构所能保证的一个例子:

1
2
3
4
5
6
7
8
9
10
11
Litmus Test: Coherence
Can this program see r1 = 1, r2 = 2, r3 = 2, r4 = 1?
(Can Thread 3 see x = 1 before x = 2 while Thread 4 sees the reverse?)
// Thread 1    // Thread 2    // Thread 3    // Thread 4
x = 1          x = 2          r1 = x         r3 = x
                              r2 = x         r4 = x
On sequentially consistent hardware: no.
On x86 (or other TSO): no.
On ARM/POWER: no.
In any modern compiled language using ordinary variables: yes!

所有现代硬件都保证一致性，这也可以看作是对单个存储单元的操作的顺序一致性。在这个程序中，一个写操作必须覆盖另一个，并且整个系统必须就哪个是哪个达成一致。事实证明，由于编译过程中程序的重新排序，现代语言甚至不能提供一致性。

假设编译器对线程4中的两次读取进行了重新排序，然后指令按照以下顺序交替运行:

1
2
3
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，它不允许引入新的读或写的优化，即使这些优化在单线程代码中是有效的。

例如，考虑下面的代码:

1
2
3
4
5
if(c) {
	x++;
} else {
	... lots of code ...
}

有一个if语句，在else中有很多代码，在if主体中只有一个x++。拥有更少的分支并彻底消除if体可能更快。如果我们编写代码有问题，我们可以在if之前运行了x++,然后在else中用x--进行调整。也就是说，编译器可能会考虑将该代码重写为:

1
2
3
4
5
x++;
if(!c) {
	x--;
	... lots of code ...
}

这是安全的编译器优化吗？在单线程程序中，是的。在一个多线程程序中，当c为false时，x与另一个线程共享，答案是否: 优化会在x上引入一个原始程序中没有的数据

这个例子来源于Hans Boehm 2004年的论文Threads Cannot Be Implemented As a Library中的一个例子，它说明了语言不能对多线程执行的语义保持沉默。

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

原始的Java内存模型 (1996)

Java是第一个试图写下多线程程序保证的主流语言。它包括互斥体(mutex)，并定义了它们隐含的内存排序要求。它还包括“volatile”原子变量: volatile变量的所有读和写都需要直接在主内存中按程序顺序执行，使得对volatile变量的操作以顺序一致的方式进行。最后，Java制定了(或者至少试图制定)具有数据竞争的程序的行为。其中的一部分是为普通变量规定一种一致性的形式，我们将在下面详细讨论。不幸的是，在Java语言规范(1996)的第一版中，这种尝试至少有两个严重的缺陷。凭借后见之明和我们已经做好的准备，它们很容易解释。当时，它们远没有那么明显被发现。

Atomic 需要同步

第一个缺陷是volatile原子变量是不同步的，所以它们无助于消除程序其余部分的竞争。我们在上面看到的消息传递程序的Java版本是:

1
2
3
4
5
6
int x;
volatile int done;
// Thread 1           // Thread 2
x = 1;                while(done == 0) { /* loop */ }
done = 1;             print(x);

因为done被声明为volatile，所以循环肯定会结束: 编译器不能将它缓存在寄存器中并导致无限循环。但是，程序不能保证打印1。编译器没有被禁止重新排序对x和done的访问，也没有被要求禁止硬件做同样的事情。

因为Java volatile是非同步原子，所以您不能使用它们来构建新的同步原语。从这个意义上说，最初的Java内存模型太弱了。

一致性与编译器优化不兼容

初的Java内存模型也太强了: 强制一致性 —— 一旦线程读取了内存位置的新值，它就不能再读取旧值——不允许基本的编译器优化。前面我们讨论了重新排序读操作会如何破坏一致性，但是你可能会想，好吧，不要重新排序读操作。这里有一个更微妙的方法，可以通过另一个优化来打破一致性:公共子表达式消除。考虑一下这个Java程序:

考虑一下这个Java程序:

1
2
3
4
5
// p and q may or may not point at the same object.
int i = p.x;
// ... maybe another thread writes p.x at this point ...
int j = q.x;
int k = p.x;

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

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

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

新的Java内存模型 (2004)

由于这些问题，并且因为最初的Java内存模型甚至对于专家来说都很难理解，Pugh和其他人开始努力为Java提供一个新的内存模型。该模型后来成为JSR-133，并在2004年发布的Java 5.0中被采用。规范参考是Jeremy Manson, Bill Pugh和Sarita Adve的Java内存模型(2005)，Jeremy Manson的博士论文中有更多细节。新模型遵循DRF-SC方法:保证无数据竞争的Java程序以顺序一致的方式执行。

同步原子和其它操作

正如我们前面看到的，要编写一个无数据竞争的程序，程序员需要同步操作，这些同步操作可以建立happens-before关系，以确保一个线程不会在另一个线程读取或写入非原子变量的同时写入该变量。在Java中，主要的同步操作有:

  • 线程的创建发生在(happen before)它的第一个动作之前
  • mutex m的unlock发生在m的后续lock之前
  • 写volatile变量v发生在后续读取v之前

“subsequent”(“后续”)`是什么意思？Java定义了所有锁、解锁和volatile变量访问的行为，就好像它们发生在一些顺序一致的中断中，给出了整个程序中所有这些操作的总顺序。“后续”是指总顺序中的较晚执行。也就是说:锁、解锁和volatile变量访问的总顺序定义了后续的含义，然后后续定义了特定执行创建了happen before关系，然后happend before关系定义了该特定执行是否有数据竞争。如果没有数据竞争，那么执行就会以顺序一致的方式进行。

事实上， volatile访问必须表现得好像在某种总排序中一样，这意味着在存储缓冲区litmus test中，不能出现r1 = 0和r2 = 0的结果:

1
2
3
4
5
6
7
8
9
10
Litmus Test: Store Buffering
Can this program see r1 = 0, r2 = 0?
// Thread 1           // Thread 2
x = 1                 y = 1
r1 = y                r2 = x
On sequentially consistent hardware: no.
On x86 (or other TSO): yes!
On ARM/POWER: yes!
On Java using volatiles: no.

在Java中，对于volatile变量x和y，读取和写入不能被重新排序:一个写入必须排在第二位，第二个写入之后的读取必须看到第一个写入。如果我们没有顺序一致的要求——比如说，如果只要求volatile是一致的——两次读取可能会错过写入。

这里有一个重要但微妙的点:所有同步操作的总顺序与happen-before关系是分开的。在程序中的每个锁、解锁或volatile变量访问之间，在一个方向或另一个方向上不存在happen-before关系:从写入到观察写入的读取，您只获得了happen-before的关系。例如，不同互斥体的锁定和解锁之间没有happen-before关系。

有数据竞争的程序的语义

DRF-SC只保证没有数据竞争的程序的顺序一致行为。新的Java内存模型和最初的一样，定义了有数据竞争的程序的行为，原因有很多:

  • 支持Java的一般安全（security）和安全保障（safety guarantee）。
  • 让程序员更容易发现错误。
  • 使攻击者更难利用问题，因为由于数据竞争的原因可能造成的损失更有限。
  • 让程序员更清楚他们的程序是做什么的。

新模型不再依赖于一致性，而是重新使用了happens-before关系(已经用来决定程序是否有竞争)来决定竞争读写的结果。

Java的具体规则是，对于word大小或更小的变量，对变量(或字段)x的读取必须看到对x的某一次写入所存储的值。如果读取r观察到对x的写入w，那么r不发生在w之前。这意味着r可以观察发生在r之前的所有写入，并且它可以观察与r竞争的写入。

使用happens-before，结合同步原子(volatile)就可以建立新的happen before关系，是对原始Java内存模型的重大改进。它为程序员提供了更多有用的保证，并使大量重要的编译器优化得到了明确的允许。这个模型至今仍然是Java的内存模型。也就是说，这仍然是不完全正确的:在试图定义竞争程序的语义时，使用before-before是有问题的。

happen-before不排除语无伦次(incoherence)

定义程序语义的“happen-before”关系的第一个问题与一致性有关(有一次!).(以下例子摘自Jaroslav Ševčík 和 David Aspinall的论文《论Java内存模型中程序转换的有效性》(2007年))。)

这里有一个三线程的程序。让我们假设线程1和线程2已知在线程3开始之前完成。

1
2
3
4
5
6
7
8
9
10
// 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在持有mutex m1时写入x = 1。线程2在持有 mutex m2时写入x = 2。这些是不同的mutex，所以两个写操作是竞争的。然而，只有线程3读取x，并且它是在获取两个mutex后读取的。对r1的读取可以是读也可以是写:两者都发生在它之前，并且都不会完全覆盖另一个。通过相同的参数，读入r2可以读或写。但是严格来说，Java内存模型中没有任何东西说两次读取必须一致：从技术上讲，r1和r2可以读取不同的x值。也就是说，这个程序可以以r1和r2持有不同的值结束。当然，没有真正的实现会产生不同的r1和r2。互斥意味着这两次读取之间没有写操作发生。他们必须得到相同的值。但是内存模型允许不同读取值的事实表明，从某种技术角度来说，它并没有精确地描述真实的Java实现。

情况变得更糟。如果我们在两个读数之间再加一个指令，x = r1，会怎么样:

1
2
3
4
5
6
7
8
9
10
11
// 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 test，使用普通的(非volatile)Java变量:

1
2
3
4
5
6
7
Litmus Test: Racy Out Of Thin Air Values
Can this program see r1 = 42, r2 = 42?
// Thread 1           // Thread 2
r1 = x                r2 = y
y = r1                x = r2
(Obviously not!)

这个程序中的所有变量都像往常一样从零开始，然后这个程序在一个线程中有效地运行y = x，在另一个线程中运行x = y。x和y最终能变成42吗？在现实生活中，显然不能。但为什么不呢？内存模型并没有否定这个结果。

假设“r1 = x”的读数是42。那么“y = r1”会将42写入y，然后竞争“r2 = y”会读取42，导致“x = r2”写入42到x，且write与原始“r1 = x”竞争(因此可被原始“r1 = x”观察到)，看起来证明原始假设是正确的。在这个例子中，42被称为无中生有的值，因为它看起来没有任何理由，但随后用循环逻辑证明了自己。如果内存在当前的0之前曾经持有42，而硬件错误地推测它仍然是42，会怎么样？这种猜测可能会成为一个自我实现的预言。(在Spectre和相关攻击显示出硬件是如何不断进步的之前，这个论点似乎更加牵强。即便如此，没有一种硬件是这样凭空创造值的。)

很明显，这个程序不能以r1和r2设置为42结束，但是happens-before本身并不能解释为什么不能这样做。这再次表明存在某种不完整性。新的Java内存模型花费了大量时间来解决这种不完整性，稍后将对此进行更详细的描述。

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

1
2
3
4
5
6
7
8
Litmus Test: Non-Racy Out Of Thin Air Values
Can this program see r1 = 42, r2 = 42?
// Thread 1           // Thread 2
r1 = x                r2 = y
if (r1 == 42)         if (r2 == 42)
    y = r1                x = r2
(Obviously not!)

由于x和y从零开始，任何顺序一致的执行都不执行写操作，所以这个程序没有写操作，所以没有竞争。不过，同样，仅happen-before并不排除这样的可能性，假设r1 = x看到竞争不是write，然后根据这个假设，两个条件最终都为真，x和y最终都是42。这是另一种无中生有的价值，但这一次是在没有竞争的程序中。任何保证DRF-SC的模型都必须保证这个程序只在末尾看到全零，然而happens-before并没有解释为什么。

Java内存模型花了很多我不想赘述的话来试图排除这些类型的假设。不幸的是，五年后，Sarita Adve and Hans Boehm对这个内存模型有这样的评价:

Prohibiting such causality violations in a way that does not also prohibit other desired optimizations turned out to be surprisingly difficult. … After many proposals and five years of spirited debate, the current model was approved as the best compromise. … Unfortunately, this model is very complex, was known to have some surprising behaviors, and has recently been shown to have a bug.

以一种不妨碍其他期望的优化的方式来禁止这种因果关系冲突，结果令人惊讶地难以实现。……经过许多提议和五年的激烈辩论，目前的模式被认为是最好的折衷方案。……不幸的是，这个模型非常复杂，已知有一些令人惊讶的缺点，最近被证明有一个错误。

(Adve 和 Boehm, “Memory Models: A Case For Rethinking Parallel Languages and Hardware,” August 2010)

C++11 内存模型 (2011)

让我们把Java放在一边，研究C++。受Java新内存模型明显成功的启发，许多同样的人开始为C++定义一个类似的内存模型，最终在C++11中采用。与Java相比，C++在两个重要方面有所不同。首先，C++对具有数据竞争的程序不做任何保证，这似乎消除了对Java模型复杂性的需求。其次，C++提供了三种原子性:强同步(“顺序一致”)、弱同步(“acquire/release”,、coherence-only)和无同步(“relaxed”，用于隐藏竞争)。“relaxed”的原子性重新引入了Java关于定义什么是竞争程序的所有复杂性。结果是C++模型比Java更复杂，但对程序员的帮助更小。

C++11还定义了原子栅栏作为原子变量的替代，但是它们并不常用，我不打算讨论它们。

DRF-SC 还是 着火(Catch Fire）

与Java不同，C++没有给有竞争的程序任何保证。任何有竞争的程序都属于“未定义的行为”。允许在程序执行的最初几微秒内进行竞争访问，从而在几小时或几天后导致任意的错误行为。这通常被称为“DRF-SC或着火”:如果程序没有数据竞争，它以顺序一致的方式运行，如果有数据竞争，它可以做任何事情，包括着火。

关于DRF-SC或Catch Fire的论点的更详细的介绍，参见Boehm，“内存模型原理”(2007) 和Boehm和Adve，“C++并发内存模型的基础”(2008)。

简而言之，这中情况有四个正当理由:

Briefly, there are four common justifications for this position:

  • C和C++已经充斥着未定义的行为，这是编译器优化横行的语言小角落，用户最好不要迟疑。多一个未定义行为又有多大的坏处？
  • 现有的编译器和库编写时没有考虑线程，以任意方式破坏了有竞争的程序。找到并修复所有的问题太难了，或者这个争论没有了，尽管还不清楚那些不固定的编译器和库是如何应对宽松的原子的。
  • 真正知道自己在做什么并希望避免未定义行为的程序员可以使用relaxed的原子。
  • 不定义竞争语义允许实现检测和诊断竞争并停止执行。

就我个人而言，最后一个理由是我认为唯一有说服力的，尽管我认为这个意思是说“允许使用竞争检测器”，而不是说“一个整数的竞争会使整个程序无效。”

这里有一个来自“内存模型原理”的例子，我认为它抓住了C++方法的本质以及它的问题。考虑这个程序，它引用了一个全局变量x。

1
2
3
4
5
6
7
8
9
10
11
12
13
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索引的表将开关编译成计算跳转，那么代码将从表的末尾索引并跳转到一个意外的地址，这可能非常糟糕。

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

题外话, C/C++的未定义行为

另外，C和C++坚持编译器对程序中的错误行为进行任意的行为的能力导致了真正荒谬的结果。例如，考虑这个程序，这是2017在推特上讨论的话题：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#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要么为空，要么为EraseAll。
  • 如果Do是Erasell，那么Do()与Erasell()相同。
  • 如果Do 是null, 那么Do()是未定义行为。我可以随意实现，包括作为EraseAll()无条件实现。
  • 因此，我可以将间接调用Do()优化为直接调用EraseAll()。
  • 当我处理这里的时候，我可能直接内联EraseAll。

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

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

你必须承认:前一个例子，局部变量i可能在if (i < 2)体的中途突然停止小于2的可能性似乎并不合适。

本质上，现代C和C++编译器假设没有程序员敢尝试未定义的行为。一个程序员写一个有bug的程序？不可思议！

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

Acquire/release atomic

C++采用了顺序一致的原子变量，很像(新的)Java的volatile变量(与C++ volatile没有关系)。在我们的消息传递示例中，我们可以将done声明为

1
atomic<int> done;

然后像使用普通变量一样使用done，就像在Java中一样。或者我们可以把一个普通的整型变量去掉。然后使用

1
atomic_store(&done, 1);

和：

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

去访问它。

无论哪种方式，完成的操作都参与原子操作的顺序一致的总顺序，并同步程序的其余部分。

C++还添加了较弱的原子，可以使用atomic_store_explicit和atomic_load_explicit以及附加的memory排序参数来访问这些原子。使用memory_order_seq_cst使显式调用等效于上面较短的调用。

较弱的原子称为acquire/release原子，一个release如果被后来的acquire观察到，那么就创建了一个happen-before的关系(从release到acquire)。这个术语意在唤起mutex:release就像unlock mutex，acquire就像lock同一个mutex。release之前执行的写入必须对后续acquire之后执行的读取可见，就像unlock mutex之前执行的写入必须对后来unlock mutex之后执行的读取可见一样。

The terminology is meant to evoke mutexes: release is like unlocking a mutex, and acquire is like locking that same mutex. The writes executed before the release must be visible to reads executed after the subsequent acquire, just as writes executed before unlocking a mutex must be visible to reads executed after later locking that same mutex.

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

1
atomic_store(&done, 1, memory_order_release);

和

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

它仍然是正确的。但不是所有的程序都会这样

回想一下，顺序一致的原子要求程序中所有原子的行为与执行的一些全局交替执行(全局顺序)一致。acquire/release原子不会。它们只需要对单个内存位置的操作进行顺序一致的交替执行。也就是说，它们只需要一致性。结果是，一个使用具有多个存储位置的acquire/release原子的程序可能会观察到无法用程序中所有acquire/release原子的顺序一致的交替来解释的执行，这可以说是违反了DRF-SC！

为了说明不同之处，这里再举一个存储缓冲区的例子:

1
2
3
4
5
6
7
8
9
10
11
12
Litmus Test: Store Buffering
Can this program see r1 = 0, r2 = 0?
// Thread 1           // Thread 2
x = 1                 y = 1
r1 = y                r2 = x
On sequentially consistent hardware: no.
On x86 (or other TSO): yes!
On ARM/POWER: yes!
On Java (using volatiles): no.
On C++11 (sequentially consistent atomics): no.
On C++11 (acquire/release atomics): yes!

C++顺序一致的原子与Java的volatile相匹配。但是acquire-release原子在x的顺序和y的顺序之间没有强加任何关系。特别地，允许程序表现得好像r1 = y发生在y = 1之前，而同时r2 = x发生在x = 1之前，使得r1 = 0，r2 = 0与整个程序的顺序一致性相矛盾。为什么要引入这些较弱的获取/发布原子？可能是因为它们是x86上的普通内存操作。

请注意，对于观察特定写入的一组给定的特定读取，C++顺序一致原子和C++ acquire/release原子创建相同的happen-before关系。它们之间的区别在于，顺序一致的原子不允许观察特定写入的某些特定读取集，但acuqire/release原子允许这些特定读取集。一个这样的例子是导致存储缓冲测试出现r1 = 0，r2 = 0的结果。

acquire/release原子在实践中不如提供顺序一致性的原子有用。这里有一个例子。假设我们有一个新的同步原语，一个具有通知和等待两种方法的一次性条件变量。为了简单起见，只有一个线程会调用Notify，只有一个线程会调用Wait。我们想安排Notify在另一个线程还没有等待的时候是无锁的。我们可以用一对原子整数来实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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 ...
}

这段代码的重要部分是在检查waiting之前notify设置done为1, 为wait在检查done之前设置waiting为1,因此并发调用notify和wait不会导致notify立即返回并等待休眠。但是使用C++ acquire/release原子，它们可以。而且它们可能只需要很少的几率发生，使得这种错误很难重现和诊断。(更糟糕的是，在像64位ARM这样的一些架构上，实现acquire/release原子的最佳方式是顺序一致的原子，因此您可能会编写在64位ARM上运行良好的代码，但在移植到其他系统时才发现它是不正确的。)

基于这种理解，“acquire/release”对于这些原子来说是一个不幸的名字，因为顺序一致的原子做同样的acquire和release。不同之处在于顺序一致性的丧失。称这些为“一致性”原子可能更好。太迟了。

Relaxed atomic

C++并没有仅仅停留在连贯的获取/发布原子上。它还引入了非同步原子，称为relaxed原子。这些原子根本没有同步效果——它们没有创建先发生的边——并且它们根本没有排序保证。事实上，宽松原子读/写和普通读/写没有区别，除了宽松原子上的竞争不被认为是竞争，不能着火。

C++没有停止与仅仅提供一致性的acquire/release原子。它还引入了非同步原子，称为relaxed原子(memory_order_relaxed)。这些原子根本没有同步效果——它们没有创建happens-before关系——并且它们根本没有排序保证。事实上，relaxed原子读/写和普通读/写没有区别，除了relaxed原子上的竞争不被认为是竞争，不能着火。

修改后的Java内存模型的大部分复杂性来自于定义具有数据竞争的程序的行为。如果C++采用DRF-SC或Catch Fire——实际上不允许有数据竞争的程序——意味着我们可以扔掉前面看到的所有奇怪的例子，那么C++语言规范将比Java语言规范更简单，那就太好了。不幸运的是，包括releaxed的原子最终保留了所有这些关注，这意味着C++11规范最终并不比Java简单。

像Java的内存模型一样，C++11的内存模型最终也是不正确的。考虑之前的无数据竞争计划:

1
2
3
4
5
6
7
8
9
10
11
Litmus Test: Non-Racy Out Of Thin Air Values
Can this program see r1 = 42, r2 = 42?
// Thread 1           // Thread 2
r1 = x                r2 = y
if (r1 == 42)         if (r2 == 42)
    y = r1                x = r2
(Obviously not!)
C++11 (ordinary variables): no.
C++11 (relaxed atomics): yes!

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

详情见论文，但在较高的层次上，C++11规范有一些正式规则，试图禁止无中生有的值，并结合了一些模糊的词语来阻止其他类型的有问题的值。这些正式的规则就是问题所在，因此C++14放弃了它们，只留下了模糊的词语。引用删除它们的基本原理，C++11公式证明是“既不充分的，因为它使人们基本上无法对内存顺序放松的程序进行推理，也严重有害，因为它可以说不允许在ARM和POWER等体系结构上对memory_order_relaxed的所有合理实现。”

综上所述，Java试图正式排除所有不合法的执行，但失败了。然后，借助Java的后知后觉，C++11试图正式地只排除一些不合法的执行，也失败了。C++14然后说什么都不正式。这不是正确的方向。

事实上，Mark Batty和其他人在2015年发表的一篇题为“编程语言并发语义的问题”的论文给出了这一发人深省的评估:

Disturbingly, 40+ years after the first relaxed-memory hardware was introduced (the IBM 370/158MP), the field still does not have a credible proposal for the concurrency semantics of any general-purpose high-level language that includes high-performance shared-memory concurrency primitives.

令人不安的是，在引入第一个relaxed内存硬件(IBM 370/158MP)40多年后，该领域仍然没有一个可信的提案来描述任何包含高性能共享内存并发原语的通用高级语言的并发语义。

甚至定义弱有序硬件的语义(忽略软件和编译器优化的复杂性)也不太顺利。张思卓等人在2018年发表的一篇名为《构建弱记忆模型》的论文讲述了最近发生的一些事情:

Sarkar et al. published an operational model for POWER in 2011, and Mador-Haim et al. published an axiomatic model that was proven to match the operational model in 2012. However, in 2014, Alglave et al. showed that the original operational model, as well as the corresponding axiomatic model, ruled out a newly observed behavior on POWER machines. For another instance, in 2016, Flur et al. gave an operational model for ARM, with no corresponding axiomatic model. One year later, ARM released a revision in their ISA manual explicitly forbidding behaviors allowed by Flur's model, and this resulted in another proposed ARM memory model. Clearly, formalizing weak memory models empirically is error-prone and challenging.

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

在过去的十年里，致力于定义和形式化所有这些的研究人员非常聪明、有才华和坚持不懈，我并不想通过指出结果中的不足来贬低他们的努力和成就。我从这些简单的结论中得出结论，这个指定线程程序的确切行为的问题，即使没有竞争，也是难以置信的微妙和困难。如今，即使是最优秀、最聪明的研究人员似乎也无法理解这一点。即使不是，编程语言定义在日常开发人员可以理解的情况下效果最好，而不需要花费十年时间研究并发程序的语义。

C, Rust 和 Swift 的内存模型

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

2015年的Rust 1.0.0和2020年的Swift 5.3都整体采用了C/C++内存模型，拥有DRF-SC或Catch Fire以及所有的原子类型和原子栅栏。

毫不奇怪，这两种语言都采用了C/C++ 模型，因为它们建立在C/C++编译器工具链(LLVM)上，并强调与C/C++代码的紧密集成。

硬件题外话： 有效的顺序一致性atomic

早期的多处理器体系结构有多种同步机制和内存模型，具有不同程度的可用性。在这种多样性中，不同同步抽象的效率取决于它们如何映射到架构所提供的内容。为了构造顺序一致的原子变量的抽象，有时唯一的选择是使用比严格必要的要多得多、贵得多的内存栅栏barriers，特别是在ARM和POWER上。

随着C、C++和Java都提供了这种顺序一致性同步原子的抽象，硬件设计者就应该让这种抽象变得高效。ARMv8架构(32位和64位)引入了ldar和stlr load和store指令，提供了直接的实现。在2017年的一次谈话中，赫伯·萨特声称，IBM已经批准了他的说法，他们希望未来的POWER实现对顺序一致的原子也有某种更有效的支持，这让程序员“更没有理由使用relaxed的原子。”我不知道是否发生了这种情况，尽管在2021年，POWER的相关性远不如ARMv8。

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

JavaScript 内存模型 (2017)

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

JavaScript有web workers，它允许在另一个线程中运行代码。按照最初的设想，工作人员只通过显式的消息复制与主JavaScript线程进行通信。没有共享的可写内存，就没有必要考虑像数据竞争这样的问题。然而，ECMAScript 2017 (ES2017)增加了SharedArrayBuffer对象，它让主线程和工作线程共享一块可写内存。为什么要这样做？在提案的早期草稿中，列出的第一个原因是将多线程C++代码编译成JavaScript。

当然，共享可写内存还需要定义同步的原子操作和内存模型。JavaScript在三个重要方面偏离了C++:

  • 首先，它将原子操作限制在顺序一致的原子上。其他原子可以被编译成顺序一致的原子，可能会损失效率，但不会损失正确性，只有一种原子可以简化系统的其余部分。
  • 第二，JavaScript不采用“DRF-SC或着火。”相反，像Java一样，它仔细定义了竞争访问的可能结果。其原理与Java非常相似，尤其是安全性。允许竞争read返回任何值允许(可以说是鼓励)实现返回不相关的数据，这可能会导致运行时私有数据的泄漏。
  • 第三，部分是因为JavaScript为竞争程序提供了语义，它定义了当原子和非原子操作在同一个内存位置使用时，以及当使用不同大小的访问访问同一个内存位置时会发生什么。

精确定义racy程序的行为会导致relaxed内存语义的复杂性，以及如何禁止无中生有的读取和类似情况。除了这些与其他地方基本相同的挑战之外，ES2017定义还有两个有趣的错误，它们是由于与新的ARMv8原子指令的语义不匹配而引起的。这些例子改编自康拉德·瓦特等人2020年的论文“Repairing and Mechanising the JavaScript Relaxed Memory Model.”

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

1
2
3
4
5
6
7
8
9
10
11
Litmus Test: ES2017 racy reads on ARMv8
Can this program (using atomics) see r1 = 0, r2 = 1?
// Thread 1           // Thread 2
x = 1                 y = 1
r1 = y                x = 2 (non-atomic)
                      r2 = x
C++: yes (data race, can do anything at all).
Java: the program cannot be written.
ARMv8 using ldar/stlr: yes.
ES2017: no! (contradicting 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之后并覆盖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等人提出的修改还包括对第二个bug的修复，第一个bug是由Watt、Andreas Rossberg和Jean Pichon-pharabad提出的，其中一个无数据竞争的程序没有按照ES2017规范给出顺序一致的语义。该程序由下式给出:

1
2
3
4
5
6
7
8
9
10
11
12
13
Litmus Test: ES2017 data-race-free program
Can this program (using atomics) see r1 = 1, r2 = 2?
// Thread 1           // Thread 2
x = 1                 x = 2
                      r1 = x
                      if (r1 == 1) {
                          r2 = x // non-atomic
                      }
On sequentially consistent hardware: no.
C++: I'm not enough of a C++ expert to say for sure.
Java: the program cannot be written.
ES2017: yes! (violating DRF-SC).

在这个程序中，所有的读和写都是顺序一致的原子，除了r2 = x，标记为。这个程序是无数据竞争的:非原子读取必须参与任何数据竞争，只有当r1 = 1时才执行，这证明线程1的x = 1发生在r1 = x之前，因此也发生在r2 = x之前。DRF-SC意味着程序必须以顺序一致的方式执行，因此r1 = 1，r2 = 2是不可能的，但ES2017规范允许这样做。

因此，ES2017程序行为规范同时太强(它不允许racy程序的真实ARMv8行为)和太弱(它允许无竞争程序的非顺序一致行为)。如前所述，这些错误已经改正。即便如此，这也再次提醒我们，精确地使用以前发生的事情来指定无数据竞争程序和活泼程序的语义是多么微妙，以及将语言内存模型与底层硬件内存模型相匹配是多么微妙。

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

结论

看看C、C++、Java、JavaScript、Rust和Swift，我们可以得出以下结论:

  • 它们都提供顺序一致的同步原子，用于协调并行程序的非原子部分。
  • 它们的目的都是确保程序使用适当的同步来避免数据竞争，就像以顺序一致的方式执行一样。
  • Java和JavaScript避免了引入弱(acquire/release)同步原子，这似乎是为x86量身定制的。
  • 它们都为程序提供了一种方式来执行“有意的”数据竞争，而不会使程序的其余部分无效。在C、C++、Rust和Swift中，这种机制是relaxed，非同步原子，一种特殊的内存访问形式。在Java和JavaScript中，这种机制就是普通的内存访问。
  • 没有一种语言找到了正式禁止悖论的方法，比如无中生有的值，但是所有语言都非正式地禁止它们。

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

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

在第一个Java内存模型问世25年后，经过许多人世纪的研究努力，我们可能开始能够形式化整个内存模型。也许，有一天，我们也会完全理解他们。

【本系列的下一篇文章，关于Go内存模型，计划在7月12日那一周发布。】

感谢

这一系列的帖子从我有幸在谷歌工作的一长串工程师的讨论和反馈中受益匪浅。我感谢他们。我对任何错误或不受欢迎的意见负全部责任。