无锁编程教程:编译期间的内存顺序(Memory Order)

  • 这是无锁编程教程的第二篇文章。
  • 本文主要介绍了内存指令重排的其中一种情况:编译器优化导致的内存重排。这种内存重排可以解释单核处理器下多线程程序的诸多表现。

当你写了一个C++程序,并让他在CPU上面运行,其中的内存指令顺序会产生重排,这样的重排是编译器优化与处理器优化共同导致的,其初衷都是让你的程序能跑的更快。

当然内存指令的重排也有一些普遍承认的规则,对于编译器以及处理器的开发者,都需要保证:

Thou shalt not modify the behavior of a single-threaded program.

你的修改不能够改变单线程程序的行为。

由于这样的规则,内存的重排对于单线程的开发者通常都不会被注意到。甚至在很多的多线程程序中,由于程序中使用了“锁(mutexes)”“信号量(semaphores)”和“事件(events)”这类用于在其所在位置防止内存重排的操作。内存重排仍然不会被注意到。然而,当我们来到“无锁编程”中,公共内存的访问没有了任何互斥的保护措施,内存顺序的灾难性后果才终于显现出来

不过,你仍然不需要在多核处理器上考虑内存重排的问题,正如我在无锁编程教程:简介 中提到过的,我们可以利用满足顺序一致性的类型(如Java中的 volatile  变量和C++中的原子变量),使用微小的时间开销代价来解决内存顺序的问题。不过我不准备在这里详述,我想在这里讲讲编译器对于非顺序一致性的内存指令重排的影响。

编译器的指令重拍

正如我们知道的,编译器的作用就是将人们可读的源代码转化成机器可读的机器代码,在翻译中,编译器可以自由做很多等价变换。

一旦编译器在保证单线程程序行为不变的基础上,产生了一系列指令重拍(通常情况下,这种重拍只会在编译器优化开关打开时进行)。考虑如下的代码片段:

如果我们使用了GCC 4.6.1并禁用编译优化开关,那么编译器生成的机器代码可以使用  -S 指令查看。全局变量 B 的内存写操作在全局变量 A 读操作的后方,和源代码顺序吻合。

对比一下打开编译器优化开关 -O2 之后的结果:

这时,编译器自作主张修改了内存读写的顺序,至少对于单线程程序完全不能区分这两种顺序。

然而,这样的编译器重排在无锁数据类型中却产生了问题,下面使用了一个常用的例子,这个例子中,我们使用一个公开的标记 isPublished 来表示某个公开变量的储存是否完毕:

考虑如果编译器将 IsPublished 的储存放在 Value 的储存之前会发生什么。甚至对于但处理器的程序,我们都会发现出了问题,首先,一个线程依次执行了 IsPublished 和 Value 的储存,在这期间,另外一个线程在监视到 IsPublished 值改变后,会认为 Value 已经更新了,而事实上没有。

当然,也有可能编译器并没有重排这些操作,在这个情况下,我们的程序也有可能和其他无锁程序一样正常结束。特别是如果我们的多核CPU拥有 强内存模型 ,例如在简介部分提到的x86/64结构,或者是在一个单处理器环境,程序都会表现的毫无问题。如果事情正式这样,我们只能说自己是太幸运了,换句话来说,我们还是应该从学习如何从原理上杜绝内存重排导致的程序行为异常。

显示定义编译屏障

最简单,也最直接的防止编译器重排的方式是编译器屏障(Complier Barrier),在之前的文章【英】中已经讲述过相关的问题。下面我们将介绍如何使用GCC实现一个编译器屏障,在Microsoft的Visual C++中, _ReadWriteBarrier 拥有同样的功能。

当加入了编译器屏障,在编译器优化开关打开的情况,内存写的指令仍然会按照我们希望的顺序生成。

同样的,如果我们试图通过引入编译器屏障,修改之前的 SendMessage 函数(这里只能在单处理器情况下正确,多处理器仍然存在问题)。实际上,不只是Sending操作需要编译器屏障,Receiving操作也需要编译器屏障限制。

诚然,编译器优化已经足够用来防止单处理器下的内存重排。但是现在已经2012年了,也就是说,在这个多核处理器普及的年代,如果我们仍然希望保证在任何处理器下,内存操作都按照我们想要的顺序进行,那么编译器屏障是不够的,我们需要引入CPU的屏障指令,或者其他的有内存屏障作用的操作。而这些操作将会出现在我的下一篇文章中。

Linux内核暴露了部分CPU的屏障指令,我们可以使用如 smb_rmb 等编译宏(preprocessor macros)来引入,这些操作在单核处理器系统中会退化为普通的编译屏障。

隐式定义编译屏障

有很多其他的防止编译器重排的方式,实际上,我们刚刚介绍过的CPU的屏障指令就可以表现的想一个编译屏障。下面是一个用PowerPC下的宏定义实现屏障指令的例子:

#define RELEASE_FENCE() asm volatile("lwsync" ::: "memory")

我们将宏 RELEASE_FENCE 放置在我们希望防止内存重排(包括编译器重排)的任意位置。比如可以让我们的 sendValue 函数变得更加安全。

在新的C++11的原子操作库中,所有的非relax的原子操作都表现的像一个编译器屏障。

顺便一提,所有包含了编译屏障的函数,自身一定能够表现为一个编译屏障(即使这个函数是内联函数)。

实际上,不论内部是否包含编译屏障,大部分的函数(出去内联函数和标记为pure的函数,以及链接时生成代码(link-time code generation))调用都可以看做是一个编译屏障。进一步说,对于一个外部函数的调用甚至比普通的编译屏障还要强,因为编译器完全不知道这些外部函数是什么,因此编译器必须要完全放弃尝试优化内存调用的顺序。

这其实是非常显然的,在之前的代码中,假设 sendValue 是定义在其他外部的库中的,编译器无从知晓是否 sendValue 依赖于 foo->bar 的值。也不知道 sendValue 是否会在内存中改变 foo->bar 的值。因此,为了满足内存乱序不改变单线程程序的行为这个规则,编译器一定不会进行任何的内存操作的重排。同样的,在函数调用之后,即使编译器开了O2优化,编译器还是会生成一些代码重新从内存中提取 foo->bar 的最新值,而非默认他的值为5。

正如读者看到的,在很多情况下,编译器的自动指令重排都是被禁止的,甚至在一些极端情况,编译器必须要理解从内存中读取并更新某个值。我相信这些规则就是为什么人们一致认为C++中的 volatile是没有存在意义的。

Out-Of-Thin-Air Stores

不知道读者是不是感觉到了指令重排让无锁编程非常的棘手呢?在C++11规范诞生之前,从技术上是没有任何方式来防止编译器对指令惊醒重拍。特别的,当一个内存区域什么东西也没有时,编译器可以按照自己的想法向共享内存写东西。这里给出一个小例子:

诚然,这种情况很少在实际中发生,但是没有东西可以组织编译器试图在与A比较前就将变量B储存在寄存器(register)中。优化后的代码如下:

同样,编译器的优化完全没有影响我们提到过的基本规则。一个单线程程序仍然会对我们所做的优化一无所知,但是在多线程环境中,我们得到了一个即使A的值是false,也可以擦除其他线程对于B的所有改变的操作 B=r 。这并不是我们代码的初衷!这种问题非常鲜为人知,而理论上并不是不可能发生,这就导致了人们认为C++并不能很好的支持多线程,即使事实上我们已经开开心心的写了一百年的C++多线程无锁程序!

我不知道有任何人被这种凭空而来的内存写坑过,也许这只是因为我们写的无锁代码并没有能够恰好优化到能够导致问题的组合。至少如果我遇到了这个问题,我会尝试去向编译器提交问题。如果你遇到了这个问题,可以在下文评论。

现在,由于这种情况会导致“数据竞争与冒险(data race)”新的C++11标准显式禁止编译器引入这种情况。你可以在 most recent C++11 working draft的$1.10.22看到:

Compiler transformations that introduce assignments to a potentially shared memory location that would not be modified by the abstract machine are generally precluded by this standard.

对于可能向潜在共享内存地址写数据的指令,在这个标准中,被禁止进行编译器的指令重排优化操作。

为什么会有指令重排

正如我一开始就已经说过的,编译器优化内存操作的顺序的动机和处理器相同——为了让代码运行的更快。这种优化直接导致了现代的CPU构造。

可能我比较天真,但是确实非常的质疑一些理论说编译器在八十年代就做了很多指令重拍的操作,那是的CPU至多只包含大约十万个晶体管。我不认我在这种情况编译器可以做到这一步。但是自从摩尔定律给CPU设计者提供的可以操作的晶体管数量翻了大于10000倍之后,这些晶体管于是乎被用来实现了类似于流水线(piplining)、内存预取(memory prefetching), 指令级并行(ILP)和最近的多核(multicore)。从结果上来看,这些操作使得指令重拍能够为程序实现较大的性能优化。

最初的Intel Pentium出现在在1993年,包含了所谓U pipe和V pipe。这是我第一次记得人们开始广泛讨论流水线和指令顺序的重要性的相关问题。近年来,当我开始使用VisualStudio的x86汇编,我甚至十分惊讶的在这里几乎没有内存指令重排。另一方面,在我多年来通过PlayStation3的反汇编,我发现编译器同样也到达了这一步。不过这仅仅是我的个人体验罢了,并不能改变我们需要在无锁代码中考虑内存顺序的必要性。

 

原创文章地址:【无锁编程教程:编译期间的内存顺序(Memory Order)】,转载时请注明出处mhy12345.xyz

《无锁编程教程:编译期间的内存顺序(Memory Order)》有一个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.