程序序（Program Order）

對單線程程序而言，代碼會一行行順序執(zhí)行，就像我們編寫的程序的順序那樣。比如：

a = 1;
b = 2;

會先執(zhí)行`a = 1`，再執(zhí)行`b = 2`，從程序角度看到的代碼行依次執(zhí)行叫程序序，我們在此基礎上構建軟件，以此作為討論的基礎。

內存序（Memory Order）

與程序序相對應叫內存序，是指從某個角度觀察到的對于內存的讀和寫所真正發(fā)生的順序。

內存操作順序并不唯一，在一個包含core0和core1的CPU中，core0和core1有著各自的內存操作順序，這兩個內存操作順序不一定相同。

從包含多個Core的CPU的視角看到的全局內存操作順序（Global Memory Order）跟單core視角看到的內存操作順序亦不同，而這種不同，對于有些程序邏輯而言，是不可接受的，例如：

程序序要求`a = 1`在`b = 2`之前執(zhí)行，但內存操作順序可能并非如此，對a賦值1并不確保發(fā)生在對b賦值2之前。

• 如果編譯器認為對b賦值沒有依賴對a賦值，那它完全可以在編譯期為了性能調整編譯后的匯編指令順序
• 即使編譯器不做調整，到了執(zhí)行期，也有可能對b的賦值先于對a賦值執(zhí)行

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

但多核系統，硬件不提供這樣的保證，多線程程序中，每個線程所工作的Core觀察到的不同內存操作序，以及這些順序與全局內存序的差異，常常導致多線程同步失敗，所以，需要有同步機制確保內存序與程序序的一致，內存屏障（Memory Barrier）的引入，就是為了解決這個問題，它讓不同的Core之間，以及Core與全局內存序達成一致。

亂序執(zhí)行（Out-of-order Execution）

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

答案是為了性能。

我們先看看沒有亂序執(zhí)行之前，早期的有序處理器（In-order Processors）是怎么處理指令的？

• 指令獲取，從代碼節(jié)內存區(qū)域加載指令到I-Cache
• 譯碼
• 如果指令操作數可用（例如操作數位于寄存器中），則分發(fā)指令到對應功能模塊中；如果操作數不可用，通常是需要從內存加載，則處理器會stall，一直等到它們就緒，知道數據被加載到cache或拷貝進寄存器
• 指令被功能單元執(zhí)行
• 功能單元將結果寫回寄存器或內存位置

亂序處理器（Out-of-order Processors）又是怎么處理指令的呢？

• 指令獲取，從代碼節(jié)內存區(qū)域加載指令到I-Cache
• 譯碼
• 分發(fā)指令到指令隊列
• 指令在指令隊列中等待，一旦操作數就緒，指令就離開指令隊列，那怕它之前的指令未被執(zhí)行（亂序）
• 指令被派往功能單元并被執(zhí)行
• 執(zhí)行結果放入隊列（Store Buffer），而不是直接寫入Cache
• 只有更早請求執(zhí)行的指令結果寫入cache后，指令執(zhí)行結果才寫入cache，通過對指令結果排序寫入cache，使得執(zhí)行看起來是有序的。

指令亂序執(zhí)行是結果，但原因并非只有CPU的亂序執(zhí)行，而是由兩種因素導致：

• 編譯期：指令重排（編譯器），編譯器會為了性能而對指令重排，源碼上先后的兩行，被編譯器編譯后，可能調換指令順序，但編譯器會基于一套規(guī)則做指令重排，有明顯依賴的指令不會被隨意重排，指令重排不能破壞程序邏輯。
• 運行期：亂序執(zhí)行（CPU），CPU的超標量流水線、以及預測執(zhí)行、Cache-Miss等都有可能導致指令亂序執(zhí)行，也就是說，后面的指令有可能先于前面的指令執(zhí)行。

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，就能確保單核程序的執(zhí)行遵從程序順序性，但多核還是有問題，讓我們考查下面的程序：

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


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


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

假設a和b都被初始化為0；CPU0執(zhí)行x()函數，CPU1執(zhí)行y()函數；變量a在CPU1的local Cache里，變量b在CPU0的local Cache里。

• CPU0執(zhí)行`a = 1;`的時候，因為a不在CPU0的local cache，CPU0會把a的新值1寫入Store Buffer里，并發(fā)送Read Invalidate消息給其他CPU
• CPU1執(zhí)行`while (b);`,因為b不在CPU1的local cache里，CPU1會發(fā)送Read Invalidate消息去其他CPU獲取b的值
• CPU0執(zhí)行`b = 2;`，因為b在CPU0的local Cache，所以直接更新local cache中b的副本
• CPU0收到CPU1發(fā)來的讀b請求，把b的新值（2）發(fā)送給CPU1；同時存放b的Cache Line的狀態(tài)被設置為Shared，以反應b同時被CPU0和CPU1 cache住的事實
• CPU1收到b的新值（2）后結束循環(huán)，繼續(xù)執(zhí)行`assert(a == 1);`，因為此時local Cache中的a值為0，所以斷言失敗
• CPU1收到CPU0發(fā)來的Read Invalidate后，更新a的值為1，但為時已晚，程序在上一步已經崩了

怎么辦？答案留到內存屏障一節(jié)揭曉。

Invalidate Queue

為什么需要Invalidate Queue

當一個變量加載到多個core的Cache，則這個CacheLine處于Shared狀態(tài)，如果Core1要修改這個變量，則需要通過發(fā)送核間消息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發(fā)出的Invalidate請求，不會導致發(fā)生Invalidate請求的Core不必要的Stall，另一方面也提供了進一步優(yōu)化可能，比如在一個CacheLine里的多個變量的Invalidate可以攢一次做了。

但寫Store Buffer的方式其實是Write Invalidate，它并非立即寫入內存，如果其他核此時從內存讀數，則有可能不一致。

內存屏障

那有沒有方法確保對b的賦值一定先于對a的賦值呢？有，內存屏障被用來提供這個保障。

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

語義上，內存屏障之前的所有寫操作都要寫入內存；內存屏障之后的讀操作都可以獲得同步屏障之前的寫操作的結果。

內存屏障，其實就是提供一種機制，確保代碼里順序寫下的多行，會按照書寫的順序，被存入內存，主要是解決StoreBuffer引入導致的寫入內存間隙的問題。

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

像上面那樣在a=1后、b=2前插入一條內存屏障語句，就能確保a=1先于b=2生效，從而解決了內存亂序訪問問題，那插入的這句smp_mb()，到底會干什么呢？

回憶前面的流程，CPU0在執(zhí)行完`a = 1`之后，執(zhí)行smp_mb()操作，這時候，它會給Store Buffer里的所有數據項做一個標記（marked），然后繼續(xù)執(zhí)行`b = 2`，但這時候雖然b在自己的cache里，但由于store buffer里有marked條目，所以，CPU0不會修改cache中的b，而是把它寫入Store Buffer；所以CPU0收到Read消息后，會把b的0值發(fā)給CPU1，所以繼續(xù)在`while (b);`自旋。

簡而言之，Core執(zhí)行到write memory barrier（wmb）的時候，如果Store Buffer還有懸而未決的store操作，則都會被mark上，直到被標注的Store操作進入內存后，后續(xù)的Store操作才能被執(zhí)行，因此wmb保障了barrier前后操作的順序，它不關心barrier前的多個操作的內存序，以及barrier后的多個操作的內存序，是否與Global Memory Order一致。

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

wmb()保證`a = 1; b = 2;`發(fā)生在`c = 3; d = 4;`之前，不保證`a = 1`和`b = 2`的內存序，也不保證`c = 3`和`d = 4`的內部序。

Invalidate Queue的引入的問題

就像引入Store Buffer會影響Store的內存一致性，Invalidate Queue的引入會影響Load的內存一致性：

因為Invalidate queue會緩存其他核發(fā)過來的消息，比如Invalidate某個數據的消息被delay處置，導致core在Cache Line中命中這個數據，而這個Cache Line本應該被Invalidate消息標記無效。

如何解決這個問題呢？

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

所以，我們可以像下面這樣修改代碼：

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

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

系統對內存屏障的支持

gcc編譯器在遇到內嵌匯編語句`asm volatile("" ::: "memory");`將以此作為一條內存屏障，重排序內存操作，即此語句之前的各種編譯優(yōu)化將不會持續(xù)到此語句之后。

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的順序。