CPU Cache知識(shí)回顧

CPU 的高速緩存，通常可以分為 L1、L2、L3 這樣的三層高速緩存，也稱為一級(jí)緩存、二級(jí)緩存、三級(jí)緩存。

L1 高速緩存訪問(wèn)速度幾乎和寄存器一樣快，大小在幾十 KB 到幾百 KB 不等。每個(gè) CPU 核心都有一塊屬于自己的 L1 高速緩存。

L2 高速緩存同樣每個(gè) CPU 核心都有，但是 L2 高速緩存位置比 L1 高速緩存距離 CPU 核心 更遠(yuǎn)，它大小比 L1 高速緩存更大，CPU 型號(hào)不同大小也就不同，通常大小在幾百 KB 到幾 MB 不等，訪問(wèn)速度則更慢。

L3 高速緩存通常是多個(gè) CPU 核心共用的，位置比 L2 高速緩存距離 CPU 核心 更遠(yuǎn)，大小也會(huì)更大些，通常大小在幾 MB 到幾十 MB 不等。

cpu cache 結(jié)構(gòu)

CPU Cache 是由很多個(gè) Cache Line 組成的，CPU Line 是 CPU 從內(nèi)存讀取數(shù)據(jù)的基本單位，而 CPU Line 是由各種標(biāo)志（Tag）+ 數(shù)據(jù)塊（Data Block）組成，你可以在下圖清晰的看到：

Cpu cache數(shù)據(jù)寫入的兩種方式

多核CPU同時(shí)工作的時(shí)候，每個(gè)核心都會(huì)從內(nèi)存中讀取一份數(shù)據(jù)并緩存到自己的Cache中，當(dāng)發(fā)生寫操作的時(shí)候，有兩種情況

• 寫直達(dá)：只要有數(shù)據(jù)寫入，都會(huì)把數(shù)據(jù)同時(shí)寫入內(nèi)存和 Cache 中，這種方式簡(jiǎn)單直觀，但是性能就會(huì)受限于內(nèi)存的訪問(wèn)速度；
• 寫回：對(duì)于已經(jīng)緩存在 Cache 的數(shù)據(jù)的寫入，只需要更新其數(shù)據(jù)就可以，不用寫入到內(nèi)存，只有在需要把緩存里面的臟數(shù)據(jù)交換出去的時(shí)候，才把數(shù)據(jù)同步到內(nèi)存里，這種方式在緩存命中率高的情況，性能會(huì)更好；

寫直達(dá)

寫回

寫直達(dá)由于每次寫操作都會(huì)把數(shù)據(jù)寫回到內(nèi)存，而導(dǎo)致影響性能，于是為了要減少數(shù)據(jù)寫回內(nèi)存的頻率，就出現(xiàn)了寫回的方法。

• 寫回策略會(huì)在每個(gè) Cache 塊上增加一個(gè) “臟（Dirty）” 標(biāo)記位 ，當(dāng)一個(gè) Cache 被標(biāo)記為臟時(shí)，說(shuō)明它的數(shù)據(jù)與內(nèi)存數(shù)據(jù)是不一致的；
• 在寫入操作時(shí)，我們只需要修改 Cache 塊并將其標(biāo)記為臟，而不需要寫入內(nèi)存；
• 那么，什么時(shí)候才將臟數(shù)據(jù)寫回內(nèi)存呢？—— 就發(fā)生在 Cache 塊被替換出去的時(shí)候：

寫回策略能夠減少寫回內(nèi)存的次數(shù)，性能會(huì)比寫直達(dá)更高。當(dāng)然，寫回策略在讀取的時(shí)候，有可能不是純粹的讀取了，因?yàn)檫€可能會(huì)觸發(fā)一次臟 Cache 塊的寫入。

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

寫回操作-寫入邏輯

寫回操作-讀取邏輯

實(shí)現(xiàn)緩存一致性

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

舉個(gè)例子：

• Core 1 和 Core 2 讀取了同一個(gè)內(nèi)存塊的數(shù)據(jù)，在兩個(gè) Core 都緩存了一份內(nèi)存塊的副本。此時(shí)，Cache 和內(nèi)存塊是一致的；
• Core 1 執(zhí)行內(nèi)存寫入操作：

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

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

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

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

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

緩存一致性機(jī)制需要解決的問(wèn)題就是 2 點(diǎn)：

• 特性 1 - 寫傳播（Write Propagation）： 每個(gè) CPU 核心的寫入操作，需要傳播到其他 CPU 核心；
• 特性 2 - 事務(wù)串行化（Transaction Serialization）： 各個(gè) CPU 核心所有寫入操作的順序，在所有 CPU 核心看起來(lái)是一致。

總線嗅探 & 總線仲裁

寫傳播和事務(wù)串行化在 CPU 中是如何實(shí)現(xiàn)的呢？

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

可以發(fā)現(xiàn)，總線嗅探方法很簡(jiǎn)單， CPU 需要每時(shí)每刻監(jiān)聽總線上的一切活動(dòng)，但是不管別的核心的 Cache 是否緩存相同的數(shù)據(jù)，都需要發(fā)出一個(gè)廣播事件，這無(wú)疑會(huì)加重總線的負(fù)載。

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

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

MESI協(xié)議

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

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

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

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

「獨(dú)占」和「共享」的差別在于，獨(dú)占狀態(tài)的時(shí)候，數(shù)據(jù)只存儲(chǔ)在一個(gè) CPU 核心的 Cache 里，而其他 CPU 核心的 Cache 沒有該數(shù)據(jù)。這個(gè)時(shí)候，如果要向獨(dú)占的 Cache 寫數(shù)據(jù)，就可以直接自由地寫入，而不需要通知其他 CPU 核心，因?yàn)橹挥心氵@有這個(gè)數(shù)據(jù)，就不存在緩存一致性的問(wèn)題了，于是就可以隨便操作該數(shù)據(jù)。

另外，在「獨(dú)占」?fàn)顟B(tài)下的數(shù)據(jù)，如果有其他核心從內(nèi)存讀取了相同的數(shù)據(jù)到各自的 Cache ，那么這個(gè)時(shí)候，獨(dú)占狀態(tài)下的數(shù)據(jù)就會(huì)變成共享狀態(tài)。

那么，「共享」?fàn)顟B(tài)代表著相同的數(shù)據(jù)在多個(gè) CPU 核心的 Cache 里都有，所以當(dāng)我們要更新 Cache 里面的數(shù)據(jù)的時(shí)候，不能直接修改，而是要先向所有的其他 CPU 核心廣播一個(gè)請(qǐng)求，要求先把其他核心的 Cache 中對(duì)應(yīng)的 Cache Line 標(biāo)記為「無(wú)效」?fàn)顟B(tài)，然后再更新當(dāng)前 Cache 里面的數(shù)據(jù)。

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

• 關(guān)鍵 1 - 阻止同時(shí)有多個(gè)核心修改的共享數(shù)據(jù)： 當(dāng)一個(gè) CPU 核心要求修改數(shù)據(jù)時(shí)，會(huì)先廣播 RFO 請(qǐng)求獲得 Cache 塊的所有權(quán)，并將其它 CPU 核心中對(duì)應(yīng)的 Cache 塊置為已失效狀態(tài)；
• 關(guān)鍵 2 - 延遲回寫： 只有在需要的時(shí)候才將數(shù)據(jù)寫回內(nèi)存，當(dāng)一個(gè) CPU 核心要求訪問(wèn)已失效狀態(tài)的 Cache 塊時(shí)，會(huì)先要求其它核心先將數(shù)據(jù)寫回內(nèi)存，再?gòu)膬?nèi)存讀取。

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

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

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

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

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

• 失效隊(duì)列（Invalidation Queue）

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

事實(shí)上，寫緩沖區(qū)和失效隊(duì)列破壞了 Cache 的一致性。

因?yàn)樵谖赐降那闆r下，程序可能會(huì)有多種執(zhí)行順序。這也是為什么Java里還需要volatile關(guān)鍵字，因?yàn)橐雽懢彌_區(qū)或失效隊(duì)列后就變成弱數(shù)據(jù)一致性，不能滿足 強(qiáng)數(shù)據(jù)一致性： 保證在任意時(shí)刻任意副本上的同一份數(shù)據(jù)都是相同的，或者允許不同，但是每次使用前都要刷新確保數(shù)據(jù)一致，所以最終還是一致。

總結(jié)

1. 在 CPU Cache 的三級(jí)緩存中，會(huì)存在 2 個(gè)緩存一致性問(wèn)題：

縱向 - Cache 與內(nèi)存的一致性問(wèn)題： 在修改 Cache 數(shù)據(jù)后，如何同步回內(nèi)存？

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

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

寫直達(dá)策略： 始終保持 Cache 數(shù)據(jù)和內(nèi)存數(shù)據(jù)一致，在每次寫入操作中都會(huì)寫入內(nèi)存；

寫回策略： 只有在臟 Cache 塊被替換出去的時(shí)候?qū)懟貎?nèi)存，減少寫回內(nèi)存的次數(shù)；

3. 多核心 Cache 一致性問(wèn)題需要滿足 2 點(diǎn)特性：

寫傳播（總線嗅探）： 每個(gè) CPU 核心的寫入操作，需要傳播到其他 CPU 核心；

事務(wù)串行化（總線仲裁）： 各個(gè) CPU 核心所有寫入操作的順序，在所有 CPU 核心看起來(lái)是一致。

4. MESI 協(xié)議能夠滿足以上 2 點(diǎn)特性，通過(guò) “已修改、獨(dú)占、共享、已失效” 4 個(gè)狀態(tài)實(shí)現(xiàn)了 CPU Cache 的一致性；
5. 現(xiàn)代 CPU 為了提高并行度，會(huì)在增加 寫緩沖區(qū) & 失效隊(duì)列 將 MESI 協(xié)議的請(qǐng)求異步化， 從內(nèi)存的視角看就是指令重排，破壞了 CPU Cache 的一致性。也是為什么使用volatile關(guān)鍵字的原因