操作系统练习 同步问题 有答案.docx
- 文档编号:9674770
- 上传时间:2023-05-20
- 格式:DOCX
- 页数:15
- 大小:35.45KB
操作系统练习 同步问题 有答案.docx
《操作系统练习 同步问题 有答案.docx》由会员分享,可在线阅读,更多相关《操作系统练习 同步问题 有答案.docx(15页珍藏版)》请在冰点文库上搜索。
操作系统练习同步问题有答案
操作系统练习题:
天大
1在南开大学和天津大学之间有一条弯曲的小路,其中从S到T一段路每次只允许一辆自行车通过,但中间有一个小的“安全岛”M(同时允许两辆自行车停留),可供两辆自行车已从两端进小路情况下错车使用,如图所示。
试设计一个算法使来往的自行车均可顺利通过。
T
K
L
S
南开
解答:
首先中间的安全岛M仅允许两辆自行车通过,应作为临界资源设置信号量。
但仔细分析发现,在任何时刻进入小路的自行车最多不会超过两辆(南开和天大方向各一辆),因此不需为安全岛M设置信号量。
在路口S处,南开出发的若干辆自行车应进行路口资源的争夺,以决定谁先进入小路SK段,为此设置信号量S,用以控制路口资源的争夺;同理,设置信号量T,控制天大方向自行车对路口T的争夺。
又小路SK段仅允许一辆车通过,设置信号量SK初值为1,同理设置小路LT段信号量LT初值为1。
程序如下:
S:
=l;T:
=1;SK:
=1;LT:
=1;
Parbegin
进程P:
(南开方向自行车)
begin
P(S);{与其它同方向的自行车争夺路口S}
P(SK);{同对面自行车争夺路段SK}
通过SK;
进入M;**
V(SK);{一旦进入M,便可释放路段SK}
P(LT);{同对面的自行车争夺路段LT}
通过LT;
V(LT);{将路段LT释放}
V(S);{将路口S释放给同方向的正在路口S处等待的自行车}
end,
进程Q:
(天大方向自行车)
begin
P(T);
P(LT);
通过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某寺庙,有小、老和尚若干,有一水缸,由小和尚提水入缸(向缸中倒水)供老和尚饮用。
水缸可容10桶水,水取自同一井中。
水井径窄,每次只能容一个捅取水。
水桶总数为3个。
每次人、取缸水仅为1桶,且不可同时进行。
试给出有关从缸中取水和向缸中倒水的算法描述。
解答:
应首先考虑清楚本题需要几个进程。
从井中取水后向缸中倒水为连续动作,可算同一进程,从缸中取水为另一进程。
再考虑信号量.有关互斥的资源有水井(一次仅一个水桶进出)和水缸(一次入、取水为一桶),分别为之设信号量mutexl,mutex2控制互斥;
另有同步问题存在:
三个水桶无论从井中取水还是人出水缸都是一次一个,应为之设信号量count,抢不到水桶的进程只好等待;还有水缸满时,不可人水,设信号量empty控制入水量.水缸空时不可出水,设信号量full,控制出水量。
mutexl:
=1;mutex2:
=1;empty:
=10;full:
=0; count:
=3;
parbegin
入水:
begin
Ll:
P(empty);
P(count);
P(mutexl);
从井中取水;
V(mutext1);
P(mutex2);
送入水缸;
V(mutex2);
V(count);
V(full);
GotoLl;
End;
取水:
begin
L2:
P(full);
P(count);
P(mutex2);
从缸中取水;
V(mutex2);
V(empty);
V(count);
GotoL2;
End;
Parend.
3桌子上有一只盘子,最多可容纳两个水果,每次只能放入或取出一个水果。
爸爸专向盘子中放苹果(apple),妈妈专向盘子中放橘子(orange),两个儿子专等吃盘子中的橘子,两个女儿专等吃盘子中的苹果。
请用P,V操作来实现爸爸、妈妈、儿子、女儿之间的同步与互斥关系。
解答:
盘子为互斥资源,因可以放两个水果,empty初值为2;father放苹果前先看看有无空间,若有则抢盘子,放apple。
后向女儿发信号(V(apple));mother放橘子前先看看有无空间,若有则抢盘子,放橘子后向儿子发信号(V(orange));女儿先看有无苹果,若有则抢盘子,取走苹果后将盘子置空(V(empty));儿子先看有无橘子,若有则抢盘子,取走橘子后将盘子置空。
该题是生产者/消费者问题的变形,有两对生产者和消费者。
生产者需指明是给哪个消费者的产品,但消费者取走产品后无须特别通知某个生产者,因为空出的缓冲区(盘子)可由两个生产者随意争夺。
设信号量mutex初值为1,控制对盘子的互斥访问;apple表示盘中苹果个数,orange表示盘中橘子个数,初值均为0.
parbegin
father:
begin
Ll:
P(empty);
P(mutex);
放苹果;。
V(mutex);
V(apple);
GotoLl;
End;
mother:
begin
L2:
P(empty);
P(mutex);
放橘子;
V(mutex);
V(orange);
CotoL2;
End;
daughter:
begin
L3:
P(apple);
P(mutex);
取苹果
V(mutex);
V(empty);
GotoL3;
End;
son:
begin
L4:
P(orange);
P(mutex);
取橘子
V(mutex);
V(empty);
GotoL4;
End;
Parend
4.在4×100米接力赛中,4个运动员之间存在如下关系,运动员1跑到终点把接力棒交给运动员2;运动员2一开始处于等待状态,在接到运动员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操作实现司机和售票员的同步。
问题描述:
设公共汽车上,司机和售票员的活动分别如下:
司机的活动:
启动车辆:
正常行车;到站停车。
售票员的活动:
关车门;售票;开车门。
在汽车不断地到站、停车、行驶过程中,这两个活动有什么同步关系?
用信号量和P、V操作实现它们的同步。
问题分析:
在汽车行驶过程中,司机活动与售票员活动之间的同步关系为:
售票员关车门后,向司机发开车信号,司机接到开车信号后启动车辆,在汽车正常行驶过程中售票员售票,到站时司机停车,售票员在车停后开门让乘客上下车。
因此,司机启动车辆的动作必须与售票员关车门的动作取得同步;售票员开车门的动作也必须与司机停车取得同步。
应设置两个信号量:
S1、S2;
S1表示是否允许司机启动汽车(其初值为0)
S2表示是否允许售票员开门(其初值为0)
用P、v原语描述如下:
TheP,VcodeUsingPascal
varS1,S2:
semaphore;
S1=0;S2=0;
cobegin
proceduredriver
begin
whileTRUE
begin
P(S1);
Start;
Driving;
Stop;
v(S2);
end
end
procedureConductor
begin
whileTRUE
begin
关车门;
v(s1);
售票;
p(s2);
开车门;
上下乘客;
end
end
coend
6.有一只铁笼子,每次只能放入一只动物,猎手向笼子里放入老虎,农民向笼子里放入猪;动物园等待取笼子里的老虎,饭店等待取笼子里的猪。
现请用wait和signal操作写出能同步执行的程序。
varSempty,Stiger,Spig,:
semaphore:
=1,0,0;
begin
parbegin
Hunter:
begin
repeat
wait(Sempty);
signal(Stiger);
untilfalse;
end;
Farmer:
begin
repeat
wait(Sempty);
signal(Spig);
untilfalse;
end;
Zoo:
begin
repeat
wait(Stiger);
signal(Sempty);
untilfalse;
end;
Hotel:
begin
repeat
wait(Spig);
signal(Sempty);untilfalse;
end;
parend;
end;
7.假设有3个并发进程P,Q,R,其中P负责从输入设备上读入信息,并传送给Q,Q将信息加工后传送给R,R负责打印输出。
进程P,Q共享一个有m个缓冲区组成的缓冲池;进程Q,R共享一个有n个缓冲区组成的缓冲池(假设缓冲池足够大,进程间每次传输信息的单位均小于等于缓冲区长度),请写出满足上述条件的并发程序。
varmutex1,mutex2,Sip,Siq,Soq,Sor:
semaphore:
=1,1,m,0,n,0;
begin
parbegin
ProcessP
begin
repeat
<读入信息>
wait(Sip);
wait(mutex1);
<数据放入缓冲区>
signal(mutex1);
signal(Siq);
untilfalse
end;
ProcessQ
begin
repeat
wait(Siq);
wait(mutex1);
<从缓冲区中取出数据>
signal(mutex1);
signal(Sip);
<数据处理〉
wait(Soq);
wait(mutex2);
<处理后的数据放入缓冲区>
signal(mutex2);
signal(Sor);
untilfalse
end;
ProcessR
repeat
wait(Sor);
wait(mutex2);
<把数据送入打印机完成打印>;
signal(mutex2);
signal(Soq);
untilfalse
end
parend
end
8.理发店里有一位理发师,一把理发椅和n把供等候理发的顾客坐的椅子。
如果没有顾客,理发师便在理发椅上睡觉,当一个顾客到来时,他必须先叫醒理发师,如果理发师正在理发时又有顾客来到,则如果有空椅子可坐,他们就坐下来等;如果没有空椅子,他就离开。
1)控制变量waiting用来记录等候理发的顾客数,初值均为0;
2)信号量customers用来记录等候理发的顾客数,并用作阻塞理发师进程,初值为0;
3)信号量barbers用来记录正在等候顾客的理发师数,并用作阻塞顾客进程,初值为0;
4)信号量mutex用于互斥,初值为1
intwaiting=0;//等候理发的顾客数
intchairs=n;//为顾客准备的椅子数
semaphorecustomers=0,barbers=0,mutex=1;
cobegin
barber()
begin
while(TRUE);//理完一人,还有顾客吗?
P(cutomers);//若无顾客,理发师睡眠
P(mutex);//进程互斥
waiting:
=waiting–1;//等候顾客数少一个
V(barbers);//理发师去为一个顾客理发
V(mutex);//开放临界区
cut-hair();//正在理发
end
customer()
begin
P(mutex);//进程互斥
if(waiting)
begin
waiting:
=waiting+1;//等候顾客数加1
V(customers);//必要的话唤醒理发师
V(mutex);//开放临界区
P(barbers);//无理发师,顾客坐着养神
get-haircut();//一个顾客坐下等理/
end
else
V(mutex);//人满了,走吧!
end
coend
9.有一阅览室,共有100个座位。
读者进入时必须先在一种登记表上登记,该表为每一座位列一个表目,包括座号和读者姓名。
读者离开时要注销掉登记内容。
试用wait和signal原语描述读者进程的同步问题。
varmutex,readcount:
semaphore:
=1,100;
Begin
Parbegin
ProcessReader:
begin
repeat
wait(readcount);
wait(mutex);
<填入座号和姓名完成登记>;
signal(mutex);
<阅读>
wait(mutex)
<删除登记表中的相关表项,完成注销>
signal(mutex);
signal(readcount);
untilfalse;
end;
parend;
End;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 操作系统练习 同步问题 有答案 操作系统 练习 同步 问题 答案