關於多執行緒同步的一切:亂序執行和記憶體屏障

語言: CN / TW / HK

程式序(Program Order)

對單執行緒程式而言,程式碼會一行行順序執行,就像我們編寫的程式的順序那樣。比如:

a = 1;
b = 2;

會先執行`a = 1`,再執行`b = 2`,從程式角度看到的程式碼行依次執行叫程式序,我們在此基礎上構建軟體,以此作為討論的基礎。

記憶體序(Memory Order)

與程式序相對應叫記憶體序,是指從某個角度觀察到的對於記憶體的讀和寫所真正發生的順序。

記憶體操作順序並不唯一,在一個包含core0和core1的CPU中,core0和core1有著各自的記憶體操作順序,這兩個記憶體操作順序不一定相同。

從包含多個Core的CPU的視角看到的全域性記憶體操作順序(Global Memory Order)跟單core視角看到的記憶體操作順序亦不同,而這種不同,對於有些程式邏輯而言,是不可接受的,例如:

程式序要求`a = 1`在`b = 2`之前執行,但記憶體操作順序可能並非如此,對a賦值1並不確保發生在對b賦值2之前。

  • 如果編譯器認為對b賦值沒有依賴對a賦值,那它完全可以在編譯期為了效能調整編譯後的彙編指令順序
  • 即使編譯器不做調整,到了執行期,也有可能對b的賦值先於對a賦值執行

雖然對一個Core而言,如上所述,這個Core觀察到的記憶體操作順序不一定符合程式序,但記憶體操作序和程式序必定產生相同的結果,無論在單Core上對a、b的賦值哪個先發生,結果上都是a被賦值為1、b被賦值為2,如果單核上,亂序執行會影響結果,那編譯器的指令重排和CPU亂序執行便不會發生,硬體會提供這項保證。

但多核系統,硬體不提供這樣的保證,多執行緒程式中,每個執行緒所工作的Core觀察到的不同記憶體操作序,以及這些順序與全域性記憶體序的差異,常常導致多執行緒同步失敗,所以,需要有同步機制確保記憶體序與程式序的一致,記憶體屏障(Memory Barrier)的引入,就是為了解決這個問題,它讓不同的Core之間,以及Core與全域性記憶體序達成一致。

亂序執行(Out-of-order Execution)

亂序執行會引起記憶體順序跟程式順序不同,亂序執行的原因是多方面的,比如編譯器指令重排、超標量指令流水線、預測執行、Cache-Miss等。記憶體操作順序無法精確匹配程式順序,這有可能帶來混亂,既然有副作用,那為什麼還需要亂序執行呢?

答案是為了效能。

我們先看看沒有亂序執行之前,早期的有序處理器(In-order Processors)是怎麼處理指令的?

  • 指令獲取,從程式碼節記憶體區域載入指令到I-Cache
  • 譯碼
  • 如果指令運算元可用(例如運算元位於暫存器中),則分發指令到對應功能模組中;如果運算元不可用,通常是需要從記憶體載入,則處理器會stall,一直等到它們就緒,知道資料被載入到cache或拷貝進暫存器
  • 指令被功能單元執行
  • 功能單元將結果寫回暫存器或記憶體位置

亂序處理器(Out-of-order Processors)又是怎麼處理指令的呢?

  • 指令獲取,從程式碼節記憶體區域載入指令到I-Cache
  • 譯碼
  • 分發指令到指令佇列
  • 指令在指令佇列中等待,一旦運算元就緒,指令就離開指令佇列,那怕它之前的指令未被執行(亂序)
  • 指令被派往功能單元並被執行
  • 執行結果放入佇列(Store Buffer),而不是直接寫入Cache
  • 只有更早請求執行的指令結果寫入cache後,指令執行結果才寫入cache,通過對指令結果排序寫入cache,使得執行看起來是有序的。

指令亂序執行是結果,但原因並非只有CPU的亂序執行,而是由兩種因素導致:

  • 編譯期:指令重排(編譯器),編譯器會為了效能而對指令重排,原始碼上先後的兩行,被編譯器編譯後,可能調換指令順序,但編譯器會基於一套規則做指令重排,有明顯依賴的指令不會被隨意重排,指令重排不能破壞程式邏輯。
  • 執行期:亂序執行(CPU),CPU的超標量流水線、以及預測執行、Cache-Miss等都有可能導致指令亂序執行,也就是說,後面的指令有可能先於前面的指令執行。

Store Buffer

為什麼需要Store Buffer?

考慮下面的程式碼:

void set_a()
{
   a = 1;
}
  • 假設執行在core0上的set_a()對整型變數a賦值1,計算機通常不會直接寫穿通到記憶體,而是會在Cache中修改對應Cache Line
  • 如果Core0的Cache裡沒有a,賦值操作(store)會造成Cache Miss
  • Core0會stall在等待Cache就緒(比如從記憶體載入變數a到對應的Cache Line),但Stall會損害CPU效能,相當於CPU在這裡停頓,白白浪費著寶貴的CPU時間
  • 有了Store Buffer,當變數在Cache中沒有就位的時候,就先Buffer住這個Store操作,而Store操作一旦進入Store Buffer,core便認為自己Store完成,當隨後Cache就位,store會自動寫入對應cache。

所以,我們需要Store Buffer,每個Core都有獨立的Store Buffer,每個Core都訪問私有的Store Buffer, Store Buffer幫助CPU遮掩了Store操作帶來的延遲。

Store Buffer會帶來什麼問題?

a = 1;
b = 2;
assert(a == 1);

上面的程式碼,斷言a==1的時候,需要讀(load)變數a的值,而如果a在被賦值前就在Cache中,就會從Cache中讀到a的舊值(可能是1之外的其他值),所以斷言就可能失敗。

但這樣的結果顯然是不能接受的,它違背了最直觀的程式順序性。

問題出在變數a除儲存在記憶體外,還有2份拷貝,一份在Store Buffer裡,一份在Cache裡,如果不考慮這2份拷貝的關係,就會出現資料不一致。那怎麼修復這個問題呢?

可以通過在Core Load資料的時候,先檢查Store Buffer中是否有懸而未決的a的新值,如果有,則取新值;否則從cache取a的副本。這種技術在多級流水線CPU設計的時候就經常使用,叫Store Forwarding。有了Store Buffer Forwarding,就能確保單核程式的執行遵從程式順序性,但多核還是有問題,讓我們考查下面的程式:

int a = 0; // 被CPU1 CACHE
int b = 0; // 被CPU0 CACHE


// CPU0執行
void x() {
   a = 1;
   b = 2;
}


// CPU1執行
void y() {
   while (b);
   assert(a == 1);
}

假設a和b都被初始化為0;CPU0執行x()函式,CPU1執行y()函式;變數a在CPU1的local Cache裡,變數b在CPU0的local Cache裡。

  • CPU0執行`a = 1;`的時候,因為a不在CPU0的local cache,CPU0會把a的新值1寫入Store Buffer裡,併發送Read Invalidate訊息給其他CPU
  • CPU1執行`while (b);`,因為b不在CPU1的local cache裡,CPU1會發送Read Invalidate訊息去其他CPU獲取b的值
  • CPU0執行`b = 2;`,因為b在CPU0的local Cache,所以直接更新local cache中b的副本
  • CPU0收到CPU1發來的讀b請求,把b的新值(2)傳送給CPU1;同時存放b的Cache Line的狀態被設定為Shared,以反應b同時被CPU0和CPU1 cache住的事實
  • CPU1收到b的新值(2)後結束迴圈,繼續執行`assert(a == 1);`,因為此時local Cache中的a值為0,所以斷言失敗
  • CPU1收到CPU0發來的Read Invalidate後,更新a的值為1,但為時已晚,程式在上一步已經崩了

怎麼辦?答案留到記憶體屏障一節揭曉。

Invalidate Queue

為什麼需要Invalidate Queue

當一個變數載入到多個core的Cache,則這個CacheLine處於Shared狀態,如果Core1要修改這個變數,則需要通過傳送核間訊息Invalidate來通知其他Core把對應的Cache Line置為Invalid,當其他Core都Invalid這個CacheLine後,則本Core獲得該變數的獨佔權,這個時候就可以修改它了。

收到Invalidate訊息的core需要回Invalidate ACK,一個個core都這樣ACK,等所有core都回復完,Core1才能修改它,這樣CPU就白白浪費。

事實上,其他核在收到Invalidate訊息後,會把Invalidate訊息快取到Invalidate Queue,並立即回覆ACK,真正Invalidate動作可以延後再做,這樣一方面因為Core可以快速返回別的Core發出的Invalidate請求,不會導致發生Invalidate請求的Core不必要的Stall,另一方面也提供了進一步優化可能,比如在一個CacheLine裡的多個變數的Invalidate可以攢一次做了。

但寫Store Buffer的方式其實是Write Invalidate,它並非立即寫入記憶體,如果其他核此時從記憶體讀數,則有可能不一致。

記憶體屏障

那有沒有方法確保對b的賦值一定先於對a的賦值呢?有,記憶體屏障被用來提供這個保障。

記憶體屏障(Memory Barrier),也稱記憶體柵欄、屏障指令等,是一類同步屏障指令,是CPU或編譯器在對記憶體隨機訪問的操作中的一個同步點,同步點之前的所有讀寫操作都執行後,才可以開始執行此點之後的操作。

語義上,記憶體屏障之前的所有寫操作都要寫入記憶體;記憶體屏障之後的讀操作都可以獲得同步屏障之前的寫操作的結果。

記憶體屏障,其實就是提供一種機制,確保程式碼裡順序寫下的多行,會按照書寫的順序,被存入記憶體,主要是解決StoreBuffer引入導致的寫入記憶體間隙的問題。

void x() {
   a = 1;
   wmb();
   b = 2;
}

像上面那樣在a=1後、b=2前插入一條記憶體屏障語句,就能確保a=1先於b=2生效,從而解決了記憶體亂序訪問問題,那插入的這句smp_mb(),到底會幹什麼呢?

回憶前面的流程,CPU0在執行完`a = 1`之後,執行smp_mb()操作,這時候,它會給Store Buffer裡的所有資料項做一個標記(marked),然後繼續執行`b = 2`,但這時候雖然b在自己的cache裡,但由於store buffer裡有marked條目,所以,CPU0不會修改cache中的b,而是把它寫入Store Buffer;所以CPU0收到Read訊息後,會把b的0值發給CPU1,所以繼續在`while (b);`自旋。

簡而言之,Core執行到write memory barrier(wmb)的時候,如果Store Buffer還有懸而未決的store操作,則都會被mark上,直到被標註的Store操作進入記憶體後,後續的Store操作才能被執行,因此wmb保障了barrier前後操作的順序,它不關心barrier前的多個操作的記憶體序,以及barrier後的多個操作的記憶體序,是否與Global Memory Order一致。

a = 1;
b = 2;
wmb();
c = 3;
d = 4;

wmb()保證`a = 1; b = 2;`發生在`c = 3; d = 4;`之前,不保證`a = 1`和`b = 2`的記憶體序,也不保證`c = 3`和`d = 4`的內部序。

Invalidate Queue的引入的問題

就像引入Store Buffer會影響Store的記憶體一致性,Invalidate Queue的引入會影響Load的記憶體一致性:

因為Invalidate queue會快取其他核發過來的訊息,比如Invalidate某個資料的訊息被delay處置,導致core在Cache Line中命中這個資料,而這個Cache Line本應該被Invalidate訊息標記無效。

如何解決這個問題呢?

  • 一種思路是硬體確保每次load資料的時候,需要確保Invalidate Queue被清空,這樣可以保證load操作的強順序。
  • 軟體的思路,就是仿照wmb()的定義,加入rmb()約束。rmb()給我們的invalidate queue加上標記。當一個load操作發生的時候,之前的rmb()所有標記的invalidate命令必須全部執行完成,然後才可以讓隨後的load發生。這樣,我們就在rmb()前後保證了load觀察到的順序等同於global memory order。

所以,我們可以像下面這樣修改程式碼:

//============
a = 1;
wmb();
b = 2;

//=============
while(b != 2) {};
rmb();
assert(a == 1);

系統對記憶體屏障的支援

gcc編譯器在遇到內嵌彙編語句`asm volatile("" ::: "memory");`將以此作為一條記憶體屏障,重排序記憶體操作,即此語句之前的各種編譯優化將不會持續到此語句之後。

Linux 核心提供函式 barrier()用於讓編譯器保證其之前的記憶體訪問先於其之後的完成。

```c
#define barrier() __asm__ __volatile__("" ::: "memory")
```

CPU記憶體屏障:

  • 通用barrier,保證讀寫操作有序, mb()和smp_mb()
  • 寫操作barrier,僅保證寫操作有序,wmb()和smp_wmb()
  • 讀操作barrier,僅保證讀操作有序,rmb()和smp_rmb()

小結

為了提高處理器的效能,SMP中引入了store buffer(以及對應實現store buffer forwarding)和invalidate queue。

store buffer的引入導致core上的store順序可能不匹配於global memory的順序,對此,我們需要使用wmb()來解決。

invalidate queue的存在導致core上觀察到的load順序可能與global memory order不一致,對此,我們需要使用rmb()來解決。

由於wmb()和rmb()分別只單獨作用於store buffer和invalidate queue,因此這兩個memory barrier共同保證了store/load的順序。