談亂序執行和內存屏障

10多年前的程序員對處理器亂序執行和內存屏障應該是很熟悉的,但隨著計算機技術突飛猛進的發展,我們離底層原理越來越遠,這并不是一件壞事,但在有些情況下了解一些底層原理有助于我們更好的工作,比如現代高級語言多提供了多線程并發技術,如果不深入下來,那么有些由多線程造成問題就很難排查和理解.

今天準備來聊聊亂序執行技術和內存屏障.為了能讓大多數人理解,這里省略了很多不影響理解的旁枝末節,但由于我個人水平有限,如果不妥之處,希望各位指正.

按順執行技術

在開始說亂序執行之前,得先把按序執行說一遍.在早期處理器中,處理器執行指令的順序就是按照我們編寫匯編代碼的順序執行的,換句話說此時處理器指令執行順序和我們代碼順序一致,我們稱之為按序執行(In Order Execution).我們以燒水泡茶為例來說明按序執行的過程(熟悉的同學會想起華羅庚的統籌學):

1. 洗水壺
2. 燒開水
3. 洗茶壺
4. 洗茶杯
5. 拿茶葉
6. 泡茶

我們假設每一步代表一條指令的執行,此時從指令1到指令6執行的過程就是我們所說的按序執行.整個過程可以表示為:

按序執行對于早期處理器而言是一種行之有效的方案,但隨著對時間的要求,我們希望上述過程能夠在最短的時間內執行完成,這就促使人們迫切希望找到一種優化指令執行過程的方案.考慮上述執行過程,我們發現洗茶壺這步完全沒有必要等待燒開水完成,也就是說洗茶壺和洗水杯完全可以和燒開水同時進行,這么一來,優化過的流程如圖:

這種通過改變原有執行順序而減少時間的執行過程我們被稱之為亂序執行,也稱為重排.到現在為止,我們已經弄明白了什么是按序執行,什么是亂序.那接下來就看看處理器中的亂序執行技術.

亂序執行技術

處理器亂序執行

隨著處理器流水線技術和多核技術的發展,目前的高級處理器通過提高內部邏輯元件的利用率來提高運行速度,通常會采用亂序執行技術.這里的亂序和上面談到燒水煮茶的道理是一樣的.

先來看一張處理器的簡要結構圖:

處理器從L1 Cache中取出一批指令,分析找出那些不存在相互依賴的指令,同時將其發射到多個邏輯單元執行,比如現在有以下幾條指令:

LDR   R1, [R0]；
ADD   R2, R1, R1；
ADD   R4，R3，R3;

通過分析發現第二條指令和第一條指令存在依賴關系,但是和第3條指令無關,那么處理器就可能將其發送到兩個邏輯單元去執行,因此上述的指令執行流程可能如下:

可以說亂序執行技術是處理器為提高運算速度而做出違背代碼原有順序的優化.在單核時代,處理器保證做出的優化不會導致執行結果遠離預期目標,但在多核環境下卻并非如此.

首先多核時代,同時會有多個核執行指令,每個核的指令都可能被亂序;另外,處理器還引入了L1,L2等緩存機制,每個核都有自己的緩存,這就導致邏輯次序上后寫入內存的數據未必真的最后寫入.最終帶來了這么一個問題:如果我們不做任何防護措施,處理器最終得出的結果和我們邏輯得出的結果大不相同.比如我們在一個核上執行數據的寫入操作,并在最后寫一個標記用來表示之前的數據已經準備好,然后從另一個核上通過判斷這個標志來判定所需要的數據已經就緒,這種做法存在風險:標記位先被寫入,但是之前的數據操作卻并未完成(可能是未計算完成,也可能是數據沒有從處理器緩存刷新到主存當中),最終導致另一個核中使用了錯誤的數據.

編譯器指令重排

除了上述由處理器和緩存引起的亂序之外,現代編譯器同樣提供了亂序優化.之所以出現編譯器亂序優化其根本原因在于處理器每次只能分析一小塊指令,但編譯器卻能在很大范圍內進行代碼分析,從而做出更優的策略,充分利用處理器的亂序執行功能.

亂序的分類

現在來總結下所有可能發生亂序執行的情況:

• 現代處理器采用指令并行技術,在不存在數據依賴性的前提下,處理器可以改變語句對應的機器指令的執行順序來提高處理器執行速度
• 現代處理器采用內部緩存技術,導致數據的變化不能及時反映在主存所帶來的亂序.
• 現代編譯器為優化而重新安排語句的執行順序

小結

盡管我們看到亂序執行初始目的是為了提高效率,但是它看來其好像在這多核時代不盡人意,其中的某些”自作聰明”的優化導致多線程程序產生各種各樣的意外.因此有必要存在一種機制來消除亂序執行帶來的壞影響,也就是說應該允許程序員顯式的告訴處理器對某些地方禁止亂序執行.這種機制就是所謂內存屏障.不同架構的處理器在其指令集中提供了不同的指令來發起內存屏障,對應在編程語言當中就是提供特殊的關鍵字來調用處理器相關的指令.

內存屏障

處理器亂序規則

上面我們說了處理器會發生指令重排,現在來簡單的看看常見處理器允許的重排規則,換言之就是處理器可以對那些指令進行順序調整:

處理器	Load-Load	Load-Store	Store-Store	Store-Load	數據依賴
x86	N	N	N	Y	N
PowerPC	Y	Y	Y	Y	N
ia64	Y	Y	Y	Y	N

表格中的Y表示前后兩個操作允許重排,N則表示不允許重排.與這些規則對應是的禁止重排的內存屏障.

注意:處理器和編譯都會遵循數據依賴性,不會改變存在數據依賴關系的兩個操作的順序.所謂的數據依賴性就是如果兩個操作訪問同一個變量,且這兩個操作中有一個是寫操作,那么久可以稱這兩個操作存在數據依賴性.舉個簡單例子:

a=100;//write
b=a;//read

或者
a=100;//write
a=2000;//write
或者
a=b;//read
b=12;//write

以上所示的,兩個操作之間不能發生重排,這是處理器和編譯所必須遵循的.當然這里指的是發生在單個處理器或單個線程中.

內存屏障的分類

在開始看一下表格之前,務必確保自己了解Store和Load指令的含義.簡單來說,Store就是將處理器緩存中的數據刷新到內存中,而Load則是從內存拷貝數據到緩存當中.

屏障類型	指令示例	說明
LoadLoad Barriers	Load1;LoadLoad;Load2	該屏障確保Load1數據的裝載先于Load2及其后所有裝載指令的的操作
StoreStore Barriers	Store1;StoreStore;Store2	該屏障確保Store1立刻刷新數據到內存(使其對其他處理器可見)的操作先于Store2及其后所有存儲指令的操作
LoadStore Barriers	Load1;LoadStore;Store2	確保Load1的數據裝載先于Store2及其后所有的存儲指令刷新數據到內存的操作
StoreLoad Barriers	Store1;StoreLoad;Load1	該屏障確保Store1立刻刷新數據到內存的操作先于Load2及其后所有裝載裝載指令的操作.它會使該屏障之前的所有內存訪問指令(存儲指令和訪問指令)完成之后,才執行該屏障之后的內存訪問指令

StoreLoad Barriers同時具備其他三個屏障的效果,因此也稱之為全能屏障,是目前大多數處理器所支持的,但是相對其他屏障,該屏障的開銷相對昂貴.在x86架構的處理器的指令集中,lock指令可以觸發StoreLoad Barriers.

現在我們綜合重排規則和內存屏障類型來說明一下.比如x86架構的處理器中允許處理器對Store-Load操作進行重排,與之對應有StoreLoad Barriers禁止其重排.

as-if-serial語義

無論是處理器還是編譯器,不管怎么重排都要保證(單線程)程序的執行結果不能被改變,這就是as-if-serial語義.比如燒水煮茶的最終結果永遠是煮茶,而不能變成燒水.為了遵循這種語義,處理器和編譯器不能對存在數據依賴性的操作進行重排,因為這種重排會改變操作結果,比如對:

a=100;//write
b=a;//read

重排為:

b=a;
a=100;

此時b的值就是不正確的.如果不存在操作之間不存在數據依賴,那么這些操作就可能被處理器或編譯器進行重排,比如:

a=10;
b=200;
result=a*b;

它們之間的依賴關系如圖:

由于 a=10 和 b=200 之間不存在依賴關系,因此編譯器或處理可以這兩兩個操作進行重排,因此最終執行順序可能有以下兩種情況:

但無論哪種執行順序,最終的結果都是對的.

正是因為as-if-serial的存在,我們在編寫單線程程序時會覺得好像它就是按代碼的順序執行的,這讓我們可以不必關心重排的影響.換句話說,如果你從來沒有編寫多線程程序的需求,那就不需要關注今天我所說的一切.

 

來自：http://blog.csdn.net/dd864140130/article/details/56494925