CPU緩存一致性原理

在本站的文章CPU緩存那些事兒中， 介紹了cpu的多級(jí)緩存的架構(gòu)和cpu緩存行cache line的結(jié)構(gòu)。CPU對(duì)于緩存的操作包含讀和寫，讀操作在cache line中有所涉及，在本文中，將重點(diǎn)討論CPU對(duì)于緩存進(jìn)行寫時(shí)的行為。

單核CPU對(duì)高速緩存的讀操作

CPU對(duì)于高速緩存的讀操作的過程在之前的文章中有提到過，這里梳理一下其流程：

• 1.首先對(duì)于一個(gè)內(nèi)存地址，CPU會(huì)按照索引規(guī)則（直接映射/多路組相連/全相連）優(yōu)先去cache line中進(jìn)行檢索。
• 2.如果檢索到了，意味著該內(nèi)存地址的內(nèi)容已經(jīng)存在于cache中，則直接讀取內(nèi)容到CPU中，流程結(jié)束。如果沒有檢索到，進(jìn)行步驟3。
• 3.此時(shí)確認(rèn)內(nèi)存的數(shù)據(jù)不在cache line中，如果cache已經(jīng)存滿或者已經(jīng)被其他內(nèi)存地址映射，則進(jìn)入步驟4，如果cache line中還有空位，則進(jìn)入步驟5.
• 4.執(zhí)行緩存淘汰策略，騰出位置
• 5.加載內(nèi)存數(shù)據(jù)到cache line中，將cache塊上的內(nèi)容讀取到cpu中。

對(duì)于單核CPU， 對(duì)cache的讀操作的流程如下所示：

單核CPU對(duì)于高速緩存的寫操作

CPU對(duì)于高速緩存的寫操作比讀操作要復(fù)雜一些，寫操作會(huì)修改cache中的數(shù)據(jù)，而這一數(shù)據(jù)最終需要同步到內(nèi)存中，在同步到內(nèi)存這個(gè)點(diǎn)上，寫操作的策略可以分為寫直達(dá)策略和寫回策略。注意這里的討論仍然是針對(duì)單核CPU而言的。

寫直達(dá)策略(Write-Through)

寫直達(dá)策略的思想是對(duì)于寫入操作，同時(shí)修改cache中的數(shù)據(jù)和內(nèi)存中的數(shù)據(jù)，使得cache和內(nèi)存中的數(shù)據(jù)保持一致。這將使得cache和內(nèi)存擁有數(shù)據(jù)的強(qiáng)一致性。

寫直達(dá)策略中寫數(shù)據(jù)的流程可以被細(xì)化為下列的步驟：

• 1.判斷待寫入的數(shù)據(jù)是否已經(jīng)存在于cache中。如寫入的數(shù)據(jù)已經(jīng)存在于cache中，則跳轉(zhuǎn)到步驟2，否則跳轉(zhuǎn)到步驟3。
• 2.將數(shù)據(jù)寫入cache中。
• 3.將數(shù)據(jù)寫入內(nèi)存。

而寫直達(dá)策略中讀數(shù)據(jù)的流程并沒有任何改變，因?yàn)閏ache和內(nèi)存的數(shù)據(jù)是強(qiáng)一致的。

寫直達(dá)策略的流程概括為如下所示：

對(duì)于寫直達(dá)策略，讀cache的流程并沒有任何改變，這一點(diǎn)和寫回策略是有區(qū)別的。

寫直達(dá)的優(yōu)缺點(diǎn)如下：

優(yōu)點(diǎn)：對(duì)于寫操作而言，可以保證內(nèi)存和高速緩存內(nèi)容的強(qiáng)一致性。

缺點(diǎn)：由于每次寫入操作都需要將數(shù)據(jù)寫入內(nèi)存，使得寫操作的耗時(shí)增加，失去了高速緩存的高效性。

寫回策略(Write-Back)

寫直達(dá)策略的思想是當(dāng)需要修改cache時(shí)，延遲修改內(nèi)存。在每個(gè)cache line上增加了Dirty的標(biāo)記，當(dāng)修改了cache中的內(nèi)容時(shí)，會(huì)將Dirty標(biāo)記置位，表明它的數(shù)據(jù)和內(nèi)存數(shù)據(jù)不一致。注意此時(shí)，并不會(huì)立即寫回內(nèi)存。只有當(dāng)cache塊被替換出去時(shí)，才會(huì)回寫到內(nèi)存中。這其實(shí)是一種異步的思想，其相較于寫直達(dá)也要復(fù)雜一些。寫回策略實(shí)現(xiàn)的是一種最終一致性。

寫回策略是由讀和寫配合完成的。

對(duì)于寫回策略中的寫操作，其流程如下：

• 1.首先判斷寫操作的地址是否存在于cache中，如存在，進(jìn)入步驟6，否則進(jìn)入步驟2。
• 2.如果寫操作的地址不在cache中，則嘗試讀取內(nèi)存數(shù)據(jù)到cache中。這里需要判斷cache此時(shí)是否已經(jīng)滿或者被占用。如果已經(jīng)滿或者被占用，則進(jìn)入步驟3，否則進(jìn)入步驟5。
• 3.如果cache此時(shí)是否已經(jīng)滿或者被占用，則使用替換策略挪出空位。此時(shí)還需要判斷被替換出的cache line是否為臟數(shù)據(jù)，如果是臟數(shù)據(jù)，則進(jìn)入步驟4，否則進(jìn)入步驟5
• 4.將被替換出的cache line的數(shù)據(jù)寫回內(nèi)存中。
• 5.讀取內(nèi)存塊的數(shù)據(jù)到cache line中。
• 6.將數(shù)據(jù)寫入cache中
• 7.將cache line標(biāo)記為臟數(shù)據(jù)。

由于替換策略也可能發(fā)生在讀操作中，因此對(duì)于寫回策略中的讀操作也發(fā)生了修改，其流程如下所示：

• 1.首先對(duì)于一個(gè)內(nèi)存地址，CPU會(huì)按照索引規(guī)則（直接映射/多路組相連/全相連）優(yōu)先去cache line中進(jìn)行檢索。
• 2.如果檢索到了，意味著該內(nèi)存地址的內(nèi)容已經(jīng)存在于cache中，則直接讀取內(nèi)容到CPU中，流程結(jié)束。如果沒有檢索到，進(jìn)行步驟3。
• 3.此時(shí)確認(rèn)內(nèi)存的數(shù)據(jù)不在cache line中，如果cache已經(jīng)存滿或者已經(jīng)被其他內(nèi)存地址映射，則進(jìn)入步驟4，如果cache line中還有空位，則進(jìn)入步驟6.
• 4.執(zhí)行緩存淘汰策略，騰出位置，此時(shí)需要判斷被替換出的cache line是否為臟數(shù)據(jù)，如果是，則進(jìn)入步驟5，否則進(jìn)入步驟6.
• 5.將臟數(shù)據(jù)寫回到內(nèi)存中。
• 6.加載內(nèi)存數(shù)據(jù)到cache line中，將cache塊上的內(nèi)容讀取到cpu中。

寫回策略的讀寫操作的流程如下所示：

多CPU核的緩存一致性問題。

上面的寫直達(dá)策略和寫回策略可以解決單核CPU的cache和內(nèi)存的一致性問題。而現(xiàn)代的CPU往往都是多核CPU，每個(gè)核心都擁有其自己的cache。那么對(duì)于寫操作而言，除了保證本CPU的cache和內(nèi)存的一致性，還需要保證其它CPU的cache和內(nèi)存的一致性問題。

MESI協(xié)議就是用來解決這個(gè)問題的。

MESI協(xié)議是一種用于保證緩存一致性的協(xié)議，其對(duì)應(yīng)了CPU cache的四種狀態(tài)，每個(gè)字母代表了一種狀態(tài)，其含義如下：

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

MESI 協(xié)議其實(shí)是 CPU Cache 的有限狀態(tài)機(jī)，其四種狀態(tài)的轉(zhuǎn)化如下圖所示：

對(duì)于MESI協(xié)議，有一個(gè)可視化的網(wǎng)站可以演示其過程，網(wǎng)址：https://www.scss.tcd.ie/Jeremy.Jones/VivioJS/caches/MESIHelp.htm。

下面我們借助該網(wǎng)站來理解MESI每個(gè)狀態(tài)的變換過程。

獨(dú)占狀態(tài)E轉(zhuǎn)已修改狀態(tài)M E->M

如下圖所示，此時(shí)cpu0上有a0的緩存，a0的緩存狀態(tài)是獨(dú)占狀態(tài)E。

此時(shí)cpu0執(zhí)行write a0操作，由于其它c(diǎn)pu上沒有a0數(shù)據(jù)，狀態(tài)E轉(zhuǎn)為狀態(tài)M：

已修改狀態(tài)M轉(zhuǎn)共享狀態(tài)S,M->S

如下圖所示，此時(shí)cpu0上有a0的緩存，a0的緩存狀態(tài)是已修改狀態(tài)M:

隨后cpu1上執(zhí)行read a0的操作，則cpu 0上的a0從狀態(tài)M轉(zhuǎn)為狀態(tài)S：

共享狀態(tài)S轉(zhuǎn)已失效狀態(tài)I， S->I

如下圖所示，此時(shí)cpu0上有a0的緩存，其狀態(tài)為S。除此以外，cpu1上也有a0的緩存。

此時(shí)cpu1上執(zhí)行write a0的操作，則cpu0上的a0狀態(tài)從S轉(zhuǎn)為了I：

共享狀態(tài)S轉(zhuǎn)獨(dú)占狀態(tài)E, S->E

如下圖所示，此時(shí)cpu0上有a0的緩存，其狀態(tài)為S。除此以外，cpu1上也有a0的緩存。

此時(shí)cpu1上執(zhí)行write a0的操作，則cpu1上的a0狀態(tài)從S轉(zhuǎn)為了E：

已失效狀態(tài)I轉(zhuǎn)獨(dú)占狀態(tài)E,I->E

狀態(tài)I轉(zhuǎn)狀態(tài)E有兩種路徑，第一種是通過Processor Read, 此時(shí)a0數(shù)據(jù)僅存在于cpu0的cache中：

cpu0執(zhí)行read a0操作，a0狀態(tài)從I轉(zhuǎn)為了E：

第二種是通過process write， 注意此時(shí)a0數(shù)據(jù)存在于cpu0和cpu1的cache中：

cpu0執(zhí)行write a0操作，a0狀態(tài)從I轉(zhuǎn)為了E：

已失效狀態(tài)I轉(zhuǎn)共享狀態(tài)S,I->S

此時(shí)cpu0上a0的狀態(tài)是I， 而cpu1上a0的狀態(tài)是E：

此時(shí)cpu0執(zhí)行read a0操作，cpu0上的a0從I轉(zhuǎn)為S：

獨(dú)占狀態(tài)E轉(zhuǎn)已失效狀態(tài)I，E->I

此時(shí)cpu0上的有a0的緩存，且狀態(tài)為E，其它c(diǎn)pu上沒有a0的緩存：

此時(shí)cpu1執(zhí)行write a0的操作，此時(shí)cpu0上a0的狀態(tài)從E轉(zhuǎn)為I：

已修改狀態(tài)E轉(zhuǎn)共享狀態(tài)S,E->S

如下圖所示，此時(shí)cpu0的獨(dú)占a0：

此時(shí)cpu1執(zhí)行read a0的操作：

獨(dú)占狀態(tài)M轉(zhuǎn)失效狀態(tài)I， M->I

此時(shí)cpu0上擁有a0的緩存，且狀態(tài)為M，其它c(diǎn)pu上沒有a0的緩存：

此時(shí)cpu1執(zhí)行write a0的操作,則cpu0上a0緩存的狀態(tài)從獨(dú)占(M)轉(zhuǎn)為了失效(I)：

已失效狀態(tài)I轉(zhuǎn)已修改狀態(tài)M，I->M

此時(shí)cpu0上a0緩存的狀態(tài)是I，其它c(diǎn)pu上沒有a0的緩存：

此時(shí)cpu0執(zhí)行write a0, 則cpu0上的a0從I轉(zhuǎn)為了E：

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

寫緩沖區(qū)和失效隊(duì)列實(shí)際上是對(duì)MESI的優(yōu)化策略。

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

從上面的對(duì)于MESI的理解中，不難發(fā)現(xiàn)，MESI協(xié)議其實(shí)并不高效。例如當(dāng)CPU1將要修改cache line時(shí)，需要廣播RFO獲得獨(dú)占權(quán)，當(dāng)收到其它c(diǎn)pu核的ACK之前，CPU1只能空等。 這對(duì)于CPU1而言，是一種資源的浪費(fèi)。寫緩沖區(qū)就是為了解決這個(gè)問題的。當(dāng)CPU核需要寫操作時(shí)，會(huì)將寫操作放入緩沖區(qū)中，然后就可以執(zhí)行其它指令了。當(dāng)收到其它核心的ACK后，就可以將寫入的內(nèi)容寫入cache中。

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

寫緩沖區(qū)是對(duì)寫操作發(fā)送命令時(shí)的優(yōu)化，而失效隊(duì)列則是針對(duì)收寫操作命令時(shí)的優(yōu)化。

對(duì)于其它的CPU核心而言，在其收到RFO請(qǐng)求時(shí)，需要更新當(dāng)前CPU的cache line狀態(tài)，并回復(fù)ACK。然而在收到RFO請(qǐng)求時(shí)，CPU核心可能在處理其它的事情，不能及時(shí)回復(fù)

寫緩沖區(qū)和失效隊(duì)列將RFO請(qǐng)求的收發(fā)修改為了異步的，這實(shí)際上實(shí)現(xiàn)的是一種最終一致性。這也會(huì)引入新的問題，即CPU對(duì)于指令會(huì)有重排。如果有一些程序?qū)τ趦?nèi)存序有要求，那么就需要進(jìn)行考慮。

考慮下面的場(chǎng)景，cpu0和cpu1分別執(zhí)行下面的指令：

cpu0上指令

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

cpu1上指令

b = 1 //B1
y = a //B2

由于store-buffer的存在，盡管A1操作先于A2操作之前發(fā)生，但是A1操作完成時(shí)間可能晚于A2，如下表中反應(yīng)的順序：

盡管A1操作發(fā)生于B2之前，但是由于寫操作的異步特性，當(dāng)執(zhí)行到y(tǒng)=a時(shí)，讀取到的還是舊值。同理x=b也可能讀取到舊的值。

對(duì)于這種cpu層面的指令重排問題，則需要內(nèi)存屏障進(jìn)行解決。

總結(jié)

• 對(duì)于單核cpu，寫操作需要考慮cache和內(nèi)存的一致性，通常有寫直達(dá)和寫回兩種策略。
• 對(duì)于多核cpu，除了cache和內(nèi)存的一致性需要保證，還需要保證每個(gè)cpu的cache的數(shù)據(jù)的一致性。
• MESI協(xié)議就是一種解決多核cpu緩存一致性的算法
• 為了改善MESI的效率，引入了store-buffer和Invalidation Queue，提升了效率，但是也引入了指令重排的問題。通?？梢允褂脙?nèi)存屏障解決。

參考文獻(xiàn)

https://www.scss.tcd.ie/Jeremy.Jones/VivioJS/caches/MESIHelp.htm
https://blog.csdn.net/weixin_46215617/article/details/115433851?share_token=0637ba7e-fc4b-4d21-8d6b-000301e7fe3e
https://juejin.cn/post/7158395475362578462
https://blog.51cto.com/qmiller/5285102文章來源地址http://www.zghlxwxcb.cn/news/detail-662306.html

到了這里，關(guān)于CPU緩存一致性原理的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！