進程同步算法習題課劉揚【例題1】司機進程：while(1){啟動車輛正常駕駛到站停車}…售票員進程：while(1){關門售票開門}…用wait、signal操作解決司機與售票員的問題分析：為保證車輛行駛安全，售票員必須關好車門，然后通知司機啟動車輛，在行駛過程中售票員不能打開車門，待車到站停穩后，司機通知售票員才能打開車門，如此不斷重復。為此，須設置兩個信號量S1，S2用來控制司機和售票員的行為，初值都為0。解:

算法如下：司機進程：while(1){wait(S1)啟動車輛正常駕駛

到站停車signal(S2)}…售票員進程：while(1){關門signal(S1)售票wait(S2)開門}…【例題2】1.用wait、signal操作解決下圖之同步問題提示：分別考慮對緩沖區S和T的同步，再合并考慮putcopygetst解:設置四個信號量Sin=1，Sout=0，Tin=1，Tout=0；

put：while（1）{wait(Sin）;將數放入S;

signal

(Sout);}

copy：while（1）{

wait

(Sout）;

wait

(Tin）;將數從S取出放入T;

signal

(Tout);

signal

(Sin);}get：while（1）{

wait

(Tout）;將數從T取走;signal(Tin);}思考題：如果S和T是由多個緩沖區組成的緩沖池，上述算法將如何修改？【例題3】桌上有一空盤，最多允許存放一只水果。爸爸可向盤中放一個蘋果或放一個桔子，兒子專等吃盤中的桔子，女兒專等吃蘋果。 試用wait、signal操作實現爸爸、兒子、女兒三個并發進程的同步。

分析：設置一個信號量S表示空盤子數，一個信號量So表示盤中桔子數，一個信號量Sa表示盤中蘋果數，初值分別為1，0，0。解:算法如下：Father(){while(1){

wait(S);將水果放入盤中;if(是桔子)signal(So);elsesignal(Sa);}}Son(){while(1){wait(So)取桔子signal(S);吃桔子;}}Daughter(){while(1){wait(Sa)取蘋果signal(S);吃蘋果;}}【例題4】有一個倉庫，可以存放A和B兩種產品，但要求：（1）

每次只能存入一種產品（A或B）（2）

－N＜A產品數量－B產品數量＜M。其中，N和M是正整數。試用wait、signal操作描述產品A與B的入庫過程。解:分析：設兩個同步信號量Sa、Sb，其中：Sa表示允許A產品比B產品多入庫的數量，初值為M-1。Sb表示允許B產品比A產品多入庫的數量，初值為N-1。設互斥信號量mutex，初值為1。

B產品入庫進程：j=0;while(1){

wait(Sb);wait(mutex);B產品入庫

signal(mutex);signal(Sa);消費產品;};A產品入庫進程：

i=0;

while(1){

生產產品;

wait(Sa);

wait(mutex);A產品入庫

signal(mutex);

signal(Sb);

};算法如下：例題5

進程A1、A2，…An1通過m個緩沖區向進程B1、B2、…Bn2不斷發送消息。發送和接收工作遵循下列規則：（1）每個發送進程一次發送一個消息，寫入一個緩沖區，緩沖區大小等于消息長度。（2）對每個消息，B1，B2，…Bn2都須各接收一次，讀入各自的數據區內。（3）m個緩沖區都滿時，發送進程等待，沒有可讀消息時，接收進程等待。試用wait、signal操作組織正確的發送和接收工作。分析：每個緩沖區只要寫一次但要讀n2次，因此，可以看成n2組緩沖區，每個發送者要同時寫n2個緩沖區，而每個接收者只要讀它自己的緩沖區。Sin[n2]=m；表示每個讀進程開始有m個空緩沖區。Sout[n2]=0；表示每個讀進程開始有0個可接收的消息。解：先將問題簡化：設緩沖區的大小為1有一個發送進程A1有二個接收進程B1、B2設有信號量Sin[1]、Sin[2]初值為1設有信號量Sout[1]、Sout[2]初值為0Bi：while(1){

wait(Sout[i]);

從緩沖區取數signal(Sin[i]);}A1:

while(1){

wait(Sin[1]);

wait(Sin[2]);

將數據放入緩沖區

signal(Sout[1]);signal(Sout[2]);

}向目標前進一步:設緩沖區的大小為m有一個發送進程A1有二個接收進程B1、B2設有信號量Sin[1]、Sin[2]初值為m設有信號量Sout[1]、Sout[2]初值為0Bi：while(1){

wait(Sout[i]);

wait(mutex); 從緩沖區取數

signal(mutex);signal(Sin[i]);};A1:

while(1){

wait(Sin[1]);

wait(Sin[2]);

wait(mutex);

將數據放入緩沖區

signal(mutex);

signal(Sout[1]);signal(Sout[2]);

}到達目標設緩沖區的大小為m有n1個發送進程A1….An1有n2個接收進程B1…Bn2設有n2個信號量Sin[n2]初值均為m設有n2個信號量Sout[n2]初值均為0Bi：while(1){

wait(Sout[i]);

wait(mutex);

從緩沖區取數

signal(mutex);signal(Sin[i]);};Aj:while(1){for(i=1;i<=n2;i++)

wait(Sin[i]);

wait(mutex); 將數據放入緩沖區

signal(mutex);

for(i=1;i<=n2;i++) signal(Sout[2]);}【例題5】復印室里有一個操作員為顧客復印資料，有5把椅子供顧客休息等待復印。如果沒有顧客，則操作員休息。當顧客來到復印室時，如果有空椅子則坐下來，并喚醒復印操作員；如果沒有空椅子則必須離開復印室。

信號量：customers表示正在等待復印的顧客數量（不包括正在復印的顧客）operator記錄正在等候顧客的操作員數，只有1和0mutex用于對waiting的訪問;變量：

waiting表示等待的顧客數量。它實際上是customers的一個副本。之所以使用waiting是因為無法讀取信號量的當前值。semaphorecustomers=0,operator=0,mutex=1;waiting=0；processoperator()//操作員進程{while(1){wait(customers);//等待顧客到來復印；signal(operator);//通知顧客已經完成復印}}processcusotmeri()//顧客進程i{wait(mutex);if(waiting<5){waiting++;signal(customers);signal(