Semaphores

帶著問題學習：如何使用semaphores？

1. Semaphores: A Definition

semaphore是一個具有整數值的物件，可用使用兩個例程來對其進行操作，
POSIX中兩個例程為sem_wait()和sem_post()，
在使用之前必須初始化，如下所示：
在這里插入圖片描述
該例程sem_init()的第三個引數表示初始化值為1，第二個引數0表示在一個行程中執行緒可共享semaphore，

注：當semaphore的值為負數時，其值表示的為處于等待狀態的執行緒的數量，

2. Binary Semaphores(Locks)

使用一個semaphore作為鎖，如下所示：
在這里插入圖片描述
注：上圖中X應該為1，

假設有兩個執行緒0和1：
第一種情況：執行緒0一直運行到結束
在這里插入圖片描述
第二種情況：執行緒0持有鎖呼叫了sem_wait()但還沒有呼叫sem_post()，執行緒1嘗試呼叫進入critical section，

3. Semaphores For Ordering

使用semaphore作為ordering primitive，如下所示：
在這里插入圖片描述
注：上圖中X應該為0（上圖有兩種情況要考慮），

4. The Producer/Consumer (Bounded Buffer) Problem

要回到上次談及的Producer/Consumer問題，

4.1 First Attempt

在這里插入圖片描述

上述代碼MAX = 1時不管是單執行緒還是多執行緒都能正常運行；但是如果MAX > 1，就出現了問題：當有多個producer和多個consumer時，兩個producer分別為P_a和P_b同時呼叫put()（F1），當P_a準備進入F2階段時被打斷（資料被放入緩沖區的第0號元素），這意味著第0號元素的舊資料被覆寫，

4.2 A Solution: Adding Mutual Exclusion

上述問題解決方法就是添加互斥鎖（mutual exclusion），因為其為關鍵部分（critical section），
在這里插入圖片描述
上述代碼會發生死鎖（deadlock）， WHY？

4.3 Avoiding Deadlock

產生死鎖原因：假設有一個producer和一個consumer，consumer首先持有鎖（line C0），然后呼叫sem_wait()（line C1），由于沒有資料，此呼叫導致consumer被阻塞而讓出CPU（但是consumer仍然持有鎖）；然后producer開始運行，它首先要做的就是持有鎖（line P0），由于鎖被consumer持有，producer不得不進入等待狀態，一直如此下去，產生死鎖，

4.4 At Last, A Working Solution

為了解決上述問題，我們必須減小鎖的范圍，如下所示：
在這里插入圖片描述

5. Reader-Writer Locks

不同的資料結構可能需要不同的鎖，
對于一個list的查找和插入，只要保證在查找時插入操作不會進行，那么就可以允許許多查找同時運行，支持這種特殊操作的特殊型別的鎖就叫做reader-writer lock，
在這里插入圖片描述

這種鎖實作了reader和writer不能同時作業（例如：一旦一個reader獲取了鎖，那么其他reader也可以獲取鎖，但是writer不能獲取鎖），這就可能造成starvation（不公平，我們要反抗！），

6. The Dining Philosophers

Dijkstra提出并解決的最著名的并發問題之一就是The Dining Philosophers，如下所示：
5個哲學家圍著桌子坐，每兩個哲學家之間有一個叉子，每個哲學家都有自己的思考時間，不需要任何叉子、吃飯，為了吃飯，哲學家需要兩個叉子（左邊和右邊），

在這里插入圖片描述
如下是每個哲學家的回圈操作：

while (1)
{
	think();
	get_forks(p);
	eat();
	put_forks(p);
}

對于每個哲學家，都能進行左右兩邊操作：

int left(int p) { return p; }
int right(int p) { return (p + 1) 5 5； }

當然，我們也需要semaphore幫助這些哲學家解決問題，假設每個哲學家都有一個semaphore：

sem_t forks[5]

6.1 Broken Solution

假設每個哲學家的semaphore都初始化為1，且每個哲學家都知道它自己的序號，如下所示：
在這里插入圖片描述
上述代碼存在問題：死鎖（deadlock），如果每個哲學家都只拿左（右）邊的叉子，每個哲學家最終都會有一個叉子而進入一直等待狀態，

6.2 A Solution: Breaking The Dependency

解決上述問題最簡單的方法就是改變至少一位哲學家獲取叉子的方式，
不妨假設序號4的哲學家（序號從0開始）獲取叉子的方式與其他哲學家不同，如下所示：
在這里插入圖片描述
還有其他著名的問題如：cigarette smoker’s problem、sleeping barber problem等，都是關于并發的，