【操作系統】進程管理——用信號量機制解決問題，以生產者-消費者問題為例（個人筆記）

學習日期：2024.7.10

內容摘要：利用信號量機制解決幾個經典問題模型

引言

問題模型

生產者-消費者問題（經典）

多生產者-多消費者問題

吸煙者問題

讀者寫者問題（難點）

哲學家進餐問題（避免死鎖）

引言

在《信號量機制》章節中，我們已經學習了信號量的概念和用其實現進程同步和互斥的工作原理，下面結合實際的模型來看信號量機制如何起效。

PV操作題目分析步驟：

1.關系分析。找出題目中描述的各個進程，分析它們之間的同步、互斥關系。

2.整理思路。根據各進程的操作流程缺點P、V操作的大致順序。

3.設置信號量。根據題目條件確定信號量初始值（互斥一般為1，同步一般看對應資源的初始值）

簡記口訣：

互斥：緊鄰操作，成對PV。（緊鄰互斥操作，在同一進程內完成PV）

同步：前V后P，前后后前。（在不同進程內進行操作以保證順序執行，在前一個進程完成后進行V操作，在后一個進程開始前進行P操作）

問題模型

生產者-消費者問題（經典）

系統中有一組生產者進程和消費者進程，生產者每次生產一個產品放入緩沖區，消費者每次從緩沖區中取出一個產品使用（“緩沖區”理解為二者共享的倉庫，“產品”理解為某種數據）

緩沖區是一個初始為空，大小固定為n，雙方共享的區域，且緩沖區是臨界資源，各進程必須互斥訪問。（原因：如果不是互斥訪問的，可能兩個生產者進程在同一片區域放入數據，導致數據覆蓋丟失）

首先分析，顯然：

①緩沖區沒滿的情況下，生產者才能生產，二者有同步關系。

②緩沖區不空的情況下，消費者才能消費，二者有同步關系。

③進程對緩沖區的訪問必須互斥。

那么，設置三個變量，一個mutex表示互斥標記，一個empty表示空閑區數目，一個full表示裝入區數目。每次生產者進程行動時，P(empty),V(full)，消費者行動時則反之

這樣就能實現通過PV操作來表示資源的獲取與釋放。

注意！實現互斥是在同一進程中進行一對PV操作，在“把產品放入緩沖區/從緩沖區中取出”這一對臨界資源的訪問行為前后，成對進行。

而同步關系是在兩進程分開執行，在一個進程中執行P，另一個執行V。具體理論部分可以參考上一章。

Q：能否交換相鄰P操作的順序？

不能。假如交換了生產者的前兩個P操作的順序，若緩沖區內已經放滿產品，此時empty=0，full=n。若生產者先進行P(mutex)聲明自己獨占了緩沖區，然后P(empty)發現緩沖區的empty區不足，就會進入阻塞狀態。

之后消費者想占用緩沖區，釋放empty資源時，因為生產者已經占用了mutex，沒有釋放，因為互斥會導致無法進行V(empty)操作

這樣，生產者在等待消費者釋放empty，消費者在等待生產者解除對緩沖區的占用，雙方會無限等待下去，形成死鎖。

所以表示互斥的PV部分要成對出現，成對執行，且實現互斥的P操作一定在實現同步操作的P操作之后。

Q:能否交換相鄰V操作的順序？

可以，V操作不會導致進程阻塞，但是為了方便理解記憶，還是讓實現互斥的PV操作緊鄰互斥行動區為好。

Q：能否不依賴互斥標識資源mutex？

通常不行，但是特殊情況下可以。這個特殊情況就是緩沖區容量為1的情況（即empty的初始值為1），此時如果一個生產者生產了產品，執行P(empty)，另一個生產者也想生產產品時，因為empty的值已經是0，就會發生阻塞，從而避免了生產者同時訪問的問題。而在生產者執行完互斥操作，V(full)之前，因為full的值為0，消費者進行P(full)時也會阻塞，避免了生產者訪問時消費者同時訪問的問題，從而不依賴mutex就能實現互斥訪問。

多生產者-多消費者問題

是生產者-消費者問題的變形，區別在于增加了若干組生產者和消費者。比如說1號生產者會生產1型商品，2號生產者生產2型商品，而1號消費者只消費1型商品，2消費者只消費2型商品。

所有的生產者和消費者仍舊共享一個緩沖區，此處的“多”指的是“多類”而不是“多個”，與上一問題的根本區別是有多類生產者和消費者。

關系分析：

①首先，同生產者-消費者問題的前提一樣，緩沖區沒滿才能生產，不空才能消費，且互斥訪問。

②根據不同資源的類型，分別PV不同的變量，來為每對生產者和消費者確立同步關系。

在分析同步問題的時候，不能從單個進程行為的角度來分析，而應該從事件角度分析。

不要想著“x號生產者生產了一個x號產品，x號消費者......”，然后設置四個同步信號量。而是從事件的角度分析，把進程的先后順序概括為事件的先后順序，在這個例子中，就是生產產品事件先于消耗產品事件。

生產產品可以是1號生產者，也可以是2號生產者，它們只需要每次占用一個倉庫空間P(empty)，然后增加一個對應產品V（product_x）。同樣的，消費者也只要每次消耗一個產品P(product_x)，然后釋放一個空間P(empty)就行了。最后再在互斥操作前后加上mutex的成對PV操作保證互斥，根據空間的大小設置empty的初始值，就可以解決問題了！

吸煙者問題

仍然是生產者-消費者問題的變形。更準確的來說，是“可生產多種產品的單生產者-多消費者問題”

假設一個系統有三個抽煙者進程和一個供應者進程，每個抽煙者進程不停的卷煙并抽煙，這需要三種材料：煙草、紙卷和膠水。在三個抽煙者中，第一個有煙草，第二個有紙卷，第三個有膠水。供應者會無限提供三種材料，每次將兩個材料置于桌面，而擁有剩下那個材料的抽煙者就會拿走，完成抽煙，然后給供應者一個信號告訴他完成了，供應者就會放另外兩種材料在桌上，讓三個抽煙者能夠輪流抽煙。

首先，桌子可以抽象為容量為1，互斥訪問的緩沖區。為什么放兩件東西容量為1呢？

我們將供應者供應的兩件東西看作是一個組合，則他一共供給三個組合，第一個消費者需要紙卷+膠水，定義為組合1，第二個消費者需要煙草＋膠水，定義為組合2，同理得組合3。

這樣問題就抽象為了一個生產者能生產1號，2號，3號三種產品，分別對應三個消費者，要進行輪流消費，緩沖區容量為1。

關系分析：

①桌上有組合x 先于 x號消費者取走東西，且緩沖區互斥訪問。

②消費者發出完成信號先于生產者將下一個組合放到桌上。

Q：輪流操作如何實現？

如右圖所示，通過一個if(i==0)的選擇分支結構，和結尾的i=(i+1)%3，實現了讓i在0，1，2不斷循環變化，從而輪流執行三個部分的生產，每次產生對應的offer。補充：如果要隨機實現，可以用Random（i）

而如上圖每一個消費者每次消耗一個offer的商品P(offer_x),然后再釋放一個finish信號給生產者，保證先釋放信號，然后生產者再生產下一個產品。

之前介紹過，因為此時緩沖區的容量為1，故不需要互斥信號量mutex也可以實現互斥訪問。

讀者寫者問題（難點）

在系統中有讀者、寫者兩組并發進程，共享一個文件。多個讀者可以同時對文件執行讀操作，但是只允許一個寫者往文件中寫入信息，寫者對文件的訪問必須互斥，也不能邊寫邊讀，每個寫者在工作時都必須獨占該共享文件。

與消費者進程不同，讀者進程在讀數據時，不會“消耗”數據，所以讀者進程可以同時訪問共享數據，互不影響。

不能邊讀邊寫是因為，如果允許并發執行，讀者可能先讀了某數據的一部分，但剩下的部分被寫者覆蓋了，導致讀者所讀的數據并不是所期望的。不能同時寫的原因同生產者進程互斥原因，會相互覆蓋。

關系分析：

①寫者進程和所有進程互斥，讀者進程之間不互斥。

難點就在于，如何在實現寫者進程互斥的同時，讓讀者進程不互斥。

我們一步一步來：

semaphore rw=1writer(){while(1){P(rw);  //寫之前上鎖寫文件操作...V(rw);  //寫完解鎖}
}reader(){while(1){P(rw);    //讀之前上鎖讀文件操作...V(rw);  //讀完解鎖}
}

?先寫個最簡單的，但是顯然，這樣是每個進程都互斥訪問共享區，不能實現同時讀操作。

那么，要如何實現“同時讀”呢？可以設法讓后面的讀進程跳過P(rw)這一步。

所以，邏輯代碼變成了這樣：

semaphore rw=1;
int count = 0;  //記錄當前有幾個讀進程在訪問文件writer(){while(1){P(rw);  //寫之前上鎖寫文件操作...V(rw);  //寫完解鎖}
}reader(){while(1){
if(count==0)  //由第一個讀進程負責上鎖P(rw);    //讀之前上鎖count++;    讀文件操作...count--;   
if(count==0)//由最后一個讀進程負責解鎖V(rw);  //讀完解鎖}
}

我們引入了一個新的變量count用來記錄當前訪問文件的讀進程數，當count==0時，訪問文件的讀進程是第一個，它負責上鎖，之后訪問的讀進程，因為count！=0，就跳過了P(rw)語句，從而可以直接進行讀文件操作。同理，當最后一個讀進程讀完時，count==0，最后一個進程進行V(rw)釋放資源，表示沒有讀進程還在操作了。

但是這樣還是有一個問題，因為讀進程是并發執行的，如果兩個讀進程同時開始執行，當第一個讀者進程P(rw)以后，還沒有來得及count++時，第二個讀進程可能已經通過了conunt的判斷語句，也進行P(rw),但是此時rw已經為0了，這會導致第二個進程阻塞。

顯然，出現上一問題的原因是，我們對count變量的檢查和賦值無法一氣呵成。無法一氣呵成...?我們最初用PV操作就是為了解決進程互斥中，軟件實現方法無法一氣呵成的問題的，（詳見《進程的同步與互斥》）所以可以想到，再加一組互斥標識，保證進程能互斥的訪問count。

semaphore rw = 1;
semaphore mutex = 1;//用于保證對count變量的互斥訪問
int count = 0;  //記錄當前有幾個讀進程在訪問文件writer(){while(1){P(rw);  //寫之前上鎖寫文件操作...V(rw);  //寫完解鎖}
}reader(){while(1){P(mutex);if(count==0)  //由第一個讀進程負責上鎖P(rw);    //讀之前上鎖count++; V(mutex);   讀文件操作...P(mutex);count--;   if(count==0)//由最后一個讀進程負責解鎖V(rw);  //讀完解鎖V(mutex);}
}

?我們引入了mutex變量，來保證進程能互斥的訪問count,此時如果兩個讀進程同步訪問count，第一個進程會P(mutex)阻止其它讀進程修改count，并且在自己修改完count之后，其它進程才能進行if判斷，這樣就不會出現上述問題了。兩組對于mutex的PV操作，能夠保證進程對count的互斥訪問。

但是，還有一個潛在的問題（受不了了），只要有讀進程還在讀，rw的值就始終是0，寫進程就會一直阻塞，如果一直有源源不斷的讀進程，寫進程就會饑餓。在這種算法中，讀進程是優先的。那么，該如何避免寫進程饑餓呢？就是說，怎樣能讓寫進程在想寫入的時候，在有限的等待時間內就能寫入呢？

semaphore rw = 1;
semaphore mutex = 1;//用于保證對count變量的互斥訪問
semaphore w = 1;  //用于實現“寫優先”
int count = 0;  //記錄當前有幾個讀進程在訪問文件writer(){while(1){P(w);P(rw);  //寫之前上鎖寫文件操作...V(rw);  //寫完解鎖V(w);}
}reader(){while(1){P(w);P(mutex);if(count==0)  //由第一個讀進程負責上鎖P(rw);    //讀之前上鎖count++; V(mutex);V(w);   讀文件操作...P(mutex);count--;   if(count==0)//由最后一個讀進程負責解鎖V(rw);  //讀完解鎖V(mutex);}
}

?我們又引入了一個新的變量w，用于實現寫優先。

假如三個進程讀者A，寫者，讀者B并發執行。

當讀者進程A通過了上半部分，開始進行讀文件操作時，釋放了w，占用了rw。此時寫者進程可以進行P(w)操作了，但是會被阻塞在P(rw)操作上。當讀者進程B開始運行時，因為寫進程已經進行過P(w)操作了，讀者B會在P(w)處被阻塞。

這樣當讀者A的讀操作結束時，count--后為0，讀者A會認為自己是最后一個讀進程，從而釋放rw，這樣寫者就可以執行P(rw)，實現了寫者優先于讀者B執行。

此方法并不是真正的“寫優先”，只是保證了寫進程不會饑餓，相對公平的實現了先來先服務。

此處的w好比一個提供順序功能的標記，第一個讀者最開始先占用，然后在讀文件之前釋放，第二個讀者如果在寫者之后來，就會因為寫者已經占用了w而不能繼續。

小結：

讀者-寫者問題為我們解決復雜的互斥問題提供了思路，核心思想在于設置一個計數器count來記錄當前正在訪問共享文件的讀進程數，用count的值來判斷當前進入的進程是否是第一個/最后一個讀進程，從而跳過部分P指令，實現讀進程不互斥。

在對count變量的檢查和賦值不能一氣呵成時，采用mutex變量來確保count部分被互斥訪問。

在寫進程會饑餓時，引入了w變量來確保可以公平的完成先來先服務。

哲學家進餐問題（避免死鎖）

圓桌上坐著5位哲學家，每兩個哲學家之間擺著一根筷子，桌子的中間是火鍋，哲學家們會思考和干飯。哲學家們在思考時不會影響別人，只有想干飯時，才會拿起左、右各一根筷子（一根一根拿），如果筷子已經在他人手上則需要等待。因為火鍋很燙，哲學家必須需要一雙筷子才能進餐，進餐完畢后，哲學家放下筷子繼續思考。

難點：這個問題中只有互斥關系，沒有同步關系，但是在這個模型中，每個哲學家進程都需要同時持有兩個臨界資源才能開始吃飯。我們可以想到一個很尷尬的情況，那就是每個哲學家都拿了一根筷子，大家都沒有辦法吃飯，但是都在等待別人吃飯然后讓出筷子，這就是死鎖。這是臨界資源分配不當導致的，我們要設法避免這種情況發生。

關系分析：

①系統中有5個哲學家進程，5位哲學家與左右鄰居對其之間的筷子的訪問是互斥關系。

②筷子是本模型中的臨界資源，哲學家想要吃飯需要獲取其左右兩根筷子。

我們給哲學家和筷子編號為0~4。顯然，編號為i的哲學家需要編號i和i+1的兩根筷子來吃飯，考慮到邊界，嚴謹的表述是i和(i+1)%5

我們很容易想到一個簡單的寫法：

這種寫法能實現對筷子的互斥訪問，但是不能避免前面提到的死鎖問題。那么該怎么解決呢？

①可以要求奇數號哲學家先拿左手的筷子，偶數號哲學家先拿右手的筷子。如圖所示，以0、1為例，這樣兩位就會在一開始爭搶1號筷子，誰先拿到，另一個就在不占用任何筷子的情況下直接進入阻塞態，這樣就避免了五個人每人占用一根筷子進入阻塞態的死鎖。

以代碼實現的話，在每個哲學家拿筷子之前判斷號碼的奇偶，然后確定P操作的順序即可。

②保證至少有一個哲學家可以一氣呵成的拿到完整的一雙筷子。

使用mutex互斥變量，保證至少有一個哲學家可以拿到完整的一雙筷子。

在拿筷子的部分前后加入了mutex的PV操作。當0號哲學家拿筷子時，先P(mutex)，之后依次拿起左右的筷子，即使在這過程中發生了進程調度，別的進程也會因為mutex值已經為0被阻塞，不能拿起筷子，直到0號哲學家把筷子拿完，釋放mutex以后，別的哲學家才能拿起筷子。這樣能夠保證，至少第一個開始拿筷子的進程會一氣呵成的拿到一雙筷子，避免死鎖。