文档文库

手机版

投诉建议

首页 > P、V操作习题答案

P、V操作习题答案

发布时间：2020-06-19 09:54:44 来源：文档文库

小中大

字号：

手机查看

信号量应用问题：

1．写出程序描述下列前趋关系。

S1->S2, S1->S3, S2->S4, S2->S5 , S3->S6, S4->S7, S5->S7, S6->S7

Var s1,s2, s3,s4:semaphore:=0, 0, 0, 0;

Begin

Parbegin

P1: begin

….;

V(s1);

End;

P2: begin

P(s1);

…;

V(s2);

End;

P3: begin

P(s1)

…

V(s3)

End;

P4: begin

P(s2);

…

V(s4);

P5: begin

P(s2);

..;

V(s4);

End;

P6: begin

P(s3)

..

V(s4)

End;

P7:begin

P(s4);

…

End;

Parend

end

2. 请用信号量实现4×100（4人，每人100米）接力赛的同步过程。

提示：前趋图同步问题，可设4个进程，三个信号量，进程1只设V操作，进程4只设P操作，其余进程先做P操作再做V操作。

Var s1,s2,s3:semaphore:=0, 0, 0;

Begin

Parbegin

Athlete1: begin

Run 100m;

V(s1);

End;

Athlete2: begin

P(s1)

Run 100m;

V(s2);

End;

Athlete3: begin

P(s2) ;

Run 100m;

V(s3);

End;

Athlete4: begin

P(s3);

Run 100m;

End;

Parend

end

3．设公共汽车上，司机和售票员的活动分别是：

司机：售票员：

启动车辆上乘客

正常行车关车门

到站停车售票

开车门

下乘客

在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系？请用信号量机制实现他们的同步。

/-假定初始状态为停车状态，引入信号量Stop和Run：

BEGIN

semaphore Stop,Run;

Stop:=Run:=0;

CoBegin

Driver: BEGIN

Repeat

Wait(Run);

启动车辆；

正常行驶；

到站停车；

Signal(Stop);

Until False;

END;

Conductor:BEGIN

Repeat

上乘客；

关车门；

Signal(Run);

售票；

Wait(Stop);

开车门；

下乘客；

Until False;

END;

CoEnd;

END;

生产者消费者问题：

1．桌上有一个可以容纳两个水果的盘子，每次只能放或取一个水果。爸爸放苹果妈妈放橘子，两个儿子吃苹果，两个女儿吃橘子。试用信号量和P、V操作，编写实现爸爸、妈妈、儿子和女儿的并发工作程序。

Mutex实现互斥放或取水果。

empty盘子可放水果数

Apple 盘子中放的苹果数

Orange 盘子中放的橘子数

Semaphore mutex=1;

Semaphore empty=2;

Semahpore apple=0;

Semahpore orange=0;

Main()

{

Cobegin

Father();

Mother();

Son();

Daughter();

;

Coend)

}

Father()

{

While(true)

{ p(empty)

P(mutex)

放苹果

V(mutex)

V(apple)}

}

Mother()

{

While(true)

{ p(empty)

P(mutex)

放橘子

V(mutex)

V(orange)}

}

Son()

{

While(true)

{ p(apple)

P(mutex)

取苹果

V(mutex)

V(empty)}

}

Daughter()

{

While(true)

{ p(orange)

P(mutex)

取橘子

V(mutex)

V(empty)}

}

2、有一个仓库存放两种零件A和B，最大库容量各为m个。有一车间不断地取A和B进行装配，每次各取一个。为了避免零件锈蚀，遵循线入库者先出库的原则。有两组供应商分别不断地供应A和B（每次一个），为保证齐套和合理库存，当某种零件的数量比另一种数量超过n（n）个时，暂停对数量大的零件的进货，集中补充数量少的零件。试用P、V操作正确实现之。

semaphore mutex=1, emptya=emptyb=m, fulla=fullb=0, sa=sb=n;

main()

{ CoBegin

Provider_A(); //零件A供应商

Provider_B(); //零件B供应商

Assembling_Shop(); //装配车间

CoEnd

}

Provider_A()

{ while(true)

{ p(emptya);

p(sa);

p(mutex);

将零件A放入仓库;

v(mutex);

v(fulla);

v(sb);

}

}

Provider_B()

{ while(true)

{ p(emptyb);

p(sb);

p(mutex);

将零件B放入仓库;

v(mutex);

v(fullb);

v(sa);

}

}

Assembling_Shop()

{ while(true)

{ p(fulla);

p(fullb);

p(mutex);

装配零件;

v(mutex);

v(emptya);

v(emptyb);

}

}

3、有一个仓库，可以存放A和B两种产品，仓库的存储空间足够大，但要求：

每次只能存入一种产品（X或Y）；

-N产品数量-B产品数量。

其中，N和M时正整数。

试用“存放A”、“存放B”和P、V操作描述产品A与产品B的入库过程。

A-B说明：如果只放A不放B，则A最多可放M-1个，如果多放一个B，则可以多放一个A。

B-A说明：如果只放B不放A，则B最多可放N-1个，如果多放一个A，则可以多放一个B。

/2-BEGIN

Mutex,SA,SB:semaphore;

Mutex:=1;

SA:=M-1;

SB:=N-1;

parBegin

process PA

Begin

loop:

P(SA);

P(Mutex);

存放A;

V(Mutex);

V(SB);

Goto loop;

End;

process PB

Begin

loop:

P(SB);

P(Mutex);

存放B;

V(Mutex);

V(SA);

Goto loop;

End;

parEnd;

END;

/北大91

读者写者问题：

1、多个进程共享一个文件，其中只读文件的程值为读者，其余只写文件的称为写者。读者可以同时读，但写者只能独立地写。

说明进程间的相互制约关系，应设置哪些信号量？

用P、V操作写出其同步算法；

修改上述算法，使得它对写者优先，即一旦有写者到达，后续的读者都必须等待，而无论是否有读者在读文件。（该问题的又一提法：在一个飞机订票系统中，多个用户共享一个数据库。多用户同时查询是可以接受的，但若一个用户要订票需更新数据库时，其余所有用户都不可以访问数据库。请画出用户查询与订票的逻辑框图(等价于同步进程的描述的图式表示)。

为了提高写者的优先级，增加一个信号量S，用于在写进程到达后封锁后续的读者

Semaphore mutex=1;

Semaphore write=1;

Semahpore s=1;

Int count =0;

Main()

{

Cobegin

Reader();

Writer();

Coend；

}

Reader()

{ while(true)

{

P(s);

P(mutex);

If(count==0) p(write);

Count++;

V(s);

读文件；

P(mutex)

Count--;

If(count==0) v(write);

V(mutex);

}

Writer()

{

While(true)

{ p(s);

P(write);

写文件；

V(write);

V(s);

}

2．某一桥只有一车道，载重为4辆车，用P、V操作实现两方向的车过桥。

本题本质上可以认为是读者写者问题，往同一个方向的车可以认为是读者，往相反方向的车可以认为是写者。但是由于桥的重量有限，增加了读者之间的互斥。本题的临界资源显然是单通道的桥，首先如果桥上有向东方向的车，那么向西方向的车一定不能过，如果超过4辆，同一方向的车也不能过，需要互斥。

设信号量mutex，实现双向车子互斥通行；信号量sew，swe表示由西向东与由东向西的负荷数，初值为4；整数型iew,iwe表示各方向的车子数，初值为0；siew,siwe实现对iew,iwe的互斥访问，初值为1；

Process 由东向西的车子；

Begin

P(sew);

P(siew);

Iew:=iew+1;

If iew=1 then p(mutex);

V(siew);

过桥；

P(siew);

Iew:=iew-1;

If iew=0 then v(mutex);

V(siew);

V(sew)

End

Porcess 由西向东

Begin

P(swe);

P(siwe);

Iwe:=iwe+1;

If iwe=1 hten p(mutex);

V(siwe);

过桥；

P(siwe);

Iwe:=iwe-1;

If iwe=0 then v(mutex);

V(siwe);

V(swe)

End;

理发师睡觉问题：

1．（睡眠的理发师问题）理发店有一个等候室（其中有N把椅子）和一个理发室（一把理发椅组成）。如果没有顾客来理发，理发时就在理发椅上睡觉，如果一个走进理发店，发现等候室的椅子都坐满就离开理发店；如果理发师正忙于理发，那么该顾客就坐在一把空椅子上等待；若理发师正在睡觉，则顾客就唤醒他。用P、V操作写出工作流程。

考点：用PV原语实现同步

Semaphore costomers=0; 等候的顾客数（不包括正在理发的）

Semaphore barbers=0; 等候顾客的理发师数

Semaphore mutex=1;

Int waiting =0; 等候的顾客数（还没有理发，实际是customers的备份，为了读取信号量的当前值）；

Void barber(void)

{ while (true)

{ P(customers);

P(mutex);

waiting = waiting – 1 ;

V(barbers);

V(mutex);

cut_hair( );

}

顾客进程

Void customers(void)

{P(mutex);

if(waiting

{ waiting = waiting + 1 ;

V(customers);

V(mutex);

P(barbers);

get_hair( );}

else {V(mutex);}

}

提示：考虑一下理发师（barber）重复的下列活动：（1）睡觉；（2）为顾客理发；

顾客（customers）重复的下列活动：（3）在椅子上等候；（4）理发；离开；

显然，理发师在（1）处要考察是否有顾客等候理发，如果没有，理发师睡觉；在（2）处理发师等待最先进入理发店的顾客唤醒，开始理发。

顾客在（3）处先看是否有座位，没有则离开；等候理发的顾客在（4）处被理发师唤醒（最先理发的顾客要唤醒理发师）；理发结束后离开。

在这两个活动中，从资源的角度来看，理发师是顾客争用的资源，用信号量barber表示，初值为0；除此以外，顾客还要争用n张椅子，信号量customers表示等候理发的顾客数，初值为0；最后设置信号灯变量mutex用于这两个活动对资源barber、customers的互斥，初值为1。

2．复印室里有一个操作员为顾客复印资料，有5把椅子供顾客休息等待复印。如果没有顾客，则操作员休息，当顾客来到复印室时，如果有空椅子则坐下来，并唤醒复印操作员；如果没有空椅子必须离开复印室。试用信号量几P、V操作实现顾客和操作员活动的同步。

Customers 表示正在等待复印的顾客数

Operator 代表操作员的状态，只能取1或0；

Waiting 表示正在等待的顾客数；

Mutex实现对waiting的互斥访问

customers, operator,mutex: semaphore;

waiting: inteter;

customers=0;

operator=0;

mutex=1;

process operator

begin

loop:

p(customers);

复印；

V(operator);

Goto loop;

End;

Process coutomeri

Begin

P(mutex);

If waiting <5 then

Begin

Waiting=waiting+1;

V(custormers);

V(mutex);

P(operator);

P(mutex);

Waiting=waiting-1;

V(mutex);

End

Else

Begin

V(mutex);

End;

4．理发师问题：一个理发店有一个入口和一个出口。理发店内有一个可站5 位顾客的站席

区、4 个单人沙发、3 个理发师及其专用理发工具、一个收银台。新来的顾客坐在沙发上等

待；没有空沙发时，可在站席区等待；站席区满时，只能在入口外等待。理发师可从事理

发、收银和休息三种活动。理发店的活动满足下列条件：

1）休息的理发师是坐地自己专用的理发椅上，不会占用顾客的沙发；

2）处理休息状态的理发师可为在沙发上等待时间最长的顾客理发；

3）理发时间长短由理发师决定；

4）在站席区等待时间最长的顾客可坐到空闲的理发上；

5）任何时刻最多只能有一个理发师在收银。

试用信号量机制或管程机制实现理发师进程和顾客进程。

原理：

(1)customer 进程：

首先检查站席区是否已满（stand_capacity）,若满选择离开，否则进入站席区，即进入

理发店。在站席区等待沙发的空位（信号量sofa），如果沙发已满，则进入阻塞等待队列，

直到出现空位，在站席区中等待时间最长的顾客离开站席区（stand_capacity）。坐到沙

发上，等待理发椅(barber_chair)，如果理发椅已满，则进入阻塞等待队列，直到出现

空位，在沙发上等待时间最长的顾客离开沙发（释放信号量sofa）。坐到理发椅上，释放

准备好的信号（customer_ready），获得该理发师的编号（0~1 的数字）。等待理发师理

发结束（finished[barber_number]）。在离开理发椅之前付款（payment），等待收据

(receipt)，离开理发椅（leave_barberchair）。最后离开理发店。

这里需要注意几点：

a) 首先是几个需要进行互斥处理的地方，主要包括:进入站席区、进入沙发、进入理发椅

和付款几个地方。

b) 通过barber_chair 保证一个理发椅上最多只有一名顾客。但这也不够，因为单凭

baber_chair 无法保证一名顾客离开理发椅之前，另一位顾客不会坐到该理发椅上，

因此增加信号量leave_barberchair，让顾客离开理发椅后，释放该信号，而理发

师接收到该信号后才释放barber_chair 等待下一位顾客。

c) 在理发的过程中，需要保证是自己理发完毕，才能够进行下面的付款、离开理发椅的活

动。这个机制是通过customer 进程获得给他理发的理发师编号来实现的，这样，当

该编号的理发师释放对应的finished信号的时候，该顾客才理发完毕。

d) 理发师是通过mutex 信号量保证他们每个人同时只进行一项操作（理发或者收款）。

e) 为了保证该顾客理发完毕后马上可以付款离开，就应该保证给该顾客理发的理发师在理

发完毕后马上到收银台进入收款操作而不是给下一位顾客服务。在伪码中由以下机制实

现：即顾客在释放离开理发椅的信号前，发出付款的信号。这样该理发师得不到顾客的

离开理发椅的信号，不能进入下一个循环为下一名顾客服务，而只能进入收款台的收款

操作。直到顾客接到收据后，才释放离开理发椅的信号，离开理发椅，让理发师释放该

理发椅的信号，让下一位等待的顾客坐到理发椅上。

(2)barber 进程

首先将该理发师的编号压入队列，供顾客提取。等待顾客坐到理发椅坐好(信号量

customer_ready)，开始理发，理发结束后释放结束信号（finished）。等待顾客

离开理发椅（leave_barberchair）（期间去收银台进行收款活动），释放理发椅空闲信

号(barber_chair)，等待下一位顾客坐上来。

(3)cash（收银台）进程

等待顾客付款(payment),执行收款操作，收款操作结束，给付收据（receipt）。

信号量总表：

信号量 wait signal

stand_capacity 顾客等待进入理发店顾客离开站席区

sofa 顾客等待坐到沙发顾客离开沙发

barber_chair 顾客等待空理发椅理发师释放空理发椅

customer_ready 理发师等待，直到一个顾客坐

到理发椅

顾客坐到理发椅上，给理发师

发出信号

mutex 等待理发师空闲，执行理发或

收款操作

理发师执行理发或收款结束，

进入空闲状态

mutex1 执行入队或出队等待入队或出队结束，释放信号

finished 顾客等待对应编号理发师理

发结束

理发师理发结束，释放信号

leave_barberchair 理发师等待顾客离开理发椅顾客付款完毕得到收据，离开

理发椅释放信号

payment 收银员等待顾客付款顾客付款，发出信号

receipt 顾客等待收银员收、开具收据收银员收款结束、开具收据，

释放信号

伪码：

semaphore stand_capacity=5;

semaphore sofa=4;

semaphore barber_chair=3;

semaphore customer_ready=0;

semaphore mutex=3;

semaphore mutex1=1;

semaphore finished[3]={0,0,0};

semaphore leave_barberchair=0;

semaphore payment=0;

semaphore receipt=0;

void customer()

{

int barber_number;

wait(stand_capacity); //等待进入理发店

enter_room(); //进入理发店

wait(sofa); //等待沙发

leave_stand_section(); //离开站席区

signal(stand_capacity);

sit_on_sofa(); //坐在沙发上

wait(barber_chair); //等待理发椅

get_up_sofa(); //离开沙发

signal(sofa);

wait(mutex1);

sit_on_barberchair(); //坐到理发椅上

signal(customer_ready);

barber_number=dequeue(); //得到理发师编号

signal(mutex1);

wait(finished[barber_number]); //等待理发结束

pay(); //付款

signal(payment); //付款

wait(receipt); //等待收据

get_up_barberchair(); //离开理发椅

signal(leave_barberchair); //发出离开理发椅信号

exit_shop(); //了离开理发店

}

void barber(int i)

{

while(true)

{

wait(mutex1);

enqueue(i); //将该理发师的编号加入队列

signal(mutex1);

wait(customer_ready); //等待顾客准备好

wait(mutex);

cut_hair(); //理发

signal(mutex);

signal(finished); //理发结束

wait(leave_barberchair); //等待顾客离开理发椅信号

signal(barber_chair); //释放barber_chair 信号

}

}

void cash() //收银

{

while(true)

{

wait(payment); //等待顾客付款

wait(mutex); //原子操作

get_pay(); //接受付款

give_receipt(); //给顾客收据

signal(mutex);

signal(receipt); //收银完毕，释放信号

}

}

分析：

在分析该问题过程中，出现若干问题，是参阅相关资料后才认识到这些问题的隐蔽性和严重

性的,主要包括：

（1）在顾客进程，如果是在释放leave_barberchair 信号之后进行付款动作的话，很

容易造成没有收银员为其收款的情形，原因是：为该顾客理发的理发师收到

leave_barberchair 信号后，释放barber_chair 信号，另外一名顾客坐到理发椅上，

该理发师有可能为这另外一名顾客理发，而没有为刚理完发的顾客收款。为解决这个问题，

就是采取在释放leave_barberchair 信号之前，完成付款操作。这样该理发师无法进入

下一轮循环为另外顾客服务，只能到收银台收款。

（2）本算法是通过给理发师编号的方式，当顾客坐到某理发椅上也同时获得理发师的编号，

如此，当该理发师理发结束，释放信号，顾客只有接收到为其理发的理发师的理发结束信号

才会进行付款等操作。这样实现，是为避免这样的错误，即：如果仅用一个finished 信

号量的话，很容易出现别的理发师理发完毕释放了finished 信号，把正在理发的这位顾

客赶去付款,而已经理完发的顾客却被阻塞在理发椅上的情形。当然也可以为顾客进行编

号，让理发师获取他理发的顾客的编号，但这样就会限制顾客的数量，因为finished[]

数组不能是无限的。而为理发师编号，则只需要三个元素即可。