CPU 緩存一致性協議 MESI

CPU 高速緩存（Cache Memory）

CPU 爲何要有高速緩存

CPU 在摩爾定律的指導下以每 18 個月翻一番的速度在發展，然而內存和硬盤的發展速度遠遠不及 CPU。這就造成了高性能能的內存和硬盤價格及其昂貴。然而 CPU 的高度運算需要高速的數據。爲了解決這個問題，CPU 廠商在 CPU 中內置了少量的高速緩存以解決 I\O 速度和 CPU 運算速度之間的不匹配問題。

在 CPU 訪問存儲設備時，無論是存取數據抑或存取指令，都趨於聚集在一片連續的區域中，這就被稱爲局部性原理。

時間局部性（Temporal Locality）：如果一個信息項正在被訪問，那麼在近期它很可能還會被再次訪問。

比如循環、遞歸、方法的反覆調用等。

空間局部性（Spatial Locality）：如果一個存儲器的位置被引用，那麼將來他附近的位置也會被引用。

比如順序執行的代碼、連續創建的兩個對象、數組等。

帶有高速緩存的 CPU 執行計算的流程

  1. 程序以及數據被加載到主內存

  2. 指令和數據被加載到 CPU 的高速緩存

  3. CPU 執行指令，把結果寫到高速緩存

  4. 高速緩存中的數據寫回主內存

目前流行的多級緩存結構

由於 CPU 的運算速度超越了 1 級緩存的數據 I\O 能力，CPU 廠商又引入了多級的緩存結構。

多級緩存結構

多核 CPU 多級緩存一致性協議 MESI

多核 CPU 的情況下有多個一級緩存，如何保證緩存內部數據的一致, 不讓系統數據混亂。這裏就引出了一個一致性的協議 MESI。

MESI 協議緩存狀態

MESI 是指 4 中狀態的首字母。每個 Cache line 有 4 個狀態，可用 2 個 bit 表示，它們分別是：

緩存行（Cache line）: 緩存存儲數據的單元。

SySS2W

從上面的意義看來 E 狀態是一種投機性的優化：如果一個 CPU 想修改一個處於 S 狀態的緩存行，總線事務需要將所有該緩存行的 copy 變成 invalid 狀態，而修改 E 狀態的緩存不需要使用總線事務。

MESI 狀態轉換

理解該圖的前置說明：

  1. 觸發事件

x0ONER

2.cache 分類：
前提：所有的 cache 共同緩存了主內存中的某一條數據。

本地 cache: 指當前 cpu 的 cache。
觸發 cache: 觸發讀寫事件的 cache。
其他 cache: 指既除了以上兩種之外的 cache。
注意：本地的事件觸發 本地 cache 和觸發 cache 爲相同。

9wWmHI

下圖示意了，當一個 cache line 的調整的狀態的時候，另外一個 cache line 需要調整的狀態。

hDo5cH

舉個栗子來說：

假設 cache 1 中有一個變量 x = 0 的 cache line 處於 S 狀態 (共享)。
那麼其他擁有 x 變量的 cache 2、cache 3 等 x 的 cache line 調整爲 S 狀態（共享）或者調整爲 I 狀態（無效）。

多核緩存協同操作

假設有三個 CPU A、B、C，對應三個緩存分別是 cache a、b、 c。在主內存中定義了 x 的引用值爲 0。

單核讀取

那麼執行流程是：
CPU A 發出了一條指令，從主內存中讀取 x。
從主內存通過 bus 讀取到緩存中（遠端讀取 Remote read）, 這是該 Cache line 修改爲 E 狀態（獨享）.

雙核讀取

修改數據

那麼執行流程是：
CPU A 計算完成後發指令需要修改 x.
CPU A 將 x 設置爲 M 狀態（修改）並通知緩存了 x 的 CPU B, CPU B 將本地 cache b 中的 x 設置爲 I 狀態 (無效)
CPU A 對 x 進行賦值。

同步數據

那麼執行流程是：

MESI 優化和他們引入的問題

緩存的一致性消息傳遞是要時間的，這就使其切換時會產生延遲。當一個緩存被切換狀態時其他緩存收到消息完成各自的切換並且發出迴應消息這麼一長串的時間中 CPU 都會等待所有緩存響應完成。可能出現的阻塞都會導致各種各樣的性能問題和穩定性問題。

CPU 切換狀態阻塞解決 - 存儲緩存（Store Bufferes）

比如你需要修改本地緩存中的一條信息，那麼你必須將 I（無效）狀態通知到其他擁有該緩存數據的 CPU 緩存中，並且等待確認。等待確認的過程會阻塞處理器，這會降低處理器的性能。應爲這個等待遠遠比一個指令的執行時間長的多。

Store Bufferes

爲了避免這種 CPU 運算能力的浪費，Store Bufferes 被引入使用。處理器把它想要寫入到主存的值寫到緩存，然後繼續去處理其他事情。當所有失效確認（Invalidate Acknowledge）都接收到時，數據纔會最終被提交。
這麼做有兩個風險

Store Bufferes 的風險

第一、就是處理器會嘗試從存儲緩存（Store buffer）中讀取值，但它還沒有進行提交。這個的解決方案稱爲 Store Forwarding，它使得加載的時候，如果存儲緩存中存在，則進行返回。
第二、保存什麼時候會完成，這個並沒有任何保證。

value = 3；

void exeToCPUA(){
  value = 10;
  isFinsh = true;
}
void exeToCPUB(){
  if(isFinsh){
    //value一定等於10？！
    assert value == 10;
  }
}

試想一下開始執行時，CPU A 保存着 finished 在 E(獨享) 狀態，而 value 並沒有保存在它的緩存中。（例如，Invalid）。在這種情況下，value 會比 finished 更遲地拋棄存儲緩存。完全有可能 CPU B 讀取 finished 的值爲 true，而 value 的值不等於 10。

即 isFinsh 的賦值在 value 賦值之前。

這種在可識別的行爲中發生的變化稱爲重排序（reordings）。注意，這不意味着你的指令的位置被惡意（或者好意）地更改。

它只是意味着其他的 CPU 會讀到跟程序中寫入的順序不一樣的結果。

順便提一下 NIO 的設計和 Store Bufferes 的設計是非常相像的。

硬件內存模型

執行失效也不是一個簡單的操作，它需要處理器去處理。另外，存儲緩存（Store Buffers）並不是無窮大的，所以處理器有時需要等待失效確認的返回。這兩個操作都會使得性能大幅降低。爲了應付這種情況，引入了失效隊列。它們的約定如下：

即便是這樣處理器已然不知道什麼時候優化是允許的，而什麼時候並不允許。
乾脆處理器將這個任務丟給了寫代碼的人。這就是內存屏障（Memory Barriers）。

寫屏障 Store Memory Barrier(a.k.a. ST, SMB, smp_wmb) 是一條告訴處理器在執行這之後的指令之前，應用所有已經在存儲緩存（store buffer）中的保存的指令。

讀屏障 Load Memory Barrier (a.k.a. LD, RMB, smp_rmb) 是一條告訴處理器在執行任何的加載前，先應用所有已經在失效隊列中的失效操作的指令。

void executedOnCpu0() {
    value = 10;
    //在更新數據之前必須將所有存儲緩存（store buffer）中的指令執行完畢。
    storeMemoryBarrier();
    finished = true;
}
void executedOnCpu1() {
    while(!finished);
    //在讀取之前將所有失效隊列中關於該數據的指令執行完畢。
    loadMemoryBarrier();
    assert value == 10;
}

現在確實安全了。完美無暇！

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/H4dZpCyObYXsiDxPkVh-aA

猜你喜歡