多线程内存模型

这个系列其实早就想写了，断断续续关注C++0x也大约有两年余了，其间看着各个重要proposals一路review过来：rvalue-references、concepts、memory-model、variadic-templates、template-aliases、auto/decltype、GC、initializer-lists…
 
    总的来说C++09跟C++98相比的变化是极其重大的。这个变化体现在三个方面，一个是形式上的变化，即在编码形式层面的支持，也就是对应我们所谓的编程范式(paradigm)。C++09不会引入新的编程范式，但在对泛型编程（GP）这个范式的支持上会得到质的提高：concepts、variadic-templates、auto/decltype、template-aliases、initializer-lists皆属于这类特性。另一个是内在的变化，即并非代码组织表达方面的，memory-model、GC属于这一类。最后一个是既有形式又有内在的，r-value references属于这类。
 
    这个系列如果能够写下去，会陆续将C++09的新特性介绍出来。鉴于已经有许多牛人写了很多很好的tutor（这里，这里，还有C++标准主页上的一些introductive的proposals，如这里，此外C++社群中老当益壮的Lawrence Crowl也在google做了非常漂亮的talk）。所以我就不作重复劳动了:)，我会尽量从一个宏观的层面，如特性引入的动机，特性引入过程中经历的修改，特性本身的最具代表性的使用场景，特性对编程范式的影响等方面进行介绍。至于细节，大家可以见每篇介绍末尾的延伸阅读。
 
 
动机
    内存模型是C++09最重大的特性之一，之所以重大是因为多线程并发编程将成为下一个十年的主题之一，对此C++小胡子Herb Sutter早有精彩的论述。
 
    为什么在C++里面要想顺畅地进行多线程编程需要对标准进行修订（而不仅仅是通过现有的多线程库如POSIX、boost.Thread即可）呢？对此Hans Boehm在他的著名的超级晦涩难懂的paper——《Threads Cannot be Implemented as a Library》——里面其实已经详尽地阐述了原因，但是，一，尽管这篇paper被到处cite，newsgroup上面关于到底能不能用volatile来实现线程安全性这类问题还是争议不断。这方面就连C++牛魔王Andrei Alexandrescu都犯过错误，可见有多难缠。二，这篇paper很难读，一般人就算头悬梁锥刺股一口气读上N遍，一转眼的工夫就又成丈二和尚了。Memory-model与多线程是一个非常棘手的领域。记得Andrei Alexandrescu曾在一篇专栏文章里面提到，大意是说，泛型编程难、编写异常安全的代码更难，但跟多线程编程比起来，它们就都成了娃娃吃奶。
 
    因此，要想比较透彻理解C++09内存模型的动机，光是Hans的那篇paper是不够的，C++09的内存模型沿袭的是的内存模型，社群在这个上面花了玩命的工夫，最后修订出来的标准的复杂度达到了不是给人看的地步（当然，只是其中的一个小部分，并非全部），Jeremy Manson在google做了一个关于java memory model的talk，也只是浅浅的从宏观层面谈了一下。所以既然Java社群已经花了这个工夫，而且C/C++/Java本就是同根生，所以也就乐得发扬一下拿来主义了，订阅了相关mailing-list的老大们会发现Java社群这方面的几个老大也时常在里面发言，语言无疆界啊:) [Page]
 
用一句话来说，修订C++的内存模型的原因在于：
 
现有的内存模型无法保证我们写出可移植的多线程程序
 
那为什么无法保证呢。对此许多人都用一句模棱两可令人摸不着头脑的话来解释：因为C++98中的内存模型是单线程的（虽然标准没有明确指出，但这是一个隐含结论）。这句话说了等于没说，让我想起那个关于数学家的笑话。人们难免要问，那为什么内存模型是单线程的就意味着无法写出可移植的多线程程序来呢？POSIX线程模型指导下不是存在了那么多的C/C++多线程程序吗？这又怎么解释呢？
 
所以，必得有一个最本质的解释，下面这个就是：
 
现有的单线程内存模型没有对编译器做足够的限制，从而许多我们看上去应该是安全的多线程程序，由于编译器不知道（并且根据现行标准（C++03）的单线程模型，编译器也无需关心）多线程的存在，从而可能做出不违反标准，但能够破坏程序正确性的优化（这类优化一旦导致错误便极难调试，基本属于非查看生成的汇编代码不可的那种）。
 
OK，说到现在，对什么是“内存模型”还没有解释呢。内存模型的正式定义很是飘逸，jsr133中这么说：
 
A memory model describes, given a program and an execution trace of that program, whether the execution trace is a legal execution of the program.
内存模型描述给定程序的某个特定的执行轨迹是否是该程序的一个合法执行。
 
其实这句话正常人多读几遍多少还能有有点似乎理解的感觉。接下来一句话就更诡异了：
 
For the Java programming language, the memory model works by examining each read in an execution trace and checking that the write observed by that read is valid according to certain rules.
对于Java来说，内存模型的工作模式如下：对一个给定执行轨迹上的每一读取操作(read)，检查该读取操作所读到的对应的写操作结果(write)是否不违背一定的规则。
 
以上是内存模型的技术定义，其最大的缺点就是不能帮我们感性而直观的理解什么是内存模型。
 
目前的多线程编程模型从广义上来说一般不外乎共享内存模型（多个线程访问共享空间，通过加锁解锁和对全局变量的操作来进行交互）和消息传递模型这两种。其中共享内存模型目前仍然是主流中的主流（比如C家族语言用的就都是这一招），消息传递模型大家也都不陌生，目前最成熟的应用是在Erlang里面。当然，这样的分类是往大了说，往小了说可就麻烦了，可以参考这里。
 
本文要说的内存模型是针对共享内存下的多线程并发编程的。内存模型的技术定义刚才已经饶舌过了，其非技术定义是这样的：
 
一个内存模型对于语言的实现方回答这样一个问题：
哪些优化是被允许的（这里的“优化”其实僵硬地说应该是transformations，当然，由于这是我杜撰的非官方定义，所以就管不了那么多繁文缛节了。） 
 
[NextPage]

另一方面，一个内存模型对于语言的使用方回答这样一个问题：
需要遵循哪些规则，才能使程序是正确的。（废话，这里的“正确”当然是多线程意义下的正确了。）
 
了解了这个定义之后我们便可以对号入座来拷问目前的C++03标准为什么在多线程上出了问题了。 [Page]
 
为什么C++03标准不能保证多线程正确性
我们来看一个简单的例子：
 
int count = 0;
bool flag = false;
 
Thread1      Thread2
count = 1;    while(!flag);
flag = true;   r0 = count;
 
按照我们的直觉，r0不可能为读到count为0，因为等到while(!flag)执行完毕的时候，flag必定已经被赋为true，也就是说count=1必定已经发生了。
 
然而，实际上，在C++03下，r0读到count为0的可能性是存在的，因为count=1和flag=true的次序可以被颠倒。为什么可以被颠倒，是因为颠倒不影响所谓的Observable Behavior。
 
Observable Behavior: 标准把Observable Behavior（可观察行为）定义为volatile变量的读写和I/O操作。原因也很简单，因为它们是Observable的。volatile变量可能对应于memory mapped I/O，所有I/O操作在外界都有可观察的效应，而所有内存内的操作都是不显山露水的，举个简单的例子：
 
int main()
{
int sum;
… 
for(int i = 0; i < n ; ++i) sum += arr[i];
printf(“%d”, sum);
}
 
如果编译器知道arr里面各项的值（如果arr事先被静态初始化了的话），那么那个for循环就可以完全优化掉，直接输出arr各项和即可。为什么这个for循环可以优化掉？因为它不具备Observable Behavior。
 
有点迷糊？Hans Boehm的paper上的例子更简单一点：
 
x = y = 0;
Thread1  Thread2
x = 1;      y = 1;
r1 = y;     r2 = x;
 
很显然，结果要么r1==1要么r2==1。不可能出现r1==r2==0的情况，因为如果r1读到y值是0，那么表明r1=y先于y=1发生，从而先于r2=x发生，又由于x=1先于r1=y发生，因而x=1先于r2=x发生，于是r2就会读到1。
 
当然，以上这段分析是理论上的。地球人都知道，理论上，理论跟实际是没有差别的，但实际上，理论跟实际的差别是相当大滴。对于本例来说，事实上r1==r2==0的情况是完全可能发生的。只需把Thread1里面的两个操作互换一下即可。为什么可以互换呢？因为这样做并不违反标准，C++03是单线程的，而互换这两个操作对单线程的语意完全没有任何影响（对于一根筋通到底的编译器来说，它们眼里看到的是x、y这两个无关的变量）。
 
为什么volatile是个废物
那么，你可能会问，volatile可不可以用在这里，从而得到想要的结果呢？很遗憾，答案是否定的。对volatile的这个误解从来就没有停止过，去comp.lang.c++.moderated新闻组上搜一搜就会发现了，我怀疑在C++所有的语言特性所引发的口水中那些由volatile引发的至少要占到30%。volatile当之无愧为C/C++里面最晦涩的语言特性之一。
 
为什么volatile不可以用在这里，Scott Meyers和Andrei Alexandrescu作了一个极其漂亮的阐述，ridiculous fish同学也写了一个漂亮的post。不过瘾的话这里还有一份由Java大牛们集体签名的申明。
 
总而言之，由于C++03标准是单线程的，因此volatile只能保证单线程内语意。对于前面的那个例子，将x和y设为volatile只能保证分别在Thread1和Thread2中的两个操作是按代码顺序执行的，但并不能保证在Thread2“眼里”的Thread1的两个操作是按代码顺序执行的。也就是说，只能保证两个操作的线程内次序，不能保证它们的线程间次序。 [Page]
 
一句话，目前的volatile语意是无法保证多线程下的操作的正确性的。
 
为什么多线程库也（基本）是废物
那么，同样又会有人问了：那么库呢，可不可以通过多线程库来编写出正确的多线程程序呢？这就是Hans Boehm那个paper所要论述的内容了。该paper全长仅仅8页，核心内容也不过两三页纸。但由于涉及了对标准中最晦涩的内容如何进行解释，所以非常难读。其实它的中心思想可以用一句简单的话概括出来：
 
因为C++03标准是单线程的，所以即便是完全符合标准的编译器也可能各个脑袋里面只装着一个线程，于是在对代码作优化的时候总是一不小心就可能做出危害多线程正确性的优化来。
 
Hans Boehm在paper里面举了三个例子，每个例子都代表一类情况。
 
第一个例子：
 
x = y = 0;
Thread1         Thread2
if(x == 1) ++y;    if(y == 1) ++x;
 
以上代码中存在data-race吗？由于x和y一开始都是1，所以答案是：不存在，因为两个if条件都不会满足，从而对x和y的++操作根本就不会被执行。但，真正的问题是，在现行标准下，编译器完全可以作出如下的优化：
 
x = y = 0;
Thread1         Thread2
++y;             ++x;
if(x != 1) --y;      if(y != 1) --x;
 
于是data-race大摇大摆地出现了。你能说这是编译器的错吗？人家可是遵章守纪的好市民。以上的代码转换并没有违背任何单线程内的语意。所以，唯一的错误是在标准本身身上。标准只要说一句：在这种情况下，所有的sequential consistent的执行路径都不可能导致data-race，因此，该程序内不存在data-race。就万事大吉了。
 
第二个例子：
 
struct
{
int a : 17;
int b : 15;
} x;
 
一个线程写x.a，另一个线程写x.b。有data-race吗？目前的标准对此一言不发。我们最妥善的做法也只能是在无论读取x.a或是x.b的时候将整个x哐当用锁锁起来。
 
第二一撇个例子：
 
struct { char a; char b; char c; char d;
char e; char f; char g; char h; } x;

[NextPage]

那么如下的操作
 
x.b = ’b’; x.c = ’c’; x.d = ’d’;
x.e = ’e’; x.f = ’f’; x.g = ’g’; x.h = ’h’;
 
会涉及到x.a吗？答案是会，因为编译器只要这么转换一下：
 
x = ’hgfedcb\\0’ | x.a;
 
如果原先的代码中有另一个线程在对x.a进行写操作，data-race就不幸发生了。而且还是违反直觉的发生的——程序员泪眼汪汪的问：我操作x.b~x.h关x.a什么事呢？
 
问题就在于，现行标准没说清什么是一个“内存位置(memory location)”。于是N2171提案里面是这样写的：
 
A memory location is either an object of scalar type, or a maximal sequence of adjacent bit-fields all having non-zero width. Two threads of execution can update and access separate memory locations without interfering with each other. [Page]
一个内存位置要么是一个标量、要么是一组紧邻的具有非零长度的位域。两个不同的线程可以互不干扰地对不同的内存位置进行读写操作。
 
第三个例子：
 
for (...) {
...
if (mt) pthread_mutex_lock(...);
x = ... x ...
if (mt) pthread_mutex_unlock(...);
}
 
对于以上代码，貌似是不会有data-race了，因为x的访问已经被pthread_mutex_(un)lock()包围（保卫？）起来了。但果真如此吗？
 
“聪明”的编译器只要运用一种“成熟”的叫做register promotion的技术就可以破坏这段表面平静的代码：
 
r = x;
for (...) {
...
if (mt) {
x = r; pthread_mutex_lock(...); r = x;
}
r = ... r ...
if (mt) {
x = r; pthread_mutex_unlock(...); r = x;
}
}
x = r;
 
在单线程上下文中，以上优化是完全合法的，而且也的确能够带来效率提升。但由于它将原本只能位于临界区内部的x的写操作“提升”到了临界区外面。结果到了多线程环境下就挂了。对此POSIX线程库也无能为力。
 
那么，究竟如何才能允许用户编写正确的多线程代码呢？
 
一个简单的办法就是禁止编译器作任何优化：所有的操作严格按照代码顺序执行，所有的操作都触发cache coherence操作以确保它们的副作用在跨线程间的visibility顺序。但这样做显然是不实际的——多线程本来的目的就是为了提升效率，这下倒好，为何实现多线程正确性却要付出巨大的效率代价了。但为什么要考虑这个方案呢，目的就是要明确我们的目的是什么：我们的目的是，使代码能够“看起来像是”被“顺序一致性(sequential consistency)地”执行的。所谓顺序一致性其实没什么神秘的，我们一开始被教导的多线程程序被执行的方式就是所谓的顺序一致性的：即多个线程的所有操作被穿插交错执行，但各个线程内的各操作之间的相对顺序被遵守——别紧张，就是你脑袋里那个对于多线程如何被执行的概念。
 
那么，要想实现顺序一致性，难道除了禁止一切优化就没有其它办法了吗？我们注意到，实际上在一个线程内部，几乎绝大多数的操作都是单线程的，也就是说，它们操作的都是局部变量，或者进一步说，对其它线程不可见的变量。也就是说，绝大多数的操作对其它线程来说都是不可见的。对于这部分操作，编译器完全可以自由地按照单线程语意来进行优化，动用所有古老的单线程环境下的优化技术都没问题。最关键的就是那部分“线程间可见”的操作。对于这部分操作，编译器必须确保它们的“对外形象”。
 
那么，编译器能否分辨出哪些操作是单线程的，哪些操作是多线程的呢？很大程度上，这是可以的。所有对局部变量的操作，都是单线程可见的。所有对全局变量的操作都是多线程可见的。因此是不是可以说，编译器只要对那些全局变量操作小心一点就可以了呢？答案是还不够。因为这样的编译模型要求编译器对所有针对全局变量的操作都禁用任何优化，并且还要时不时通过插入memory fences（或称memory barrier）来确保cache coherence。这个代价，还是太大。
 
于是所谓的data-race-free模型粉墨登场。Data-race-free模型的核心内容是： [Page]
 
只要你通过基本的同步原语（由标准库提供，如Lock）来保证你的程序是没有data-race的，那么编译器就能向你保证你的程序是被sequentially-consistent地执行的。
 
为什么这个模型是有优势的。是因为它最大化了编译器可能作的优化。举个简单的例子：
 
… // #1
Lock(m)
… // #2
Unlock(m)
… // #3
 
在这样的一段程序中，#1、#2、#3处的代码完全可以享受所有的单线程优化。编译器再也不用去猜测哪些操作是有线程间语意的哪些操作没有了，省心省事。在以上的程序中，Lock(m)和Unlock(m)就充当了所谓的one-way barrier（单向内存栅栏），不同的是Lock(m)具有Acquire语意，而Unlock(m)具有Release语意。Acquire语意是说所有下方的操作都不能往其上方移动，Release语意则相反。对于上面的代码来说也就是说，编译器的优化不能将#2处的代码移到临界区外，但可以将#1、#3处的代码往临界区内移。
 
至于为什么data-race-free能够确保sequential-consistency，我以前写过一篇文章阐述这一点，其实也就是阐述这个经典的证明。不过由于是用英文写的，所以读的人很少。因为当时没有作任何的铺垫，所以读懂的就更少了。