互斥和同步练习题

1、互斥和同步练习题例例1.1.在一个仅允许单向行驶的单排车道十字路口，只允许车在一个仅允许单向行驶的单排车道十字路口，只允许车辆从南向北和从西向东行驶，如图辆从南向北和从西向东行驶，如图8.18.1所示；为了安全起见，所示；为了安全起见，每次仅允许一辆汽车通过十字路口；当有车辆通过路口时其每次仅允许一辆汽车通过十字路口；当有车辆通过路口时其它车辆必须等待，当无车辆在路口行驶时则一次仅允许一辆它车辆必须等待，当无车辆在路口行驶时则一次仅允许一辆汽车通过。请用汽车通过。请用P P、V V原语及信号量实现十字路口的交通控制原语及信号量实现十字路口的交通控制系统，并描述具体的控制算法。系统，并描述具体的

2、控制算法。 北东 图图1 1 允许单向行驶的单排车道十字路口允许单向行驶的单排车道十字路口设一信号量设一信号量semsem表示是否允许汽车通过，初值为表示是否允许汽车通过，初值为1 1，表示允许汽车，表示允许汽车通过。通过。设入口检测进程设入口检测进程procedureinprocedurein, ,出口检测进程出口检测进程procedureoutprocedureout，它们，它们的描述如下：的描述如下：procedureinprocedurein（）（） beginbegin L1: L1:检测到有一辆车要进入路口检测到有一辆车要进入路口 P(semP(sem) ) 允许进入路口允许进入路

3、口 gotogoto L1 L1 end endprocedureoutprocedureout（）（） beginbegin L2: L2:检测到有一辆车驶出路口检测到有一辆车驶出路口 V(semV(sem) ) goto goto L2 L2 end end例例2 2：设存在三个过程：设存在三个过程getget、copycopy和和putput分别对缓冲区分别对缓冲区S S和和T T进进行操作，其中行操作，其中getget负责将数据块存入缓冲区负责将数据块存入缓冲区S S，copycopy负责从缓负责从缓冲区冲区S S读出数据并复制到缓冲区读出数据并复制到缓冲区T T中，中，putput负

4、责从缓冲区负责从缓冲区T T中读中读出数据并打印，如图出数据并打印，如图2 2所示。请用所示。请用P P、V V操作描述上述三个过操作描述上述三个过程。程。 getgetcopycopyputput缓冲区缓冲区S S缓冲区缓冲区T T图图2 2 输入输入缓冲缓冲输出问题输出问题解：设信号量解：设信号量SGCSGC表示缓冲区表示缓冲区S S是否允许放数据，值为是否允许放数据，值为1 1时表示允许，初值为时表示允许，初值为1 1； 信号量信号量SCGSCG表示缓冲区表示缓冲区S S是否允许取数据，值为是否允许取数据，值为1 1时表示允许，初值为时表示允许，初值为0 0； 信号量信号量SCPSCP表

5、示缓冲区表示缓冲区T T是否允许放数据，值为是否允许放数据，值为1 1时表示允许，初值为时表示允许，初值为1 1； 信号量信号量SPCSPC表示缓冲区表示缓冲区T T是否允许取数据，值为是否允许取数据，值为1 1时表示允许，初值为时表示允许，初值为0 0。 get（）begin L1：取存入缓冲区S的数据x P（SGC） 把数据x存入缓冲区S中 V（SCG） goto L1endcopy（）begin L2： P（SCG） 把缓冲区S的数据存入x中 V（SGC） P（SCP） 把数据x要存入缓冲区T中 V（SPC） goto L2endput（）begin L3：P（SPC） 把缓冲区T的数据

6、存入x中 V（SCP） 打印数据x goto L3end例例3 3：试用信号灯与：试用信号灯与PVPV操作实现司机与售票员之间的同步问操作实现司机与售票员之间的同步问题。设公共汽车上有一个司机和一个售票员，司机负责驾驶题。设公共汽车上有一个司机和一个售票员，司机负责驾驶汽车，售票员负责开关车门，他们之间必须协同工作。一方汽车，售票员负责开关车门，他们之间必须协同工作。一方面售票员关好车门并通知司机后，司机才能开车；另一方面，面售票员关好车门并通知司机后，司机才能开车；另一方面，司机将车停稳并通知售票员后，售票员才能打开车门上下乘司机将车停稳并通知售票员后，售票员才能打开车门上下乘客。客。 例例

7、4 4：公交车上司机负责驾驶汽车，而售票员：公交车上司机负责驾驶汽车，而售票员负责开关车门，他们之间必须协同工作。一方负责开关车门，他们之间必须协同工作。一方面售票员关好车门并通知司机后，司机才能开面售票员关好车门并通知司机后，司机才能开车；另一方面，司机将车停稳并通知售票员后，车；另一方面，司机将车停稳并通知售票员后，售票员才能打开车门上下乘客。假设某辆公交售票员才能打开车门上下乘客。假设某辆公交车上有一名司机和两名售票员，每个售票员各车上有一名司机和两名售票员，每个售票员各负责一个车门，请设适当的信号量，并用负责一个车门，请设适当的信号量，并用P P、V V原语描述他们的同步过程。原语描述

8、他们的同步过程。例例4 4：公交车上司机负责驾驶汽车，而售票员：公交车上司机负责驾驶汽车，而售票员负责开关车门，他们之间必须协同工作。一方负责开关车门，他们之间必须协同工作。一方面售票员关好车门并通知司机后，司机才能开面售票员关好车门并通知司机后，司机才能开车；另一方面，司机将车停稳并通知售票员后，车；另一方面，司机将车停稳并通知售票员后，售票员才能打开车门上下乘客。假设某辆公交售票员才能打开车门上下乘客。假设某辆公交车上有一名司机和两名售票员，每个售票员各车上有一名司机和两名售票员，每个售票员各负责一个车门，请设适当的信号量，并用负责一个车门，请设适当的信号量，并用P P、V V原语描述他们

9、的同步过程。原语描述他们的同步过程。解：设信号量解：设信号量dooropendooropen表示是否允许开门，值为表示是否允许开门，值为1 1时时表示是允许开门，初值为表示是允许开门，初值为0 0；doorclose1doorclose1表示前们是表示前们是否关上；值为否关上；值为1 1时表示已关上，初值为时表示已关上，初值为1 1；doorclose2doorclose2表示后们是否关上；值为表示后们是否关上；值为1 1时表示已关上，初值为时表示已关上，初值为1 1； driver() begin L1:开车 停车 V（dooropen） 等待 P（doorclose1） P（doorclo

10、se2） 启动车辆 goto L1 end司机和两名售票员所司机和两名售票员所对应的进程描述如下：对应的进程描述如下：tackiter1() begin L2:售票售票 P（dooropen） 等待乘客上车等待乘客上车 关车门关车门 V（doorclose1） goto L2 endtackiter2() begin L3:售票售票 P（dooropen） 等待乘客上车等待乘客上车 关车门关车门 V（doorclose2） goto L3 end例例6 6：设一个理发店内有：设一个理发店内有n n张椅子和一个理发师（及其理发椅张椅子和一个理发师（及其理发椅和理发工具）。当一个顾客走进理发店时，

11、若供等候的椅子和理发工具）。当一个顾客走进理发店时，若供等候的椅子已坐满人，则离开。若有空座位则进入理发店，此时若理发已坐满人，则离开。若有空座位则进入理发店，此时若理发师正在为他人理发，则他就找一个空座位坐下；若理发师空师正在为他人理发，则他就找一个空座位坐下；若理发师空闲则就要求理发师为他理发。请给出此问题的同步算法。闲则就要求理发师为他理发。请给出此问题的同步算法。 设信号量设信号量chairchair椅子是否有和有多少把椅子空闲，初椅子是否有和有多少把椅子空闲，初值为值为n n表示有表示有n n把椅子可以空闲；把椅子可以空闲；hairdresserhairdresser理发师是理发师是

12、否正在为他人理发，值为否正在为他人理发，值为1 1时表示正在为他人理发，初时表示正在为他人理发，初值为值为0 0；顾客进程描述如下：顾客进程描述如下： customer( )customer( ) begin begin L1: L1: 走进理发店走进理发店 P(chairP(chair) ) P(hairdresser P(hairdresser) ) V(chair V(chair) ) 让理发师为他理发让理发师为他理发 V(hairdresserV(hairdresser) ) goto goto L1 L1 end end例题例题7：A、B两人共同使用一个报箱，该报箱每次仅能容纳两人共

13、同使用一个报箱，该报箱每次仅能容纳一份报纸。一份报纸。A订阅订阅生活报生活报，B订阅订阅晚报晚报，分别由投，分别由投递员递员C和和D投递。请用投递。请用P、V操作描述他们的同步程序操作描述他们的同步程序. 答；设信号量答；设信号量SP，表示信箱是否允许放报纸，值为，表示信箱是否允许放报纸，值为1时表时表示允许放报纸，初值为示允许放报纸，初值为1；信号量；信号量SA，表示信箱中是否有，表示信箱中是否有生活报，值为生活报，值为1时表示有，初值为时表示有，初值为0；信号量；信号量SB，表示信，表示信箱中是否有晚报，值为箱中是否有晚报，值为1时表示有，初值为时表示有，初值为0。例题：例题：A、B两人共同使用一个报箱，该报箱每次仅能两人共同使用一个报箱，该报箱每次仅能容纳一份报纸。容纳一份报纸。A订阅订阅生活报生活报，B订阅订阅晚报晚报，分别由投递员分别由投递员C和和D投递。请用投递。请用P、V操作描述他们的同操作描述他们的同步程序。步程序