進程與進程管理 | 經典進程同步問題

05-01

生產者－消費者問題

問題描述：

若干進程通過有限的共享緩衝區交換數據。其中，"生產者"進程不斷寫入，而"消費者"進程不斷讀出；共享緩衝區共有N個；任何時刻只能有一個進程可對共享緩衝區進行操作。

分析：

確定進程：進程數量及工作內容；
確定進程間的關係：

互斥：多個進程間互斥使用同一個緩衝池；
同步：當緩衝池空時，消費者必須阻塞等待；當緩衝池滿時，生產者必須阻塞等待。

設置信號量：

Mutex：用於訪問緩衝池時的互斥，初值是1
Full：「滿緩衝」數目，初值為0；
Empty：「空緩衝"數目，初值為N。full+empty=N
in, out：生產者進程和消費者進程可以操作的緩衝區數目，初值為0

如下是生產者和消費者進程的演算法描述：

＃define N 100＃define MAXLEN 80typedef struct{ int num; char array[MAXLEN];}Message ;semaphore mutex={1,NULL};semaphore empty={N,NULL};semaphore full={0,NULL};Message buffers[N];int in =0, out=0; cobegin // 生產者進程 program producer { Message p_puf; while(1){ produce a message in p_buf; // 生產一個消息，放在 p_buf 中。 P(empty); // 判斷當前緩衝池裡是否有空閑的緩衝區 P(mutex); // 判斷當前緩衝池是否為空閑，申請緩衝池的使用權。 buffers[in] = p_buf; // 將消息放入緩衝區 in = (in + 1)%N; V(mutex); // 釋放臨界資源緩衝池 V(full); // 向消費者進程發送消息，緩衝池中有消息存在 } } // 消費者進程 program consumer { Message c_buf; while(1){ P(full); // 判斷緩衝池裡是否有滿緩衝區 P(mutex); // 申請緩衝池使用權 c_buf = buffers[out]； out =(out + 1)%N; V(mutex)； V(empty)； consume the message in c_buf; } }coend

對於消費者的兩個P操作，我們不能隨意的將其進行調換，因為當 mutex=1, full=0, empty=n 的時候，如果先執行 P(mutex) 在執行 P(full)。那麼消費者進程就會在 P(full) 中被阻塞，然而此時的 mutex = 0。生產者也會在 P(mutex) 中被阻塞，不能執行。

哲學家進餐問題

問題描述：

有五個哲學家坐在一張圓桌旁，在圓桌上有五個盤子有五隻筷子，他們的生活方式就是交替地進行思考和進餐。平時，一個哲學家進行思考，飢餓時取其左右兩隻筷子，只有拿到這兩隻筷子是才能進餐；進餐完畢，放下筷子繼續思考。

約束關係：

只有拿到兩隻筷子時,哲學家才能吃飯。
如果筷子已被別人拿走,則必須等別人吃完之後才能拿到筷子。

該問題描述的是計算機系統中一些需要兩個或兩個以上條件同時滿足時才能進行執行的進程。

演算法描述：

semaphore chopstick[0…4]={1,NULL};cobegin program philosopher（i） { thinking ... // 思考，等待 P(chopstick[i])； // 申請右手邊的筷子 P(chopstick[(i+1) mod 5]); // 申請左手邊的筷子 eating; // 進餐 V(chopstick[i])； // 釋放左右兩邊的筷子 V(chopstick[(i+1) mod 5]); }coend

但是該演算法存在一個問題，就是當所有的哲學家都去拿右邊的筷子的時候，就會導致所有的哲學家都沒有左手邊的筷子。導致死鎖。

解決辦法如下：

每一個哲學家必須同時那左右的筷子，如果有一隻筷子不滿足，就全部不拿。
奇數編號的哲學家先去拿右手邊的筷子，偶數編號的哲學家先去拿左手邊的筷子。
規定最多只允許四個哲學家同時拿筷子。

新的演算法描述如下，使用的是第三種方法來實現：

semaphore chopstick[0…4]={1,NULL};semaphore sm={4,NULL}; // 進程是否還有資格來拿筷子cobegin program philosopher（i） { P(sm); P(chopstick[i]); P(chopstick[(i+1)mod 5]); eating; V(chopstick[i]); V(chopstick[(i+1)mod 5]); V(sm); }coend

讀者優先的讀者－寫者問題

問題描述：

有多個讀者進程和多個寫者進程共享一數據。要求多進程對共享數據進行讀寫操作時，任一時刻「寫者」最多只允許一個，而「讀者」則允許多個。

制約關係：

當有寫者在寫數據時，其他寫者和讀者必須等待；
當有讀者在讀數據時，其他寫者必須等待；但其他讀者可以同時讀數據。

信號量設置：

信號量wmutex表示「允許寫」，互斥使用數據，初值是1
公共整形變數Readcount表示「正在讀」的讀者數，初值是0；
信號量Rmutex：實現多個讀者對Readcount的互斥操作，初值是1。

wmutex: semaphore = 1; //讀者與寫者之間、寫者與寫者之間互斥使用共享數據readcount: int = 0; //當前正在讀的讀者數量 rmutex: semaphore = 1 //多個讀者互斥使用readcount

演算法描述：

Cobegin:Reader: begin Repeat P(rmutex) // 沒有其他的讀者進程在訪問 readcount if readcount=0 then P(wmutex); // 判斷是否有讀者在讀 readcount++; V(rmutex); // 釋放臨界資源 readcount 的使用權 reading … P(rmutex); readcount--; if readcount=0 then V(wmutex); // 如果有其他讀者進程，則不釋放 V(rmutex); until falseendwriter: begin repeat: P(wmutex); // 是否有別的進程在用 writing … V(wmutex); until falseendcoend

在該問題中是讀者優先的讀者 - 寫者問題：如果有讀者在讀，則寫者必須等待。如果此時有另一個讀者想要讀數據，則它可以越過寫者進程進行讀數據。

寫者優先的讀者－寫者問題

問題描述：

對共享資源的讀寫操作，任一時刻「寫者」最多只允許一個，而「讀者」則允許多個。

寫進程與其他所有進程互斥
允許多個讀者同時讀
寫者優先於讀者（一旦有寫者，則後續讀者必須等待；若同時有讀者和寫者在等待，喚醒時有限考慮先者。）

演算法描述：

wmutex:semaphore=1 //讀者與寫者之間、寫者與寫者之間互斥使用共享數據S：semaphore=1 //當至少有一個寫者準備訪問共享數據時，它可使後續的讀者等待寫完成S2：semaphore＝1 //阻塞第二個以後的等待讀者Readcount,writecount: int = 0,0; //當前讀者數量、寫者數量mutex1 :semaphore = 1 //多個讀者互斥使用 readcountmutex2 :semaphore = 1 //多個寫者互斥使用 writecountCobegin:Reader: begin Repeat P(S2); // 是否已經有讀者進程在等待隊列中 P(S); // 是否有寫者進程在等待隊列中 P(mutex1); // 沒有其他的讀者進程在訪問 readcount if readcount=0 then P(wmutex); // 判斷是否有寫者進程在寫 readcount++; V(mutex1); // 釋放 readcount V(S); // 允許寫者進程等待 V(S2); // 允許讀者進程等待 reading … P(mutex1); readcount--; if readcount=0 then V(wmutex); // 允許寫者進程寫 V(mutex1); // 釋放 readcount until falseendwriter: begin repeat; P(mutex2); // 申請訪問 writecount if writecount=0 then P(S); // 寫者進程進入等待隊列 writecount++; V(mutex2）; // 釋放 writecount P(wmutex); // 是否有讀者或者寫者正在操作 writing … V(wmutex); // 寫操作完成 P(mutex2); writecount--; if writecount=0 then V(S); // 沒有寫者在等待，允許讀者進程進入操作 V(mutex2）; until false;endcoend;