目錄
讀寫者問題
問題描述
問題分析
進程互斥問題三部曲
讀者寫者算法實現
一、找進程——確定進程關系
二、找主營業務
三、找同步約束
a.互斥
b.資源?
c.配額?
理發店問題?
問題描述
問題分析
進程互斥問題三部曲
理發店問題算法實現
一、找進程——確定進程關系
?二、找主營業務
?三、找同步約束
a.資源
b.互斥?
c.配額?
總結
讀寫者問題
問題描述
有一個許多進程共享的數據區。有一些只讀取這個數據區的進程（Reader）和一些只往數據區寫數據的進程(Writer)。現在要寫一個程序，保證這些進程的運行是安全的。
問題分析
分析問題可以發現以下這些要點：
1、讀者進程彼此可以同時訪問共享數據區
2、讀者和寫者進程不可以同時訪問共享數據區
3、寫者進程彼此不可以同時訪問共享數據區
進程互斥問題三部曲
任何進程互斥（PV問題）都可以按照以下三步思考（來源：山東大學高曉程老師）
一、找進程——確定進程關系
二、找主營業務——拋開互斥，確定每個進程的主要任務
三、找同步約束
- 互斥
- 資源（計數信號量、空閑空間信號量等）
- 限額
讀者寫者算法實現
接下來，我們按照上面三部曲的思路來實現這個PV經典算法
一、找進程——確定進程關系
進程有兩類：1、讀者進程；2、寫者進程
進程關系如下：
1、讀者寫者是互斥的
2、寫者之間是互斥的
3、讀者之間不是互斥的
二、找主營業務
讀者進程的主營業務就是：讀取reading
寫者進程的主營業務就是：寫入writing
（此時不考慮任何同步約束~~）
代碼如下：
//寫者進程
writer(){while(1){writing;}
}//讀者進程
reader(){while(1){reading;}
}三、找同步約束
a.互斥
互斥約束：1、找到臨界區；2、互斥變量緊貼臨界區
在上面程序的基礎上增加互斥約束，如下：
//寫者進程
writer(){while(1){wait(rwmutex);writing;signal(rwmutex);}
}//讀者進程
reader(){while(1){wait(mutex);if(count==0){wait(rwmutex);}count++;signal(mutex);reading;wait(mutex);count--;if(count==0)signal(rwmutex);signal(mutex);}
}關鍵點：
1、讀者可以一起讀取文件，但是讀者和寫者不能一起訪問資源區。這表明如果沒有讀者訪問，此時有一個讀者想要訪問資源區，他需要和寫者競爭這個資源。一旦這個讀者開始讀取后，其他讀者可以直接讀取，不需要互斥訪問。———需要一個讀者和寫者之間的互斥量rwmutex。
2、?由于只有第一個讀者需要去競爭rwmutex，所以需要一個格外的變量count去記錄目前有幾個讀者。
3、又由于count變量對于多個讀者進程來說又是共享的變量（臨界區），所以需要另外一個互斥量mutex去約束讀者進程對count變量的訪問
b.資源?
資源視角主要包括有界緩存問題的計數信號量、先后執行問題的同步信號量等。本題顯然沒有這兩個信號量的約束，所以這邊資源視角沒有新的代碼修改。
但是資源視角是一個萬能視角，我們可以從資源視角來看上面的互斥：
1、rwmutex是訪問資源，第一個讀者進程需要和眾多寫者進程去競爭。只有競爭成功才可以進一步操作
2、對count的訪問也是一種讀者進程間的訪問資源，只有每個讀者進程競爭到了這個資源，才可以訪問count變量，對變量進行修改
c.配額?
配額僅僅在特殊的進程互斥問題上才需要考慮，本題中并沒有對配額進行限制。后續有遇到配額約束，我們再展開說說。
理發店問題?
問題描述
理發店里有一位理發師、一把理發椅和 n 把供等候理發的顧客坐的椅子。如果沒有顧客，理發師便在理發椅上睡覺；當一個顧客到來時，它必須叫醒理發師；如果理發師正在理發時又有顧客來到，那么，如果有空椅子可坐，顧客就坐下來等待，否則就離開理發店。
問題分析
1、只有n把顧客坐的等待椅子，一旦椅子滿了，新顧客就離開
2、理發椅子只有一個
3、沒有客人理發師就睡覺，客人來了理發師才理發
進程互斥問題三部曲
任何進程互斥（PV問題）都可以按照以下三步思考（來源：山東大學高曉程老師）
一、找進程——確定進程關系
二、找主營業務——拋開互斥，確定每個進程的主要任務
三、找同步約束
- 互斥
- 資源（計數信號量、空閑空間信號量等）
- 限額
理發店問題算法實現
一、找進程——確定進程關系
兩個進程：1、理發師進程；2、顧客進程
1、理發師和顧客進程存在先后關系，顧客來了理發師才理發
2、顧客進程之間存在互斥關系，理發椅只有一張
3、顧客進程存在上限，一旦超過上限便不再添加
?二、找主營業務
理發師：叫號+理發
顧客：取號+被理發
//理發師進程
Server(){while(1){叫號;理發;
}//顧客進程
Customer(){while(1){取號;被理發;
}?三、找同步約束
a.資源
顧客來了，給理發師釋放一個資源；理發師理完發，給顧客們釋放一種資源。所以這里需要兩個資源customer、server：
//默認先對信號量操作，再進行實際操作
//理發師進程
Server(){while(1){wait(customer);叫號; //減少一個顧客數，訪問臨界區signal(server);理發;
}//顧客進程
Customer(){while(1){取號; //增加一個顧客數(可能失敗，所以signal在后面），訪問臨界區signal(customer);wait(server)被理發;
}只有n把顧客坐的等待椅子，一旦椅子滿了，新顧客就離開。所以這里需要共享變量waiting，來記錄等待的顧客數目：
//默認先對信號量操作，再進行實際操作
//理發師進程
Server(){while(1){wait(customer);叫號; //減少一個顧客數，訪問臨界區waiting--; //減少一個等待顧客數，訪問臨界區signal(server);理發;
}//顧客進程
Customer(){while(1){if(waiting<n){取號; //增加一個顧客數(可能失敗，所以signal在后面），訪問臨界區signal(customer);wait(server)被理發;}else{離店;}
}b.互斥?
對所有臨界區的變量加上互斥鎖
//默認先對信號量操作，再進行實際操作
//理發師進程
Server(){while(1){wait(customer);wait(mutex);叫號; //減少一個顧客數，訪問臨界區waiting--; //減少一個等待顧客數，訪問臨界區signal(mutex);signal(server);理發;}
}//顧客進程
Customer(){while(1){wait(mutex); //這個wait同樣也是保護if語句，所以在后面else結束if語句時也需要signalif(waiting<n){取號; //增加一個顧客數(可能失敗，所以signal在后面），訪問臨界區waiting++;signal(mutex);signal(customer);wait(server)被理發;}else{signal(mutex);離店;}}
}c.配額?
配額僅僅在特殊的進程互斥問題上才需要考慮，本題中并沒有對配額進行限制。后續有遇到配額約束，我們再展開說說。
總結
本文到這里就結束啦~~有時間我們再來進入其他的經典進程互斥算法
如果覺得對你有幫助，辛苦友友點個贊哦~
知識來源：操作系統概念（黑寶書）、山東大學高曉程老師PPT及課上講解。不要私下外傳
(100分))
