无锁编程教程:通过版本控制理解内存屏障(Memory Barrier)

  • 这是无锁编程教程的第三篇文章。
  • 本文主要介绍了内存指令重排的另外一种情况:由于缓存的原因导致的线程间内存操作相互不可见的原理,并介绍了四种内存屏障模型#LoadLoad,#StoreStore,#LoadStore和#StoreLoad

如果你使用过版本控制系统,那么你也许能够更容易理解内存顺序,进而理解无锁代码的诸多特性。

理解内存顺序需要两步,第一步在我之前的文章编译期间的内存顺序 已经成功介绍了,而第二步,则是这篇文章我想讲的,来自于处理器本身的运行时的内存操作重排。和编译器的重排相似,处理器的重排也是对单线程程序不可见的,只有在无锁程序中,共享内存被多个不互斥的线程同时访问时才能够出现。不过,与编译重排不同的是,处理器重排只在多核/多处理器系统可见。

你可以通过强制一些指令表现为内存屏障来保证正确的内存顺序,从某种意义上来说,你只需要这些技巧就够了,因为这样,编译器顺序就已经自动维护了。这些指令包括但不限于:

  • 某些特定的汇编指令,例如PowerPC的 asm volatile("lwsync" ::: "memory")
  • 任何Win32的原子操作(Interlock operation),Xbox360除外
  • 大部分C++11原子类型的方法
  • 与POSIX锁相关的操作,如 pthread_mutex_lock

既然有很多的指令都能表现的如同一个内存屏障,那么内存屏障的种类就有很多种了。实际上,上述的这些指令所代表的内存屏障都并不相同。leading to another possible area of confusion when writing lock-free code。为了让读者能够更加清楚,我准备通过类比的方式介绍大部分内存屏障的种类。

首先,考虑经典的多核系统:双核,每个核有32KB的私有L1缓存,1MB的公有L2缓存,和512MB的公有主存。

 

一个多核系统有点像一组程序员合作完成一个工程,他们用了一个很奇怪的源码维护方式。比如一个双核系统意味着两个程序员,我们不妨称他们为Larry和Sergey

在我们的右边,我们有一个公有的,核心代码仓库,这一部分表示了主存和L2缓存。Larry与Sergey分别将将他们的相关代码拷贝到自己的私有电脑上,这个私有电脑代表了每一个核拥有的L1缓存,由于每一个机器都有一个暂存区域,默默地耿总寄存器以及局部变量。我们的两个程序员坐在电脑前,不停地改动他们自己暂存区中的代码拷贝,这里的改动指的是基于自己在内存中(自己的私有拷贝)看到的数据,进行一系列决策,并且更新内存中的数据,和线程的执行过程完全相同。

现在,我们再来看看代码控制的策略吧,在这个类比情形中,源码控制的策略非常奇怪。当Larry和Sergey修改了自己的私有代码仓库,他们的修改逐步的渗透到中心代码仓库,而且这种渗透是随机的。一旦Larry修改了本地代码X,修改一定会在通过渗透与中心代码仓库同步,但是我们无法保证渗透的时间。也许同步在修改后立即发生,也许在修改后很久很久才成功同步。甚至当Larry后续修改了代码Y和Z,后面的修改比前面的修改更早渗透也是有可能的。在这样的情形下,内存的写从主存的角度来看,是完全乱序的。

同样的,在Sergey的机器上,修改从公共代码仓库反向同步到私有代码仓库的时间也是不固定的,内存读的顺序因此也被打乱了。

现在,倘若一个程序员在这个代码仓库中工作,他既不会知道中心代码的渗透同步何时在发生,他甚至不能知道是否有其他程序员在和他一起工作!这样,程序员就可以和我们的线程联系到一起了。顺便一提,之前曾提到过的基本规则——单线程无法分辨内存的乱序仍然是满足的。

上述类比在程序员们开始处理代码仓库的同一个文件时,变得很有意思。首先,我们复习一下之前文章中提到的一个问题:X和Y都是初始值为0的全局变量:

考虑X和Y是存在于Larry的私有仓库的两个文件,同时X和Y也存在于公共代码仓库和Sergey的私有仓库。Larry在自己的私有仓库的X中写下了一个1,同时Sergey也在同时向自己的私有仓库Y写下了一个1。现在,由于他们写的太快了,双方都在自己修改还没有渗透到公共仓库的情况下查询另一个文件的值。他们会发现同时满足r1=0和r2=0。这个结果在原来是根本无法理解的,但是通过代码仓库的类比,我们发现这中情况的发生是显然的。

内存屏障的种类

幸运的是,对于这种无法预测的渗透同步操作,Larry和Sergey并没有束手无策。他们拥有一个特殊的指令,称之为“屏障(fence)”。屏障(fence)的表现和内存屏障(memory barrier)相似,且在我们的类比中,我们可以定义出四种不同的内存屏障(memory barrier),每一种屏障通过一种“屏障指令(fence instruction)”实现,且代表了一种为了避免的内存重排。举一个例子#StoreLoad是用来防止一个内存写后面一个内存读这样的指令的重排的。

正如Doug Lea指出的,这四个类别非常清楚地对应了真实CPU上的指令,但是也不近绝对。在大多数情况下,CPU的指令可能表现的向上述一些屏障类型的组合,甚至外加一些其他额外的效果。不过,只要通过类比你理解这四种屏障的含义,你就可以很轻松拓展到真实CPU上的情况了。

#LoadLoad

一个#LoadLoad屏障用于防止屏障前的Load操作和屏障后的Load操作的重排。

在我们的类比中,一个#LoadLoad屏障等价于从中心仓库pull一次。考虑 git pull , hg pull , p4 sync , svn update 或者 cvs update ,都是作用于整个代码仓库的,如果其中有任何合并冲突,那么就只有随机舍弃一边的修改了。

这里有一点需要注意的,#LoadLoad操作并没有保证pull的一定是最近的修改,他甚至可能pull到一个较早的修改,不过可以保证的是,屏障后的Load操作至少会比之前的Load操作更新。也就是说至少不会比最近渗透同步到私有仓库的那个文件早。

听起来,这是一个非常弱的保证,不过仍然能够有效防止读取到过时的信息。考虑一个经典操作,Sergey通过比较公共的标记(flag)来判断是否有一些数据被Larry更新了,如果flag是真,那么他就可以在读取数据之前使用#LoadLoad屏障来保证数据已经成功更新的值。

诚然,这个例子要求 IsPublished 标记自己渗透到Sergey的私有仓库,而这并没有确切发生时间,不过只要标记成功渗透过去,那么Sergey久一定可以通过#LoadLoad屏障防止读到的 Value 比标记老。

#StoreStore

一个#StoreStore屏障用于防止屏障前的Store操作和屏障后的Store操作的重排。

在我们的类比中,一个#StoreStore屏障等价于向中心仓库push一次。考虑 git push , hg push , p4 submit , svn commit 或者 cvs commit ,都是作用于整个代码仓库的。

同理,我们#StoreStore操作可能不会立即进行,而是存在一些延迟,类似于异步操作。因此,即使Larry执行了#StoreStore,我们并不能得出什么时候他的所有的Store操作在中心仓库可见。

相似的,虽然看起来#StoreStore屏障非常的弱,但仍然足够用来防止Sergey看到过时的数据。还是原来的例子,Larry只需要先讲数据放在储存下来,然后使用#StoreStore屏障,保证之后对flag的储存一定晚于数据就好了。

我们假设 IsPublished 自发渗透到了Larry的私有仓库,一旦Sergey发现了flag的变化,那么他可以肯定此时读到的Value是足够新的。有趣的是,这样的工作甚至不需要Value是一个原子数据类型,甚至一个复杂的大结构体也可以使用这种方式传递。

#LoadStore

不同于#LoadLoad和#StoreStore,我们不太好用版本系统的方式理解。最好的理解方式很简单,就是用从指令重排的角度理解。

考虑Larry有一系列操作,其中一部分让他从自己的私有仓库读取一些数据到寄存器,另一部分将寄存器的信息写回到私有仓库。在一些特殊的情况下,Larry有能力去打乱这些指令的顺序。一旦他遇到了load操作,他看看之后的所有store操作,如果这些store操作完全和当前的load无关,那么他允许这些store提前执行,并在之后执行load。在这种情况下,基本规则——单线程无法分辨出内存乱序是满足的。

在真实CPU上,如果在load操作时发生了cache miss,而在store操作时发生了cache hit,处理器可能会尝试上述的内存操作重排。不过,硬件的实现细节并不会有助于我们理解内存屏障。现在Larry有一个很无聊的工作,不过有些时候他被允许自行调整工作的顺序,这样的调整是不可预料的。幸运的是,存在这样的一个时间花销并不昂贵的指令,强制Larry不在这个地方随意调整读写的执行顺序。

在我们的类比中,即使存在了#LoadLoad屏障和#StoreStore屏障,Larry仍然可以在Load和Store中间进行重排。不过在真实CPU中,如果一个指令表现为#LoadStore屏障,那么这个指令一定可以以理解为#LoadLoad和#StoreStore的其中之一。

#StoreLoad

一个#StoreLoad屏障保证屏障前所有的Store在其他处理器可见后,屏障后的Load操作的结果一定比Store操作的结果更新。换句话说,这个屏障保证了屏障前的所有store操作不会发生在之后所有load操作之后。符合顺序一致性。

#StoreLoad非常特别,因为他是唯一一种可以防止前文例子中结果为r1=r2=0的情况的发生。看到这里,你一定会非常疑惑,为什么#StoreLoad操作就是如此的特别呢?毕竟#StoreStore等价于代码管理的push,#LoadLoad等价于代码管理的pull,而这两种内存屏障都是不够的。因为push操作可能被延迟若干时间,而这时pull并没有能力去获得最新的版本。这结识了为什么PowerPC的 lwsync 操作同时支持了#LoadLoad,#LoadStore和#StoreStore,但是仍然无法防止r1=r2=0的出现。

在类比中,#StoreLoad屏障push了所有的局部修改,等这些修改push完成后,再pull最近的远程库的HEAD。在大多数处理器中#StoreLoad屏障的时间花销远大于其他三种内存屏障。

如果我们使用了#LoadStore,我们就能够得到一个万能的内存屏障,同时支持了本文介绍的四种内存屏障。正如Doug Lea所说,所有支持#StoreLoad屏障的指令都是一个完整的内存屏障。

版本控制的类比告诉我们

之前曾说过,每一个处理器在处理内存重排的策略不尽相同。在x86/64系列中,内存模型是抢的,内存重排被降低到了最小。而在PowerPC和ARM中,内存模型是弱的,Alpha则自成一派。辛运的是,我们的类比是依赖于弱内存模型的,只要我们在类比中成功理解了屏障操作,那么我们就可以随心所欲解决主流CPU的无锁编程任务了。

这个类比在C++11下也非常实用,因此,如果我们这个类比来理解无锁代码,那么也可以在很多平台上正确编程。

在这个类比中,我曾假设所有程序员在不同的核上执行程序,而在实际的操作系统中,线程有时会在不同的核上交替运行,不过我们的假设依然成立。同时,我们的类比是以C++为载体,不过也可拓展到其他语言上。

至今为止,我并没有介绍完所有的内存屏障,比如,同时存在有数据依赖性的屏障,我在之后的文章中将深入讲解。不过本文的这四个算是最重要的了。

如果你好奇CPU工作的内部细节,比如内存写缓冲区, 缓存一致性协议和其他硬件实现细节。我推荐读者阅读资料。实际上,我相信只要你成功的实现了一些无锁的代码,你就已经非常熟悉有关的硬件细节了。

原创文章地址:【无锁编程教程:通过版本控制理解内存屏障(Memory Barrier)】,转载时请注明出处mhy12345.xyz

《无锁编程教程:通过版本控制理解内存屏障(Memory Barrier)》有3个想法

发表评论

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

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据