本文是 Russ Cox 大佬撰写的 Hardware Memory Models 的姊妹篇,发布于 2021年7月6日,原文链接: Programming Language Memory Models
LLM 使用声明:本文翻译重度依赖 LLM 技术。有英文基础的读者可对照阅读原始材料。
编程语言内存模型(内存模型,第二部分)
Table of Contents
引言:并行程序的"行为守则"
编程语言内存模型回答这样一个问题:并行程序在线程间共享内存时,能指望什么样的行为保障?
举个例子,下面这个类C程序中,x
和done
的初始值都是0:
// 线程 1 // 线程 2
x = 1; while(done == 0) { /* loop */ }
done = 1; print(x);
这段代码试图把消息x
从线程1传递给线程2,用done
作为"消息就绪"的信号。如果两个线程各自跑在专属处理器上都执行完毕,程序能不能如预期那样结束并打印1?编程语言内存模型就是回答这类问题的。
虽然每种语言的具体细节不同,但下面几条共性几乎适用于所有现代多线程语言,包括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 variables)或原子操作(atomic operations)让程序可以同步线程。如果我们把done
改成原子变量(或者在某些语言里用原子操作操纵它),那么程序就保证能结束并打印1。把done
原子化会带来一系列效果:
- 线程1的编译代码必须确保对
x
的写入完成且对其他线程可见,然后才让对done
的写入可见。 - 线程2的编译代码必须在每次循环时都(重新)读取
done
。 - 线程2的编译代码必须在读完
done
之后才读取x
。 - 编译代码必须禁用那些可能重新引入上述问题的硬件优化。
最终结果是,把done
变成原子变量就能让程序按预期工作,成功把x
的值从线程1传递到线程2。
在原始程序里,经过编译器重排后,线程1可能在写x
的同时线程2正在读x
,这就是数据竞争(data race)。在修改后的程序里,原子变量done
起到了同步x
访问的作用:线程1写x
的瞬间线程2不可能同时读x
。程序变得无数据竞争(data-race-free)。
现代语言普遍保证:无数据竞争的程序总是按顺序一致的方式执行,仿佛不同线程的操作被任意交错(但不重排)到单个处理器上。这就是硬件内存模型里提到的DRF-SC属性,在编程语言语境下同样成立。
顺便说一句,这些原子变量/操作其实应叫"同步化原子(synchronizing atomics)"——它们确实具备数据库意义上的原子性,即看似串行的并发读写;但更关键的是它们能同步程序其他部分,消除对非原子数据的竞争。不过业界都叫"原子",本文也如此。记住把"原子"读成"同步化原子"就对了。
编程语言内存模型精确规定了程序员和编译器各自的责任,是二者之间的契约。前文的概述对几乎所有现代语言都成立,但各家达成今日共识其实没几年——2000年代初的情况可五花八门。即便今天,在以下二阶问题上语言间仍有明显差异:
- 原子变量自身的排序保证是什么?
- 一个变量能否同时被原子操作和普通操作访问?
- 除了原子操作,还有哪些同步机制?
- 是否存在不带同步语义的“原子”操作?
- 带竞争的程序是否还有点保底保证?
下面我们先做点铺垫,然后逐一细看各语言如何回答这些问题,以及它们走过的弯路——提醒后来者我们仍在摸石头过河。
硬件、Litmus测试、Happens-Before与DRF-SC
在深入任何具体语言前,先概括一下从硬件内存模型一文需回顾的知识点:
不同架构对指令重排的容忍度不同,同一份并行代码在不同处理器上可见的结果集合也不同。黄金标准是顺序一致性(sequential consistency),即执行效果仿佛各处理器的程序被某种顺序串行交织到单核上。开发者最容易推理,但今日没有主流架构提供它,因为弱保证能带来性能红利。
比较内存模型时很难做绝对化综述,不如聚焦具体测试用例——litmus测试。若两模型对同一测试给出不同结果,就证明二者不同,通常也能看出谁更弱或更强。例如之前出现的经典例子:
Litmus测试:消息传递
程序能否看到 r1 = 1
, r2 = 0
?
// 线程 1 // 线程 2
x = 1 r1 = y
y = 1 r2 = x
在顺序一致硬件:不能;在x86(TSO):不能;在ARM/POWER:能;在任何现代编译语言用普通变量:能。
(同前,所有例子默认共享变量初值为0;rN
表示寄存器或局部存储;x
、y
等是不同共享全局变量;问程序结束时寄存器能否取到指定值。回答硬件行为时,假设指令就是列出来的汇编,无编译器重排。)
结果r1 = 1, r2 = 0
对应线程2跳出循环(因为y == 1
)却打印0。顺序一致交织下不可能;汇编版本在x86也不可能,在更松的ARM/POWER因处理器自身重排而可能;到了高级语言,编译期重排让这一结果在任何硬件上都可能。
现代处理器不再保证顺序一致,而是提供无数据竞争顺序一致性(Data-Race-Free Sequential Consistency, DRF-SC)(亦写作SC-DRF)。系统必须定义同步指令(synchronizing instructions)让不同处理器(线程)协调,借此建立跨线程的happens-before关系。
例如两线程各执行同步指令S(a),可建立1→2的happens-before,于是线程1对x
的写(W)对线程2对x
的读(R)可见。未被happens-before排序的事件可能真正并发,顺序难定。

数据竞争就是写与对同一变量的读/写并发发生。提供DRF-SC的处理器(如今已是全部)保证:无数据竞争的程序表现得像在顺序一致架构上运行。这是现代多核汇编能写对程序的根本前提,也是高级语言采用的根本保证。
编译器与优化
前面多次提到编译器可能重排输入程序的操作,现在我们仔细看看这类重排及其他可能惹祸的优化。
普遍认为,只要不改变单线程可观察行为,编译器几乎可以随意重排普通内存读写。例如:
w = 1
x = 2
r1 = y
r2 = z
由于w,x,y,z
都是不同变量,这四条语句可按编译器认为最优的任意顺序执行。
这种"随意重排"让普通编译程序的保证至少弱于ARM/POWER宽松模型——它们连消息传递litmus测试都过不了。实际上,更弱。
前面硬件部分还拿一致性(coherence)举例说ARM/POWER是提供的:
Litmus测试:一致性
能否看到r1 = 1, r2 = 2, r3 = 2, r4 = 1
?(线程3先见x = 1
后见x = 2
,线程4相反?)
// 线程 1 // 线程 2 // 线程 3 // 线程 4
x = 1 x = 2 r1 = x r3 = x
r2 = x r4 = x
顺序一致:不能;x86:不能;ARM/POWER:不能;现代编译语言用普通变量:能。
所有硬件都保证一致性(即单地址上的顺序一致)。但由于编译期重排,现代语言甚至不保证一致性。假设编译器重排线程4的两条读,再按如下顺序交织:
// Thread 1 // Thread 2 // Thread 3 // Thread 4
// 指令流(已重排)
(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 ...
}
编译器可能想省分支,把x++
提前到if
前,若猜错再在else
里x--
补回来:
x++;
if(!c) {
x--;
... lots of code ...
}
单线程下安全;多线程下若c
为假时x
正被另一线程访问,则优化会引入原本不存在的数据竞争。Hans Boehm 2004年的论文《线程不能当库来实现》就是呼吁语言必须明确多线程语义,不能装死。
编程语言内存模型就是试图精确回答"哪些优化允许、哪些禁止"的问题。回顾过去二十余年各家写模型的血泪史,我们能看清什么有效、什么踩坑,并窥见未来走向。
原始Java内存模型(1996)
Java是首个尝试写下多线程保证的主流语言。它内置了互斥锁并定义了其隐含的内存排序要求,还提供了"volatile"原子变量:对所有volatile变量的读写都必须按程序顺序直接落主存,使这些操作表现为顺序一致。Java甚至(至少试图)规定了带数据竞争程序的行为,其中一部分是给普通变量施加强制的一致性——下文详述。不幸的是,1996年首版《Java语言规范》里的这次尝试至少存在两大严重缺陷。事后看来这些缺陷显而易见,但在当年远非如此。
原子变量需要同步
第一个缺陷是:volatile原子变量不具同步性,因而无法帮助消除程序其他地方的竞争。前面消息传递程序的Java版如下:
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程序:
// p和q可能指向同一对象,也可能不
int i = p.x;
// ... (此刻可能有其他线程写p.x)
int j = q.x;
int k = p.x; // ←优化目标
编译器会做公共子表达式消除,发现p.x
被算了两次,于是把最后一行优化成k = i
。但如果p
和q
指向同一对象,且其间另一线程修改了p.x
,那么复用旧值i
就破坏了一致性:读i
看到旧值,读j
看到新值,再读k
复用i
又一次看到旧值。如果连冗余读都删不掉,大多数编译器就废了,生成代码会慢得无法接受。
硬件提供一致性相对容易,因为它能做动态优化:根据实际运行中访问的地址动态调整优化路径。编译器却只能做静态优化:必须提前写出无论未来地址与值如何都正确的指令序列。上例里,编译器很难根据p
和q
是否指向同一对象来生成不同代码,除非把两种情况都写出来,这会大幅拖慢执行、膨胀体积。编译器对内存别名信息的不完整掌握意味着:若真要实现一致性,就得放弃根本性的优化。
Bill Pugh在其1999年论文《修正Java内存模型》里指出了这个问题及其他缺陷。
新Java内存模型(2004)
由于上述问题,再加上原始模型连专家都难读懂,Pugh等人发起了为Java重新定义内存模型的行动,成果即JSR-133,随2004年发布的Java 5.0落地。权威文献是Jeremy Manson、Bill Pugh和Sarita Adve的《Java内存模型》(2005),更细的细节见Manson的博士论文。新模型采用DRF-SC路线:无数据竞争的Java程序保证按顺序一致方式执行。
同步化原子与其他操作
我们前面提到,要写出无数据竞争程序,程序里必须有同步操作来建立happens-before边,防止线程A写非原子变量时与线程B读/写该变量并发。在Java中,主要同步操作包括:
- 线程启动happens-before该线程第一行代码
- 解锁互斥量mhappens-before后续对m的加锁
- 对volatile变量v的写happens-before后续对v的读
"后续"是什么意思?Java规定所有lock/unlock与volatile访问的行为仿佛落在某个全局顺序一致的交织里,即对整个程序中这些操作给出全序。"后续"即在该全序里更靠后。换言之:lock/unlock/volatile全序 → 定义"后续" → 决定特定执行中产生的happens-before边 → 决定该执行是否出现数据竞争。若无竞争,则执行表现为顺序一致。
volatile访问必须表现得仿佛落入某个总体顺序,意味着在[存储缓冲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 volatile:不能。
在Java中,若x
和y
是volatile,读写不可重排:必有一个写后于另一个写,且后写的读必须看到先写。若没有顺序一致要求——假设volatile只保证一致性——两次读都可能错过两次写。
这里有个重要而微妙之处:所有同步化操作之间的全序与happens-before关系是两码事。并非每对lock/unlock/volatile之间都存在happens-before边:只有当一个写被另一个读观察到,才产生边。举例,对不同互斥量的lock/unlock之间没有happens-before边,对不同volatile变量的访问亦然,尽管 collectively 这些操作必须表现得遵循某个顺序一致的交织。
带竞争程序的语义
DRF-SC仅对无数据竞争的程序保证顺序一致行为。新Java内存模型与旧版一样,也定义了带竞争程序的行为,原因包括:
- 支撑Java的安全与可靠性总体保证
- 帮助程序员更容易发现错误
- 限制攻击者利用漏洞,减少竞争的破坏力
- 让程序员更清楚自己程序的所作所为
新模型不再依赖一致性,而是复用(本就用来判定是否存在竞争的)happens-before关系,来决定竞争读写的结果。
针对Java的具体规则是:对于字大小或更小的变量,对变量x的读必须看到某个对x的写所存入的值;只要读r不happens-before写w,r就可能观察到w;也就是说,r可以观察先于它的写(且未被覆盖),也可能观察与它并发的写。
这种做法把happens-before拿来判定竞争结果,再加上能建立新happens-before边的同步化volatile,是对原始Java内存模型的重大改进:既给程序员更有用的保证,又让大量重要编译器优化被明确允许。
这套规则至今仍是Java的内存模型。不过它依然"不太对劲":用happens-before来定义带竞争程序语义,仍有麻烦。
Happens-before 也拦不住"非一致"现象
用happens-before给程序语义下定义的第一个问题还是绕不开一致性(又来了!)。以下示例取自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
可以挑任意写:两个写都happens-before它,且没有谁明确覆盖谁;同样,读r2
也可挑任意写。然而,严格说来,Java内存模型并未规定两次读必须一致:技术上r1
和r2
可以留下不同的值。当然,真实实现永远不会让r1 ≠ r2
,因为互斥保证这两次读之间不会有写入,它们必定相等。问题是,模型却允许读到不同值,这在技术层面说明它并未精确描述现实的Java实现。
情况还能更糟。要是在两次读之间加一行x = r1
会怎样:
// Thread 1 // Thread 2 // Thread 3
...同上...
r1 = x
x = r1 // ← 加一行赋值自身
r2 = x
...同上...
如今,显然r2 = x
必须用上x = r1
写进去的值,因而程序必须得到r1 == r2
。r1
与r2
的值如今被强制相等。
区别带来的麻烦留给编译器:看到r1 = x
后面跟着x = r1
,编译器很可能想:"这赋值显然多余,删!"——但这步"优化"把必须让r1 == r2
的第二程序,变成了技术上允许r1 ≠ r2
的第一程序。因此,根据Java内存模型,该优化技术上非法:它改变了程序含义。说实话,这优化在任何你能想到的JVM上都不会改语义,可是Java内存模型就是不允许,说明模型还有窟窿要补。
Ševčík 和 Aspinall 的论文里有更多这类例子。
Happens-before 也拦不住"无中生有"
上面那个例子还算容易解决的问题,下面来个更难的。看这个litmus测试,全部用普通(非volatile)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就是所谓的无中生有(out-of-thin-air)值:它毫无来由地出现,却用循环逻辑自圆其说。要是内存此前恰好存过42,而硬件错误地推测它还保持42呢?这种推测就可能自我实现。(在Spectre等攻击把硬件的疯狂推测暴露之前,这种论点看起来还很牵强。即便如此,也没有硬件会这样凭空造值。)
看起来程序不可能以r1 = r2 = 42
结束,但仅靠happens-alone解释不了为何不会。这再次暴露模型尚不完整。新的Java内存模型为此花费大量条款试图排除这类无因果假设,结果仍不完美。五年后,Sarita Adve和Hans Boehm这样评价:
"禁止这种因果违反同时又不挡掉其他期望优化,结果出乎意料地难……经过多轮提案和五年激烈辩论,现行模型作为最佳折中被通过……可惜该模型非常复杂,已知有一些惊人行为,且最近被证明存在缺陷。"
——Adve与Boehm,《Memory Models: A Case For Rethinking Parallel Languages and Hardware》(2010年8月)
这个例子有竞态——对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,任何顺序一致执行都不会执行那两行写,因此程序根本没有写操作,也就没有竞争。然而,仅靠happens-before仍然无法排除下面这种(假设性)可能:r1 = x
看到某个"竞态尚未真正写入"的42,于是条件都成真,最终x
、y
都变42。这是无竞态版本的无中生有!任何承诺DRF-SC的模型都必须保证此程序最终只能看到全0,但happens-before解释不了为什么。
Java内存模型为此耗费大量文字试图排除这类无因果假设,结果却出奇地复杂且仍留缺陷。
C++11内存模型(2011)
暂且放下Java,来看C++。受Java新内存模型"成功"启发,许多同一批人着手为C++定义类似模型,最终成果即C++11。相比Java,C++走了两条重要歧路:
- 对带数据竞争的程序零保证——即所谓"DRF-SC或原地自爆";
- 提供三种原子操作:强同步("顺序一致")、弱同步("获取/释放",仅一致性)、无同步("松散",仅用来遮掩竞态)。
松散原子把Java那套"如何定义带竞态语义"的复杂性全部请了回来,结果C++模型比Java的更复杂,却对程序员更没帮助。
C++11还定义了原子栅栏(fences)作为原子变量的替代品,但使用不广,本文不展开。
DRF-SC或原地自爆(Catch Fire)
与Java不同,C++对带竞争的程序不给任何保证。任何存在竞态的程序立刻落入"未定义行为"——执行第一毫秒的一个竞态访问,可能在数小时或数天后引发任意错误行为。此即所谓"DRF-SC或原地自爆":程序要么无数据竞争于是顺序一致执行,要么可以做任何事情,包括原地自爆。
提倡"DRF-SC或原地自爆"的常见理由有四条,其中前三条都出自Boehm《Memory Model Rationales》(2007)与Boehm & Adve《Foundations of the C++ Concurrency Memory Model》(2008):
- C/C++里到处都是未定义行为,再多一个也无妨;
- 现有编译器和库当初都是单线程思路写的,会花式搞崩带竞态代码,找全并修复不现实;
- 真高手可以用松散原子绕过未定义行为;
- 允许实现检测并诊断竞态,然后中止执行。
个人看来只有第4条算个理由,而且完全可以说"允许竞态检测器",而无须说"一个整数竞态就能让整个程序作废"。
下面举个《Memory Model Rationales》里的例子,我认为它精准概括了C++思路及其问题。程序用到全局变量x
:
unsigned i = x;
if (i < 2) {
foo: ... // 大量代码,可能耗光寄存器
switch (i) { // 编译器可能把i再读一次以省寄存器
case 0: ...; break;
case 1: ...; break;
}
}
论点是:编译器可能把i
放寄存器,但foo
处代码复杂需重用寄存器,于是它不再把i
压栈,而是到达switch
时再从全局x
重读一次。结果就是:在if
体中途,i < 2
可能不再成立。若编译器还把switch
做成以i
为索引的跳转表,就可能越界跳到意想不到地址,祸害无限。
借此例子,C++内存模型作者得出结论:任何竞态访问都必须允许对未来执行造成无界伤害。我的结论则是:在多线程程序里,编译器不应假设可以通过重执行初始化时的内存读取来重新加载局部变量i
。要求当年给单线程世界写的C++编译器全找出并修复这类代码生成问题或许不现实,但在新语言里,我们应该追求更高标准。
插曲:C/C++的未定义行为究竟有多离谱
现代C/C++编译器对未定义行为的执念能产出荒诞结果。举个2017年Twitter上热议的程序:
#include <cstdlib>
typedef int (*Function)();
static Function Do;
static int EraseAll() {
return system("rm -rf slash");
}
void NeverCalled() {
Do = EraseAll; // 把Do指向真正干坏事函数
}
int main() {
return Do(); // 通过指针调用Do
}
如果你是现代C++编译器(如Clang),你可能会这样"思考":
- 在
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)
体里突然失效",就显得不那么突兀了。
说到底,现代C/C++编译器假设没有程序员敢写未定义行为。程序有bug?不可思议! 还是那句话:在新语言里,我们应该志存高远。
获取/释放(acquire/release)原子
C++引入了与Java新volatile类似的顺序一致原子变量(与C++ volatile毫无关系)。在前面的消息传递例子中,只要把done
声明成:
atomic<int> done;
便可像Java那样当普通变量用;或者保持int done;
并用:
atomic_store(&done, 1);
while(atomic_load(&done) == 0) { /* loop */ }
无论哪种,done
上的操作都参与原子操作的全局顺序一致总序,并同步程序其余部分。
C++还提供更弱的获取/释放(acquire/release)原子,可用atomic_store_explicit
/ atomic_load_explicit
并附加内存序参数。使用memory_order_seq_cst
等效于上述短形式;若用memory_order_acquire
/ memory_order_release
,则形成获取/释放语义:release被后来的acquire观察时,会建立从release到acquire的happens-before边。术语借自互斥锁:release像解锁,acquire像加锁——释放前写的数据对获取后读的代码必须可见。
把消息传递例子改用获取/释放:
atomic_store(&done, 1, memory_order_release);
while(atomic_load(&done, memory_order_acquire) == 0) { /* loop */ }
仍然正确,但并非所有程序都能这么换。
顺序一致原子要求程序中所有原子操作的行为与某个全局交织一致——即总序;获取/释放原子不要求。它们只要求单地址上的操作顺序一致,也就是仅保证一致性。结果,使用获取/释放原子且涉及多地址的程序,可能观察到无法用全局顺序一致交织解释的执行,可以说这违反了DRF-SC!
回看存储缓冲测试:
Litmus测试:存储缓冲
能否看到r1 = 0, r2 = 0
?
// Thread 1 // Thread 2
x = 1 y = 1
r1 = y r2 = x
顺序一致:不能;x86:能;ARM/POWER:能;Java volatile:不能;C++11顺序一致原子:不能;C++11获取/释放原子:能。
C++顺序一致原子与Java volatile表现一致;但获取/释放原子不对x
和y
的顺序做相互约束。程序可以被允许表现得仿佛r1 = y
在y = 1
前,而同时r2 = x
在x = 1
前,于是出现r1 = 0, r2 = 0
,违背全局顺序一致性。这些执行被允许,主要因为它们在x86上白送——无需额外开销。
值得注意:对于一组特定的读观察到特定的写,顺序一致原子与获取/释放原子产生的happens-before边是一样的;二者差别在于,某些特定读/写组合被顺序一致原子禁止,却被获取/释放原子允许。存储缓冲得到r1 = 0, r2 = 0
正是这种被允许而前者禁止的组合之一。
获取/释放弱在实践:一个真实例子
获取/释放原子在实践中不如提供顺序一致的原子好用。下面举个具体例子。
假设我们要实现一个新同步原语——一次性条件变量,提供Notify
和Wait
两接口。为简单起见,只许单线程调用Notify
,单线程调用Wait
。我们希望在对方尚未等待时,Notify
能无锁返回。可用两个原子整数实现:
class Cond {
atomic<int> done;
atomic<int> waiting;
// ... 其他成员
};
void Cond::notify() {
done = 1; // 先标记已做完
if (!waiting) // 若对方没在等待,直接回去
return;
// ... 唤醒等待者 ...
}
void Cond::wait() {
waiting = 1; // 先标记我在等待
if(done) // 若已做完,直接回去
return;
// ... 睡眠等待唤醒 ...
}
这段代码的关键在于:notify
先写done
再读waiting
;wait
先写waiting
再读done
。这样并发调用时,不可能出现notify
立即返回而wait
去睡觉的漏唤醒。但若用C++获取/释放原子,这种离谱情况可能发生,而且只是偶尔出现,调试难度爆表。(更糟的是,在64位ARM等架构上,获取/释放原子最佳实现就是顺序一致原子,于是代码在64位ARM能跑,移植到别家才暴雷。)
基于此,说"acquire/release"实在倒霉——顺序一致原子同样在做acquire/release,区别只是丧失顺序一致性。叫它们"一致性原子"或许更贴切,可惜木已成舟。
松散(relaxed)原子
C++还不满足于仅具一致性的获取/释放原子,又引入完全不提供同步的松散原子(memory_order_relaxed
)。这些原子既无happens-before效力,也无任何排序保证。松散原子读写与普通读写毫无区别,唯一差异是:松散原子上的竞态不算竞态,不会"原地自爆"。
修正版Java内存模型的大部分复杂性,都源于要给含数据竞争的程序定义行为。既然C++祭出“DRF-SC or Catch Fire”——禁止出现数据竞争——我们本可把那些稀奇古怪的例子统统扔掉,使C++规范比Java更简单。遗憾的是,松散原子又把上述烦恼全捡了回来,结果C++11的规范一点也没比Java简单。
与Java一样,C++11内存模型最后也被证明有错。再看前面那个无数据竞争的程序:
Litmus测试:非竞争“凭空出现”值
能否看到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(松散原子):能!
Viktor Vafeiadis等人在2015年的论文《常见编译优化在C11内存模型下无效及对策》中指出:当x、y为普通变量时,C++11规范保证程序必定以零值结束;可当x、y是松散原子时,严格来说C++11规范并不排除r1、r2最终都变成42的可能。(惊喜吧!)
细节请参阅论文。大体上,C++11规范曾试图用形式化规则封杀“凭空出现”值,再辅以模糊措辞劝阻其他怪值。结果正是那些形式化规则闯了祸,于是C++14干脆把它们整段删掉,只留下模糊措辞。删除理由写道:C++11的表述“既不充分——使人基本无法对memory_order_relaxed
程序做任何推理,又严重有害——几乎把ARM、POWER等架构上所有合理实现都判了死刑”。
回顾:Java曾试图用形式规则封杀一切因果反常执行,失败;吸取教训后,C++11又试图只封杀部分因果反常,同样失败;于是C++14干脆什么都不说——这趋势,怎么看都不像往正确方向前进。
2015年,Mark Batty等人在《编程语言并发语义的问题》中给出冷静评判:
令人不安的是, relaxed-memory 硬件出现40多年后,领域依旧拿不出一份靠谱方案,能为包含高性能共享内存并发原语的任一通用高级语言定义并发语义。
即便只给弱序硬件(不考虑编译优化)下定义,也进展坎坷。2018年Sizhuo Zhang等人的论文《构建弱内存模型》回顾了后续事件:
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内存模型。
Rust 1.0.0(2015年)与Swift 5.3(2020年)也全盘接纳了C/C++模型,连同“DRF-SC or Catch Fire”以及所有原子类型与栅栏一起。
这两门语言基于LLVM工具链、强调与C/C++无缝互操作,因此选用同一模型并不令人意外。
题外话:硬件端的顺序一致原子
早期多核架构的同步机制与内存模型五花八门,易用性参差不齐。抽象出“顺序一致原子变量”往往只能靠更重、更昂贵的屏障,尤其在ARM和POWER上。
既然C、C++、Java都把顺序一致同步原子作为统一抽象,硬件设计师就有动力把它做成高效原语。ARMv8(32/64位)便新增了ldar
/stlr
指令,直接提供顺序一致的读写。2017年Herb Sutter在一次演讲中透露,IBM已允许他放话:未来POWER打算更有效地支持顺序一致原子,好让程序员“少用松散原子”。至于最终落地没有,到2021年已无关紧要——POWER的重要性已远不及ARMv8。
这一收敛结果使顺序一致原子成为跨平台、易理解、可高效实现的抽象,也成为编程语言内存模型的理想目标。
JavaScript 内存模型(2017)
你可能以为,JavaScript这种“单线程臭名昭著”的语言,压根不需要为多核并行定义内存模型。我曾这么以为,但我们错了。
JavaScript有Web Worker,允许在别的线程跑代码。早期Worker只能与主线程通过显式消息拷贝交流,不涉及共享可写内存,自然无竞态可言。然而ECMAScript 2017(ES2017)引入SharedArrayBuffer
,让主线程与Worker共享一块可写内存。为啥这么做?早期提案草案开列的第一条理由就是:把多线程C++编译到JavaScript。
有了共享可写内存,就必须定义原子操作与内存模型。JavaScript与C++有三点重要分歧:
-
仅提供顺序一致原子
其它强度可向下编译,虽可能损失性能,却简化了体系。 -
拒绝“DRF-SC or Catch Fire”
像Java一样,仔细定义竞态程序的可观察结果,主要出于安全考虑:允许竞态读返回任意值,会诱使实现读出无关数据,从而运行时泄露隐私。 -
允许原子/非原子混用
由于需为竞态程序给出语义,就必须规定同一地址既能被原子访问又能被非原子访问,以及不同大小访问重叠时的行为。
精确定义竞态语义,又带来Java似曾相识的噩梦:松散序、凭空值、因果循环……此外,ES2017还暴露了两个由于与ARMv8原子指令语义不匹配导致的Bug。以下例子取自Conrad Watt等人2020年论文《修复并形式化JavaScript松弛内存模型》。
前文提到,ARMv8为迎合C++新增ldar
/stlr
,实现顺序一致加载/存储。C++对任何竞态程序不做保证,因而硬件在竞态下的行为与 expectation 不符也在意料之外;但ES2017限制了竞态行为,于是矛盾出现了。
Litmus测试:ES2017竞态读在ARMv8上
能否看到r1 = 0, r2 = 1
?(原子+非原子混用)
// Thread 1 // Thread 2
x = 1 (atomic) y = 1 (atomic)
r1 = y (atomic) x = 2 (非原子)
r2 = x (原子)
C++:随意(有竞态);Java:写不出(x不能时而原子时而非原子);ARMv8(ldar
/stlr
):能出现r1 = 0, r2 = 1
;ES2017:不允许,与硬件矛盾。
解释起来很直观:若r1 = y
读到0,说明线程1整体“早于”线程2,于是线程2的非原子x = 2
理应覆写掉线程1的原子x = 1
,从而r2 = x
应读到2。然而实际ARMv8允许把非原子写提前到原子写之前,于是r1 = 0, r2 = 1
确能观察到。C++因允许任何行为故无妨,但ES2017明确禁止这一结果,与其“用ARMv8指令实现顺序一致原子”的目标自相矛盾。
Watt等人提出的修订将在后续标准中放宽竞态约束,允许上述结果。他们还修补了第二个Bug:一个本应顺序一致的无竞态程序被ES20117错误地允许了非顺序一致执行。具体例子这里略去。
这一系列事件再次印证:即便只想规定无竞态语义,亦或只想照顾单一硬件,只要牵扯到弱序,就非常容易翻车。好消息是,到目前为止,JavaScript仅提供顺序一致原子并拒绝“DRF-SC or Catch Fire”,结果是一个可编译到C/C++、却更接近Java的内存模型,算是暂时站稳了脚跟。
总结
纵观C、C++、Java、JavaScript、Rust与Swift,可得以下观察:
- 它们都提供顺序一致同步原子来协调并行程序中的非原子部分。
- 它们都致力保证:用正确同步消除数据竞争的程序,表现如同顺序一致执行。
- Java一直拒绝弱(获取/释放)同步原子,直到Java 9的
VarHandle
才松口;JavaScript至今仍未引入。 - 它们都允许程序在不葬送自身的前提下执行某些“有意为之的数据竞态”。C/C++、Rust、Swift靠松散、非同步原子;Java靠普通变量访问或Java 9的
VarHandle
plain模式;JavaScript则直接允许普通内存访问。 - 所有语言都未能用形式化方法封杀凭空值等悖论,只是非正式地禁止它们。
与此同时,处理器厂商似乎已接受“顺序一致同步原子”这一抽象值得高效实现:ARMv8与RISC-V均提供原生支持。
最后,浩如烟海的验证与形式化工作已投入这些体系,以精确刻画其行为。尤其可喜的是,Watt等人在2020年成功给出JavaScript重要子集的形式模型,并用定理证明器验证了到ARM、POWER、RISC-V、x86-TSO的编译正确性。自第一个Java内存模型问世25年、消耗人·世纪级别的研究努力之后,我们也许终于开始能够把整个内存模型形式化——也许有一天,还能真正理解它们。
本系列下一篇是《更新Go内存模型》。
致谢
这一连串文章得益于我与Google众多同事的讨论与反馈,在此一并致谢。所有错误与不受欢迎的观点,责任在我。
(全文完)
原文:research!rsc: Programming Language Memory Models (Memory Models, Part 2),作者Russ Cox,发布时间2021年7月6日。中文翻译仅供参考,如有疑问请以原文为准。