鎖

并發編程的一個最基本問題就是原子性地執行一系列指令。鎖有助于直接解決這一問題。

鎖的基本思想

鎖就是一個變量。這個變量保存了鎖在某一時刻的狀態。它要么是可用的，表示沒有線程持有鎖，要么是被占用的，表示有線程持有鎖，正處于臨界區（訪問共享資源的那部分代碼）。

Pthread鎖

POSIX庫將鎖稱為互斥量（mutex），因為它被用來提供線程之間的互斥。當一個線程在臨界區，它能阻止其它線程進入到本地線程直到本線程離開臨界區。

設計鎖

一個鎖應當能保證不會有第二個線程進入臨界區。另外，還應當保證公平性，所有的線程都有機會公平搶到鎖。在設計鎖時還應該考慮到搶鎖和釋放鎖的開銷。

為了實現上面兩點，我們需要使用硬件和操作系統的支持。

控制中斷

在臨界區關閉中斷。這個方案是為單處理系統開發的。

原子交換（測試并設置）

控制中斷無在多處理器上工作，系統設計者開始讓硬件支持鎖。最簡單的硬件支持就是測試并設置指令（test-and-set instruction），也叫做原子交換。

typedef struct lock_t { int flag; } lock_t;void init(lock_t* mutex)
{mutex->flag = 0;
}void lock(lock_t* mutex)
{while (mutex->flag == 1) //測試; //鎖被其它線程占用，該線程陷入自旋mutex->flag = 1; //設置
}void unlock(lock_t* mutex)
{mutex->flag = 0;
}

這種設置也是有問題的，首先它不能完成讓線程互斥的基本任務。考慮這種情況，當線程1在測試鎖時（只是通過了測試并未設置），發生了中斷切換的線程2，隨后線程2執行了完整的測試和設置，此時再次發生中斷切換到線程1。由于先前線程1已經通過了測試語句，接下來會執行設置代碼。這樣一來，就有兩個線程同時持有鎖了。

在性能上，如果一個線程在等待已經被持有的鎖時，會一直自旋，不停地檢查鎖。這會浪費許多CPU時間。

實現這種鎖，需要一條硬件指令支持。在x86上是xchg指令（原子交換）。下面的代碼片段說明了該指令的工作方式：

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

這些代碼都是原子地執行。利用這類原子交換指令可以實現自旋鎖。

typedef struct lock_t
{int flag;
} lock_t;void init(lock_t* lock)
{lock->flag = 0;
}void lock(lock_t* lock)
{while (TestAndSet(lock, 1) == 1);//自旋
}void unlock(lock_t* lock)
{lock->flag = 0;
}

比較并交換

另一個硬件支持是比較并交換指令。

int CompareAndSwap(int *ptr, int expected, int new)
{int actual = *ptr;if (actual == expected)*ptr = new;return actual;
}

鏈接的加載和條件式存儲指令

int LoadLinked(int* ptr)
{return *ptr;
}int StoreConditional(int* ptr, int value)
{if (no one has updated *ptr since the LoadLinked to this address){*ptr = value;return 1;}else{return 0;}
}

獲取并增加

int FetchAndAdd(int *ptr)
{int old = *ptr;*ptr = old + 1;return old;
}typedef struct lock_t
{int ticket;int turn;
} lock_t;void lock_init(lock_t *lock)
{lock->ticket = 0;lock->turn = 0;
}void lock(lock_t* lock)
{int myturn = FetchAndAdd(&lock->ticket);while (lock->turn != myturn); //spin
}void unlock(lock_t* lock)
{FetchAndAdd(&lock->turn);
}

解決自旋時的浪費

在自旋的時候，線程應該放棄CPU，從運行狀態變為就緒狀態。而且我們應該控制釋放鎖時誰可以搶到鎖，這是為了避免性能上的浪費以及餓死的問題。

為此，我們需要操作系統維護一個隊列保存正在等待鎖的線程隊列。這樣我們就可以在鎖被占用時休眠線程，在鎖可用時從隊頭中喚醒一個線程。