10張圖打開(kāi)CPU緩存一致性的大門(mén)

時(shí)間：2020-10-27 11:57:18

關(guān)鍵字： CPU 計(jì)算機(jī)

手機(jī)看文章

掃描二維碼
隨時(shí)隨地手機(jī)看文章

[導(dǎo)讀]隨著時(shí)間的推移，CPU和內(nèi)存的訪問(wèn)性能相差越來(lái)越大，于是就在CPU內(nèi)部嵌入了CPU Cache（高速緩存），CPU Cache離CPU核心相當(dāng)近，因此它的訪問(wèn)速度是很快的，于是它充當(dāng)了CPU與內(nèi)存之間的緩存角色。

前言

直接上，不多 BB 了。

正文

CPU Cache 的數(shù)據(jù)寫(xiě)入

隨著時(shí)間的推移，CPU 和內(nèi)存的訪問(wèn)性能相差越來(lái)越大，于是就在 CPU 內(nèi)部嵌入了 CPU Cache（高速緩存），CPU Cache 離 CPU 核心相當(dāng)近，因此它的訪問(wèn)速度是很快的，于是它充當(dāng)了 CPU 與內(nèi)存之間的緩存角色。

CPU Cache 通常分為三級(jí)緩存：L1 Cache、L2 Cache、L3 Cache，級(jí)別越低的離 CPU 核心越近，訪問(wèn)速度也快，但是存儲(chǔ)容量相對(duì)就會(huì)越小。其中，在多核心的 CPU 里，每個(gè)核心都有各自的 L1/L2 Cache，而 L3 Cache 是所有核心共享使用的。

我們先簡(jiǎn)單了解下 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）組成，你可以在下圖清晰的看到：

我們當(dāng)然期望 CPU 讀取數(shù)據(jù)的時(shí)候，都是盡可能地從 CPU Cache 中讀取，而不是每一次都要從內(nèi)存中獲取數(shù)據(jù)。所以，身為程序員，我們要盡可能寫(xiě)出緩存命中率高的代碼，這樣就有效提高程序的性能，具體的做法，你可以參考我上一篇文章「如何寫(xiě)出讓 CPU 跑得更快的代碼？」

事實(shí)上，數(shù)據(jù)不光是只有讀操作，還有寫(xiě)操作，那么如果數(shù)據(jù)寫(xiě)入 Cache 之后，內(nèi)存與 Cache 相對(duì)應(yīng)的數(shù)據(jù)將會(huì)不同，這種情況下 Cache 和內(nèi)存數(shù)據(jù)都不一致了，于是我們肯定是要把 Cache 中的數(shù)據(jù)同步到內(nèi)存里的。

問(wèn)題來(lái)了，那在什么時(shí)機(jī)才把 Cache 中的數(shù)據(jù)寫(xiě)回到內(nèi)存呢？為了應(yīng)對(duì)這個(gè)問(wèn)題，下面介紹兩種針對(duì)寫(xiě)入數(shù)據(jù)的方法：

寫(xiě)直達(dá)（Write Through）
寫(xiě)回（Write Back）

寫(xiě)直達(dá)

保持內(nèi)存與 Cache 一致性最簡(jiǎn)單的方式是，把數(shù)據(jù)同時(shí)寫(xiě)入內(nèi)存和 Cache 中，這種方法稱(chēng)為寫(xiě)直達(dá)（Write Through）。

在這個(gè)方法里，寫(xiě)入前會(huì)先判斷數(shù)據(jù)是否已經(jīng)在 CPU Cache 里面了：

如果數(shù)據(jù)已經(jīng)在 Cache 里面，先將數(shù)據(jù)更新到 Cache 里面，再寫(xiě)入到內(nèi)存里面；
如果數(shù)據(jù)沒(méi)有在 Cache 里面，就直接把數(shù)據(jù)更新到內(nèi)存里面。

寫(xiě)直達(dá)法很直觀，也很簡(jiǎn)單，但是問(wèn)題明顯，無(wú)論數(shù)據(jù)在不在 Cache 里面，每次寫(xiě)操作都會(huì)寫(xiě)回到內(nèi)存，這樣寫(xiě)操作將會(huì)花費(fèi)大量的時(shí)間，無(wú)疑性能會(huì)受到很大的影響。

寫(xiě)回

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

在寫(xiě)回機(jī)制中，當(dāng)發(fā)生寫(xiě)操作時(shí)，新的數(shù)據(jù)僅僅被寫(xiě)入 Cache Block 里，只有當(dāng)修改過(guò)的 Cache Block「被替換」時(shí)才需要寫(xiě)到內(nèi)存中，減少了數(shù)據(jù)寫(xiě)回內(nèi)存的頻率，這樣便可以提高系統(tǒng)的性能。

那具體如何做到的呢？下面來(lái)詳細(xì)說(shuō)一下：

如果當(dāng)發(fā)生寫(xiě)操作時(shí)，數(shù)據(jù)已經(jīng)在 CPU Cache 里的話(huà)，則把數(shù)據(jù)更新到 CPU Cache 里，同時(shí)標(biāo)記 CPU Cache 里的這個(gè) Cache Block 為臟（Dirty）的，這個(gè)臟的標(biāo)記代表這個(gè)時(shí)候，我們 CPU Cache 里面的這個(gè) Cache Block 的數(shù)據(jù)和內(nèi)存是不一致的，這種情況是不用把數(shù)據(jù)寫(xiě)到內(nèi)存里的；
如果當(dāng)發(fā)生寫(xiě)操作時(shí)，數(shù)據(jù)所對(duì)應(yīng)的 Cache Block 里存放的是「別的內(nèi)存地址的數(shù)據(jù)」的話(huà)，就要檢查這個(gè) Cache Block 里的數(shù)據(jù)有沒(méi)有被標(biāo)記為臟的，如果是臟的話(huà)，我們就要把這個(gè) Cache Block 里的數(shù)據(jù)寫(xiě)回到內(nèi)存，然后再把當(dāng)前要寫(xiě)入的數(shù)據(jù)，寫(xiě)入到這個(gè) Cache Block 里，同時(shí)也把它標(biāo)記為臟的；如果 Cache Block 里面的數(shù)據(jù)沒(méi)有被標(biāo)記為臟，則就直接將數(shù)據(jù)寫(xiě)入到這個(gè) Cache Block 里，然后再把這個(gè) Cache Block 標(biāo)記為臟的就好了。

可以發(fā)現(xiàn)寫(xiě)回這個(gè)方法，在把數(shù)據(jù)寫(xiě)入到 Cache 的時(shí)候，只有在緩存不命中，同時(shí)數(shù)據(jù)對(duì)應(yīng)的 Cache 中的 Cache Block 為臟標(biāo)記的情況下，才會(huì)將數(shù)據(jù)寫(xiě)到內(nèi)存中，而在緩存命中的情況下，則在寫(xiě)入后 Cache 后，只需把該數(shù)據(jù)對(duì)應(yīng)的 Cache Block 標(biāo)記為臟即可，而不用寫(xiě)到內(nèi)存里。

這樣的好處是，如果我們大量的操作都能夠命中緩存，那么大部分時(shí)間里 CPU 都不需要讀寫(xiě)內(nèi)存，自然性能相比寫(xiě)直達(dá)會(huì)高很多。

緩存一致性問(wèn)題

現(xiàn)在 CPU 都是多核的，由于 L1/L2 Cache 是多個(gè)核心各自獨(dú)有的，那么會(huì)帶來(lái)多核心的緩存一致性（Cache Coherence） 的問(wèn)題，如果不能保證緩存一致性的問(wèn)題，就可能造成結(jié)果錯(cuò)誤。

那緩存一致性的問(wèn)題具體是怎么發(fā)生的呢？我們以一個(gè)含有兩個(gè)核心的 CPU ?作為例子看一看。

假設(shè) A 號(hào)核心和 B 號(hào)核心同時(shí)運(yùn)行兩個(gè)線程，都操作共同的變量 i（初始值為 0 ）。

這時(shí)如果 A 號(hào)核心執(zhí)行了 i++ 語(yǔ)句的時(shí)候，為了考慮性能，使用了我們前面所說(shuō)的寫(xiě)回策略，先把值為 1 的執(zhí)行結(jié)果寫(xiě)入到 L1/L2 Cache 中，然后把 L1/L2 Cache 中對(duì)應(yīng)的 Block 標(biāo)記為臟的，這個(gè)時(shí)候數(shù)據(jù)其實(shí)沒(méi)有被同步到內(nèi)存中的，因?yàn)閷?xiě)回策略，只有在 A 號(hào)核心中的這個(gè) Cache Block 要被替換的時(shí)候，數(shù)據(jù)才會(huì)寫(xiě)入到內(nèi)存里。

如果這時(shí)旁邊的 B 號(hào)核心嘗試從內(nèi)存讀取 i 變量的值，則讀到的將會(huì)是錯(cuò)誤的值，因?yàn)閯偛?A 號(hào)核心更新 i 值還沒(méi)寫(xiě)入到內(nèi)存中，內(nèi)存中的值還依然是 0。這個(gè)就是所謂的緩存一致性問(wèn)題，A 號(hào)核心和 B 號(hào)核心的緩存，在這個(gè)時(shí)候是不一致，從而會(huì)導(dǎo)致執(zhí)行結(jié)果的錯(cuò)誤。

那么，要解決這一問(wèn)題，就需要一種機(jī)制，來(lái)同步兩個(gè)不同核心里面的緩存數(shù)據(jù)。要實(shí)現(xiàn)的這個(gè)機(jī)制的話(huà)，要保證做到下面這 2 點(diǎn)：

第一點(diǎn)，某個(gè) CPU 核心里的 Cache 數(shù)據(jù)更新時(shí)，必須要傳播到其他核心的 Cache，這個(gè)稱(chēng)為寫(xiě)傳播（Wreite Propagation）；
第二點(diǎn)，某個(gè) CPU 核心里對(duì)數(shù)據(jù)的操作順序，必須在其他核心看起來(lái)順序是一樣的，這個(gè)稱(chēng)為事務(wù)的串形化（Transaction Serialization）。

第一點(diǎn)寫(xiě)傳播很容易就理解，當(dāng)某個(gè)核心在 Cache 更新了數(shù)據(jù)，就需要同步到其他核心的 Cache 里。

而對(duì)于第二點(diǎn)事務(wù)的串形化，我們舉個(gè)例子來(lái)理解它。

假設(shè)我們有一個(gè)含有 4 個(gè)核心的 CPU，這 4 個(gè)核心都操作共同的變量 i（初始值為 0 ）。A 號(hào)核心先把 i 值變?yōu)?100，而此時(shí)同一時(shí)間，B 號(hào)核心先把 i 值變?yōu)?200，這里兩個(gè)修改，都會(huì)「?jìng)鞑ァ沟?C 和 D 號(hào)核心。

那么問(wèn)題就來(lái)了，C 號(hào)核心先收到了 A 號(hào)核心更新數(shù)據(jù)的事件，再收到 B 號(hào)核心更新數(shù)據(jù)的事件，因此 C 號(hào)核心看到的變量 i 是先變成 100，后變成 200。

而如果 D 號(hào)核心收到的事件是反過(guò)來(lái)的，則 D 號(hào)核心看到的是變量 i 先變成 200，再變成 100，雖然是做到了寫(xiě)傳播，但是各個(gè) Cache 里面的數(shù)據(jù)還是不一致的。

所以，我們要保證 C 號(hào)核心和 D 號(hào)核心都能看到相同順序的數(shù)據(jù)變化，比如變量 i 都是先變成 100，再變成 200，這樣的過(guò)程就是事務(wù)的串形化。

要實(shí)現(xiàn)事務(wù)串形化，要做到 2 點(diǎn)：

CPU 核心對(duì)于 Cache 中數(shù)據(jù)的操作，需要同步給其他 CPU 核心；
要引入「鎖」的概念，如果兩個(gè) CPU 核心里有相同數(shù)據(jù)的 Cache，那么對(duì)于這個(gè) Cache 數(shù)據(jù)的更新，只有拿到了「鎖」，才能進(jìn)行對(duì)應(yīng)的數(shù)據(jù)更新。

那接下來(lái)我們看看，寫(xiě)傳播和事務(wù)串形化具體是用什么技術(shù)實(shí)現(xiàn)的。

總線嗅探

寫(xiě)傳播的原則就是當(dāng)某個(gè) CPU 核心更新了 Cache 中的數(shù)據(jù)，要把該事件廣播通知到其他核心。最常見(jiàn)實(shí)現(xiàn)的方式是總線嗅探（Bus Snooping）。

我還是以前面的 i 變量例子來(lái)說(shuō)明總線嗅探的工作機(jī)制，當(dāng) A 號(hào) CPU 核心修改了 L1 Cache 中 i 變量的值，通過(guò)總線把這個(gè)事件廣播通知給其他所有的核心，然后每個(gè) CPU 核心都會(huì)監(jiān)聽(tīng)總線上的廣播事件，并檢查是否有相同的數(shù)據(jù)在自己的 L1 Cache 里面，如果 B 號(hào) CPU 核心的 L1 Cache 中有該數(shù)據(jù)，那么也需要把該數(shù)據(jù)更新到自己的 L1 Cache。

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

另外，總線嗅探只是保證了某個(gè) CPU 核心的 Cache 更新數(shù)據(jù)這個(gè)事件能被其他 CPU 核心知道，但是并不能保證事務(wù)串形化。

于是，有一個(gè)協(xié)議基于總線嗅探機(jī)制實(shí)現(xiàn)了事務(wù)串形化，也用狀態(tài)機(jī)機(jī)制降低了總線帶寬壓力，這個(gè)協(xié)議就是 MESI 協(xié)議，這個(gè)協(xié)議就做到了 CPU 緩存一致性。

MESI 協(xié)議

MESI 協(xié)議其實(shí)是 4 個(gè)狀態(tài)單詞的開(kāi)頭字母縮寫(xiě)，分別是：

Modified，已修改
Exclusive，獨(dú)占
Shared，共享
Invalidated，已失效

這四個(gè)狀態(tài)來(lái)標(biāo)記 Cache Line 四個(gè)不同的狀態(tài)。

「已修改」?fàn)顟B(tài)就是我們前面提到的臟標(biāo)記，代表該 Cache Block 上的數(shù)據(jù)已經(jīng)被更新過(guò)，但是還沒(méi)有寫(xiě)到內(nèi)存里。而「已失效」?fàn)顟B(tài)，表示的是這個(gè) Cache Block 里的數(shù)據(jù)已經(jīng)失效了，不可以讀取該狀態(tài)的數(shù)據(jù)。

「獨(dú)占」和「共享」?fàn)顟B(tài)都代表 Cache Block 里的數(shù)據(jù)是干凈的，也就是說(shuō)，這個(gè)時(shí)候 Cache Block 里的數(shù)據(jù)和內(nèi)存里面的數(shù)據(jù)是一致性的。

「獨(dú)占」和「共享」的差別在于，獨(dú)占狀態(tài)的時(shí)候，數(shù)據(jù)只存儲(chǔ)在一個(gè) CPU 核心的 Cache 里，而其他 CPU 核心的 Cache 沒(méi)有該數(shù)據(jù)。這個(gè)時(shí)候，如果要向獨(dú)占的 Cache 寫(xiě)數(shù)據(jù)，就可以直接自由地寫(xiě)入，而不需要通知其他 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ù)。

我們舉個(gè)具體的例子來(lái)看看這四個(gè)狀態(tài)的轉(zhuǎn)換：

當(dāng) A 號(hào) CPU 核心從內(nèi)存讀取變量 i 的值，數(shù)據(jù)被緩存在 A 號(hào) CPU 核心自己的 Cache 里面，此時(shí)其他 CPU 核心的 Cache 沒(méi)有緩存該數(shù)據(jù)，于是標(biāo)記 Cache Line 狀態(tài)為「獨(dú)占」，此時(shí)其 Cache 中的數(shù)據(jù)與內(nèi)存是一致的；
然后 B 號(hào) CPU 核心也從內(nèi)存讀取了變量 i 的值，此時(shí)會(huì)發(fā)送消息給其他 CPU 核心，由于 A 號(hào) CPU 核心已經(jīng)緩存了該數(shù)據(jù)，所以會(huì)把數(shù)據(jù)返回給 B 號(hào) CPU 核心。在這個(gè)時(shí)候， A 和 B 核心緩存了相同的數(shù)據(jù)，Cache Line 的狀態(tài)就會(huì)變成「共享」，并且其 Cache 中的數(shù)據(jù)與內(nèi)存也是一致的；
當(dāng) A 號(hào) CPU 核心要修改 Cache 中 i 變量的值，發(fā)現(xiàn)數(shù)據(jù)對(duì)應(yīng)的 Cache Line 的狀態(tài)是共享狀態(tài)，則要向所有的其他 CPU 核心廣播一個(gè)請(qǐng)求，要求先把其他核心的 Cache 中對(duì)應(yīng)的 Cache Line 標(biāo)記為「無(wú)效」?fàn)顟B(tài)，然后 A 號(hào) CPU 核心才更新 Cache 里面的數(shù)據(jù)，同時(shí)標(biāo)記 Cache Line 為「已修改」?fàn)顟B(tài)，此時(shí) Cache 中的數(shù)據(jù)就與內(nèi)存不一致了。
如果 A 號(hào) CPU 核心「繼續(xù)」修改 Cache 中 i 變量的值，由于此時(shí)的 Cache Line 是「已修改」?fàn)顟B(tài)，因此不需要給其他 CPU 核心發(fā)送消息，直接更新數(shù)據(jù)即可。
如果 A 號(hào) CPU 核心的 Cache 里的 i 變量對(duì)應(yīng)的 ?Cache Line 要被「替換」，發(fā)現(xiàn) ?Cache Line 狀態(tài)是「已修改」?fàn)顟B(tài)，就會(huì)在替換前先把數(shù)據(jù)同步到內(nèi)存。

所以，可以發(fā)現(xiàn)當(dāng) Cache Line 狀態(tài)是「已修改」或者「獨(dú)占」?fàn)顟B(tài)時(shí)，修改更新其數(shù)據(jù)不需要發(fā)送廣播給其他 CPU 核心，這在一定程度上減少了總線帶寬壓力。

事實(shí)上，整個(gè) MESI 的狀態(tài)可以用一個(gè)有限狀態(tài)機(jī)來(lái)表示它的狀態(tài)流轉(zhuǎn)。還有一點(diǎn)，對(duì)于不同狀態(tài)觸發(fā)的事件操作，可能是來(lái)自本地 CPU 核心發(fā)出的廣播事件，也可以是來(lái)自其他 CPU 核心通過(guò)總線發(fā)出的廣播事件。下圖即是 MESI 協(xié)議的狀態(tài)圖：

MESI 協(xié)議的四種狀態(tài)之間的流轉(zhuǎn)過(guò)程，我匯總成了下面的表格，你可以更詳細(xì)的看到每個(gè)狀態(tài)轉(zhuǎn)換的原因：

總結(jié)

CPU 在讀寫(xiě)數(shù)據(jù)的時(shí)候，都是在 CPU Cache 讀寫(xiě)數(shù)據(jù)的，原因是 Cache 離 CPU 很近，讀寫(xiě)性能相比內(nèi)存高出很多。對(duì)于 Cache 里沒(méi)有緩存 CPU 所需要讀取的數(shù)據(jù)的這種情況，CPU 則會(huì)從內(nèi)存讀取數(shù)據(jù)，并將數(shù)據(jù)緩存到 Cache 里面，最后 CPU 再?gòu)?Cache 讀取數(shù)據(jù)。

而對(duì)于數(shù)據(jù)的寫(xiě)入，CPU 都會(huì)先寫(xiě)入到 Cache 里面，然后再在找個(gè)合適的時(shí)機(jī)寫(xiě)入到內(nèi)存，那就有「寫(xiě)直達(dá)」和「寫(xiě)回」這兩種策略來(lái)保證 Cache 與內(nèi)存的數(shù)據(jù)一致性：

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

當(dāng)今 CPU 都是多核的，每個(gè)核心都有各自獨(dú)立的 L1/L2 Cache，只有 L3 Cache 是多個(gè)核心之間共享的。所以，我們要確保多核緩存是一致性的，否則會(huì)出現(xiàn)錯(cuò)誤的結(jié)果。

要想實(shí)現(xiàn)緩存一致性，關(guān)鍵是要滿(mǎn)足 2 點(diǎn)：

第一點(diǎn)是寫(xiě)傳播，也就是當(dāng)某個(gè) CPU 核心發(fā)生寫(xiě)入操作時(shí)，需要把該事件廣播通知給其他核心；
第二點(diǎn)是事物的串行化，這個(gè)很重要，只有保證了這個(gè)，次啊能保障我們的數(shù)據(jù)是真正一致的，我們的程序在各個(gè)不同的核心上運(yùn)行的結(jié)果也是一致的；

基于總線嗅探機(jī)制的 MESI 協(xié)議，就滿(mǎn)足上面了這兩點(diǎn)，因此它是保障緩存一致性的協(xié)議。

MESI 協(xié)議，是已修改、獨(dú)占、共享、已實(shí)現(xiàn)這四個(gè)狀態(tài)的英文縮寫(xiě)的組合。整個(gè) MSI 狀態(tài)的變更，則是根據(jù)來(lái)自本地 CPU 核心的請(qǐng)求，或者來(lái)自其他 CPU 核心通過(guò)總線傳輸過(guò)來(lái)的請(qǐng)求，從而構(gòu)成一個(gè)流動(dòng)的狀態(tài)機(jī)。另外，對(duì)于在「已修改」或者「獨(dú)占」?fàn)顟B(tài)的 Cache Line，修改更新其數(shù)據(jù)不需要發(fā)送廣播給其他 CPU 核心。