萬字詳解緩存一致性協定與記憶體屏障（漫畫風）

2024-08-27碼農

故事還得從一個矛盾說起。

莫耳定律告訴我們：大約每18個月會將芯片的效能提高一倍。芯片的這種飛速發展直接導致了芯片的指令執行速度與記憶體讀取速度之間的巨大鴻溝。

舉個例子，CPU在1納秒之內可以執行幾十條指令，但是從記憶體中讀取一條數據就需要花費幾十納秒。這種數量級的差異便是電腦中的一個主要矛盾：

CPU日益增長的對數據快速讀取的需要和I/O裝置讀取速度不平衡不充分的發展之間的矛盾

而CPU執行所需要的指令和數據都儲存在低速的記憶體中，人們無法容忍讓CPU這樣寶貴的高速裝置進行漫長的等待。

電腦科學領域的任何問題都可以透過增加一個中間層來解決。所以需要一個比記憶體更快的存取裝置做緩沖，盡量做到和CPU一樣快，這樣就不需要每次都從低速的記憶體中獲取數據了。

於是引入了快取。

1. 快取

我們已經知道為什麽需要快取了。那麽什麽是快取？它為什麽就比記憶體快？既然這麽快，為什麽不直接當成記憶體用？

別急，我一點點解釋。

1.1. 什麽是快取Cache

我們最熟悉的記憶體是一種 動態隨機存取記憶體（Dynamic RAM,DRAM） ，記憶體中每個儲存單元由配對出現的晶體管和電容器構成，每隔一段時間，固定要對 DRAM 重新整理充電一次，否則內部的數據就會消失。

而快取是一種 靜態隨機存取記憶體（Static RAM,SRAM） ，不需要重新整理電路就能保存它內部儲存的數據，這就是靜態的含義，因此 SRAM 的儲存效能非常高！工作速度在納秒級別，勉強能跟得上CPU的運算速度。

但是 SRAM 的缺點就是整合度低，相同容量的記憶體可以設計成較小的體積，但是 SRAM 卻需要更大的體積；而且， SRAM 這玩意兒巨貴！這就是不能直接把它當記憶體用的原因。

越靠近CPU核心地帶的裝置越需要強悍的效能，可是容量如果太小又幫不上太大的忙。如果一個中間層（一層快取）不能高效解決問題，那就多來幾個中間層。目前CPU的解決思路一般是以量取勝，比如同時設定 L1 、 L2 、 L3 三級緩存。

在緩存容量上，通常是 記憶體 > L3 > L2 > L1 ，容量越小速度越快。其中 L1 和 L2 是由每個CPU核心獨享的， L3 緩存是由所有CPU核心共享的。CPU的架構見下圖：

需要特別說明的是， L1 緩存又分為了 L1d 數據緩存（L1 Data）和 L1i 指令緩存（L1 Instruct），上圖為了完整性一並畫出了，本文中的快取一律指數據緩存。

為了接下來方便講解，我們把三級緩存模型簡化為一級緩存模型，畢竟道理都是相通的嘛。看一下簡化之後的圖。

1.2. 緩存行

說完了什麽是Cache，接下來我們來看看Cache裏裝的到底是什麽？

這不是廢話嘛，肯定裝的是數據啊。沒錯，是從記憶體中獲取到的數據，但是數據的單位呢？CPU每次只把需要的數據從記憶體中讀取到Cache就行了嗎？肯定不是，我們想一下，只把需要的一個數據從記憶體中讀到Cache，CPU再從Cache中繼續讀這個數據進行處理，Cache的存在完全就是多此一舉，還不如直接從記憶體讀數據呢。

所以要想讓Cache充分發揮作用，必須讓它做點「多余」的事情。因此從記憶體中獲取數據的時候，我們把包含目標數據的一整塊記憶體數據都放入Cache中。別小看這個動作，它有個科學的解釋，叫做 空間局部性 。

位置相鄰的數據常常會在相近的時間內被存取

根據 空間局部性 原理，如果目標數據相鄰的數據被存取，CPU就不需要再從記憶體中獲取了，這種直接從Cache中獲取到目標數據的行為叫做「 緩存命中 」，極大地提高了CPU的工作效率。如果Cache裏邊沒有，就稱為 Cache Miss ，CPU需要再等待幾十個指令周期從記憶體中把這一整塊記憶體數據讀入Cache。

給儲存「一整塊記憶體數據」的地方起個名字，叫「 緩存行 」（ Cache Line ）。

Cache是由緩存行組成的，緩存行是CPU快取和記憶體互動的最小單元。在X86架構中，緩存行的大小是64個字節，大小和CPU具體型號有關。本文只關註緩存行的抽象概念，不涉及具體的緩存行大小。

接下來，終於要進入本文的正式部份了。

我一直認為，電腦的演進就是一部在挖坑和填坑之間反復橫跳的發展史。對這一點的理解會隨著本文的後續講述逐漸加深。比如快取Cache很好地解決了CPU與記憶體的速度矛盾，但是也為電腦系統帶來了更高的復雜度，我來舉個例子。

2. 偽共享問題

我們到目前為止說的都是CPU從Cache中read數據，但是總得有write的時候吧。既然有了Cache，肯定就得先把值write到Cache中，再更新到記憶體裏啊。那麽，問題來了。

2.1. 什麽是偽共享

偽共享問題

數據 X 、 Y 、 Z 同處於一個緩存行內， Core0 和 Core1 同時載入了該緩存行到Cache中，此時 Core0 修改了該緩存行中的 X 為 X1 ，如果此時 Core1 也想修改 Y 為 Y1 該怎麽辦呢？

由於緩存行是Cache和記憶體之間互動的最小單元，所以 Core0 根本不知道 Core1 修改的是緩存中的 Y 還是 X ，所以為了防止造成並行問題，最好的辦法就是讓 Core1 中的該緩存行失效，重新載入。這就是 偽共享 問題。

偽共享問題的定義： 當多核心修改互相獨立的變量時，如果這些變量共享同一個緩存行，就會無意中影響彼此的效能，這就是偽共享 。

2.2. 解決偽共享

既然問題是由多個變量共享一個緩存行導致的，那就讓 Y 變量獨享一個緩存行就好了。

最簡單的方法就是透過程式碼手動進行字節填充，拿早期的 LinkedTransferQueue 中的部份源碼舉個例子，註意看註釋內容：

staticfinal classPaddedAtomicReference<T> extendsAtomicReference<T> { // 追加15個物件參照,一個物件參照占據4個字節 // 加上繼承自父類的value，共64字節，正好占一個緩存行 Object p0, p1, p2, p3, p4, p5, p6, p7, p8, p9, pa, pb, pc, pd, pe; PaddedAtomicReference(T r) { super(r); } } //父類 public classAtomicReference<V> implementsjava.io.Serializable{ privatevolatile V value; publicAtomicReference(V initialValue){ value = initialValue; } }

此外，JDK 8開始，提供了一個 sun.misc.Contended 註解來解決偽共享問題，加上這個註解的類會自動補齊緩存行。

稍微扯遠了一些，我們回到上方的動圖。 Core0 修改了緩存行中的 X ，我們說當前最合適的處理辦法就是讓 Core1 中的緩存行失效，否則就會出現緩存一致性問題。偽共享問題其實就是解決緩存一致性問題的副作用。只不過本文中我單獨把這個問題列了出來。

為了解決緩存一致性問題，CPU天然支持了匯流排鎖的功能。

3. 匯流排鎖

顧名思義就是，鎖住Bus匯流排。透過處理器發出 lock 指令，匯流排接受到指令後，其他處理器的請求就會被阻塞，直到此處理器執行完成。這樣，處理器就可以獨占共享記憶體的使用。

但是， 匯流排鎖有一個非常大的缺點，一旦某個處理器獲取匯流排鎖，其他處理器都只能阻塞等待，多處理器的優勢就無法發揮 。

於是，經過發展、最佳化，又產生了緩存鎖。

4. 緩存鎖

緩存鎖：不需釘選匯流排，維護本處理器內部緩存和其他處理器緩存的一致性。相比匯流排鎖，會提高cpu利用率。

但是緩存鎖也不是萬能，有些場景和情況依然必須透過匯流排鎖才能完成。

緩存鎖其實是一種實作的效果 ，它是透過 緩存一致性協定 來實作的，可能有的讀者也聽說過 Snoopy嗅探協定 ，我舉個例子幫助大家理解這三個概念。

假如村裏有一個單人公廁，一條蜿蜒大道與公廁相連，大道旁邊住著A、B、C、D四個人，每個人要上廁所必須經過主幹道。

我們再設定一點前提，假設每個人都不想到了廁所門口的時候才知道廁所已經被人占用了。

為了合理使用廁所，保證每次只有一個人進入廁所，並且不會出現其他人在廁所門口等待的情況，ABCD四個人聚在一起開會討論，協商出了一條約定。

當有人去上廁所的時候，其他人在家老實呆著，不要去上廁所！

四個人紛紛拍著自己大腿叫絕。他們商議出來了一個聽起來確實能解決問題，但是實際上內容非常空洞的一個協定。

因為他們不知道現在有誰正在占用廁所，更不知道誰正在前往廁所的路上。

其中A靈機一動，想出了一個辦法。可以在每家和主幹道的岔路口設定一個監測裝置，當有人上廁所經過岔路口的時候監測裝置就提醒其他三個人已經有人去廁所了，老實在家等著吧。

如此一來，就達成了一種給廁所添加鎖的一種效果，這種效果就相當於上文提到的緩存鎖。4人商議出來的協定就相當於緩存一致性協定，A提出來的方法實作了協定，相當於Snoopy嗅探。

如果大家讀到這裏在思考例子中的廁所究竟表示記憶體還是緩存行，我勸大家趕緊止住。在生活中找到和電腦科學中非常貼切的例子是非常非常困難的。這個例子只是簡單說明一下緩存鎖和鎖存一致性協定以及Snoopy嗅探協定之間的關系罷了，不要深究！

自然，緩存一致性協定就是我們接下來的主角了。

5. 緩存一致性協定

每個處理器共享同一個主記憶體，並且都有自己的快取。 如果多個處理器都對同一塊主記憶體區域進行更改，將導致各自的的緩存數據不一致 。那同步到主記憶體時該以誰的緩存數據為準呢？

緩存一致性協定就是為了解決這個問題提出的，這類協定有 MSI 、 MESI 和 MOSI 等。

我們以套用最廣泛的 MESI 為例進行介紹。

5.1. MESI

MESI 是 Modified 、 Exclusive 、 Shared 、 Invalid 四個單詞的首字母縮寫，表示 緩存行 的4種狀態。

Modified

緩存行被對應的CPU核心修改之後就會處於 Modified 狀態，並且保證該緩存行不會出現在任何其他CPU的緩存中。即使有，也是 Invalid 狀態，需要從記憶體或其他Cache中重新讀取。

因此，處於 Modified 狀態的緩存行可以說是被相應CPU核心獨占的。由於該緩存行擁有該數據的唯一最新副本，因此該緩存行最終負責將其寫回記憶體或將其傳遞給其他CPU。

Exclusive

Exclusive 狀態就非常好理解了，意味著獨占、排他，和 Modified 狀態非常類似。唯一不同的一點就是這個緩存行還沒有被CPU核心修改，這也說明記憶體中的內容依然是最新的。即便如此，一旦某個緩存行處於該狀態，就意味著其他CPU核心不能擁有該緩存行的副本。

Shared

處於 Shared 狀態的緩存行意味著同時出現在了一個或多個CPU Cache中，且多個CPU Cache的緩存行和記憶體中的數據一致。CPU核心不能在未與其他核心「協商」的情況下，修改其Cache中的該緩存行。至於什麽是「協商」，下文會講到。

Invalid

處於 Invalid 狀態的緩存行不包含任何數據，只是被打上了 Invalid 狀態的標簽而已。其他CPU修改了緩存行，就會導致本CPU中的該緩存行失效為 Invalid 狀態。當有新數據被放入Cache中時，會被優先放入 Invalid 狀態的緩存行中，避免置換出其他有用的緩存導致Cache Miss。

以上4種狀態之間的躍遷離不開各個CPU核心之間的協作，比如某個數據被同時緩存在多個CPU核心的Cache中，此時這些緩存行的狀態是 Shared ，假如 Core0 對緩存行做了write操作，為了避免緩存數據的不一致性，其他CPU核心需要將對應的緩存行狀態設定為 Invalid 狀態。那麽其他CPU核心是怎麽知道 Core0 修改了緩存行呢？換個問法， Core0 怎麽讓其他核心知道自己修改了緩存行呢？

人有人言，獸有獸語。CPU核心之間的溝通也有自己的一套「黑話」，稱為 緩存一致性訊息 。

5.2. CPU之間的「黑話」

訊息分為請求和響應兩類。

處理器在進行數據讀寫的時候會往匯流排（Bus）中發請求訊息，同時每個處理器核心還會嗅探（Snoop）匯流排中由其他處理器發出的請求訊息並在一定條件下往匯流排中回復響應訊息。

Read

Read 訊息表示要讀取某個緩存行，同時會攜帶目標緩存行對應的實體位址。

Read Response

是對 Read 訊息的反饋，反饋的內容就是發 送Read 訊息的CPU核心請求的目標緩存行。 Read Response 可能來自於記憶體，也可能來自其他CPU核心。

比如，如果被請求的目標緩存行不存在於任何CPU Cache中，那麽只能從記憶體中獲取；如果被請求的目標緩存行恰好被其中一個CPU修改，此時該緩存行為 Modified 狀態，意味著該緩存行目前是最新數據，那麽理應讓其他同樣需要該緩存行的CPU核心獲取到該最新數據，更進一步，自然理應由該CPU核心把該緩存行的內容反饋給發出 Read 訊息的CPU核心。

Read Response

Invalidate

Invalidate 的含義是使某個緩存行失效，擁有該緩存行的其他CPU核心需要刪除該緩存行中的數據，並對發出 Invalidate 訊息的核心做出反饋。

Invalidate Acknowledge

這就是上面提到的 Invalidate 訊息的反饋，意味著發出此訊息的CPU核心已經將 Invalidate 訊息的目標緩存行中的數據清除。

Invalidate

如果有多個CPU同時發出 Invalidate 訊息怎麽辦？答案是匯流排裁決。首先占用訊息匯流排的CPU核心獲勝，其他核心只能乖乖清空自己的緩存行，並向其發出 Invalidate Acknowledge 反饋。

Read Invalidate

Read Invalidate 相當於 Read + Invalidate ，既要讀取某個緩存行資訊，又要讓屬於其他CPU核心的此緩存行失效。同樣， Read Invalidate 也需要收到反饋，只不過此反饋既包含1條 Read Response ，又包含多條（如果其他CPU核心也擁有目標緩存行的話） Invalidate Acknowledge 。

Writeback

Writeback 訊息包含要寫回記憶體的地址和數據，通常指的是 Modified 狀態的數據，這樣Cache就可以根據需要彈出處於 Modified 狀態的緩存行，以便為其他數據騰出空間。

這倆訊息很簡單，就不畫圖浪費你們的流量了。。。

5.3. MESI狀態躍遷範例

CPU之間透過緩存一致性訊息的傳遞，才有了緩存行在 MESI 四種狀態之間的躍遷。

如上圖，每兩個狀態之間都可能會發生狀態越遷，是不是感覺很復雜？

如果之前的內容我給你解釋地很清楚的話，就很容易想明白每個狀態之間的躍遷場景了。為了不影響接下來的講解，我把每種場景解釋放在了文章最後（見附錄1），需要的讀者讀完文章之後可以翻閱一下（即使不看也不會影響接下來的閱讀哦）。

還有一個線上的網站可以幫助你更好地理解MESI協定（見附錄2），你可以站在CPU的角度發出指令，網站以動態方式展示緩存行的狀態變換，強烈建議閱讀完文章之後大家試一下。

截至目前，文章都是圍繞Cache展開的，快取的引入極大地提高了電腦的整體執行效率。但在某些特殊情況下，CPU的效能表現卻是非常糟糕。

6. 不能讓CPU閑著

考慮這麽一個場景， CPU 0 和 CPU 1 同時擁有某個緩存行，兩個緩存行都處於 Shared 狀態， CPU 0 想對自己的緩存行執行write操作，必須先發送 Invalidate 訊息讓 CPU 1 中的緩存行失效。如下圖所示：

CPU閑下來了

由於 CPU 0 必須等到 CPU 1 反饋了 Invalidate Acknowledge 之後才能確保自己可以操作緩存行，所以從發出 Invalidate 直到收到 Invalidate Acknowledge 的這段時間， CPU 0 一直處於閑置狀態。

CPU是何等寶貴的資源，讓它閑著是不可能的，絕對不可能的！

硬體工程師為了解決這個問題，引入了 Store Buffers 。

6.1. 引入Store Buffers

工程師在CPU和Cache之間添加了一個中間層—— Store Buffer 。當 CPU 0 想執行write指令時，先把想要write的值寫入到 Store Buffer 中，然後再繼續執行其他任務，無需傻傻地等待 CPU 1 。直到 CPU 1 傳回反饋之後， CPU 0 再將 Store Buffer 中的最新值寫入到緩存行中。

電腦的發展就是不斷挖坑、填坑的過程。 Store Buffers 的引入解決了CPU閑置的問題，如果事情發展到現在就完美了該有多好，然而又引出了3個新問題。

6.2. Store Buffers引起的問題1

看一下上圖左側的程式碼，其中 a 和 b 的初始值為0，在大多數時候，最後的斷言會為True。

之所以說大多數時候，因為左側的程式碼在某個場景下可能會出現不符合我們預期的情況（斷言為False）。如果要證明，我們只需要舉出一個反例即可，因此我們進一步假設含有變量 a 的緩存行已經存在於 CPU 1 的Cache中，含有變量 b 的緩存行已經存在於 CPU 0 的Cache中。

下面我們根據引入 Store Buffers 之後的CPU架構來執行上面的程式碼， CPU 0和CPU 1 的操作順序如下圖所示：

CPU 0 執行 a = 1 ;
CPU 0 首先從自己的Cache中尋找 a ，發現沒有；
CPU 0 發送 Read Invalidate 訊息來獲取含有 a 的緩存行，並通知其他CPU，「老子要用，你們都給我銷毀！」；
CPU 0 在 Store Buffer 中記錄下自己想賦給 a 的值，即 a = 1 。此時CPU 0並不會阻塞，會繼續向下執行，但是在時間線的發展上，緊接著是CPU 1的操作，見第5步；
CPU 1收到來自CPU 0的 Read Invalidate 訊息，於是把自己包含 a 的緩存行返回給CPU 0，並且把自己的緩存行狀態設定為 Invalid ；
CPU 0 開始執行 b = a + 1 ；
CPU 0 收到來自CPU 1 的緩存行，並放到自己的緩存行中，其中 a 的值為0；此時CPU 0 的緩存行中的 a 和 b 的狀態都是 Exclusive ，因為這些緩存行都由CPU 0 獨占；
CPU 0 從緩存行中讀取 a ，此時值為0；
CPU 0 根據自己之前在 Store Buffer 中存放的 a = 1 來更新自己Cache中的 a ，設定為1；
CPU 0 在第8步獲取的 a 值的基礎上 + 1 （這一步不需要重新從緩存行中讀取數據，因為讀取的動作在第8步中已經做了），並更新自己緩存行中的 b ；此時包含 b 的緩存行的狀態 為Modified ；
CPU 0 執行斷言操作，發現斷言為False。

再給大家補充一個動圖：

這確實是一件非常違反直覺的事情，我們本來以為CPU就是完全按照程式碼的順序執行的（至少最終結果應該表現地像CPU是完全按照程式碼的順序執行的一樣），我們認為 b 的最終結果就應該是2。

出現這個問題的原因是 CPU 0 執行過程中出現了 a 的兩份數據拷貝，一份是在 Store Buffer 中，一份是在Cache中。為了不讓軟體工程師瘋掉，繼續保持軟體程式碼的直觀性，硬體工程師又引入了 Store Forwarding 來解決這個問題。

6.3. 引入Store Forwarding

每個CPU在執行數據載入操作時都直接使用 Store Buffer 中的內容，而無需從Cache中獲取，如下圖所示。

請註意上圖和原來圖片的區別，上圖中的 Store Buffer 中的數據可以直接被CPU讀取。對應到上面的 CPU 0 的操作步驟，就是第8步直接從 Store Buffer 中讀取最新的 a ，而不是從Cache中讀取，這樣整個程式的最終斷言結果就是True！

總之，引發的第1個問題，硬體工程師透過引入 Store Forwarding 為我們解決了。

6.4. Store Buffers引起的問題2

在多個CPU並行處理情況下也可能會導致程式碼執行出現問題。

同樣也是舉一個極端一點的例子。見下圖左側的程式碼，其中 a 和 b 的初始值為0，進一步假設含有變量 a 的緩存行已經存在於 CPU 1 的Cache中，含有變量 b 的緩存行已經存在於 CPU 0 的Cache中。 CPU 0 執行 foo 方法， CPU 1 執行 bar 方法。正常情況下， bar 方法中的斷言結果應該為True。

然而，我們按照下圖中的執行順序操作一遍之後，斷言卻是False！

CPU 0 執行 a = 1 ，首先從自己的Cache尋找啊，發現沒有；
CPU 0 將 a 的新值 1 寫入到自己的 Store Buffer 中；
CPU 0 發送 Read Invalidate 訊息（從發出這個訊息到CPU 1 接收到，期間又執行了非常多的步驟，見下方GIF圖）；
CPU 1 執行 while (b == 0) continue ，發現 b 不在自己的 Cache 中，於是發送 Read 訊息；
CPU 0 執行 b = 1 ，由於 b 已經存在於自己的Cache中了，所以直接將Cache中的 b 修改為 1 ，並修改包含 b 的緩存行的狀態為 Modified ；
CPU 0 收到來自第4步CPU 1 發出的 Read 訊息，由於當前自己擁有的 b 是最新版本的，所以CPU 0 把含有 b 的緩存行返回給CPU 1，同時修改自己的緩存行狀態為 Shared ；
CPU 1 收到來自CPU 0 的 b 緩存行數據，放到自己的Cache中，並設定為 Shared 狀態；
CPU 1 結束 while 迴圈，因為此時的 b 值已經是 1 了；
CPU 1 執行 assert(a == 1) ，由於Cache中的 a 值是 0 （此時還沒收到來自CPU 0 的 Read Invalidate 訊息，因此CPU 1 有理由認為自己的數據就是合法的），因此斷言結果為False；
CPU 1 終於收到來自CPU 0 的 Read Invalidate 訊息了，雖然已經晚了（當然CPU壓根不知道自己的這個訊息接收的時機並不合適），但是還得按照約定把自己的 a 設定為 Invalid 狀態，並且給CPU 0 發送 Invalidate Acknowledge 以及 Read Response 反饋；
CPU 0 收到CPU 1 的反饋，利用 Store Buffer 中的值更新 a 。

至此，流程全部結束，再送給大家一個GIF。

我們分析一下結果不符合我們預期的原因。

Store Buffer 的加入導致 Read Invalidate 的發送是一個異步操作，異步可能導致的結果就是CPU 1 接收到CPU 0 的 Read Invalidate 訊息太晚了，導致在Cache中的實際操作順序是 b = 1 ，最後才是 a = 1 ，就好像 寫操作被重排序 了一樣，這就是 CPU的亂序執行 。

如果沒有看懂上面一段就再看一下圖片中的CPU 0 Cache的時間線演化。

很多人看到「亂序執行」唯恐避之不及，它當初可是為了提高CPU的工作效率而誕生的，而且在大多數情況下並不會導致什麽錯誤，只是在多處理器（smp）並行執行的時候可能會出現問題，於是便有了下文。

也就是說，如果在第5步CPU 0 修改 b 之前，我們強制讓CPU 0先完成對 a 的修改就可以了。

為了解決這樣的問題，CPU提供了一些操作指令，來幫助我們避免這樣的問題，就是大名鼎鼎的 記憶體屏障 （Memory Barrier,mb）。

6.5. 記憶體屏障

我們稍微修改一下 foo 方法，在 b = 1 之前添加一條記憶體屏障指令 smp_mb() 。

多說一點， smp 的全稱是Symmetrical Multi-Processing（對稱多處理）技術，是指在一個電腦上匯集了一組處理器(多CPU)，各CPU之間共享記憶體子系統以及匯流排結構。

為什麽要特意加上 smp 呢？因為即便現代處理器會亂序執行，但在單個CPU上，指令能透過指令佇列順序獲取指令並執行，結果利用佇列順序返回寄存器，這使得程式執行時所有的記憶體存取操作看起來像是按程式程式碼編寫的順序執行的，因此沒必要使用記憶體屏障（前提是不考慮編譯器的最佳化的情況）。

記憶體屏障聽起來很高大上，但是對於軟體開發者而言其實非常簡單，總結一句話就是：

在記憶體屏障語句之後的所有針對Cache的寫操作開始之前，必須先把Store Buffer中的數據全部重新整理到Cache中。

如果你看明白了我上面說的 Store Buffer ，這句話是不是賊好懂呢？換個角度再轉譯一下，就是一定要保證 存到Store Buffer中的數據有序地重新整理到Cache中 ，這樣就可以避免發生指令重排序了。

如何保證有序呢？

最簡單的方式就是讓CPU傻等， CPU 0 在執行第5步之前必須等著 CPU 1 給出反饋，直到清空自己的 Store Buffer ，然後才能繼續向下執行。

啥？又讓CPU閑著？一切讓CPU閑置的方法都是餿主意！

還有一個辦法就是讓數據在 Store Buffer 中排隊，誰先進入就必須先重新整理誰，後邊的必須等著！

這樣一來，本來可以直接寫入Cache的操作（比如待操作的數據已經存在於自己的Cache中了）也必須先存到Store Buffer，然後依序進行重新整理 。

套用記憶體屏障之後的操作步驟就不給大家再寫一遍了，相信大家能夠想清楚。

總之，引發的第2個問題，我們透過使用記憶體屏障解決了。

6.6. Store Buffers引起的問題3

Store Buffer 的容量通常很小，如果CPU此時需要對多個數據執行write操作，碰巧這些數據都不在該CPU的Cache中，那麽該CPU只能發送對應的 Read Invalidate 指令了，同時新數據寫入 Store Buffer ，非常容易導致 Store Buffer 空間被占滿。

一旦 Store Buffer 被占滿，CPU就只能 幹等著 目標CPU完成 Read Invalidate 操作，並且返給自己 Invalidate Acknowledge ，當前CPU才能逐步將 Store Buffer 中的值重新整理到Cache，騰出空間，然後繼續執行。

CPU又又又閑下來了！所以我們肯定又得找個辦法來解決這個問題。

出現這個問題的主要原因在於 Invalidate Acknowledge 的反饋速度太慢了！

因為CPU太老實了，它只有在確認自己的緩存行被設定為 Invalid 狀態之後才會發送 Invalidate Acknowledge 。如果Cache的其他操作太頻繁，「設定緩存行為Invalid狀態」這個動作本身都會被延遲執行，更何況 Invalidate Acknowledge 的反饋動作呢，得等到猴年馬月啊！

上面的GIF圖中為了表現出「反饋慢」這種情況，我特意把 Invalidate 訊息的發送速度設定地很慢，其實訊息地發送速度非常快，只是CPU處理 Invalidate 訊息的速度太慢了而已，望悉知。

如果不想等，想直接獲取操作結果，你想到了什麽？

沒錯，是異步！

實作方式就是再加一層訊息佇列—— Invalidate Queues 。

6.7. 引入Invalidate Queues

如下圖，我們的硬體架構又升級了。在每個CPU的Cache之上，又設定了一個 Invalidate Queue 。

這樣一來，收到 Invalidate 訊息的CPU核心會把 Invalidate 訊息直接儲存到 Invalidate Queue 中，然後立即返回 Invalidate Acknowledge ，不需要再等著緩存行被實際設定成 Invalid 狀態再發送，極大地提高了反饋速度。

你可能會問，萬一 Invalidate Queues 中的 Invalidate 訊息最終執行失敗，但是 Acknowledge 訊息已經返回了，這該怎麽辦呢？

好問題！答案是，我不知道。我們就當作硬體工程師絕對不會留下這個bug就是了。

Invalidate Queue

Invalidate Queue 填了 Store Buffer 容量太小的坑，接下來看看它自己又挖了什麽坑吧。

6.7.1. Invalidate Queue引發的問題

這個坑比較嚴重，很有可能直接幹翻緩存屏障，再次引發亂序執行的問題。

老樣子，還是先準備一下翻車的環境。如下圖，我們假設變量 a 被 CPU 0 和 CPU 1 共享，為 Shared 狀態；變量 b 被 CPU 0 獨占，為 Exclusive 狀態； CPU 0 和 CPU 1 分別執行 foo 和 bar 方法。

我們按照下圖中的執行順序操作一遍。

CPU 0 執行 a = 1 ，因為CPU 0 的Cache中已經有 a 了，狀態為 Shared ，因此不能直接修改，需要發送 Invalidate （不是 Read Invalidate ，因為自己有 a ）訊息使其他緩存行失效；
CPU 0 把試圖修改的 a 的最新值 1 放入 Store Buffer ；
CPU 0 發送 Invalidate 訊息；
CPU 1 執行 while(b == 0) continue; 發現 b 不在自己的Cache中，於是發送 Read 訊息來獲取 b ；
CPU 1 收到來自CPU 0 的 Invalidate 訊息，把該訊息放入 Invalidate Queue 中（並沒有立即讓 a 失效），等候處理，然後立刻返回 Anknowledge ；
CPU 0 收到 Acknowledge 訊息，認為CPU 1 已經把 a 值設定為 Invalid 了，於是放心地把 Store Buffer 中的數據重新整理到自己的Cache中，此時CPU 0 Cache中的 a 為 1 ，狀態為 Modified ；然後就可以直接越過 smp_mb() 記憶體屏障，因為現在 Store Buffer 中的數據已經空了，滿足記憶體屏障的約束條件。
CPU 0 執行 b = 1 ，因為其獨占了 b ，所以可以直接在Cache中修改 b 的值，此時 b 緩存行的狀態為 Modified ；
CPU 0 收到來自CPU 1 的 Read 訊息，將修改之後的 b 緩存行返回，並修改自己Cache中的 b 緩存行的狀態為 Shared ；
CPU 1 收到包含 b 的緩存行數據，放在自己的Cache中，此時CPU 1 的Cache同時擁有了 a 和 b ；
CPU 1 結束執行 while(b == 0) continue; 因為此時CPU 1 讀到的 b 已經是 1 了；
CPU 1 開始執行 assert(a == 1) ，CPU 1 從自己的Cache讀到 a 為 0 ，斷言為False。
CPU 1 開始處理 Invalidate Queue 佇列，令Cache中的 a 失效，但是為時已晚！

至此流程全部結束，再上個GIF。

問題很明顯出在第11步，這就是臭名昭著著名的 可見性問題 。 CPU 0 修改了 a 的值， CPU 1 卻不知道或者說知道的太晚！如果在第11步讀取 a 的值之前就趕緊重新整理 Invalidate Queue 中的訊息，讓 a 失效就好了，這樣 CPU 1 就不得不重新 Read ，得到的結果自然就是 1 了。

原因搞明白了，怎麽解決呢？記憶體屏障再一次閃亮登場！