操作系统第4章 习题课

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;

本文来源：https://www.bwwdw.com/article/ctkg.html