CPU緩存一致性協(xié)議解析

CPU運(yùn)行效率高不高，一定程度取決于緩存，這里就給大家分享一下CPU緩存相關(guān)的內(nèi)容。

CPU高速緩存（Cache Memory）

CPU為何要有高速緩存

CPU在摩爾定律的指導(dǎo)下以每18個(gè)月翻一番的速度在發(fā)展，然而內(nèi)存和硬盤(pán)的發(fā)展速度遠(yuǎn)遠(yuǎn)不及CPU。這就造成了高性能能的內(nèi)存和硬盤(pán)價(jià)格及其昂貴。然而CPU的高度運(yùn)算需要高速的數(shù)據(jù)。為了解決這個(gè)問(wèn)題，CPU廠商在CPU中內(nèi)置了少量的高速緩存以解決IO速度和CPU運(yùn)算速度之間的不匹配問(wèn)題。 在CPU訪問(wèn)存儲(chǔ)設(shè)備時(shí)，無(wú)論是存取數(shù)據(jù)抑或存取指令，都趨于聚集在一片連續(xù)的區(qū)域中，這就被稱為局部性原理。

時(shí)間局部性（Temporal Locality）：如果一個(gè)信息項(xiàng)正在被訪問(wèn)，那么在近期它很可能還會(huì)被再次訪問(wèn)。

比如循環(huán)、遞歸、方法的反復(fù)調(diào)用等。

空間局部性（Spatial Locality）：如果一個(gè)存儲(chǔ)器的位置被引用，那么將來(lái)他附近的位置也會(huì)被引用。

比如順序執(zhí)行的代碼、連續(xù)創(chuàng)建的兩個(gè)對(duì)象、數(shù)組等。

帶有高速緩存的CPU執(zhí)行計(jì)算的流程

程序以及數(shù)據(jù)被加載到主內(nèi)存

指令和數(shù)據(jù)被加載到CPU的高速緩存

CPU執(zhí)行指令，把結(jié)果寫(xiě)到高速緩存

高速緩存中的數(shù)據(jù)寫(xiě)回主內(nèi)存

目前流行的多級(jí)緩存結(jié)構(gòu)

由于CPU的運(yùn)算速度超越了1級(jí)緩存的數(shù)據(jù)IO能力，CPU廠商又引入了多級(jí)的緩存結(jié)構(gòu)。

多級(jí)緩存結(jié)構(gòu)

多核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ù)的單元。

狀態(tài) 描述 監(jiān)聽(tīng)任務(wù)

M 修改 (Modified)	該Cache line有效，數(shù)據(jù)被修改了，和內(nèi)存中的數(shù)據(jù)不一致，數(shù)據(jù)只存在于本Cache中。	緩存行必須時(shí)刻監(jiān)聽(tīng)所有試圖讀該緩存行相對(duì)就主存的操作，這種操作必須在緩存將該緩存行寫(xiě)回主存并將狀態(tài)變成S（共享）狀態(tài)之前被延遲執(zhí)行。
E 獨(dú)享、互斥 (Exclusive)	該Cache line有效，數(shù)據(jù)和內(nèi)存中的數(shù)據(jù)一致，數(shù)據(jù)只存在于本Cache中。	緩存行也必須監(jiān)聽(tīng)其它緩存讀主存中該緩存行的操作，一旦有這種操作，該緩存行需要變成S（共享）狀態(tài)。
S 共享 (Shared)	該Cache line有效，數(shù)據(jù)和內(nèi)存中的數(shù)據(jù)一致，數(shù)據(jù)存在于很多Cache中。	緩存行也必須監(jiān)聽(tīng)其它緩存使該緩存行無(wú)效或者獨(dú)享該緩存行的請(qǐng)求，并將該緩存行變成無(wú)效（Invalid）。
I 無(wú)效 (Invalid)	該Cache line無(wú)效。	無(wú)

注意： 對(duì)于M和E狀態(tài)而言總是精確的，他們?cè)诤驮摼彺嫘械恼嬲隣顟B(tài)是一致的，而S狀態(tài)可能是非一致的。如果一個(gè)緩存將處于S狀態(tài)的緩存行作廢了，而另一個(gè)緩存實(shí)際上可能已經(jīng)獨(dú)享了該緩存行，但是該緩存卻不會(huì)將該緩存行升遷為E狀態(tài)，這是因?yàn)槠渌彺娌粫?huì)廣播他們作廢掉該緩存行的通知，同樣由于緩存并沒(méi)有保存該緩存行的copy的數(shù)量，因此（即使有這種通知）也沒(méi)有辦法確定自己是否已經(jīng)獨(dú)享了該緩存行。 從上面的意義看來(lái)E狀態(tài)是一種投機(jī)性的優(yōu)化：如果一個(gè)CPU想修改一個(gè)處于S狀態(tài)的緩存行，總線事務(wù)需要將所有該緩存行的copy變成invalid狀態(tài)，而修改E狀態(tài)的緩存不需要使用總線事務(wù)。

MESI狀態(tài)轉(zhuǎn)換

理解該圖的前置說(shuō)明： 1.觸發(fā)事件 觸發(fā)事件 描述

本地讀?。↙ocal read）	本地cache讀取本地cache數(shù)據(jù)
本地寫(xiě)入（Local write）	本地cache寫(xiě)入本地cache數(shù)據(jù)
遠(yuǎn)端讀取（Remote read）	其他cache讀取本地cache數(shù)據(jù)
遠(yuǎn)端寫(xiě)入（Remote write）	其他cache寫(xiě)入本地cache數(shù)據(jù)

2.cache分類： 前提：所有的cache共同緩存了主內(nèi)存中的某一條數(shù)據(jù)。 本地cache:指當(dāng)前cpu的cache。 觸發(fā)cache:觸發(fā)讀寫(xiě)事件的cache。 其他cache:指既除了以上兩種之外的cache。 注意：本地的事件觸發(fā) 本地cache和觸發(fā)cache為相同。 上圖的切換解釋： 狀態(tài) 觸發(fā)本地讀取 觸發(fā)本地寫(xiě)入 觸發(fā)遠(yuǎn)端讀取 觸發(fā)遠(yuǎn)端寫(xiě)入

M狀態(tài)（修改）	本地cache:M 觸發(fā)cache:M 其他cache:I	本地cache:M 觸發(fā)cache:M 其他cache:I	本地cache:M→E→S 觸發(fā)cache:I→S 其他cache:I→S 同步主內(nèi)存后修改為E獨(dú)享,同步觸發(fā)、其他cache后本地、觸發(fā)、其他cache修改為S共享	本地cache:M→E→S→I 觸發(fā)cache:I→S→E→M 其他cache:I→S→I 同步和讀取一樣,同步完成后觸發(fā)cache改為M，本地、其他cache改為I
E狀態(tài)（獨(dú)享）	本地cache:E 觸發(fā)cache:E 其他cache:I	本地cache:E→M 觸發(fā)cache:E→M 其他cache:I 本地cache變更為M,其他cache狀態(tài)應(yīng)當(dāng)是I（無(wú)效）	本地cache:E→S 觸發(fā)cache:I→S 其他cache:I→S 當(dāng)其他cache要讀取該數(shù)據(jù)時(shí)，其他、觸發(fā)、本地cache都被設(shè)置為S(共享)	本地cache:E→S→I 觸發(fā)cache:I→S→E→M 其他cache:I→S→I 當(dāng)觸發(fā)cache修改本地cache獨(dú)享數(shù)據(jù)時(shí)時(shí)，將本地、觸發(fā)、其他cache修改為S共享.然后觸發(fā)cache修改為獨(dú)享，其他、本地cache修改為I（無(wú)效），觸發(fā)cache再修改為M
S狀態(tài)(共享)	本地cache:S 觸發(fā)cache:S 其他cache:S	本地cache:S→E→M 觸發(fā)cache:S→E→M 其他cache:S→I 當(dāng)本地cache修改時(shí)，將本地cache修改為E,其他cache修改為I,然后再將本地cache為M狀態(tài)	本地cache:S 觸發(fā)cache:S 其他cache:S	本地cache:S→I 觸發(fā)cache：S→E→M 其他cache:S→I 當(dāng)觸發(fā)cache要修改本地共享數(shù)據(jù)時(shí)，觸發(fā)cache修改為E（獨(dú)享）,本地、其他cache修改為I（無(wú)效）,觸發(fā)cache再次修改為M(修改)
I狀態(tài)（無(wú)效）	本地cache:I→S或者I→E 觸發(fā)cache:I→S或者I →E 其他cache:E、M、I→S、I 本地、觸發(fā)cache將從I無(wú)效修改為S共享或者E獨(dú)享，其他cache將從E、M、I 變?yōu)镾或者I	本地cache:I→S→E→M 觸發(fā)cache:I→S→E→M 其他cache:M、E、S→S→I	既然是本cache是I，其他cache操作與它無(wú)關(guān)	既然是本cache是I，其他cache操作與它無(wú)關(guān)

下圖示意了，當(dāng)一個(gè)cache line的調(diào)整的狀態(tài)的時(shí)候，另外一個(gè)cache line 需要調(diào)整的狀態(tài)。 M E S I

M	×	×	×	√
E	×	×	×	√
S	×	×	√	√
I	√	√	√	√

舉個(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。

單核讀取

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

雙核讀取

那么執(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)(共享)。

修改數(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)行賦值。

同步數(shù)據(jù)

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

MESI優(yōu)化和他們引入的問(wèn)題

緩存的一致性消息傳遞是要時(shí)間的，這就使其切換時(shí)會(huì)產(chǎn)生延遲。當(dāng)一個(gè)緩存被切換狀態(tài)時(shí)其他緩存收到消息完成各自的切換并且發(fā)出回應(yīng)消息這么一長(zhǎng)串的時(shí)間中CPU都會(huì)等待所有緩存響應(yīng)完成?？赡艹霈F(xiàn)的阻塞都會(huì)導(dǎo)致各種各樣的性能問(wèn)題和穩(wěn)定性問(wèn)題。

CPU切換狀態(tài)阻塞解決-存儲(chǔ)緩存（Store Bufferes）

比如你需要修改本地緩存中的一條信息，那么你必須將I（無(wú)效）狀態(tài)通知到其他擁有該緩存數(shù)據(jù)的CPU緩存中，并且等待確認(rèn)。等待確認(rèn)的過(guò)程會(huì)阻塞處理器，這會(huì)降低處理器的性能。應(yīng)為這個(gè)等待遠(yuǎn)遠(yuǎn)比一個(gè)指令的執(zhí)行時(shí)間長(zhǎng)的多。

Store Bufferes

為了避免這種CPU運(yùn)算能力的浪費(fèi)，Store Bufferes被引入使用。處理器把它想要寫(xiě)入到主存的值寫(xiě)到緩存，然后繼續(xù)去處理其他事情。當(dāng)所有失效確認(rèn)（Invalidate Acknowledge）都接收到時(shí)，數(shù)據(jù)才會(huì)最終被提交。 這么做有兩個(gè)風(fēng)險(xiǎn)

Store Bufferes的風(fēng)險(xiǎn)

第一、就是處理器會(huì)嘗試從存儲(chǔ)緩存（Store buffer）中讀取值，但它還沒(méi)有進(jìn)行提交。這個(gè)的解決方案稱為Store Forwarding，它使得加載的時(shí)候，如果存儲(chǔ)緩存中存在，則進(jìn)行返回。 第二、保存什么時(shí)候會(huì)完成，這個(gè)并沒(méi)有任何保證。

value = 3； void exeToCPUA(){ value = 10; isFinsh = true; } void exeToCPUB(){ if(isFinsh){ //value一定等于10？！ assert value == 10; } } 試想一下開(kāi)始執(zhí)行時(shí)，CPU A保存著finished在E(獨(dú)享)狀態(tài)，而value并沒(méi)有保存在它的緩存中。（例如，Invalid）。在這種情況下，value會(huì)比f(wàn)inished更遲地拋棄存儲(chǔ)緩存。完全有可能CPU B讀取finished的值為true，而value的值不等于10。 即isFinsh的賦值在value賦值之前。 這種在可識(shí)別的行為中發(fā)生的變化稱為重排序（reordings）。注意，這不意味著你的指令的位置被惡意（或者好意）地更改。 它只是意味著其他的CPU會(huì)讀到跟程序中寫(xiě)入的順序不一樣的結(jié)果。 順便提一下NIO的設(shè)計(jì)和Store Bufferes的設(shè)計(jì)是非常相像的。

硬件內(nèi)存模型

執(zhí)行失效也不是一個(gè)簡(jiǎn)單的操作，它需要處理器去處理。另外，存儲(chǔ)緩存（Store Buffers）并不是無(wú)窮大的，所以處理器有時(shí)需要等待失效確認(rèn)的返回。這兩個(gè)操作都會(huì)使得性能大幅降低。為了應(yīng)付這種情況，引入了失效隊(duì)列。它們的約定如下：

對(duì)于所有的收到的Invalidate請(qǐng)求，Invalidate Acknowlege消息必須立刻發(fā)送

Invalidate并不真正執(zhí)行，而是被放在一個(gè)特殊的隊(duì)列中，在方便的時(shí)候才會(huì)去執(zhí)行。

處理器不會(huì)發(fā)送任何消息給所處理的緩存條目，直到它處理Invalidate。

即便是這樣處理器已然不知道什么時(shí)候優(yōu)化是允許的，而什么時(shí)候并不允許。 干脆處理器將這個(gè)任務(wù)丟給了寫(xiě)代碼的人。這就是內(nèi)存屏障（Memory Barriers）。

寫(xiě)屏障 Store Memory Barrier(a.k.a. ST, SMB, smp_wmb)是一條告訴處理器在執(zhí)行這之后的指令之前，應(yīng)用所有已經(jīng)在存儲(chǔ)緩存（store buffer）中的保存的指令。

讀屏障Load Memory Barrier (a.k.a. LD, RMB, smp_rmb)是一條告訴處理器在執(zhí)行任何的加載前，先應(yīng)用所有已經(jīng)在失效隊(duì)列中的失效操作的指令。

void executedOnCpu0() {
    value = 10;
    //在更新數(shù)據(jù)之前必須將所有存儲(chǔ)緩存（store buffer）中的指令執(zhí)行完畢。
    storeMemoryBarrier();
    finished = true;
}
void executedOnCpu1() {
    while(!finished);
    //在讀取之前將所有失效隊(duì)列中關(guān)于該數(shù)據(jù)的指令執(zhí)行完畢。
    loadMemoryBarrier();
    assert value == 10;
}

現(xiàn)在確實(shí)安全了。完美無(wú)暇！