[轉錄] 簡單而有趣的雙執行緒同步問題

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

#include
#include

#include
#include
#include
#include

#include
#include 

#define INC_TO 1000000 // one million...

int global_int = 0;

pid_t gettid( void )
{
    return syscall( __NR_gettid );
}

void *thread_routine( void *arg )
{
    int i;
    int proc_num = (int)(long)arg;
    cpu_set_t set;

    CPU_ZERO( &set );
    CPU_SET( proc_num, &set );

    sched_setaffinity( gettid(), sizeof( cpu_set_t ), &set )

    for (i = 0; i < INC_TO; i++)
        global_int++;

    return NULL;
}

int main()
{
    int procs = 0;
    int i;
    pthread_t *thrs;

    // Getting number of CPUs
    procs = (int)sysconf( _SC_NPROCESSORS_ONLN );

    thrs = malloc( sizeof( pthread_t ) * procs );

    printf( "Starting %d threads...\n", procs );

    for (i = 0; i < procs; i++)
        pthread_create( &thrs[i], NULL, thread_routine, (void *)(long)i ))

    for (i = 0; i < procs; i++)
        pthread_join( thrs[i], NULL );

    free( thrs );

    printf( "After doing all the math, global_int value is: %d\n", global_int );
    printf( "Expected value is: %d\n", INC_TO * procs );

    return 0;
}

程式跟 Makefile 可以在作者提供的載點下載。
看一下就可以知道這程式只是簡單的產生兩個執行緒（測試環境為雙核心），分別對 global_int 對遞增動作，而且迴圈的條件是不相依的，也就是說，我們直覺上會認為：
Thread 1: 遞增 global_int 一百萬次，然後結束回到 Master thread。
Thread 2: 也是遞增 global_int 一百萬次，然後結束回到 Master thread。
Master thread：等到兩個執行緒都回來，理論上期望得到 global_int = 2000000。
但是，只要大家用原作者的 Makefile 編譯完並執行看看這程式，可以很明顯的發現，得到的數值一定是小於兩百萬。這是為什麼呢？這個概念就是所謂的 Data race，也就是這兩個執行緒同時存取的同一塊共享記憶體，而且其中一個操作是寫入動作。
讓我們只看單一一次的遞增動作，並且把 global_int++ 表示成 global_int = global_int + 1;
Thread 1 Thread 2
——————————
T1: load global_int load global_int
T2: inc global_int inc global_int
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 。
首先增加一個全域變數：

 thread_spinlock_t spinlock;

以及一個區域變數：

 int pshared;

然後在 pthread_create 之前加入

 pthread_spin_init(&spinlock, pshared);

最後把遞增的部份改寫：

    pthread_spin_lock(&spinlock);
    for (i = 0; i < INC_TO; i++)
        global_int++;
    pthread_spin_unlock(&spinlock);

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

使用 Atomic Operation

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

    for (i = 0; i < INC_TO; i++)
        __sync_fetch_and_add( &global_int, 1 );
        //global_int++;

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

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

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