前言

大家好，我是小彭。

在上一篇文章里，我們聊到了 CPU 的三級緩存結(jié)構(gòu)，提到 CPU 緩存就一定會聊到 CPU 的緩存一致性問題。那么，什么是緩存一致性問題，CPU Cache 的讀取和寫入過程是如何執(zhí)行的，MESI 緩存一致性協(xié)議又是什么？今天我們將圍繞這些問題展開。

學(xué)習(xí)路線圖：

1. 回顧 CPU 三級緩存結(jié)構(gòu)

由于 CPU 和內(nèi)存的速度差距太大，為了拉平兩者的速度差，現(xiàn)代計算機會在兩者之間插入一塊速度比內(nèi)存更快的高速緩存，CPU 緩存是分級的，有 L1 / L2 / L3 三級緩存。

由于單核 CPU 的性能遇到瓶頸（主頻與功耗的矛盾），芯片廠商開始在 CPU 芯片里集成多個 CPU 核心，每個核心有各自的 L1 / L2 緩存。 其中 L1 / L2 緩存是核心獨占的，而 L3 緩存是多核心共享的。

基于局部性原理的應(yīng)用，CPU Cache 在讀取內(nèi)存數(shù)據(jù)時，每次不會只讀一個字或一個字節(jié)，而是一塊塊地讀取，每一小塊數(shù)據(jù)也叫 CPU 緩存行（CPU Cache Line）。 為了標(biāo)識 Cache 塊中的數(shù)據(jù)是否已經(jīng)從內(nèi)存中讀取，需要在 Cache 塊上增加一個 有效位（Valid bit）。

無論對 Cache 數(shù)據(jù)檢查、讀取還是寫入，CPU 都需要知道訪問的內(nèi)存數(shù)據(jù)映射在 Cache 上的哪個位置，這就是 Cache - 內(nèi)存地址映射問題，映射方案有直接映射、全相聯(lián)映射和組相聯(lián)映射 3 種方案。當(dāng)緩存塊滿或者內(nèi)存塊映射的緩存塊位置被占用時，就需要使用 替換策略 將舊的 Cache 塊換出騰出空閑位置。

Cache - 內(nèi)存的直接映射方案

基于以上結(jié)構(gòu)，就會存在緩存一致性問題。

2. 什么是 CPU 緩存一致性問題？

CPU 緩存一致性（Cache Coherence）問題指 CPU Cache 與內(nèi)存的不一致性問題。事實上， 在分析緩存一致性問題時，考慮 L1 / L2 / L3 的多級緩存沒有意義， 所以我們提出緩存一致性抽象模型，只考慮核心獨占的緩存。

CPU 三級緩存與抽象模型

在單核 CPU 中，只需要考慮 Cache 與內(nèi)存的一致性。但是在多核 CPU 中，由于每個核心都有一份獨占的 Cache，就會存在一個核心修改數(shù)據(jù)后，兩個核心 Cache 數(shù)據(jù)不一致的問題。因此，我認(rèn)為 CPU 的緩存一致性問題應(yīng)該從 2 個維度理解：

• 縱向：Cache 與內(nèi)存的一致性問題： 在修改 Cache 數(shù)據(jù)后，如何同步回內(nèi)存？
• 橫向：多核心 Cache 的一致性問題： 在一個核心修改 Cache 數(shù)據(jù)后，如何同步給其他核心 Cache？

接下來，我們將圍繞這兩個問題展開。

3. 縱向：Cache 與內(nèi)存的一致性問題

3.1 CPU Cache 的讀取過程

這一節(jié)，我們先來討論 Cache 的讀取過程。事實上，Cache 的讀取過程會受到 Cache 的寫入策略影響，我們暫且用相對簡單的 “寫直達策略” 的讀取過程：

• 1、CPU 在訪問內(nèi)存地址時，會先檢查該地址的數(shù)據(jù)是否已經(jīng)加載到 Cache 中（Valid bit 是否為 1）；

• 2、如果數(shù)據(jù)在 Cache 中，則直接讀取 Cache 塊上的字到 CPU 中；

• 3、如果數(shù)據(jù)不在 Cache 中：

  • 3.1 如果 Cache 已裝滿或者 Cache 塊被占用，先執(zhí)行替換策略，騰出空閑位置；
  • 3.2 訪問內(nèi)存地址，并將內(nèi)存地址所處的整個內(nèi)存塊寫入到映射的 Cache 塊中；
  • 3.3 讀取 Cache 塊上的字到 CPU 中。

讀取過程（以寫直達策略）

但是，CPU 不僅會讀取 Cache 數(shù)據(jù)，還會修改 Cache 數(shù)據(jù)，這就是第 1 個一致性問題 —— 在修改 Cache 數(shù)據(jù)后，如何同步回內(nèi)存？有 2 種寫入策略：

3.2 寫直達策略（Write-Through）

寫直達策略是解決 Cache 與內(nèi)存一致性最簡單直接的方式： 在每次寫入操作中，同時修改 Cache 數(shù)據(jù)和內(nèi)存數(shù)據(jù)，始終保持 Cache 數(shù)據(jù)和內(nèi)存數(shù)據(jù)一致：

• 1、如果數(shù)據(jù)不在 Cache 中，則直接將數(shù)據(jù)寫入內(nèi)存；
• 2、如果數(shù)據(jù)已經(jīng)加載到 Cache 中，則不僅要將數(shù)據(jù)寫入 Cache，還要將數(shù)據(jù)寫入內(nèi)存。

寫直達的優(yōu)點和缺點都很明顯：

• 優(yōu)點： 每次讀取操作就是純粹的讀取，不涉及對內(nèi)存的寫入操作，讀取速度更快；
• 缺點： 每次寫入操作都需要同時寫入 Cache 和寫入內(nèi)存，在寫入操作上失去了 CPU 高速緩存的價值，需要花費更多時間。

寫直達策略

3.3 寫回策略（Write-Back）

既然寫直達策略在每次寫入操作都會寫內(nèi)存，那么有沒有什么辦法可以減少寫回內(nèi)存的次數(shù)呢？這就是寫回策略：

• 1、寫回策略會在每個 Cache 塊上增加一個 “臟（Dirty）” 標(biāo)記位 ，當(dāng)一個 Cache 被標(biāo)記為臟時，說明它的數(shù)據(jù)與內(nèi)存數(shù)據(jù)是不一致的；

• 2、在寫入操作時，我們只需要修改 Cache 塊并將其標(biāo)記為臟，而不需要寫入內(nèi)存；

• 3、那么，什么時候才將臟數(shù)據(jù)寫回內(nèi)存呢？—— 就發(fā)生在 Cache 塊被替換出去的時候：

  • 3.1 在寫入操作中，如果目標(biāo)內(nèi)存塊不在 Cache 中，需要先將內(nèi)存塊數(shù)據(jù)讀取到 Cache 中。如果替換策略換出的舊 Cache 塊是臟的，就會觸發(fā)一次寫回內(nèi)存操作；
  • 3.2 在讀取操作中，如果目標(biāo)內(nèi)存塊不在 Cache 中，且替換策略換出的舊 Cache 塊是臟的，就會觸發(fā)一次寫回內(nèi)存操作；

可以看到，寫回策略只有當(dāng)一個 Cache 數(shù)據(jù)將被替換出去時判斷數(shù)據(jù)的狀態(tài)，“清（未修改過，數(shù)據(jù)與內(nèi)存一致）” 的 Cache 塊不需要寫回內(nèi)存，“臟” 的 Cache 塊才需要寫回內(nèi)存。這個策略能夠減少寫回內(nèi)存的次數(shù)，性能會比寫直達更高。當(dāng)然，寫回策略在讀取的時候，有可能不是純粹的讀取了，因為還可能會觸發(fā)一次臟 Cache 塊的寫入。

這里還有一個設(shè)計： 在目標(biāo)內(nèi)存塊不在 Cache 中時，寫直達策略會直接寫入內(nèi)存。而寫回策略會先把數(shù)據(jù)讀取到 Cache 中再修改 Cache 數(shù)據(jù)，這似乎有點多余？其實還是為了減少寫回內(nèi)存的次數(shù)。雖然在未命中時會增加一次讀取操作，但后續(xù)重復(fù)的寫入都能命中緩存。否則，只要一直不讀取數(shù)據(jù)，寫回策略的每次寫入操作還是需要寫入內(nèi)存。

寫回策略

通過寫直達或?qū)懟夭呗?，我們已?jīng)能夠解決 “在修改 Cache 數(shù)據(jù)后，如何同步回內(nèi)存” 的問題。接下來，我們來討論第 2 個緩存一致性問題 —— 在一個核心修改 Cache 數(shù)據(jù)后，如何同步給其他核心 Cache？

4. 橫向：多核心 Cache 的一致性問題

在單核 CPU 中，我們通過寫直達策略或?qū)懟夭呗员３至薈ache 與內(nèi)存的一致性。但是在多核 CPU 中，由于每個核心都有一份獨占的 Cache，就會存在一個核心修改數(shù)據(jù)后，兩個核心 Cache 不一致的問題。

舉個例子：

• 1、Core 1 和 Core 2 讀取了同一個內(nèi)存塊的數(shù)據(jù)，在兩個 Core 都緩存了一份內(nèi)存塊的副本。此時，Cache 和內(nèi)存塊是一致的；

• 2、Core 1 執(zhí)行內(nèi)存寫入操作：

  • 2.1 在寫直達策略中，新數(shù)據(jù)會直接寫回內(nèi)存，此時，Cache 和內(nèi)存塊一致。但由于之前 Core 2 已經(jīng)讀過這塊數(shù)據(jù)，所以 Core 2 緩存的數(shù)據(jù)還是舊的。此時，Core 1 和 Core 2 不一致；

  • 2.2 在寫回策略中，新數(shù)據(jù)會延遲寫回內(nèi)存，此時 Cache 和內(nèi)存塊不一致。不管 Core 2 之前有沒有讀過這塊數(shù)據(jù)，Core 2 的數(shù)據(jù)都是舊的。此時，Core 1 和 Core 2 不一致。

• 3、由于 Core 2 無法感知到 Core 1 的寫入操作，如果繼續(xù)使用過時的數(shù)據(jù)，就會出現(xiàn)邏輯問題。

多核 Cache 不一致

可以看到：由于兩個核心的工作是獨立的，在一個核心上的修改行為不會被其它核心感知到，所以不管 CPU 使用寫直達策略還是寫回策略，都會出現(xiàn)緩存不一致問題。 所以，我們需要一種機制，將多個核心的工作聯(lián)合起來，共同保證多個核心下的 Cache 一致性，這就是緩存一致性機制。

4.1 寫傳播 & 事務(wù)串行化

緩存一致性機制需要解決的問題就是 2 點：

• 特性 1 - 寫傳播（Write Propagation）： 每個 CPU 核心的寫入操作，需要傳播到其他 CPU 核心；

• 特性 2 - 事務(wù)串行化（Transaction Serialization）： 各個 CPU 核心所有寫入操作的順序，在所有 CPU 核心看起來是一致。

第 1 個特性解決了 “感知” 問題，如果一個核心修改了數(shù)據(jù)，就需要同步給其它核心，很好理解。但只做到同步還不夠，如果各個核心收到的同步信號順序不一致，那最終的同步結(jié)果也會不一致。

舉個例子：假如 CPU 有 4 個核心，Core 1 將共享數(shù)據(jù)修改為 1000，隨后 Core 2 將共享數(shù)據(jù)修改為 2000。在寫傳播下，“修改為 1000” 和 “修改為 2000” 兩個事務(wù)會同步到 Core 3 和 Core 4。但是，如果沒有事務(wù)串行化，不同核心收到的事務(wù)順序可能是不同的，最終數(shù)據(jù)還是不一致。

非事務(wù)串行化

4.2 總線嗅探 & 總線仲裁

寫傳播和事務(wù)串行化在 CPU 中是如何實現(xiàn)的呢？—— 此處隆重請出計算機總線系統(tǒng)。

• 寫傳播 - 總線嗅探： 總線除了能在一個主模塊和一個從模塊之間傳輸數(shù)據(jù)，還支持一個主模塊對多個從模塊寫入數(shù)據(jù)，這種操作就是廣播。要實現(xiàn)寫傳播，其實就是將所有的讀寫操作廣播到所有 CPU 核心，而其它 CPU 核心時刻監(jiān)聽總線上的廣播，再修改本地的數(shù)據(jù)；

• 事務(wù)串行化 - 總線仲裁： 總線的獨占性要求同一時刻最多只有一個主模塊占用總線，天然地會將所有核心對內(nèi)存的讀寫操作串行化。如果多個核心同時發(fā)起總線事務(wù)，此時總線仲裁單元會對競爭做出仲裁，未獲勝的事務(wù)只能等待獲勝的事務(wù)處理完成后才能執(zhí)行。

提示： 寫傳播還有 “基于目錄（Directory-base）” 的實現(xiàn)方案。

基于總線嗅探和總線仲裁，現(xiàn)代 CPU 逐漸形成了各種緩存一致性協(xié)議，例如 MESI 協(xié)議。

4.3 MESI 協(xié)議

MESI 協(xié)議其實是 CPU Cache 的有限狀態(tài)機，一共有 4 個狀態(tài)（MESI 就是狀態(tài)的首字母）：

• M（Modified，已修改）： 表明 Cache 塊被修改過，但未同步回內(nèi)存；
• E（Exclusive，獨占）： 表明 Cache 塊被當(dāng)前核心獨占，而其它核心的同一個 Cache 塊會失效；
• S（Shared，共享）： 表明 Cache 塊被多個核心持有且都是有效的；
• I（Invalidated，已失效）： 表明 Cache 塊的數(shù)據(jù)是過時的。

在 “獨占” 和 “共享” 狀態(tài)下，Cache 塊的數(shù)據(jù)是 “清” 的，任何讀取操作可以直接使用 Cache 數(shù)據(jù)；

在 “已失效” 和 “已修改” 狀態(tài)下，Cache 塊的數(shù)據(jù)是 “臟” 的，它們和內(nèi)存的數(shù)據(jù)都可能不一致。在讀取或?qū)懭?“已失效” 數(shù)據(jù)時，需要先將其它核心 “已修改” 的數(shù)據(jù)寫回內(nèi)存，再從內(nèi)存讀??；

在 “共享” 和 “已失效” 狀態(tài)，核心沒有獲得 Cache 塊的獨占權(quán)（鎖）。在修改數(shù)據(jù)時不能直接修改，而是要先向所有核心廣播 RFO（Request For Ownership）請求 ，將其它核心的 Cache 置為 “已失效”，等到獲得回應(yīng) ACK 后才算獲得 Cache 塊的獨占權(quán)。這個獨占權(quán)這有點類似于開發(fā)語言層面的鎖概念，在修改資源之前，需要先獲取資源的鎖；

在 “已修改” 和 “獨占” 狀態(tài)下，核心已經(jīng)獲得了 Cache 塊的獨占權(quán)（鎖）。在修改數(shù)據(jù)時不需要向總線發(fā)送廣播，能夠減輕總線的通信壓力。

事實上，完整的 MESI 協(xié)議更復(fù)雜，但我們沒必要記得這么細。我們只需要記住最關(guān)鍵的 2 點：

• 關(guān)鍵 1 - 阻止同時有多個核心修改的共享數(shù)據(jù)： 當(dāng)一個 CPU 核心要求修改數(shù)據(jù)時，會先廣播 RFO 請求獲得 Cache 塊的所有權(quán)，并將其它 CPU 核心中對應(yīng)的 Cache 塊置為已失效狀態(tài)；

• 關(guān)鍵 2 - 延遲回寫： 只有在需要的時候才將數(shù)據(jù)寫回內(nèi)存，當(dāng)一個 CPU 核心要求訪問已失效狀態(tài)的 Cache 塊時，會先要求其它核心先將數(shù)據(jù)寫回內(nèi)存，再從內(nèi)存讀取。

提示： MESI 協(xié)議在 MSI 的基礎(chǔ)上增加了 E（獨占）狀態(tài)，以減少只有一份緩存的寫操作造成的總線通信。

MESI 協(xié)議有一個非常 nice 的在線體驗網(wǎng)站，你可以對照文章內(nèi)容，在網(wǎng)站上操作指令區(qū)，并觀察內(nèi)存和緩存的數(shù)據(jù)和狀態(tài)變化。網(wǎng)站地址：https://www.scss.tcd.ie/Jeremy.Jones/VivioJS/caches/MESI.htm

MESI 協(xié)議在線模擬

4.4 寫緩沖區(qū) & 失效隊列

MESI 協(xié)議保證了 Cache 的一致性，但完全地遵循協(xié)議會影響性能。 因此，現(xiàn)代的 CPU 會在增加寫緩沖區(qū)和失效隊列將 MESI 協(xié)議的請求異步化，以提高并行度：

• 寫緩沖區(qū)（Store Buffer）

由于在寫入操作之前，CPU 核心 1 需要先廣播 RFO 請求獲得獨占權(quán)，在其它核心回應(yīng) ACK 之前，當(dāng)前核心只能空等待，這對 CPU 資源是一種浪費。因此，現(xiàn)代 CPU 會采用 “寫緩沖區(qū)” 機制：寫入指令放到寫緩沖區(qū)后并發(fā)送 RFO 請求后，CPU 就可以去執(zhí)行其它任務(wù)，等收到 ACK 后再將寫入操作寫到 Cache 上。

• 失效隊列（Invalidation Queue）

由于其他核心在收到 RFO 請求時，需要及時回應(yīng) ACK。但如果核心很忙不能及時回復(fù)，就會造成發(fā)送 RFO 請求的核心在等待 ACK。因此，現(xiàn)代 CPU 會采用 “失效隊列” 機制：先把其它核心發(fā)過來的 RFO 請求放到失效隊列，然后直接返回 ACK，等當(dāng)前核心處理完任務(wù)后再去處理失效隊列中的失效請求。

寫緩沖區(qū) & 失效隊列

事實上，寫緩沖區(qū)和失效隊列破壞了 Cache 的一致性。 舉個例子：初始狀態(tài)變量 a 和變量 b 都是 0，現(xiàn)在 Core1 和 Core2 分別執(zhí)行這兩段指令，最終 x 和 y 的結(jié)果是什么？

Core1 指令

a = 1; // A1
x = b; // A2

Core2 指令

b = 2; // B1
y = a; // B2

我們知道在未同步的情況下，這段程序可能會有多種執(zhí)行順序。不管怎么執(zhí)行，只要 2 號指令是在 1 號指令后執(zhí)行的，至少 x 或 y 至少一個有值。但是在寫緩沖區(qū)和失效隊列的影響下，程序還有以意料之外的方式執(zhí)行：

上圖。

寫緩沖區(qū)造成指令重排

可以看到：從內(nèi)存的視角看，直到 Core1 執(zhí)行 A3 來刷新寫緩沖區(qū)，寫操作 A1 才算真正執(zhí)行了。雖然 Core 的執(zhí)行順序是 A1 → A2 → B1 → B2，但內(nèi)存看到的順序卻是 A2 → B1 → B2 → A1，變量 a 寫入沒有同步給對變量 a 的讀取，Cache 的一致性被破壞了。

5. 總結(jié)

• 1、在 CPU Cache 的三級緩存中，會存在 2 個緩存一致性問題：

  • 縱向 - Cache 與內(nèi)存的一致性問題： 在修改 Cache 數(shù)據(jù)后，如何同步回內(nèi)存？
  • 橫向 - 多核心 Cache 的一致性問題： 在一個核心修改 Cache 數(shù)據(jù)后，如何同步給其他核心 Cache？

• 2、Cache 與內(nèi)存的一致性問題有 2 個策略：

  • 寫直達策略： 始終保持 Cache 數(shù)據(jù)和內(nèi)存數(shù)據(jù)一致，在每次寫入操作中都會寫入內(nèi)存；
  • 寫回策略： 只有在臟 Cache 塊被替換出去的時候?qū)懟貎?nèi)存，減少寫回內(nèi)存的次數(shù)；

• 3、多核心 Cache 一致性問題需要滿足 2 點特性：

  • 寫傳播（總線嗅探）： 每個 CPU 核心的寫入操作，需要傳播到其他 CPU 核心；
  • 事務(wù)串行化（總線仲裁）： 各個 CPU 核心所有寫入操作的順序，在所有 CPU 核心看起來是一致。

• 4、MESI 協(xié)議能夠滿足以上 2 點特性，通過 “已修改、獨占、共享、已失效” 4 個狀態(tài)實現(xiàn)了 CPU Cache 的一致性；

• 5、現(xiàn)代 CPU 為了提高并行度，會在增加 寫緩沖區(qū) & 失效隊列 將 MESI 協(xié)議的請求異步化， 從內(nèi)存的視角看就是指令重排，破壞了 CPU Cache 的一致性。

今天，我們主要討論了 CPU 的緩存一致性問題與對應(yīng)的緩存一致性協(xié)議。這里有一個問題：既然 CPU 已經(jīng)實現(xiàn)了 MESI 協(xié)議，已經(jīng)在硬件層面實現(xiàn)了寫傳播和事務(wù)串行化，為什么 Java 語言層面還需要定義 volatile 關(guān)鍵字呢？豈不是多此一舉？

你可能會說因為寫緩沖區(qū)和失效隊列破壞了 Cache 一致性。好，那不考慮這個因素的話，還需要定義 volatile 關(guān)鍵字嗎？這個問題我們在 下一篇文章 展開討論，請關(guān)注。

參考資料

• 深入淺出計算機組成原理（第 37、38、39 講） —— 徐文浩 著，極客時間 出品
• 深入理解 Java 虛擬機（第 5 部分） —— 周志明 著
• Java 并發(fā)編程的藝術(shù)（第 1、2、3 章） —— 方騰飛 魏鵬 程曉明 著
• 計算機組成原理教程（第 7 章） —— 尹艷輝 王海文 邢軍 著
• 10 張圖打開 CPU 緩存一致性的大門 —— 小林 Coding 著
• CPU有緩存一致性協(xié)議(MESI)，為何還需要 volatile —— 一角錢技術(shù) 著
• Cache Miss – What It Is and How to Reduce It —— Linda D. 著
• CPU cache —— Wikipedia
• CPU caches —— LWN.net
• Cache coherence —— Wikipedia
• Directory-based cache coherence —— Wikipedia
• MESI protocol —— Wikipedia