最近，在學習 Disruptor 的時候，再次接觸到這個聽了很多次，但是一直不熟悉的名詞————記憶體屏障。因為知道了記憶體屏障的實際應用場景，所有這次決定好好了解一下它。
要了解記憶體屏障，首先要了解 計算機CPU以及緩存。
一、計算機CPU以及多級緩存
現代CPU現在比現代的記憶體系統快得多。為了彌合這一鴻溝，CPU使用複雜的緩存系統，這些系統可以有效地快速生成硬體哈希表，而無需連結。
下面是一張從美團的技術部落格————《高性能隊列——Disruptor》 講解僞共享 時的配圖：
- L1、L2、L3分别表示一級緩存、二級緩存、三級緩存，越靠近CPU的緩存，速度越快，容量也越小。
- L1 緩存很小但很快，并且緊靠着在使用它的CPU核心；
- L2 大一些，也慢一些，并且仍然隻能被一個單獨的CPU核使用；
- L3 更大、更慢，并且被單個插槽上的所有CPU核共享；
- 最後是主存（記憶體），被全部插槽上的所有CPU核共享。
另外，線程之間共享一份資料的時候，需要一個線程把資料寫回主存，而另一個線程通路主存中相應的資料。
二、Memory Barrier
接着就是 《Disruptor Paper》 中 Memory Barriers 一節中的論述：
這些緩存通過消息傳遞協定與其他處理器緩存系統保持一緻。
此外，處理器具有“存儲緩沖區”來解除安裝對這些緩存的寫入，以及“使隊列失效”，以便緩存一緻性協定能夠在即将發生寫入時快速确認失效消息，進而提高效率。
讀記憶體屏障通過在無效隊列中标記一個點來訓示 CPU 上的加載指令來執行它，以便更改進入其緩存。 這使它對在讀取屏障之前排序的寫入操作具有一緻的視圖。
寫屏障通過在存儲緩沖區中标記一個點來指令 CPU 上的存儲指令執行它，進而通過其緩存重新整理寫出。 這個屏障提供了一個有序的視圖，了解在寫入屏障之前發生了什麼存儲操作。
在Java記憶體模型中，volatile字段的讀寫分别實作讀寫屏障。
讀到這邊，我起初還是不明白其中含義，當時隻是Get 了幾個關鍵字————緩存一緻性協定，存儲緩沖區，失效隊列，讀記憶體屏障，寫記憶體屏障。
幸運的是，我不是第一個踩坑的，早有前人栽樹了——
- 《什麼是記憶體屏障？ Why Memory Barriers ?》
- 《CPU緩存一緻性協定MESI》
三、緩存一緻性協定————MESI
MESI 協定是 Cache line 四種狀态的首字母的縮寫，分别是修改（Modified）态、獨占（Exclusive）态、共享（Shared）态和失效（Invalid）态。 Cache 中緩存的每個 Cache Line 都必須是這四種狀态中的一種。
3.1 Cache 的狀态：
| Cache塊狀态 | 詳細解釋 | 簡要說明 |
|---|---|---|
| 修改态（Modified） | 如果該 Cache Line 在多個 Cache 中都有備份，那麼隻有一個備份能處于這種狀态，并且“dirty”标志位被置上。擁有修改态 Cache Line 的 Cache 需要在某個合适的時候把該 Cache Line 寫回到記憶體中。但是在寫回之前，任何處理器對該 Cache Line在記憶體中相對應的記憶體塊都不能進行讀操作。 Cache Line 被寫回到記憶體中之後，其狀态就由修改态變為共享态。 | 目前CPU cache擁有最新資料（最新的cache line），其他CPU擁有失效資料（cache line的狀态是invalid），雖然目前CPU中的資料和主存是不一緻的，但是以目前CPU的資料為準； |
| 獨占态（Exclusive） | 和修改狀态一樣，如果該 Cache Line 在多個 Cache 中都有備份，那麼隻有一個備份能處于這種狀态，但是“dirty”标志位沒有置上，因為它是和主記憶體内容保持一緻的一份拷貝。如果産生一個讀請求，它就可以在任何時候變成共享态。相應地，如果産生了一個寫請求，它就可以在任何時候變成修改态。 | 隻有目前CPU中有資料，其他CPU中沒有改資料，目前CPU的資料和主存中的資料是一緻的； |
| 共享态（Shared） | 意味着該 Cache Line 可能在多個 Cache 中都有備份，并且是相同的狀态，它是和記憶體内容保持一緻的一份拷貝，而且可以在任何時候都變成其他三種狀态。 | 目前CPU和其他CPU中都有共同資料，并且和主存中的資料一緻； |
| 失效态（Invalid） | 該 Cache Line 要麼已經不在 Cache 中，要麼它的内容已經過時。一旦某個Cache Line 被标記為失效，那它就被當作從來沒被加載到 Cache 中； | 目前CPU中的資料失效，資料應該從主存中擷取，其他CPU中可能有資料也可能無資料，目前CPU中的資料和主存被認為是不一緻的； |
上表中的詳細解釋摘自《什麼是記憶體屏障？ Why Memory Barriers ?》，簡要說明摘自《CPU多級緩存與緩存一緻性，詳細的講解》
3.2 Cache 的操作：
MESI協定中，每個cache的控制器不僅知道自己的操作（local read和local write），每個核心的緩存控制器通過監聽也知道其他CPU中cache的操作（remote read和remote write），進而再确定自己cache中共享資料的狀态是否需要調整。
| 操作類型 | 操作說明 |
|---|---|
| local read | 讀本地cache中的資料 |
| local write | 将資料寫到本地cache |
| remote read | 其他核心發生read |
| remote write | 其他核心發生write |
在維基百科 MSI protocol，國内可能打不開維基百科連結，可以看看 TheFreeDictionary MSI protocol，對于操作的定義很詳盡：
Cache塊的狀态從一種狀态過渡到另一種狀态，通常有兩大類刺激因素：
- 第一個刺激因素是處理器的特定讀寫請求。例如：處理器P1在其緩存中有一個塊X，并且有來自處理器的從該塊讀取或寫入的請求。
- 第二個刺激因素來自另一個處理器。例如：處理器P2的緩存中沒有緩存塊或緩存塊中不是最新資料，目前處理器P1通過連接配接所有處理器的總線收到來自處理器P2的“刺激”。
總線請求在偵測器（Snoopers）的幫助下被監視，偵測器監視所有總線事務。
以下是不同類型的處理器請求和總線側請求：
- 處理器對緩存的請求包括以下操作：
- 處理器讀緩存塊請求（PrRd: The processor requests to read a Cache block.）
- 處理器寫緩存塊請求（PrWr: The processor requests to write a Cache block.）
- 總線側請求包括以下操作：
- 總線讀請求（BusRd）: 表明正有其他處理器請求讀取緩存塊。
- 總線寫請求（BusRdX）：表明正有其他處理器請求寫入一個它的緩存中不存在的緩存塊。
- 總線更新請求（BusUpgr）：表明有其他處理器請求寫入一個已經儲存在緩存中的緩存塊。
- 總線“回寫”請求（Flush）：表明其他處理器正在回寫一整塊緩存塊到主存中。
- 總線“緩存到緩存的傳輸”請求（FlushOpt）：整個緩存塊釋出在總線上，以便将其提供給另一個處理器。
如果将資料塊從主存轉移到緩存的延遲大于從緩存轉移到緩存的延遲（在基于總線的系統中通常是這樣），則這種緩存到緩存的轉移可以減少讀未命中延遲。但在多核架構中，一緻性保持在二級緩存級别，片上三級緩存可能更快從三級緩存而不是從另一個二級緩存擷取丢失的塊。
偵測（Snooping）操作：在偵測系統中，總線上的所有緩存監視（或偵測）所有總線事務。每個緩存都有其存儲的每個實體記憶體塊的共享狀态副本。根據所用協定的狀态圖更改塊的狀态。總線的兩側都有偵測者：
- 處理器/緩存端的偵測器。
- 記憶體側的監聽功能由記憶體控制器完成。
每個緩存塊都有自己的4種狀态Finite State Machine（MESI）。表1.1和表1.2顯示了與不同輸入有關的狀态轉換和特定狀态下的響應：
Table 1.1 狀态轉換和對各種處理器操作的響應
| 初始狀态 | 處理器操作 | 響應 |
|---|---|---|
| Invalid(I) | PrRd | 1. 向總線發出BusRd信号； 2. 其他緩存看到BusRd，檢查是否有有效副本，通知發送方緩存； 3. 如果其他緩存具有有效副本，則狀态轉換為共享Shared(S)； 4. 如果其他緩存沒有有效副本(必須確定所有其他緩存都已報告) ，則狀态轉換為共享Exclusive(E)； 5. 若其他緩存具有副本，則其中一個緩存發送值，否則從主存擷取； |
| PrWr | 1. 在總線上發出BusRdX信号； 2. 在請求程式緩存中狀态轉換為Modified(M)； 3. 如果其他緩存有副本，則發送值，否則從主存擷取； 4. 如果其他緩存有副本，它們将看到BusRdX信号并使其副本無效； 5. 寫入緩存塊修改該值； | |
| Exclusive(E) | 1. 沒有生成總線事務； 2. 狀态保持不變； 3. 對塊的讀取命中緩存； | |
| 2. 狀态從Exclusive(E)轉換到Modified(M)； 3. 對塊的寫入命中緩存； | ||
| Shared(S) | ||
| 1. 在總線上發出BusUpgr信号； 2. 狀态從Shared(S)轉換到Modified(M)； 3. 其他緩存看到BusUpgr并将其塊副本标記為Invalid(I)。 | ||
| Modified(M) | ||
Table 1.2 狀态轉換和對各種總線操作的響應
| 總線操作 | 備注 | ||
|---|---|---|---|
| BusRd | 沒有狀态變化。信号被忽略； | ||
| BusRdX | |||
| BusUpgr | |||
| 1. 狀态由Exclusive轉換為Shared（因為它意味着在其他緩存中進行讀取）； 2. 将FlushOpt信号和塊内容一起發送到總線； | |||
| 1. 狀态由Exclusive轉換為Invalid； 2. 将FlushOpt信号和現在已無效的塊中的資料一起發送到總線； | 1. 發生PrWr的處理器緩存将接收已失效的塊中的資料，因為緩存到緩存的傳輸通常比記憶體到緩存的傳輸延遲要短； 2. 有且僅有一個緩存狀态是Exclusive，其他緩存狀态是Invalid(I)，是以不會有BusUpgr操作； | ||
| 1. 無狀态變化（其他緩存在此塊上執行讀取，是以仍然共享）； 2. 可以将FlushOpt和塊的内容一起放在總線上（設計選擇，哪個共享狀态的緩存可以執行此操作）； | |||
| 1. 狀态從Shared轉換為Invalid，已發送BusUpgr的緩存狀态變為Modified(M)； | 對其他Shared(S)狀态的緩存的PrWr操作，向總線發出了BusUpgr信号； | ||
| 1. 狀态從Shared轉換為Invalid，已發送BusR的緩存狀态變為Modified(M)； | 英文原文中沒有這一項，但是我感覺這種情況是存在的：因為Shared和Invalid狀态的緩存是可以共存的，此時對Invalid緩存的PrWr操作會使所有其他Shared緩存副本無效； | ||
| 1. 狀态由Modified轉換為Shared； 2.把FlushOpt和資料放在總線上。由BusRd的發送方和記憶體控制器接收，寫入主記憶體； | |||
| 1. 狀态從Modified轉換為Invalid； 2.把FlushOpt和資料放在總線上。由BusRdX的發送方和記憶體控制器接收，寫入主記憶體； |
僅當緩存行處于Modified或Exclusive狀态時，才能自由執行寫操作。如果緩存處于Shared(S)狀态，則必須首先使所有其他緩存副本無效。這通常通過一種稱為“請求所有權”（RFO，Request For Ownership）的廣播操作來完成。
儲存處于Modified狀态的行的緩存 必須偵測（截獲）對對應主存位置的所有嘗試讀取（來自系統中的所有其他緩存），并插入其儲存的資料。
- 這可以通過強制讀取退出（即稍後重試），然後将資料寫入主記憶體并将緩存行更改為Shared狀态來實作。
-
也可以通過将資料從Modified的緩存發送到執行讀取的緩存來完成。
注意，隻有讀未命中時才需要監聽（協定確定，如果任何其他緩存可以執行讀命中，則Modified緩存将不存在）。
儲存處于Shared狀态的行的緩存必須偵聽來自其他緩存的invalidate或request-for-ownership廣播，并在比對時丢棄該行（通過将其移動到無效狀态）。
Modified狀态和Exclusive狀态總是精确的：即，它們與系統中真正的緩存行所有權情況相比對。
Shared狀态可能不精确：如果另一個緩存丢棄共享行，此緩存可能成為該緩存行的唯一所有者，但不會提升為獨占狀态。其他緩存在丢棄緩存行時不會廣播通知，并且此緩存在不保留共享副本數的情況下無法使用此類通知。
從這個意義上說，Exclusive狀态是一種機會主義優化：如果CPU想要修改處于Shared狀态的緩存行，則需要一個總線事務來使所有其他緩存副本無效。狀态Exclusive允許在沒有總線事務的情況下修改緩存行。
3.3 存儲緩沖區和無效隊列
MESI協定在其簡單、直接的實作中表現出兩個特殊的性能問題。
- 首先，當寫入無效緩存行時，從另一個CPU擷取緩存行時會有很長的延遲。
-
其次，将緩存行移動到Invalid狀态非常耗時。
為了減輕這些延遲，CPU實作存儲緩沖區和無效隊列。
3.4 存儲緩沖區
寫入無效緩存行時使用存儲緩沖區。由于寫操作仍将繼續，CPU會發出一條讀無效消息（是以有問題的緩存行和存儲該記憶體位址的所有其他CPU緩存行都将失效），然後将寫操作推入存儲緩沖區，在緩存行最終到達緩存時執行。
存儲緩沖區存在的直接後果是，當CPU送出寫操作時，該寫操作不會立即寫入緩存。是以，每當CPU需要讀取緩存行時，它首先必須掃描自己的存儲緩沖區，以确定是否存在相同的緩存行，因為有可能相同的緩存行以前由相同的CPU寫入，但尚未寫入緩存（前面的寫入仍在存儲緩沖區中等待）。請注意，雖然CPU可以讀取其存儲緩沖區中自己以前的寫操作，但在将這些寫操作從存儲緩沖區重新整理到緩存之前，其他CPU無法看到這些寫操作-CPU無法掃描其他CPU的存儲緩沖區。
3.5 無效隊列
關于無效消息，CPU實作了無效隊列，通過該隊列，剛收到的無效請求會立即得到确認，但實際上不會被執行。相反，無效消息隻需進入一個無效隊列，并盡快（但不一定立即）進行處理。是以，CPU可以忽略其緩存中的緩存線實際上無效的事實，因為無效隊列包含已接收但尚未應用的無效。請注意，與存儲緩沖區不同，CPU不能掃描無效隊列，因為CPU和無效隊列在實體上位于緩存的兩側。
是以，需要記憶體屏障。
- 存儲(寫)屏障将重新整理存儲緩沖區，確定所有寫操作都已應用于該CPU的緩存。
- 讀屏障将重新整理無效隊列，進而確定其他CPU的所有寫操作對重新整理CPU可見。
此外，記憶體管理單元不掃描存儲緩沖區，導緻類似問題。即使在單線程處理器中也可以看到這種效果。
Request-For-Ownership 廣播
所有權讀取（RFO）是緩存一緻性協定中的一種操作，它結合了讀取和無效廣播。
該操作是由試圖寫入處于Shared或Invalid狀态的緩存行的處理器發出的。該操作會導緻所有其他緩存将該行的狀态設定為Invalid。
所有權讀取事務是一種旨在寫入該記憶體位址的讀取操作。是以，此操作是獨占的。
它将資料帶到緩存中，并使儲存此記憶體行的所有其他處理器緩存失效。在上表中稱為“BusRdX”。
4、示例與問題：
4.1 引入store buffer後出現的問題1
試考慮如下代碼，a和b的初始值為0
a = 1;
b = a + 1;
assert(b == 2);
大緻過程如下圖所示：
- a,b假設在記憶體中的同一個Cache Block中；
- CPU 0 開始執行代碼
a = 1
- CPU 0 未命中 a 的緩存，處理器發出 PrWr 信号，同時将 BusRdX 信号放到總線上，使儲存此緩存行的所有其他處理器的緩存失效
- CPU 0 将寫入操作儲存在了存儲緩沖區
- 因為其他處理器沒有 a 的緩存行的副本，是以從主存中擷取
- CPU 0 現在開始執行
b = a + 1
- CPU 0 從它的緩存中讀取了 a ，值為 0，并用于計算。（此時，主存傳輸給Cache 0 的資料才剛剛到，還未來得及将存儲緩沖區的寫操作作用到緩存）
- CPU 0 根據緩存中擷取到的 a = 0，計算出了 b 的值為 1
- CPU 0 根據存儲緩沖區中的寫操作，将 Cache 0 中的緩存行上 a 的值更新為 1
- CPU 0 用 b = 1 修改了緩存塊
- CPU 0 執行
assert(b == 2)
出現問題的原因是我們有兩份”a”的拷貝，一份在cache-line中，一份在store buffer中。硬體設計師的解決辦法是“store forwarding”，當執行PrRr操作時，會同時從cache和store buffer裡讀取。也就是說，當進行一次PrRr操作，如果store-buffer裡有該資料，則CPU會從store-buffer裡直接取出數 據，而不經過cache。因為“store forwarding”是硬體實作，我們并不需要太關心。
4.2 引入store buffer後出現的問題2
假如我們讓CPU 0 執行：
void flag(void) {
a = 1;
b = 1;
}
讓 CPU 1 執行：
void judge(void) {
while (b = 0) continue;
assert(a == 1);
}
-
a = 1
- CPU 1 執行
while (b == 0) continue
-
b = 1
- CPU 0 接收到BusRd消息，并且發送FlushOpt帶着緩存行中的最新的“b”的值到總線上，同時将緩存行設定為“shared”狀态；
- CPU 1 接收到包含“b”值的緩存行，并将其值寫到它的緩存行中，記憶體控制器也接收到“b”值的緩存行，更新記憶體塊；
- CPU 1 現在結束執行
while (b == 0) continue
-
assert(a == 1)
- CPU 0 把存儲緩沖區的“a”的值寫入到它的緩存 Cache 0 中，個人感覺這個地方可以再次修改緩存行為“Modified”狀态，并再次發送“BusRdX”消息到總線，使儲存此記憶體行的所有其他處理器緩存失效，（但是這裡我沒查閱資料，如果講得不對，歡迎指正）
總而言之，可能出現這類情況，b已經指派了，但是a還沒有，是以出現了
b = 1, a = 0
的情況。對于這類問題，硬體設計者也愛莫能助，因為CPU無法知道變量之間的關聯關系。是以硬體設計者提供了
memory barrier
指令，讓軟體來告訴CPU這類關系
解決辦法是：使用硬體設計者提供的“記憶體屏障”來修改代碼：
void foo(void)
{
a = 1;
smp_mb();// 強制重新整理store-buffer，再繼續進行後面的指派
b = 1;
}
4.3 Invalidate Queue的引入
store buffer一般很小，是以CPU執行幾個store操作就會填滿, 這時候CPU必須等待invalidation ACK消息（得到invalidation ACK消息後會将storebuffer中的資料存儲到cache中，然後将其從store buffer中移除），來釋放store buffer緩沖區空間。
“Invalidation ACK”消息需要如此長的時間，其原因之一是它們必須確定相應的緩存行實際變成無效了。如果緩存比較忙的話，這個使無效操作可能被延遲。例如，如果CPU密集的裝載或者存儲資料，并且這些資料都在緩存中。另外，如果在一個較短的時間内，大量的“使無效”消息到達，一個特定的CPU會忙于處理它們。這會使得其他CPU陷于停頓。但是，在發送應答前，CPU 不必真正的使無效緩存行。它可以将使無效消息排隊。并且它明白，在發送更多的關于該緩存行的消息前，需要處理這個消息。
一個帶Invalidation Queue的CPU可以迅速應答一個Invalidation Ack消息，而不必等待相應的行真正變成無效狀态。于是乎出現了下面的組織架構：
這樣可以提高效率，但是仍然無法避免
4.2 引入store buffer後出現的問題2
中存在的問題。
- CPU0執行
a=1
- CPU1執行 while(b==0) continue;但是b不再CPU1-cache中，是以發送read消息
- CPU1接受到CPU0的invalidate消息，将其排隊，然後傳回ACK消息
- CPU0接收到來自CPU1的ACK消息，然後執行smp_mb()，将a從store-buffer移到cache-line中。（記憶體屏蔽在此處生效了）
- CPU0執行b=1;因為已經包含了該cache-line，是以将b的新值寫入cache-line
- CPU0接收到了read消息，于是傳遞包含b新值的cache-line給CPU1，并标記為shared狀态
- CPU1接收到包含b的cache-line
- CPU1繼續執行while(b==0) continue;因為為假是以進行下一個語句
- CPU1執行assert(a==1)，因為a的舊值依然在CPU1-cache中，斷言失敗
盡管斷言失敗了，但是CPU1還是處理了隊列中的invalidate消息，并真的invalidate了包含a的cache-line，但是為時已晚
出現問題的原因是，當CPU排隊某個invalidate消息後，并做錯了應答Invalidate Ack, 但是在它還沒有處理這個消息之前，就再次讀取了位于cache中的資料，該資料此時本應該已經失效，但由于未處理invalidate消息導緻使用錯誤。
void bar(void)
{
while (b == 0) continue;
smp_mb();
assert(a == 1);
}
void foo(void)
{
a = 1;
smp_wmb();/*CPU1要使用該值，是以需要及時更新處理store buffer中的資料*/
b = 1;
}
void bar(void)
{
while (b == 0) continue;
smp_rmb();/*由于CPU0修改了a值，使用此值時及時處理Invalidation Queue中的消息*/
assert(a == 1);
}