珠海网站设计公司,潍坊建设网站公司电话,wordpress awesome图标,网络公司网页设计突然想聊聊这个话题#xff0c;是因为知乎上的一个问题多次出现在了我的Timeline里#xff1a;请问#xff0c;多个线程可以读一个变量#xff0c;只有一个线程可以对这个变量进行写#xff0c;到底要不要加锁?可惜的是很多高票答案语焉不详#xff0c;甚至有所错漏。
…突然想聊聊这个话题是因为知乎上的一个问题多次出现在了我的Timeline里请问多个线程可以读一个变量只有一个线程可以对这个变量进行写到底要不要加锁?可惜的是很多高票答案语焉不详甚至有所错漏。
作者浅墨 突然想聊聊这个话题是因为知乎上的一个问题多次出现在了我的Timeline里请问多个线程可以读一个变量只有一个线程可以对这个变量进行写到底要不要加锁?可惜的是很多高票答案语焉不详甚至有所错漏。所以我想在这篇文章里斗胆聊聊这个水挺深的问题。受限于个人水平文章若有错漏还望读者不吝赐教。
首先约定由于CPU的架构和设计浩如烟海本文站在工程师的角度只谈IA32/AMD64(x86-64)架构不讨论其他架构的细节和差异。并且文章中主要引用Intel的文档予以佐证不关注AMD在实现细节上的差异。
众所周知当一个执行中的程序的数据被多个执行流并发访问的时候就会涉及到同步(Synchronization)的问题。同步的目的是保证不同执行流对共享数据并发操作的一致性。早在单核时代使用锁或者原子变量就很容易达成这一目的。甚至因为CPU的一些访存特性对某些内存对齐数据的读或写也具有原子的特性。
比如在《Intel® 64 and IA-32 Architectures Software Developer’s Manual》的第三卷System Programming Guide的Chapter 8 Multiple-Processor Management里就给出了这样的说明 也就是说有些内存对齐的数据的访问在CPU层面就是原子进行的(注意这里说的只是单次的读或者写类似普通变量i的i操作不止一次内存访问)。此时环形队列(Ring buffer)这种数据结构在某些架构的单核CPU上只有一个Reader和一个Writer的情况下是不需要额外同步措施的。原因就是read_index和writer_index的写操作在满足对齐内存访问的情况下是原子的不需要额外的同步措施。注意这里我加粗了单核CPU这个关键字那么到了多核心处理器的今天该操作就不是原子了吗?不依旧是原子的但是出现了其他的干扰因素迫使可能需要额外的同步措施才能保证原本无锁代码的正确运行。
首先是现代编译器的代码优化和编译器指令重排可能会影响到代码的执行顺序。编译期指令重排是通过调整代码中的指令顺序在不改变代码语义的前提下对变量访问进行优化。从而尽可能的减少对寄存器的读取和存储并充分复用寄存器。但是编译器对数据的依赖关系判断只能在单执行流内无法判断其他执行流对竞争数据的依赖关系。就拿无锁环形队列来说如果Writer做的是先放置数据再更新索引的行为。如果索引先于数据更新Reader就有可能会因为判断索引已更新而读到脏数据。
那禁止编译器对该类变量的优化解决了编译期的重排序就没事了吗?不CPU还有乱序执行(Out-of-Order Execution)的特性。流水线(Pipeline)和乱序执行是现代CPU基本都具有的特性。机器指令在流水线中经历取指、译码、执行、访存、写回等操作。为了CPU的执行效率流水线都是并行处理的在不影响语义的情况下。处理器次序(Process Ordering机器指令在CPU实际执行时的顺序)和程序次序(Program Ordering程序代码的逻辑执行顺序)是允许不一致的即满足As-if-Serial特性。显然这里的不影响语义依旧只能是保证指令间的显式因果关系无法保证隐式因果关系。即无法保证语义上不相关但是在程序逻辑上相关的操作序列按序执行。从此单核时代CPU的Self-Consistent特性在多核时代已不存在多核CPU作为一个整体看不再满足Self-Consistent特性。
简单总结一下如果不做多余的防护措施单核时代的无锁环形队列在多核CPU中一个CPU核心上的Writer写入数据更新index后。另一个CPU核心上的Reader依靠这个index来判断数据是否写入的方式不一定可靠。index有可能先于数据被写入从而导致Reader读到脏数据。
所有的麻烦到这里就结束了吗?当然不还有Cache的问题。前文提到的都是顺序一致性(Sequential Consistency)的问题没有涉及Cache一致性(Cache Coherence)的问题。虽然说一般情况下程序员只需要关注顺序一致性即可但是区分清楚这两个概念也能更好的解释内存屏障(Memory Barrier)。
开始提到Cache一致性协议之前先介绍两个名词
Load/Read CPU读操作是指将内存数据加载到寄存器的过程
Store/Write CPU写操作是指将寄存器数据写回主存的过程
现代处理器的缓存一般分为三级由每一个核心独享的L1、L2 Cache以及所有的核心共享L3 Cache组成 由于Cache的容量很小一般都是充分的利用局部性原理按行/块来和主存进行批量数据交换以提升数据的访问效率。以前写过一篇《浅析x86架构中cache的组织结构》这里不再赘述。既然各个核心之间有独立的Cache存储器那么这些存储器之间的数据同步就是个比较复杂的事情。缓存数据的一致性由缓存一致性协议保证。这里比较经典的当属MESI协议。Intel的处理器使用从MESI中演化出的MESIF协议而AMD使用MOESI协议。缓存一致性协议的细节超出了本文的讨论范围有兴趣的读者可以自行研究。
传统的MESI协议中有两个行为的执行成本比较大。一个是将某个Cache Line标记为Invalid状态另一个是当某Cache Line当前状态为Invalid时写入新的数据。所以CPU通过Store Buffer和Invalidate Queue组件来降低这类操作的延时。如图 当一个核心在Invalid状态进行写入时首先会给其它CPU核发送Invalid消息然后把当前写入的数据写入到Store Buffer中。然后异步在某个时刻真正的写入到Cache Line中。当前CPU核如果要读Cache Line中的数据需要先扫描Store Buffer之后再读取Cache Line(Store-Buffer Forwarding)。但是此时其它CPU核是看不到当前核的Store Buffer中的数据的要等到Store Buffer中的数据被刷到了Cache Line之后才会触发失效操作。而当一个CPU核收到Invalid消息时会把消息写入自身的Invalidate Queue中随后异步将其设为Invalid状态。和Store Buffer不同的是当前CPU核心使用Cache时并不扫描Invalidate Queue部分所以可能会有极短时间的脏读问题。当然这里的Store Buffer和Invalidate Queue的说法是针对一般的SMP架构来说的不涉及具体架构。事实上除了Store Buffer和Load Buffer流水线为了实现并行处理还有Line Fill Buffer/Write Combining Buffer 等组件参考文献8-10给出了相关的资料可以进一步阅读。 好了问题背景描述的差不多了下面该解决方案登场了。
编译器优化乱序和CPU执行乱序的问题可以分别使用优化屏障 (Optimization Barrier)和内存屏障 (Memory Barrier)这两个机制来解决
优化屏障 (Optimization Barrier)避免编译器的重排序优化操作保证编译程序时在优化屏障之前的指令不会在优化屏障之后执行。这就保证了编译时期的优化不会影响到实际代码逻辑顺序。
IA-32/AMD64架构上在Linux下常用的GCC编译器上优化屏障定义为(linux kernel, include/linux/compiler-gcc.h)
#define barrier() __asm__ __volatile__(: : :memory)
优化屏障告知编译器
内存信息已经修改屏障后的寄存器的值必须从内存中重新获取必须按照代码顺序产生汇编代码不得越过屏障
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》有如下的阐述 简单翻译一下
读操作之间不能重新排序
写操作不能跟旧的读操作排序
主存写操作不能跟其他的写操作排序但是以下情况除外
带有CLFLUSH(失效缓存)指令的写操作
带有non-temporal move指令的流存储(写入)(MOVNTI, MOVNTQ, MOVNTDQ, MOVNTPS, 和 MOVNTPD都是SSE/SSE2扩展的指令)
字符串操作(REP STOSD等)
不同内存地址的读可以与较早的写排序同一地址的情况除外
对I/O指令、锁指令、序列化指令的读写不能重排序
读不能越过较早的读屏障指令(LFENCE)或者全屏障指令(MFENCE)
写不能越过较早的读屏障指令(LFENCE)、写屏障指令(SFENCE)和全屏障指令(MFENCE)
读屏障指令(LFENCE)不能越过较早的读
写屏障指令(SFENCE)不能越过较早的写
全屏障指令(MFENCE)不能越过较早的读和写
在多处理器的情况下单处理器内部的内存访问排序仍然依照以上的原则并且规定处理器与处理器之间遵循如下的原则
某个处理器的全部写操作以同样的顺序被其它处理器观察到
不同处理器之间的写操作不重排序
排序遵循逻辑上的因果关系
第三方总是观察到一致的写操作顺序
那么上文提到的四种可能的乱序在AMD64下明确说明不会有Load-Load乱序、Load-Store乱序明确会出现Store-Load乱序Store-Store乱序除了几种例外的情况也不会出现。参考文献5中给出了在Linux下重现出Store-Load乱序的代码有兴趣的读者可以自行测试。
但是内存一致性模型不仅仅是没有指令重排就会保证一致的。但是如果仅仅只考虑指令重排完全按照该规则来思考就会遇到违反直觉的事情。特别的在对写缓存的同步处理上AMD64内存访问模型的 Intra-Processor Forwarding Is Allowed这个特性比较要命 只考虑指令重排的话AMD64架构既然不会有Load-Load重排的r2r40就不可能会出现但是实际的结果是违反直觉的。出现这个现象的原因就是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)作用是
保证了sfence前后Store指令的顺序防止Store重排序通过刷新Store Buffer保证sfence之前的Store要指令对全局可见
lfence指令读屏障(Load Barrier)作用是
保证了lfence前后的Load指令的顺序防止Load重排序刷新Load Buffer
mfence指令全屏障(Full Barrier)作用是
保证了mfence前后的Store和Load指令的顺序防止Store和Load重排序保证了mfence之后的Store指令全局可见之前mfence之前的Store指令要先全局可见
如前文所说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)
代码中的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不需要内存同步需要满足哪些特性呢?
以下面的定义为例
struct ring_buffer { uint32_t read_index; uint32_t write_index; uchar_t buffer[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行对齐即
struct ring_buffer { uint32_t read_index __attribute__ ((aligned(64))); uint32_t write_index __attribute__ ((aligned(64))); uchar_t buffer[BUFF_LEN]; };
然后在入队和出队的地方插入编译屏障禁止掉编译器优化根据Intel的文档就能保证不会出现乱序问题
主存写操作不能跟其他的写操作排序但是以下情况除外
带有CLFLUSH(失效缓存)指令的写操作带有non-temporal move指令的流存储(写入)(MOVNTI, MOVNTQ, MOVNTDQ, MOVNTPS, 和 MOVNTPD都是SSE/SSE2扩展的指令)字符串操作(REP STOSD等)
在多处理器的情况下单处理器内部的内存访问排序仍然依照以上的原则并且规定处理器与处理器之间遵循如下的原则
某个处理器的全部写操作以同样的顺序被其它处理器观察到第三方总是观察到一致的写操作顺序
至于串操作对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: 在此操作后的所有读写操作必然发生在Acquire这个动作之后Release: 在此操作前的所有读写操作必然发生在Release这个动作之前
要注意的是Acquire和Release都只保证了一半的顺序
对于Acquire来说并没保证Acquire前的读写操作不会发生在Acquire动作之后对于Release来说并没保证Release后的读写操作不会发生在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
阅读目录置顶)(长期更新计算机领域知识
阅读目录置顶)(长期更新计算机领域知识
阅读目录置顶)(长期科技领域知识
歌谣带你看java面试题
