歡迎光臨
每天分享高質量文章

聊聊原子變數、鎖、記憶體屏障那點事(1)

突然想聊聊這個話題,是因為知乎上的一個問題多次出現在了我的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_indexwriter_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給出了相關的資料可以進一步閱讀。


赞(0)

分享創造快樂