P127

三、應(yīng)用題：

?

　　1．另一個經(jīng)典同步問題：吸煙者問題（patal,1971）。三個吸煙者在一間房間內(nèi)，還有一個香煙供應(yīng)者。為了制造并抽掉香煙，每個吸煙者需要三樣?xùn)|西：煙草、紙和火柴。供應(yīng)者有豐富的貨物提供。三個吸煙者中，第一個有自己的煙草，第二個有自己的紙，第三個有自己的火柴。供應(yīng)者將兩樣?xùn)|西放在桌子上，允許一個吸煙者進(jìn)行對健康不利的吸煙。當(dāng)吸煙者完成吸煙后喚醒供應(yīng)者，供應(yīng)者再放兩樣?xùn)|西（隨機(jī)地）在桌面上，然后喚醒另一個吸煙者。試采用信號量和P、V操作編寫他們同步工作的程序。

　　問題分析：

　　供應(yīng)者seller隨即產(chǎn)生兩樣?xùn)|西，提供它們，這里用普通變量來表示

　　吸煙者進(jìn)程smoker根據(jù)其排號不同，擁有不同的一件東西。假設(shè)1號吸煙者擁有煙草tobacco，2號吸煙者擁有紙paper，3號吸煙者擁有火柴match。其他號碼錯誤返回。

　　吸煙者的序號代表他們擁有的東西，用他們的序號和供應(yīng)者產(chǎn)生的兩樣?xùn)|西比較，如果都不相等，則說明他擁有的東西和供應(yīng)者產(chǎn)生的東西匹配，它可以吸煙。如果其中一個相等，則退出，繼續(xù)排隊。

　　mutex信號量代表一個只能進(jìn)入的門，每次只有一個吸煙者可以進(jìn)入進(jìn)行比較和吸煙。

　　每個吸煙者在吸煙完畢之后出門之前要叫醒供應(yīng)者，調(diào)用seller進(jìn)程。

?

　　var s, S1, S2, S3; semaphore;

　　S:=1; S1:=S2:=S3:=0;

　　fiag1,flag2,fiag3:Boolean;

　　fiag1:=flag2:=flag3:=true;

　　cobegin

　　?process 供應(yīng)者

　　begin

　　repeat

　　?P(S);

　　取兩樣香煙原料放桌上，由flagi標(biāo)記；

　　?//flag1、flag?2、flag?3 代表煙草、紙、火柴

if flag2&flag3 then V(S1); //供紙和火柴

　　?else if flag1&fiag3 then V(S2); //供煙草和火柴

　　?else V(S3); //供煙草和紙

　　untile false;

　　end

　　?process吸煙者1

　　begin

　　repeat

　　P(S1);

　　取原料；

　　做香煙；

　　?V(S);

　　吸香煙；

　　untile false;

　　end

　　?process吸煙者2

　　begin

　　repeat

P(S2);

　　取原料；

　　做香煙；

　　?V(S);

　　吸香煙；

　　untile false;

　　end

　　?process吸煙者3

　　begin

　　repeat

　　P(S3);

　　取原料；

　　做香煙；

　　V(S);

　　吸香煙；

　　untile false;

　　end

　　coend

2．在一個盒子里，混裝了數(shù)量相等的圍棋白子和黑子，現(xiàn)在要用自動分揀系統(tǒng)把白子和黑子分開。該系統(tǒng)設(shè)有兩個進(jìn)程P1和P2，其中P1揀白子，P2揀黑子。規(guī)定每個進(jìn)程每次只揀一子，當(dāng)一進(jìn)程正在揀子時，不允許另一個進(jìn)程去揀，當(dāng)一進(jìn)程揀了一子時，必須讓另一進(jìn)程去揀，試寫出兩個并發(fā)進(jìn)程能正確執(zhí)行的算法。

分析：實(shí)質(zhì)上是兩個進(jìn)程的同步問題，設(shè)信號量S1和S2分別表示可揀白子和黑子，不失一般性，若令先揀白子。

var ?S1,S2:semaphore;

S1:=1;S2:=0;

Cobegin

{

process P1

begin

repeat

P(S1);

揀白子

V(S2);

until false;

end

process P2

begin

repeat

P(S2);

揀黑子

V(S1);

until false;

end

}

coend.

3、一個餐廳有4類職員：（1）領(lǐng)班：接受顧客點(diǎn)菜（2）廚師：準(zhǔn)備顧客的飯菜（3）打包工：將做好的飯菜打包（4）出納員：收款并提交食品。

分析：將這四類職員看成四類進(jìn)程P1，P2，P3，P4，然后四類進(jìn)程對兩個變量進(jìn)行操作，s1是點(diǎn)菜數(shù)量，s2是每道菜的狀態(tài)，其值0表示菜做好，1表示菜做好了

具體解答：

定義三個信號量：

s1——點(diǎn)菜數(shù)量，初始值為0;

s2——菜的狀態(tài)，初始值為0;

s3——包裝狀態(tài)，初始值為0;

領(lǐng)班進(jìn)程：

while(true){

顧客點(diǎn)菜;

v（s1）; ?????//此時表示有人點(diǎn)菜了

}

廚師進(jìn)程：

while(true){

p（s1）; ?????//保證有人點(diǎn)菜之后才會準(zhǔn)備菜
準(zhǔn)備飯菜;

v（s2）;

}
打包工進(jìn)程：

while(true){

p(s2); ??????//保證廚師做好飯菜才能準(zhǔn)備包裝

包裝好飯菜;

v(s3);

}

出納員進(jìn)程：

while(true){

p(s3); ????//保證包裝好才能出納

收款并提交食品；

｝

如果考慮到必須完成一個顧客訂單之后，才能接下一位顧客訂單的話，那就可以增加一個控制變量s4(初始值為0)，在領(lǐng)班進(jìn)程開始時，即“顧客點(diǎn)菜”之前進(jìn)行v(s4)操作，在出納員進(jìn)程中增加v(s4)操作即可。

4．設(shè)有三組進(jìn)程Pi、Qj、Rk,其中Pi、Qj構(gòu)成一對生產(chǎn)者和消費(fèi)者，共享一個由M1個緩沖區(qū)構(gòu)成的循環(huán)緩沖池buf1。Qj、Rk構(gòu)成另一對生產(chǎn)者和消費(fèi)者，共享一個由M2個緩沖區(qū)構(gòu)成的循環(huán)緩沖池buf2。如果Pi每次生產(chǎn)一個產(chǎn)品投入buf1，Qj每次從中取兩個產(chǎn)品組裝后成一個并投入buf2，Rk每次從中取三個產(chǎn)品包裝出廠。試用信號量和P、V操作寫出它們同步工作的程序。

var mutex1 , mutex2 , mutex3 : semaphore;

empty1 , empty2 , full1 , full2 ; semaphore ;

　　in1 , in2 , out1 , out2 : integer ; counter1 , counter2:integer ;

　　buffer1:array[0…M1-1] of item ; buffer2:array[0…M2-1]of item ;

　　empty1:=M1 ; empty:=M2;

　　in1 : = in2 :=out1:=out2:=0 ; counter1:=counter2:=0 ;

　　fun1:=full2:＝mutex1:=mutex2:=mutex3:=1;

　　cobegin

　　{

　　process Pi

　　begin
　　L1:

　　P(empty1) ;

　　P(mutex1 ) ;

　　put an item into buffer [in1] ;

　　in1:=(in1+1) mod M1 ;

　　counter++;

　　if counter1 = 2 then { counter1:=0;V(full1);}

　　V(mutex) ;

　　goto L1;

　　end

?

　　processQj

　　begin

　　L2:

　　P ( full2) ;

　　P ( mutex1 ) ;

　　take an item from buffer1[out1];

　　out1:=(out1+1) mod M1;

　　take an item from buffer1[out1] ;

　　out1:=(out1 + 1) mod M1 ;

　　V ( mutex1 ) ;

　　V ( empty1 ) ;

　　V ( empty1 ) ;

　　Process the products ;

　　P ( emPty2) ;

　　P ( mutex2 ) ;

　　put an item into buffer2 [ in2 ] ;

　　in2:=( in2 + l ) mod M2 ;

　　counter2 + + ;

　　if counter2 = 3 then { counter2:=0 ;V( full2 ) ; }

　　V ( mutex2) ;

　　goto L2 ;

　　

processRk

　　begin L3 :

　　P ( full2 ) ;

　　P ( mutex2 ) ;

　　take an item from buffer2 [out2];

　　out2: = ( out2 + 1 ) mod M2 ;

　　take an item from buffer2 [out2] ;

　　out2:=( out2 + 1) mod M2 ;

　　take an item from buffer2 [out2];

　　out2:=(out2 + 1 ) mod M2 ;

　　V( mutex2 ) ;

　　V ( empty2 ) ;

　　V ( empty2 ) ;

　　V ( empty2 ) ;

　　packet the products ;

　　goto L3 ;

　　end

　　}

　　Coend

6．某一游覽勝地,有一天然隧道,隧道內(nèi)只允許一人通過。為使雙方游人都有機(jī)會通過,規(guī)定當(dāng)同一方向經(jīng)過一人后就交替地改變方向，讓另一個游人通過，要想進(jìn)入隧道的人在隧道口排隊等待，試用信號量與P、V操作編寫游人到達(dá)隧道口，通過隧道并從另一端隧道口離開的程序。

將隧道的兩個方向分別標(biāo)記為A和B；并設(shè)置三個初值都1信號量：SA用來實(shí)現(xiàn)對從A到B通行，SB用來實(shí)現(xiàn)從B到A通行，mutex用來實(shí)現(xiàn)兩個方向的行人對隧道的互斥使用。則具體描述如下：

VarSA,SB,mutex:semaphore:=1,0,1;

Begin

Parbegin

　　　process A: begin

　　　　　　　　　P(SA);

　　　　　　　　　P(Mutex);
　　　　　　　　　過隧道；

　　　　　　　　V(mutex);

　　　　　　　????V(SB);

end　　　

process B: begin

　　　　　P(SB)

　　　　　　　　　P(Mutex);
　　　　　　　　　過隧道；

　　　　　　　　V(mutex);

　　　　　　　????V?(SA);

end

7. 有P1、P2、P3三個進(jìn)程共享一個表格，P1對F只讀不寫，P2對F只寫不讀，P3對F先讀后寫。進(jìn)程可同時讀F，但有進(jìn)程寫時，其他進(jìn)程不能讀和寫。用(1)信號量和P、V操作編寫三進(jìn)程能正確工作的程序。

分析：這是讀--寫者問題的變種。其中，P3既是讀者又是寫者。讀者與寫者之間需要互斥，寫者與寫者之間需要互斥，為提高進(jìn)程運(yùn)行的并發(fā)性，可讓讀者盡量優(yōu)先。

varrmutex,wmutex:semaphore;

rmutex:=wmutex:=1; count:integer;count:=0; cobegin {

process P1

begin repeat

P(rmutex);

count:=count+1;

if count=1 then P(wmutex); V(rmutex); Read F; P(rmutex);

count:=count-1;

if count=0 then V(wmutex); V(rmutex); untile false; end

process P2

begin repeat

P(wmutex); Write F; V(wmutex);

untile false;

process P3

begin repeat

P(rmutex);

count:=count+1;

if count=1 then P(wmutex); V(rmutex); Read F; P(rmutex);

count:=count-1;

if count=0 then V(wmutex); V(rmutex); P(wmutex); Write F; V(wmutex); untile false; end }

coend

，