CPU Cache是如何保證緩存一致性的？

單核CPU

我們介紹CPU Cache的組織架構(gòu)及其進(jìn)行讀操作時(shí)的尋址方式，但是緩存不僅僅只有讀操作，還有 寫(xiě)操作 ，這會(huì)帶來(lái)一個(gè)新的問(wèn)題：

當(dāng)CPU是單核的情況下，CPU執(zhí)行寫(xiě)入數(shù)據(jù)操作，當(dāng)數(shù)據(jù)寫(xiě)入CPU Cache之后，此時(shí)CPU Cache數(shù)據(jù)會(huì)和內(nèi)存數(shù)據(jù)就不一致了(這里前提條件：CPU Cache數(shù)據(jù)和內(nèi)存數(shù)據(jù)原本是一致的)，那么如何保證Cache和內(nèi)存保持?jǐn)?shù)據(jù)一致？

主要有兩種寫(xiě)入數(shù)據(jù)的策略：

1. Write Through寫(xiě)直達(dá)
2. Write Back寫(xiě)回

Write Through寫(xiě)直達(dá)

Write Through寫(xiě)直達(dá)是一個(gè)比較簡(jiǎn)單的寫(xiě)入策略，顧名思義就是每次CPU執(zhí)行寫(xiě)操作，如果 緩存命中 ，將數(shù)據(jù)更新到緩存，同時(shí)將數(shù)據(jù)更新到內(nèi)存中，來(lái)保證Cache 數(shù)據(jù)和內(nèi)存數(shù)據(jù)一致；如果緩存沒(méi)有命中，就直接更新內(nèi)存

這個(gè)策略優(yōu)點(diǎn)是簡(jiǎn)單可靠，但是速度較慢，可以從上圖看出，每次寫(xiě)操作都需要與內(nèi)存接觸，此時(shí)緩存失去意義了，當(dāng)然讀操作時(shí)緩存還是能起作用的

Write Back寫(xiě)回

Write Back寫(xiě)回，也被稱為 延遲寫(xiě)入 ，相比于Write Through寫(xiě)直達(dá)策略每次寫(xiě)操作都需要內(nèi)存參與；而Write Back策略則是，CPU向緩存寫(xiě)入數(shù)據(jù)時(shí)，只是把 更新的cache區(qū)標(biāo)記為dirty臟 （即Cache Line增加 dirty臟 的標(biāo)記位 ** ），即來(lái)表示該Cache Line的數(shù)據(jù)，和內(nèi)存中的數(shù)據(jù)是不一致的， 并不同步寫(xiě)入內(nèi)存**

也就是說(shuō)對(duì)內(nèi)存的寫(xiě)入操作會(huì)被 推遲 ，直到當(dāng)這個(gè)Cache Line要被刷入新的數(shù)據(jù)時(shí)，才將Cache Line的數(shù)據(jù)回寫(xiě)到內(nèi)存中

如今CPU Cache更多地采用write back寫(xiě)回的方式，寫(xiě)回的核心就是盡可能減少回寫(xiě)內(nèi)存的次數(shù)，來(lái)提升CPU性能，缺點(diǎn)就是實(shí)現(xiàn)起來(lái)比較復(fù)雜

我們來(lái)看下它的具體流程是：當(dāng)CPU發(fā)起寫(xiě)入操作請(qǐng)求時(shí)，如果緩存命中，就直接更新 CPU Cache 里面的數(shù)據(jù)，并把更新的Cache區(qū)標(biāo)記為dirty臟

若緩存未命中的話，再判斷緩存區(qū)已滿或者定位到的Cache Line已被占用，緩存就會(huì)執(zhí)行 替換策略 ，常見(jiàn)的策略有：隨機(jī)替換RR、先進(jìn)先出FIFO、最近最少使用LRU等，我們后文再詳細(xì)介紹；

當(dāng)被替換的Cache Line被標(biāo)記為臟，也就是該Cache Line的數(shù)據(jù)，和內(nèi)存中的數(shù)據(jù)是不一致的，此時(shí)會(huì)觸發(fā)操作： 將Cache Line中的數(shù)據(jù)回寫(xiě)到內(nèi)存中 ；然后，再把當(dāng)前要寫(xiě)入的數(shù)據(jù)，寫(xiě)入到 Cache里，同時(shí)把Cache Line標(biāo)記成臟

如果Cache Line的數(shù)據(jù)沒(méi)有被標(biāo)記成臟的、緩存區(qū)未滿、定位到的Cache Line未被占用，那么直接把數(shù)據(jù)寫(xiě)入到 Cache 里面，同時(shí)把Cache Line標(biāo)記成臟

結(jié)束或者可以說(shuō)是等待下一次CPU請(qǐng)求

常見(jiàn)的內(nèi)存替換策略

RR

隨機(jī)替換 (Random Replacement，RR) ，顧名思義就是隨機(jī)選擇被替換的緩存塊

實(shí)現(xiàn)簡(jiǎn)單，在緩存大小較大時(shí)表現(xiàn)良好，能夠減少緩存替換的次數(shù)，提高緩存命中率

但是沒(méi)有利用 “局部性原理”，無(wú)法提高緩存命中率；且算法性能不穩(wěn)定，在緩存大小較小時(shí)，隨機(jī)替換可能導(dǎo)致頻繁的緩存替換，降低了緩存的命中率

FIFO

先進(jìn)先出（First-In-First-Out, FIFO），根據(jù)數(shù)據(jù)進(jìn)入緩存的順序，每次將最早進(jìn)入緩存的數(shù)據(jù)先出去，也就是先進(jìn)入緩存的數(shù)據(jù)先被淘汰。

實(shí)現(xiàn)簡(jiǎn)單，適合短期的緩存數(shù)據(jù)；但不合適長(zhǎng)期存儲(chǔ)數(shù)據(jù)的場(chǎng)景，緩存中的數(shù)據(jù)可能早已經(jīng)過(guò)時(shí)；當(dāng)緩存大小不足時(shí)，容易產(chǎn)生替換過(guò)多的情況，從而降低了緩存的效率

FIFO 算法 存在Belady貝萊迪現(xiàn)象 ： 在某些情況下，緩存容量增大，命中率反而降低 。概率比較小，但是危害是無(wú)限的

貝萊迪在1969年研究FIFO算法時(shí)，發(fā)現(xiàn)了一個(gè)反例，使用4個(gè)頁(yè)框時(shí)的缺頁(yè)次數(shù)比3個(gè)頁(yè)框時(shí)的缺頁(yè)多，由于在同一時(shí)刻，使用4個(gè)頁(yè)框時(shí)緩存中保存的頁(yè)面并不完全包含使用3個(gè)頁(yè)框時(shí)保存的頁(yè)面，二者不是超集子集關(guān)系，造成都某些特殊的頁(yè)面請(qǐng)求序列，4個(gè)頁(yè)框命中率反而低

下圖引用于：Memory management and Virtual memory

LRU

最近最少使用 (Least-Recently-Used，LRU)，記錄各個(gè) Cache 塊的歷史訪問(wèn)記錄， 最近最少使用的塊最先被替換 。LRU 策略利用了局部性原理，來(lái)提高緩存命中率：如果一個(gè)數(shù)據(jù)在最近一段時(shí)間內(nèi)沒(méi)有被訪問(wèn)，那么它在未來(lái)被訪問(wèn)的概率也相對(duì)較低，可以考慮將其替換出緩存，以便為后續(xù)可能訪問(wèn)的數(shù)據(jù)騰出緩存空間

實(shí)現(xiàn)簡(jiǎn)單，適用于大多數(shù)場(chǎng)景，盡可能地保留最常用的數(shù)據(jù)，提高緩存的命中率；但是當(dāng)緩存大小達(dá)到一定閾值時(shí)，需要清除舊數(shù)據(jù)，如果清除不當(dāng)可能會(huì)導(dǎo)致性能下降；且無(wú)法保證最佳性能，可能會(huì)出現(xiàn)緩存命中率不高的情況

LRU 不會(huì)出現(xiàn) Belady 現(xiàn)象，因?yàn)槿萘扛【彺嬷械臄?shù)據(jù)集合始終是容量更大緩存中數(shù)據(jù)集合的子集

下圖來(lái)源于：LRU and LFU Cache Algorithms

當(dāng)然還有許多其他算法，比如LFU、2Q、MQ、ARC等等，大家感興趣地可以自行去了解

多核CPU

上述都是單核CPU的情況，但如今CPU都是多核的，由于每個(gè)核心都獨(dú)占的 Cache(L1，L2)，就會(huì)存在當(dāng)一個(gè)核心修改數(shù)據(jù)后，另外核心Cache中數(shù)據(jù)不一致的問(wèn)題，那又該如何保證緩存一致性呢？

這個(gè)時(shí)候，單核情況下的寫(xiě)直達(dá)策略還是寫(xiě)回策略都無(wú)法解決一致性的問(wèn)題，那么我們需要一種全新的機(jī)制來(lái)保證緩存一致性

多核CPU緩存一致性主要有2種策略：基于總線監(jiān)聽(tīng)的一致性策略 和 基于目錄的一致性策略

基于總線監(jiān)聽(tīng)的一致性策略

基于總線監(jiān)聽(tīng)的一致性策略，也叫 總線嗅探 （Bus Snooping），它的工作原理是：

1. 當(dāng)有一個(gè)CPU核心修改了Cache中的值，會(huì)通過(guò)總線把這個(gè)事件廣播給其他所有的核心；
2. 而每個(gè)CPU核心都會(huì)去監(jiān)聽(tīng)總線中的數(shù)據(jù)廣播，并檢測(cè)是否有相同數(shù)據(jù)的副本，在本核心的Cache中；如果有副本，就執(zhí)行相應(yīng)操作來(lái)確保多核心的緩存一致性

其中將相應(yīng)操作傳播到所有擁有該Cache副本的核心中時(shí)，一般有2種處理辦法：

• write-update寫(xiě)更新協(xié)議：某個(gè)Cache發(fā)生寫(xiě)操作，就傳播所有核心中Cache都更新該數(shù)據(jù)副本，由于需要把對(duì)應(yīng)的數(shù)據(jù)傳輸給其他CPU核心，所以該策略成本較高
• write-invalidate寫(xiě)失效協(xié)議：某個(gè)Cache發(fā)生寫(xiě)操作，就把其他Cache中的該數(shù)據(jù)副本置為 無(wú)效 ，這樣CPU 只需也只能讀取和寫(xiě)入數(shù)據(jù)的其中一個(gè)副本 ，因?yàn)槠渌诵牡木彺嬷性摂?shù)據(jù)副本都已經(jīng)無(wú)效的。這也是最常用的監(jiān)聽(tīng)協(xié)議

基于目錄的一致性策略

基于目錄的一致性策略會(huì)維護(hù)一個(gè)數(shù)據(jù)結(jié)構(gòu)，叫做 目錄 （directory-based），保存著緩存中不同數(shù)據(jù)副本寫(xiě)入哪些Cache及其對(duì)應(yīng)的狀態(tài)等相關(guān)信息；

當(dāng)CPU執(zhí)行寫(xiě)操作時(shí)，不會(huì)再向所有核心的Cache進(jìn)行廣播，而是是通過(guò)此目錄來(lái)跟蹤所有緩存中數(shù)據(jù)副本的狀態(tài)，來(lái)僅將其發(fā)送到指定的數(shù)據(jù)副本中；這樣相比總線嗅探節(jié)省大量總線流量，更具有擴(kuò)展性

它又分為SI，MSI，MESI策略，我們這里主要介紹MESI協(xié)議

MESI協(xié)議

MESI協(xié)議是一個(gè)基于失效的緩存?致性協(xié)議，通過(guò)總線嗅探來(lái)處理多個(gè)核心之間的數(shù)據(jù)傳播，同時(shí)也用 目錄狀態(tài)機(jī)制 ，來(lái)降低了總線帶寬壓力。

所謂緩存一致性是指：通過(guò)在緩存之間做同步，達(dá)到仿佛系統(tǒng)不存在緩存時(shí)的行為。一般有 如下要求：

• Write Propagation寫(xiě)傳播：在一個(gè)CPU核心里，Cache Line數(shù)據(jù)更新，能夠傳播到其他核心的對(duì)應(yīng)的Cache Line里
• Transaction Serialization事務(wù)順序化：在一個(gè)CPU核心里面的讀寫(xiě)操作，不管這些指令最終的先后順序如何，但在其他的核心看起來(lái)，順序要一樣的。

這也對(duì)應(yīng)我們常說(shuō)的并發(fā)可見(jiàn)性和順序性~

四大狀態(tài)

MESI名字中，"M", "E", "S", "I"這4個(gè)字母分別代表了Cache Line的四種狀態(tài)(存放再Cache Line)，分別是：

1. M：代表已修改（Modified），表明Cache Line被修改過(guò)，但未同步回內(nèi)存(就是上面我們說(shuō)的臟數(shù)據(jù))
2. E：代表獨(dú)占（Exclusive），表明 Cache Line被當(dāng)前核心獨(dú)占，和內(nèi)存中的數(shù)據(jù)一致(數(shù)據(jù)是干凈的)
3. S：代表共享（Shared），表明Cache Line被多個(gè)核心共享，且數(shù)據(jù)是干凈的
4. I：代表已失效（Invalidated），表明Cache Line的數(shù)據(jù)是失效的，數(shù)據(jù)未加載或緩存已失效

下圖來(lái)源于：https://en.wikipedia.org/wiki/MESI_protocol

上圖圖中，紅色表示總線初始化事件，黑色表示處理器初始化事件， MESI其實(shí)是一個(gè)有限狀態(tài)機(jī) ，狀態(tài)轉(zhuǎn)換主要有2種場(chǎng)景，緩存所在處理器的讀寫(xiě)、其他處理器的讀寫(xiě)。

下面我們一起來(lái)看看這2種場(chǎng)景分別有哪些事件：

事件

處理器CPU對(duì)緩存的請(qǐng)求,也就是讀寫(xiě)操作:

1. PrRd: 處理器請(qǐng)求讀一個(gè)緩存塊
2. PrWr: 處理器請(qǐng)求寫(xiě)一個(gè)緩存塊

同步的信息通過(guò)總線傳遞，同步信號(hào)(總線對(duì)緩存的請(qǐng)求)有下面5種:

1. BusRd: 總線窺探器收到其他處理器請(qǐng)求讀一個(gè)緩存塊(總線的請(qǐng)求被總線窺探器監(jiān)視)
2. BusRdX: 窺探器請(qǐng)求指出其他處理器請(qǐng)求寫(xiě)一個(gè)該處理器不擁有的緩存塊
3. BusUpgr: 窺探器請(qǐng)求指出其他處理器請(qǐng)求寫(xiě)一個(gè)該處理器擁有的緩存塊
4. Flush: 窺探器請(qǐng)求指出請(qǐng)求回寫(xiě)整個(gè)緩存到主存
5. FlushOpt: 窺探器請(qǐng)求指出整個(gè)緩存塊被發(fā)到總線以發(fā)送給另外一個(gè)處理器（和 Flush 類似，但是緩存到緩存的復(fù)制)

狀態(tài)標(biāo)記關(guān)系

下圖是mesi的狀態(tài)標(biāo)記圖，表示當(dāng)一個(gè)Cache Line的調(diào)整的狀態(tài)的時(shí)候，另外一個(gè)Cache Line能夠調(diào)整的對(duì)應(yīng)狀態(tài)

舉個(gè)例子，假如Cache 1 中存放變量x = 0的Cache Line處于S狀態(tài)(共享)；那么其他擁有x變量的Cache 2、Cache 3等Cache x的Cache line只能調(diào)整為S狀態(tài)（共享）或調(diào)整為 I 狀態(tài)（無(wú)效）

狀態(tài)轉(zhuǎn)化過(guò)程

結(jié)合上面MESI各個(gè)狀態(tài)含義以及事件，我們?cè)賮?lái)詳細(xì)看看狀態(tài)流轉(zhuǎn)與事件的關(guān)系：

Store buffer

如果嚴(yán)格按照MESI協(xié)議，某一個(gè)核心A在寫(xiě)入Invalid狀態(tài)的緩存時(shí)，需要向其他核心廣播RFO獲得獨(dú)占權(quán)；當(dāng)其它 CPU 的Cache Line收到消息后，使他們對(duì)應(yīng)的緩存副本失效，并返回 Invalid acknowledgement 消息；直到這個(gè)核心A收到消息才能修改緩存，期間當(dāng)前核心只能空等待，這對(duì)于CPU來(lái)說(shuō)很浪費(fèi)

整個(gè)過(guò)程有較長(zhǎng)的延時(shí)，比較緩慢，一般緩存會(huì)通過(guò) Store Buffer寫(xiě)緩沖區(qū)和 Invalidate Queue失效隊(duì)列機(jī)制來(lái)進(jìn)一步優(yōu)化

引入Store Buffer后，當(dāng)核心寫(xiě)入緩存時(shí)，直接寫(xiě)入Store Buffer，當(dāng)前核心無(wú)需等待，繼續(xù)處理其他事情； 由Store Buffer接手后續(xù)工作 ，由Store Buffer向其他核心廣播RFO獲得獨(dú)占權(quán)，等收到 ACK 后再將修改緩存上。

但是它會(huì)導(dǎo)致，雖然核心A以為某個(gè)修改寫(xiě)入緩存了，但其實(shí)還在Store buffer里。此時(shí)如果要讀數(shù)據(jù)，則需要先掃描 Store buffer，另外其它核心在數(shù)據(jù)真正寫(xiě)入緩存之前是看不到這次寫(xiě)入的

Invalidate Queue

對(duì)于其它的CPU核心而言，在其收到RFO請(qǐng)求時(shí)，需要更新本地的Cache Line狀態(tài)，并回復(fù)Invalid acknowledgement消息。然而在收到RFO請(qǐng)求時(shí)，CPU核心可能在處理其它的事情，無(wú)法及時(shí)回復(fù)。這就會(huì)導(dǎo)致當(dāng)前核心A在等待回復(fù)過(guò)來(lái)的Invalid acknowledgement消息

引入Invalidate Queue后，收到Invalid消息的核心會(huì)立刻返回Invalid acknowledgement消息，然后把 Invalid 消息加入 Invalidate Queue ，等到空閑的時(shí)候再去處理 Invalid 消息

但是它也會(huì)導(dǎo)致，此時(shí)核心A可能以為其他核心的緩存已經(jīng)失效，但真的嘗試讀取時(shí)，緩存還沒(méi)有置為Invalid狀態(tài)，于是有可能讀到舊的數(shù)據(jù)

內(nèi)存屏障

Store Buffer是對(duì)MESI發(fā)生寫(xiě)操作命令的優(yōu)化，而Invalidate Queue則是對(duì)接受寫(xiě)操作命令時(shí)的優(yōu)化

這些優(yōu)化，雖然提高了CPU的緩存利用率，但也會(huì)帶來(lái)各自的問(wèn)題，所以引入了 內(nèi)存屏障 ，筆者之前在寫(xiě)Java關(guān)鍵字volatile也提及過(guò)

內(nèi)存屏障又可以細(xì)分為：寫(xiě)屏障和讀屏障

1. 這里插入store buffer寫(xiě)屏障，內(nèi)存屏障會(huì)強(qiáng)制將 store buffer 的數(shù)據(jù)寫(xiě)到緩存中，這樣保證數(shù)據(jù)寫(xiě)到了所有的緩存里；
2. 插入 read barrier讀屏障 會(huì)保證 invalidate queue 的請(qǐng)求都已經(jīng)被處理，這樣其它 CPU 的修改都已經(jīng)對(duì)當(dāng)前 CPU可見(jiàn)