[[408474]]

本文轉(zhuǎn)載自微信公眾號(hào)「虛機(jī)」，作者cloud3。轉(zhuǎn)載本文請(qǐng)聯(lián)系虛機(jī)公眾號(hào)。

 這是圖解系列之CPU cache

本文接著說(shuō)Cache的一致性

我是cloud3

[[408475]]

下面分析一下緩存一致性問(wèn)題。

本文只討論硬件的cache一致性機(jī)制，所以對(duì)軟件來(lái)說(shuō)是透明的。

首先來(lái)看Cache和內(nèi)存保持一致性的兩種寫(xiě)入方式

write through和write back

CPU把數(shù)據(jù)寫(xiě)入 Cache 之后，內(nèi)存與 Cache中 對(duì)應(yīng)的數(shù)據(jù)就不一致了，所以要在一定的時(shí)機(jī)要把 Cache 中的數(shù)據(jù)同步到內(nèi)存中。

根據(jù)寫(xiě)操作后同步到內(nèi)存的時(shí)機(jī)，Cache和內(nèi)存同步的方法可分為write back和write through。

write through

CPU向cache寫(xiě)入數(shù)據(jù)時(shí)，同時(shí)也寫(xiě)入memory，使cache和memory的數(shù)據(jù)保持一致。

優(yōu)點(diǎn)是簡(jiǎn)單，缺點(diǎn)是每次都要訪問(wèn)memory，速度比較慢。但是讀數(shù)據(jù)時(shí)還是能夠享受Cache帶來(lái)的快速優(yōu)點(diǎn)的。

write back

CPU向cache寫(xiě)入數(shù)據(jù)時(shí)，只是把更新的cache區(qū)標(biāo)記一下(cache line 被標(biāo)為dirty)，并不同步寫(xiě)入memory。

只是在cache區(qū)要被刷入新的數(shù)據(jù)時(shí)，才更新memory。

優(yōu)點(diǎn)是CPU執(zhí)行的效率提高，缺點(diǎn)是實(shí)現(xiàn)起來(lái)技術(shù)比較復(fù)雜。

其中write back可以減少不必要的內(nèi)存寫(xiě)入，減輕總線(xiàn)壓力。現(xiàn)在大部分場(chǎng)景下，cache多采用write back的方式，本文的介紹都是基于write back的方式。

單核一致性

首先我們看一下單處理器情況下Cache和主存之間如何保持一致性。

讀Cache:

寫(xiě)Cache:

如果是多處理器呢?

多處理器的一致性問(wèn)題

舉個(gè)例子吧，內(nèi)存0x48處數(shù)據(jù)為0x20，處理器0和1都從0x48處讀取內(nèi)存數(shù)據(jù)到自己的Cache line中。

然后處理器0寫(xiě)Cache把0x48數(shù)據(jù)更新為0x10，處理器1讀0x48自己Cache命中，返回了0x20。

出現(xiàn)兩個(gè)處理器讀到的內(nèi)存數(shù)據(jù)不一致了!

那么多處理器如何解決緩存一致性問(wèn)題呢?

多處理器的一致性方法

多處理器一般是采用基于總線(xiàn)監(jiān)聽(tīng)機(jī)制的高速緩存一致性協(xié)議。包括寫(xiě)無(wú)效和寫(xiě)更新協(xié)議。另外還有基于目錄的高速緩存一致性機(jī)制。

總線(xiàn)監(jiān)聽(tīng)(Bus snooping)

總線(xiàn)監(jiān)聽(tīng)(Bus snooping)機(jī)制由 Ravishankar 和 Goodman 在 1983 年提出。其工作原理是當(dāng)一個(gè)CPU修改了cache塊之后，此更改必須傳播到所有擁有該Cache 塊副本的Cache上。

所有的監(jiān)聽(tīng)者會(huì)監(jiān)視總線(xiàn)上的所有數(shù)據(jù)廣播。如果總線(xiàn)上出現(xiàn)修改共享Cache塊的事件，所有監(jiān)聽(tīng)者會(huì)檢查自己的Cache是否緩存有共享Cache塊的副本。

如果緩存有該共享Cache塊的副本，則監(jiān)聽(tīng)者執(zhí)行操作以確保緩存一致性。

這些操作可以是刷新或失效緩存塊，根據(jù)緩存一致性協(xié)議更改緩存塊狀態(tài)。

兩類(lèi)總線(xiàn)監(jiān)聽(tīng)協(xié)議

根據(jù)管理本地Cache塊副本的方式，有兩類(lèi)總線(xiàn)監(jiān)聽(tīng)協(xié)議：

寫(xiě)更新(Write-update)

寫(xiě)無(wú)效(Write-invalidate)。

寫(xiě)更新(Write-update)

當(dāng)處理器寫(xiě)入Cache塊時(shí)，其他Cache監(jiān)聽(tīng)到后把自己Cache中的數(shù)據(jù)副本進(jìn)行更新。該方法通過(guò)總線(xiàn)向所有緩存廣播寫(xiě)入數(shù)據(jù)。它比寫(xiě)無(wú)效協(xié)議產(chǎn)生更大的總線(xiàn)流量，所有這種方式不常見(jiàn)。Dragon和firefly屬于這一類(lèi)協(xié)議。

寫(xiě)無(wú)效(Write-invalidate)

這是最常用的監(jiān)聽(tīng)協(xié)議。當(dāng)處理器寫(xiě)入Cache塊時(shí)，其他Cache監(jiān)聽(tīng)到后把自己Cache中的數(shù)據(jù)副本標(biāo)記為無(wú)效狀態(tài)。這樣處理器只能讀取和寫(xiě)入數(shù)據(jù)的一個(gè)副本，其他緩存中的副本都是無(wú)效的。

寫(xiě)直通無(wú)效協(xié)議、寫(xiě)一次協(xié)議、MSI、MESI、MOSI、MOESI、MESIF都屬于寫(xiě)無(wú)效這一類(lèi)協(xié)議。

下面以最為常用的MESI協(xié)議為例子分析寫(xiě)無(wú)效協(xié)議

MESI

MESI協(xié)議又叫Illinois協(xié)議，MESI，"M", "E", "S", "I"這4個(gè)字母代表了一個(gè)cache line的四種狀態(tài)，分別是Modified,Exclusive,Shared和Invalid。

• Modified (M)

cache line只被當(dāng)前cache所有，并且是dirty的。

• Exclusive (E)

cache line僅存在于當(dāng)前緩存中，并且是clean的。

• Shared (S)

cache line在其他Cache中也存在并且都是clean的。

• Invalid (I)

cache line無(wú)效，即沒(méi)有被任何Cache加載。

有一個(gè)著名的狀態(tài)標(biāo)記圖：

這個(gè)狀態(tài)標(biāo)記圖什么意思呢?

對(duì)同一個(gè)Cache line，

我標(biāo)記它為是M時(shí)，你只能標(biāo)記為I

我標(biāo)記它為是E時(shí)，你只能標(biāo)記為I

我標(biāo)記它為是S時(shí)，你只能標(biāo)記為S或I

我標(biāo)記它為是I時(shí)，你能標(biāo)記為MESI

MESI有一個(gè)狀態(tài)機(jī)：

這個(gè)狀態(tài)機(jī)什么意思呢?它顯示了一種狀態(tài)在出現(xiàn)什么Event時(shí)轉(zhuǎn)換成哪一種狀態(tài)，自己狀態(tài)轉(zhuǎn)換過(guò)程中要向總線(xiàn)上廣播什么消息(這些消息會(huì)被其他Cache監(jiān)聽(tīng)到)

下面的表是對(duì)這個(gè)狀態(tài)機(jī)的詳細(xì)說(shuō)明:

舉個(gè)例子：

某Cache上一個(gè)cache line的現(xiàn)在狀態(tài)是Shared。

如果本地CPU對(duì)它Read hit，那它狀態(tài)還是Shared。

如果本地CPU對(duì)它Write hit，那它的狀態(tài)變?yōu)镸odified，并在總線(xiàn)上廣播它Invalidate。

如果監(jiān)聽(tīng)到總線(xiàn)上的Read消息，那它的狀態(tài)還是Shared。

如果監(jiān)聽(tīng)到總線(xiàn)上的Invalidate消息，那它的狀態(tài)變?yōu)镮nvalidate。

其他的狀態(tài)轉(zhuǎn)換也是類(lèi)似的處理。

總線(xiàn)監(jiān)聽(tīng)的優(yōu)缺點(diǎn)

如果有足夠的帶寬，總線(xiàn)監(jiān)聽(tīng)比基于目錄的一致性機(jī)制更快，因?yàn)樗惺聞?wù)都是直接被所有處理器看到。

總線(xiàn)偵聽(tīng)的缺點(diǎn)是可擴(kuò)展性有限。頻繁監(jiān)聽(tīng)緩存會(huì)導(dǎo)致與處理器的訪問(wèn)競(jìng)爭(zhēng)，從而增加緩存訪問(wèn)時(shí)間和功耗。每個(gè)請(qǐng)求都必須廣播到系統(tǒng)中的所有節(jié)點(diǎn)。這意味著總線(xiàn)帶寬必須隨著系統(tǒng)變大而增長(zhǎng)。由于總線(xiàn)偵聽(tīng)不能很好地?cái)U(kuò)展，較大的緩存一致性NUMA系統(tǒng)傾向于使用基于目錄的一致性協(xié)議。

基于目錄(Directory-based)

基于目錄的一致性方法中，緩存的Cache塊副本信息被保存在稱(chēng)為目錄的結(jié)構(gòu)中。當(dāng)處理器寫(xiě)入Cache塊時(shí)，不會(huì)向所有Cache廣播請(qǐng)求，而是先查詢(xún)目錄以檢索具有該副本的Cache，再發(fā)送到特定的處理器。與總線(xiàn)監(jiān)聽(tīng)相比，目錄方法可以大量節(jié)省總線(xiàn)流量。

在NUMA系統(tǒng)中，通常選擇基于目錄(directory-based)的方式來(lái)維護(hù)Cache的一致性。