操作系统第4章习题课.docx

P127
三、应用题：

　　1．另一个经典同步问题：吸烟者问题（patal,1971）。三个吸烟者在一间房间内，还有一个香烟供应者。为了制造并抽掉香烟，每个吸烟者需要三样东西：烟草、纸和火柴。供应者有丰富的货物提供。三个吸烟者中，第一个有自己的烟草，第二个有自己的纸，第三个有自己的火柴。供应者将两样东西放在桌子上，允许一个吸烟者进行对健康不利的吸烟。当吸烟者完成吸烟后唤醒供应者，供应者再放两样东西（随机地）在桌面上，然后唤醒另一个吸烟者。试采用信号量和P、V操作编写他们同步工作的程序。
　　问题分析：
　　供应者seller随即产生两样东西，提供它们，这里用普通变量来表示
　　吸烟者进程smoker根据其排号不同，拥有不同的一件东西。假设1号吸烟者拥有烟草tobacco，2号吸烟者拥有纸paper，3号吸烟者拥有火柴match。其他号码错误返回。
　　吸烟者的序号代表他们拥有的东西，用他们的序号和供应者产生的两样东西比较，如果都不相等，则说明他拥有的东西和供应者产生的东西匹配，它可以吸烟。如果其中一个相等，则退出，继续排队。
　　mutex信号量代表一个只能进入的门，每次只有一个吸烟者可以进入进行比较和吸烟。
　　每个吸烟者在吸烟完毕之后出门之前要叫醒供应者，调用seller进程。

　　var s, S1, S2, S3; semaphore;
　　S:=1; S1:=S2:=S3:=0;
　　fiag1,flag2,fiag3:Boolean;
　　fiag1:=flag2:=flag3:=true;
　　cobegin
　　 process 供应者
　　begin
　　repeat
　　 P(S);
　　取两样香烟原料放桌上，由flagi标记；
　　 //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．在一个盒子里，混装了数量相等的围棋白子和黑子，现在要用自动分拣系统把白子和黑子分开。该系统设有两个进程P1和P2，其中P1拣白子，P2拣黑子。规定每个进程每次只拣一子，当一进程正在拣子时，不允许另一个进程去拣，当一进程拣了一子时，必须让另一进程去拣，试写出两个并发进程能正确执行的算法。
分析：实质上是两个进程的同步问题，设信号量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）领班：接受顾客点菜（2）厨师：准备顾客的饭菜（3）打包工：将做好的饭菜打包（4）出纳员：收款并提交食品。
分析：将这四类职员看成四类进程P1，P2，P3，P4，然后四类进程对两个变量进行操作，s1是点菜数量，s2是每道菜的状态，其值0表示菜做好，1表示菜做好了
具体解答：
定义三个信号量：
s1——点菜数量，初始值为0;
s2——菜的状态，初始值为0;
s3——包装状态，初始值为0;
领班进程：
while(true){
顾客点菜;
v（s1）; //此时表示有人点菜了
}
厨师进程：
while(true){
p（s1）; //保证有人点菜之后才会准备菜
准备饭菜;
v（s2）;
}
打包工进程：
while(true){
p(s2); //保证厨师做好饭菜才能准备包装
包装好饭菜;
v(s3);
}
出纳员进程：
while(true){
p(s3); //保证包装好才能出纳
收款并提交食品；
｝
如果考虑到必须完成一个顾客订单之后，才能接下一位顾客订单的话，那就可以增加一个控制变量s4(初始值为0)，在领班进程开始时，即“顾客点菜”之前进行v(s4)操作，在出纳员进程中增加v(s4)操作即可。
4．设有三组进程Pi、Qj、Rk,其中Pi、Qj构成一对生产者和消费者，共享一个由M1个缓冲区构成的循环缓冲池buf1。Qj、Rk构成另一对生产者和消费者，共享一个由M2个缓冲区构成的循环缓冲池buf2。如果Pi每次生产一个产品投入buf1，Qj每次从中取两个产品组装后成一个并投入buf2，Rk每次从中取三个产品包装出厂。试用信号量和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．某一游览胜地,有一天然隧道,隧道内只允许一人通过。为使双方游人都有机会通过,规定当同一方向经过一人后就交替地改变方向，让另一个游人通过，要想进入隧道的人在隧道口排队等待，试用信号量与P、V操作编写游人到达隧道口，通过隧道并从另一端隧道口离开的程序。
将隧道的两个方向分别标记为A和B；并设置三个初值都1信号量：SA用来实现对从A到B通行，SB用来实现从B到A通行，mutex用来实现两个方向的行人对隧道的互斥使用。则具体描述如下：
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三个进程共享一个表格，P1对F只读不写，P2对F只写不读，P3对F先读后写。进程可同时读F，但有进程写时，其他进程不能读和写。用(1)信号量和P、V操作编写三进程能正确工作的程序。
分析：这是读--写者问题的变种。其中，P3既是读者又是写者。读者与写者之间需要互斥，写者与写者之间需要互斥，为提高进程运行的并发性，可让读者尽量优先。
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
，