互斥和同步练习题.ppt

1、互斥和同步练习题,例1.在一个仅允许单向行驶的单排车道十字路口，只允许车辆从南向北和从西向东行驶，如图8.1所示；为了安全起见，每次仅允许一辆汽车通过十字路口；当有车辆通过路口时其它车辆必须等待，当无车辆在路口行驶时则一次仅允许一辆汽车通过。请用P、V原语及信号量实现十字路口的交通控制系统，并描述具体的控制算法。,设一信号量sem表示是否允许汽车通过，初值为1，表示允许汽车通过。 设入口检测进程procedurein,出口检测进程procedureout，它们的描述如下： procedurein（） begin L1:检测到有一辆车要进入路口 P(sem) 允许进入路口 goto L1 end

2、 procedureout（） begin L2:检测到有一辆车驶出路口 V(sem) goto L2 end,例2：设存在三个过程get、copy和put分别对缓冲区S和T进行操作，其中get负责将数据块存入缓冲区S，copy负责从缓冲区S读出数据并复制到缓冲区T中，put负责从缓冲区T中读出数据并打印，如图2所示。请用P、V操作描述上述三个过程。,解：设信号量SGC表示缓冲区S是否允许放数据，值为1时表示允许，初值为1； 信号量SCG表示缓冲区S是否允许取数据，值为1时表示允许，初值为0； 信号量SCP表示缓冲区T是否允许放数据，值为1时表示允许，初值为1； 信号量SPC表示缓冲区T是否允

3、许取数据，值为1时表示允许，初值为0。,get（） begin L1：取存入缓冲区S的数据x P（SGC） 把数据x存入缓冲区S中 V（SCG） goto L1 end,copy（） begin L2： P（SCG） 把缓冲区S的数据存入x中 V（SGC） P（SCP） 把数据x要存入缓冲区T中 V（SPC） goto L2 end,put（） begin L3：P（SPC） 把缓冲区T的数据存入x中 V（SCP） 打印数据x goto L3 end,例3：试用信号灯与PV操作实现司机与售票员之间的同步问题。设公共汽车上有一个司机和一个售票员，司机负责驾驶汽车，售票员负责开关车门，他们之间必须

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

5、票员才能打开车门上下乘客。假设某辆公交车上有一名司机和两名售票员，每个售票员各负责一个车门，请设适当的信号量，并用P、V原语描述他们的同步过程。 解：设信号量dooropen表示是否允许开门，值为1时表示是允许开门，初值为0；doorclose1表示前们是否关上；值为1时表示已关上，初值为1；doorclose2表示后们是否关上；值为1时表示已关上，初值为1；,driver() begin L1:开车 停车 V（dooropen） 等待 P（doorclose1） P（doorclose2） 启动车辆 goto L1 end,司机和两名售票员所 对应的进程描述如下：,tackiter1() b

6、egin L2:售票 P（dooropen） 等待乘客上车 关车门 V（doorclose1） goto L2 end,tackiter2() begin L3:售票 P（dooropen） 等待乘客上车 关车门 V（doorclose2） goto L3 end,例6：设一个理发店内有n张椅子和一个理发师（及其理发椅和理发工具）。当一个顾客走进理发店时，若供等候的椅子已坐满人，则离开。若有空座位则进入理发店，此时若理发师正在为他人理发，则他就找一个空座位坐下；若理发师空闲则就要求理发师为他理发。请给出此问题的同步算法。,设信号量chair椅子是否有和有多少把椅子空闲，初值为n表示有n把椅子可

7、以空闲；hairdresser理发师是否正在为他人理发，值为1时表示正在为他人理发，初值为0；,顾客进程描述如下： customer( ) begin L1: 走进理发店 P(chair) P(hairdresser) V(chair) 让理发师为他理发 V(hairdresser) goto L1 end,例题7：A、B两人共同使用一个报箱，该报箱每次仅能容纳一份报纸。A订阅生活报，B订阅晚报，分别由投递员C和D投递。请用P、V操作描述他们的同步程序.,答；设信号量SP，表示信箱是否允许放报纸，值为1时表示允许放报纸，初值为1；信号量SA，表示信箱中是否有生活报，值为1时表示有，初值为0；信号量SB，表示信箱中是否有晚报，值为1时表示有，初值为0。,例题：A、B两人共同使用一个报箱，该报箱每次仅能容纳一份报纸。A订阅生活报，B订阅晚报，分别由投递员C和D投递。请用P、V操作描述他们的同步程序。,A（） begin L3：P(SA) 取生活报 V（SP） goto L3 End,C（） begin L1：P(SP) 把生活报放入报箱 V（SA）