第5章作业答案.ppt

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

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

3、 直到另一方向没人继续过桥。”,semaphore T =1, T_x =1,x =0; Person_x() semWait(T_x); x+; if(x =1) semWait(T); semSignal(T_x); pass_bridge(); semWait(T_x); x-; if(x =0) semSignal(T); semSignal(T_x); ,semaphore T_y = 1,y=0; Person_y() semWait(T_y); y+; if(y =1) semWait(T); semSignal(T_y); pass_bridge(); semWait(T_y)

4、; y-; if(y =0) semSignal(T); semSignal(T_y); ,增加x方向人数,增加y方向人数,减少x方向人数,减少y方向人数,题二,a,b 两点间是一段东西走向的单行车道，现要设计一个自动管理系统，管理规则如下： 当ab间有车辆在行驶时同方向的车可以同时驶入ab段，但另一方向的车必须在ab段外等待； 当ab之间无车时，到达a（或b）的车辆可以进入ab段，但不能从a，b点同时驶入； 当某方向在ab段行驶的车辆使出了ab段且无车辆进入ab段时，应让另一方向等待的车辆进入ab段行驶。 请用wait,signal工具对ab段实现正确管理。,semaphore T =1,

5、T_a =1,a =0; Car_a() semWait(T_a); a+; if(a =1) semWait(T); semSignal(T_a); pass_ab(); semWait(T_a); a-; if(a =0) semSignal(T); semSignal(T_a); ,semaphore T_b = 1,b=0; Car_b() semWait(T_b); b+; if(b =1) semWait(T); semSignal(T_b); pass_ab(); semWait(T_b); b-; if(b =0) semSignal(T); semSignal(T_b); ,

6、增加a方向人数,增加b方向人数,减少a方向人数,减少b方向人数,题三,桌子上有一只盘子，最多可容纳两个水果，每次只能放入或取出一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，两个儿子专等吃盘子中的橘子，两个女儿专等吃盘子中的苹果。请用信号量操作来实现爸爸、妈妈、儿子、女儿之间的同步与互斥关系。,分析：该题中要求“每次只能放入或取出一个水果”，所以盘子为临界资源，需要引入一个信号量对盘子进行互斥保护，设为T ，T的初值设为1; 父亲或母亲每次往盘中放入水果前需要判断盘中是否有空余空间，所以需要一个同步信号量empty来表示盘子的余量，若盘中空余空间则放入水果，否则阻塞等待； 每次放入水果后

7、需要增加苹果或橘子的数量，通知儿子或女儿盘中有水果，所以需要同步信号量apple, orange分别用于表示两种水果的余量； 儿子或女儿每次消费一个水果后将相应的水果数量减1，同时增加盘子余量empty,father() whiel(true) seamWait(empty); seamWait(T); put_apple(); seamSignal(apple); seamSignal(T); ,mother() whiel(true) seamWait(empty); seamWait(T); put_orangle(); seamSignal(orangle); seamSignal(T

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

9、; eat_orange(); seamSignal(empty); seamSignal(T); ,放苹果,放橘子,吃苹果,吃橘子,题四,汽车司机与售票员之间必须协同工作: 一方面只有售票员把车门关好了司机才能开车，因此，售票员关好车门应通知司机开车; 另一方面，只有当汽车已经停下，售票员才能开门上下客，故司机停车后应通知售票员，汽车当前正在始发站停车上客， 试用PV操作写出他们的同步过程。,分析：该题中没有涉及互斥访问的临界资源; 司机开车与售票员关门，以及司机停车与售票员开门间存在同步过程； 所以需要引入两组同步集号量: stop用于司机通知售票员车已停好，可以开门； door用于售票员

10、通知司机，门已关好，可以开车。,driver() whiel(true) seamWait(door); driver_car(); stop_car(); seamSignal(stop); ,saler() whiel(true) seamWait(stop); open_door(); close_door(); seamSignal(door); ,seamphore stop = 0; /代表车已停的同步信号量 seamphore door = 1; /代表门已关的同步信号量,发散： 加入“车上乘客在售票员打开后门，从后门依次下车，站上乘客在售票员打开前门后依次上车，前后门一次均只能

11、容一个乘客通过，每次上下车的乘客数量m,n由司机分别在停车后设置。” 分析，除了司机与售票员间的同步信号量stop，door外，现在前后门分别需要引入互斥信号量T_f,T_b分别用于实现前后门的互斥访问，。 此外，每上或每下一个乘客，则相应的乘客数量m,n应递减1，本来需要引入两个互斥信号量对m,n进行保护，但可以将m-或n-放到上下车的过程中，由T_f,T_b进行互斥保护，所以可以减少两个互斥信号量。,driver() whiel(true) seamWait(door); driver_car(); stop_car(); set_m_n(); /设置上下车人数 seamSignal(st

12、op); ,saler() whiel(true) seamWait(stop); open_frontdoor(); open_backdoor(); /T_f,T_b为售票员与乘客间的同步信号 seamSignal(T_f); seamSignal(T_b); /售票员等待乘客上下车完毕 while(m0 | n0); close_frontdoor(); close_backdoor(); seamWait(T_f); seamWait(T_b); seamSignal(door); ,seamphore stop = 0; /代表车已停的同步信号量 seamphore door = 1

13、; /代表门已关的同步信号量 seamphore T_f = T_b = 0; /前后门互斥通过的信号量 int m,n; /分别代表下车和上车的乘客数量,passenger() /此处T_f作为互斥信号(第一个上车乘客兼有与售票员间的同步作用) seamWait(T_f); on_door(); n-; seamSignal(T_f); . /此处T_b作为互斥信号(第一个下车乘客兼有与售票员间的同步作用) seamWait(T_b); off_door(); m-; seamSignal(T_b); ,seamphore stop = 0; /代表车已停的同步信号量 seamphore d

14、oor = 1; /代表门已关的同步信号量 seamphore T_f = T_b = 0; /前后门互斥通过的信号量 int m,n; /分别代表下车和上车的乘客数量,题五,和尚挑水问题：寺庙里有多个小、老和尚，一水缸。小和尚打水，老和尚饮水。水缸容积10桶水，水取自同一水井，水井和水缸每次都只容放入一个桶，桶总数3个。试用P、V操作描述和尚取水、饮水的互斥与同步过程。,要求使用以下信号量： mutex1=mutex2=1; 分别用于实现水井和水缸的互斥empty=10; 水缸的剩余容量 full=0; 水缸的剩余水量 count=3;水桶个数,分析：需要互斥访问的资源有：水缸，水井，水桶，

15、对应的互斥信号量及初值为 seamphore T_g = 1; /水缸 seamphore T_j = 1; /水井 seamphore T_t = 3; /水桶 需要同步的信号有：水缸的剩余容量(有剩余容量小和尚才可以往缸里装水)，水缸的剩余水量(有剩余水量老和尚才可以从缸里取水) seamphore T_empty = 10; /剩余容量 seamphore T_water = 0; /剩余水量,young_monk() whiel(true) seamWait(T_empty); seamWait(T_t); seamWait(T_j); get_water(); seamSignal(

16、T_j); seamWait(T_g); put_water(); seamSignal(T_g); seamSignal(T_t); seamSignal(T_water); ,old_monk() whiel(true) seamWait(T_water); seamWait(T_t); seamWait(T_g); drink_water(); seamSignal(T_g); seamSignal(T_t); seamSignal(T_empty); ,seamphore T_g = 1; /水缸 seamphore T_j = 1; /水井 seamphore T_t = 3; /水

17、桶 seamphore T_empty = 10; /剩余容量 seamphore T_water = 0; /剩余水量,水井取水,水缸存水,水缸取水,题六,假设后街有家理发店，店里有一个理发师、一把理发椅和n把等候理发的顾客椅子。 （1）如果没有顾客则理发师便在理发椅上睡觉；（2）当有一个顾客到达时，若理发师在睡觉则叫醒理发师，然后理发；如果理发师正在理发，且有空的椅子可坐，则坐下等待，如果没有，则离开；（3）理发师为一位顾客理完发后，如有人等待则唤醒一位为其理发，如没有则睡觉。 试用PV操作实现上述 同步与互斥过程,分析：需要互斥访问的资源有： 顾客人数，对应的互斥信号量及初值为 seam

18、phore mutex = 0; /对顾客人数进行互斥保护 需要同步的信号有： 理发师叫醒信号量(有至少一个顾客时理发时才清醒)， 客人开始理发(理发师服务完一个客人后，通知等待的客人) seamphore wakeup= 0; /同步叫醒 seamphore cuthair = 0; /同步理发,barber() whiel(true) /睡觉 seamWait(wakeup); while(m0) cut_hair(); /理发； semWait(mutex); m-; semSignal(mutex); if m 0 then semSignal(cuthair); ,customer(

19、) if m = n +1 then exit; semWait(mutex); m+; semSignal(mutex); /第一位顾客唤醒理发 if m =1 then semSignal(wakeup); else semWait (cuthair); cut_hair(); /理发； ,seamphore mutex = 1; /互斥 seamphore wakeup = 0; /同步叫醒 seamphore cuthair = 0; /同步理发 Int m = 0; /当前总顾客人数,减少顾客人数,通知顾客理发,增加顾客人数,barber() whiel(true) /睡觉 seam

20、Wait(wakeup); while(m0) cut_hair(); /理发； semWait(mutex); m-; semSignal(mutex); if m 0 then semSignal(cuthair); ,customer() if m = n +1 then exit; semWait(mutex); m+; /第一位顾客唤醒理发 if m =1 then semSignal(wakeup); else semWait (cuthair); semSignal(mutex); cut_hair(); /理发； ,seamphore mutex = 1; /互斥 seamphore wakeup = 0; /同步叫醒 seamphore cuthair = 0; /同步理发 Int m = 0; /当前总顾客人数,减少顾客人数,通知顾客理发,增加顾客人数,barber() whiel(true) /睡觉 seamWait(wakeup); while(m0) cut_hair(); /理发； semWait(mutex); m-; semSignal(mutex); if m 0 then semSignal(cuthair); ,customer() if m = n +1 then exit; semWait(mutex);