程序同步經典示例 多執行緒上篇（五）
同步回顧
程序同步控制有多種方式： 演算法、硬體、訊號量、管程
這些方式可以認為就是 同步的工具（方法、函式）
比如訊號量機制中的wait(S) 和 signal(S) ，就相當於是兩個方法呼叫。
呼叫wait(S)就會申請這個資源，否則就會等待（進入等待佇列）；呼叫signal(S)就會釋放資源（或一併喚醒等待佇列中的某個）；
在梳理同步問題的解決思路時，只需要合理安排方法呼叫即可，底層的實現細節不需要關注。
接下來以這種套路，看一下藉助與不同的同步方式“演算法、硬體、訊號量、管程”這一“API”，如何解決經典的程序同步問題
生產者消費者
生產者-消費者(producer-consumer)問題是一個著名的程序同步問題。它描述的是：
有一 群生產者程序在生產產品，並將這些產品提供給消費者程序去消費。
為使生產者程序與消 費者程序能併發執行，在兩者之間設定了一個具有 n 個緩衝區的緩衝池，生產者程序將它 所生產的產品放入一個緩衝區中；消費者程序可從一個緩衝區中取走產品去消費。
儘管所 有的生產者程序和消費者程序都是以非同步方式執行的，但它們之間必須保持同步
也就是即不允 許消費者程序到一個空緩衝區去取產品，也不允許生產者程序向一個已裝滿產品且尚未被 取走的緩衝區中投放產品。
記錄型訊號量
對於緩衝池本身，可以藉助一個互斥訊號量mutex實現各個程序對緩衝池的互斥使用；
生產者關注於緩衝池空位子的個數，消費者關注的是緩衝池中被放置好產品的滿的個數
所以，我們總共設定 三個訊號量semaphore ：
mutex 值為 1 ，用於程序間互斥訪問緩衝池
full 表示緩衝區這一排坑中被放置產品的個數，初始時為 0
empty 表示緩衝區中空位子的個數，初始時為 n
對於緩衝池以一個數組的形式進行描述： buffer[n]
另外還需要定義兩個用於對陣列進行訪問的下標 in 和 out ，初始時都是0，也就是生產者會往0號位置放置元素，消費者會從0號開始取
每次的操作之後，下標後移，in和out採用自增的方式，所以應該是迴圈設定，比如in為10時，應該從頭再來，所以求餘（簡言之in out序號一直自增，通過求餘迴圈）
//變數定義
int in=0, out=0;
item buffer[n];
semaphore mutex=l，empty=n, full=0;
//生產者
void proceducer(){
do{
producer an item nextp;
......
wait(empty);//等待空位子
wait(mutex);//等待緩衝池可用
buffer[in] =nextp;//設定元素
in =(in+1)%n;//下標後移
signal(mutex);//釋放緩衝池
signal(full);//“滿”也就是已生產產品個數釋放1個(+1)
}while(TRUE);
//消費者
void consumer() {
do{
wait(full);//等待已生產資源個數
wait(mutex);//等待緩衝池可用
nextc= buffer[out];//獲得一個元素
out =(out+1) % n;//下標後移
signal(mutex);//釋放緩衝池
signal(empty);//空位子多出來一個
consumer the item in nextc;//消費掉獲得的產品
} while(TRUE);
}
//主程式
void main() {
proceducer();
consumer();
}
以上就是一個記錄型訊號量解決生產者消費者的問題的思路
對於訊號量中用於實現互斥的wait和signal必須是成對出現的，儘管他們可能位於不同的程式中，這都無所謂，他們使用訊號量作為紐帶進行聯絡
AND型訊號量
對於生產者和消費者，都涉及兩種資源，一個是緩衝池，一個是緩衝池空或滿
所以可以將上面兩種資源申請的步驟轉換為AND型，比如
wait(empty);//等待空位子
wait(mutex);//等待緩衝池可用
轉換為AND的形式的Swait(empty，mutex)
int in=0, out=0;
item buffer[n];
semaphore mutex=l, empty=n, full=O;
void proceducer() {
do{
producer an item nextp;
......
Swait(empty, mutex);
buffer[in] = nextp;
in =(in+1) % n;
Ssignal(mutex, full)
} while(TRUE);
}
void consumer() {
do{
Swait(full, mutex);
nextc= buffer[out];
out =(out+1) % n;
Ssignal(mutex, empty);
consumer the item in nextc;
......
} while(TRUE);
}
這個示例中，AND型訊號量方案只是記錄型訊號量機制的一個簡單升級
管程方案
管程由一組共享資料結構以及過程，還有條件變數組成。
共享的資料結構就是緩衝池，大小為n
生產者向緩衝池中放入產品，定義過程put(item)
消費者從緩衝池中取出產品，定義過程get(item)
對於生產者，非滿 not full 就可以繼續生產資料；
對於消費者，非空 not empty 就可以繼續消費資料；
所以設定兩個條件：notfull，notempty
如果資料個數 count>=N，那麼 notfull 非滿條件不成立
如果資料個數 count<=0，那麼notempty 非空條件不成立
也就是說：
count>=N，notfull 不滿足，生產者就會在 notfull 條件上等待
count<=0N，notempty 不滿足，消費者就會在 notempty 條件上等待
//定義一個管程
Monitor procducerconsumer {
item buffer[N];//緩衝區大小
int in, out;//訪問下標
condition notfull, notempty;//條件變數
int count;//已生產產品的個數
//生產方法
void put(item x) {
if(count>=N){
notfull.wait; //如果生產個數已經大於緩衝區大小，將生產程序新增到notfull條件的等待佇列中
}
buffer[in] = x; //設定元素
in = (in+1) % N; //下標移動
count++;//已生產產品個數+1
notempty.signal //釋放等待notempty條件的程序
}
//獲取方法
void get(item x) {
if(count<=0){
notempty.wait; // 如果已生產產品數量為0（以下），消費者程序新增到notempty的等待佇列中
}
x = buffer[out];// 讀取元素
out = (out+1) % N; // 下標移動
count--; //已生產產品個數-1
notfull.signal; // 釋放等待notfull條件的程序
}
//初始化資料方法
void init(){
in=0;out=0;count=0;
}
} PC;
生產者和消費者邏輯
void producer(){
item x;
while(TRUE){
produce an item in nextp;
PC.put(x);
}
}
void consumer( {
item x;
while(TRUE) {
PC.get(x);
consume the item in nextc;
......
}
}
void main(){
proceducer();
consumer();
}
管程的解決思路就是將同步的問題封裝在管程內部，管程會幫你解決所有的問題
哲學家進餐
由Dijkstra提出並解決的哲學家進餐問題(The Dinning Philosophers Problem)是典型的同 步問題。
該問題是描述有五個哲學家共用一張圓桌，分別坐在周圍的五張椅子上，在圓桌 上有五個碗和五隻筷子，他們的生活方式是交替地進行思考和進餐。
平時，一個哲學家進 行思考，飢餓時便試圖取用其左右最靠近他的筷子，只有在他拿到兩隻筷子時才能進餐。
進餐完畢，放下筷子繼續思考。
灰色大圓桌，黃色凳子，每個人左右各有一根筷子，小圓點表示碗。（儘管畫的像烏龜，但這真的是桌子 ￣□￣｜｜）
記錄型訊號量機制
放在桌子上的筷子是臨界資源，同一根筷子不可能被兩個人同時使用，所以每一根筷子都是一個共享資源
需要使用五個訊號量表示，五個訊號量每個表示一根筷子
當哲學家飢餓時，總是先去拿他左邊的筷子，即執行wait(chopstick[i])；
成功後，再去拿他右邊的筷子，即執行wait(chopstick[(i+1)mod 5])；又成功後便可進餐。（i+1)mod 5 是為了處理第五個人右邊的是第一個的問題 ）
進餐完畢，又先放下他左邊的筷子，然後再放右邊的筷子。
//定義五個訊號量
//為簡單起見，假定陣列起始下標為1
//訊號量全部初始化為1
semaphore chopstick[5]={1,1,1,1,1};
do{
//按照我們上面圖中所示，第 i號哲學家，左手邊為i號筷子，右手邊是 (i+1)%5
wait(chopstick[i]);//等待左手邊的，
wait(chopstick[(i+1)%5]);]);//等待右手邊的
// 進餐......
signal(chopstick[i]);//釋放左手邊的
signal(chopstick[(i+1)%5])//釋放右手邊的
// 思考......
} while(TRUE);
通過這種演算法可以保證相鄰的兩個哲學家之間不會出現問題，但是一旦五個人同時拿起左邊的筷子，都等待右邊的筷子，將會出現死鎖
有幾種解決思路
(1)至多隻允許有四位哲學家同時去拿左邊的筷子
可以保證肯定會空餘一根筷子，並且沒拿起筷子的這個人的左手邊的這一根，肯定是已經拿起左手邊筷子的某一個人的右手邊，所以肯定不會死鎖
(2) 僅當哲學家的左、右兩隻筷子均可用時，才允許他拿起筷子進餐。 也就是AND機制，將左右操作轉化為“原子”
(3) 規定奇數號哲學家先拿他左邊的筷子，然後再去拿右邊的筷子，而偶數號哲學家則相反。
如上圖所示，1搶1號筷子，2號和3號哲學家競爭3號筷子，4號和5號哲學家競爭5號筷子，所有人都是先競爭奇數，然後再去競爭偶數
這一條是為了所有的人都會先競爭奇數號筷子，那麼也就是最多三個人搶到了奇數號筷子，有兩個人第一步奇數號筷子都沒搶到的這一輪就相當於出局了
三個人，還有兩個偶數號筷子，必然會有一個人搶得到
AND型訊號量
哲學家進餐需要左手和右手的筷子，所以可以將左右手筷子的獲取操作原子化，藉助於AND型訊號量
//定義五個訊號量
//為簡單起見，假定陣列起始下標為1
//訊號量全部初始化為1
semaphore chopstick[5]={1,1,1,1,1};
do{
//按照我們上面圖中所示，第 i號哲學家，左手邊為i號筷子，右手邊是 (i+1)%5
Swait(chopstick[i],chopstick[(i+1)%5]))
// 進餐......
Ssignal(chopstick[i],chopstick[(i+1)%5]);
// 思考......
} while(TRUE);
讀者寫者問題
一個數據檔案或記錄，可被多個程序共享，我們把只要求讀該檔案的程序稱為“Reader程序” ，其他程序則稱為“Writer 程序” 。
允許多個程序同時讀一個共享物件，因為讀操作不會使資料檔案混亂。
但不允許一個Writer 程序和其他Reader 程序或 Writer 程序同時訪問共享物件，因為這種訪問將會引起混亂。
所謂“讀者—寫者問題(Reader-Writer Problem)”是指保證一個 Writer 程序必須與其他程序互斥地訪問共享物件的同步問題。
讀者—寫者問題常被用來測試新同步原語。
很顯然，只有多個讀者時不衝突
記錄型訊號量機制
讀和寫之間是互斥的，所以需要一個訊號量用於讀寫互斥Wmutex
另外如果有讀的程序存在，另外的程序如果想要讀的話，不需要同步也就是Wait(Wmutex)操作；
如果當前沒有程序在讀，那麼需要Wait(Wmutex)操作，所以設定一個變數記錄寫者個數Readcount，可以用來判斷是否需要同步
另外Readcount 會被多個讀者程序訪問，所以也是臨界資源，所以設定一個rmutex 用於互斥訪問Readcount
//兩個訊號量，一個用於讀者互斥 readcount ，一個用於讀寫互斥
semaphore rmutex=l,wmutex=1;
int readcount=0;//初始時讀者個數為0
//讀者
void reader() {
do{
wait(rmutex);//讀者先獲取 readcount
if(readcount==0){//如果一個讀者沒有，第一個讀者需要與寫者互斥訪問
wait(wmutex);
}
readcount++;//讀者個數+1
signal(rmutex);//讀者個數+1後，可以釋放readcount的鎖，其他讀者可以進來
//開始慢慢讀書......
wait(rmutex);//讀者結束時，需要獲取readcount的鎖
readcount--;//退出一個讀者
if (readcount==0) {//如果此時一個讀者都沒有了，還需要釋放與讀寫互斥的鎖
signal(wmutex);
}
signal(rmutex);//釋放readcount的鎖
}while(TRUE);
}
void writer(){
do{
wait(wmutex);//寫者必須獲得wmutex
//執行寫任務....
signal(wmutex);//寫任務結束後就可以釋放鎖
}while(TRUE);
}
//主程式
void main() {
reader();
writer();
}
寫者相對比較簡單，獲得鎖wmutex之後，進行寫操作，否則等待wmutex
讀者也是需要先獲得鎖，讀操作後釋放鎖，但是因為多個讀者之間互不影響，所以使用readcount記錄讀者個數，只有第一個讀者才需要競爭wmutex，只有最後一個讀者才需要釋放wmutex
readcount作為讀者之間的競爭資源，所以對readcount進行操作的時候也需要進行加鎖
訊號量集機制
將讀者寫者的問題複雜化一點， 它增加了一個限制，即最多隻允許 N個讀 者同時讀。
在上面的解決方法中，可以不使用rmutex控制對readcount的互斥，可以構造一個讀者個數的訊號量readcountmutex，初始值設定為N
每次新增一個讀者時，wait(readcountmutex)，一個讀者離開時signal(readcountmutex)
也可以使用訊號量集機制
int N;//最大的讀者個數，也就是相當於圖書館的空位子，初始時空位子為N
semaphore L=N, mx=1;//定義兩個訊號量資源L和mx，分別用於控制讀者個數限制和讀寫（寫寫)
void reader() {
do{
Swait(L, 1, 1);//獲取空位子L，每次獲取1個，>=1時可分配
Swait(mx, 1, 0);//獲取與寫的互斥量mx，每次獲取0個，>=1時可分配，如果mx為1，也就是沒有寫者，讀者都可以進來，否則一個都進不來
//進行一些讀操作
Ssignal(L, 1);//釋放一個單位的資源L
}while(TRUE);
}
void writer() {
do{
Swait(mx,1,1; L,N,0);//獲得資源mx，每次獲取1個，>=1時分配，獲得資源L，每次獲得0個，>=N時即可分配
//進行一些寫操作
Ssignal(mx, 1);//釋放資源mx
}while(TRUE);
}
void main(){
reader();
writer();
}
Swait(L, 1, 1);用於獲取讀者空位子沒什麼好說的
Swait(mx, 1, 0);作為開關，只要mx滿足條件>=1，那麼就可以無限制的進入（此例中有L的限制），一旦條件不滿足，則全都不能進入，滿足多讀者，有寫不能讀的情況
對於寫者中的Swait(mx,1,1; L,N,0);
他會獲取mx，>=1時，獲取一個資源，並且當L>=N時，分配0個L資源，也就是說一個讀者都沒有的時候才行
Swait(mx, 1, 0); 與Swait( L,N,0);都是需求0個，相當於開關判斷
總結
以上為藉助“程序同步的API”，訊號量，管程等方式完成程序同步的經典示例，例子來源於《計算機作業系統》
說白了，就是用 wait(S) Swait(S) signal(S) Ssignal(S)等這些“方法”描述程序同步演算法
可能會覺得這些內容亂七八糟的，根本沒辦法使用，的確這些內容全都沒辦法直接轉變為程式碼寫到你的專案中
但是，這些都是解決問題的思路
不管是訊號量還是管程還是什麼，不會需要你從頭開始實現一個訊號量，然後.......也不需要你從頭開始實現一個管程，然後......
不管是作業系統層面，還是程式語言層面，還是具體的API，萬變不離其宗
儘管這些wait和signal的確不存在，但是，但是，但是程式語言中很可能已經提供了語意相同的方法供你呼叫了
也就是說，你只需要理解同步的思路即可，儘管沒有我們此處說的wait（S）,但是肯定有對應物。
原文地址: 程序同步經典示例 多執行緒上篇（五）