深入理解一致性與 C++ 記憶體模型

語言: CN / TW / HK

本文旨在對電腦科學下的 一致性模型 以及 C++ 的記憶體模型 做一個系統的、深入淺出的介紹。一共 3 個 章節:第 1 章介紹一致性模型,第 2 章介紹 C++ 記憶體模型,第 3 章是參考資料。

1. Consistency model

上圖摘自 https://jepsen.io/consistency,這是一個對一致性比較好的分類和總結。

右面的分支表達了 operations 之間的順序以及可見性,左面的分支表達了 operations 作為 group 時的特性,比如一組 operations 可能需要和另一組 operations 具有某種組級別的作為整體來看的一致性語義,一般來說就是事務性,要滿足一定的完整性約束。下面分別就兩個方向所涉及到的各種主要的一致性概念進行介紹。

1.1 Non Transaction

本節關於一致性的介紹是按照嚴格到放鬆的順序來介紹的,在每一個一致性介紹的開始處都有相比較上一個一致性的說明,因此最好按照順序去理解概念。

Data-centric consistency models

嚴格一致性 Strict consistency

嚴格一致性是最強的一致性保證,任意處理單元對變數的寫入要求對所有處理單元立刻可見。

可以看出這樣實現對效能的影響非常不好,需要有很大的通訊開銷來保證可見性,實際上基本沒有實現這個一致性級別的系統。

線性一致性 Linearizability(Atomic consistency)

線性一致性不是一個很容易深入理解的簡單概念,很多人都誤會線性一致性為作用在一個物件上的概念,其實這麼理解是錯誤的,線性一致性沒有作用到一個物件上的約束,如開頭分類時提到的,只不過沒有對 operations 進行 group 行為(一般來講就是事務性)的約束而已,是面向多物件下一般化場景的。線性一致性沒有嚴格一致性要求的那麼強,只是“看起來像”嚴格一致性,沒有那麼強的 瞬時性(instantaneousness) 要求。這裡分兩個方面介紹線性一致性:一個是個人的提煉直觀理解,一個是 wikipedia 中的定義。

  • 直觀理解

對於一個系統如果所有 呼叫(Invocations) 和 響應(Responses) 從特性上描述滿足如下條件,則滿足線性一致性:

  1. 滿足 real-time,即在 invocation 和 reponse 之間產生影響。

  2. 具有原子性,不會比如因為 client 自身的 retry 導致一個自增動作執行多次。

  • 正式定義

Wikipedia 中更正式的概念是(解釋翻譯版,Wikipedia 詞條中有原文)

對於一個 invocations 和 responses 的歷史 H,如果滿足下面的條件則 H 就是線性化的:

  • 對於 H 中完成的所有操作,返回的結果必須等價於某一個 操作看成原子(invocation 得到 reponse 是立刻的) 的情況下構成的序列執行的歷史。

  • 實際執行過程中如果一個操作 op1 在另一個操作 op2 完成之前,那麼在 H 中 op1 也必須在 op2 之前。

換句話說:

  • H 的所有 invocations 和 responses 可以被重排序成一個按順序(序列)的歷史;

  • 如果滿足程式的語義(sequential definition of the object or semantics of the program),則這個順序歷史就是正確的;

  • 如果在原始的歷史中一個響應在另一個呼叫的前面,那在重排序的順序歷史中也必須同樣如此。

單看概念有點抽象,下面舉個例子。假設有這樣一個併發執行下的 real-time 觀察到的歷史:

其中,I 代表 invocation,R 代表 response,A、B 代表不同的執行緒,1、2 代表不同的物件。

根據 wikipedia 定義中的規則,我們可以 reorder 出下面幾個 符合規則的 排程歷史:

而下面這個排程歷史就是 不符合規則 的:

由於 RB1 在 IA2 之前,所以這樣 reorder 破壞了規則:

如果在原始的歷史中一個響應在另一個呼叫的前面,那在重排序的順序歷史中也必須同樣如此。

那麼現在有了這些,我們怎麼判定 H_C 是一個正確的歷史?答案就是隻要任何一個根據 reorder 規則得到的排程歷史是正確的(如果滿足程式的語義 sequential definition of the object or semantics of the program),則 H_C 就是一個正確的歷史,這個排程就是線性化的。進一步, 如果一個系統所有的歷史都是線性化的,則這個系統是滿足線性一致性的

上述的描述還是有一點太抽象,這裡給出 直觀的解釋

  1. 滿足程式序:reorder 的時候不會破壞具有時序關係的操作的順序,但是對於併發的操作 reorder 的時候順序任意,因為併發了本身結果就是無法預測,進而怎麼 reorder 都可以。

  2. 對於 reorder 之後得到的排程歷史,只要有任何一個滿足程式的語義,則可以認為這個排程就是正確的。為什麼任何一個正確就可以認為實際的 real-time 歷史是正確的?可以分為兩個方面:

  1. 沒有併發。按照 reorder 規則,非併發的由於不會破壞 real-time 的 操作順序,那麼 reorder 之後只會有一個 real-time 的實際排程,這個排程的正確性就是代表了實際 real-time 歷史的正確性。

  2. 有併發。按照 reorder 規則,併發的部分才可以任意 reorder,所以 reorder 的所有歷史都只是不同併發 reorder 之後的組合得到的結果集,併發本身就是不確定的執行序,只要 reorder 得到的歷史有任何一個正確,那麼就可以認為實際執行就是這個順序,也就是這個正確的順序。

下面 wikipedia 給出的例子可以更為直觀的理解這件事,兩個執行緒 A 和 B 去拿同一個鎖,執行的 real-time 實際歷史 H_C 如下:

根據 reorder 規則,可以有如下兩個 reorder 的排程歷史:

這個歷史 H_S1 不符合程式語義,因為 A 先執行就肯定能拿到鎖。

這個歷史 H_S2 是符合程式語義的,B 先搶鎖成功拿到鎖,A 再搶鎖拿鎖自然會失敗。因此基於 H_S2 reorder 正確這樣的事實,得到實際執行滿足線性一致性。

現在根據上面提到的 直觀的解釋 來理解這件事:根據 real-time 實際歷史可以看出,A 和 B 在併發爭鎖,所以誰先誰後是不確定的,因為併發,所以也就能 reorder 出 2 個 結果了,併發本身執行序就不可確定,所以怎麼解釋都是可以的,又因為第 2 個 reorder 的歷史是滿足正確排程的程式語義的,則可以作為併發執行過程的解釋,所以實際歷史滿足線性一致性。

順序一致性 Sequential consistency

順序一致性相對嚴格一致性和線性一致性有了一些放鬆,放鬆了對 real-time 的要求,不要求立刻可見,但是要求:

  1. 單個處理單元內要滿足程式序

  2. 所有處理單元的記憶體操作具有全域性序,即每個處理單元見到的記憶體操作順序是一致的

由於沒有 real-time,所以只能通過程式序後面的邏輯觀察基於全域性序來推匯出被觀察事件的發生,進而得到同步點。

一個 wikipedia 的例子:其中 x 的初始值是 0,P 代表 processor, W 代表 write,R 代表 read。

可以看出這種一致性的開銷雖然沒有 Strict 大,但是也不小。因為強行要求整體的記憶體順序滿足全域性序,這就有 processors 之間協商的開銷,其實大多數情況下沒有因果關係的操作之間是不太需要順序性的。

因果一致性 Causal consistency

因果一致性相對順序一致性又有一些放鬆,不僅沒有 real-time 的要求,不再要求所有操作的全域性序,只要求 具有因果關係操作的全域性序 。同樣的由於沒有 real-time 的保證,所以 只有觀察到了果,才能得到因發生的結論

因果關係:如果一個處理單元執行了一個寫操作 A,自己或者另一個處理單元觀察了 A 之後執行了寫操作 B,則 A 是 B 的因,也就是 Lamport's happened-before A -> B 關係。

因果一致性保證了在處理單元之間具有因果關係的操作間的全域性順序,但是不保證沒有因果關係的操作間的順序。可以通過下面 2 個 例子加深一下理解。

上面這個例子滿足因果一致性,但是不滿足順序一致性。因為 P1 的 W(x)3 和 P2 的 W(x)5 沒有因果關係,所以具體的執行不要求全域性序。

上面這個例子的執行歷史是滿足因果關係的。P2 的 W(x)2 與 P1 的 W(x)1 具有因果關係,而 P1 的 W(x)3 與 P2 的 W(x)2 沒有因果關係,因此對於 W(x)1 和 W(x)2 是要有全域性序的,而 W(x)2 和 W(x)3 不需要有全域性序。可以看出 P2、P3 和 P4 對 x 先 1 後 2 的觀察滿足全域性序,但是對於 x 2 和 3 的順序由於沒有因果關係,所以 P3 和 P4 表現出了不一致的觀察順序。

PRAM(Pipelined RAM consistency, or FIFO consistency)

PRAM 要求所有處理單元觀察到的同一個處理單元的寫入滿足其寫入的順序,但是不同處理單元觀察到的不同處理單元的寫入的順序沒有保證。

Client-centric consistency models

對於強調 AP 的系統來說,為了效能和可用性,經常會放鬆一致性的要求。但是往往也需要一定的 client session 級別的規範化的一致性語義,可以稱之為 “Session Guarantees for Weakly Consistent Replicated Data”。這一部分介紹 4 個 常見的 Session guarantees 下的一致性模型。

Read Your Writes

在一個 session 內,讀取會得到最近寫入的值。比如初始值為 0,如果寫入了 1,之後再讀取,那麼一定會得到 1 而不是 0。但是對於跨 session 則沒有這樣的保證,比如其他 sessions 寫入,本 session 則不一定會讀取到其他 sessions 的寫入。

Monotonic Reads

Monotonic Reads 相比 Read Your Writes 弱,沒有了 session 內 real-time 可見性的保證,只要求在一個 session 內,讀取永遠不會回退。比如寫入序列為 1、2、3、4,一旦讀取到了 2,就永遠不會再讀取到 1,只會讀取到 3 或者 4。

Writes Follow Reads

這個定義本身描述比較複雜,這裡簡單描述就是:對於一個 session,如果一個寫 W2 在讀 R1 之後,並且 R1 是在 server S1 在 t1 時刻發生的,則對於任意其他的 server S2,如果 W2 同步到了 S2,則 S2 需要包含 S1 中對 R1 產生作用的所有寫 Wall,且 WriteOrder(Wall, W2)。

可以看出 Writes Follow Reads 不同於前兩個只規範單個 session 內的一致性,也會要求一個 session 內的順序在所有 servers 上同步,因而也就具備了跨 session 的同步能力,基本上和 PRAM 是很相似的,一個 session 可以看成一個 pipeline。

Monotonic Writes

類似於 Writes Follow Reads,monotonic writes 要求對於一個 session,如果 W1 在 W2 之後,那麼對於任意 servers,如果同步到了 W2,那麼也必然同步了 W1 且 WriteOrder(W1, W2)。

1.2 Transaction

這裡只介紹序列化相關的概念,因為這個概念是理解一切事務隔離級別的基礎,最難理解也最為重要。為了精簡概念突出重點,其他的非可序列化的一致性本文都沒有做說明。

序列 (Serial)

事務一個接著一個的執行,完全沒有並行,也就是說事務之間沒有時間上的交疊,一個事務的所有操作一定是在另一個事務之前。可以看出序列化排程效能不怎麼樣,不論是不是衝突的部分都得序列執行。

可序列化 Serializability

對事務 T1,T2,...,Tn 排程的執行產生了一個歷史,如果這個歷史的影響等價於任何一種 T1 到 Tn 的序列組合的執行結果,稱這個排程是可序列化的。可以看出可序列化排程放鬆了約束,不要求一個接一個執行,只要等價於某一種序列化排程就可以了。這樣的定義本身也比較泛泛,對於具體如何等價沒有明確的說明。下面則對如何等價進行了定義,進而發展出來幾種等價關係概念下的可序列化模型。

可序列化的一節的 2 點 說明:

  1. 由於沒有找到比較好的對這幾個概念的翻譯,這裡的 終態和檢視可序列化 都是個人的翻譯,這一點需要注意。

  2. 由於終態可序列化和檢視可序列化實際上沒有實現的,而且由於 Herbrand semantics 概念也相對複雜,就不過多介紹了,只是簡單說明,否則就背離了本文的目的。

下面對可序列化下的概念進行介紹,其中 Herbrand Semantics of Steps、Herbrand Universe 和 Schedule Semantics 三個概念沒興趣可以不去了解。另外對於後面的每一個可序列化概念,都可以不看定義,直接看圖下的文字解釋。

Herbrand Semantics of Steps

Herbrand Universe

Schedule Semantics

終態可序列化 Final State Serializability

終態可序列化通過終態等價關係來定義,由於其等價關係是不完整的,且驗證複雜度太高,所以實際中沒有使用的。

  • 終態等價

其中 op(s) 表示排程 s 中的所有操作,H[s] 簡單理解是表示排程 s 中所有項的最後一個寫入的集合。

簡單來說,對於兩個排程 s 和 s',如果他們的所有操作相同,並且每一個數據項的最後寫入相同,則 s 和 s' 是終態等價的。

  • 終態可序列化

對於一個歷史 s,如果存在一個序列的歷史 s' 和 s 終態等價,則稱歷史 s 是終態可序列化的。用 FSR 表示所有終態可序列化的排程歷史聚類。

總結

終態可序列化實際沒有應用的,且不說終態等價的驗證複雜度,從定義可以看出對於終態的等價性上並沒有考慮只讀事務的終態,而這會導致讀不一致異常的發生:

檢視可序列化 View Serializability

既然終態可序列化沒有考慮讀會導致等價關係不完整進而會出現異常,那麼想辦法讓整個驗證完整不就行了麼?檢視可序列化就是這樣的背景產生的,檢視可序列化會驗證排程中每一個步驟的等價關係。

  • 檢視等價

其中 Hs(p) 表示 p 的 Herbrand 語義,簡單理解就是 操作的上下文和作用效果。

簡單來說,對於兩個排程 s 和 s',如果滿足終態等價的要求之外,還要滿足 過程中每一個操作的 Herbrand 語義(上下文和作用效果) 相同,則 s 和 s' 是檢視等價的。

  • 檢視可序列化

對於一個歷史 s,如果存在一個序列的歷史 s' 和 s 檢視等價,則稱歷史 s 是檢視可序列化的。用 VSR 表示所有檢視可序列化的排程歷史聚類。

由於 檢視等價 基於 終態等價 的等價關係之外額外附加了調價,所以可以直觀的瞭解到:VSR ⊂ FSR。

總結

由定義可以看出,檢視可序列化要求非常嚴謹,會要求整個事務過程的所有過程必須等價,這導致驗證的開銷會非常大,所以實際中沒法應用。驗證排程是否是檢視可序列化的是一個 NP complete 問題:

衝突可序列化 Conflict Serializability

更進一步,引起排程是非序列化的根本原因是事務的操作之間有 read-write 或者 write-write 衝突,無衝突的部分互相無關,不會對彼此造成影響。因此基於這個出發點,就有了相比檢視等價進一步縮小約束範圍的衝突等價性,即只考慮衝突部分的等價關係。

簡單來說就是在一個排程 s 的兩個事務中,如果它們有操作相同的資料項並且至少有一個是寫操作,則認為這兩個事務中的操作構成衝突關係,s 中所有的衝突表示為 conf(s)。

  • 衝突等價

對於兩個排程 s 和 s',如果他們的所有操作相同,並且有相同的衝突關係,則 s 和 s' 是衝突等價的。

  • 衝突可序列化

對於一個歷史 s,如果存在一個序列的歷史 s' 和 s 衝突等價,則稱歷史 s 是衝突可序列化的。用 CSR 表示所有衝突可序列化的排程歷史聚類。由於只考慮衝突部分,可以直觀的瞭解到:CSR ⊂ VSR ⊂ FSR。

總結

衝突可序列化是主流資料庫系統中實現序列化隔離級別最為常見的模型。一般通過 Two-Phase Locking Protocol 來實現,另外主流資料庫也都是 SS2PL 的方式來實現,這一點可以參考 Wikipedia Two-Phase Locking。

嚴格可序列化 Strict Serializability

通過上述對可序列化的定義可以看出,只要求等價性,並沒有 real-time 的約束,也就是說任意事務可以任意亂序。比如對於 T1, T2 和 T3,T1 和 T2 有併發,T3 時序上在 T1 和 T2 之後,前面提到的可序列化可以排程成最終結果等價於 T3 -> T1 -> T2 這樣一個違背 real-time 的序列歷史。

嚴格可序列化相比前面的可序列化,多了 real-time 的約束,所以對上述例子的排程結果只可能是等價於 T1 -> T2 -> T3 或者 T2 -> T1 -> T3。所以嚴格可序列化也是一個在可序列化概念上新增 real-time 額外約束衍生出來的概念。更多的理解可以參見下面 外部一致性 部分的內容。

讀未提交 Read Uncommitted(Dirty)

一個事務讀到了另一個進行中事務的中間結果。實現比如讀和寫的鎖都僅限於讀寫的時刻,用完之後立刻釋放。一般情況下應該沒有人用這種隔離級別,這基本相當於沒有事務,那也就沒必要使用事務了,這裡只是介紹一下概念。

讀已提交 Read Committed(RC)

一個事務執行過程中可以讀到另一個已提交事務的資料。存在不可重複讀和幻讀異常:事務進行中讀到了不一致的資料。現實比如讀的時候加鎖但完成之後立刻釋放,寫的時候加鎖且直到事務提交才釋放。

可重複讀 Repeatable read(RR)

一個事務執行過程中不會讀到本事務具體行的其他事務提交的資料。存在幻讀異常:事務進行中讀到了不一致的資料。現實比如讀寫都加鎖且持續到事務結束,但並沒有加表鎖,不相關的行還是可以變更。

快照隔離 Snapshot Isolation(SI)

事務是滿足快照隔離的,不存在不可重複讀和幻讀。存在寫偏斜(WriteSkew)異常:讀和寫之間沒有併發控制。

一般化的隔離級別

由於 ANSI 提出的隔離級別比較老舊,不太能表達樂觀鎖和 MVCC 的情況,有人提出了更為精準的隔離級別的分類方法,這方面可以參考論文:《Generalized Isolation Level Definitions》。

1.3 外部一致性 External Consistency

外部一致性是一個相對泛泛的概念,可以分為 2 個方面:

  1. 用在非事務操作上,則等價於 Linearizability。

  2. 用在事務操作上,則類似於 Strict Serializability,比 Serializability 要強,相當於事務級別的 Linearizability,給事務排程加了 real-time 的約束但是並不要求瞬時性(instantaneousness)。簡單來說假如有這樣一個場景:事務 T1 和 T2,使用者先執行了 T1 且提交成功之後再執行 T2。對於 Serializability 來說,先 T1 再 T2 或者先 T2 再 T1 都是滿足語義的;但是對於 Strict Serializability 來說看起來就必須是先 T1 再 T2。

注:對於 Google Spanner 來說,除了上面描述的之外,還蘊含著內部資料物理時間與外部物理時間一致的外部一致性。另外還有隻讀事務以快照的方式讀任意副本都能夠保證讀取到最近快照的外部一致性。

2. C++ memory model

在第 1 章介紹了普遍意義下各個一致性模型的語義,那到了單機系統中,對於系統程式設計來說,面對著多核系統以及不同架構下的不同一致性語義,該如何理解不同記憶體模型下的一致性語義進而寫出符合正確同步語義程式碼呢?本節要基於 C++11 定義的記憶體模型來展開討論這個問題。

首先需要明確的是一個單機系統,其實 也完全就是一個分散式系統 。比如跨 NUMA 的記憶體訪問就需要走匯流排,這就相當於網路;對於 IO 子系統(disk、net)的訪問同樣需要走各種匯流排;CPU 對記憶體的訪問也一樣是分散式的。我們知道,對於 CPU 來說,每一個 core 有自己的 L1 cache,cores 間還有 L2 cache 甚至 L3 cache,那麼這些 cores 之間資料的一致性保證就是非常重要的,這有一個專門的概念叫 Cache Coherence,相應的協議就是 Cache Coherence Protocol,一般都是 MESI 及其擴充套件協議,定義了 cores 間的資料一致性模型,主要就是規範了第 1 章中提到的比如 strict、sequential、causal 等一致性模型在多 cores 之間如何滿足。

為了追求效能,各種 CPU 架構尤其是 ARM 提供的一致性模型都是比較鬆散的,在多 cores 間預設可以理解為是達不到 causal consistency 的,不僅硬體一致性協議會導致一致性的不確定,CPU 的流水線優化、亂序執行以及編譯器的優化都會導致一致性的不確定性,因此我們想做到 causal 甚至 sequential 一致性就需要通過一定的同步語義來做到。在 C++11 之前 C++ 標準並沒有給出相關的標準化規範,linux 側都需要通過 programmer 基於 GCC 或彙編下的原子操作和記憶體屏障來達到目的,好在 C++11 抽象了相應的記憶體模型,從語言層面提供了同步語義。

我們這裡不需要深入瞭解 MESI 協議在不同 CPU 架構下是有怎樣的一致性保證以及如何人為做同步的,有了 C++ 記憶體模型這一層抽象,我們只需要面向 C++ 記憶體模型去實現就好了。所以這裡不會對 MESI 及其衍生協議進行介紹,對於 programmer 來說其實意義不是很大,另外也不是本文的主題。

下面首先介紹 C++ 中用於同步的語義以及相關的概念;之後具體的基於不同原子操作提供的語義介紹如何建立同步語義。其他語言也是如此, 只需要面向具體語言規範來理解和實現即可

2.1 Concepts

上面是 C++ 官網給出的記憶體序列舉定義,由上到下由鬆散逐漸嚴格。可以看出最高的一致性保證是 memory_order_seq_cst,也就是 sequential consistency,所以可以看出 C++ 是不支援 strict 一致性的,也就是說任何寫操作是沒辦法 real-time、瞬時完成立即可見的。基於 C++ 記憶體模型,參考第 1 章順序一致性和因果一致性中提到的概念:

可以看出,在一致性最高級別也不支援 strict,而且出於效能的考慮程式設計師也會盡量用寬鬆的一致性,那 基於一定的結果進而就可以確定性地推斷出一定的原因 的能力就非常重要了,這是典型的因果關係,由於 sequential consistency 能提供比因果更強的保證,所以這裡只基於因果關係進行討論。

因果關係,最初是由 Lamport 在 《Time, Clocks, and the Ordering of Events in a Distributed System》paper 中提出的 happened-before 關係發展而來。Lamport 在 paper 中稱之為 happened-before,但是 C++ 稱之為 happens-before,為了統一描述在 C++ memory model 這個主題中後續均採用 happens-before 這一說法。在 C++ 中,說 A happens-before B,那麼可以明確的就是時序上可以認為 A 先發生 B 後發生,B 可以觀察到 A。因此只要我們在程式中建立了 happens-before 關係,那麼就能得到因 happens-before 而來的同步關係。下面介紹 C++ 記憶體模型中 happens-before 相關的概念。

Sequenced-before

在同一執行緒中,evaluation A 根據語言定義的執行序 sequenced-before evaluation B。比如

具體規則參考 Order of evaluation。

Carries dependency

簡單理解,在同一執行緒中,如果 A sequenced-before B 且 evaluation B 用到了 A,則 A carries dependency into B,即 B depends on A。

Modification order

對於單個變數的原子操作,無論以什麼樣的 memory_order,都是有全域性序的,但是不同變數間的原子操作是沒有這樣的保證的,想要這種保證就需要有一定的同步語義或者完全使用 memory_order_seq_cst。

Modification order 指的就是 單個物件上原子操作的全域性序 。可以看出,C++ 約束了對於 同一個變數原子操作 的 total order,其實就是具備 sequential consistency。

Release sequence

對於一個變數 M,evaluation A 是作用在 M 的一個 release operation,那麼在 A 之後由下面兩種情況:

  • 同一執行緒內以任意 memory_order 執行的原子操作,

  • 不同執行緒內 read-modify-write 類的所有原子操作,比如 fetch_add、cas 等

構成的 modification order(包括 A) 稱之為 以 A 為 head 的 release sequence

比如對於 M,A 是一個 release operation,之後本執行緒內有 relaxed 的任意操作 B,其他執行緒有 read-modify-write 類操作如 fetch_add C、D,那麼 A -> {B、C、D } 是以 A 為 head 的 release sequence。由於 B、C、D 順序不確定,所以這裡放到了一個大括號內。具體為什麼這麼設計,可以參考 <<C++ Concurrency in Action>> 5.3.4 一節。

Dependency-ordered before

線上程間,如果滿足下面任一情況,則 evaluation A dependency-ordered before evaluation B:

  • A 在 M 上執行了一個 release operation,在另一個不同的執行緒,B 對 M 執行了一個 consume operation,並且 B 讀了以 A 為 head 的 release sequence 中的任意一個操作的寫入值。

  • A dependency-ordered before X 並且 X carries a dependency into B。

Synchronizes-with

線上程間,同一變數的一對具備 Release - Acquire 語的義原子操作會建立 同步。比如 evaluation A 是對 M 的 release operation,而之後 evaluation B 是對 M 的 acquire/consume operation,則稱 A synchronizes-with B。根據 memory_order 中介紹的內容,能夠線上程間構成 synchronizes-with 的 operations 如下:

  • Mutex 的 lock() 和 unlock()

  • 具有 Release-Acquire 語義的原子操作

  • 具有 Release-Acquire 語義的 fences

需要注意的是,memory_order_seq_cst 是包含 release & acquire 語義的,更多的細節參考 memory_order 文件即可。

Inter-thread happens-before

線上程間,如果滿足下面任一情況,則 A Inter-thread happens-before B:

  • 1) A synchronizes-with B

  • 2) A is dependency-ordered before B

  • 3) A synchronizes-with some evaluation X, and X is sequenced-before B

  • 4) A is sequenced-before some evaluation X, and X inter-thread happens-before B

  • 5) A inter-thread happens-before some evaluation X, and X inter-thread happens-before B

Happens-before

如果滿足下面任一情況,則 A happens-before B(以後偶爾會用 “->” 簡化):

  • 1) 單執行緒內 A is sequenced-before B

  • 2) 多執行緒間 A inter-thread happens-before B

至此,我們由 sequenced-before 一步步走到了 happens-before 關係。因為 A happens-before B 則 A 對 B 可見,所以只要構建了 happens-before 關係就具備了同步能力。

需要注意的是,從文件可以看出 C++ 的 happens-before 強調的是 visible 性,而沒有 execution order 的約束。比如如下例子:

我們考慮單執行緒執行的情況,對於上面的程式碼,A sequenced-before B,由於單執行緒考慮,因此 A happens-before B,但是實際執行時順序可以是 B 先執行 A 後執行。可以看出,這並沒有破壞 happens-before 對 visible 性的保證,最終結果是等價於 A 先執行 B 後執行,所以 B 先於 A 執行依然滿足 happens-before 語義,但 execution order 不是 program order。

下面 2.2 節會結合具體的 memory_order 型別以及例子進一步強化理解。

2.2 Atomic Operations

memory_order_relaxed

寬鬆操作:沒有同步或順序約束,僅對此操作要求原子性。

memory_order_consume

可以與其他執行緒的 release operation 構成 synchronization。另外不僅如此,還具有一個 副作用(side effects,memory barrier 的作用) :所有本執行緒內依賴於該 memory_order_consume operation 得到的 value 的所有讀或者寫不可以重排到該操作之前。

memory_order_acquire

類似於 memory_order_consume 但是副作用強於 memory_order_consume,要求所有 memory_order_acquire 操作後面的讀或者寫都不可以重排到該操作之前。

memory_order_release

可以與其他執行緒的 acquire/consume operation 構成 synchronization,副作用是所有當前執行緒的讀或者寫不可以重排到該操作後面。具體的 synchronization 行為如下:

  • 與 acquire:當前執行緒的所有寫入對具備 acquire operation 的其他執行緒可見。

  • 與 consume:當前執行緒所有 carry a dependency into memory_order_release 變數的寫入對具備 consume operation 的其他執行緒可見。

memory_order_acq_rel

memory_order_acq_rel 只能作用在 read-modify-write 動作上,語義上是 memory_order_acquire 和 memory_order_release 的結合。

memory_order_seq_cst

不僅具有 memory_order_acquire、memory_order_release 和 memory_order_acq_rel 有的語義,額外保證所有 memory_order_seq_cst 作用的變數具備全域性序。

2.3 Examples

這裡的例子都以原子操作為基礎,但是其實通過 std::atomic_thread_fence 結合 Release-Acquire 語義也一樣可以實現同步。

Sequential

最終 assert 會通過。

直觀的理解:由於 x 和 y 都是 memory_order_seq_cst memory_order,所以具有全域性序。因此當 B 判定失敗導致 z 沒有 ++,那說明對於 read_x_then_y 來說,順序是 x = true -> y = true -> x = true -> y = false,這個順序對於 read_y_then_x 來說,一旦 C 通過,因為 x = true 在 D 之前,所以 D 也會判定通過,進而 z 會 ++,其他情況讀者可以自行分析。另外,語義上的理解可以參考 <<C++ Concurrency in Action>> 的 5.3.3 一節。

Relaxed

上面的程式碼中,由於 x 和 y 都是 relaxed order,所以沒有任何同步,因此 assert 可能失敗。

直觀的理解:relaxed 沒有同步語義,因此 A、B、C、D 可以亂序,沒法判定先後順序。

語義上理解:如下圖,不同執行緒中的 A 沒有和 C 建立 synchronizes-with 關係,所以 也就沒有 A happens-before C 的關係,所以 read_y_then_x 中 d 執行見到的 x 可能還是 false。

Release-Acquire

這個例子中,assert 判定可能會失敗。不同於 memory_order_seq_cst,Release-Acquire 沒有全域性序,因此沒辦法按照 Sequential 例子中的語義做同步了。簡單理解就是 x 和 y 沒啥關係,隨便亂序。

assert 不會失敗。因為 B synchronizes-with C,因此 B -> C。又因為 A -> B,C -> D,所以 A -> B -> C -> D,所以 C 發生之候 x 一定為 true,因此 D 會判定通過。

3. References

  • <<Transactional Information Systems>>

  • https://en.wikipedia.org/wiki/Consistency_model

  • https://en.wikipedia.org/wiki/Linearizability

  • https://en.cppreference.com/w/cpp/atomic/memory_order

  • https://stackoverflow.com/questions/9762101/what-is-linearizability

  • https://timilearning.com/posts/consistency-models/

  • https://cloud.google.com/spanner/docs/true-time-external-consistency

  • https://timilearning.com/posts/mit-6.824/lecture-13-spanner/

  • https://jepsen.io/consistency

  • <<C++ Concurrency in Action>>

  • <<Spanner>>

  • http://www.bailis.org/blog/linearizability-versus-serializability/

  • http://www.cs.cornell.edu/courses/cs734/2000FA/cached%20papers/SessionGuaranteesPDIS_1.html#HEADING1