多線程(1): 亂序和屏障

來自專欄 C語言黑魔法

前言

終於計劃在這個已經荒廢了一年多的專欄里寫一點東西了. 這一次我把專欄的名字改成了"黑魔法", 接下來我準備在這裡分享一些有意思但是並不基礎的內容, 算是對自己從寫代碼過程中學到的東西的一些記錄. 很多寫在這裡的東西, 有可能都是我的個人看法, 如果大家有什麼想法歡迎探討.

這一個系列我準備記錄一下我在過去的一兩年時間內遇到的有意思的有關多線程有意思的話題. 再次強調一下, 這裡不是多線程基礎教程, 我會假設大家都知道線程的基本概念, 鎖的基本概念等等. 這個系列會用到很多原子操作的函數, 雖然C11引入了stdatomic.h, 但是在這裡我會使用gcc的內建原子操作 __sync_xxxxxx()

最後希望大家在實際的開發過程中不要過分地依賴黑魔法...

一個送分題

首先我們來看下面兩段代碼 (假設x,y,r1,r2是int型的全局變數)

volatile int x = 0,y = 0,r1,r2;void t1(){ x = 1; r1 = y;}void t2(){ y = 1; r2 = x;}

假設有兩個線程分別同時執行t1和t2, 會有什麼效果呢? 可能你會回答, 因為這裡沒有加鎖, 所以任何事情都可能發生, 但是事實上r1和r2不是1就是0. 讓我們來分析一下這段代碼可能會出現的情況.

• 如果t1執行到r1 = y 時 t2 還沒有執行 y = 1, 那麼 r1 = 0, r2 = 1
• 如果t2執行到r2 = y 時 t1 還沒有執行 x = 1, 那麼 r1 = 1, r2 = 0
• 如果t1和t2同時到了r1 = x 和 r2 = y, 那麼r1 = 1, r2 = 1

r1 = 0, r2 = 0 是不會發生的, 因為一旦r1 = 0 表明在t1讀取y的時候t2還沒有完成第一個賦值, 所以在t2 讀取 x 的時候 x 一定是1. 反之對於r2 = 0 那麼一定有 r1 = 1.

看,這個結果並不是很難理解, 接下來讓我們實際實驗一下.

實驗

為了能夠完成實驗, 我們必須保證"兩個函數同時執行". 然而這段程序都相當的小, 所以即使啟動兩個線程也無法真正實現"同時執行" 的效果. 所以我們使用了下面這段代碼作為線程執行的代碼.

volatile int chance, complete;typedef struct { int mask; volatile int *x, *y, *r;} param_t;void* thread_main(void* ar){ param_t* p = (param_t*)ar; volatile int* x = p->x; volatile int* y = p->y; int r, mask = p->mask; for(;;) { //第一部分: 等待主線程允許這個線程繼續執行的信號 int obs; do { obs = chance; } while((obs & mask) == 0 || !__sync_bool_compare_and_swap(&chance, obs, obs ^ mask)); //第二部分: 我們實際的實驗 *x = 1; r = *y; //第三部分: 寫回全局變數, 然後更新完成計數器 *p->r = r; do { obs = complete; } while(!__sync_bool_compare_and_swap(&complete, obs, obs + 1)); } return NULL;}

變數chance就是一個"信號燈", chance = 0的時候兩個線程就處於等紅燈的狀態.

一旦主線程吧chance改成了3, 兩個線就同時執行我們期望的代碼.

最後主線程等待complete計數器編程2, 主線程就可以檢查r1和r2的值了.

通過這種方式,我們能夠大致同時讓第二部分代碼同時執行.

再來看主線程, 我們希望能夠重複多次這個實驗,所以我們把代碼寫在一個循環里:

for(i = 0; i < 10000000; i ++) { x = y = 0; r1 = r2 = 0; // 信號燈編程綠燈 while(!__sync_bool_compare_and_swap(&chance, 0, 0x3)); // 等待兩個線程完成 while(complete != 2); // 檢查r1 和 r2的數值 complete = 0; count[r1 * 2 + r2] ++; } for(i = 0; i < 4; i ++) printf("r1 = %d r2 = %d count = %d
", i / 2, i % 2, count[i]);

有了這段代碼, 我們終於可以真正地驗證我們之前分析的結果了: r1 = r2 = 0是不可能發生的.

$ gcc ts.c -pthread -O0 -g $ ./a.outr1 = 0 r2 = 0 count = 1264938 ;<= 這是什麼鬼??r1 = 0 r2 = 1 count = 3689635r1 = 1 r2 = 0 count = 5043147r1 = 1 r2 = 1 count = 2280

結果出乎意料, r1 = 0 r2 = 0 居然會發生,而且概率並不低...為什麼會發生這種情況? (GCC O0 應該是可以保證操作的順序的)

亂序執行

事實上, 前面的實驗證明了X86 CPU在亂序執行我們的指令. 什麼意思 ? 雖然我們給CPU的程序是

*x = 1;r = *y;

但是CPU在某些情況下會交換兩條指令的順序.

如果這是一個單線程程序, 交換兩個語句的順序(時序改變)將沒有任何不同, 然而對於多線程程序, 很可能其他的線程正在另外一個core上悄悄地觀察指令執行的順序, 這從根本上導致了為什麼我們會看到r1 = 0, r2 = 0的結果.

內存模型

幾乎所有的現代處理器架構都允許CPU對程序的指令進行重排, 但是對重排的方式都有一定的限制.

(表格來自 Memory ordering - Wikipedia)

我們可以看到x86和x64僅僅允許 Load 指令提前到 Store 指令前面 (就是我們之前看到的情況)

如果我們把我們的線程內同時執行的代碼改成

r = *y;*x = 1;

那麼我們最開始的推測方法就是正確的了, r1 = 1 r2 = 1的情況並不會發生.

r1 = 0 r2 = 0 count = 1093819r1 = 0 r2 = 1 count = 2071502r1 = 1 r2 = 0 count = 6834679r1 = 1 r2 = 1 count = 0

根據那個內存順序的圖,我們知道對於ARM CPU, r1 = 1 r2 = 1的情況仍然有可能發生.

(沒有用手機做實驗....所以就不放結果了)

內存屏障

我們已經知道了造成這種詭異現象的原因, 那麼問題就是在一些應用中,某些內存存取的操作的時序是重要的 (比如說無鎖數據結構), 那麼有沒有辦法能夠阻止CPU打亂指令的順序, 保證操作的時序呢 ?

為了達到這個效果, X86中內存屏障指令 mfence, 這條指令正如它的名字, 是一個阻止CPU重拍指令的時候跨越這個屏障. 在GCC里, 我們可以使用 __sync_synchrnoize() 來產生一個mfence指令.

於是我們把線程同時執行的代碼改成

*x = 1;__sync_synchronize();r = y;

我們就可以得到我們預測的結果了.

$ gcc ts.c -pthread -O0 -g $ ./a.out r1 = 0 r2 = 0 count = 0 //這種情況不會發生了r1 = 0 r2 = 1 count = 1096801r1 = 1 r2 = 0 count = 8735302r1 = 1 r2 = 1 count = 167897

編譯時屏障

我們之前的例子都沒有開編譯器優化, 事實上, 不僅CPU可以重排操作, 編譯器在優化代碼的時候也會重排代碼. 這就需要另一種屏障, 告訴編譯器,不要跨越屏障重排指令, 在GCC和Clang中寫成

asm volatile ("" ::: "memory");

例如下面這段代碼

char arr[4];int x;int foo(){ arr[0] = 1; arr[1] = 2; x = 3; arr[2] = 3; arr[3] = 4; return *(int*)arr;}

使用GCC O3編譯

foo:.LFB0: .cfi_startproc movb $1, arr(%rip) #, arr movb $2, arr+1(%rip) #, arr movb $3, arr+2(%rip) #, arr movb $4, arr+3(%rip) #, arr movl $3, x(%rip) #, x // x = 3 被重排到了arr[2] = 3的後面 movl arr(%rip), %eax # MEM[(int *)&arr], ret

現在讓我們加入編譯器屏障

int foo(){ arr[0] = 1; arr[1] = 2; x = 3; sm volatile ("" ::: "memory"); arr[2] = 3; arr[3] = 4; return *(int*)arr;}

O3的之後生成的代碼

foo:.LFB0: .cfi_startproc movb $1, arr(%rip) #, arr movb $2, arr+1(%rip) #, arr movl $3, x(%rip) #, x //保留了原有的複製順序 movb $3, arr+2(%rip) #, arr movb $4, arr+3(%rip) #, arr movl arr(%rip), %eax # MEM[(int *)&arr], ret .cfi_endproc

於是,為了保證操作的順序, 在運行時我們需要內存屏障指令, 在編譯時我們需要編譯器屏障.

加鎖是最簡單最可靠的保證多線程程序正確性的方法, 如果大家不是為了壓榨性能, 請忽略各種屏障的黑魔法. 接下我計劃繼續介紹一些無鎖數據結構和高性能多線程程序的技巧

完整的實驗代碼在這裡: