零、開局

前兩天我搞了兩個(gè)每日一個(gè)知識(shí)點(diǎn)，對(duì)多線程并發(fā)的部分知識(shí)做了下概括性的總結(jié)。但通過(guò)小伙伴的反饋是，那玩意寫的比較抽象，看的云里霧里暈暈乎乎的。有興趣的可以看看

每日一個(gè)知識(shí)點(diǎn)：Volatile 和 CAS 的弊端之總線風(fēng)暴

每日一個(gè)知識(shí)點(diǎn)系列：volatile的可見性原理

所以又針對(duì)多線程底層這一塊再重新做下系統(tǒng)性的講解。有興趣的朋友可以先看下前兩節(jié)，可以說(shuō)是個(gè)籠統(tǒng)的概念版。

好了，回歸正題。在多線程并發(fā)的世界里synchronized、volatile、JMM是我們繞不過(guò)去的技術(shù)坎，而重排序、可見性、內(nèi)存屏障又有時(shí)候搞得你一臉懵逼。有道是知其然知其所以然，了解了底層的原理性問(wèn)題，不論是日常寫B(tài)UG還是面試都是必備神器了。

先看幾個(gè)問(wèn)題點(diǎn)：

1、處理器與內(nèi)存之間是怎么交互的？

2、什么是緩存一致性協(xié)議？

3、高速緩存內(nèi)的消息是怎么更新變化的？

4、內(nèi)存屏障又和他們有什么關(guān)系？

如果上面的問(wèn)題你都能倒背如流，那就去看看電影放松下吧！

一、高速緩存

目前的處理器的處理能力要遠(yuǎn)遠(yuǎn)的勝于主內(nèi)存（DRAM）訪問(wèn)的效率，往往主內(nèi)存執(zhí)行一次讀寫操作所需的時(shí)間足夠處理器執(zhí)行上百次指令。所以為了填補(bǔ)處理器與主內(nèi)存之間的差距，設(shè)計(jì)者們?cè)谥鲀?nèi)存和處理器直接引入了高速緩存（Cache）。如圖：

其實(shí)在現(xiàn)代處理器中，會(huì)有多級(jí)高速緩存。一般我們會(huì)成為一級(jí)緩存（L1 Cache）、二級(jí)緩存（L2 Cache）、三級(jí)緩存（L3 Cache）等，其中一級(jí)緩存一般會(huì)被集成在CPU內(nèi)核中。如圖：

內(nèi)部結(jié)構(gòu)

高速緩存存在于每個(gè)處理器內(nèi)，處理器在執(zhí)行讀、寫操作的時(shí)候并不需要直接與內(nèi)存交互，而是通過(guò)高速緩存進(jìn)行。

高速緩存內(nèi)其實(shí)就是為應(yīng)用程序訪問(wèn)的變量保存了一個(gè)數(shù)據(jù)副本。高速緩存相當(dāng)于一個(gè)容量極小的散列表（Hash Table），其鍵是一個(gè)內(nèi)存地址，值是內(nèi)存數(shù)據(jù)的副本或是我們準(zhǔn)備寫入的數(shù)據(jù)。從其內(nèi)部來(lái)看，其實(shí)相當(dāng)于一個(gè)拉鏈散列表，也就是包含了很多桶，每個(gè)桶上又可以包含很多緩存條目（想想HashMap），如圖：

緩存條目

在每個(gè)緩存條目中，其實(shí)又包含了Tag、Data Block、Flag三個(gè)部分，咱們來(lái)個(gè)小圖：

**Data Block : **也就是我們常常叨叨的緩存行（Cache Line）,她其實(shí)是高速緩存與主內(nèi)存間進(jìn)行數(shù)據(jù)交互的最小單元，里面存儲(chǔ)著我們需要的變量數(shù)據(jù)。

**Tag : **包含了緩存行中數(shù)據(jù)內(nèi)存地址的信息（其實(shí)是內(nèi)存地址的高位部分的比特）

Flag :標(biāo)識(shí)了當(dāng)前緩存行的狀態(tài)（MESI咯）

那么，我們的處理器又是怎么尋找到我們需要的變量呢？

不多說(shuō)，上圖：

其實(shí)，在處理器執(zhí)行內(nèi)存訪問(wèn)變量的操作時(shí)，會(huì)對(duì)內(nèi)存地址進(jìn)行解碼的(由高速緩存控制器執(zhí)行)。而解碼后就會(huì)得到tag、index 、offset三部分?jǐn)?shù)據(jù)。

index :我們知道高速緩存內(nèi)的結(jié)構(gòu)是一個(gè)拉鏈散列表，所以index就是為了幫我們來(lái)定位到底是哪個(gè)緩存條目的。

tag :很明顯和我們緩存條目中的Tag 一樣，所以tag 相當(dāng)于緩存條目的編號(hào)。主要用于，在同一個(gè)桶下的拉鏈中來(lái)尋找我們的目標(biāo)。

offset :我們要知道一個(gè)前提，就是一個(gè)緩存條目中的緩存行是可以存儲(chǔ)很多變量的，所以offset的作用是用來(lái)確定一個(gè)變量在緩存行中的起始位置。

所以，在如果在高速緩存內(nèi)能找到緩存條目并且定位到了響應(yīng)的緩存行，而此時(shí)緩存條目的Flag標(biāo)識(shí)為有效狀態(tài)，這時(shí)候也就是我們所說(shuō)的緩存命中（Cache Hit）,否則就是緩存未命中（Cache Miss）。

緩存未命又包括讀未命中（Read Miss）和寫未命中(Write Miss)兩種,對(duì)應(yīng)著對(duì)內(nèi)存的讀寫操作。

而在讀未命中（Read Miss）產(chǎn)生時(shí)，處理器所需要的數(shù)據(jù)會(huì)從主內(nèi)存加載并被存入高速緩存對(duì)應(yīng)的緩存行中，此過(guò)程會(huì)導(dǎo)致處理器停頓（Stall）而不能執(zhí)行其他指令。

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

在多線程進(jìn)行共享變量訪問(wèn)時(shí)，因?yàn)楦鱾€(gè)線程執(zhí)行的處理器上的高速緩存中都會(huì)保存一份變量的副本數(shù)據(jù)，這樣就會(huì)有一個(gè)問(wèn)題，那當(dāng)一個(gè)副本更新后怎么保證其它處理器能馬上的獲取到最新的數(shù)據(jù)。這其實(shí)就是緩存一致性的問(wèn)題，其本質(zhì)也就是怎么防止數(shù)據(jù)的臟讀。

為了解決這個(gè)問(wèn)題，處理器間出現(xiàn)了一種通信機(jī)制，也就是緩存一致性協(xié)議（Cache Coherence Protocol）。

MESI是什么

緩存一致性協(xié)議有很多種，MESI（Modified-Exclusive-Shared-Invalid）協(xié)議其實(shí)是目前使用很廣泛的緩存一致性協(xié)議，x86處理器所使用的緩存一致性協(xié)議就是基于MESI的。

我們可以把MESI對(duì)內(nèi)存數(shù)據(jù)訪問(wèn)理解成我們常用的讀寫鎖，它可以使對(duì)同一內(nèi)存地址的讀操作是并發(fā)的，而寫操作是獨(dú)占的。所以在任何時(shí)刻寫操作只能有一個(gè)處理器執(zhí)行。而在MESI中，一個(gè)處理器要向內(nèi)存寫數(shù)據(jù)時(shí)必須持有該數(shù)據(jù)的所有權(quán)。

MESI將緩存條目的狀態(tài)分為了Modified、Exclusive、Shared、Invalid四種，并在此基礎(chǔ)上定義了一組消息用于處理器的讀、寫內(nèi)存操作。如圖：

MESI的四種狀態(tài)

所以MESI其實(shí)就是使用四種狀態(tài)來(lái)標(biāo)識(shí)了緩存條目當(dāng)前的狀態(tài)，來(lái)保證了高速緩存內(nèi)數(shù)據(jù)一致性的問(wèn)題。那我們來(lái)仔細(xì)的看下四種狀態(tài)

Modified ：

表示高速緩存中相應(yīng)的緩存行內(nèi)的數(shù)據(jù)已經(jīng)被更新了。由于MESI協(xié)議中任意時(shí)刻只能有一個(gè)處理器對(duì)同一內(nèi)存地址對(duì)應(yīng)的數(shù)據(jù)進(jìn)行更新，也就是說(shuō)再多個(gè)處理器的高速緩存中相同Tag值的緩存條目只能有一個(gè)處于Modified狀態(tài)。處于此狀態(tài)的緩存條目中緩存行內(nèi)的數(shù)據(jù)與主內(nèi)存包含的數(shù)據(jù)不一致。

Exclusive：

表示高速緩存相應(yīng)的緩存行內(nèi)的數(shù)據(jù)副本與主內(nèi)存中的數(shù)據(jù)一樣。并且，該緩存行以獨(dú)占的方式保留了相應(yīng)主內(nèi)存地址的數(shù)據(jù)副本，此時(shí)其他處理上高速緩存當(dāng)前都不保留該數(shù)據(jù)的有效副本。

Shared：

表示當(dāng)前高速緩存相應(yīng)緩存行包含相應(yīng)主內(nèi)存地址對(duì)應(yīng)的數(shù)據(jù)副本，且與主內(nèi)存中的數(shù)據(jù)是一致的。如果緩存條目狀態(tài)是Shared的，那么其他處理器上如果也存在相同Tag的緩存條目，那這些緩存條目狀態(tài)肯定也是Shared。

Invalid：

表示該緩存行中不包含任何主內(nèi)存中的有效數(shù)據(jù)副本，這個(gè)狀態(tài)也是緩存條目的初始狀態(tài)。

MESI處理機(jī)制

前面說(shuō)了那么多，都是MESI的基礎(chǔ)理論，那么，MESI協(xié)議到底是怎么來(lái)協(xié)調(diào)處理器進(jìn)行內(nèi)存的讀寫呢？

其實(shí)，想?yún)f(xié)調(diào)處理必然需要先和各個(gè)處理器進(jìn)行通信。所以MESI協(xié)議定義了一組消息機(jī)制用于協(xié)調(diào)各個(gè)處理器的讀寫操作。

我們可以參考HTTP協(xié)議來(lái)進(jìn)行理解，可以將MESI協(xié)議中的消息分為請(qǐng)求和響應(yīng)兩類。

處理器在進(jìn)行主內(nèi)存讀寫的時(shí)候會(huì)往總線（Bus）中發(fā)請(qǐng)求消息，同時(shí)每個(gè)處理器還會(huì)嗅探（Snoop）總線中由其他處理器發(fā)出的請(qǐng)求消息并在一定條件下往總線中回復(fù)響應(yīng)消息。

針對(duì)于消息的類型，有如下幾種：

Read :請(qǐng)求消息，用于通知其他處理器、主內(nèi)存，當(dāng)前處理器準(zhǔn)備讀取某個(gè)數(shù)據(jù)。該消息內(nèi)包含待讀取數(shù)據(jù)的主內(nèi)存地址。

Read Response:響應(yīng)消息，該消息內(nèi)包含了被請(qǐng)求讀取的數(shù)據(jù)。該消息可能是主內(nèi)存返回的，也可能是其他高速緩存嗅探到Read 消息返回的。

Invalidate：請(qǐng)求消息，通知其他處理器刪除指定內(nèi)存地址的數(shù)據(jù)副本。其實(shí)就是告訴他們你這個(gè)緩存條目?jī)?nèi)的數(shù)據(jù)無(wú)效了，刪除只是邏輯上的，其實(shí)就是更新下緩存條目的Flag.

Invalidate Acknowledge：響應(yīng)消息，接收到Invalidate消息的處理器必須回復(fù)此消息，表示已經(jīng)刪除了其高速緩存內(nèi)對(duì)應(yīng)的數(shù)據(jù)副本。

Read Invalidate:請(qǐng)求消息，此消息為Read 和 Invalidate消息組成的復(fù)合消息，作用主要是用于通知其他處理器當(dāng)前處理器準(zhǔn)備更新一個(gè)數(shù)據(jù)了，并請(qǐng)求其他處理器刪除其高速緩存內(nèi)對(duì)應(yīng)的數(shù)據(jù)副本。接收到該消息的處理器必須回復(fù)Read Response 和 Invalidate Acknowledge消息。

Writeback:請(qǐng)求消息，消息包含了需要寫入主內(nèi)存的數(shù)據(jù)和其對(duì)應(yīng)的內(nèi)存地址。

了解完了基礎(chǔ)的消息類型，那么我們就來(lái)看看MESI協(xié)議是如何協(xié)助處理器實(shí)現(xiàn)內(nèi)存讀寫的，看圖說(shuō)話：

舉例：假如內(nèi)存地址0xxx上的變量s 是CPU1 和CPU2共享的我們先來(lái)說(shuō)下CPU上讀取數(shù)據(jù)s

高速緩存內(nèi)存在有效數(shù)據(jù)時(shí)：

CPU1會(huì)根據(jù)內(nèi)存地址0xxx在高速緩存找到對(duì)應(yīng)的緩存條目，并讀取緩存條目的Tag和Flag值。如果此時(shí)緩存條目的Flag 是M、E、S三種狀態(tài)的任何一種，那么就直接從緩存行中讀取地址0xxx對(duì)應(yīng)的數(shù)據(jù)，不會(huì)向總線中發(fā)送任何消息。

高速緩存內(nèi)不存在有效數(shù)據(jù)時(shí)：

1、如CPU2 高速緩存內(nèi)找到的緩存條目狀態(tài)為I時(shí)，則說(shuō)明此時(shí)CPU2的高速緩存中不包含數(shù)據(jù)s的有效數(shù)據(jù)副本。

2、CPU2向總線發(fā)送Read消息來(lái)讀取地址0xxx對(duì)應(yīng)的數(shù)據(jù)s.

3、CPU1（或主內(nèi)存）嗅探到Read消息，則需要回復(fù)Read Response提供相應(yīng)的數(shù)據(jù)。

4、CPU2接收到Read Response消息時(shí)，會(huì)將其中攜帶的數(shù)據(jù)s存入相應(yīng)的緩存行并將對(duì)應(yīng)的緩存條目狀態(tài)更新為S。

從宏觀的角度看，就是上面的流程了，我們?cè)倮^續(xù)深入下，看看在緩存條目為I的時(shí)候到底是怎么進(jìn)行消息處理的

說(shuō)完了讀取數(shù)據(jù)，我們就在說(shuō)下CPU1是怎么寫入一個(gè)地址為0xxx的數(shù)據(jù)s的

MESI協(xié)議解決了緩存一致性的問(wèn)題，但其中有一個(gè)問(wèn)題，那就是需要在等待其他處理器全部回復(fù)后才能進(jìn)行下一步操作，這種等待明顯是不能接受的，下面就繼續(xù)來(lái)看看大神們是怎么解決處理器等待的問(wèn)題的。

三、寫緩沖和無(wú)效化隊(duì)列

因?yàn)镸ESI自身有個(gè)問(wèn)題，就是在寫內(nèi)存操作的時(shí)候必須等待其他所有處理器將自身高速緩存內(nèi)的相應(yīng)數(shù)據(jù)副本都刪除后，并接收到這些處理器回復(fù)的Invalidate Acknowledge/Read Response消息后才能將數(shù)據(jù)寫入高速緩存。

為了避免這種等待造成的寫操作延遲，硬件設(shè)計(jì)引入了寫緩沖器和無(wú)效化隊(duì)列。

寫緩沖器（Store Buffer）

在每個(gè)處理器內(nèi)都有自己獨(dú)立的寫緩沖器，寫緩沖器內(nèi)部包含很多條目（Entry）,寫緩沖器比高速緩存還要小點(diǎn)。

那么，在引入了寫緩沖器后，處理器在執(zhí)行寫入數(shù)據(jù)的時(shí)候會(huì)做什么處理呢？還會(huì)直接發(fā)送消息到BUS嗎？

我們來(lái)看幾個(gè)場(chǎng)景：

（注意x86處理器是不管相應(yīng)的緩存條目是什么狀態(tài)，都會(huì)直接將每一個(gè)寫操作結(jié)果存入寫緩沖器）

1、如果此時(shí)緩存條目狀態(tài)是E或者M(jìn)：

代表此時(shí)處理器已經(jīng)獲取到數(shù)據(jù)所有權(quán)，那么就會(huì)將數(shù)據(jù)直接寫入相應(yīng)的緩存行內(nèi)，而不會(huì)向總線發(fā)送消息。

2、如果此時(shí)緩存條目狀態(tài)是S

此時(shí)處理器會(huì)將寫操作的數(shù)據(jù)存入寫緩沖器的條目中，并發(fā)送Invalidate消息。

如果此時(shí)相應(yīng)緩存條目的狀態(tài)是I ，那就稱之為寫操作遇到了寫未命中（Write Miss），此時(shí)就會(huì)將數(shù)據(jù)先寫入寫緩沖器的條目中，然后在發(fā)送Read Invalidate來(lái)通知其他處理器我要進(jìn)行數(shù)據(jù)更新了。

處理器的寫操作其實(shí)在將數(shù)據(jù)寫入緩沖器時(shí)就完成了，處理器并不需要等待其他處理器返回Invalidate Acknowledge/Read Response消息

當(dāng)處理器接收到其他處理器回復(fù)的針對(duì)于同一個(gè)緩存條目的Invalidate Acknowledge消息時(shí)，就會(huì)將寫緩沖內(nèi)對(duì)應(yīng)的數(shù)據(jù)寫入相應(yīng)的緩存行中

通過(guò)上面的場(chǎng)景描述我們可以看出，寫緩沖器幫助處理器實(shí)現(xiàn)了異步寫數(shù)據(jù)的能力，使得處理器處理指令的能力大大提升。

無(wú)效化隊(duì)列（Invalidate Queue）

其實(shí)在處理器接到Invalidate類型的消息時(shí)，并不會(huì)刪除消息中指定地址對(duì)應(yīng)的數(shù)據(jù)副本（也就是說(shuō)不會(huì)去馬上修改緩存條目的狀態(tài)為I），而是將消息存入無(wú)效化隊(duì)列之后就回復(fù)Invalidate Acknowledge消息了，主要原因還是為了減少處理器等待的時(shí)間。

所以不管是寫緩沖器還是無(wú)效化隊(duì)列，其實(shí)都是為了減少處理器的等待時(shí)間，采用了空間換時(shí)間的方式來(lái)實(shí)現(xiàn)命令的異步處理。

總之就是，寫緩沖器解決了寫數(shù)據(jù)時(shí)要等待其他處理器響應(yīng)得問(wèn)題，無(wú)效化隊(duì)列幫助解決了刪除數(shù)據(jù)等待的問(wèn)題。

但既然是異步的，那必然又會(huì)帶來(lái)新的問(wèn)題 -- 內(nèi)存重排序和可見性問(wèn)題。

所以，我們繼續(xù)接著聊。

存儲(chǔ)轉(zhuǎn)發(fā)（Store Fowarding）

通過(guò)上面內(nèi)容我們知道了有了寫緩沖器后，處理器在寫數(shù)據(jù)時(shí)直接寫入緩沖器就直接返回了。

那么問(wèn)題就來(lái)了，當(dāng)我們寫完一個(gè)數(shù)據(jù)又要馬上進(jìn)行讀取可咋辦呢？話不多說(shuō)，咱們還是舉個(gè)例子來(lái)說(shuō)，如圖：

此時(shí)第一步處理器將變量S的更新后的數(shù)據(jù)寫入到寫緩沖器返回，接著馬上執(zhí)行了第二步進(jìn)行S變量的讀取。由于此時(shí)處理器對(duì)S變量的更新結(jié)果還停留在寫緩沖器中，因此從高速緩存緩存行中讀到的數(shù)據(jù)還是變量S的舊值。

為了解決這種問(wèn)題，存儲(chǔ)轉(zhuǎn)發(fā)（Store Fowarding）這個(gè)概念上線了。其理論就是處理器在執(zhí)行讀操作時(shí)會(huì)先根據(jù)相應(yīng)的內(nèi)存地址從寫緩沖器中查詢。如果查到了直接返回，否則處理器才會(huì)從高速緩存中查找，這種從緩沖器中讀取的技術(shù)就叫做存儲(chǔ)轉(zhuǎn)發(fā)。看圖：

內(nèi)存重排序和可見性的問(wèn)題

由于寫緩沖器和無(wú)效化隊(duì)列的出現(xiàn)，處理器的執(zhí)行都變成了異步操作。緩沖器是每個(gè)處理器私有的，一個(gè)處理器所存儲(chǔ)的內(nèi)容是無(wú)法被其他處理器讀取的。

舉個(gè)例子：

CPU1 更新變量到緩沖器中，而CPU2因?yàn)闊o(wú)法讀取到CPU1緩沖器內(nèi)容所以從高速緩存中讀取的仍然是該變量舊值。

其實(shí)這就是寫緩沖器導(dǎo)致StoreLoad重排序問(wèn)題，而寫緩沖器還會(huì)導(dǎo)致StoreStore重排序問(wèn)題等。

為了使一個(gè)處理器上運(yùn)行的線程對(duì)共享變量所做的更新被其他處理器上運(yùn)行的線程讀到，我們必須將寫緩沖器的內(nèi)容寫到其他處理器的高速緩存上，從而使在緩存一致性協(xié)議作用下此次更新可以被其他處理器讀取到。

處理器在寫緩沖器滿、I/O指令被執(zhí)行時(shí)會(huì)將寫緩沖器中的內(nèi)容寫入高速緩存中。但從變量更新角度來(lái)看，處理器本身無(wú)法保障這種更新的”及時(shí)“性。為了保證處理器對(duì)共享變量的更新可被其他處理器同步，編譯器等底層系統(tǒng)借助一類稱為內(nèi)存屏障的特殊指令來(lái)實(shí)現(xiàn)。

內(nèi)存屏障中的存儲(chǔ)屏障（Store Barrier）會(huì)使執(zhí)行該指令的處理器將寫緩沖器內(nèi)容寫入高速緩存。

內(nèi)存屏障中的加載屏障（Load Barrier）會(huì)根據(jù)無(wú)效化隊(duì)列內(nèi)容指定的內(nèi)存地址，將相應(yīng)處理器上的高速緩存中相應(yīng)的緩存條目狀態(tài)標(biāo)記為I。

四、內(nèi)存屏障

因?yàn)檎f(shuō)了存儲(chǔ)屏障（Store Barrier）和加載屏障（Load Barrier） ，所以這里再簡(jiǎn)單的提下內(nèi)存屏障的概念。

劃重點(diǎn)：（你細(xì)品）

處理器支持哪種內(nèi)存重排序（LoadLoad重排序、LoadStore重排序、StoreStore重排序、StoreLoad重排序），就會(huì)提供相對(duì)應(yīng)能夠禁止重排序的指令，而這些指令就被稱之為內(nèi)存屏障（LoadLoad屏障、LoadStore屏障、StoreStore屏障、StoreLoad屏障）

劃重點(diǎn)：

如果用X和Y來(lái)代替Load或Store,這類指令的作用就是禁止該指令左側(cè)的任何 X 操作與該指令右側(cè)的任何 Y 操作之間進(jìn)行重排序（就是交換位置），確保指令左側(cè)的所有 X 操作都優(yōu)先于指令右側(cè)的Y操作。

內(nèi)存屏障的具體作用：

五、總結(jié)

其實(shí)從頭看到尾就會(huì)發(fā)現(xiàn)，一個(gè)技術(shù)點(diǎn)的出現(xiàn)往往是為了填補(bǔ)另一個(gè)的坑。

為了解決處理器與主內(nèi)存之間的速度鴻溝，引入了高速緩存，卻又導(dǎo)致了緩存一致性問(wèn)題

為了解決緩存一致性問(wèn)題，引入了如MESI等技術(shù)，又導(dǎo)致了處理器等待問(wèn)題

為了解決處理器等待問(wèn)題，引入了寫緩沖和無(wú)效化隊(duì)列，又導(dǎo)致了重排序和可見性問(wèn)題

為了解決重排序和可見性問(wèn)題，引入了內(nèi)存屏障，舒坦。。。
編輯：hfy