in Programming ~ read.

簡單而有趣的雙執行緒同步問題

今天看到一系列有趣的文章:1, 2, 3

主要是這樣的,作者聽到有人說像是 int, float 這些基本的形態都是 atomic ,也就是說只要是 int 的變數就不能能同時有兩個以上的執行入對他做寫入/讀取動作(至少一個操作是寫入)。所以作者寫了以下的程式來驗證這個說法:(篇幅關係,我刪減了一些程式中錯誤檢查部分)

include #include #include #include #include #include #include #include #define INCTO 1000000 // one million... int globalint = 0; pidt gettid( void ) { return syscall( _NRgettid ); } void *threadroutine( void *arg ) { int i; int procnum = (int)(long)arg; cpusett set; CPUZERO( &set ); CPUSET( procnum, &set ); schedsetaffinity( gettid(), sizeof( cpusett ), &set ) for (i = 0; i < INCTO; i++) globalint++; return NULL; } int main() { int procs = 0; int i; pthreadt *thrs; // Getting number of CPUs procs = (int)sysconf( SCNPROCESSORSONLN ); thrs = malloc( sizeof( pthreadt ) * procs ); printf( "Starting %d threads...\n", procs ); for (i = 0; i < procs; i++) pthreadcreate( &thrs[i], NULL, threadroutine, (void *)(long)i )) for (i = 0; i < procs; i++) pthreadjoin( thrs[i], NULL ); free( thrs ); printf( "After doing all the math, globalint value is: %d\n", globalint ); printf( "Expected value is: %d\n", INCTO * procs ); return 0; }

程式跟 Makefile 可以在作者提供的載點下載。

看一下就可以知道這程式只是簡單的產生兩個執行緒(測試環境為雙核心),分別對 globalint 對遞增動作,而且迴圈的條件是不相依的,也就是說,我們直覺上會認為:
Thread 1: 遞增 global
int 一百萬次,然後結束回到 Master thread。
Thread 2: 也是遞增 globalint 一百萬次,然後結束回到 Master thread。
Master thread:等到兩個執行緒都回來,理論上期望得到 global
int = 2000000。

但是,只要大家用原作者的 Makefile 編譯完並執行看看這程式,可以很明顯的發現,得到的數值一定是小於兩百萬。這是為什麼呢?這個概念就是所謂的 Data race,也就是這兩個執行緒同時存取的同一塊共享記憶體,而且其中一個操作是寫入動作。

讓我們只看單一一次的遞增動作,並且把 globalint++ 表示成 globalint = globalint + 1;
Thread 1 Thread 2
——————————
T1: load global
int load globalint
T2: inc global
int inc globalint
T3: store global
int store global_int

由上到下同時執行一模一樣的動作(當然,這只是其中一種可能),我們可以發現光是這樣原本預期會是 2 的值就減少為 1 了,所以最後得不到完整的兩百萬也不奇怪了!

使用 Spinlock

當然,我們得為這樣的情況想些解決辦法,大家比較熟知的就是透過 Lock 機制中的 mutex(binary semaphore),使用 mutex 當然比使用 semaphore 快多了,而且在 Linux 中, POSIX mutex 是透過 FUTEX(Fast-Usermode-muTEX) 實作的,也就是說在替 unlocked futex 上鎖的時候,不使用系統呼叫;不過在等待 locked futex 就沒辦法了,畢竟行程的等待只能透過系統呼叫,不過即使是這樣,還是比一般情況要快了。

但是除此之外的情況,還是跟 semaphore 差不多慢,這也就是 spinlock 存在的目的,spinlock 的原理雖然跟 mutex 大致相同,但是唯一一點不同的它不用等待 locked spinlock ,也就是說它不必透過很慢的系統呼叫去等待,而是在不斷的在原地執行,也就是透過 while loop 做 busy waiting,雖然整體來說時間會變短,可是要特別注意這種方式會花費掉許多 CPU 時間,所以當使用這種方式的時候,不要訝異你的 CPU 使用率突然飆高。

要減少這副作用很簡單,spinlock 鎖住的程式碼區塊(critical section)千萬不可以執行太久,該區塊如果執行時間越短,就越適合使用 spinlock。讓我們看一下如何在上面的程式加入 spinlock 。

首先增加一個全域變數:

threadspinlockt spinlock;

以及一個區域變數:

int pshared;

然後在 pthread_create 之前加入

pthreadspininit(&spinlock, pshared);

最後把遞增的部份改寫:

pthreadspinlock(&spinlock); for (i = 0; i < INCTO; i++) globalint++; pthreadspinunlock(&spinlock);

就完成了,切記千萬不可以把 lock & unlock 放入迴圈之中,否則很有可能會在來不及上鎖之前就先偷跑,導致最後的數值會有點小誤差。

使用 Atomic Operation

除了上面的作法之外呢,我們還可以透過 gcc builtins 來解決這問題。
我們只要簡單的把原來遞增那行註解掉,並且改成 Atomic Operation 就完成了!

for (i = 0; i < INCTO; i++) _syncfetchandadd( &globalint, 1 ); //global_int++;

至於這個動作是在做什麼呢?其實意思大概是這樣的:

int _syncfetchandadd(int *ptr, int value) { tmp = *ptr; *ptr += 1; return tmp; }

可以發現我們其實沒有用到它回傳的數值,所以其實使用 _syncandandfetch 或是 _syncfetchandadd 都不會影響結果,單純只是用它 Atomic 的特性。

comments powered by Disqus