Categories
程式開發

10 張圖打開CPU 緩存一致性的大門


10 張圖打開CPU 緩存一致性的大門 1

前言

直接上,不多BB 了。

10 張圖打開CPU 緩存一致性的大門 2

正文

CPU Cache 的數據寫入

隨著時間的推移,CPU 和內存的訪問性能相差越來越大,於是就在CPU 內部嵌入了CPU Cache(高速緩存),CPU Cache 離CPU 核心相當近,因此它的訪問速度是很快的,於是它充當了CPU 與內存之間的緩存角色。

CPU Cache 通常分為三級緩存:L1 Cache、L2 Cache、L3 Cache,級別越低的離CPU 核心越近,訪問速度也快,但是存儲容量相對就會越小。其中,在多核心的CPU 裡,每個核心都有各自的L1/L2 Cache,而L3 Cache 是所有核心共享使用的。

10 張圖打開CPU 緩存一致性的大門 3

我們先簡單了解下CPU Cache 的結構,CPU Cache 是由很多個Cache Line 組成的,CPU Line 是CPU 從內存讀取數據的基本單位,而CPU Line 是由各種標誌(Tag)+ 數據塊(Data Block)組成,你可以在下圖清晰的看到:

10 張圖打開CPU 緩存一致性的大門 4

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

事實上,數據不光是只有讀操作,還有寫操作,那麼如果數據寫入Cache 之後,內存與Cache 相對應的數據將會不同,這種情況下Cache 和內存數據都不一致了,於是我們肯定是要把Cache 中的數據同步到內存裡的。

問題來了,那在什麼時機才把Cache 中的數據寫回到內存呢?為了應對這個問題,下面介紹兩種針對寫入數據的方法:

寫直達(Write Through)寫回(Write Back)

寫直達

保持內存與Cache 一致性最簡單的方式是,把數據同時寫入內存和Cache 中,這種方法稱為*寫直達(Write Through)*。

10 張圖打開CPU 緩存一致性的大門 5

在這個方法裡,寫入前會先判斷數據是否已經在CPU Cache 裡面了:

如果數據已經在Cache 裡面,先將數據更新到Cache 裡面,再寫入到內存裡面;如果數據沒有在Cache 裡面,就直接把數據更新到內存裡面。

寫直達法很直觀,也很簡單,但是問題明顯,無論數據在不在Cache 裡面,每次寫操作都會寫回到內存,這樣寫操作將會花費大量的時間,無疑性能會受到很大的影響。

寫回

既然寫直達由於每次寫操作都會把數據寫回到內存,而導致影響性能,於是為了要減少數據寫回內存的頻率,就出現了*寫回(Write Back)的方法*。

在寫回機制中,當發生寫操作時,新的數據僅僅被寫入Cache Block 裡,只有當修改過的Cache Block「被替換」時才需要寫到內存中,減少了數據寫回內存的頻率,這樣便可以提高系統的性能。

10 張圖打開CPU 緩存一致性的大門 6

那具體如何做到的呢?下面來詳細說一下:

如果當發生寫操作時,數據已經在CPU Cache 裡的話,則把數據更新到CPU Cache 裡,同時標記CPU Cache 裡的這個Cache Block 為臟(Dirty)的,這個臟的標記代表這個時候,我們CPU Cache 裡面的這個Cache Block 的數據和內存是不一致的,這種情況是不用把數據寫到內存裡的;如果當發生寫操作時,數據所對應的Cache Block 裡存放的是「別的內存地址的數據」的話,就要檢查這個Cache Block 裡的數據有沒有被標記為臟的,如果是臟的話,我們就要把這個Cache Block 裡的數據寫回到內存,然後再把當前要寫入的數據,寫入到這個Cache Block 裡,同時也把它標記為臟的;如果Cache Block 裡面的數據沒有被標記為臟,則就直接將數據寫入到這個Cache Block 裡,然後再把這個Cache Block 標記為臟的就好了。

可以發現寫回這個方法,在把數據寫入到Cache 的時候,只有在緩存不命中,同時數據對應的Cache 中的Cache Block 為臟標記的情況下,才會將數據寫到內存中,而在緩存命中的情況下,則在寫入後Cache 後,只需把該數據對應的Cache Block 標記為臟即可,而不用寫到內存裡。

這樣的好處是,如果我們大量的操作都能夠命中緩存,那麼大部分時間裡CPU 都不需要讀寫內存,自然性能相比寫直達會高很多。

緩存一致性問題

現在CPU 都是多核的,由於L1/L2 Cache 是多個核心各自獨有的,那麼會帶來多核心的*緩存一致性(Cache Coherence)* 的問題,如果不能保證緩存一致性的問題,就可能造成結果錯誤。

那緩存一致性的問題具體是怎麼發生的呢?我們以一個含有兩個核心的CPU 作為例子看一看。

假設A 號核心和B 號核心同時運行兩個線程,都操作共同的變量i(初始值為0 )。

10 張圖打開CPU 緩存一致性的大門 7

這時如果A 號核心執行了i++ 語句的時候,為了考慮性能,使用了我們前面所說的寫回策略,先把值為1 的執行結果寫入到L1/L2 Cache 中,然後把L1/L2 Cache 中對應的Block 標記為臟的,這個時候數據其實沒有被同步到內存中的,因為寫回策略,只有在A 號核心中的這個Cache Block 要被替換的時候,數據才會寫入到內存裡。

如果這時旁邊的B 號核心嘗試從內存讀取i 變量的值,則讀到的將會是錯誤的值,因為剛才A 號核心更新i 值還沒寫入到內存中,內存中的值還依然是0。這個就是所謂的緩存一致性問題,A 號核心和B 號核心的緩存,在這個時候是不一致,從而會導致執行結果的錯誤。

10 張圖打開CPU 緩存一致性的大門 8

那麼,要解決這一問題,就需要一種機制,來同步兩個不同核心裡面的緩存數據。要實現的這個機制的話,要保證做到下面這2 點:

第一點,某個CPU 核心裡的Cache 數據更新時,必須要傳播到其他核心的Cache,這個稱為*寫傳播(Wreite Propagation)*;第二點,某個CPU 核心裡對數據的操作順序,必須在其他核心看起來順序是一樣的,這個稱為*事務的串形化(Transaction Serialization)*。

第一點寫傳播很容易就理解,當某個核心在Cache 更新了數據,就需要同步到其他核心的Cache 裡。而對於第二點事務事的串形化,我們舉個例子來理解它。

假設我們有一個含有4 個核心的CPU,這4 個核心都操作共同的變量i(初始值為0 )。 A 號核心先把i 值變為100,而此時同一時間,B 號核心先把i 值變為200,這裡兩個修改,都會「傳播」到C 和D 號核心。

10 張圖打開CPU 緩存一致性的大門 9

那麼問題就來了,C 號核心先收到了A 號核心更新數據的事件,再收到B 號核心更新數據的事件,因此C 號核心看到的變量i 是先變成100,後變成200 。

而如果D 號核心收到的事件是反過來的,則D 號核心看到的是變量i 先變成200,再變成100,雖然是做到了寫傳播,但是各個Cache 裡面的數據還是不一致的。

所以,我們要保證C 號核心和D 號核心都能看到相同順序的數據變化,比如變量i 都是先變成100,再變成200,這樣的過程就是事務的串形化。

要實現事務串形化,要做到2 點:

CPU 核心對於Cache 中數據的操作,需要同步給其他CPU 核心;要引入「鎖」的概念,如果兩個CPU 核心裡有相同數據的Cache,那麼對於這個Cache 數據的更新,只有拿到了「鎖」 ,才能進行對應的數據更新。

那接下來我們看看,寫傳播和事務串形化具體是用什麼技術實現的。

總線嗅探

寫傳播的原則就是當某個CPU 核心更新了Cache 中的數據,要把該事件廣播通知到其他核心。最常見實現的方式是*總線嗅探(Bus Snooping)*。

我還是以前面的i 變量例子來說明總線嗅探的工作機制,當A 號CPU 核心修改了L1 Cache 中i 變量的值,通過總線把這個事件廣播通知給其他所有的核心,然後每個CPU 核心都會監聽總線上的廣播事件,並檢查是否有相同的數據在自己的L1 Cache 裡面,如果B 號CPU 核心的L1 Cache 中有該數據,那麼也需要把該數據更新到自己的L1 Cache。

可以發現,總線嗅探方法很簡單, CPU 需要每時每刻監聽總線上的一切活動,但是不管別的核心的Cache 是否緩存相同的數據,都需要發出一個廣播事件,這無疑會加重總線的負載。

另外,總線嗅探只是保證了某個CPU 核心的Cache 更新數據這個事件能被其他CPU 核心知道,但是並不能保證事務串形化。

於是,有一個協議基於總線嗅探機制實現了事務串形化,也用狀態機機制降低了總線帶寬壓力,這個協議就是MESI 協議,這個協議就做到了CPU 緩存一致性。

MESI 協議

MESI 協議其實是4 個狀態單詞的開頭字母縮寫,分別是:

Modified,已修改Exclusive,獨占Shared,共享Invalidated,已失效

這四個狀態來標記Cache Line 四個不同的狀態。

「已修改」狀態就是我們前面提到的髒標記,代表該Cache Block 上的數據已經被更新過,但是還沒有寫到內存裡。而「已失效」狀態,表示的是這個Cache Block 裡的數據已經失效了,不可以讀取該狀態的數據。

「獨占」和「共享」狀態都代表Cache Block 裡的數據是乾淨的,也就是說,這個時候Cache Block 裡的數據和內存裡面的數據是一致性的。

「獨占」和「共享」的差別在於,獨占狀態的時候,數據只存儲在一個CPU 核心的Cache 裡,而其他CPU 核心的Cache 沒有該數據。這個時候,如果要向獨占的Cache 寫數據,就可以直接自由地寫入,而不需要通知其他CPU 核心,因為只有你這有這個數據,就不存在緩存一致性的問題了,於是就可以隨便操作該數據。

另外,在「獨占」狀態下的數據,如果有其他核心從內存讀取了相同的數據到各自的Cache ,那麼這個時候,獨占狀態下的數據就會變成共享狀態。

那麼,「共享」狀態代表著相同的數據在多個CPU 核心的Cache 裡都有,所以當我們要更新Cache 裡面的數據的時候,不能直接修改,而是要先向所有的其他CPU 核心廣播一個請求,要求先把其他核心的Cache 中對應的Cache Line 標記為「無效」狀態,然後再更新當前Cache 裡面的數據。

我們舉個具體的例子來看看這四個狀態的轉換:

當A 號CPU 核心從內存讀取變量i 的值,數據被緩存在A 號CPU 核心自己的Cache 裡面,此時其他CPU 核心的Cache 沒有緩存該數據,於是標記Cache Line 狀態為「獨占」,此時其Cache 中的數據與內存是一致的;然後B 號CPU 核心也從內存讀取了變量i 的值,此時會發送消息給其他CPU 核心,由於A 號CPU 核心已經緩存了該數據,所以會把數據返回給B 號CPU 核心。在這個時候, A 和B 核心緩存了相同的數據,Cache Line 的狀態就會變成「共享」,並且其Cache 中的數據與內存也是一致的;當A 號CPU 核心要修改Cache 中i 變量的值,發現數據對應的Cache Line 的狀態是共享狀態,則要向所有的其他CPU 核心廣播一個請求,要求先把其他核心的Cache 中對應的Cache Line 標記為「無效」狀態,然後A 號CPU 核心才更新Cache 裡面的數據,同時標記Cache Line 為「已修改」狀態,此時Cache 中的數據就與內存不一致了。如果A 號CPU 核心「繼續」修改Cache 中i 變量的值,由於此時的Cache Line 是「已修改」狀態,因此不需要給其他CPU 核心發送消息,直接更新數據即可。如果A 號CPU 核心的Cache 裡的i 變量對應的Cache Line 要被「替換」,發現Cache Line 狀態是「已修改」狀態,就會在替換前先把數據同步到內存。

所以,可以發現當Cache Line 狀態是「已修改」或者「獨占」狀態時,修改更新其數據不需要發送廣播給其他CPU 核心,這在一定程度上減少了總線帶寬壓力。

事實上,整個MESI 的狀態可以用一個有限狀態機來表示它的狀態流轉。還有一點,對於不同狀態觸發的事件操作,可能是來自本地CPU 核心發出的廣播事件,也可以是來自其他CPU 核心通過總線發出的廣播事件。下圖即是MESI 協議的狀態圖:

10 張圖打開CPU 緩存一致性的大門 10

MESI 協議的四種狀態之間的流轉過程,我匯總成了下面的表格,你可以更詳細的看到每個狀態轉換的原因:

10 張圖打開CPU 緩存一致性的大門 11

總結

CPU 在讀寫數據的時候,都是在CPU Cache 讀寫數據的,原因是Cache 離CPU 很近,讀寫性能相比內存高出很多。對於Cache 裡沒有緩存CPU 所需要讀取的數據的這種情況,CPU 則會從內存讀取數據,並將數據緩存到Cache 裡面,最後CPU 再從Cache 讀取數據。

而對於數據的寫入,CPU 都會先寫入到Cache 裡面,然後再在找個合適的時機寫入到內存,那就有「寫直達」和「寫回」這兩種策略來保證Cache 與內存的數據一致性:

寫直達,只要有數據寫入,都會直接把數據寫入到內存裡面,這種方式簡單直觀,但是性能就會受限於內存的訪問速度;寫回,對於已經緩存在Cache 的數據的寫入,只需要更新其數據就可以,不用寫入到內存,只有在需要把緩存裡面的髒數據交換出去的時候,才把數據同步到內存裡,這種方式在緩存命中率高的情況,性能會更好;

當今CPU 都是多核的,每個核心都有各自獨立的L1/L2 Cache,只有L3 Cache 是多個核心之間共享的。所以,我們要確保多核緩存是一致性的,否則會出現錯誤的結果。

要想實現緩存一致性,關鍵是要滿足2 點:

第一點是寫傳播,也就是當某個CPU 核心發生寫入操作時,需要把該事件廣播通知給其他核心;第二點是事物的串行化,這個很重要,只有保證了這個,次啊能保障我們的數據是真正一致的,我們的程序在各個不同的核心上運行的結果也是一致的;

基於總線嗅探機制的MESI 協議,就滿足上面了這兩點,因此它是保障緩存一致性的協議。

MESI 協議,是已修改、獨占、共享、已實現這四個狀態的英文縮寫的組合。整個MSI 狀態的變更,則是根據來自本地CPU 核心的請求,或者來自其他CPU 核心通過總線傳輸過來的請求,從而構成一個流動的狀態機。另外,對於在「已修改」或者「獨占」狀態的Cache Line,修改更新其數據不需要發送廣播給其他CPU 核心。

說幾句

10 張圖打開CPU 緩存一致性的大門 12

哈嘍,我是小林,就愛圖解計算機基礎,如果覺得文章對你有幫助,歡迎分享給你的朋友,也給小林點個「在看」,這對小林非常重要,謝謝你們,給各位小姐姐小哥哥們抱拳了,我們下次見!

推薦閱讀

面試官:如何寫出讓CPU 跑得更快的代碼?

讀者問:小林你的500 張圖是怎麼畫的?