一、高速緩存

高速緩存是一種存取速率遠(yuǎn)比主內(nèi)存大，而容量遠(yuǎn)比主內(nèi)存小的處理器存儲(chǔ)部件。引入高速緩存之后，處理器在執(zhí)行內(nèi)存讀、寫操作的時(shí)候并不直接與主內(nèi)存打交道，而是通過高速緩存進(jìn)行的。變量名相當(dāng)于內(nèi)存地址，而變量值則相當(dāng)于相應(yīng)內(nèi)存空間所存儲(chǔ)的數(shù)據(jù)。

高速緩存又可以分為指令緩存和數(shù)據(jù)緩存。指令緩存用來緩存程序的代碼，數(shù)據(jù)緩存用來緩存程序的數(shù)據(jù)。

1. 【一級(jí)緩存(L1 Cache)】本地 core 的緩存，分成 32K 的數(shù)據(jù)緩存 L1d 和 32k 指令緩存 L1i，訪問 L1 需要 3 cycles，耗時(shí)大約 1ns。
2. 【二級(jí)緩存(L2 Cache)】本地 core 的緩存，被設(shè)計(jì)為 L1 緩存與共享的 L3 緩存之間的緩沖。大小為 256K，訪問 L2 需要 12 cycles，耗時(shí)大約 3ns。
3. 【三級(jí)緩存(L3 Cache)】在同插槽的所有 core 共享 L3 緩存，分為多個(gè) 2M 的段，訪問 L3 需要 38 cycles，耗時(shí)大約 12ns。

一級(jí)緩存可能直接被集成在處理器的內(nèi)核里，因此訪問效率非常高。通常包括兩部分，一部分用于存儲(chǔ)指令，一部分用于存儲(chǔ)數(shù)據(jù)，距離處理器越近的高速緩存，存儲(chǔ)速率越快，制造成本越高，容量越小。

1. Tag 包含了與緩存行中數(shù)據(jù)相應(yīng)的內(nèi)存地址的部分信息(內(nèi)存地址的高位部分比特)。
2. Data Block 被稱為緩存行(CacheLine)，它是高速緩存與主內(nèi)存之間的數(shù)據(jù)交換最小單元，用于存儲(chǔ)從內(nèi)存中讀取的或者準(zhǔn)備寫往內(nèi)存的數(shù)據(jù)。
3. Flag 用于表示相應(yīng)緩存行的狀態(tài)信息。緩存行的容量(也被稱為緩存行寬度)通常是 2 的倍數(shù)，其大小在 16-256 字節(jié)/Byte之間不等。一個(gè)緩存行可以存儲(chǔ)若干變量的值， 而多個(gè)變量的值則可能被存儲(chǔ)在同一個(gè)緩存行之中。

處理器在執(zhí)行內(nèi)存訪問操作時(shí)會(huì)將相應(yīng)的內(nèi)存地址解碼。內(nèi)存地址的解碼結(jié)果包括 index、tag 以及 offset 這三部分?jǐn)?shù)據(jù)。

1. index 相當(dāng)于桶編號(hào)，它可以用來定位內(nèi)存地址對(duì)應(yīng)的桶。
2. 一個(gè)桶可能包含多個(gè)緩存條目。tag 相當(dāng)于緩存條目的相對(duì)編號(hào)，其作用在于用來與同一個(gè)桶中的各個(gè)緩存條目中的 Tag 部分進(jìn)行比較，以定位一個(gè)具體的緩存條目。
3. 一個(gè)緩存條目中的緩存行可以用來存儲(chǔ)多個(gè)變量，offset 是緩存行內(nèi)的位置偏移，其作用在于確定一個(gè)變量在一個(gè)緩存行中的存儲(chǔ)起始位置。

二、緩存命中

根據(jù)這個(gè)內(nèi)存地址的解碼結(jié)果，如果高速緩存子系統(tǒng)能夠找到相應(yīng)的緩存行并且緩存行所在的緩存條目的 Flag 表示相應(yīng)緩存條目是有效的，那么就稱相應(yīng)的內(nèi)存操作產(chǎn)生了緩存命中(CacheHit)；否則，就稱相應(yīng)的內(nèi)存操作產(chǎn)生了緩存未命中(CacheMiss)。

1從性能角度來看，減少緩存未命中

緩存未命中包括讀未命中(Read Miss)和寫未命中(Write Miss)，分別對(duì)應(yīng)內(nèi)存讀和寫操作。當(dāng)讀未命中產(chǎn)生時(shí)，處理器所需讀取的數(shù)據(jù)會(huì)從主內(nèi)存中加載并被存入相應(yīng)的緩存行之中。這個(gè)過程會(huì)導(dǎo)致處理器停頓(Stall)而不能執(zhí)行其他指令，這不利于發(fā)揮處理器的處理能力。

2緩存未命中不可避免

由于高速緩存的總?cè)萘窟h(yuǎn)小于主內(nèi)存的總?cè)萘?，同一個(gè)緩存行在不同時(shí)刻存儲(chǔ)的可能是不同的一段數(shù)據(jù)，因此緩存未命中是不可避免的。

三、緩存一致性協(xié)議

1??緩存一致性問題

多個(gè)線程并發(fā)訪問同一個(gè)共享變量的時(shí)候，這些線程的執(zhí)行處理器上的高速緩存各自都會(huì)保留一份該共享變量的副本，這就帶來一個(gè)問題一個(gè)處理器對(duì)其副本數(shù)據(jù)進(jìn)行更新之后，其他處理器如何“察覺”到該更新并做出適當(dāng)反應(yīng)，以確保這些處理器后續(xù)讀取該共享變量時(shí)能夠讀取到這個(gè)更新，這就是緩存一致性問題。 例如：CPU-0 讀取主存 count 的數(shù)據(jù)為 1，緩存到 CPU-0 的高速緩存中。CPU-1 也做了同樣的事情，而 CPU-1 把 count 的值修改成了 2，并且同步到 CPU-1 的高速緩存，但是這個(gè)修改以后的值并沒有寫入到主存中，CPU-0 訪問該字節(jié)，由于緩存沒有更新，所以仍然是之前的值，就會(huì)導(dǎo)致數(shù)據(jù)不一致的問題。

2??實(shí)質(zhì)就是如何防止讀臟數(shù)據(jù)和丟失更新的問題。

1. 【總線鎖】
   

   總線鎖就是用來鎖住總線的?？梢酝ㄟ^圖來了解總線在這個(gè)場景中所處的位置。當(dāng)一個(gè) CPU 核執(zhí)行一個(gè)線程對(duì)其緩存中的數(shù)據(jù)進(jìn)行操作的時(shí)候，它會(huì)向總線上發(fā)送一個(gè) Lock 信號(hào)，此時(shí)其他的線程想要去請(qǐng)求主內(nèi)存的時(shí)候，就會(huì)被阻塞，這樣該處理器核心就可以獨(dú)享這個(gè)共享內(nèi)存?？偩€鎖相當(dāng)于把內(nèi)存和 CPU 之間的通信鎖住，把并行化的操作變成了串行，這會(huì)導(dǎo)致 CPU 的性能下降，這與需要多核多線程并行操作來提高程序的效率的目的大相徑庭。所以 P6 系列以后的處理器，出現(xiàn)了另外一種方式，就是緩存鎖。

2. 【緩存鎖】如果某個(gè)內(nèi)存區(qū)域數(shù)據(jù)，已經(jīng)同時(shí)被兩個(gè)或以上處理器核緩存，緩存鎖就會(huì)通過緩存一致性機(jī)制阻止對(duì)其修改，以此來保證操作的原子性，當(dāng)其他處理器核回寫已經(jīng)被鎖定的緩存行的數(shù)據(jù)時(shí)會(huì)導(dǎo)致該緩存行無效。就是說當(dāng)某塊 CPU 核對(duì)緩存中的數(shù)據(jù)進(jìn)行操作了之后，就通知其他 CPU 放棄儲(chǔ)存在它們內(nèi)部的緩存，或者從主內(nèi)存中重新讀取。

處理器上有一套完整的協(xié)議，來保證緩存的一致性，比較經(jīng)典的就是 MESI 協(xié)議，其實(shí)現(xiàn)方法是在 CPU 緩存中保存一個(gè)標(biāo)記位，以此來標(biāo)記四種狀態(tài)。另外，每個(gè) Core 的 Cache 控制器不僅知道自己的讀寫操作，也監(jiān)聽其它 Cache 的讀寫操作，就是嗅探(snooping)協(xié)議。

1. Modified(更改過的，記為 M)：處于這一狀態(tài)的數(shù)據(jù)，只在本 CPU 核中有緩存數(shù)據(jù)，而其他核中沒有。同時(shí)其狀態(tài)相對(duì)于內(nèi)存中的值來說，是已經(jīng)被修改的，只是沒有更新到內(nèi)存中。
2. Exclusive(獨(dú)占的，記為 E)：處于這一狀態(tài)的數(shù)據(jù)，只有在本 CPU 中有緩存，且其數(shù)據(jù)沒有修改，即與內(nèi)存中一致。
3. Shared(共享的，記為s)：處于這一狀態(tài)的數(shù)據(jù)在多個(gè) CPU 中都有緩存，且與內(nèi)存一致。
4. Invalid(無效的，記為I)：本 CPU 中的這份緩存已經(jīng)無效。

CPU的讀取會(huì)遵循幾個(gè)原則(其實(shí)就是上面說的嗅探)

1. 一個(gè)處于 M 狀態(tài)的緩存行，必須時(shí)刻監(jiān)聽所有試圖讀取該緩存行對(duì)應(yīng)的主存地址的操作，如果監(jiān)聽到，則必須在此操作執(zhí)行前把其緩存行中的數(shù)據(jù)寫回 CPU。

2. 一個(gè)處于 S 狀態(tài)的緩存行，必須時(shí)刻監(jiān)聽使該緩存行無效或者獨(dú)享該緩存行的請(qǐng)求，如果監(jiān)聽到，則必須把其緩存行狀態(tài)設(shè)置為 I。

3. 一個(gè)處于 E 狀態(tài)的緩存行，必須時(shí)刻監(jiān)聽其他試圖讀取該緩存行對(duì)應(yīng)的主存地址的操作，如果監(jiān)聽到，則必須把其緩存行狀態(tài)設(shè)置為 S。

當(dāng) CPU 需要讀取數(shù)據(jù)時(shí)，如果其緩存行的狀態(tài)是 I 的，則需要從內(nèi)存中讀取，并把自己狀態(tài)變成 S，如果不是 I，則可以直接讀取緩存中的值，但在此之前，必須要等待其他 CPU 的監(jiān)聽結(jié)果，如其他 CPU 也有該數(shù)據(jù)的緩存且狀態(tài)是 M，則需要等待其把緩存更新到內(nèi)存之后，再讀取。

當(dāng) CPU 需要寫數(shù)據(jù)時(shí)，只有在其緩存行是 M 或者 E 的時(shí)候才能執(zhí)行，否則需要發(fā)出特殊的 RFO 指令(Read Or Ownership，這是一種總線事務(wù))，通知其他 CPU 置緩存無效(I)，這種情況下性能開銷是相對(duì)較大的。在寫入完成后，修改其緩存狀態(tài)為 M。

所以如果一個(gè)變量在某段時(shí)間只被一個(gè)線程頻繁地修改，那么使用其內(nèi)部緩存就完全可以了，并不需要涉及到總線事務(wù)。如果內(nèi)存一會(huì)被這個(gè) CPU 獨(dú)占，一會(huì)被那個(gè) CPU 獨(dú)占，這時(shí)才會(huì)不斷產(chǎn)生 RFO 指令影響到并發(fā)性能。這其實(shí)是跟 CPU 協(xié)調(diào)機(jī)制有關(guān)，如果在 CPU 間調(diào)度不合理，會(huì)形成 RFO 指令的開銷比任務(wù)開銷還要大，喧賓奪主，我們反而不能提高效率。

并非所有情況都會(huì)使用緩存一致性的，如被操作的數(shù)據(jù)不能被緩存在 CPU 內(nèi)部或操作數(shù)據(jù)跨越多個(gè)緩存行(狀態(tài)無法標(biāo)識(shí))，則處理器會(huì)調(diào)用總線鎖定；另外當(dāng) CPU 不支持緩存鎖定時(shí)，自然也只能用總線鎖定了，比如說奔騰 486 以及更老的 CPU。

四、MESI 協(xié)議的處理器讀寫操作？

1??Processor 0 上讀取數(shù)據(jù) S 的實(shí)現(xiàn)

設(shè)內(nèi)存地址 A 上的數(shù)據(jù) S 是處理器 Processor 0 和處理器 Processor l 可能共享的數(shù)據(jù)。

Processor 0 會(huì)根據(jù)地址 A 找到對(duì)應(yīng)的緩存條目，并讀取該緩存條目的 Tag 和 Flag 值(緩存條目狀態(tài))。為討論方便，這里不討論 Tag 值的匹配問題。Processor 0 找到的緩存條目的狀態(tài)如果為 M、E 或者 S，那么該處理器可以直接從相應(yīng)的緩存行中讀取地址 A 所對(duì)應(yīng)的數(shù)據(jù)，而無需往總線中發(fā)送任何消息。Processor 0 找到的緩存條目的狀態(tài)如果為 I，則說明該處理器的高速緩存中并不包含 S 的有效副本數(shù)據(jù)，此時(shí) Processor 0 需要往總線發(fā)送 Read 消息以讀取地址 A 對(duì)應(yīng)的數(shù)據(jù)，而其他處理器 Processor l (或者主內(nèi)存)則需要回復(fù) ReadResponse 以提供相應(yīng)的數(shù)據(jù)。

Processor 0 接收到 ReadResponse 消息時(shí)，會(huì)將其中攜帶的數(shù)據(jù)(包含數(shù)據(jù) S 的數(shù)據(jù)塊) 存入相應(yīng)的緩存行并將相應(yīng)緩存條目的狀態(tài)更新為 S。Processor 0 接收到的 Read Response 消息可能來自主內(nèi)存也可能來自其他處理器(Processor I)。

Processor I 會(huì)嗅探總線中由其他處理器發(fā)送的消息。Processor I 嗅探到 Read 消息的時(shí)候，會(huì)從該消息中取出待讀取的內(nèi)存地址，并根據(jù)該地址在其高速緩存中查找對(duì)應(yīng)的緩存條目。如果 Processor I 找到的緩存條目的狀態(tài)不為 I (如圖)，則說明該處理器的高速緩存中有待讀取數(shù)據(jù)的副本，此時(shí) Processor l 會(huì)構(gòu)造相應(yīng)的 ReadResponse 消息并將相應(yīng)緩存行所存儲(chǔ)的整塊數(shù)據(jù)(而不僅僅是 Processor 0 所請(qǐng)求的數(shù)據(jù)S)塞入該消息。如果 Processor 1 找到的相應(yīng)緩存條目的狀態(tài)為 M，那么 Processor 1 可能在往總線發(fā)送 ReadResponse 消息前將相應(yīng)緩存行中的數(shù)據(jù)寫入主內(nèi)存。Processor 1 往總線發(fā)送 ReadResponse 之后，相應(yīng)緩存條目的狀態(tài)會(huì)被更新為 S。如果 Processor I 找到的高速緩存條目的狀態(tài)為 I，那么 Processor 0 所接收到的 ReadResponse 消息就來自主內(nèi)存。

可見，在 Processor 0 讀取內(nèi)存 的時(shí)候，即便 Processor I 對(duì)相應(yīng)的內(nèi)存數(shù)據(jù)進(jìn)行了更新且這種更新還停留在 Processor I 的高速緩存中而造成高速緩存與主內(nèi)存中的數(shù)據(jù)不一致，在 MESI 協(xié)議消息的協(xié)調(diào)下這種不一 致也并不會(huì)導(dǎo)致 Processor 0 讀取到一個(gè)過時(shí)的舊值。

2??Processor 0 往地址 A 寫數(shù)據(jù)的實(shí)現(xiàn)

Processor 0 所找到的緩存條目的狀態(tài)若為 s，則說明 Processor l 上的高速緩存可能也保留了地址 A 對(duì)應(yīng)的數(shù)據(jù)副本(場景 I)，此時(shí) Processor 0 需要往總線發(fā)送 Invalidate 消息。Processor 0 在接收到其他所有處理器所回復(fù)的 InvalidateAcknowledge 消息之后會(huì)將相應(yīng)的緩存條目的狀態(tài)更新為 E，此時(shí) Processor 0 獲得了地址 A 上數(shù)據(jù)的所有權(quán)。 接著，Processor 0 便可以將數(shù)據(jù)寫入相應(yīng)的緩存行，并將相應(yīng)緩存條目的狀態(tài)更新為 M 。Processor 0 所找到的緩存條目的狀態(tài)若為 I，則表示該處理器不包含地址 A 對(duì)應(yīng)的有效副本數(shù)據(jù)(場景 2)，此時(shí) Processor 0 需要往總線發(fā)送 Read Invalidate 消息。Processor 0 在接收到 Read Response 消息以及其他所有處理器所回復(fù)的 Invalidate Acknowledge 消息之后，會(huì)將相應(yīng)緩存條目的狀態(tài)更新為 E，這表示該處理器已經(jīng)獲得相應(yīng)數(shù)據(jù)的所有權(quán)。接 著，Processor 0 便可以往相應(yīng)的緩存行中寫入數(shù)據(jù)了并將相應(yīng)緩存條目的狀態(tài)更新為 M。其他處理器在接收到 Invalidate 消息或者 Read Invalidate 消息之后，必須根據(jù)消息中包含的內(nèi)存地址在該處理器的高速緩存中查找相應(yīng)的高速緩存條目。若 Processor I 所找到的高速緩存條目的狀態(tài)不為 I (場景 2)，那么 Processor I 必須將相應(yīng)緩存條目的狀態(tài)更新為 I，以刪除相應(yīng)的副本數(shù)據(jù)并給總線回復(fù) Invalidate Acknowledge 消息。可見 Invalidate 消息和 Invalidate Acknowledge 消息使得針對(duì)同一個(gè)內(nèi)存地址的寫操作在任意一個(gè)時(shí)刻只能由一個(gè)處理器執(zhí)行，從而避免了多個(gè)處理器同時(shí)更新同一數(shù)據(jù)可能導(dǎo)致的數(shù)據(jù)不一致問題。

從上述例子來看，在多個(gè)線程共享變抵的情況下，MESI 協(xié)議已經(jīng)能夠保障一個(gè)線程對(duì)共享變量的更新對(duì)其他處理器上運(yùn)行的線程來說是可見的。既然如此，可見性又何以存在呢？這就要從寫緩沖器和無效化隊(duì)列的角度來解釋了。