談亂序執行和記憶體屏障

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=;//write
b=a;//read

或者
a=;//write
a=;//write
或者
a=b;//read
b=;//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=;//write
b=a;//read
           

重排為:

b=a;
a=;
           

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

a=;
b=;
result=a*b;
           

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

由于

a=10

和

b=200

之間不存在依賴關系,是以編譯器或處理可以這兩兩個操作進行重排,是以最終執行順序可能有以下兩種情況:

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

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