10多年前的程序員對(duì)處理器亂序執(zhí)行和內(nèi)存屏障應(yīng)該是很熟悉的,但隨著計(jì)算機(jī)技術(shù)突飛猛進(jìn)的發(fā)展,我們離底層原理越來(lái)越遠(yuǎn),這并不是一件壞事,但在有些情況下了解一些底層原理有助于我們更好的工作,比如現(xiàn)代高級(jí)語(yǔ)言多提供了多線程并發(fā)技術(shù),如果不深入下來(lái),那么有些由多線程造成問(wèn)題就很難排查和理解.
今天準(zhǔn)備來(lái)聊聊亂序執(zhí)行技術(shù)和內(nèi)存屏障.為了能讓大多數(shù)人理解,這里省略了很多不影響理解的旁枝末節(jié),但由于我個(gè)人水平有限,如果不妥之處,希望各位指正.
按順執(zhí)行技術(shù)
在開始說(shuō)亂序執(zhí)行之前,得先把按序執(zhí)行說(shuō)一遍.在早期處理器中,處理器執(zhí)行指令的順序就是按照我們編寫匯編代碼的順序執(zhí)行的,換句話說(shuō)此時(shí)處理器指令執(zhí)行順序和我們代碼順序一致,我們稱之為按序執(zhí)行(In Order Execution).我們以燒水泡茶為例來(lái)說(shuō)明按序執(zhí)行的過(guò)程(熟悉的同學(xué)會(huì)想起華羅庚的統(tǒng)籌學(xué)):
- 洗水壺
- 燒開水
- 洗茶壺
- 洗茶杯
- 拿茶葉
- 泡茶
我們假設(shè)每一步代表一條指令的執(zhí)行,此時(shí)從指令1到指令6執(zhí)行的過(guò)程就是我們所說(shuō)的按序執(zhí)行.整個(gè)過(guò)程可以表示為:
按序執(zhí)行對(duì)于早期處理器而言是一種行之有效的方案,但隨著對(duì)時(shí)間的要求,我們希望上述過(guò)程能夠在最短的時(shí)間內(nèi)執(zhí)行完成,這就促使人們迫切希望找到一種優(yōu)化指令執(zhí)行過(guò)程的方案.考慮上述執(zhí)行過(guò)程,我們發(fā)現(xiàn)洗茶壺這步完全沒(méi)有必要等待燒開水完成,也就是說(shuō)洗茶壺和洗水杯完全可以和燒開水同時(shí)進(jìn)行,這么一來(lái),優(yōu)化過(guò)的流程如圖:
這種通過(guò)改變?cè)袌?zhí)行順序而減少時(shí)間的執(zhí)行過(guò)程我們被稱之為亂序執(zhí)行,也稱為重排.到現(xiàn)在為止,我們已經(jīng)弄明白了什么是按序執(zhí)行,什么是亂序.那接下來(lái)就看看處理器中的亂序執(zhí)行技術(shù).
亂序執(zhí)行技術(shù)
處理器亂序執(zhí)行
隨著處理器流水線技術(shù)和多核技術(shù)的發(fā)展,目前的高級(jí)處理器通過(guò)提高內(nèi)部邏輯元件的利用率來(lái)提高運(yùn)行速度,通常會(huì)采用亂序執(zhí)行技術(shù).這里的亂序和上面談到燒水煮茶的道理是一樣的.
先來(lái)看一張?zhí)幚砥鞯暮?jiǎn)要結(jié)構(gòu)圖:
處理器從L1 Cache中取出一批指令,分析找出那些不存在相互依賴的指令,同時(shí)將其發(fā)射到多個(gè)邏輯單元執(zhí)行,比如現(xiàn)在有以下幾條指令:
LDR R1, [R0]侧但；
ADD R2, R1, R1咐扭；
ADD R4，R3伶椿，R3;
通過(guò)分析發(fā)現(xiàn)第二條指令和第一條指令存在依賴關(guān)系,但是和第3條指令無(wú)關(guān),那么處理器就可能將其發(fā)送到兩個(gè)邏輯單元去執(zhí)行,因此上述的指令執(zhí)行流程可能如下:
可以說(shuō)亂序執(zhí)行技術(shù)是處理器為提高運(yùn)算速度而做出違背代碼原有順序的優(yōu)化.在單核時(shí)代,處理器保證做出的優(yōu)化不會(huì)導(dǎo)致執(zhí)行結(jié)果遠(yuǎn)離預(yù)期目標(biāo),但在多核環(huán)境下卻并非如此.
首先多核時(shí)代,同時(shí)會(huì)有多個(gè)核執(zhí)行指令,每個(gè)核的指令都可能被亂序;另外,處理器還引入了L1,L2等緩存機(jī)制,每個(gè)核都有自己的緩存,這就導(dǎo)致邏輯次序上后寫入內(nèi)存的數(shù)據(jù)未必真的最后寫入.最終帶來(lái)了這么一個(gè)問(wèn)題:如果我們不做任何防護(hù)措施,處理器最終得出的結(jié)果和我們邏輯得出的結(jié)果大不相同.比如我們?cè)谝粋€(gè)核上執(zhí)行數(shù)據(jù)的寫入操作,并在最后寫一個(gè)標(biāo)記用來(lái)表示之前的數(shù)據(jù)已經(jīng)準(zhǔn)備好,然后從另一個(gè)核上通過(guò)判斷這個(gè)標(biāo)志來(lái)判定所需要的數(shù)據(jù)已經(jīng)就緒,這種做法存在風(fēng)險(xiǎn):標(biāo)記位先被寫入,但是之前的數(shù)據(jù)操作卻并未完成(可能是未計(jì)算完成,也可能是數(shù)據(jù)沒(méi)有從處理器緩存刷新到主存當(dāng)中),最終導(dǎo)致另一個(gè)核中使用了錯(cuò)誤的數(shù)據(jù).
編譯器指令重排
除了上述由處理器和緩存引起的亂序之外,現(xiàn)代編譯器同樣提供了亂序優(yōu)化.之所以出現(xiàn)編譯器亂序優(yōu)化其根本原因在于處理器每次只能分析一小塊指令,但編譯器卻能在很大范圍內(nèi)進(jìn)行代碼分析,從而做出更優(yōu)的策略,充分利用處理器的亂序執(zhí)行功能.
亂序的分類
現(xiàn)在來(lái)總結(jié)下所有可能發(fā)生亂序執(zhí)行的情況:
- 現(xiàn)代處理器采用指令并行技術(shù),在不存在數(shù)據(jù)依賴性的前提下,處理器可以改變語(yǔ)句對(duì)應(yīng)的機(jī)器指令的執(zhí)行順序來(lái)提高處理器執(zhí)行速度
- 現(xiàn)代處理器采用內(nèi)部緩存技術(shù),導(dǎo)致數(shù)據(jù)的變化不能及時(shí)反映在主存所帶來(lái)的亂序.
- 現(xiàn)代編譯器為優(yōu)化而重新安排語(yǔ)句的執(zhí)行順序
小結(jié)
盡管我們看到亂序執(zhí)行初始目的是為了提高效率,但是它看來(lái)其好像在這多核時(shí)代不盡人意,其中的某些"自作聰明"的優(yōu)化導(dǎo)致多線程程序產(chǎn)生各種各樣的意外.因此有必要存在一種機(jī)制來(lái)消除亂序執(zhí)行帶來(lái)的壞影響,也就是說(shuō)應(yīng)該允許程序員顯式的告訴處理器對(duì)某些地方禁止亂序執(zhí)行.這種機(jī)制就是所謂內(nèi)存屏障.不同架構(gòu)的處理器在其指令集中提供了不同的指令來(lái)發(fā)起內(nèi)存屏障,對(duì)應(yīng)在編程語(yǔ)言當(dāng)中就是提供特殊的關(guān)鍵字來(lái)調(diào)用處理器相關(guān)的指令.
內(nèi)存屏障
處理器亂序規(guī)則
上面我們說(shuō)了處理器會(huì)發(fā)生指令重排,現(xiàn)在來(lái)簡(jiǎn)單的看看常見處理器允許的重排規(guī)則,換言之就是處理器可以對(duì)那些指令進(jìn)行順序調(diào)整:
| 處理器 | Load-Load | Load-Store | Store-Store | Store-Load | 數(shù)據(jù)依賴 |
|---|---|---|---|---|---|
| x86 | N | N | N | Y | N |
| PowerPC | Y | Y | Y | Y | N |
| ia64 | Y | Y | Y | Y | N |
表格中的Y表示前后兩個(gè)操作允許重排,N則表示不允許重排.與這些規(guī)則對(duì)應(yīng)是的禁止重排的內(nèi)存屏障.
注意:處理器和編譯都會(huì)遵循數(shù)據(jù)依賴性,不會(huì)改變存在數(shù)據(jù)依賴關(guān)系的兩個(gè)操作的順序.所謂的數(shù)據(jù)依賴性就是如果兩個(gè)操作訪問(wèn)同一個(gè)變量,且這兩個(gè)操作中有一個(gè)是寫操作,那么久可以稱這兩個(gè)操作存在數(shù)據(jù)依賴性.舉個(gè)簡(jiǎn)單例子:
a=100;//write
b=a;//read
或者
a=100;//write
a=2000;//write
或者
a=b;//read
b=12;//write
以上所示的,兩個(gè)操作之間不能發(fā)生重排,這是處理器和編譯所必須遵循的.當(dāng)然這里指的是發(fā)生在單個(gè)處理器或單個(gè)線程中.
內(nèi)存屏障的分類
在開始看一下表格之前,務(wù)必確保自己了解Store和Load指令的含義.簡(jiǎn)單來(lái)說(shuō),Store就是將處理器緩存中的數(shù)據(jù)刷新到內(nèi)存中,而Load則是從內(nèi)存拷貝數(shù)據(jù)到緩存當(dāng)中.
| 屏障類型 | 指令示例 | 說(shuō)明 |
|---|---|---|
| LoadLoad Barriers | Load1;LoadLoad;Load2 | 該屏障確保Load1數(shù)據(jù)的裝載先于Load2及其后所有裝載指令的的操作 |
| StoreStore Barriers | Store1;StoreStore;Store2 | 該屏障確保Store1立刻刷新數(shù)據(jù)到內(nèi)存(使其對(duì)其他處理器可見)的操作先于Store2及其后所有存儲(chǔ)指令的操作 |
| LoadStore Barriers | Load1;LoadStore;Store2 | 確保Load1的數(shù)據(jù)裝載先于Store2及其后所有的存儲(chǔ)指令刷新數(shù)據(jù)到內(nèi)存的操作 |
| StoreLoad Barriers | Store1;StoreLoad;Load1 | 該屏障確保Store1立刻刷新數(shù)據(jù)到內(nèi)存的操作先于Load2及其后所有裝載裝載指令的操作.它會(huì)使該屏障之前的所有內(nèi)存訪問(wèn)指令(存儲(chǔ)指令和訪問(wèn)指令)完成之后,才執(zhí)行該屏障之后的內(nèi)存訪問(wèn)指令 |
StoreLoad Barriers同時(shí)具備其他三個(gè)屏障的效果,因此也稱之為全能屏障,是目前大多數(shù)處理器所支持的,但是相對(duì)其他屏障,該屏障的開銷相對(duì)昂貴.在x86架構(gòu)的處理器的指令集中,lock指令可以觸發(fā)StoreLoad Barriers.
現(xiàn)在我們綜合重排規(guī)則和內(nèi)存屏障類型來(lái)說(shuō)明一下.比如x86架構(gòu)的處理器中允許處理器對(duì)Store-Load操作進(jìn)行重排,與之對(duì)應(yīng)有StoreLoad Barriers禁止其重排.
as-if-serial語(yǔ)義
無(wú)論是處理器還是編譯器,不管怎么重排都要保證(單線程)程序的執(zhí)行結(jié)果不能被改變,這就是as-if-serial語(yǔ)義.比如燒水煮茶的最終結(jié)果永遠(yuǎn)是煮茶,而不能變成燒水.為了遵循這種語(yǔ)義,處理器和編譯器不能對(duì)存在數(shù)據(jù)依賴性的操作進(jìn)行重排,因?yàn)檫@種重排會(huì)改變操作結(jié)果,比如對(duì):
a=100;//write
b=a;//read
重排為:
b=a;
a=100;
此時(shí)b的值就是不正確的.如果不存在操作之間不存在數(shù)據(jù)依賴,那么這些操作就可能被處理器或編譯器進(jìn)行重排,比如:
a=10;
b=200;
result=a*b;
它們之間的依賴關(guān)系如圖:
由于a=10和b=200之間不存在依賴關(guān)系,因此編譯器或處理可以這兩兩個(gè)操作進(jìn)行重排,因此最終執(zhí)行順序可能有以下兩種情況:
但無(wú)論哪種執(zhí)行順序,最終的結(jié)果都是對(duì)的.
正是因?yàn)閍s-if-serial的存在,我們?cè)诰帉憜尉€程程序時(shí)會(huì)覺(jué)得好像它就是按代碼的順序執(zhí)行的,這讓我們可以不必關(guān)心重排的影響.換句話說(shuō),如果你從來(lái)沒(méi)有編寫多線程程序的需求,那就不需要關(guān)注今天我所說(shuō)的一切.
