接上一篇文章,问题背景描述的差不多了,下面该解决方案登场了。
编译器优化乱序和CPU执行乱序的问题可以分别使用优化屏障 (Optimization Barrier)和内存屏障 (Memory Barrier)这两个机制来解决:
优化屏障 (Optimization Barrier):避免编译器的重排序优化操作,保证编译程序时在优化屏障之前的指令不会在优化屏障之后执行。这就保证了编译时期的优化不会影响到实际代码逻辑顺序。
IA-32/AMD64架构上,在Linux下常用的GCC编译器上,优化屏障定义为(linux kernel, include/linux/compiler-gcc.h):
优化屏障告知编译器:
C/C++的volatile关键字也能起到优化限制的作用,但是和Java中的volatile(Java 5之后)不同,C/C++中的volatile不提供任何防止乱序的功能,也并不保证访存的原子性。
内存屏障 (Memory Barrier)分为写屏障(Store Barrier)、读屏障(Load Barrier)和全屏障(Full Barrier),其作用有两个:
关于第一点,关于指令重排,这里不考虑架构的话,Load和Store两种操作会有Load-Store、Store-Load、Load-Load、Store-Store这四种可能的乱序结果。 上文提到的三种屏障则是限制这些不同乱序的机制。
关于第二点。写屏障会阻塞直到把Store Buffer中的数据刷到Cache中;读屏障会阻塞直到Invalid Queue中的消息执行完毕。以此来保证核间各级数据的一致性。
这里要强调,内存屏障解决的只是顺序一致性的问题,不解决Cache一致性的问题(这是Cache一致性协议的责任,也不需要程序员关注)。Store Buffer和Load Buffer等组件是属于流水线的一部分,和Cache无关。这里一定要区分清楚这两点,Cache一致性协议只是保证了Cache一致性(Cache Coherence),但是不关注顺序一致性(Sequential Consistency)的问题。比如,一个处理器对某变量A的写入操作仅比另一个处理器对A的读取操作提前很短的一点时间,那就不一定能确保该读取操作会返回新写入的值。这个新写入的值多久之后能确保被读取操作读取到,这是内存一致性模型(Memory Consistency Models)要讨论的问题。
完全的确保顺序一致性需要很大的代价,不仅限制编译器的优化,也限制了CPU的执行效率。为了更好地挖掘硬件的并行能力,现代的CPU多半都是介于两者之间,即所谓的宽松的内存一致性模型(Relaxed Memory Consistency Models)。不同的架构在重排上有各自的尺度,在严格排序和自由排序之间会有各自的偏向。偏向严格排序的一边,称之为强模型(Strong Model),而偏向于自由排序的一边,称之为弱模型(Weak Model)。AMD64架构是強模型:
特别地,早先时候,AMD64架构也会有Load-Load乱序发生(Memory Ordering in Modern Microprocessors, PaulE.McKenney, 2006)。
注意这里的IA-64(Intanium Processor Family)是弱模型,它和Intel® 64不是一回事。后者是从AMD交叉授权来的,源头就是AMD64架构。这里不讨论历史,只需要知道平时说的x86-64/x64就是指的AMD64架构即可。
《Intel® 64 and IA-32 Architectures Software Developer’s Manual》有如下的阐述:
简单翻译一下:
在多处理器的情况下,单处理器内部的内存访问排序仍然依照以上的原则,并且规定处理器与处理器之间遵循如下的原则:
那么上文提到的四种可能的乱序在AMD64下明确说明不会有Load-Load乱序、Load-Store乱序,明确会出现Store-Load乱序,Store-Store乱序除了几种例外的情况也不会出现。参考文献5中给出了在Linux下重现出Store-Load乱序的代码,有兴趣的读者可以自行测试。
但是内存一致性模型不仅仅是没有指令重排就会保证一致的。但是如果仅仅只考虑指令重排,完全按照该规则来思考,就会遇到违反直觉的事情。特别的,在对写缓存的同步处理上,AMD64内存访问模型的 Intra-Processor Forwarding Is Allowed这个特性比较要命:
只考虑指令重排的话,AMD64架构既然不会有Load-Load重排的,r2=r4=0就不可能会出现,但是实际的结果是违反直觉的。出现这个现象的原因就是Intel对Store Buffer的处理上,Store Buffer的修改对其他CPU核心是不可见的。Processor 0对_x的修改缓存在了Processor 0的Store Buffer中,还未提交到L1 Cache,自然也不会失效掉Processor 1的L1 Cache中的相关行。Processor 1对_y的修改同理。
对于以上问题,AMD64提供了三个内存屏障指令来解决:
sfence指令为写屏障(Store Barrier),作用是:
lfence指令读屏障(Load Barrier),作用是:
mfence指令全屏障(Full Barrier),作用是:
如前文所说,AMD64架构上是不存在Load-Load重排的,但是当一个CPU核心收到其他CPU核心失效Cache Line的消息后,立即回复给对方一个应答信号。但是此时并没有立即失效掉Cache Line,而是将其包装成一个结构投递到自身的Load Buffer里。AMD64架构上不存在Load-Load重排并不意味着流水线真的就一条一条执行Load指令。在保证两个CPU核看到的Store顺序一致的情况下,是允许Load乱序的。比如连续的两个访存指令,指令1 Cache Miss,指令2 Cache Hit,实际上指令2是不会真的等待指令1的Load完成整个Cache替换过程后才执行的。实际流水线的实现中,Load先是乱序执行,然后有一个Load-ordering-Buffer(Load Buffer)的结构,在Load Commit之前检测冲突,Load过的地址是否又被其他CPU核心写过(没有存在失效信息)。只要没有冲突,这种乱序就是安全的。如果发生冲突,这种乱序就违反x86要求,需要被取消并Flush流水线。而上文提到的lfence指令会刷新Load Buffer,保证当前CPU核心立即读取到最新的数据。
另外, 除了显式的内存屏障指令,有些指令也会造成指令保序的效果,比如I/O操作的指令、exch等原子交换的指令,任何带有lock前缀的指令以及CPUID等指令都有内存屏障的作用。
说了这么多,环形队列(Ring buffer)在IA-32/AMD64架构上到底怎么实现才能保证安全?Linux Kernel里的KFIFO的实现可以拿来参考(include/linux/kfifo.h):
现可以拿来参考(include/linux/kfifo.h):
代码中的smp_wmb()
、smp_rmb()
和smp_mb()
在AMD64架构上分别对应sfence
、lfence
、mfence
指令。但是Linux Kernel的代码要兼容所有的SMP架构,还要考虑很多弱内存模型的架构。所以这里的内存同步操作很多,但是不一定在AMD64上是必要的。当然,如果要考虑跨平台跨架构的代码,这样做是最保险的(另外Linux Kernel 4.0上KFIFO这个数据结构变化很大,内存同步操作也仅剩下smp_wmb()
,这个还没顾得上研究)。
如果IA-32/AMD64架构下,Ring Buffer如果要实现单Reader和单Writer不需要内存同步,需要满足哪些特性呢?
以下面的定义为例:
structring_buffer {uint32_tread_index;uint32_twrite_index;uchar_tbuffer[BUFF_LEN];};
首先,read_index
和write_index
的写入操作必须是原子的,这就要求这两个变量本身在P6 Family及以后的CPU上至少是不能跨Cache行的。同时如果是32-bit的变量则P6之前的CPU还要保持32-bit字节对齐,如果是64-bit变量在IA-32上无法保障(IA-32下64bit的变量Store操作不是原子的)。另外,为了避免False Sharing,这两个变量最好按照Cache行对齐,即:
structring_buffer {uint32_tread_index __attribute__ ((aligned(64)));uint32_twrite_index __attribute__ ((aligned(64)));uchar_tbuffer[BUFF_LEN];};
然后在入队和出队的地方插入编译屏障禁止掉编译器优化,根据Intel的文档,就能保证不会出现乱序问题:
主存写操作不能跟其他的写操作排序,但是以下情况除外:
在多处理器的情况下,单处理器内部的内存访问排序仍然依照以上的原则,并且规定处理器与处理器之间遵循如下的原则:
至于串操作,对buffer的修改可能是memcpy之类的操作,而对index的操作是普通赋值。memcpy在某些库中的实现使用了串操作指令又会怎样?会导致Store操作乱序吗?Intel有如下的说明:
所以不担心index的修改出现在rep:stosd之前。但是这样做是有这样的前提的,即Reader和Writer当前的修改不需要立即被对方知晓,即允许一段时间内的“不一致”。否则,必然需要内存屏障来确保修改操作全局一致。
以上的结论很容易引起口水仗,所以这里再次强调该结论只是在AMD64架构下,且不考虑可移植性的情况下成立。但是,按照我个人看法,这几个屏障指令不见得在所有Intel的CPU上都是有意义的,甚至有些屏障指令在Intel某些CPU上没有该屏障本身的语义。比如lfence本意是限制Load重排,然而AMD64就没有Load-Load乱序(内存可见性另说)。这几个屏障指令更像是Intel提供给软件开发者的一个Interface,在需要加屏障的地方让开发者加吧。至于实际上需不需要,CPU本身会判断,如果不需要的话直接由CPU直接NOP掉即可。这也是一种长远的考虑,那你问我在AMD64架构的CPU上写代码的时候,需要强一致的时候加不加屏障?那当时是要加的。按照Interface写代码是最保险的,万一Intel以后出一个采用弱一致模型的CPU(替被市场淘汰的IA-64默哀三分钟),遗留代码出点问题就不好了。
下面说说锁和原子变量。对于数据竞争(Data Races)的情况,最简单和最常见的场景就是使用Mutex了,包括并不限于互斥锁、自旋锁、读写锁等。拿互斥锁来说,除了保护临界区只能有一个执行流之外,还有其他的作用。这里要引入宽松的内存一致性模型(Relaxed Memory Consistency Models)中的Release Consistency模型[6]来解释,这个模型包含了同步操作Acquire和Release:
要注意的是Acquire和Release都只保证了一半的顺序:
因此Acquire和Release的组合便形成了内存屏障。
Mutex的Lock操作暗含了Acquire语义,Unlock暗含了Release语义。这里是脱离架构在讨论的,在具体的平台上如果Load和Store操作暗含Acquire和Release语义的话自然保证一致,否则可以是相关的内存屏障指令。所以Mutex不仅会保证执行的序列化,同时也保证了访存的一致性。与之类似,平台提供的原子变量除了保证内存操作原子之外,也会保证访存的一致性。
GCC提供了Built-in的原子操作函数可以使用,GCC 4以后的版本也提供了Built-in的屏障函数__sync_synchronize()
,这个屏障函数既是编译屏障又是内存屏障,代码插入这个函数的地方会被安插一条mfence
指令。不过GCC 4.4以上才支持mfence
,这个问题的讨论(bug?)在这里,Patch在这里。
实际上无锁的代码仅仅是不需要显式的Mutex来完成,但是存在数据竞争(Data Races)的情况下也会涉及到同步(Synchronization)的问题。从某种意义上来讲,所谓的无锁,仅仅只是颗粒度特别小的“锁”罢了,从代码层面上逐渐降低级别到CPU的指令级别而已,总会在某个层级上付出等待的代价,除非逻辑上彼此完全无关。另外,Lockfree
和Lockless
是两个概念,但这个话题太大,我个人尚且拿捏不住,就此打住。至于工程上,普通的程序员老老实实的用Mutex就好了,普通的计数类场景用原子变量也无可厚非。诸如无锁队列这种能明确证明其正确性的数据结构在一些场合也是很有价值的,用用无妨(但是多说一句,CAS这种乐观锁在核数很多的时候不见得高效,竞争太厉害的时候总体消耗很可能超出普通的锁)。但是如果不能做到在任何时候都能想明白顺序一致性的话,还是老老实实的用Mutex吧,否则造成的麻烦可比提升的这一点点效率折腾多了。
最后,讨论这些问题的文章太多了,各路说法到处飞,我也不敢保证这篇文章的说法全部正确,但至少我觉得是可以自圆其说的。如果你觉得哪里的描述有问题,不妨一起讨论,我们一起纠正这些错误的观点。
文章的撰写过程中参考了若干资料,下面列出的参考的资料和文章中,个别文章我只是“部分同意”原作者的观点,因为引用了作者部分说法,所以一并列出。这不代表我完全同意原作者观点,具体细节请读者自行判断(有了冲突,自然是以Intel最新文档的说法为准)。
[1] Intel® 64 and IA-32 Architectures Software Developer’s Manual,
https://software.intel.com/en-us/articles/intel-sdm
[2] Memory Barriers/Fences,
https://mechanical-sympathy.blogspot.jp/2011/07/memory-barriersfences.html
[3] Memory Barriers: a Hardware View for Software Hackers, Paul E. McKenney, Linux Technology Center, IBM Beaverton,
https://www.researchgate.net/publication/228824849_Memory_Barriers_a_Hardware_View_for_Software_Hackers
[4] 为什么程序员需要关心顺序一致性(Sequential Consistency)而不是Cache一致性(Cache Coherence)?,
http://www.parallellabs.com/2010/03/06/why-should-programmer-care-about-sequential-consistency-rather-than-cache-coherence/
[5] 一个关于Memory Reordering的实验,
http://blog.csdn.net/yxc135/article/details/11747995
[6] 计算机体系结构:量化研究方法, (美)亨尼西 等著, 机械工业出版社, 2012-1-1
[7] http://stackoverflow.com/questions/23603304/java-8-unsafe-xxxfence-instructions
[8] Intel Sandy Bridge Configuration, http://www.7-cpu.com/cpu/SandyBridge.html
[9] Intel’s Haswell CPU Microarchitecture, http://www.realworldtech.com/haswell-cpu/5/
[10] Write Combining, http://mechanical-sympathy.blogspot.com/2011/07/write-combining.html
[11] Memory ordering, https://en.wikipedia.org/wiki/Memory_ordering