mutex一般用于為一段代碼加鎖，以保證這段代碼的原子性（atomic）操作，即：要么不執(zhí)行這段代碼，要么將這段代碼全部執(zhí)行完畢。

例如，最簡(jiǎn)單的并發(fā)沖突問題就是一個(gè)變量自增1：

balance = balance + 1;

表面看這是一條語(yǔ)句，可是在背后的匯編中我們可以看到，指令集操作過程中會(huì)引入中間變量來(lái)保存右邊的值，進(jìn)而這個(gè)操作至少會(huì)被擴(kuò)充為：

int tmp = balance + 1;
balance = tmp;

這就需要一把互斥鎖（mutual exclusive, mutex）將這段代碼給鎖住，使其達(dá)到任何一個(gè)線程“要么全部執(zhí)行上述代碼，要么不執(zhí)行這段代碼”的效果。這個(gè)用法可以表示為：

lock_t mutex;
...
lock(&mutex)
    balance = balance + 1;
unlock(&mutex);

那么，一個(gè)自然的問題便是，我如何實(shí)現(xiàn)上面的這個(gè)lock()函數(shù)呢？

乍一看這個(gè)問題是非常復(fù)雜的，特別是考慮到它能夠被適用于各種代碼的各種情況。但經(jīng)過各種簡(jiǎn)化，這個(gè)lock()實(shí)現(xiàn)，可以通過幾個(gè)test和set的組合得以實(shí)現(xiàn)。

例如，

typedef struct __lock_t { int flag; } lock_t;

void init(lock_t *mutex) {
    // 0: lock is available
    // 1: lock is held
    mutex->flag = 0;
}

void lock(lock_t *mutex) {
    while (mutex->flag == 1) {  // Test the flag.
        ;    // Wait the lock
    mutex->flag = 1;  // Set the lock, i.e. start to hold lock
}

void unlock(lock_t *mutex) {
    mutex->flag = 0;
}

我第一次看到這個(gè)算法的時(shí)候非常驚訝，一個(gè)本來(lái)極其復(fù)雜的問題就這么優(yōu)雅地被解決了。它僅僅涉及到對(duì)條件的檢驗(yàn)和變量的復(fù)制，然后整個(gè)問題就這么輕而易舉地被攻破了。

當(dāng)然，我并沒能看到上述代碼的“坑”，也即是必須依靠指令集級(jí)別的支持才能真正做到atomic。這同樣說(shuō)明了并發(fā)程序的困難，稍微不注意便會(huì)調(diào)入一個(gè)萬(wàn)劫不復(fù)的坑里，并且你還不知道哪里出錯(cuò)了。

上述極端優(yōu)雅的代碼，有一個(gè)隱藏的坑，那便是在lock()函數(shù)的實(shí)現(xiàn)里，while循環(huán)那一段其實(shí)是可以被亂入的。

假設(shè)thread A是第一個(gè)運(yùn)行到此的線程，那么它得到的mutex->flag就肯定是0，于是它繼續(xù)跳出循環(huán)往下運(yùn)行，希望通過下面的mutex->flag = 1來(lái)持有鎖，使得其它線程在檢測(cè)while循環(huán)時(shí)為真，進(jìn)而進(jìn)入循環(huán)的等待狀態(tài)。

可如果在A執(zhí)行到這個(gè)賦值為1的語(yǔ)句之前，又有另外一個(gè)thread B運(yùn)行到了這個(gè)while循環(huán)部分，由于mutex->flag還未被賦值為1，B同樣可以跳出while，從而跟A一樣拿到這把鎖！這就出現(xiàn)了沖突。

那怎么辦呢？仔細(xì)后可以發(fā)現(xiàn)，其實(shí)關(guān)鍵問題就在于：

• 對(duì)mutex->flag的檢測(cè)
• 對(duì)mutex->flag的賦值

這兩個(gè)操作必須是不被干擾的，也就是它必須是atomic的，要么這兩段代碼不被執(zhí)行，要么這兩段代碼被不中斷地完整執(zhí)行。

這就需要借助CPU指令集的幫助，來(lái)保證上述兩條語(yǔ)句的atomic操作，也即是著名的TestAndSet()操作。

int TestAndSet(int *ptr, int new) {
    int old = *ptr;
    *ptr = new;
    return old;
}

CPU的指令集，并不需要支持繁復(fù)的各種atomic操作。僅僅支持上面這個(gè)函數(shù)，各種互斥加鎖的情形，便都能夠被涵蓋。

此時(shí)，在回到我們最開始的那個(gè)優(yōu)雅的lock()實(shí)現(xiàn)，就可以將其改造為：

typedef struct __lock_t { int flag; } lock_t;

void init(lock_t *lock) {
    // 0: lock is available
    // 1: lock is held
    mutex->flag = 0;
}

void lock(lock_t *mutex) {
    while (TestAndSet(&lock_t->flag, 1) == 1) {
        ;
}

void unlock(lock_t *lock) {
    lock->flag = 0;
}

上述代碼極其精巧。乍一看在lock()實(shí)現(xiàn)里不是還缺少一行mutex->flag = 1;么？可其實(shí)呢，它已經(jīng)被整合到了TestAndSet()函數(shù)中。

這樣的支持TestAndSet()的實(shí)現(xiàn)，便是最簡(jiǎn)單的spin lock，彈簧鎖。之所以叫彈簧鎖，那是因?yàn)樵诟黝愭i當(dāng)中，彈簧鎖就是最初的被投入工業(yè)使用的最簡(jiǎn)單的實(shí)現(xiàn)技術(shù)。