操作系统练习 同步问题 有答案.docx

操作系统练习 同步问题 有答案.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；mutex２:

＝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;