"Multithreading is just one damn thing after, before, or simultaneous with another. "[2]

0 寫在前面

在分散式存儲系統中，為了提高可靠性，通常會引入多個副本，多個副本需要向用戶表現出一致的內容。這很自然的讓人想到如何確保多副本之間的一致性。為此也有了paxos和raft等保證多副本之間一致性的協議。當我們在一個多處理器機器上編程時我們通常會忽略在多處理器環境下的一致性問題，因為系統已經為我們做好了基本的一致性保證，當存在一致性問題的時候上層編程語言也提供了具備一致性語意的介面，只是我們在編程中並沒有意識到這些介面與一致性的關係。無論是分散式存儲還是多處理器編程都有一個共同點，就是會涉及共享對象的操作。

一旦出現共享，就會出現正確性的問題，那麼如何定義在並發中操作共享對象的正確性，這就是一致性協議的任務了。

本文主要針對多處理器系統中的一致性問題進行了一些總結，對於分散式中的一致性問題會在後面文章中總結。

多處理器中的一致性問題源於並發，源於共享。對於共享內存並發操作下的正確性保證是硬體設計者需要提供給上層開發人員最重要的保證。對於上層開發人員來說，系統內部的一致性是透明的，但是去了解系統內部一致性的設計及原理有利於我們更能夠面向機器編程，寫出正確的代碼。

由於水平有限，文中如存在問題，請幫忙提出。

1 本文主要內容

本文主要包括以下內容：

  • cache coherence
    • cache design
    • cache coherence protocol
    • store buffer & invalidate message queue
    • memory barrier/ fence
  • memory consistency
    • consistency 分類定義
    • SC
    • x86 TSO
    • relaxed memory model
  • C++ memory order
    • memory model and memory order
    • memory order release/acquire
    • memory order sequence
    • memory order relaxed
  • Synchronize
    • insight lock

2 cache coherence[4]

一致性的任務就是保證並發操作共享內存的正確性，在討論內存操作正確性的時候，通常分為兩個部分：memory consistency 和 cache coherence[3]。

本節著重討論cache coherence的實現。

2.1 cache vs buffer

在底層系統設計中通常會有cache 及 buffer的設計，兩者都有緩存的意思，那麼真正的區別在哪裡呢，知乎上有個回答我感覺挺好的。Cache 和 Buffer 都是緩存，主要區別是什麼？

Buffer（緩衝區）是系統兩端處理速度平衡（從長時間尺度上看）時使用的。它的引入是為了減小短期內突發I/O的影響，起到流量整形的作用。比如生產者——消費者問題，他們產生和消耗資源的速度大體接近，加一個buffer可以抵消掉資源剛產生/消耗時的突然變化。

Cache（緩存）則是系統兩端處理速度不匹配時的一種折衷策略。因為CPU和memory之間的速度差異越來越大，所以人們充分利用數據的局部性（locality）特徵，通過使用存儲系統分級（memory hierarchy）的策略來減小這種差異帶來的影響。

2.2 cache設計

從cache vs buffer的區別中我們可看出，cache的出現其實就是為了緩解CPU與主存之間的速度極度不平衡。因此通常CPU設計中引入了cache，分為L1 cache，L2 cache和L3 cache，其性能指數大致如下[11]：

通常L1 cache又會分為I cache和D cache，分別存放指令與數據，L1 cache通常是core獨佔的，L2可以是兩個core共享，L3 cache則是所有core共享。

2.2.0 CPU cache架構

如下圖[4]， 目前的CPU架構中的cache通常架構如此，這裡的cache是L1 cache。我們這裡討論的cache基本都是基於L1 cache的，因為L1 cache通常是core獨佔的，所以L1 cache的設計及數據一致性是難點也是重點。

cache中的數據存放單位是cache line，通常一個cache line長度大概在16-256Bytes之間。CPU訪問memory的時候首先會先查看cache中是否已經緩存該address，如果已緩存當前address並且是可用的，那麼CPU就會直接從cache讀取該值，這樣極大的提高performance。如果所要訪問的address不在cache中，CPU則要從memory讀取，CPU會讀取cache line大小的數據，並將其放入cache中這樣下次讀取的時候可以直接從cache中讀。L1 cache通常在32KB大小，當cache被填滿之後就需要按照一定策略將元素踢出去，這個策略可以是LRU或者隨機等等。

這裡有兩個小點需要注意：

  • L1 cache獨佔導致的數據不一致因為每個core都有自己獨立的L1 cache，對於一個共享的memory location兩個cache可以有自己的copy。那麼這就會出現了數據不一致的狀況，兩個core可能同時訪問這個memory location，且如果一個core是對這個memory location進行修改，那麼這就需要兩邊的cache進行同步，防止數據不一致。這個工作就是cache coherence protocol要做的事情。
  • cacheline導致的false sharing

struct test {
uint32_t a;
uint32_t b;
}
test t;

t是一個共享變數，core1上線程t1訪問t.a， core2線程t2訪問t.b,如果cacheline大小是16Bytes，那麼當t1訪問t.a時cache miss，然後會將這個t.a讀取到cache中，但是為了提高效率，core每次讀取的長度是cacheline的長度，t.a長度是4， t.b長度是4，所以在一次讀取中會將t.a和t.b一次性讀到了自己cache中了，那麼t2也同樣存在這個問題，如果t1修改當前cacheline中的值，他需要與core2對應的cacheline同步，那麼本來兩個可以並發的memory location引入了不必要的同步。對性能產生不必要的影響。

那麼為了避免false sharing，就需要讓這兩個memory location進行cacheline對齊。C++ 提供了alignas的方法。

2.3 cache coherence protocol

前面小節提到了為什麼需要coherence protocol，那麼coherence protocol是如何保證cache之間的數據一致性的呢？

這裡就需要引入MESI協議了，MESI是一種維護cacheline狀態一致性的協議。MESI: 由Modified,Exclusive,Share,Invalid四種狀態組合。

2.3.1 cacheline state

  • Modified(M):當一個core 的cacheline的狀態是M時，說明當前core最近修改了這個cache，那麼其他core的cache不能再修改當前cache line對應的memory location，除非該cache將這個修改同步到了memory。這個core對這個memory location可以理解為Owned。
  • Exclusive(E):

    E這個狀態與M很像，區別在於當前core並沒有修改當前的cacheline，這意味著當前cacheline存儲的memory location的值是最新的。當前core可以對該cacheline進行modify且不需要與其他core的cache同步。這個core對這個memory location可以理解為Owned。

  • Share(S):S表示當前cacheline在其他core的cache也存在copy，當前core如果需要修改該cacheline則需要與其他core的cache進行提前溝通。
  • Invalid(I):I表示當前cacheline是空的。

cacheline的狀態變化需要在各個core之間同步，那麼如何進行同步呢，MESI使用protocol message。

2.3.2 protocol message

作為core之間的溝通工具，protocol message分為以下幾種消息類型：

  • Read當一個cache需要讀取某個cacheline消息的時候就會發起read消息。
  • Read Responseread response是read的回應，這response可以來自其他core的cache也可以來自memory。當其他core中對當前cacheline是M狀態時，則會發起read response。
  • InvalidateInvalidate消息包含對應的memory location，接收到這個消息的cache需要將自己cacheline內容剔除，並響應。
  • Invalidate acknowledge接收到Invalidate後刪除cacheline中的數據就向發起者回復invalidate ack。
  • Read Invalidate這個消息包含兩個操作，read和invalidate，那麼它也需要接收read response和多個invalidate ack響應。
  • write back

    writeback包含數據和地址，會將這個地址對應的數據刷到內存中。

2.4 store buffer and invalidate queue

MESI中的四種狀態可以互相轉化，具體狀態遷移條件請參考[4]，這裡不再贅述。

2.4.1 store buffer

CPU設計者都是在極致壓榨其性能。cache就是CPU設計者壓榨CPU性能的一種體現，但是這樣他們覺得還不夠。考慮一種狀況，假設當core1執行一次store操作，且這個store操作的memory location對應的cacheline在另外一個core2上是owned狀態，那麼core1需要向core2發送Invalidate message，並且需要等到core2返回invalidate ack之後才能繼續向下執行，那麼在這個期間core1就處於盲等階段，那麼core1必須要等這麼久嗎？於是CPU設計者引入了store buffer，這個buffer處於CPU與cache之間。如下圖[4].

有了store buffer之後core1如果執行store操作就不用立刻向core2發送invalidate message了，core1隻需要將store值添加到store buffer中即可。但是引入store buffer會帶來兩個問題。

  • 考慮以下場景：

// a, b init to 0.
a=1;
b = a + 1;
assert(b == 2);

上述代碼中，core執行a=1後，a=1這個值被放到core的storebuffer裏了，然後繼續執行b=a+1,這時候core的cacheline中保存的a還是原來的0.這個時候就會導致assert失敗。因為我們在storebuffer裏和擦車line中的a是兩個獨立的拷貝，所以導致這種錯誤的結果，因此CPU設計者通過使用"store Forwarding"的方式解決這個問題，就是在執行load操作時先去storebuffer中查找對應的memory location，如果查到就使用storebuffer中的最新值。

  • 考慮另外一個場景

void foo(void) {
a=1;
b=1;
}
?
void bar(void) {
while (b == 0) continue;
assert(a == 1);
}

foo和bar兩個函數如果在兩個不同的core上執行，假設core1執行foo，core2執行bar，a不在core1的cache中，b在core1的cache中，且b對應的cacheline狀態是M。

那麼core1執行a=1的時候會將a=1放到storebuffer中，然後再執行b=1，因為b在core1上是M狀態，所以修改b不需要與其他core進行同步，b的修改直接就在cacheline中進行了，所以也不會進storebuffer。這時候core2執行while(b==0)判斷的時候發現b=1了，那麼就會進入到assert，但這個時候如果a=1的storebuffer還沒有更新core1中的a的cacheline的話，core2獲得的a的值為0，那麼這個時候結果也是不符合預期的。

但是在CPU設計層面是無法判斷當前core中執行的變數是否與其他的core中的變數存在關係，因為CPU在執行代碼的時候他認為這個當前所執行程序就是一個單線程的，他無法感知多線程的存在。因此這個問題無法在CPU設計層面解決，這個就需要編碼人員介入了，編碼人員需要告訴CPU現在需要將storebuffer flush到cache裏，於是CPU設計者提供了叫memory barrier的工具。

void foo(void) {
a=1;
smp_mb(); // memory barrier
b=1;
}
?
void bar(void) {
while (b == 0) continue;
assert(a == 1);
}

smp_mb()會在執行的時候將storebuffer中的數據全部刷進cache。這樣assert就會執行成功了。

2.4.2 invalidate message queue

storebuffer幫助core在進行stor操作的時候儘快返回，這裡的buffer和cache都是硬體元素，所以這些buffer一般都比較小（或許就只有幾十個位元組這麼大），當storebuffer滿了之後就需要將buffer中的內容刷到cache，刷到cache就會觸發cacheline的invalidate message，這些message會一起發送給其他的core，然後等到其他的core返回invalidate ack之後才能繼續向下執行。那麼這個時候問題又來了，這些message發到另外的core，這些core需要先invlidate，然後在返回ack，如果這些core本來就很忙的話就會導致message處理被延後，這對於CPU設計者來說同樣是不可接受的。因此CPU設計者又引入了invalidate queue。如下圖[4].

同樣，類似於storebuffer，有了invalidate queue之後，發送的invalidate message只需要push到對應core的invalidate queue即可，然後這個core就會返回對應的invalidate ack了，中間不需要等待。這樣cache之間的溝通就不會有很大的阻塞了，但是這同樣帶來了問題。

  • 考慮以下場景這個例子與store buffer中的例子一樣。

void foo(void) {
a=1;
smp_mb(); // memory barrier
b=1;
}
?
void bar(void) {
while (b == 0) continue;
assert(a == 1);
}

core1執行foo，core2執行bar，同樣當core1執行到smp_mb()會將storebuffer中的數據全部刷到cache，然後cache會向core2發送invalidate message，這個message會push到core2的invalidate queue, 然後執行b=1之後，core2的bar判斷b==0失敗然後執行assert，但是這時候如果core2中a的cacheline不為I，且invalidate queue還沒有刷到core2的cache，這時候assert還會失敗。這也是不符合程序語意的。但是同樣core2並不知道當前執行的a與其他core中的變數有什麼關係，CPU設計層面依然不能直接解決這個問題。於是還是需要加上memory_barrier.

void foo(void) {
a=1;
smp_mb(); // memory barrier
b=1;
}
?
void bar(void) {
while (b == 0) continue;
smp_mb(); // memory_barrier
assert(a == 1);
}

同樣，在core2中添加smp_mb()，這個memory_barrier會將所在core的storebuffer和invalidate queue都 flush。

2.5 memory barrier

上面兩小節中可已看出memory barrier的作用，上面提到的smp_mb()是一種full memory barrier，他會將store buffer和invalidate queue都flush一遍。但是就像上面例子中體現的那樣有時候我們不用兩個都flush，於是硬體設計者引入了read memory barrier和write memory barrier。

read memory barrier會將invalidate queue flush。

write memory barrier會將storebuffer flush。

2.6 總結

從上幾節討論可以看出，cache coherence主要集中在對一個memory location的一致性保證，MESI協議是對同一個memory location在不同cache之間的一致性保證。

3 memory consistency[3]

memory model, memory model consistency, memory consistency三個指的是同一個東西。

memory consistency是什麼[8]：

1. The guarantees provided by the runtime environment to a multithreaded program, regarding the order of memory operations.2. Each level of the environment might have a different memory model – CPU, virtual machine, language.3. The correctness of parallel algorithms depends on the memory model.

這節我們討論的是CPU memory model。

3.1 consistency分類

一致性從強到弱有多種分類，分散式系統中常用lineraziblity consistency（線性一致性），這是一種強一致性模型，在對分散式事務的一致性保證中又有Serializability consistency這也是一種強一致性模型，在底層系統設計時又有sequence consistency（SC）一致性模型，sequence consistency也是一種強一致性模型，不過比線性一致性稍弱。當然還有若一致性模型，比如內存一致性中的relaxed memory consistency model。

在底層系統設計時，一致性設計主要是在SC和XC的一種設計，為什麼在底層系統設計時不是對lineraziblity consistency的實現而是對相比較較弱的SC或者XC的實現？這個在本節末尾會談一下個人的觀點。

本文主要是對memory consistency的一致性模型的總結，所以對lineraziblity和Serializability consistency不會涉及很多。

3.2 Sequence Consistency

3.2.0 reorder

在談memory consistency之前我們先了解下reorder，我們編碼並發布運行需要經過編譯器編譯後然後在CPU上運行，通常我們認為我們所寫的代碼是按照順序執行下去的，就是說上一個語句一定在下一個語句執行之前執行。這是我們的潛意識，然而事實可能並不是這樣，因為中間經過了編譯器也經過了CPU。編譯器和CPU為了充分提高程序運行性能會在內部進行一系列優化，這些優化方法有很多，也很複雜。比較典型的有reorder，Speculative execution等。編譯器會對我們寫的代碼順序進行reorder，CPU執行的時候也會進行reorder，也就是說在執行時，我們寫的代碼並不是一定按照我們所看到順序。但是不用擔心，CPU或者編譯器在reorder的時候並不會無釐頭的reorder，他們至少要保證的是，在reorder之後，程序所表現出來的行為效果與單線程執行效果是一致的。這裡提到的是單線程，也就是說CPU和編譯器並不能感知道你的代碼是多線程還是單線程，他只能保證單線程狀況時正確的，多線程就不得而知了。

所以 C++ and the Perils of Double-Checked Locking.這篇論文的作者有這麼一句話："Multithreading is just one damn thing after, before, or simultaneous with another. "。 其實蠻有道理的。

那麼既然CPU和compiler不能感知多線程，那會出現什麼問題呢？如下。

3.2.1 memory consistency motivation

在memory 系統設計時為什麼需要memory consistency這樣的約束？考慮下面表格鎖描述的一種場景。

core C1與 core C2是兩個單獨的core，各自執行自己的程序，就像表格標題r2會一直被置為NEW嗎？答案當然不是，首先CPU是存在out-of-order[6]優化的，另外對於core來說，他並不知道自己當前執行的是一個多線程程序。一個CPU core在設計時至少需要保證當前core上執行的程序是遵循其program order的(program order就是代碼順序)。但是為了提高性能,CPU優化引入了out-of-order-excution機制和Speculative execution機制，那麼對於C1而言，CPU可以執行S2->S1,也可以執行S1->S2, 對於這兩種執行方式在C1看來是沒有問題的，因為單線程而言這兩種執行方式最後達到的效果是一樣的。（因為S2和S1是對不同的memory location的操作，所以會reorder，如果是對同一個memory location操作是不允許出現這種reorder的，當然TSO允許這種reorder，但是對同一location而言reorder前後效果一致，具體會在後面章節詳細描述。）

那麼如果C1的執行順序是S2->L1->L2->S1，那麼得到的結果r2 = 0，而不是向我們預期的r2 = NEW。對我們而言這種結果是超出預期的，是錯的。

那麼為了保證不會出現這種超出預期的行為，我們就需要一種規則來約束這種行為不能出現。這個任務就是memory consistency需要保證的（這裡指的是強一致性模型：SC/TSO， XC的memory consistency並不能保證這點）。

3.2.2 program order vs memory order

在引入SC定義之前，我們先明確什麼是program order什麼是memory order。這裡我們談的都是針對共享內存的操作，對那些局部變數，對core來說是私有的，不存在共享，所以不會存在consistency的問題。

program order: 就是我們寫的代碼的順序，這個是靜態的也是每個CPU core各自擁有的。

memory order: 就是代碼執行的順序，這個是全局的，每個CPU core對共享內存的執行都會出現在memory order中。

如下圖所示，每個core的代碼都會對應到memory order這條執行線上。

3.2.3 SC definition

Lamport引入了對SC的定義，他這樣定義multiprocessor下的SC: "the result of any execution is the same as if the operations of all processors (cores) were executed in some sequential order, and the operations of each individual processor (core) appear in this sequence in the order specified by its program."[3]

如上圖中，S1 與 S2的program order可以表示為： S1 <p S2, S1與L2可以表示為 S1 <m L2.

用<p 表示program order的先於順序，<m表示memory order的先於順序。

那麼SC的形式化定義如下[3]：

(1) All cores insert their loads and stores into the order <m respecting their program order, regardless of whether they are to the same or different addresses (i.e., a=b or a=?b). There are four cases:

If L(a) <p L(b) ? L(a) <m L(b) /* Load→Load */

If L(a) <p S(b) ? L(a) <m S(b) /* Load→Store */

If S(a) <p S(b) ? S(a) <m S(b) / Store→Store */

If S(a) <p L(b) ? S(a) <m L(b) / Store→Load */

(所有對共享內存的操作都可以抽象成load(讀取)和store(寫入)，每一core執行load和store是按照其program order，那麼就有S1 <p S2肯定會推出 S1 <m S2，SC的定義也由此引入了load和store的四種關係。在SC的定義中這四種關係是不允許被reorder的，即使是對不同memory location的操作。)

(2) Every load gets its value from the last store before it (in global memory order) to the same address:

Value of L(a) = Value of MAX <m {S(a) | S(a) <m L(a)}, where MAX <m denotes 「latest in memory order.」

（SC中定義每個共享內存的讀取肯定是其在memory order中最近的一次寫入的值）。

只要符合上述兩個條件，那麼我們就可以說這個memory操作是符合順序一致性的。

下表給出了SC的定義中約束的行為。operation1 <p operation2。

3.2.4 SC example

還是用3.2.1節中的例子，來驗證一下SC對memory操作的約束。

  • 程序memory operation如下

  • 程序可能出現的SC執行結果下圖中前三種結果是符合SC定義的，最後一種是不符合SC定義的，另外一方面可以看出SC中是不允許執行線（虛線）交叉的。每個執行語句落在memory order這條線上的位置表示當前的執行已經發生了。（在lineraziblity consistency定義中每個操作會劃分為invocation和response兩個階段，且操作會在這兩個階段中間任一個瞬間發生，這裡語句在memory order這條線上的落點就是該操作執行的瞬間。）

從圖中可以看出在保證program order不變的情況下，memory order的順序可以隨意排列。這個特別像我們平常洗牌的過程，兩副撲克牌互相交疊，但是每副牌的順序（program order）是不變的，但是在洗完之後兩副牌合成一副牌的時候這個順序是隨機的，不確定。在符合SC定義下的執行中會出現多種正確的結果，這些結果符合SC定義，在編碼人員開來，這樣一個多線程程序執行的結果也是正確的。並發在不強加干涉的情況下是不能預測執行順序的。

3.3 TSO

3.3.0 SC帶來的問題

SC嚴格定義了對於共享內存的load和store操作，loadload，storestore，loadstore，storeload四種執行順序是不允許reorder的。當下CPU的執行速度已經甩DRAM（memory）好幾個量級，如果每次store，load操作都從DRAM讀取會拖慢CPU的執行速度，在這個極度壓榨硬體性能的時代，是不能接受這種行為的。因此在x86的架構實現中引入了TSO。

However, current commercial compilers and most current commercial hardware do not preserve sequential consistency.[9]

3.3.1 TSO如何解決SC的問題

TSO全稱Total Store Order，我們在討論TSO的時候先忽略cache這一層。

TSO在CPU與memory之間引入了write buffer。CPU寫入的時候先寫入write buffer然後就返回了，這樣就將cpu與memory之間的差距隱藏了，但是這樣同樣帶來了一個問題。

還是上面這個例子，S1將x=NEW放到了core C1的write buffer中，S2將y=NEW放到了C2的write buffer中，那麼在執行L1,L2的時候，r1與r2這時候從memory讀到是0。這個是違背了SC的，但是這樣的設計確實帶來了性能的提升。

那麼在TSO模型下的執行結果如下：

前三種與SC一致，第四個執行結果則是TSO獨有的，可以看出，TSO中允許執行線交叉。

3.3.2 TSO definition

TSO在實現SC的過程中做了一些改動，帶來了性能提升。SC是TSO的一些特例，x86通過在每個core上引入FIFO 的write buffer實現了TSO[3]。

TSO與SC的定義很像，其定義如下：

（1） All cores insert their loads and stores into the memory order <m respecting their program order, regardless of whether they are to the same or different addresses (i.e., a==b or a!=b). There are four cases:

If L(a) <p L(b) ? L(a) <m L(b) /* Load→Load */

If L(a) <p S(b) ? L(a) <m S(b) /* Load→Store */

If S(a) <p S(b) ? S(a) <m S(b) /* Store→Store */

// If S(a) <p L(b) ==> S(a) <m L(b) /*Store->Load*/ //這個是SC的，TSO沒有

（2）Every load gets its value from the last store before it to the same address:

// Value of L(a) = Value of MAX <m {S(a) | S(a) <m L(a)} // 這個是SC的， TSO沒有

Value of L(a) = Value of MAX <m {S(a) | S(a) <m L(a) or S(a) <p L(a)}

TSO的定義與SC的定義有兩個變化：

  • 變化一：不保證storeload順序舉個例子：Core C1中S1和L1， S1先去L1執行，但是S1隻是將值送入了write buffer就返回了，緊接著執行L1，L1在memory order中的點執行完之後，S1的write buffer這時候flush到內存，那麼S1在memory order這條線上真正執行的點在L1之後了，那麼這時候S1與L1就出現了reorder了。
  • 變化二：load的最新值不一定是memory order中最近的，有可能是program order最近的store需要注意的是，無論是TSO還是SC都需要至少保證一點，即使允許reorder也要保證program執行的結果與單線程執行的結果是一致的。比如一對操作：S1: x = newL1: y = x.無論是TSO還是SC都需要保證y讀到的是x=new的值（排除其他線程在這兩個語句之前對x進行store操作。）因為TSO引入了write buffer，那麼上述x=new會寫入buffer，如何確保L1會讀到最新的值呢，TSO引入了一種叫「bypass」的概念，就是對於同一memory location的讀寫會保障load會讀到store的最新值無論這個store會不會進入write buffer。如下圖所示：L1讀取的是S1的值，即使L1 <m S1 且 S1 <p L1.

3.3.3 FENCE

3.3.1小節提到的例子中，出現了一種超出預期的執行狀況，如果我們想避免這種問題，那麼需要在上層代碼中添加FENCE，這個fence可以理解為memory barrier，他的作用是將write buffer中的記錄flush到內存。

FENCE會強制保證program order。

  • If S(a) <p FENCE ? S(a) <m FENCE /* Store → FENCE */
  • If FENCE <p L(a) ? FENCE <m L(a) /* FENCE → Load */

如果再S1與L1之間加上FENCE，就保證了S1 <p L1 和 S1 <m L1.

x86系統中並沒有為我們加上FENCE，什麼時候需要添加FENCE只有開發人員知道，所以為了避免程序出現莫名其妙的錯誤，記得在store和load共享內存的時候加上FENCE。

因此TSO下的operation order如下: (operation1 <p operation2)

3.4 relaxed memory consistency

SC和TSO嚴格意義上來說都是一種強一致性模型，因為他們都對程序的執行順序做了一定的約束，既然存在約束那麼就會帶來一定的性能損耗。

那麼有沒有一種沒這麼多的約束的一致性模型，能夠使機器進行深度的優化並發揮極致性能。那麼執行順序的正確性就只能有編碼人員來保證了。

relaxed memory consistency實現對於load與store順序完全放開，除了對同一memory location的操作保證load看到是最新的store以外其他都不進行約束，編碼人員如果想強加order可以通過上述的FENCE。

3.5 Linearizability consistency

Linearizability是比SC更強的一致性模型，在SC定義中不同core的執行語句在memory order的時間線中可以隨意插入，而對於Linearizability consistency不僅限制了單線程中的執行順序，同時對於多線程中執行順序也做了一些限制。具體 Linearizability consistency的相關知識在後面文章再詳細總結一下。

3.6 memory consistency總結

  • 為什麼memory consistency只談sequence consistency(SC)而不談linearizability(LIN)
    • 一方面，因為SC在底層已經定義一個多線程能夠對共享內存並發操作的正確性，LIN比SC更嚴格，LIN是SC的一種形式，LIN更貼近與上層，在SC提供的多種正確性的執行序列中，我們需要一個符合我們業務邏輯正確性的保障手段，而LIN就是這種手段。
    • 另一方面是，在底層系統中CPU和編譯器是不能意識到多線程的存在的，也就是說CPU只是 知道當前的指令，並不知道當前指令與其他CPU指令之間的關係，LIN中約束了兩個process（也就是兩個執行體，可以理解為線程也可以理解為進程等）之間的partial order（偏序關係），而這種關係在底層是不得而知的。

SC在定義中沒有約定執行時間這個概念，只是強調了program order與execution order，也就是memory order。

Linearizability在定義中約定了兩個執行體之間的執行順序，也就是執行時間先後被約定了。
  • memory consistency與cache coherence的關係從以上討論可以看出，memory consistency注重的是全局的memory order，而cache coherence則是關注於一個memory location。memory consistency是保證多處理器編程中的正確性，我們在討論這個的時候可以把cache當做一個黑盒子來處理，也就是說即使沒有cache，我們也同樣需要memory consistency來保證正確性。
  • memory barrier與memory order的關係第2節中最後提到了memory barrier，這個memory barrier會flush storebuffer和invalidate queue。那麼memory barrier與memory order有啥關係呢。memory order是全局的多處理器對共享變數的操作的一個排序。對共享變數操作落在memory order這條線上的點就是對外表現出的執行順序。memory barrier會將storebuffer中的內容flush到cache然後cache，那麼只有執行這個memory barrier之後，這個操作纔算真正的執行，才能真正落在memory order這條線上。所以memory barrier起到一個order的作用，這個order是一個動詞，就是什麼時候真正執行這個動作。

4 ==篇幅限制，後續部分放在後一篇==

7 References

  1. M. Mizuno, M. Raynal, J.Z. Zhou. Sequential Consistency in Distributed Systems.
  2. Scott Meyers and Andrei Alexandrescu. C++ and the Perils of Double-Checked Locking.
  3. Daniel J. Sorin, Mark D. Hill, and David A. Wood. A Primer on Memory Consistency and Cache Coherence.
  4. Paul E. McKenney .Memory Barriers: a Hardware View for Software Hackers.
  5. C++ memory order
  6. out of order execution
  7. The New C++: Lay down your guns, knives, and clubs
  8. c++ memory model
  9. H. Boehm, S. V. Adve.Foundations of the C++ Concurrency Memory Model
  10. C++ Standard - 2012-01-16 - Working Draft (N3337).pdf
  11. CPU Cache and Memory Ordering
  12. think cell talk memory model
  13. Acquire and Release Semantics
  14. C++ Memory model

推薦閱讀：

查看原文 >>
相關文章