第5章作业答案.ppt

《第5章作业答案.ppt》由会员分享，可在线阅读，更多相关《第5章作业答案.ppt（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第5章作业上交时间:2013年4月16上交到课程网站题一一条小河上有一座独木桥，规定每次只允许一一条小河上有一座独木桥，规定每次只允许一人过桥。如果把每个过桥者看作一个进程，为人过桥。如果把每个过桥者看作一个进程，为保证安全，请用信号量操作实现正确管理。保证安全，请用信号量操作实现正确管理。分析：该题中要求“每次只允许一人过桥每次只允许一人过桥”，所以桥为临界资源，需要引入一个信号量对桥进行互斥保护，设为T。T的初值设为1，每个人过桥前都需要执行P(T)，若T=0，则可以过桥，否则必须等待。过完桥后，需要释放临界资源，让别人过桥。1.semaphore T=1;2.Person()3.4.se

2、mWait(T);5.pass_bridge();6.semSignal(T);7.互斥过桥发散：改为“只要有同方向的人过桥，则可以直接过桥，其余方向的人需要等待，直到另一方向没人继续过桥。”分析，此时桥可以容许某一个方有多人可以同时过桥，桥本身不再属于临界资源，而过桥的优先权属于临界资源，由桥两个方向的人竞争。需要引入一个信号量对过桥优先权进行互斥保护，设为T，T的初值设为1，每个方向第一个人过桥前都需要执行P(T)，若T=1，则可以过桥，否则必须等待。每个方向最后一个人过完桥后，需要释放临界资源T，让别人过桥。此外，还应有两个全局变量x,y分别保存两个方向上的过桥人数，以及两个信号量T_x

3、,T_y分别用于对x和y的互斥访问。发散：改为“只要有同方向的人过桥，则可以直接过桥，其余方向的人需要等待，直到另一方向没人继续过桥。”1.semaphore T=1,T_x=1,x=0;2.Person_x()3.4.semWait(T_x);5.x+;6.if(x=1)7.semWait(T);8.semSignal(T_x);9.pass_bridge();10.semWait(T_x);x-;11.if(x=0)semSignal(T);semSignal(T_x);12.1.semaphore T_y=1,y=0;2.Person_y()3.4.semWait(T_y);5.y+;6

4、.if(y=1)7.semWait(T);8.semSignal(T_y);9.pass_bridge();10.semWait(T_y);y-;11.if(y=0)semSignal(T);semSignal(T_y);12.增加x方向人数增加y方向人数减少x方向人数减少y方向人数题二a,b 两点间是一段东西走向的单行车道，现要设计一个自动管理系统，两点间是一段东西走向的单行车道，现要设计一个自动管理系统，管理规则如下：管理规则如下：当当ab间有车辆在行驶时同方向的车可以同时驶入间有车辆在行驶时同方向的车可以同时驶入ab段，但另一方向段，但另一方向的车必须在的车必须在ab段外等待；段外等待；

5、当当ab之间无车时，到达之间无车时，到达a（或（或b）的车辆可以进入）的车辆可以进入ab段，但不能从段，但不能从a，b点同时驶入；点同时驶入；当某方向在当某方向在ab段行驶的车辆使出了段行驶的车辆使出了ab段且无车辆进入段且无车辆进入ab段时，应让段时，应让另一方向等待的车辆进入另一方向等待的车辆进入ab段行驶。段行驶。请用请用wait,signal工具对工具对ab段实现正确管理。段实现正确管理。1.semaphore T=1,T_a=1,a=0;2.Car_a()3.4.semWait(T_a);5.a+;6.if(a=1)7.semWait(T);8.semSignal(T_a);9.pa

6、ss_ab();10.semWait(T_a);a-;11.if(a=0)semSignal(T);semSignal(T_a);12.1.semaphore T_b=1,b=0;2.Car_b()3.4.semWait(T_b);5.b+;6.if(b=1)7.semWait(T);8.semSignal(T_b);9.pass_ab();10.semWait(T_b);b-;11.if(b=0)semSignal(T);semSignal(T_b);12.增加a方向人数增加b方向人数减少a方向人数减少b方向人数题三桌子上有一只盘子，最多可容纳两个水果，每桌子上有一只盘子，最多可容纳两个水果

7、，每次只能放入或取出一个水果。爸爸专向盘子中次只能放入或取出一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，两个儿子专放苹果，妈妈专向盘子中放橘子，两个儿子专等吃盘子中的橘子，两个女儿专等吃盘子中的等吃盘子中的橘子，两个女儿专等吃盘子中的苹果。请用信号量操作来实现爸爸、妈妈、儿苹果。请用信号量操作来实现爸爸、妈妈、儿子、女儿之间的同步与互斥关系。子、女儿之间的同步与互斥关系。分析：该题中要求“每次只能放入或取出一个水果”，所以盘子为临界资源，需要引入一个信号量对盘子进行互斥保护，设为T，T的初值设为1;父亲或母亲每次往盘中放入水果前需要判断盘中是否有空余空间，所以需要一个同步信号量emp

8、ty来表示盘子的余量，若盘中空余空间则放入水果，否则阻塞等待；每次放入水果后需要增加苹果或橘子的数量，通知儿子或女儿盘中有水果，所以需要同步信号量apple,orange分别用于表示两种水果的余量；儿子或女儿每次消费一个水果后将相应的水果数量减1，同时增加盘子余量empty1.father()2.whiel(true)3.seamWait(empty);4.seamWait(T);5.put_apple();6.seamSignal(apple);7.seamSignal(T);8.1.mother()2.whiel(true)3.seamWait(empty);4.seamWait(T);5

9、.put_orangle();6.seamSignal(orangle);7.seamSignal(T);8.seamphore T=1;/保护盘子的互斥信号量seamphore empty=2;/代表盘子容量的同步信号量seamphore apple=0;/代表盘中apple数量的同步信号量seamphore orange=0;/代表盘中orange数量的同步信号量1.daughter()2.whiel(true)3.seamWait(apple);4.seamWait(T);5.eat_apple();6.seamSignal(empty);7.seamSignal(T);8.1.son(

10、)2.whiel(true)3.seamWait(orangle);4.seamWait(T);5.eat_orange();6.seamSignal(empty);7.seamSignal(T);8.放苹果放橘子吃苹果吃橘子题四汽车司机与售票员之间必须协同汽车司机与售票员之间必须协同工作工作:一方面一方面只有售票员把车门关好了司机才能开车，只有售票员把车门关好了司机才能开车，因此，售票员关好车门应通知司机因此，售票员关好车门应通知司机开车开车;另一方面另一方面，只有当汽车已经停下，售票员才能，只有当汽车已经停下，售票员才能开门上下客，故司机停车后应通知售票员，汽开门上下客，故司机停车后应通知

11、售票员，汽车当前正在始发站停车上客车当前正在始发站停车上客，试用试用PVPV操作写出操作写出他们的同步过程。他们的同步过程。分析：该题中没有涉及互斥访问的临界资源;司机开车与售票员关门，以及司机停车与售票员开门间存在同步过程；所以需要引入两组同步集号量:stop用于司机通知售票员车已停好，可以开门；door用于售票员通知司机，门已关好，可以开车。1.driver()2.3.whiel(true)4.5.seamWait(door);6.driver_car();7.stop_car();8.seamSignal(stop);9.10.1.saler()2.3.whiel(true)4.5.se

12、amWait(stop);6.open_door();7.close_door();8.seamSignal(door);9.10.seamphore stop=0;/代表车已停的同步信号量seamphore door=1;/代表门已关的同步信号量发散：加入“车上乘客在售票员打开后门，从后门依次下车，站上乘客在售票员打开前门后依次上车，前后门一次均只能容一个乘客通过，每次上下车的乘客数量m,n由司机分别在停车后设置。”分析，除了司机与售票员间的同步信号量stop，door外，现在前后门分别需要引入互斥信号量T_f,T_b分别用于实现前后门的互斥访问，。此外，每上或每下一个乘客，则相应的乘客数量

13、m,n应递减1，本来需要引入两个互斥信号量对m,n进行保护，但可以将m-或n-放到上下车的过程中，由T_f,T_b进行互斥保护，所以可以减少两个互斥信号量。1.driver()2.3.whiel(true)4.5.seamWait(door);6.driver_car();7.stop_car();8.set_m_n();/设置上下车人数设置上下车人数9.seamSignal(stop);10.11.1.saler()2.3.whiel(true)4.seamWait(stop);5.open_frontdoor();6.open_backdoor();7./T_f,T_b为售票员与乘客间的同

14、步信号为售票员与乘客间的同步信号8.seamSignal(T_f);seamSignal(T_b);9./售票员等待乘客上下车完毕售票员等待乘客上下车完毕10.while(m0|n0);11.close_frontdoor();12.close_backdoor();13.seamWait(T_f);14.seamWait(T_b);15.seamSignal(door);16.seamphore stop=0;/代表车已停的同步信号量seamphore door=1;/代表门已关的同步信号量seamphore T_f=T_b=0;/前后门互斥通过的信号量int m,n;/分别代表下车和上车的

15、乘客数量1.passenger()2.3./此处T_f作为互斥信号(第一个上车乘客兼有与售票员间的同步作用)4.seamWait(T_f);5.on_door();6.n-;7.seamSignal(T_f);8.9./此处T_b作为互斥信号(第一个下车乘客兼有与售票员间的同步作用)10.seamWait(T_b);11.off_door();12.m-;13.seamSignal(T_b);14.seamphore stop=0;/代表车已停的同步信号量seamphore door=1;/代表门已关的同步信号量seamphore T_f=T_b=0;/前后门互斥通过的信号量int m,n;/

16、分别代表下车和上车的乘客数量题五和尚挑水问题：寺庙里有多个小、老和尚，一水缸。和尚挑水问题：寺庙里有多个小、老和尚，一水缸。小和尚打水，老和尚饮水。水缸容积小和尚打水，老和尚饮水。水缸容积1010桶水，水取自桶水，水取自同一水井，水井和水缸每次都只容放入一个桶，桶总同一水井，水井和水缸每次都只容放入一个桶，桶总数数3 3个。试用个。试用P P、V V操作描述和尚取水、饮水的互斥与操作描述和尚取水、饮水的互斥与同步过程。同步过程。要求使用以下信号量：要求使用以下信号量：mumutex1=mutex2=1;tex1=mutex2=1;分别用于实现水井和水缸的互斥分别用于实现水井和水缸的互斥empt

17、y=10;empty=10;水缸的剩余容量水缸的剩余容量full=0;full=0;水缸的剩余水量水缸的剩余水量count=3;count=3;水桶个数水桶个数分析：需要互斥访问的资源有：水缸，水井，水桶，对应的互斥信号量及初值为1.seamphore T_g=1;/水缸2.seamphore T_j=1;/水井3.seamphore T_t=3;/水桶 需要同步的信号有：水缸的剩余容量(有剩余容量小和尚才可以往缸里装水)，水缸的剩余水量(有剩余水量老和尚才可以从缸里取水)1.seamphore T_empty=10;/剩余容量2.seamphore T_water=0;/剩余水量1.youn

18、g_monk()2.3.whiel(true)4.5.seamWait(T_empty);6.seamWait(T_t);7.seamWait(T_j);8.get_water();9.seamSignal(T_j);10.seamWait(T_g);11.put_water();12.seamSignal(T_g);13.seamSignal(T_t);14.seamSignal(T_water);15.16.1.old_monk()2.3.whiel(true)4.5.seamWait(T_water);6.seamWait(T_t);7.seamWait(T_g);8.drink_wat

19、er();9.seamSignal(T_g);10.seamSignal(T_t);11.seamSignal(T_empty);12.13.seamphore T_g=1;/水缸seamphore T_j=1;/水井seamphore T_t=3;/水桶seamphore T_empty=10;/剩余容量seamphore T_water=0;/剩余水量水井取水水缸存水水缸取水题六假设后街有家理发店，店里有一个理发师、一把理发椅和假设后街有家理发店，店里有一个理发师、一把理发椅和n把等候理把等候理发的顾客椅子发的顾客椅子。（1）如果）如果没有顾客则理发师便在理发椅没有顾客则理发师便在理发椅上

20、睡上睡觉觉；（2）当）当有一个顾客到达时有一个顾客到达时，若理发师在睡觉则叫醒理发师，然后理，若理发师在睡觉则叫醒理发师，然后理发发；如果理发师正在理发；如果理发师正在理发，且有空，且有空的椅子可坐的椅子可坐，则坐下，则坐下等待，如果等待，如果没有，则离开；没有，则离开；（3）理发师）理发师为一位顾客理完发后为一位顾客理完发后，如，如有人等待有人等待则则唤醒一位为其理发，唤醒一位为其理发，如如没有则睡觉。没有则睡觉。试用试用PV操作实现上述操作实现上述同步与互斥过程同步与互斥过程分析：需要互斥访问的资源有：顾客人数，对应的互斥信号量及初值为1.seamphore mutex=0;/对顾客人数进

21、行互斥保护需要同步的信号有：理发师叫醒信号量(有至少一个顾客时理发时才清醒)，客人开始理发(理发师服务完一个客人后，通知等待的客人)1.seamphore wakeup=0;/同步叫醒2.seamphore cuthair=0;/同步理发1.barber()2.3.whiel(true)4.5./睡觉6.seamWait(wakeup);7.while(m0)8.9.cut_hair();/理发；理发；10.semWait(mutex);11.m-;12.semSignal(mutex);13.if m 0 then 14.semSignal(cuthair);15.16.1.customer

22、()2.3.if m=n+1 then exit;4.semWait(mutex);5.m+;6.semSignal(mutex);7./第一位顾客唤醒理发8.if m=1 then semSignal(wakeup);9.else semWait(cuthair);10.11.cut_hair();/理发；理发；12.seamphore mutex =1;/互斥seamphore wakeup=0;/同步叫醒seamphore cuthair=0;/同步理发Int m=0;/当前总顾客人数减少顾客人数通知顾客理发增加顾客人数1.barber()2.3.whiel(true)4.5./睡觉6.

23、seamWait(wakeup);7.while(m0)8.9.cut_hair();/理发；理发；10.semWait(mutex);11.m-;12.semSignal(mutex);13.if m 0 then 14.semSignal(cuthair);15.16.1.customer()2.3.if m=n+1 then exit;4.semWait(mutex);5.m+;6.7./第一位顾客唤醒理发8.if m=1 then semSignal(wakeup);9.else semWait(cuthair);10.semSignal(mutex);11.12.cut_hair()

24、;/理发；理发；13.seamphore mutex=1;/互斥seamphore wakeup=0;/同步叫醒seamphore cuthair=0;/同步理发Int m=0;/当前总顾客人数减少顾客人数通知顾客理发增加顾客人数1.barber()2.3.whiel(true)4.5./睡觉6.seamWait(wakeup);7.while(m0)8.9.cut_hair();/理发；理发；10.semWait(mutex);11.m-;12.semSignal(mutex);13.if m 0 then 14.semSignal(cuthair);15.16.1.customer()2.

25、3.if m=n+1 then exit;4.semWait(mutex);5.m+;6.if m=1 then semSignal(wakeup);7.semSignal(mutex);8./第一位顾客才唤醒理发9.if m!=1 then semWait(cuthair);10.11.cut_hair();/理发；理发；12.seamphore mutex=1;/互斥seamphore wakeup=0;/同步叫醒seamphore cuthair=0;/同步理发Int m=0;/当前总顾客人数减少顾客人数通知顾客理发增加顾客人数1.barber()2.3.whiel(true)4.5./

26、睡觉6.seamWait(wakeup);7.while(m0)8.9.cut_hair();/理发；理发；10.semWait(mutex);11.m-;12.13.if m 0 then 14.semSignal(cuthair);15.semSignal(mutex);16.17.1.customer()2.3.int t=0;4.semWait(mutex);5.if m=n+1 then 6.semSignal(mutex);exit;7.end8.m+;9.t=m;10.if m=1 then semSignal(wakeup);11.semSignal(mutex);12.if t!=1 then semWait(cuthair);13.14.cut_hair();/理发；理发；15.seamphore mutex=1;/互斥seamphore wakeup=0;/同步叫醒seamphore cuthair=0;/同步理发Int m=0;/当前总顾客人数减少顾客人数通知顾客理发增加顾客人数