《操作系统练习 同步问题 有答案.doc》由会员分享,可在线阅读,更多相关《操作系统练习 同步问题 有答案.doc(11页珍藏版)》请在金锄头文库上搜索。
1、操作系统练习题:天大1 在南开大学和天津大学之间有一条弯曲的小路,其中从S到T一段路每次只允许一辆自行车通过,但中间有一个小的“安全岛”M(同时允许两辆自行车停留),可供两辆自行车已从两端进小路情况下错车使用,如图所示。试设计一个算法使来往的自行车均可顺利通过。TMKLS南开解答:首先中间的安全岛M仅允许两辆自行车通过,应作为临界资源设置信号量。但仔细分析发现,在任何时刻进入小路的自行车最多不会超过两辆(南开和天大方向各一辆),因此不需为安全岛M设置信号量。在路口S处,南开出发的若干辆自行车应进行路口资源的争夺,以决定谁先进入小路SK段,为此设置信号量S,用以控制路口资源的争夺;同理,设置信号
2、量T,控制天大方向自行车对路口T的争夺。又小路SK段仅允许一辆车通过,设置信号量SK初值为1,同理设置小路LT段信号量LT初值为1。程序如下:S := l; T:=1; SK :1; LT:=1;Parbegin进程P:(南开方向自行车)beginP(S) ; 与其它同方向的自行车争夺路口SP(SK); 同对面自行车争夺路段SK通过SK;进入M; *V (SK);一旦进入M,便可释放路段SKP (LT) ; 同对面的自行车争夺路段LT通过LT;V (LT);将路段LT释放V(S); 将路口S释放给同方向的正在路口S处等待的自行车end,进程Q:(天大方向自行车)beginP(T);P(LT);
3、通过LT;进入M;V(LT);P(SK);通过SK;V(SK);V(T);End;Parend。说明:P进程进入安全岛M后,释放了路段SK,但没有释放路口S,原因在于它是向对面的4进程释放路段资源SK,而在P进程离开小路LT后,才会将路口S释放给其他P进程,如不这样,就会死锁。请考虑如下情况:两个方向各有一辆车前进,若在P进程到达安全岛M后,执行V (S)及V (SK)操作,则有可能使得同方向的其它P进程得到路段SK的使用权,而进入小路;同理,Q进程到达安全岛后执行V (LT)及V (T)操作,有可能使得同方向的其它Q进程得到路段LT而进入小路。此时共有四辆车在整个路径中,最终出现死锁状态。2
4、某寺庙,有小、老和尚若干,有一水缸,由小和尚提水入缸(向缸中倒水)供老和尚饮用。水缸可容10桶水,水取自同一井中。水井径窄,每次只能容一个捅取水。水桶总数为3个。每次人、取缸水仅为1桶,且不可同时进行。试给出有关从缸中取水和向缸中倒水的算法描述。解答:应首先考虑清楚本题需要几个进程。从井中取水后向缸中倒水为连续动作,可算同一进程,从缸中取水为另一进程。再考虑信号量有关互斥的资源有水井(一次仅一个水桶进出)和水缸(一次入、取水为一桶),分别为之设信号量mutexl , mutex2控制互斥;另有同步问题存在:三个水桶无论从井中取水还是人出水缸都是一次一个,应为之设信号量count,抢不到水桶的进
5、程只好等待;还有水缸满时,不可人水,设信号量empty控制入水量水缸空时不可出水,设信号量full,控制出水量。mutexl:1;mutex:1; empty:10; full:0 ;count:3;parbegin入水: beginLl: P(empty);P( count) ;P (mutexl) ;从井中取水;V(mutext1);P(mutex2);送入水缸;V(mutex2);V(count);V(full);Goto Ll;End;取水: begin L2: P(full); P(count); P(mutex2) ; 从缸中取水; V (mutex2) ; V(empty); V
6、(count); Goto L2; End; Parend.3桌子上有一只盘子,最多可容纳两个水果,每次只能放入或取出一个水果。爸爸专向盘子中放苹果(apple),妈妈专向盘子中放橘子(orange),两个儿子专等吃盘子中的橘子,两个女儿专等吃盘子中的苹果。请用P, V操作来实现爸爸、妈妈、儿子、女儿之间的同步与互斥关系。解答:盘子为互斥资源,因可以放两个水果,empty初值为2; father放苹果前先看看有无空间,若有则抢盘子,放apple。后向女儿发信号(V (apple)); mother放橘子前先看看有无空间,若有则抢盘子,放橘子后向儿子发信号(V (orange));女儿先看有无苹
7、果,若有则抢盘子,取走苹果后将盘子置空(V (empty));儿子先看有无橘子,若有则抢盘子,取走橘子后将盘子置空。该题是生产者消费者问题的变形,有两对生产者和消费者。生产者需指明是给哪个消费者的产品,但消费者取走产品后无须特别通知某个生产者,因为空出的缓冲区(盘子)可由两个生产者随意争夺。设信号量mutex初值为1,控制对盘子的互斥访问;apple表示盘中苹果个数,orange表示盘中橘子个数,初值均为0. parbegin father: begin Ll:P( empty); P(mutex ); 放苹果;。 V (mutex); V(apple); Goto Ll ; End; mot
8、her: begin L2: P(empty) ; P(mutex); 放橘子; V (mutex ); V(orange); Coto L2; End;daughter: begin L3: P(apple); P(mutex); 取苹果 V (mutex); V(empty); Goto L3 ; End; son: begin L4: P(orange); P(mutex); 取橘子 V (mutex); V (empty) ; Goto L4; End; Parend4. 在4100米接力赛中,4个运动员之间存在如下关系,运动员1跑到终点把接力棒交给运动员2;运动员2一开始处于等待状态
9、,在接到运动员1传来的接力棒后才能往前跑,他跑完100米后交给运动员3,运动员3也只有在接到运动员2传来的棒后才能跑,他跑完100米后交给运动员4,运动员4接到棒后跑完全程。请试用信号量机制对其上过程进行分析。解答:P1: P2: P(Sl); P3: P(S2); P4: P(S3);起跑,前进l00m; 起跑,前进l00m; 起跑,前进l00m; 起跑,前进l00m;V(S1); V(S2); V(S3); 到达终点。5. 在公共汽车上,司机和售票员各行其职,司机负责开车和到站停车;售票员负责售票和开、关车门;当售票员关好车门后驾驶员才能开车行驶。试用wait和signal操作实现司机和售
10、票员的同步。问题描述:设公共汽车上,司机和售票员的活动分别如下:司机的活动:启动车辆:正常行车;到站停车。售票员的活动:关车门;售票;开车门。在汽车不断地到站、停车、行驶过程中,这两个活动有什么同步关系?用信号量和P 、V 操作实现它们的同步。问题分析:在汽车行驶过程中,司机活动与售票员活动之间的同步关系为:售票员关车门后,向司机发开车信号,司机接到开车信号后启动车辆,在汽车正常行驶过程中售票员售票,到站时司机停车,售票员在车停后开门让乘客上下车。因此,司机启动车辆的动作必须与售票员关车门的动作取得同步;售票员开车门的动作也必须与司机停车取得同步。应设置两个信号量:S1、S2 ;S1表示是否允
11、许司机启动汽车(其初值为0 )S2表示是否允许售票员开门(其初值为0 )用P 、v 原语描述如下:The P,V code Using Pascalvar S1,S2 : semaphore ;S1=0;S2=0;cobeginprocedure driver beginwhile TRUE beginP(S1); Start; Driving; Stop;v(S2); endendprocedure Conductorbeginwhile TRUE begin关车门;v(s1);售票;p(s2);开车门;上下乘客;end endcoend6.有一只铁笼子,每次只能放入一只动物,猎手向笼子里放
12、入老虎,农民向笼子里放入猪;动物园等待取笼子里的老虎,饭店等待取笼子里的猪。现请用wait和signal操作写出能同步执行的程序。var Sempty, Stiger, Spig,: semaphore:= 1,0,0; beginparbeginHunter: beginrepeatwait(Sempty); ;signal(Stiger); until false; end;Farmer: beginrepeatwait(Sempty); ;signal(Spig); until false; end;Zoo: beginrepeatwait(Stiger); ;signal(Sempty); until false; end;Hotel: beginrepeatwait(Spig); ;signal(Sempty); until false; end;parend;end;7. 假设有3个并发进程P,Q,R,其中P负责从输入设备上读入信息,并传送给Q,Q将信息加工后传送给R,R负责打印输出。进程P,Q共享一个有m个缓冲区组成的缓冲池;进程Q,R共享一个有n个缓冲区组成的缓冲池(假设缓冲池足够大,进程间每次传输信息的单位均小