單核CPU

我們介紹CPU Cache的組織架構(gòu)及其進行讀操作時的尋址方式，但是緩存不僅僅只有讀操作，還有 寫操作 ，這會帶來一個新的問題：

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

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

1. Write Through寫直達
2. Write Back寫回

Write Through寫直達

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

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

Write Back寫回

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

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

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

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

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

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

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

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

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

RR

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

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

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

FIFO

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

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

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

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

下圖引用于：Memory management and Virtual memory

LRU

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

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

LRU 不會出現(xiàn) Belady 現(xiàn)象，因為容量更小緩存中的數(shù)據(jù)集合始終是容量更大緩存中數(shù)據(jù)集合的子集

下圖來源于：LRU and LFU Cache Algorithms

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

多核CPU

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

這個時候，單核情況下的寫直達策略還是寫回策略都無法解決一致性的問題，那么我們需要一種全新的機制來保證緩存一致性

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

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

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

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

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

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

基于目錄的一致性策略

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

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

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

MESI協(xié)議

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

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

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

這也對應(yīng)我們常說的并發(fā)可見性和順序性~

四大狀態(tài)

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

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

下圖來源于：https://en.wikipedia.org/wiki/MESI_protocol

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

下面我們一起來看看這2種場景分別有哪些事件：

事件

處理器CPU對緩存的請求,也就是讀寫操作:

1. PrRd: 處理器請求讀一個緩存塊
2. PrWr: 處理器請求寫一個緩存塊

同步的信息通過總線傳遞，同步信號(總線對緩存的請求)有下面5種:

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

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

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

舉個例子，假如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)（無效）

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

結(jié)合上面MESI各個狀態(tài)含義以及事件，我們再來詳細看看狀態(tài)流轉(zhuǎn)與事件的關(guān)系：

Store buffer

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

整個過程有較長的延時，比較緩慢，一般緩存會通過 Store Buffer寫緩沖區(qū)和 Invalidate Queue失效隊列機制來進一步優(yōu)化

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

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

Invalidate Queue

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

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

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

內(nèi)存屏障

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

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

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

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