聊聊原子變量、鎖、內(nèi)存屏障那點(diǎn)事（2）

接上一篇文章，問題背景描述的差不多了，下面該解決方案登場(chǎng)了。

編譯器優(yōu)化亂序和CPU執(zhí)行亂序的問題可以分別使用優(yōu)化屏障 (Optimization Barrier)和內(nèi)存屏障 (Memory Barrier)這兩個(gè)機(jī)制來解決：

優(yōu)化屏障 (Optimization Barrier)：避免編譯器的重排序優(yōu)化操作，保證編譯程序時(shí)在優(yōu)化屏障之前的指令不會(huì)在優(yōu)化屏障之后執(zhí)行。這就保證了編譯時(shí)期的優(yōu)化不會(huì)影響到實(shí)際代碼邏輯順序。

IA-32/AMD64架構(gòu)上，在Linux下常用的GCC編譯器上，優(yōu)化屏障定義為（linux kernel, include/linux/compiler-gcc.h）：

優(yōu)化屏障告知編譯器：

1.內(nèi)存信息已經(jīng)修改，屏障后的寄存器的值必須從內(nèi)存中重新獲取

2.必須按照代碼順序產(chǎn)生匯編代碼，不得越過屏障

C/C++的volatile關(guān)鍵字也能起到優(yōu)化限制的作用，但是和Java中的volatile（Java 5之后）不同，C/C++中的volatile不提供任何防止亂序的功能，也并不保證訪存的原子性。

內(nèi)存屏障 (Memory Barrier)分為寫屏障（Store Barrier）、讀屏障（Load Barrier）和全屏障（Full Barrier），其作用有兩個(gè)：

防止指令之間的重排序

保證數(shù)據(jù)的可見性

關(guān)于第一點(diǎn)，關(guān)于指令重排，這里不考慮架構(gòu)的話，Load和Store兩種操作會(huì)有Load-Store、Store-Load、Load-Load、Store-Store這四種可能的亂序結(jié)果。 上文提到的三種屏障則是限制這些不同亂序的機(jī)制。

關(guān)于第二點(diǎn)。寫屏障會(huì)阻塞直到把Store Buffer中的數(shù)據(jù)刷到Cache中；讀屏障會(huì)阻塞直到Invalid Queue中的消息執(zhí)行完畢。以此來保證核間各級(jí)數(shù)據(jù)的一致性。

這里要強(qiáng)調(diào)，內(nèi)存屏障解決的只是順序一致性的問題，不解決Cache一致性的問題（這是Cache一致性協(xié)議的責(zé)任，也不需要程序員關(guān)注）。Store Buffer和Load Buffer等組件是屬于流水線的一部分，和Cache無關(guān)。這里一定要區(qū)分清楚這兩點(diǎn)，Cache一致性協(xié)議只是保證了Cache一致性（Cache Coherence），但是不關(guān)注順序一致性（Sequential Consistency）的問題。比如，一個(gè)處理器對(duì)某變量A的寫入操作僅比另一個(gè)處理器對(duì)A的讀取操作提前很短的一點(diǎn)時(shí)間，那就不一定能確保該讀取操作會(huì)返回新寫入的值。這個(gè)新寫入的值多久之后能確保被讀取操作讀取到，這是內(nèi)存一致性模型（Memory Consistency Models）要討論的問題。

完全的確保順序一致性需要很大的代價(jià)，不僅限制編譯器的優(yōu)化，也限制了CPU的執(zhí)行效率。為了更好地挖掘硬件的并行能力，現(xiàn)代的CPU多半都是介于兩者之間，即所謂的寬松的內(nèi)存一致性模型（Relaxed Memory Consistency Models）。不同的架構(gòu)在重排上有各自的尺度，在嚴(yán)格排序和自由排序之間會(huì)有各自的偏向。偏向嚴(yán)格排序的一邊，稱之為強(qiáng)模型（Strong Model），而偏向于自由排序的一邊，稱之為弱模型（Weak Model）。AMD64架構(gòu)是強(qiáng)模型：

特別地，早先時(shí)候，AMD64架構(gòu)也會(huì)有Load-Load亂序發(fā)生（Memory Ordering in Modern Microprocessors, PaulE.McKenney, 2006）。

注意這里的IA-64（Intanium Processor Family）是弱模型，它和Intel? 64不是一回事。后者是從AMD交叉授權(quán)來的，源頭就是AMD64架構(gòu)。這里不討論歷史，只需要知道平時(shí)說的x86-64/x64就是指的AMD64架構(gòu)即可。

《Intel? 64 and IA-32 Architectures Software Developer’s Manual》有如下的闡述：

簡(jiǎn)單翻譯一下：

讀操作之間不能重新排序

寫操作不能跟舊的讀操作排序

主存寫操作不能跟其他的寫操作排序，但是以下情況除外：

帶有CLFLUSH（失效緩存）指令的寫操作

帶有non-temporal move指令的流存儲(chǔ)（寫入）（MOVNTI, MOVNTQ, MOVNTDQ, MOVNTPS, 和 MOVNTPD，都是SSE/SSE2擴(kuò)展的指令）

字符串操作（REP STOSD等）

不同內(nèi)存地址的讀可以與較早的寫排序，同一地址的情況除外

對(duì)I/O指令、鎖指令、序列化指令的讀寫不能重排序

讀不能越過較早的讀屏障指令（LFENCE）或者全屏障指令（MFENCE）

寫不能越過較早的讀屏障指令（LFENCE）、寫屏障指令（SFENCE）和全屏障指令（MFENCE）

讀屏障指令（LFENCE）不能越過較早的讀

寫屏障指令（SFENCE）不能越過較早的寫

全屏障指令（MFENCE）不能越過較早的讀和寫

在多處理器的情況下，單處理器內(nèi)部的內(nèi)存訪問排序仍然依照以上的原則，并且規(guī)定處理器與處理器之間遵循如下的原則：

某個(gè)處理器的全部寫操作以同樣的順序被其它處理器觀察到

不同處理器之間的寫操作不重排序

排序遵循邏輯上的因果關(guān)系

第三方總是觀察到一致的寫操作順序

那么上文提到的四種可能的亂序在AMD64下明確說明不會(huì)有Load-Load亂序、Load-Store亂序，明確會(huì)出現(xiàn)Store-Load亂序，Store-Store亂序除了幾種例外的情況也不會(huì)出現(xiàn)。參考文獻(xiàn)5中給出了在Linux下重現(xiàn)出Store-Load亂序的代碼，有興趣的讀者可以自行測(cè)試。

但是內(nèi)存一致性模型不僅僅是沒有指令重排就會(huì)保證一致的。但是如果僅僅只考慮指令重排，完全按照該規(guī)則來思考，就會(huì)遇到違反直覺的事情。特別的，在對(duì)寫緩存的同步處理上，AMD64內(nèi)存訪問模型的Intra-Processor Forwarding Is Allowed這個(gè)特性比較要命：

只考慮指令重排的話，AMD64架構(gòu)既然不會(huì)有Load-Load重排的，r2=r4=0就不可能會(huì)出現(xiàn)，但是實(shí)際的結(jié)果是違反直覺的。出現(xiàn)這個(gè)現(xiàn)象的原因就是Intel對(duì)Store Buffer的處理上，Store Buffer的修改對(duì)其他CPU核心是不可見的。Processor 0對(duì)_x的修改緩存在了Processor 0的Store Buffer中，還未提交到L1 Cache，自然也不會(huì)失效掉Processor 1的L1 Cache中的相關(guān)行。Processor 1對(duì)_y的修改同理。

對(duì)于以上問題，AMD64提供了三個(gè)內(nèi)存屏障指令來解決：

sfence指令為寫屏障（Store Barrier），作用是：

保證了sfence前后Store指令的順序，防止Store重排序

通過刷新Store Buffer保證sfence之前的Store要指令對(duì)全局可見

lfence指令讀屏障（Load Barrier），作用是：

保證了lfence前后的Load指令的順序，防止Load重排序

刷新Load Buffer

mfence指令全屏障（Full Barrier），作用是：

保證了mfence前后的Store和Load指令的順序，防止Store和Load重排序

保證了mfence之后的Store指令全局可見之前，mfence之前的Store指令要先全局可見

如前文所說，AMD64架構(gòu)上是不存在Load-Load重排的，但是當(dāng)一個(gè)CPU核心收到其他CPU核心失效Cache Line的消息后，立即回復(fù)給對(duì)方一個(gè)應(yīng)答信號(hào)。但是此時(shí)并沒有立即失效掉Cache Line，而是將其包裝成一個(gè)結(jié)構(gòu)投遞到自身的Load Buffer里。AMD64架構(gòu)上不存在Load-Load重排并不意味著流水線真的就一條一條執(zhí)行Load指令。在保證兩個(gè)CPU核看到的Store順序一致的情況下，是允許Load亂序的。比如連續(xù)的兩個(gè)訪存指令，指令1 Cache Miss，指令2 Cache Hit，實(shí)際上指令2是不會(huì)真的等待指令1的Load完成整個(gè)Cache替換過程后才執(zhí)行的。實(shí)際流水線的實(shí)現(xiàn)中，Load先是亂序執(zhí)行，然后有一個(gè)Load-ordering-Buffer（Load Buffer）的結(jié)構(gòu)，在Load Commit之前檢測(cè)沖突，Load過的地址是否又被其他CPU核心寫過（沒有存在失效信息）。只要沒有沖突，這種亂序就是安全的。如果發(fā)生沖突，這種亂序就違反x86要求，需要被取消并Flush流水線。而上文提到的lfence指令會(huì)刷新Load Buffer，保證當(dāng)前CPU核心立即讀取到最新的數(shù)據(jù)。

另外， 除了顯式的內(nèi)存屏障指令，有些指令也會(huì)造成指令保序的效果，比如I/O操作的指令、exch等原子交換的指令，任何帶有l(wèi)ock前綴的指令以及CPUID等指令都有內(nèi)存屏障的作用。

說了這么多，環(huán)形隊(duì)列（Ring buffer）在IA-32/AMD64架構(gòu)上到底怎么實(shí)現(xiàn)才能保證安全？Linux Kernel里的KFIFO的實(shí)現(xiàn)可以拿來參考（include/linux/kfifo.h）：

現(xiàn)可以拿來參考（include/linux/kfifo.h）：

代碼中的smp_wmb()、smp_rmb()和smp_mb()在AMD64架構(gòu)上分別對(duì)應(yīng)sfence、lfence、mfence指令。但是Linux Kernel的代碼要兼容所有的SMP架構(gòu)，還要考慮很多弱內(nèi)存模型的架構(gòu)。所以這里的內(nèi)存同步操作很多，但是不一定在AMD64上是必要的。當(dāng)然，如果要考慮跨平臺(tái)跨架構(gòu)的代碼，這樣做是最保險(xiǎn)的（另外Linux Kernel 4.0上KFIFO這個(gè)數(shù)據(jù)結(jié)構(gòu)變化很大，內(nèi)存同步操作也僅剩下smp_wmb()，這個(gè)還沒顧得上研究）。

如果IA-32/AMD64架構(gòu)下，Ring Buffer如果要實(shí)現(xiàn)單Reader和單Writer不需要內(nèi)存同步，需要滿足哪些特性呢？

以下面的定義為例：

structring_buffer {

uint32_tread_index;

uint32_twrite_index;

uchar_tbuffer[BUFF_LEN];

};

首先，read_index和write_index的寫入操作必須是原子的，這就要求這兩個(gè)變量本身在P6 Family及以后的CPU上至少是不能跨Cache行的。同時(shí)如果是32-bit的變量則P6之前的CPU還要保持32-bit字節(jié)對(duì)齊，如果是64-bit變量在IA-32上無法保障（IA-32下64bit的變量Store操作不是原子的）。另外，為了避免False Sharing，這兩個(gè)變量最好按照Cache行對(duì)齊，即：

structring_buffer {

uint32_tread_index __attribute__ ((aligned(64)));

uint32_twrite_index __attribute__ ((aligned(64)));

uchar_tbuffer[BUFF_LEN];

};

然后在入隊(duì)和出隊(duì)的地方插入編譯屏障禁止掉編譯器優(yōu)化，根據(jù)Intel的文檔，就能保證不會(huì)出現(xiàn)亂序問題：

主存寫操作不能跟其他的寫操作排序，但是以下情況除外：

帶有CLFLUSH（失效緩存）指令的寫操作

帶有non-temporal move指令的流存儲(chǔ)（寫入）（MOVNTI, MOVNTQ, MOVNTDQ, MOVNTPS, 和 MOVNTPD，都是SSE/SSE2擴(kuò)展的指令）

字符串操作（REP STOSD等）

在多處理器的情況下，單處理器內(nèi)部的內(nèi)存訪問排序仍然依照以上的原則，并且規(guī)定處理器與處理器之間遵循如下的原則：

某個(gè)處理器的全部寫操作以同樣的順序被其它處理器觀察到

第三方總是觀察到一致的寫操作順序

至于串操作，對(duì)buffer的修改可能是memcpy之類的操作，而對(duì)index的操作是普通賦值。memcpy在某些庫(kù)中的實(shí)現(xiàn)使用了串操作指令又會(huì)怎樣？會(huì)導(dǎo)致Store操作亂序嗎？Intel有如下的說明：

所以不擔(dān)心index的修改出現(xiàn)在rep:stosd之前。但是這樣做是有這樣的前提的，即Reader和Writer當(dāng)前的修改不需要立即被對(duì)方知曉，即允許一段時(shí)間內(nèi)的“不一致”。否則，必然需要內(nèi)存屏障來確保修改操作全局一致。

以上的結(jié)論很容易引起口水仗，所以這里再次強(qiáng)調(diào)該結(jié)論只是在AMD64架構(gòu)下，且不考慮可移植性的情況下成立。但是，按照我個(gè)人看法，這幾個(gè)屏障指令不見得在所有Intel的CPU上都是有意義的，甚至有些屏障指令在Intel某些CPU上沒有該屏障本身的語義。比如lfence本意是限制Load重排，然而AMD64就沒有Load-Load亂序（內(nèi)存可見性另說）。這幾個(gè)屏障指令更像是Intel提供給軟件開發(fā)者的一個(gè)Interface，在需要加屏障的地方讓開發(fā)者加吧。至于實(shí)際上需不需要，CPU本身會(huì)判斷，如果不需要的話直接由CPU直接NOP掉即可。這也是一種長(zhǎng)遠(yuǎn)的考慮，那你問我在AMD64架構(gòu)的CPU上寫代碼的時(shí)候，需要強(qiáng)一致的時(shí)候加不加屏障？那當(dāng)時(shí)是要加的。按照Interface寫代碼是最保險(xiǎn)的，萬一Intel以后出一個(gè)采用弱一致模型的CPU（替被市場(chǎng)淘汰的IA-64默哀三分鐘），遺留代碼出點(diǎn)問題就不好了。

下面說說鎖和原子變量。對(duì)于數(shù)據(jù)競(jìng)爭(zhēng)（Data Races）的情況，最簡(jiǎn)單和最常見的場(chǎng)景就是使用Mutex了，包括并不限于互斥鎖、自旋鎖、讀寫鎖等。拿互斥鎖來說，除了保護(hù)臨界區(qū)只能有一個(gè)執(zhí)行流之外，還有其他的作用。這里要引入寬松的內(nèi)存一致性模型（Relaxed Memory Consistency Models）中的Release Consistency模型[6]來解釋，這個(gè)模型包含了同步操作Acquire和Release：

Acquire: 在此操作后的所有讀寫操作必然發(fā)生在Acquire這個(gè)動(dòng)作之后

Release: 在此操作前的所有讀寫操作必然發(fā)生在Release這個(gè)動(dòng)作之前

要注意的是Acquire和Release都只保證了一半的順序：

對(duì)于Acquire來說，并沒保證Acquire前的讀寫操作不會(huì)發(fā)生在Acquire動(dòng)作之后

對(duì)于Release來說，并沒保證Release后的讀寫操作不會(huì)發(fā)生在Release動(dòng)作之前

因此Acquire和Release的組合便形成了內(nèi)存屏障。

Mutex的Lock操作暗含了Acquire語義，Unlock暗含了Release語義。這里是脫離架構(gòu)在討論的，在具體的平臺(tái)上如果Load和Store操作暗含Acquire和Release語義的話自然保證一致，否則可以是相關(guān)的內(nèi)存屏障指令。所以Mutex不僅會(huì)保證執(zhí)行的序列化，同時(shí)也保證了訪存的一致性。與之類似，平臺(tái)提供的原子變量除了保證內(nèi)存操作原子之外，也會(huì)保證訪存的一致性。

GCC提供了Built-in的原子操作函數(shù)可以使用，GCC 4以后的版本也提供了Built-in的屏障函數(shù)__sync_synchronize()，這個(gè)屏障函數(shù)既是編譯屏障又是內(nèi)存屏障，代碼插入這個(gè)函數(shù)的地方會(huì)被安插一條mfence指令。不過GCC 4.4以上才支持mfence，這個(gè)問題的討論（bug？）在這里，Patch在這里。

實(shí)際上無鎖的代碼僅僅是不需要顯式的Mutex來完成，但是存在數(shù)據(jù)競(jìng)爭(zhēng)（Data Races）的情況下也會(huì)涉及到同步（Synchronization）的問題。從某種意義上來講，所謂的無鎖，僅僅只是顆粒度特別小的“鎖”罷了，從代碼層面上逐漸降低級(jí)別到CPU的指令級(jí)別而已，總會(huì)在某個(gè)層級(jí)上付出等待的代價(jià)，除非邏輯上彼此完全無關(guān)。另外，Lockfree和Lockless是兩個(gè)概念，但這個(gè)話題太大，我個(gè)人尚且拿捏不住，就此打住。至于工程上，普通的程序員老老實(shí)實(shí)的用Mutex就好了，普通的計(jì)數(shù)類場(chǎng)景用原子變量也無可厚非。諸如無鎖隊(duì)列這種能明確證明其正確性的數(shù)據(jù)結(jié)構(gòu)在一些場(chǎng)合也是很有價(jià)值的，用用無妨（但是多說一句，CAS這種樂觀鎖在核數(shù)很多的時(shí)候不見得高效，競(jìng)爭(zhēng)太厲害的時(shí)候總體消耗很可能超出普通的鎖）。但是如果不能做到在任何時(shí)候都能想明白順序一致性的話，還是老老實(shí)實(shí)的用Mutex吧，否則造成的麻煩可比提升的這一點(diǎn)點(diǎn)效率折騰多了。

最后，討論這些問題的文章太多了，各路說法到處飛，我也不敢保證這篇文章的說法全部正確，但至少我覺得是可以自圓其說的。如果你覺得哪里的描述有問題，不妨一起討論，我們一起糾正這些錯(cuò)誤的觀點(diǎn)。

文章的撰寫過程中參考了若干資料，下面列出的參考的資料和文章中，個(gè)別文章我只是“部分同意”原作者的觀點(diǎn)，因?yàn)橐昧俗髡卟糠终f法，所以一并列出。這不代表我完全同意原作者觀點(diǎn)，具體細(xì)節(jié)請(qǐng)讀者自行判斷（有了沖突，自然是以Intel最新文檔的說法為準(zhǔn)）。