先來(lái)一個(gè)整體圖：

image.png

一.cpu和內(nèi)存的關(guān)系

大致關(guān)系： CPU Cache --> 前端總線 FSB (下圖中的Bus) --> Memory 內(nèi)存

CPU 為了更快的執(zhí)行代碼。于是當(dāng)從內(nèi)存中讀取數(shù)據(jù)時(shí)，并不是只讀自己想要的部分。而是讀取足夠的字節(jié)來(lái)填入高速緩存行(緩存預(yù)讀性原理)。根據(jù)不同的 CPU ，高速緩存行大小不同。如 X86 是 32BYTES ，而 ALPHA 是 64BYTES 。并且始終在第 32 個(gè)字節(jié)或第 64 個(gè)字節(jié)處對(duì)齊(內(nèi)存對(duì)齊)。這樣，當(dāng) CPU 訪問(wèn)相鄰的數(shù)據(jù)時(shí)，就不必每次都從內(nèi)存中讀取，提高了速度。 因?yàn)樵L問(wèn)內(nèi)存要比訪問(wèn)高速緩存用的時(shí)間多得多。

下面一張圖可以看出各級(jí)緩存之間的響應(yīng)時(shí)間差距，以及內(nèi)存到底有多慢！

image.png

二. CPU Cache和Cache Line

什么是Cache Line

Cache Line可以簡(jiǎn)單的理解為CPU Cache中的最小緩存單位。目前主流的CPU Cache的Cache Line大小都是64Bytes。假設(shè)我們有一個(gè)512字節(jié)的一級(jí)緩存，那么按照64B的緩存單位大小來(lái)算，這個(gè)一級(jí)緩存所能存放的緩存?zhèn)€數(shù)就是512/64 = 8個(gè)。具體參見下圖：

image.png

例子：一段邏輯代碼，會(huì)從命令行接收一個(gè)參數(shù)作為數(shù)組的大小創(chuàng)建一個(gè)數(shù)量為N的int數(shù)組。并依次循環(huán)的從這個(gè)數(shù)組中進(jìn)行數(shù)組內(nèi)容訪問(wèn)，循環(huán)10億次。最終輸出數(shù)組總大小和對(duì)應(yīng)總執(zhí)行時(shí)間。

如果我們把這些數(shù)據(jù)做成折線圖后就會(huì)發(fā)現(xiàn)：總執(zhí)行時(shí)間在數(shù)組大小超過(guò)64Bytes時(shí)有較為明顯的拐點(diǎn)。原因是當(dāng)數(shù)組小于64Bytes時(shí)數(shù)組極有可能落在一條Cache Line內(nèi)，而一個(gè)元素的訪問(wèn)就會(huì)使得整條Cache Line被填充，因而使得后面的若干個(gè)元素受益于緩存帶來(lái)的加速。而當(dāng)數(shù)組大于64Bytes時(shí)，必然至少需要兩條Cache Line，繼而在循環(huán)訪問(wèn)時(shí)會(huì)出現(xiàn)兩次Cache Line的填充，由于緩存填充的時(shí)間遠(yuǎn)高于數(shù)據(jù)訪問(wèn)的響應(yīng)時(shí)間，因此多一次緩存填充對(duì)于總執(zhí)行的影響會(huì)被放大，最終得到下圖的結(jié)果：

image.png

我們來(lái)看下面這個(gè)C語(yǔ)言中常用的循環(huán)優(yōu)化例子
下面兩段代碼中，第一段代碼在C語(yǔ)言中總是比第二段代碼的執(zhí)行速度要快。具體的原因相信你仔細(xì)閱讀了Cache Line的介紹后就很容易理解了。

for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
        int num;   
        arr[i][j] = num;
    }
}
//在內(nèi)存中順序填充數(shù)組，會(huì)在cpu緩存行中也順序填充

for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
        int   num;       
        arr[j][i] = num;
    }
}
////在內(nèi)存中不連續(xù)填充，會(huì)在多個(gè)cpu緩存行中填充

三. 下面看CPU Cache與Memory關(guān)系圖

image.png

上述左圖是最簡(jiǎn)單的高速緩存的圖示，數(shù)據(jù)的讀取和存儲(chǔ)都經(jīng)過(guò)高速緩存，CPU核心和高速緩存之間有一條特殊的快速通道，在這個(gè)簡(jiǎn)化的圖示上，主存（main memory）與高速緩存（cache）都連在系統(tǒng)總線上。這條總線同時(shí)還用于其他組件之間的通信。在高速緩存出現(xiàn)后不久，系統(tǒng)變得更加復(fù)雜，高速緩存與主存之間的速度差異被拉大，直到加入了另一級(jí)的緩存（由于加大一級(jí)緩存的做法從經(jīng)濟(jì)上考慮是行不通的，所以有了二級(jí)緩存甚至三級(jí)緩存）。新加入的這些緩存比第一緩存更大但是更慢。

多核發(fā)達(dá)的年代。情況就不能那么簡(jiǎn)單了。試想下面這樣一個(gè)情況。

1、CPU1 讀取了一個(gè)字節(jié)，以及它和它相鄰的字節(jié)被讀入 CPU1 的高速緩存。
2、CPU2 做了上面同樣的工作。這樣 CPU1 ， CPU2 的高速緩存擁有同樣的數(shù)據(jù)。
3、CPU1 修改了那個(gè)字節(jié)，被修改后，那個(gè)字節(jié)被放回 CPU1 的高速緩存行。但是該信息并沒(méi)有被寫入 RAM 。
4、CPU2 訪問(wèn)該字節(jié)，但由于 CPU1 并未將數(shù)據(jù)寫入 RAM ，導(dǎo)致了數(shù)據(jù)不同步。

為了解決這個(gè)問(wèn)題，芯片設(shè)計(jì)者制定了一個(gè)規(guī)則。當(dāng)一個(gè) CPU 修改高速緩存行中的字節(jié)時(shí)，計(jì)算機(jī)中的其它 CPU 會(huì)被通知，它們的高速緩存將視為無(wú)效。于是，在上面的情況下， CPU2 發(fā)現(xiàn)自己的高速緩存中數(shù)據(jù)已無(wú)效， CPU1 將立即把自己的數(shù)據(jù)寫回 RAM ，然后 CPU2 重新讀取該數(shù)據(jù)。 可以看出，高速緩存行在多處理器上會(huì)導(dǎo)致一些不利。

四. 多核CPU多級(jí)緩存一致性協(xié)議MESI

多核CPU的情況下有多個(gè)一級(jí)緩存，如何保證緩存內(nèi)部數(shù)據(jù)的一致,不讓系統(tǒng)數(shù)據(jù)混亂。這里就引出了一個(gè)一致性的協(xié)議MESI。

MESI協(xié)議緩存狀態(tài)

MESI 是指4種狀態(tài)的首字母。每個(gè)Cache line有4個(gè)狀態(tài)，可用2個(gè)bit表示，它們分別是：

緩存行（Cache line）:緩存存儲(chǔ)數(shù)據(jù)的單元。

image.png

舉個(gè)栗子來(lái)說(shuō)：

假設(shè)cache 1 中有一個(gè)變量x = 0的cache line 處于S狀態(tài)(共享)。
那么其他擁有x變量的cache 2、cache 3等x的cache line調(diào)整為S狀態(tài)（共享）或者調(diào)整為 I 狀態(tài)（無(wú)效）。

多核緩存協(xié)同操作

假設(shè)有三個(gè)CPU A、B、C，對(duì)應(yīng)三個(gè)緩存分別是cache a、b、 c。在主內(nèi)存中定義了x的引用值為0。

image.png

單核讀取
那么執(zhí)行流程是：
CPU A發(fā)出了一條指令，從主內(nèi)存中讀取x。
從主內(nèi)存通過(guò)bus讀取到緩存中（遠(yuǎn)端讀取Remote read）,這是該Cache line修改為E狀態(tài)（獨(dú)享）.

image.png

雙核讀取
那么執(zhí)行流程是：
CPU A發(fā)出了一條指令，從主內(nèi)存中讀取x。
CPU A從主內(nèi)存通過(guò)bus讀取到 cache a中并將該cache line 設(shè)置為E狀態(tài)。
CPU B發(fā)出了一條指令，從主內(nèi)存中讀取x。
CPU B試圖從主內(nèi)存中讀取x時(shí)，CPU A檢測(cè)到了地址沖突。這時(shí)CPU A對(duì)相關(guān)數(shù)據(jù)做出響應(yīng)。此時(shí)x 存儲(chǔ)于cache a和cache b中，x在chche a和cache b中都被設(shè)置為S狀態(tài)(共享)。

image.png

修改數(shù)據(jù)
那么執(zhí)行流程是：
CPU A 計(jì)算完成后發(fā)指令需要修改x.
CPU A 將x設(shè)置為M狀態(tài)（修改）并通知緩存了x的CPU B, CPU B將本地cache b中的x設(shè)置為I狀態(tài)(無(wú)效)
CPU A 對(duì)x進(jìn)行賦值。

image.png

同步數(shù)據(jù)
那么執(zhí)行流程是：

CPU B 發(fā)出了要讀取x的指令。
CPU B 通知CPU A,CPU A將修改后的數(shù)據(jù)同步到主內(nèi)存并且cache a 修改為E（獨(dú)享）
CPU A同步CPU B的x,將cache a和同步后cache b中的x設(shè)置為S狀態(tài)（共享）。

image.png

五. Cache淘汰策略

常見的淘汰策略主要有LRU和Random兩種。通常意義下LRU對(duì)于Cache的命中率會(huì)比Random更好，所以CPU Cache的淘汰策略選擇的是LRU。當(dāng)然也有些實(shí)驗(yàn)顯示在Cache Size較大的時(shí)候Random策略會(huì)有更高的命中率。