姓名：韓宜真

學(xué)號(hào)：17020120095

轉(zhuǎn)載自：https://mp.weixin.qq.com/s/7GKYgtTfENJfRN4NtYvS_w

【嵌牛導(dǎo)讀】本文介紹了?CPU 高速緩存方法。

【嵌牛鼻子】獨(dú)占狀態(tài) 共享狀態(tài)

【嵌牛提問(wèn)】?這種CPU 高速緩存方法是如何實(shí)現(xiàn)的？

【嵌牛正文】

來(lái)看 3 行代碼障斋，比較一下兩個(gè)循環(huán)運(yùn)行所花的時(shí)間旧找。

int[] arr =newint[64*1024*1024];

// 循環(huán)1

for(inti =0; i < arr.length; i++) arr[i] *=3;

// 循環(huán)2

for(inti =0; i < arr.length; i +=16) arr[i] *=3

按道理來(lái)說(shuō)浴韭，循環(huán)1 花費(fèi)的時(shí)間應(yīng)該是循環(huán)2 的 16 倍左右核畴。但實(shí)際上域慷，循環(huán)1 在我的電腦上運(yùn)行需要 50 毫秒严就，循環(huán)2 只需要 46 毫秒总寻。相差在 15% 之內(nèi)，1 倍都沒(méi)有梢为。

這就是 CPU Cache （高速緩存）帶來(lái)的效果渐行。

程序執(zhí)行時(shí)，CPU 將對(duì)應(yīng)的數(shù)據(jù)從內(nèi)存中讀取出來(lái)铸董，加載到 CPU Cache 里祟印。這里注意，CPU 是一小塊一小塊來(lái)讀取數(shù)據(jù)的粟害，而不是按照單個(gè)數(shù)組元素來(lái)讀取數(shù)據(jù)的蕴忆。

這一小塊一小塊的數(shù)據(jù)，在 CPU Cache 里面悲幅，我們把它叫作 Cache Line（緩存塊）套鹅。

日常用的 Intel 服務(wù)器或者 PC 中，Cache Line 的大小通常是 64 字節(jié)汰具。

上面的循環(huán)2 里面卓鹿，每隔 16 個(gè)整型數(shù)計(jì)算一次，16 個(gè)整型數(shù)正好是 64 個(gè)字節(jié)留荔。所以减牺，循環(huán)1 和循環(huán)2，都需要把同樣數(shù)量的 Cache Line 數(shù)據(jù)從內(nèi)存中讀取到 CPU Cache 中，導(dǎo)致兩個(gè)程序花費(fèi)的時(shí)間就差別不大了拔疚。

CPU Cache 一般有三層肥隆，L1/L2 單核私有，L3 多核共享緩存(這里的 L1-L3 指特定的由 SRAM 組成的物理芯片稚失，不是概念上的緩存)栋艳。有了 CPU Cache，內(nèi)存中的指令句各、數(shù)據(jù)吸占，會(huì)被加載到 L1-L3 Cache 中，95% 的情況下凿宾，CPU 都只需要訪問(wèn) L1-L3 Cache矾屯，而無(wú)需訪問(wèn)內(nèi)存。

Cpu Cache 讀取數(shù)據(jù)

現(xiàn)代 CPU 進(jìn)行數(shù)據(jù)讀取的時(shí)候初厚，無(wú)論數(shù)據(jù)是否已經(jīng)存儲(chǔ)在 Cache 中件蚕，CPU 始終會(huì)首先訪問(wèn) Cache。只有當(dāng) CPU 在 Cache 中找不到數(shù)據(jù)的時(shí)候产禾，才會(huì)去訪問(wèn)內(nèi)存排作，并將讀取到的數(shù)據(jù)寫(xiě)入 Cache 之中。

那么亚情，Cache 如何根據(jù)內(nèi)存地址定位到數(shù)據(jù)呢妄痪？

根據(jù)內(nèi)存地址的低位，計(jì)算在 Cache 中的索引楞件；

判斷有效位衫生，確認(rèn) Cache 中的數(shù)據(jù)是有效的；

對(duì)比內(nèi)存地址的高位土浸，和 Cache 中的組標(biāo)記障簿，確認(rèn) Cache 中的數(shù)據(jù)就是我們要訪問(wèn)的內(nèi)存數(shù)據(jù)，從 Cache Line 中讀取到對(duì)應(yīng)的數(shù)據(jù)塊（Data Block）栅迄；

根據(jù)內(nèi)存地址的Offset位站故，從Data Block中，讀取希望讀取到的字

如果在2毅舆、3這兩個(gè)步驟中西篓，CPU 發(fā)現(xiàn)，Cache 中的數(shù)據(jù)并不是要訪問(wèn)的內(nèi)存地址的數(shù)據(jù)憋活，那 CPU 就會(huì)訪問(wèn)內(nèi)存岂津，并把對(duì)應(yīng)的 Block Data 更新到 Cache Line 中，同時(shí)更新對(duì)應(yīng)的有效位和組標(biāo)記的數(shù)據(jù)悦即。

總結(jié)一下吮成，一個(gè)內(nèi)存的訪問(wèn)地址橱乱，最終包括高位代表的組標(biāo)記、低位代表的索引粱甫，以及在對(duì)應(yīng)的Data Block中定位對(duì)應(yīng)字的位置偏移量泳叠。

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

當(dāng) Cpu 要寫(xiě)入數(shù)據(jù)時(shí)，到底是寫(xiě) Cache 還是寫(xiě)主存呢茶宵，如何保證一致性呢危纫？

這里介紹兩種寫(xiě)入策略。

1. 寫(xiě)直達(dá)（Write-Through）

寫(xiě)入前乌庶，我們會(huì)先去判斷數(shù)據(jù)是否已經(jīng)在 Cache 里面了种蝶。如果數(shù)據(jù)已經(jīng)在 Cache 里面了，我們先把數(shù)據(jù)寫(xiě)入更新到 Cache 里面瞒大，再寫(xiě)入到主內(nèi)存里面螃征；如果數(shù)據(jù)不在 Cache 里，我們就只更新主內(nèi)存透敌。

這個(gè)策略很直觀盯滚，但是問(wèn)題也很明顯，那就是這個(gè)策略很慢拙泽。無(wú)論數(shù)據(jù)是不是在 Cache 里面，我們都需要把數(shù)據(jù)寫(xiě)到主內(nèi)存里面裸燎。這個(gè)方式就有點(diǎn)兒像 Java 里 volatile 關(guān)鍵字顾瞻，始終都要把數(shù)據(jù)同步到主內(nèi)存里面。

2. 寫(xiě)回（Write-Back）

如果要寫(xiě)入的數(shù)據(jù)德绿，就在 CPU Cache 里面荷荤，那么就只更新 CPU Cache 里面的數(shù)據(jù)。同時(shí)標(biāo)記 CPU Cache 里的這個(gè) Block 是臟（Dirty）的移稳。就是這個(gè)時(shí)候蕴纳，CPU Cache 里的這個(gè) Block 的數(shù)據(jù)，和主內(nèi)存是不一致的个粱。

如果要寫(xiě)入的數(shù)據(jù)所對(duì)應(yīng)的 Cache Block 里古毛，放的是別的內(nèi)存地址的數(shù)據(jù)，那么就要看一看都许，Cache Block 里的數(shù)據(jù)有沒(méi)有被標(biāo)記成臟的稻薇。如果是臟的，要先把這個(gè) Cache Block 里面的數(shù)據(jù)胶征，寫(xiě)入到主內(nèi)存里面塞椎。然后，再把當(dāng)前要寫(xiě)入的數(shù)據(jù)睛低，寫(xiě)入到 Cache 里案狠，同時(shí)把 Cache Block 標(biāo)記成臟的服傍。如果 Block 里面的數(shù)據(jù)沒(méi)有被標(biāo)記成臟的，那么我們直接把數(shù)據(jù)寫(xiě)入到 Cache 里面骂铁，然后再把 Cache Block 標(biāo)記成臟的就好了吹零。

然而，無(wú)論是寫(xiě)回還是寫(xiě)直達(dá)从铲，都沒(méi)有解決多線程瘪校，或者是多個(gè) CPU 核的緩存一致性的問(wèn)題。

這也就是我們?cè)趯?xiě)入修改緩存后名段，需要解決的第二個(gè)問(wèn)題阱扬。

要解決這個(gè)問(wèn)題，我們需要引入一個(gè)新的方法伸辟，叫作 MESI 協(xié)議麻惶。這是一個(gè)維護(hù)緩存一致性協(xié)議。這個(gè)協(xié)議不僅可以用在 CPU Cache 之間信夫，也可以廣泛用于各種需要使用緩存窃蹋，同時(shí)緩存之間需要同步的場(chǎng)景下。

因?yàn)槎嗪?CPU Cache 在 L3 緩存是共享的静稻，所以一致性問(wèn)題警没，只會(huì)出現(xiàn)在 L1/L2 級(jí)這種單核私有緩存的場(chǎng)景中。

我們需要有一種機(jī)制振湾，來(lái)同步兩個(gè)不同核心里面的緩存數(shù)據(jù)杀迹。這樣的機(jī)制需要滿足兩點(diǎn)：

第一點(diǎn)叫寫(xiě)傳播（Write Propagation）。寫(xiě)傳播是說(shuō)押搪，在一個(gè)CPU核心里树酪，我們的Cache數(shù)據(jù)更新，必須能夠傳播到其他的對(duì)應(yīng)節(jié)點(diǎn)的Cache Line里大州。

第二點(diǎn)叫事務(wù)的串行化（Transaction Serialization）续语，事務(wù)串行化是說(shuō)，我們?cè)谝粋€(gè)CPU核心里面的讀取和寫(xiě)入厦画，在其他的節(jié)點(diǎn)看起來(lái)疮茄，順序是一樣的。

CPU Cache 里做到事務(wù)串行化根暑，需要做到兩點(diǎn)娃豹，第一點(diǎn)是一個(gè) CPU 核心對(duì)于數(shù)據(jù)的操作，需要同步通信給到其他 CPU 核心购裙。第二點(diǎn)是懂版，如果兩個(gè) CPU 核心里有同一個(gè)數(shù)據(jù)的 Cache，那么對(duì)于這個(gè) Cache 數(shù)據(jù)的更新躏率，需要有一個(gè)“鎖”的概念躯畴。只有拿到了對(duì)應(yīng) Cache Block 的“鎖”之后民鼓，才能進(jìn)行對(duì)應(yīng)的數(shù)據(jù)更新。接下來(lái)蓬抄，我們就看看實(shí)現(xiàn)了這兩個(gè)機(jī)制的 MESI 協(xié)議丰嘉。

MESI 協(xié)議，是一種叫作寫(xiě)失效（Write Invalidate）的協(xié)議嚷缭。在寫(xiě)失效協(xié)議里饮亏，只有一個(gè) CPU 核心負(fù)責(zé)寫(xiě)入數(shù)據(jù)，其他的核心阅爽，只是同步讀取到這個(gè)寫(xiě)入路幸。在這個(gè) CPU 核心寫(xiě)入 Cache 之后，它會(huì)去廣播一個(gè)“失效”請(qǐng)求告訴所有其他的 CPU 核心付翁。其他的 CPU 核心简肴，只是去判斷自己是否也有一個(gè)“失效”版本的 Cache Block，然后把這個(gè)也標(biāo)記成失效的就好了百侧。

MESI協(xié)議的由來(lái)呢砰识，來(lái)自于我們對(duì) Cache Line 的四個(gè)不同的標(biāo)記，分別是：

M：代表已修改（Modified） E：代表獨(dú)占（Exclusive） S：代表共享（Shared） I：代表已失效（Invalidated）

我們先來(lái)看看“已修改”和“已失效”佣渴，這兩個(gè)狀態(tài)比較容易理解辫狼。所謂的“已修改”，就是我們上一講所說(shuō)的“臟”的 Cache Block辛润。Cache Block 里面的內(nèi)容我們已經(jīng)更新過(guò)了膨处，但是還沒(méi)有寫(xiě)回到主內(nèi)存里面。而所謂的“已失效“频蛔，自然是這個(gè) Cache Block 里面的數(shù)據(jù)已經(jīng)失效了灵迫，我們不可以相信這個(gè) Cache Block 里面的數(shù)據(jù)秦叛。

然后晦溪，我們?cè)賮?lái)看“獨(dú)占”和“共享”這兩個(gè)狀態(tài)。這就是 MESI 協(xié)議的精華所在了挣跋。無(wú)論是獨(dú)占狀態(tài)還是共享狀態(tài)三圆，緩存里面的數(shù)據(jù)都是“干凈”的。這個(gè)“干凈”避咆，自然對(duì)應(yīng)的是前面所說(shuō)的“臟”的舟肉，也就是說(shuō)，這個(gè)時(shí)候查库，Cache Block 里面的數(shù)據(jù)和主內(nèi)存里面的數(shù)據(jù)是一致的路媚。

那么“獨(dú)占”和“共享”這兩個(gè)狀態(tài)的差別在哪里呢？這個(gè)差別就在于樊销，在獨(dú)占狀態(tài)下整慎，對(duì)應(yīng)的 Cache Line 只加載到了當(dāng)前 CPU 核所擁有的 Cache 里脏款。其他的 CPU 核，并沒(méi)有加載對(duì)應(yīng)的數(shù)據(jù)到自己的 Cache 里裤园。這個(gè)時(shí)候撤师，如果要向獨(dú)占的 Cache Block 寫(xiě)入數(shù)據(jù)，我們可以自由地寫(xiě)入數(shù)據(jù)拧揽，而不需要告知其他 CPU 核剃盾。

在獨(dú)占狀態(tài)下的數(shù)據(jù)，如果收到了一個(gè)來(lái)自于總線的讀取對(duì)應(yīng)緩存的請(qǐng)求淤袜，它就會(huì)變成共享狀態(tài)痒谴。這個(gè)共享狀態(tài)是因?yàn)椋@個(gè)時(shí)候饮怯，另外一個(gè) CPU 核心闰歪，也把對(duì)應(yīng)的 Cache Block，從內(nèi)存里面加載到了自己的 Cache 里來(lái)蓖墅。

而在共享狀態(tài)下库倘，因?yàn)橥瑯拥臄?shù)據(jù)在多個(gè) CPU 核心的 Cache 里都有。所以论矾，當(dāng)我們想要更新 Cache 里面的數(shù)據(jù)的時(shí)候教翩，不能直接修改，而是要先向所有的其他 CPU 核心廣播一個(gè)請(qǐng)求贪壳，要求先把其他 CPU 核心里面的 Cache饱亿，都變成無(wú)效的狀態(tài)，然后再更新當(dāng)前 Cache 里面的數(shù)據(jù)闰靴。這個(gè)廣播操作彪笼，一般叫作 RFO（Request For Ownership），也就是獲取當(dāng)前對(duì)應(yīng) Cache Block 數(shù)據(jù)的所有權(quán)蚂且。

有沒(méi)有覺(jué)得這個(gè)操作有點(diǎn)兒像我們?cè)诙嗑€程里面用到的讀寫(xiě)鎖配猫。在共享狀態(tài)下，大家都可以并行去讀對(duì)應(yīng)的數(shù)據(jù)杏死。但是如果要寫(xiě)泵肄，我們就需要通過(guò)一個(gè)鎖，獲取當(dāng)前寫(xiě)入位置的所有權(quán)淑翼。

整個(gè) MESI 的狀態(tài)腐巢，可以用一個(gè)有限狀態(tài)機(jī)來(lái)表示它的狀態(tài)流轉(zhuǎn)。需要注意的是玄括，對(duì)于不同狀態(tài)觸發(fā)的事件操作冯丙，可能來(lái)自于當(dāng)前 CPU 核心，也可能來(lái)自總線里其他 CPU 核心廣播出來(lái)的信號(hào)遭京。我把對(duì)應(yīng)的狀態(tài)機(jī)流轉(zhuǎn)圖放在了下面胃惜，你可以對(duì)照著 Wikipedia 里面 MESI 的內(nèi)容风宁，仔細(xì)研讀一下。