2022年操作系统第章习题课 .pdf

P127 三、应用题：1另一个经典同步问题：吸烟者问题（patal,1971） 。三个吸烟者在一间房间内，还有一个香烟供应者。为了制造并抽掉香烟，每个吸烟者需要三样东西：烟草、纸和火柴。供应者有丰富的货物提供。三个吸烟者中，第一个有自己的烟草，第二个有自己的纸，第三个有自己的火柴。供应者将两样东西放在桌子上，允许一个吸烟者进行对健康不利的吸烟。 当吸烟者完成吸烟后唤醒供应者，供应者再放两样东西 （随机地）在桌面上，然后唤醒另一个吸烟者。 试采用信号量和P、V 操作编写他们同步工作的程序。问题分析：供应者 seller 随即产生两样东西，提供它们，这里用普通变量来表示吸烟者进程 smoker 根据其排号不同，拥有不同的一件东西。假设 1 号吸烟者拥有烟草tobacco，2 号吸烟者拥有纸paper，3 号吸烟者拥有火柴 match。其他号码错误返回。吸烟者的序号代表他们拥有的东西， 用他们的序号和供应者产生的两样东西比较， 如果都不相等， 则说明他拥有的东西和供应者产生的东西匹配，它可以吸烟。如果其中一个相等，则退出，继续排队。mutex 信号量代表一个只能进入的门，每次只有一个吸烟者可以进入进行比较和吸烟。每个吸烟者在吸烟完毕之后出门之前要叫醒供应者，调用seller名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 12 页 - - - - - - - - - 进程。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); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 12 页 - - - - - - - - - 取原料；做香烟；V(S); 吸香烟；untile false; end process 吸烟者 2 begin repeat P(S2); 取原料；做香烟；V(S); 吸香烟；untile false; end process 吸烟者 3 begin repeat P(S3); 取原料；做香烟；名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 12 页 - - - - - - - - - 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); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 12 页 - - - - - - - - - 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; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 12 页 - - - - - - - - - s3包装状态，初始值为0; 领班进程：while(true) 顾客点菜 ; v（s1）; / 此时表示有人点菜了 厨师进程：while(true) p（s1）; / 保证有人点菜之后才会准备菜准备饭菜 ; v（s2）; 打包工进程：while(true) p(s2); / 保证厨师做好饭菜才能准备包装包装好饭菜 ; v(s3); 出纳员进程：while(true) p(s3); / 保证包装好才能出纳收款并提交食品；名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 12 页 - - - - - - - - - 如果考虑到必须完成一个顾客订单之后，才能接下一位顾客订单的话，那就可以增加一个控制变量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:array0M1-1 of item ; buffer2:array0M2-1of item ; empty1:=M1 ; empty:=M2; in1 : = in2 :=out1:=out2:=0 ; counter1:=counter2:=0 ; fun1:=full2:mutex1:=mutex2:=mutex3:=1; cobegin process Pi 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 12 页 - - - - - - - - - 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 buffer1out1; out1:=(out1+1) mod M1; take an item from buffer1out1 ; out1:=(out1 + 1) mod M1 ; V ( mutex1 ) ; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 12 页 - - - - - - - - - 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 ; processRkbegin 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 ; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 12 页 - - - - - - - - - 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); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 12 页 - - - - - - - - - P(Mutex); 过隧道；V(mutex); V(SB); endprocess 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 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 12 页 - - - - - - - - - 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 P3begin 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 ，名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 12 页 - - - - - - - - -