聊聊原子變量、鎖、內存屏障那點事
突然想聊聊這個話題，是因為知乎上的一個問題多次出現在了我的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重排的，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)，作用是：
- 保證了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
