零、開局
前兩天我搞了兩個每日一個知識點(diǎn),對多線程并發(fā)的部分知識做了下概括性的總結(jié)。但通過小伙伴的反饋是,那玩意寫的比較抽象,看的云里霧里暈暈乎乎的。有興趣的可以看看
每日一個知識點(diǎn):Volatile 和 CAS 的弊端之總線風(fēng)暴
每日一個知識點(diǎn)系列:volatile的可見性原理
所以又針對多線程底層這一塊再重新做下系統(tǒng)性的講解。有興趣的朋友可以先看下前兩節(jié),可以說是個籠統(tǒng)的概念版。
好了,回歸正題。在多線程并發(fā)的世界里synchronized、volatile、JMM是我們繞不過去的技術(shù)坎,而重排序、可見性、內(nèi)存屏障又有時候搞得你一臉懵逼。有道是知其然知其所以然,了解了底層的原理性問題,不論是日常寫B(tài)UG還是面試都是必備神器了。
先看幾個問題點(diǎn):
1、處理器與內(nèi)存之間是怎么交互的?
2、什么是緩存一致性協(xié)議?
3、高速緩存內(nèi)的消息是怎么更新變化的?
4、內(nèi)存屏障又和他們有什么關(guān)系?
如果上面的問題你都能倒背如流,那就去看看電影放松下吧!
一、高速緩存
目前的處理器的處理能力要遠(yuǎn)遠(yuǎn)的勝于主內(nèi)存(DRAM)訪問的效率,往往主內(nèi)存執(zhí)行一次讀寫操作所需的時間足夠處理器執(zhí)行上百次指令。所以為了填補(bǔ)處理器與主內(nèi)存之間的差距,設(shè)計(jì)者們在主內(nèi)存和處理器直接引入了高速緩存(Cache)。如圖:
其實(shí)在現(xiàn)代處理器中,會有多級高速緩存。一般我們會成為一級緩存(L1 Cache)、二級緩存(L2 Cache)、三級緩存(L3 Cache)等,其中一級緩存一般會被集成在CPU內(nèi)核中。如圖:
內(nèi)部結(jié)構(gòu)
高速緩存存在于每個處理器內(nèi),處理器在執(zhí)行讀、寫操作的時候并不需要直接與內(nèi)存交互,而是通過高速緩存進(jìn)行。
高速緩存內(nèi)其實(shí)就是為應(yīng)用程序訪問的變量保存了一個數(shù)據(jù)副本。高速緩存相當(dāng)于一個容量極小的散列表(Hash Table),其鍵是一個內(nèi)存地址,值是內(nèi)存數(shù)據(jù)的副本或是我們準(zhǔn)備寫入的數(shù)據(jù)。從其內(nèi)部來看,其實(shí)相當(dāng)于一個拉鏈散列表,也就是包含了很多桶,每個桶上又可以包含很多緩存條目(想想HashMap),如圖:
緩存條目
在每個緩存條目中,其實(shí)又包含了Tag、Data Block、Flag三個部分,咱們來個小圖:
**Data Block : **也就是我們常常叨叨的緩存行(Cache Line),她其實(shí)是高速緩存與主內(nèi)存間進(jìn)行數(shù)據(jù)交互的最小單元,里面存儲著我們需要的變量數(shù)據(jù)。
**Tag : **包含了緩存行中數(shù)據(jù)內(nèi)存地址的信息(其實(shí)是內(nèi)存地址的高位部分的比特)
Flag :標(biāo)識了當(dāng)前緩存行的狀態(tài)(MESI咯)
那么,我們的處理器又是怎么尋找到我們需要的變量呢?
不多說,上圖:
其實(shí),在處理器執(zhí)行內(nèi)存訪問變量的操作時,會對內(nèi)存地址進(jìn)行解碼的(由高速緩存控制器執(zhí)行)。而解碼后就會得到tag、index 、offset三部分?jǐn)?shù)據(jù)。
index :我們知道高速緩存內(nèi)的結(jié)構(gòu)是一個拉鏈散列表,所以index就是為了幫我們來定位到底是哪個緩存條目的。
tag :很明顯和我們緩存條目中的Tag 一樣,所以tag 相當(dāng)于緩存條目的編號。主要用于,在同一個桶下的拉鏈中來尋找我們的目標(biāo)。
offset :我們要知道一個前提,就是一個緩存條目中的緩存行是可以存儲很多變量的,所以offset的作用是用來確定一個變量在緩存行中的起始位置。
所以,在如果在高速緩存內(nèi)能找到緩存條目并且定位到了響應(yīng)的緩存行,而此時緩存條目的Flag標(biāo)識為有效狀態(tài),這時候也就是我們所說的緩存命中(Cache Hit),否則就是緩存未命中(Cache Miss)。
緩存未命又包括讀未命中(Read Miss)和寫未命中(Write Miss)兩種,對應(yīng)著對內(nèi)存的讀寫操作。
而在讀未命中(Read Miss)產(chǎn)生時,處理器所需要的數(shù)據(jù)會從主內(nèi)存加載并被存入高速緩存對應(yīng)的緩存行中,此過程會導(dǎo)致處理器停頓(Stall)而不能執(zhí)行其他指令。
二、緩存一致性協(xié)議
在多線程進(jìn)行共享變量訪問時,因?yàn)楦鱾€線程執(zhí)行的處理器上的高速緩存中都會保存一份變量的副本數(shù)據(jù),這樣就會有一個問題,那當(dāng)一個副本更新后怎么保證其它處理器能馬上的獲取到最新的數(shù)據(jù)。這其實(shí)就是緩存一致性的問題,其本質(zhì)也就是怎么防止數(shù)據(jù)的臟讀。
為了解決這個問題,處理器間出現(xiàn)了一種通信機(jī)制,也就是緩存一致性協(xié)議(Cache Coherence Protocol)。
MESI是什么
緩存一致性協(xié)議有很多種,MESI(Modified-Exclusive-Shared-Invalid)協(xié)議其實(shí)是目前使用很廣泛的緩存一致性協(xié)議,x86處理器所使用的緩存一致性協(xié)議就是基于MESI的。
我們可以把MESI對內(nèi)存數(shù)據(jù)訪問理解成我們常用的讀寫鎖,它可以使對同一內(nèi)存地址的讀操作是并發(fā)的,而寫操作是獨(dú)占的。所以在任何時刻寫操作只能有一個處理器執(zhí)行。而在MESI中,一個處理器要向內(nèi)存寫數(shù)據(jù)時必須持有該數(shù)據(jù)的所有權(quán)。
MESI將緩存條目的狀態(tài)分為了Modified、Exclusive、Shared、Invalid四種,并在此基礎(chǔ)上定義了一組消息用于處理器的讀、寫內(nèi)存操作。如圖:
MESI的四種狀態(tài)
所以MESI其實(shí)就是使用四種狀態(tài)來標(biāo)識了緩存條目當(dāng)前的狀態(tài),來保證了高速緩存內(nèi)數(shù)據(jù)一致性的問題。那我們來仔細(xì)的看下四種狀態(tài)
Modified :
表示高速緩存中相應(yīng)的緩存行內(nèi)的數(shù)據(jù)已經(jīng)被更新了。由于MESI協(xié)議中任意時刻只能有一個處理器對同一內(nèi)存地址對應(yīng)的數(shù)據(jù)進(jìn)行更新,也就是說再多個處理器的高速緩存中相同Tag值的緩存條目只能有一個處于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ù)副本,此時其他處理上高速緩存當(dāng)前都不保留該數(shù)據(jù)的有效副本。
Shared:
表示當(dāng)前高速緩存相應(yīng)緩存行包含相應(yīng)主內(nèi)存地址對應(yīng)的數(shù)據(jù)副本,且與主內(nèi)存中的數(shù)據(jù)是一致的。如果緩存條目狀態(tài)是Shared的,那么其他處理器上如果也存在相同Tag的緩存條目,那這些緩存條目狀態(tài)肯定也是Shared。
Invalid:
表示該緩存行中不包含任何主內(nèi)存中的有效數(shù)據(jù)副本,這個狀態(tài)也是緩存條目的初始狀態(tài)。
MESI處理機(jī)制
前面說了那么多,都是MESI的基礎(chǔ)理論,那么,MESI協(xié)議到底是怎么來協(xié)調(diào)處理器進(jìn)行內(nèi)存的讀寫呢?
其實(shí),想?yún)f(xié)調(diào)處理必然需要先和各個處理器進(jìn)行通信。所以MESI協(xié)議定義了一組消息機(jī)制用于協(xié)調(diào)各個處理器的讀寫操作。
我們可以參考HTTP協(xié)議來進(jìn)行理解,可以將MESI協(xié)議中的消息分為請求和響應(yīng)兩類。
處理器在進(jìn)行主內(nèi)存讀寫的時候會往總線(Bus)中發(fā)請求消息,同時每個處理器還會嗅探(Snoop)總線中由其他處理器發(fā)出的請求消息并在一定條件下往總線中回復(fù)響應(yīng)消息。
針對于消息的類型,有如下幾種:
Read :請求消息,用于通知其他處理器、主內(nèi)存,當(dāng)前處理器準(zhǔn)備讀取某個數(shù)據(jù)。該消息內(nèi)包含待讀取數(shù)據(jù)的主內(nèi)存地址。
Read Response:響應(yīng)消息,該消息內(nèi)包含了被請求讀取的數(shù)據(jù)。該消息可能是主內(nèi)存返回的,也可能是其他高速緩存嗅探到Read 消息返回的。
Invalidate:請求消息,通知其他處理器刪除指定內(nèi)存地址的數(shù)據(jù)副本。其實(shí)就是告訴他們你這個緩存條目內(nèi)的數(shù)據(jù)無效了,刪除只是邏輯上的,其實(shí)就是更新下緩存條目的Flag.
Invalidate Acknowledge:響應(yīng)消息,接收到Invalidate消息的處理器必須回復(fù)此消息,表示已經(jīng)刪除了其高速緩存內(nèi)對應(yīng)的數(shù)據(jù)副本。
Read Invalidate:請求消息,此消息為Read 和 Invalidate消息組成的復(fù)合消息,作用主要是用于通知其他處理器當(dāng)前處理器準(zhǔn)備更新一個數(shù)據(jù)了,并請求其他處理器刪除其高速緩存內(nèi)對應(yīng)的數(shù)據(jù)副本。接收到該消息的處理器必須回復(fù)Read Response 和 Invalidate Acknowledge消息。
Writeback:請求消息,消息包含了需要寫入主內(nèi)存的數(shù)據(jù)和其對應(yīng)的內(nèi)存地址。
了解完了基礎(chǔ)的消息類型,那么我們就來看看MESI協(xié)議是如何協(xié)助處理器實(shí)現(xiàn)內(nèi)存讀寫的,看圖說話:
舉例:假如內(nèi)存地址0xxx上的變量s 是CPU1 和CPU2共享的我們先來說下CPU上讀取數(shù)據(jù)s
高速緩存內(nèi)存在有效數(shù)據(jù)時:
CPU1會根據(jù)內(nèi)存地址0xxx在高速緩存找到對應(yīng)的緩存條目,并讀取緩存條目的Tag和Flag值。如果此時緩存條目的Flag 是M、E、S三種狀態(tài)的任何一種,那么就直接從緩存行中讀取地址0xxx對應(yīng)的數(shù)據(jù),不會向總線中發(fā)送任何消息。
高速緩存內(nèi)不存在有效數(shù)據(jù)時:
1、如CPU2 高速緩存內(nèi)找到的緩存條目狀態(tài)為I時,則說明此時CPU2的高速緩存中不包含數(shù)據(jù)s的有效數(shù)據(jù)副本。
2、CPU2向總線發(fā)送Read消息來讀取地址0xxx對應(yīng)的數(shù)據(jù)s.
3、CPU1(或主內(nèi)存)嗅探到Read消息,則需要回復(fù)Read Response提供相應(yīng)的數(shù)據(jù)。
4、CPU2接收到Read Response消息時,會將其中攜帶的數(shù)據(jù)s存入相應(yīng)的緩存行并將對應(yīng)的緩存條目狀態(tài)更新為S。
從宏觀的角度看,就是上面的流程了,我們再繼續(xù)深入下,看看在緩存條目為I的時候到底是怎么進(jìn)行消息處理的
說完了讀取數(shù)據(jù),我們就在說下CPU1是怎么寫入一個地址為0xxx的數(shù)據(jù)s的
MESI協(xié)議解決了緩存一致性的問題,但其中有一個問題,那就是需要在等待其他處理器全部回復(fù)后才能進(jìn)行下一步操作,這種等待明顯是不能接受的,下面就繼續(xù)來看看大神們是怎么解決處理器等待的問題的。
三、寫緩沖和無效化隊(duì)列
因?yàn)镸ESI自身有個問題,就是在寫內(nèi)存操作的時候必須等待其他所有處理器將自身高速緩存內(nèi)的相應(yīng)數(shù)據(jù)副本都刪除后,并接收到這些處理器回復(fù)的Invalidate Acknowledge/Read Response消息后才能將數(shù)據(jù)寫入高速緩存。
為了避免這種等待造成的寫操作延遲,硬件設(shè)計(jì)引入了寫緩沖器和無效化隊(duì)列。
寫緩沖器(Store Buffer)
在每個處理器內(nèi)都有自己獨(dú)立的寫緩沖器,寫緩沖器內(nèi)部包含很多條目(Entry),寫緩沖器比高速緩存還要小點(diǎn)。
那么,在引入了寫緩沖器后,處理器在執(zhí)行寫入數(shù)據(jù)的時候會做什么處理呢?還會直接發(fā)送消息到BUS嗎?
我們來看幾個場景:
(注意x86處理器是不管相應(yīng)的緩存條目是什么狀態(tài),都會直接將每一個寫操作結(jié)果存入寫緩沖器)
1、如果此時緩存條目狀態(tài)是E或者M(jìn):
代表此時處理器已經(jīng)獲取到數(shù)據(jù)所有權(quán),那么就會將數(shù)據(jù)直接寫入相應(yīng)的緩存行內(nèi),而不會向總線發(fā)送消息。
2、如果此時緩存條目狀態(tài)是S
此時處理器會將寫操作的數(shù)據(jù)存入寫緩沖器的條目中,并發(fā)送Invalidate消息。
如果此時相應(yīng)緩存條目的狀態(tài)是I ,那就稱之為寫操作遇到了寫未命中(Write Miss),此時就會將數(shù)據(jù)先寫入寫緩沖器的條目中,然后在發(fā)送Read Invalidate來通知其他處理器我要進(jìn)行數(shù)據(jù)更新了。
處理器的寫操作其實(shí)在將數(shù)據(jù)寫入緩沖器時就完成了,處理器并不需要等待其他處理器返回Invalidate Acknowledge/Read Response消息
當(dāng)處理器接收到其他處理器回復(fù)的針對于同一個緩存條目的Invalidate Acknowledge消息時,就會將寫緩沖內(nèi)對應(yīng)的數(shù)據(jù)寫入相應(yīng)的緩存行中
通過上面的場景描述我們可以看出,寫緩沖器幫助處理器實(shí)現(xiàn)了異步寫數(shù)據(jù)的能力,使得處理器處理指令的能力大大提升。
無效化隊(duì)列(Invalidate Queue)
其實(shí)在處理器接到Invalidate類型的消息時,并不會刪除消息中指定地址對應(yīng)的數(shù)據(jù)副本(也就是說不會去馬上修改緩存條目的狀態(tài)為I),而是將消息存入無效化隊(duì)列之后就回復(fù)Invalidate Acknowledge消息了,主要原因還是為了減少處理器等待的時間。
所以不管是寫緩沖器還是無效化隊(duì)列,其實(shí)都是為了減少處理器的等待時間,采用了空間換時間的方式來實(shí)現(xiàn)命令的異步處理。
總之就是,寫緩沖器解決了寫數(shù)據(jù)時要等待其他處理器響應(yīng)得問題,無效化隊(duì)列幫助解決了刪除數(shù)據(jù)等待的問題。
但既然是異步的,那必然又會帶來新的問題 -- 內(nèi)存重排序和可見性問題。
所以,我們繼續(xù)接著聊。
存儲轉(zhuǎn)發(fā)(Store Fowarding)
通過上面內(nèi)容我們知道了有了寫緩沖器后,處理器在寫數(shù)據(jù)時直接寫入緩沖器就直接返回了。
那么問題就來了,當(dāng)我們寫完一個數(shù)據(jù)又要馬上進(jìn)行讀取可咋辦呢?話不多說,咱們還是舉個例子來說,如圖:
此時第一步處理器將變量S的更新后的數(shù)據(jù)寫入到寫緩沖器返回,接著馬上執(zhí)行了第二步進(jìn)行S變量的讀取。由于此時處理器對S變量的更新結(jié)果還停留在寫緩沖器中,因此從高速緩存緩存行中讀到的數(shù)據(jù)還是變量S的舊值。
為了解決這種問題,存儲轉(zhuǎn)發(fā)(Store Fowarding)這個概念上線了。其理論就是處理器在執(zhí)行讀操作時會先根據(jù)相應(yīng)的內(nèi)存地址從寫緩沖器中查詢。如果查到了直接返回,否則處理器才會從高速緩存中查找,這種從緩沖器中讀取的技術(shù)就叫做存儲轉(zhuǎn)發(fā)。看圖:
內(nèi)存重排序和可見性的問題
由于寫緩沖器和無效化隊(duì)列的出現(xiàn),處理器的執(zhí)行都變成了異步操作。緩沖器是每個處理器私有的,一個處理器所存儲的內(nèi)容是無法被其他處理器讀取的。
舉個例子:
CPU1 更新變量到緩沖器中,而CPU2因?yàn)闊o法讀取到CPU1緩沖器內(nèi)容所以從高速緩存中讀取的仍然是該變量舊值。
其實(shí)這就是寫緩沖器導(dǎo)致StoreLoad重排序問題,而寫緩沖器還會導(dǎo)致StoreStore重排序問題等。
為了使一個處理器上運(yùn)行的線程對共享變量所做的更新被其他處理器上運(yùn)行的線程讀到,我們必須將寫緩沖器的內(nèi)容寫到其他處理器的高速緩存上,從而使在緩存一致性協(xié)議作用下此次更新可以被其他處理器讀取到。
處理器在寫緩沖器滿、I/O指令被執(zhí)行時會將寫緩沖器中的內(nèi)容寫入高速緩存中。但從變量更新角度來看,處理器本身無法保障這種更新的”及時“性。為了保證處理器對共享變量的更新可被其他處理器同步,編譯器等底層系統(tǒng)借助一類稱為內(nèi)存屏障的特殊指令來實(shí)現(xiàn)。
內(nèi)存屏障中的存儲屏障(Store Barrier)會使執(zhí)行該指令的處理器將寫緩沖器內(nèi)容寫入高速緩存。
內(nèi)存屏障中的加載屏障(Load Barrier)會根據(jù)無效化隊(duì)列內(nèi)容指定的內(nèi)存地址,將相應(yīng)處理器上的高速緩存中相應(yīng)的緩存條目狀態(tài)標(biāo)記為I。
四、內(nèi)存屏障
因?yàn)檎f了存儲屏障(Store Barrier)和加載屏障(Load Barrier) ,所以這里再簡單的提下內(nèi)存屏障的概念。
劃重點(diǎn):(你細(xì)品)
處理器支持哪種內(nèi)存重排序(LoadLoad重排序、LoadStore重排序、StoreStore重排序、StoreLoad重排序),就會提供相對應(yīng)能夠禁止重排序的指令,而這些指令就被稱之為內(nèi)存屏障(LoadLoad屏障、LoadStore屏障、StoreStore屏障、StoreLoad屏障)
劃重點(diǎn):
如果用X和Y來代替Load或Store,這類指令的作用就是禁止該指令左側(cè)的任何 X 操作與該指令右側(cè)的任何 Y 操作之間進(jìn)行重排序(就是交換位置),確保指令左側(cè)的所有 X 操作都優(yōu)先于指令右側(cè)的Y操作。
內(nèi)存屏障的具體作用:
屏障名稱 | 示例 | 具體作用 |
---|---|---|
StoreLoad | Store1;Store2;Store3;StoreLoad;Load1;Load2;Load3 | 禁止StoreLoad重排序,確保屏障之前任何一個寫(如Store2)的結(jié)果都會在屏障后任意一個讀操作(如Load1)加載之前被寫入 |
StoreStore | Store1;Store2;Store3;StoreStore;Store4;Store5;Store6 | 禁止StoreStore重排序,確保屏障之前任何一個寫(如Store1)的結(jié)果都會在屏障后任意一個寫操作(如Store4)之前被寫入 |
LoadLoad | Load1;Load2;Load3;LoadLoad;Load4;Load5;Load6 | 禁止LoadLoad重排序,確保屏障之前任何一個讀(如Load1)的數(shù)據(jù)都會在屏障后任意一個讀操作(如Load4)之前被加載 |
LoadStore | Load1;Load2;Load3;LoadStore;Store1;Store2;Store3 | 禁止LoadStore重排序,確保屏障之前任何一個讀(如Load1)的數(shù)據(jù)都會在屏障后任意一個寫操作(如Store1)的結(jié)果被寫入高速緩存(或主內(nèi)存)前被加載 |
五、總結(jié)
其實(shí)從頭看到尾就會發(fā)現(xiàn),一個技術(shù)點(diǎn)的出現(xiàn)往往是為了填補(bǔ)另一個的坑。
為了解決處理器與主內(nèi)存之間的速度鴻溝,引入了高速緩存,卻又導(dǎo)致了緩存一致性問題
為了解決緩存一致性問題,引入了如MESI等技術(shù),又導(dǎo)致了處理器等待問題
為了解決處理器等待問題,引入了寫緩沖和無效化隊(duì)列,又導(dǎo)致了重排序和可見性問題
為了解決重排序和可見性問題,引入了內(nèi)存屏障,舒坦。。。
編輯:hfy
-
處理器
+關(guān)注
關(guān)注
68文章
18927瀏覽量
227233 -
高速緩存
+關(guān)注
關(guān)注
0文章
30瀏覽量
11034 -
多線程
+關(guān)注
關(guān)注
0文章
275瀏覽量
19850 -
volatile
+關(guān)注
關(guān)注
0文章
44瀏覽量
12982
發(fā)布評論請先 登錄
相關(guān)推薦
評論