讀者寫者問題萬能模板
讀者寫者問題，其本質(zhì)就是連續(xù)多個同類進(jìn)程訪問同一個臨界資源的問題。
第一個進(jìn)程開始訪問臨界資源前，需要對資源加上互斥鎖，后面的進(jìn)程再訪問時就不用再對資源加互斥鎖了，直到最后一個進(jìn)程訪問完后，發(fā)現(xiàn)自己是最后一個進(jìn)程，就解鎖互斥鎖。這就像一種情況：第一個人進(jìn)房間時必須順手開門，后面進(jìn)來的人和離開的人就不用開門，直到最后一個人離開房間時才需要順手關(guān)門。
代碼的通用模板是“三段式”，如下：
int count = 0; // 記錄正在訪問的進(jìn)程數(shù)量
信號量 busy = 1; // “完成事件”的互斥鎖
信號量 mutex = 1; // 變量 count 的互斥鎖
Process(){
while(1){
P(mutex);
count++; // 訪問資源的進(jìn)程數(shù)量加 1
if (count == 1){ // （1）如果發(fā)現(xiàn)自己是第一個訪問的進(jìn)程，需要負(fù)責(zé)加鎖
P(busy);
}
V(mutex);
完成事件; // （2）訪問臨界資源、完成臨界事件
P(mutex);
count--; // 訪問完畢，訪問資源的進(jìn)程數(shù)量減 1
if (count == 0){ // （3）如果發(fā)現(xiàn)自己是最后一個訪問的進(jìn)程，需要負(fù)責(zé)解鎖
V(busy);
}
V(mutex);
}
}
理解了最基本的原理后，下面來正式討論讀者寫者問題。
【讀者寫者問題】有讀者和寫者兩組并發(fā)進(jìn)程，共享一個文件，當(dāng)兩個或兩個以上的讀進(jìn)程（只是讀數(shù)據(jù)，不會對數(shù)據(jù)產(chǎn)生影響，而消費者讀數(shù)據(jù)時，會將數(shù)據(jù)取走，因此不能兩個消費者一起讀數(shù)據(jù)）同時訪問共享數(shù)據(jù)時不會產(chǎn)生副作用，但若某個寫進(jìn)程和其他進(jìn)程（讀進(jìn)程或?qū)戇M(jìn)程）同時訪問共享數(shù)據(jù)時則可能導(dǎo)致數(shù)據(jù)不一致的錯誤。
因此要求:
- 允許多個讀者可以同時對文件執(zhí)行讀操作；
- 只允許一個寫者往文件中寫信息；
- 任一寫者在完成寫操作之前不允許其他讀者或?qū)懻吖ぷ鳎?/li>
- 寫者執(zhí)行寫操作前，應(yīng)讓已有的讀者和寫者全部退出。
萬能模板 1——讀進(jìn)程優(yōu)先
即使寫者發(fā)出了請求寫的信號，但是只要還有讀者在讀取內(nèi)容，就還允許其他讀者繼續(xù)讀取內(nèi)容，直到所有讀者結(jié)束讀取，才真正開始寫。
int count = 0;
信號量 busy = 1; // “讀文件”和“寫文件”的互斥鎖
信號量 mutex = 1; // 變量 count 的互斥鎖
Reader(){ // 讀者進(jìn)程
while(1){
P(mutex);
count++;
if (count == 1){
P(busy);
}
V(mutex);
讀文件;
P(mutex);
count--;
if (count == 0){
V(busy);
}
V(mutex);
}
}
Writer(){ // 寫者進(jìn)程
while(1){
P(busy);
寫文件;
V(busy);
}
}
如果讀者寫者到達(dá)的順序是：讀者 1–讀者2–讀者 3–寫者 A–讀者 4–寫者 B–讀者 5，則：
- 讀者 1、讀者 2、讀者 3 到達(dá)，busy 加鎖，開始讀；
- 寫者 A 到達(dá)，但是讀者還在讀，未釋放 busy 鎖，因此不能寫；
- 讀者 4 到達(dá)，可以開始讀；
- 寫者 B 到達(dá)，但是讀者還在讀，未釋放 busy 鎖，因此不能寫；
- 讀者 5 到達(dá)，可以開始讀；
- 等到讀者們都讀完，釋放 busy 鎖，寫者才可以開始寫。
萬能模板 2——讀寫公平法
讀寫進(jìn)程都要排隊進(jìn)行操作文件。即使里面有讀進(jìn)程在操作文件，讀進(jìn)程也要和寫進(jìn)程一起排隊。
int count = 0;
信號量 queue = 1; // 實現(xiàn)“讀寫公平”的互斥鎖，可以視為一個隊列
信號量 busy = 1; // “讀文件”和“寫文件”的互斥鎖
信號量 mutex = 1; // 變量 count 的互斥鎖
Reader(){ // 讀者進(jìn)程
while(1){
P(queue); // 在無寫進(jìn)程請求時不需要進(jìn)入隊列
P(mutex); // 該互斥量實際上是多余的，上面語句已經(jīng)兼有互斥功能
count++;
if (count == 1){
P(busy);
}
V(mutex); // 該互斥量實際上是多余的，下面語句已經(jīng)兼有互斥功能
V(queue); // 恢復(fù)對共享文件的訪問
讀文件;
P(mutex);
count--;
if (count == 0){
V(busy);
}
V(mutex);
}
}
Writer(){ // 寫者進(jìn)程
while(1){
P(queue); // 在無其他寫進(jìn)程請求時不需要進(jìn)入隊列
P(busy);
寫文件;
V(busy);
V(queue); // 恢復(fù)對共享文件的訪問
}
}
如果讀者寫者到達(dá)的順序是：讀者 1–讀者2–讀者 3–寫者 A–讀者 4–寫者 B–讀者 5，則：
- 讀者 1、讀者 2、讀者 3 到達(dá)，busy 加鎖，開始讀；
- 寫者 A 到達(dá)，queue 加鎖，但是讀者還在讀，busy 鎖仍未釋放，因此不能寫；
- 讀者 4 到達(dá)，但是讀者還在讀，queue 和 busy 鎖仍未釋放，不能開始讀；
- 寫者 B 到達(dá)，queue 鎖和 busy 鎖仍未釋放，因此不能寫；
- 讀者 5 到達(dá)，但是讀者還在讀，queue 和 busy 鎖仍未釋放，不能開始讀；
- 等到讀者 1 到 3 都讀完，釋放 busy 鎖，寫者 A 才可以開始寫；
- 接下來就是按讀者 4、寫者 B、讀者 5 的順序依次訪問文件。
實際上，讀寫公平法也可以不用任何除了訪問文件外的互斥鎖：
信號量 busy = 1; // 也可以視為一個隊列
Reader(){ // 讀者進(jìn)程
while(1){
P(busy);
讀文件;
V(busy);
}
}
Writer(){ // 寫者進(jìn)程
while(1){
P(busy);
寫文件;
V(busy);
}
}
萬能模板 3——寫進(jìn)程優(yōu)先
如果有寫者申請寫文件，那么在申請之前還在讀取文件的讀進(jìn)程可以繼續(xù)讀取，但是如果再有讀者申請讀取文件，則不能夠讀取，只有在所有的寫者寫完之后才可以讀取。
int ReaderCount = 0; // 讀者數(shù)量
int WriterCount = 0; // 寫者數(shù)量
信號量 Read = 1; // “讀文件”的互斥鎖
信號量 Write = 1; // “寫文件”的互斥鎖
信號量 ReaderMutex = 1; // 變量 ReaderCount 的互斥鎖
信號量 WriterMutex = 1; // 變量 WriterCount 的互斥鎖
Reader(){ // 讀者進(jìn)程
while(1){
P(Read); // 每個讀進(jìn)程都需要對 Read 加鎖
P(ReaderMutex); // 對 ReadCount 的互斥，實際上，上條語句已經(jīng)兼有此功能，可以去掉
ReaderCount++;
if (ReaderCount == 1){ // 如果是第一個讀進(jìn)程
P(Write); // 則對寫者上鎖
}
V(ReaderMutex); // 對 ReadCount 的互斥，實際上，下條語句已經(jīng)兼有此功能，可以去掉
V(Read); // Read 解鎖
讀文件;
P(ReaderMutex); // 對 ReadCount 的互斥
ReaderCount--;
if (ReaderCount == 0){ // 如果是最后一個讀進(jìn)程
V(Write); // 則對寫者解鎖
}
V(ReaderMutex); // 對 ReadCount 的互斥
}
}
Writer(){ // 寫者進(jìn)程
while(1){
P(WriterMutex); // 對 WriterCount 的互斥
WriterCount++;
if (WriterCount == 1){ // 如果是第一個寫進(jìn)程
P(Read); // 則對讀者上鎖
}
V(WriterMutex); // 對 WriterCount 的互斥
P(Write); // Write 加鎖
寫文件;
V(Write); // Write 解鎖
P(WriterMutex); // 對 WriterCount 的互斥
WriterCount--;
if (WriterCount == 0){ // 如果是最后一個寫進(jìn)程
V(Read); // 則對讀者解鎖
}
V(WriterMutex); // 對 WriterCount 的互斥
}
}
如果讀者寫者到達(dá)的順序是：讀者 1–讀者2–讀者 3–寫者 A–讀者 4–寫者 B–讀者 5，則：
- 讀者 1、讀者 2、讀者 3 到達(dá)，Write 加鎖，開始讀；
- 寫者 A 到達(dá)，Read 加鎖，但是讀者還在讀，Write 鎖仍未釋放，因此不能寫；
- 讀者 4 到達(dá)，Read 鎖仍未釋放，不能開始讀；
- 寫者 B 到達(dá)，Write 鎖仍未釋放，因此不能寫；
- 讀者 5 到達(dá)，Read 鎖仍未釋放，不能開始讀；
- 等到讀者 1 到 3 都讀完，釋放 Write 鎖，寫者 A 才可以開始寫，寫完后 Write 解鎖。由于寫者 A 不是最后一個寫進(jìn)程，因此 Read 不解鎖；
- 寫者 B 進(jìn)行寫操作，寫完后 Write 解鎖，由于寫者 B 是最后一個寫進(jìn)程，因此 Read 解鎖；
- 讀者 4、讀者 5 依次進(jìn)行讀操作。
題目 1：南北過橋問題
【題目 1】有橋如下圖所示，車流如箭頭所示，橋上不允許兩車交匯，但允許同方向多輛車依次通過（即橋上可以有多個同方向的車）。用P、V操作實現(xiàn)交通管理以防止橋上堵塞。
【解答】直接套“三段式”，如下：
int count1 = 0; // 北到南的車輛數(shù)
int count2 = 0; // 南到北車輛數(shù)
信號量 bridge = 1;
信號量 mutex1 = 1;
信號量 mutex2 = 1;
北到南(){
P(mutex1);
count1++;
if (count1 == 1){
P(bridge);
}
V(mutex1);
北到南過橋;
P(mutex1);
count1--;
if (count1 == 0){
V(bridge);
}
V(mutex1);
}
南到北(){
P(mutex2);
count2++;
if (count2 == 1){
P(bridge);
}
V(mutex2);
南到北過橋;
P(mutex2);
count2--;
if (count2 == 0){
V(bridge);
}
V(mutex2);
}
題目 2：錄像廳問題
【題目 2】假設(shè)一個錄像廳有 0,1,2 三種不同的錄像片可由觀眾選擇放映。錄像廳的放映規(guī)則為：
- 任何時刻最多只能放映一種錄像片，正在放映的錄像片是自動循環(huán)放映的。最后一個觀眾主動離開時結(jié)束當(dāng)前錄像片的放映。
- 選擇當(dāng)前正在放映錄像片的觀眾可立即進(jìn)入，允許同時有多位選擇同一中錄像片的觀眾同時觀看，同時觀看的觀眾數(shù)量不受限制。
- 等待觀看其他錄像片的觀眾按到達(dá)順序排隊，當(dāng)一種新的錄像片開始放映時，所有等待觀看該錄像片的觀眾可一次進(jìn)入錄像廳同時觀看。
【解答 1】本題也可以直接套“三段式”，如下：
int count0 = 0; // 看影片 0 的觀眾數(shù)
int count1 = 0; // 看影片 1 的觀眾數(shù)
int count2 = 0; // 看影片 2 的觀眾數(shù)
信號量 movie = 1;
信號量 mutex0 = 1;
信號量 mutex1 = 1;
信號量 mutex2 = 1;
看影片0的觀眾(){
P(mutex0);
count0++;
if (count0 == 1){
P(movie);
}
V(mutex0);
看影片0;
P(mutex0);
count0--;
if (count0 == 0){
V(movie);
}
V(mutex0);
}
看影片1的觀眾(){
P(mutex1);
count1++;
if (count1 == 1){
P(movie);
}
V(mutex1);
看影片1;
P(mutex1);
count1--;
if (count1 == 0){
V(movie);
}
V(mutex1);
}
看影片2的觀眾(){
P(mutex2);
count2++;
if (count2 == 1){
P(movie);
}
V(mutex2);
看影片2;
P(mutex2);
count2--;
if (count2 == 0){
V(movie);
}
V(mutex2);
}
【解答 2】借助“寫進(jìn)程優(yōu)先”的思想，觀看某影片的觀眾在進(jìn)去前，可以先把要觀看其他影片的觀眾先上鎖，讓他們暫時阻塞，如下：
int count0 = 0; // 看影片 0 的觀眾數(shù)
int count1 = 0; // 看影片 1 的觀眾數(shù)
int count2 = 0; // 看影片 2 的觀眾數(shù)
信號量 mutex0 = 1; // 影片 0 的互斥鎖，兼有對變量 count0 的互斥功能
信號量 mutex1 = 1; // 影片 1 的互斥鎖，兼有對變量 count1 的互斥功能
信號量 mutex2 = 1; // 影片 2 的互斥鎖，兼有對變量 count2 的互斥功能
看影片0的觀眾(){
P(mutex0);
count0++;
if (count0 == 1){ // 第一個進(jìn)去的觀眾把其他影片的觀眾“擋住”
P(mutex1);
P(mutex2);
}
V(mutex0);
看影片0;
P(mutex0);
count0--;
if (count0 == 0){ // 最后一個出來的觀眾允許其他影片的觀眾進(jìn)來
V(mutex1);
V(mutex2);
}
V(mutex0);
}
看影片1的觀眾(){
P(mutex1);
count1++;
if (count1 == 1){ // 第一個進(jìn)去的觀眾把其他影片的觀眾“擋住”
P(mutex0);
P(mutex2);
}
V(mutex1);
看影片1;
P(mutex1);
count1--;
if (count1 == 0){ // 最后一個出來的觀眾允許其他影片的觀眾進(jìn)來
V(mutex0);
V(mutex2);
}
V(mutex1);
}
看影片2的觀眾(){
P(mutex2);
count2++;
if (count2 == 1){ // 第一個進(jìn)去的觀眾把其他影片的觀眾“擋住”
P(mutex0);
P(mutex1);
}
V(mutex2);
看影片2;
P(mutex2);
count2--;
if (count2 == 0){ // 最后一個出來的觀眾允許其他影片的觀眾進(jìn)來
V(mutex0);
V(mutex1);
}
V(mutex2);
}
看似沒毛病吧。然而，事實上這段代碼是有問題的，可能會引發(fā)死鎖，哈哈哈……你發(fā)現(xiàn)了嗎？
題目 3：更衣問題
【題目 3】某男??球俱樂部，有教練、隊員若?。每次?球訓(xùn)練開始之前，教練、球員都需要先進(jìn)?更?室換?服，可惜俱樂部只有?個更?室。教練們臉?薄，?法接受和別?共?更?室。隊員們臉?厚，可以和其他隊員?起使?更?室。如果隊員和教練都要使?更?室，則應(yīng)該讓教練優(yōu)先。請使? P、V 操作描述上述過程的互斥與同步，并說明所?信號量及初值的含義。文章來源：http://www.zghlxwxcb.cn/news/detail-794771.html
【解答】把教練視為寫進(jìn)程，把隊員視為讀進(jìn)程，更衣室視為緩沖區(qū)，則該題需要實現(xiàn)的“寫進(jìn)程優(yōu)先”。如下：文章來源地址http://www.zghlxwxcb.cn/news/detail-794771.html
int ReaderCount = 0; // 讀者數(shù)量
int WriterCount = 0; // 寫者數(shù)量
信號量 Read = 1; // “讀文件”的互斥鎖
信號量 Write = 1; // “寫文件”的互斥鎖
信號量 ReaderMutex = 1; // 變量 ReaderCount 的互斥鎖
信號量 WriterMutex = 1; // 變量 WriterCount 的互斥鎖
Reader(){ // 讀者進(jìn)程（相當(dāng)于教練）
while(1){
P(Read); // 每個讀進(jìn)程都需要對 Read 加鎖
P(ReaderMutex); // 對 ReadCount 的互斥
ReaderCount++;
if (ReaderCount == 1){ // 如果是第一個讀進(jìn)程
P(Write); // 則對寫者上鎖
}
V(ReaderMutex); // 對 ReadCount 的互斥
V(Read); // Read 解鎖
讀文件;
P(ReaderMutex); // 對 ReadCount 的互斥
ReaderCount--;
if (ReaderCount == 0){ // 如果是最后一個讀進(jìn)程
V(Write); // 則對寫者解鎖
}
V(ReaderMutex); // 對 ReadCount 的互斥
}
}
Writer(){ // 寫者進(jìn)程（相當(dāng)于隊員）
while(1){
P(WriterMutex); // 對 WriterCount 的互斥
WriterCount++;
if (WriterCount == 1){ // 如果是第一個寫進(jìn)程
P(Read); // 則對讀者上鎖
}
V(WriterMutex); // 對 WriterCount 的互斥
P(Write); // Write 加鎖
寫文件;
V(Write); // Write 解鎖
P(WriterMutex); // 對 WriterCount 的互斥
WriterCount--;
if (WriterCount == 0){ // 如果是最后一個寫進(jìn)程
V(Read); // 則對讀者解鎖
}
V(WriterMutex); // 對 WriterCount 的互斥
}
}
到了這里，關(guān)于【操作系統(tǒng)-進(jìn)程】PV操作——讀者寫者問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
