无锁编程教程:强内存模型与弱内存模型


内存重排有非常多种类,但是并不是所有的内存重排都会经常发生。这决定于你是用的处理器类型以及你是用的工具链(toolchain)

一个内存模型告诉你,对于一个指定的处理器或工具链,究竟哪种类型的内存重排可能出现。需要时刻警醒,内存重排仅仅会在多线程无锁编程中才会显现。

经过一段时间的研究——查阅网上的资料以及亲手实验,我成功的将他们总结成为如下4种类型。在下图中,对于所有右边的模型,不仅满足其左侧模型的所有要求,并且还更近一步。通过图示,我们可以画出一条清晰地界限指定强/弱内存模型。

上图中,所有的实际的硬件类型都对应了一个硬件内存模型,而硬件内存模型又对应了一个内存重排的严格性等级。

在内存重排方面,不同类别的处理器表现不尽相同。不过这些表现只有在多核条件下才能表现出来,鉴于多核是当今的一个主流趋势,所以我们需要对这些内存顺序问题有所理解。

有了硬件内存模型,我们也有软件内存模型。技术上来说,当你编写并调试可移植的C11,C++11或Java的无锁代码,你只需要关心软件内存模型。但是了解了硬件内存模型,你可以知道为什么一个错误的代码在某些处理器上运行毫无问题。

弱内存模型

在一个弱的内存模型中,我们可能遇到所有的四种内存重排。这些重排我在之前的文章中已经讲解过了,在不影响单线程程序的情况下,任何的读写操作都会有概率互相交换顺序,这些重排源于编译器和处理器的共同作用。

当一个处理器是弱内存模型,我们倾向于说是“弱有序(weakly-ordered)”,我们又是也会称之为relaxed 内存模型.弱内存模型的一个经典的例子是DEC Alpha. 不过主流的处理器都不是弱有序的。

C11和C++11所描述的弱内存模型在很多方面都是收Alpha影响的,当我们在这些语言中使用底层原子操作时,即便你使用了 x86/64这一类强有序的硬件,你也应该保证正确的内存顺序来保证编译器正确处理编译期间的内存重排。

保证数据依赖性的弱有序模型

虽然Alpha现在已经不再流行了,我们仍然有若干的线代CPU模型继承了弱有序硬件模型的性质

  • ARM,实现中很多手机、平板的处理器,在多核环境下也越来越普及
  • PowerPC,以Xbox 360为典型,也在生活中普及
  • Itanium,现今已经不被Window支持维护,但是仍然被Linux支持,存在于一些HP服务器端。

这些类别对应的内存模型,在很多方面都和Alpha类似,但是他们抱着了数据依赖性(data dependency ordering)。具体来说,如果你在C/C++中写了A->B,那么你永远保证对于B的读取一定至少比A要新,这是Alpha所不能霸主的。对于数据依赖性,我不在这里深究了。

强内存模型

先让我们看看硬件内存模型,强内存模型和弱内存模型的区别是什么呢?对于这个问题,确实有一些争议。但是就我的感觉而言,对于80%的情况,大多数人都有共同的认识。归纳如下——

strong hardware memory model is one in which every machine instruction comes implicitly with acquire and release semantics. As a result, when one CPU core performs a sequence of writes, every other CPU core sees those values change in the same order that they were written.

强硬件内存模型是指,硬件的所有指令都保证了 acquire和release语义。这意味着,当处理器核心进行了一系列写操作,其他处理器核心看到值的改变的一定符合相同的顺序。

这不难通过版本控制的例子想象出来,所有的修改都向共享内存以指定顺序渗透(没有#StoreStore重排),而所有的读取也按照固定顺序(没有#LoadLoad重排),指令的处理也都按照顺序执行(没有#LoadStore重排),在此基础上#StoreLoad仍然是可能的。

在上述的定义下,x86/64系列处理器通常是强有序的,但是在一些特定情况下,这个强有序的保证是不存在的,不过对于应用编写者,我们完全可以忽视这些情况,处理器确实会乱序执行指令,但是这仅仅是处理器内部的问题,重要的是即使如此,所有的内存指令仍然是有序的,因此在多核环境中,我们仍然将其视为强有序的。

运行在TSO模式下的SPARC处理器是另一个强硬件有序的例子,TSO意思是储存全有序(total store order),换句话说,对于向内存的写操作,所有核心有一个唯一的全局的顺序,x86/64也保证了这个性质。从我知道的来看,TSO性质并不被程序员们关注,但是这确实是想顺序一致性又进了一步。

顺序一致性

在顺序一致性内存模型中,内存重排不复存在,整个程序多个线程的指令可以看做不在相交,这时,之前例子中r1 = r2 = 0的情况将不复存在。

现在,想要找到一个多核设备保证了顺序一致性并不容易,不过回顾历史,在1989年,386系列的 Compaq SystemPro 从Intel手册上来看,并没有足够“先进”以至于能够引入运行时内存重排。

顺序一致性一般而言都是作为一个软件内存模型存在的,在编写高级语言时,比如Java5以上你可以定义volatile,在C++11,你可以使用缺省的memory_order指示符,memory_order_seq_cst来实现顺序一致性。倘若你读过Herlihy & Shavit的 多核编程的艺术,注意他们的大多数例子都是基于顺序一致性的。

更多

关于内存模型,还有很多重要的细节,但是在我看来都在工程中不那么重要,比如control dependencies, causal consistency, and different memory types。而对他们的大部分研究都会回到我之前说过的四种组合。

如果你真的希望深入研究,你可以看看剑桥大学的admirably detailed work,以及Paul McKenney的accessible overview 。

 

原创文章地址:【无锁编程教程:强内存模型与弱内存模型】转载时请注明出处mhy12345.xyz

无锁编程教程:Acquire和Release语义

  • 这是无锁编程教程的第四篇文章。
  • 本文详细讲解了内存顺序中Acquire和Release的含义,包括了如何使用甚至屏障命令以及使用C++11的原子数据类型库实现屏障。
  • 如果你发现本文使用了一些没有解释的术语,那么很有可能我已经在本系列之前的几篇文章中有所涉及。
  • 原文地址:http://preshing.com/20120913/acquire-and-release-semantics/

在无锁编程中,线程有两种方法操纵他们的共享内存:他们既可以通过竞争的方式抢夺某一种资源,也可以借助共享内存传递信息来实现相互之间的合作。Acquire和Release对于后者来说是至关重要的:他们可以让信息的传递变得可靠,实际上,缺少或者不正确的Acquire/Release使用是无锁编程中的一个经典错误!

在这篇文章中,我将向大家介绍若干种通过C++实现Acquire/Release的方式。作为引入,我将以最快的速度过一遍C++11的原子类型库,因此,你并不一定需要立即读懂。同时,这篇文章仍然默认我们的编程都不满足顺序一致性。我们将直面存在内存重排问题的多核处理器环境。

不幸的是,倘若你尝试通过搜索网上来学习他们,你会发现Acquire和Release术语的定义过于混乱,根本不知道在说些什么。不过,Bruce Dawson在他的论文中给我们了一系列非常靠谱的定义,而我在这里,也将向大家介绍我自己归纳出的一些定义,尽可能的与现存的C++11原子数据类型相吻合。

Acquire semantics is a property that can only apply to operations that read from shared memory, whether they are read-modify-write operations or plain loads. The operation is then considered a read-acquire. Acquire semantics prevent memory reordering of the read-acquire with any read or write operation that follows it in program order.

Acquire语义修饰内存读操作(包括内存读取或者读-修改-写操作),倘若一个操作被该修饰符修饰(read-acquire),那么他就能够防止其后面的所有内存读/写操作重排到他的前面。

Release semantics is a property that can only apply to operations that write to shared memory, whether they are read-modify-write operations or plain stores. The operation is then considered a write-release. Release semantics prevent memory reordering of the write-release with any read or write operation that precedes it in program order.

Release语义修饰内存写操作(包括内存修改或者读-修改-写操作),倘若一个操作被该修饰符修饰(write-release),那么他就能够防止其前面的所有内存读/写操作重排到他的后面。

一旦你仔细理解了上述定义,你就会发现acquire和release操作可以通过上一篇文章中说的内存屏障实现——将内存屏障通过某种方式放在read-acquire操作后,或者write-acquire操作前面,这样,内存屏障就能起到acquire/release相同的作用。不过,需要注意的是,从技术上来说还会复杂一些,不过并不影响我们理解。

一个很好的地方是,acquire和release都不需要使用#StoreLoad屏障,也就是说,他们总不会太低效。举一个例子,在PowerPC中,lwsync(全称”lightweight sync”,即轻量级同步)指令表现为#LoadLoad,#LoadStore和#StoreStore屏障的组合,在这种情况下仍然比sync要快很多,而sync就是一个#StoreLoad屏障。

直接使用平台的屏障指令

实现我们希望的内存屏障的一种方法是直接使用平台指定的屏障指令,让我们从一个简单的例子出发,假设我们在PowerPC上面编程,而 __lwsync() 是一个编译器的内部用于生成 lwsync 的函数。由于 lwsync 同时引入了多种屏障,因此,不论我们希望使用release语义还是acquire语义,我们都可以用同样的方式建立屏障——在线程1中,将对于 Ready 变量的储存转化为write-release,并在线程2中,将对于 Ready 变量的读取转化为read-acquire.

如果我们让两个线程执行结果为 r1==1 ,那么我们可以确信在第一个线程中,A的赋值操作成功的传递到了线程中,进而保证了 r2 == 42 。在我之前的文章中,我已经详细讲解了#LoadLoad和#StoreStore的原理,因此就不在这里赘述了。

用正规的术语表示,我们可以说:变量 Ready 与数据的读取是同步(synchronized-with)的。而对于同步的理解,可以参见这里。至少我们现在可以肯定这样的策略是可行的,但是他们必须作用于同一个变量上,比如这里的 Ready ,而且读取和储存必须是原子的。由于在这里,Ready是一个int类型,因此它的读写操作在PowerPC上面本身就是原子的。

在C++11中使用屏障指令

在之前的样例中,为了实现屏障代码,我们需要仔细了解编译器以及处理器的版本。并在此基础上设计代码。而假设我们希望写一个支持多处理器的代码,我们可以使用C++11重写我们的代码。在C++11中和原子操作有关的所有的数据类型都存在于std命名空间中,我们在之后的代码中,默认包含 using namespace std; 。

在C++原子库中定义了一个可移植的函数 atomic_thread_fence() ,这个函数接受一个参数来决定屏障的种类。当然,比如 memory_order_acquire 和 memory_order_acquire 就是一种选择,我们可以把这个函数放在之前我们放 __lwsync() 的地方。

不过,还有一点点小小的缺陷,那就是在PowerPC,我们可以保证 Ready 是一个原子变量,但是我们不能够假设这适合与所有的平台,因此我们应该将 int 改为 atomic<int> 。唔,这确实是一个挺愚蠢的改变,因为现在所有CPU对于int的读写都是原子的。不过我将在这里详细叙述这个问题,但是至少现在为止,我们使用这个愚蠢的修改来保证我们理论上100%的正确率吧。

在代码中,参数 memory_order_relaxed 意思是“保证这个操作是原子的,但是我并不指定一个特定的内存顺序限制。”

重新申明一些,所有之前的 atomic_thread_fence() 调用都能够(并很有可能确实是)用PowerPC上的  lwsync 替代的,他们都可以在ARM中生成 dmb 指令,在PowerPC上面, atomic_thread_fence() 也至少不比 lwsync 糟糕。在x86/64上面, atomic_thread_fence() 都被解析成了编译器屏障,因为所有的x86/64的读写操作都自动蕴含了acquire/release语义。这也是为什么x86/64是强顺序(strongly ordered)的。

在C++11中不使用屏障指令

在C++11中,我们实际上可以不显示指定内存屏障指令来实现屏障,我们只需要对于Ready的指令显示指定内存顺序要求就好了。

考虑将所有屏障指令包含在Ready的修改指令自身(注意,这种形式不完全和在外面定义屏障指令相同,前者是不那么严格的)。编译器会生成必要的指令来保证屏障的效果,比如在Itanium里面,所有操作可以被表示为单个指令 ld.acq 和 st.rel 。正如之前所说的,这样的操作保证了 r1 == 1 能够决定 r2 == 42 一定成立,也就是保证了同步(synchronizes-with)关系。

这也是C++11推荐的,表达acquire/release语义的方式,事实上, atomic_thread_fence() 的加入甚至比标准的指定还要晚。

Acquire 和 Release 和锁

正如你所看到的,上述所有的例子都没有使用acquire和release语义引出的#LoadStore屏障,只有#LoadLoad和#StoreStore是真正有用的,这是因为在这个文章中,我选择最简单的例子让大家理解API和语法。

一个#LoadStore比较重要的例子是我们使用acquire和release语义实现一个锁。实际上,这也是acquire和release两个词的来历——获取(acquire)一个锁,和释放(releaseing)一个锁。所有的内存操作内存操作都被这两个命令关在了一个小区域内,进保证锁的临界区的有效性。

在这里,acquire和release语义保证了在持有锁的时候的修改都在锁里面,所有锁的的实现(包括你自己实现的锁),都需要保证这些要求,而这些都是为了能够有效地在两个线程中传递信息,即使是在多核、多处理器环境中。

在之后的一系列文章中,我会展示一个用C++11实现的演示。他可以在真实的硬件上运行,而其中,acquire和release保证了其运行的稳定性。

原创文章地址:【无锁编程教程:Acquire和Release语义】转载时请注明出处mhy12345.xyz

无锁编程教程:通过版本控制理解内存屏障(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 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

无锁编程教程:简介


无锁程序的设计非常复杂,一方面,需要读者对于并行计算涉及概念有较深的理解,另一方面,由于不同平台表现不一致,调试困难等客观原因,即使写出了程序也不容易检验。我的无锁编程始于Bruce Dawson的论文,十分幸运的是,我甚至有机会在工作中,借鉴Bruce的一些无锁数据结构编程技巧,并运用到Xbox 360等平台的编程与调试中。

从那以后,我写了一系列资料,从最基本的理论推导到最实际的代码编写,甚至最底层的硬件细节都有所涉及。然而不幸的是,这些资料甚至有些都是相互矛盾的,比如,有一些材料直接假定了顺序一致性(sequential consistency),并借此避免了任何有关于内存顺序细节的讨论,而在另一些材料中却没有做这些假设。随着C++11原子数据类型 的出现,本来就非常混乱的无锁编程变得更加复杂,让我们更难解释无锁算法的运行原理了。

在这篇文章中,我希望能够重新系统得介绍无锁编程,从对于每一个基本概念的定义开始。运用流程图,展示出这些概念如何互相关联,进而分析这些概念的一些细节。如果你准备继续读下去,我假设你已经理解最简单的多线程程序的编写,以及锁(mutex),信号量(semaphores)等同步机制。

无锁编程是什么?

大多数人对于无所编程的理解都停留在“不用锁来写多线程程序”。毋庸置疑,这样的定义是没有问题的,但是并不完整。对于无锁编程,被学术界认可的定义更加宽泛,学术界认为,“无锁(lockfree)”仅仅是一种代码的性质罢了。

简单的来说,如果程序的一部分满足接下来提到的这些条件,那么我们就可以认为他是“无锁”的,反之,如果不满足,则程序不是“无锁”的。

通过上图,我我们发现“无锁(lock-free)”这个词中的“锁(lock)”并不是指代码中的“锁(mutex)”,而是指的是能够通过某种方式“阻塞(locking up)”整个程序的可能性。这个可能性可能来源于经典的“死锁(deadlock)”,也可能由于很糟糕的内存调度顺序使得程序停滞不前(这可能变成一些恶意攻击者的突破口)。这听起来挺搞笑的,但是由于持有锁(mutex)的线程的调用顺序是任意的,因此最坏的情况是可能发生的,纵使有些时候,理论计算告诉我们“最坏情况”是一个不可能事件(概率为0),但是从概念上来说,只要“可能发生”阻塞,那么这个程序就不是无锁的。

举一个例子,对于下面的无锁程序,在初始 X=0 的情况下,什么样的调度顺序可以导致程序永远按无法退出循环?(这个问题留给读者自己思考)

没有人指望一个很大的工程是完全无锁的,通常来说,我们希望这个工程中某一个访问了公有内存的代码片段是无锁的。举一个例子,我们可能希望拥有一个“无锁队列”,这个无锁队列支持若干无锁的操作,诸如 push , pop , isEmpty 等等操作。

The Art of Multiprocessor Programming的作者Herlihy 和 Shavit倾向于将上述的操作描述成类的方法,进而对无锁(lock-free)有了一个更简单的定义:

在无限次执行中,可以完成无限次方法调用。

换句话来说,只要程序不停地调用这些“无锁”的方法,已完成的函数调用不停增加,则从算法上来看,系统是不可能发生死锁的。

从无锁编程的定义,我们可以引出一个很重要的结果:假如说我们停止了一个线程,这个操作是不会影响其他线程的执行的。正因为如此,在编写实际程序的时候,所有的线程都必须能够在有限的时间内完成,不论其他的线程干了什么。

顺带一提,如果一个操作被设计成阻塞操作,他有可能仍然是无锁的。比如无锁队列的删除会在队列为空的时候被阻塞,这并不影响他是无锁的。

无锁编程的技巧

当你尝试去实现一个无阻塞的无锁程序,这会引出一系列技巧,比如:原子操作(atomic operations),内存屏障(memory barriers), ABA问题等。从这里开始,问题就变得棘手起来。

这些技巧是如何关联起来的呢?我准备使用一个流程图来解释这个问题:

原子的“读-修改-写”操作

原子操作的定义为一系列可以访问内存,并且不可分割的操作。没有任何线程可以观测到进行了一半的原子操作。在现代的处理器中,很多的操作都是原子的,比如:基础数据类型的“对齐读取(aligned reads)”和“对齐写(aligned writes)”通常是原子的。

更近一步,我们有了 读-修改-写(Read-modify-write) (RMW)操作,这个操作使我们可以原子化更复杂的操作,特别的,当有多个写线程时,这个操作非常有用。原因在于,当多个线程试图去读-修改-写一个内存区域时,他们会自动被排成不想交的一列,并依次执行。在之前的博客中,我已经讲过读-修改-写操作了,比如在 轻量锁, a 自旋锁 和  轻量的日志系统.

RMW操作的例子有Win32编程中的  _InterlockedIncrement ,IOS编程中的 OSAtomicAdd32 ,和C++11中的 std::atomic<int>::fetch_add 。值得注意的是,C++11标准并不保证这个实现是无锁的,具体是不是通过无锁来实现依赖于你的平台。因此,你最好提前了解你的平台是否支持这些无锁操作,或者通过调用 std::atomic<>::is_lock_free 来查看。

不同的CPU系列使用不同的方式支持RMW操作。比如PowerPC和ARM等处理器使用load-link/store-conditional 指令,这种指令使你能够在底层自定义你自己的RMW操作,即使通常并没有人这么干,毕竟普通的RMW操作已经足够了。

正如流程图中所说,RMW十分重要,即使是在只有一个处理器的系统中。如果没有了原子性,一个线程可能被中途打断,并导致一些潜在的问题。

“比较并交换”循环

最常讨论的RMW操作是 比较并交换(compare-and-swap) (CAS)。在Win32里面,CAS通过一系列intrinsics函数实现的,比如 _InterlockedCompareExchange 。通常情况下,我们在循环中使用CAS操作来尝试提交一些操作。具体来说,我们首先拷贝一些公有变量到局部变量中,并进行一些操作来改动局部变量的值,最后,将这些改动借助CAS操作提交至公有可见。

这样的循环是无锁的,因为如果一个线程的if条件测试为false,这意味着他一定紧接着另一个线程执行完毕相同操作的线程之后。尽管在一些架构下,存在 弱化的CAS操作,在这些CAS操作中,上述不一定是if语句判断false的充要条件,但是这些弱化的CAS操作仍然能够有效避免ABA问题。

顺序一致性

顺序一致性(Sequential Consistency)意味着所有的线程都有共同的对于内存访问操作的顺序的判定。这个判定的内存访问操作的顺序恰好等同于在源代码中的内存访问定义的顺序。在线性一致性模型中,一些内存顺序有关的问题不会发生。

一个非常简单(但是显然不可能在实际中使用的)解决内存一致性的方式是禁用编译器优化,并且强制所有的线程在同一个处理器上面运行。这样,即使存在着线程的切换,处理器将永远无法发现自己的内存顺序出现了问题。

一些编程语言即使在优化了代码之后,在多核环境中,依然保证了顺序移植性。在C++11中,你可以定义拥有默认内存顺序(memory ordering)的公共的原子数据类型来实现内存访问的移植性。在Java中,你可以将公有变量标记为 volatile 已实现顺序移植性。下面是一个例子:

由于C++原子操作保证了顺序一致性,因此结果r1 = r2 = 0是不会发生的。从编译器层面来看,编译器添加了一些额外的指令(如内存屏障或RMW操作)来保证顺序一致性。这些额外的指令带来了更大的时间花销,但是让程序员能够以最直观的方式操作内存顺序。

内存顺序

正如流程图中所述,当你在多核计算机上运行无锁程序,且你的程序并没有保证内存顺序一致性的时候,你需要思考如何避免内存乱序的发生。

在线代的处理器结构中,这些试图矫正内存顺序的方法可以分为两类分别是矫正 编译器导致的内存乱序(compiler reordering)处理器导致的内存乱序(processor reordering) 具体而言有如下方式:

  • 一系列轻量级的同步以及屏障指令,这些我将在之后讨论
  • 一系列内存屏障的指令,我在之前已经展示过
  • 一些内存顺序的指令,提供了acquire和release语义

Acquire语义防止该语句后的语句内存乱序,而Release语义防止了该语句之前语句的错排,这些语义特别适合用于处理“生产者/消费者”关联的线程关系,一个线程生产并广播消息,而另一个线程接收消息,这些我也将在之后的文章中详述。

不同处理器有不同的内存模型

不同的处理器有不同的内存模型,在内存重拍的问题上,不同的CPU以来的规则是依赖于硬件的,比如PowerPC和ARM处理器可以修改内存写的执行顺序,而Inter和AMD的x86/64处理器则不行。因此,古老的处理器有更加弱的内存模型(relaxed memory model).

通过C++11,我们可以调用一些固有的模板来无视掉这些由于平台导致的问题。不过我认为程序员们需要知道不同平台的区别。其中比较重要的一点事,在x86/64的处理器层面,所有的读(load)操作都自带了acquire语义,而所有的写(store)操作都自带了release语义,至少对于非SSE指令集和非并行储存的内存模型而言是这样的。从结果上来看,一些在x86/64上运行正常的程序在其他处理器上崩溃就不是一件很奇怪的事情了。

如果你对于处理器如何将内存操作重排感兴趣的话,我推荐你阅读Is Parallel Programming Hard的附录C。并且时刻警醒内存重排有时候是来自于编译器而非处理器。

在这篇文章中,我们有过多的提及无锁编程的一些实际代码编写上的策略,比如什么时候我们应该用无锁编程,我们应该做到什么程度,以及验证你程序有效性的必要性。对于大多数读者,这个简介只是为了给你一些无锁编程的最基本的概念,让你在之后的阅读中不会因为一些简单的概念而困惑。与之前相似,如果你发现有任何的不准确的地方,请通过评论告诉我。

原创文章地址:【无锁编程教程:简介】转载时请注明出处mhy12345.xyz