互斥算法.doc

用wait,signal操作解决进程的同步和互斥问题,绝大部分题目可以按以下步骤解决:⑴根据题目要求将每个进程的执行过程一步一步描述出来;⑵分析每个进程每一步的执行条件,将条件一一记录;⑶比较各个条件,将同一条件归为一个,设置一个信号量表示;注意:这里是做题,不是实现系统,所以若某个条件题目中没有加以说明或限制,则删除;⑷设置信号量初值:若信号量是代表某种资源,则为系统初始时的可使用的资源数或可使用资源的进程数,若为互斥则为“1”;⑸重新分析每个进程的每个步骤:若该步骤有执行条件涉及信号量A,则在该步骤语句前加入wait(A);若该步骤有执行后某个信号量B会增值,则在该步骤语句后加入signal(B);注意:若某个步骤前同时有几个wait操作,则一般同步(合作)信号量在前,互斥信号量在后;⑹题目已经做完,最后检查各个进程是否能按题目要求并发执行,若可以,停止;若不可以,检查上述过程,查找错误。1、a,b两点之间是一段东西向的单行车道,现要设计一个自动管理系统,管理规则如下:当ab之间有车辆在行驶时同方向的车可以同时驶入ab段,但另一方向的车必须在ab段外等待;当ab之间无车辆在行驶时,到达a点(或b点)的车辆可以进入ab段,但不能从a点和b点同时驶入,当某方向在ab段行驶的车辆驶出了ab段且暂无车辆进入ab段时,应让另一方向等待的车辆进入ab段行驶。请用信号量为工具,对ab段实现正确管理以保证行驶安全。SemaphoreSab=1,Sba=1,S=1;intab=ba=0;()voidPab{while(1){wait(Sab);if(ab==0)wait(S);ab=ab+1;signal(Sab);车辆从a点驶向b点;wait(Sab);ab=ab-1;if(ab==0)signal(S);signal(Sab);}}()voidPba{while(1){wait(Sba);if(ba==0)wait(S);ba=ba+1;signal(Sba);车辆从b点驶向a点;wait(Sba);ba=ba-1;if(ba==0)signal(S);signal(Sba);}}main(){cobegin{();PabPba();}}2、桌子上有一只盘子,每次只能放一只水果。爸爸专向盘子中放苹果,妈妈专向盘子中放橘子,一个儿子专等吃盘子中的橘子,一个女儿专等吃盘子中的苹果。用PV操作实现他们之间的同步机制。SemaphoreS=1,S1=S2=0;voidfather(){while(1){准备苹果;wait(S);将苹果放在盘子内;signal(S1);}}voidmother(){while(1){准备橘子;wait(S);将橘子放在盘子内;signal(S2);}}voiddaughter(){while(1){wait(Sl);从盘子里拿走苹果;signal(S);吃苹果;}}voidson(){while(1){wait(S2);从盘子里拿走橘子;signal(S);吃橘子;}}main(){cobegin{father();mother();daughter();son();}3、司机与售票员问题请用自然语言描述司机与售票员之间的同步关系,并用信号量给出同步算法司机与售票员的活动程序如下:司机:售票员:L:车在行进中;M:买票;停车;开门;开车;关门;gotoL;gotoM;分析:在汽车行驶过程中,司机活动与售票员活动之间的同步关系为:售票员关车门后,向司机发开车信号,司机接到开车信号后启动车辆,在汽车正常行驶过程中售票员售票,到站时司机停车,售票员在车停后开车门让乘客下车。因此司机启动车辆的动作必须与售票员关车门的动作取得同步;售票员开车门的动作也必须与司机停车取得同步。在本题中,设置两个信号量:S1、S2,S1表示是否允许司机启动汽车,其初值为0;S2表示是否允许售票员开门,其初值为0。答:则该问题描述如下:SemaphoereS1=S2=0;voidDriver(){while(1){wait(S1);启动车辆;正常行车;到站停车;signal(S2);}}voidBusman(){while(1){关车门;signal(S1);售票;wait(S2);开车门;}}main(){cobegin{Driver();Busman();}}1、嗜睡的理发师问题:一个理发店由一个有N张沙发的等候室和一个放有一张理发椅的理发室组成。没有顾客要理发时,理发师便去睡觉。当一个顾客走进理发店时,如果所有的沙发都已经占用,他便离开理发店;否则,如果理发师正在为其他顾客理发,则该顾客就找一张空沙发坐下等待;如果理发师因无顾客正在睡觉,则由新到的顾客唤醒理发师为其理发。在理发完成后,顾客必须付费,直到理发师收费后才能离开理发店,试用信号