什么是亂序執(zhí)行

亂序執(zhí)行 [1] ，簡單說就是程序里面的代碼的執(zhí)行順序，有可能會(huì)被編譯器、CPU 根據(jù)某種策略調(diào)整順序（俗稱，“打亂”）——雖然從單線程的角度看，亂序執(zhí)行不影響執(zhí)行結(jié)果。

為什么需要亂序執(zhí)行

主要原因是 CPU 內(nèi)部采用 流水線技術(shù) [2] 。抽象且簡化地看，一個(gè) CPU 指令的執(zhí)行過程可以分成 4 個(gè)階段：取指、譯碼、執(zhí)行、寫回。

這 4 個(gè)階段分別由 4 個(gè)獨(dú)立物理執(zhí)行單元來完成。這種情況下，如果指令之間沒有依賴關(guān)系，后一條指令并不需要等到前一條指令完全執(zhí)行完成再開始執(zhí)行。而是前一條指令完成取指之后，后一條指令便可以開始執(zhí)行取指操作。

比較理想的情況如下圖所示：指令之間無依賴，可以使流水線的并行度最大化。

在 按序執(zhí)行 的情況下，一旦遇到指令依賴的情況，流水線就會(huì)停滯。比如：

上面的偽代碼中，指令 2 依賴指令 1 的執(zhí)行結(jié)果。該指令 1 執(zhí)行完成之前，指令 2 無法執(zhí)行，這會(huì)讓流水線的執(zhí)行效率大大降低。

觀察到，指令 3 和指令 4 對(duì)其它指令沒有依賴，可以考慮將這兩條指令”亂序“到指令 2 之前。

這樣，流水線執(zhí)行單元就可以盡可能處于工作狀態(tài)。

總的來說，通過亂序執(zhí)行，合理調(diào)整指令的執(zhí)行順序，可以提高流水線的運(yùn)行效率，讓指令的執(zhí)行能夠盡可能地并行起來。

Compiler Fence

在多線程的環(huán)境下，亂序執(zhí)行的存在，很容易打破一些預(yù)期，造成一些意想不到的問題。

亂序執(zhí)行有兩種情況：

1. 在編譯期，編譯器進(jìn)行指令重排。
2. 在運(yùn)行期，CPU 進(jìn)行指令亂序執(zhí)行。

我們先來看一個(gè)編譯器指令重排的例子：

#include <atomic>// 按序遞增發(fā)號(hào)器std::atomic<int> timestamp_oracle{0};// 當(dāng)前處理的號(hào)碼int now_serving_ts{0};int shared_value;int compute();void memory_reorder() {    // 原子地獲取一個(gè)號(hào)碼    int ts = timestamp_oracle.fetch_add(1);    // 加鎖：判斷當(dāng)前是否輪到這個(gè)號(hào)碼，否則就循環(huán)等    while (now_serving_ts != ts);    // 臨界區(qū)：開始處理請(qǐng)求    shared_value = compute();        // 編譯器 memory barrier    asm volatile('' : : : 'memory');    // 解鎖：下一個(gè)要處理的號(hào)碼    now_serving_ts = ts + 1;}

簡單解釋一下這段代碼：

1. 這個(gè)程序通過維護(hù)一個(gè)“發(fā)號(hào)器 timestamp_oracle”，來實(shí)現(xiàn)按順序處理每個(gè)線程的請(qǐng)求。
2. 每個(gè)線程先從“發(fā)號(hào)器”取一個(gè)號(hào)，然后不停判斷當(dāng)前是否輪到自己執(zhí)行，類似自旋鎖的邏輯。
3. 每個(gè)線程執(zhí)行完，將“號(hào)碼”切換到下一個(gè)。

在 O1 的編譯優(yōu)化選項(xiàng)下，編譯出來的匯編指令沒有被重排（通過左右兩邊的代碼行背景色就可以看出來）。

在 O2 的編譯優(yōu)化選項(xiàng)下，出現(xiàn)了指令被重排了，并且這里的指令重排打破了程序的預(yù)期，先切換了 now_serving_ts，再更新 shared_value，導(dǎo)致 shared_value 可能被并發(fā)修改。

為了阻止編譯器重排這兩句代碼的指令，需要在它們之間插入一個(gè) compiler fence。

這個(gè)是 GCC 擴(kuò)展的 compiler fence 的寫法。這條指令告訴編譯器（ GCC 官方文檔 [3] ）：

1. 防止這條 fence 指令上方的內(nèi)存訪問操作被移到下方，同時(shí)防止下方的內(nèi)存訪問操作移到上面，也就是防止了亂序。
2. 讓編譯器把所有緩存在寄存器中的內(nèi)存變量 flush 到內(nèi)存中，然后重新從內(nèi)存中讀取這些值。

對(duì)于第 2 點(diǎn)，有時(shí)候我們只需要刷新部分變量。刷新所有寄存器并不一定完全符合我們的預(yù)期，并且會(huì)引入不必要的開銷。GCC 支持指定變量的 compiler fence。

write(x)asm volatile('': '=m'(y) : 'm'(x):)read(y)

中間的內(nèi)聯(lián)匯編指令告訴編譯器不要把 write(x) 和 read(y) 這兩個(gè)操作亂序。

CPU Fence

先來看一個(gè)例子：

上面的例子中，由于 compiler fence 的存在，編譯器不會(huì)對(duì)函數(shù) f1 和函數(shù) f2 內(nèi)部的指令進(jìn)行重排。

此時(shí)，如果 CPU 執(zhí)行時(shí)也沒有亂序，是不可能出現(xiàn) r0 == 0 && r1 == 0 的情況的。不幸的是，由于 CPU 亂序執(zhí)行的存在，這種情況是可能發(fā)生的。看下面這個(gè)例子：

#include <iostream>#include <thread>int x = 0;int y = 0;int r0 = 100;int r1 = 100;void f1() {    x = 1;    asm volatile('': : :'memory');    r0 = y;}void f2() {    y = 1;    asm volatile('': : :'memory');    r1 = x;}void init() {    x = 0;    y = 0;    r0 = 100;    r1 = 100;}bool check() {    return r0 == 0 && r1 == 0;}std::atomic<bool> wait1{true};std::atomic<bool> wait2{true};std::atomic<bool> stop{false};void loop1() {    while(!stop.load(std::memory_order_relaxed)) {        while (wait1.load(std::memory_order_relaxed));        asm volatile('' ::: 'memory');        f1();        asm volatile('' ::: 'memory');        wait1.store(true, std::memory_order_relaxed);    }}void loop2() {    while (!stop.load(std::memory_order_relaxed)) {        while (wait2.load(std::memory_order_relaxed));        asm volatile('' ::: 'memory');        f2();        asm volatile('' ::: 'memory');        wait2.store(true, std::memory_order_relaxed);    }}int main() {    std::thread thread1(loop1);    std::thread thread2(loop2);    long count = 0;    while(true) {        count++;        init();        asm volatile('' ::: 'memory');        wait1.store(false, std::memory_order_relaxed);        wait2.store(false, std::memory_order_relaxed);        while (!wait1.load(std::memory_order_relaxed));        while (!wait2.load(std::memory_order_relaxed));        asm volatile('' ::: 'memory');        if (check()) {            std::cout << 'test count ' << count << ': r0 == ' << r0 << ' && r1 == ' << r1 << std::endl;            break;        } else {            if (count % 10000 == 0) {                std::cout << 'test count ' << count << ': OK' << std::endl;            }        }    }    stop.store(true);    wait1.store(false);    wait2.store(false);    thread1.join();    thread2.join();    return 0;}

上面的程序可以很輕易就運(yùn)行出 r0 == 0 && r1 == 0 的結(jié)果，比如：

為了防止 CPU 亂序執(zhí)行，需要使用 CPU fence。我們可以將函數(shù) f1 和 f2 中的 compiler fence 修改為 CPU fence：

void f1() {    x = 1;    asm volatile('mfence': : :'memory');    r0 = y;}void f2() {    y = 1;    asm volatile('mfence': : :'memory');    r1 = x;}

如此，便不會(huì)出現(xiàn) r0 == 0 && r1 == 0 的情況了。

總結(jié)

指令亂序執(zhí)行主要由兩種因素導(dǎo)致：

1. 編譯期指令重排。
2. 運(yùn)行期 CPU 亂序執(zhí)行。

無論是編譯期的指令重排還是 CPU 的亂序執(zhí)行，主要都是為了讓 CPU 內(nèi)部的指令流水線可以“充滿”，提高指令執(zhí)行的并行度。

上面舉的插入 fence 的例子都是使用了 GCC 的擴(kuò)展語法，實(shí)際上 C++ 標(biāo)準(zhǔn)庫已經(jīng)提供了類似的封裝： std::atomic_thread_fence [4] ，跨平臺(tái)且可讀性更好。

一些無鎖編程、追求極致性能的場景可能會(huì)需要手動(dòng)在合適的地方插入合適 fence，這里涉及的細(xì)節(jié)太多，非常容易出錯(cuò)。原子變量操作根據(jù)不同的 memory order 會(huì)自動(dòng)插入合適的 fence，建議優(yōu)先考慮使用原子變量。

原文鏈接：
https://mp.weixin.qq.com/s?__biz=MzI0NjA1MTU5Ng==&mid=2247484193&idx=1&sn=
88968ef741f3d336276e23e577e21bf8&utm_source=tuicool&utm_medium=referral