os例题

一真经之银行排队问题(北京大学2000)

问题描述：

银行有n个柜员,每个顾客进入银行后先取一个号,并且等着叫号,当一个柜员空闲后，就叫下一个号. 问题分析：

将顾客号码排成一个队列,顾客进入银行领取号码后,将号码由队尾插入;柜员空闲时,从队首取得顾客号码,并且为这个顾客服务,由于队列为若干进程共享, 所以需要互斥.柜员空闲时,若有顾客,就叫下一个顾客为之服务.因此,需要设臵一个信号量来记录等待服务的顾客数.

The P,V code Using Pascal

begin

var mutex=1,customer_count=0:semaphore; cobegin

process customer begin repeat 取号码； p(mutex); 进入队列； v(mutex);

v(customer_count); end

process serversi(i=1,...,n) begin repeat

p(customer_count); p(mutex);

从队列中取下一个号码； v(mutex);

为该号码持有者服务； end coend

20

CHAPTER 3. 九阴真经之研究生题辑21

end

_思考：

某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答下列问题

(1)用PV操作管理这些并发进程时，应怎样定义信号量，写出信号量的初值以及信号量各种取值的含义。

(2)若欲购票者最多为n个人，写出信号量可能的变化范围(最大值和最小值)。 定义信号量S,初值为20，当s > 0时，它表示可以继续进入购票厅的人数，当s = 0时,表示厅内已有20人正在购票，当s < 0时jSj表示正等待进入的人数。

The P,V code Using Pascal

var S:semaphore; S=20; cobegin

procedure P_i: begin p(s); .

Enter and buy ticket; . v(s) end coend

(2)最大值为20，最小值为20-N。

二真经之生产消费问题扩展(浙江大学2001)

假设缓冲区buf1和缓冲区buf2无限大，进程p1向buf1写数据，进程p2向buf2写数据，要求buf1数据个数和buf2数据个数的差保持在(m,n)之间(m

题中没有给出两个进程执行顺序之间的制约关系，只给出了一个数量上的制约关 系，即m·—buf1数据个数－buf2数据个数·n．不需要考虑缓冲区的大小，只需要考虑两个进程的同步和互斥．p2向buf2写数据比p1向buf1写数据的次数最少不超过m次，最多不能超过n次，反之也成立．所以是一个生产者和消费者问题。将等式展开得：(1)m·(buf1数据个数－buf2数据个数)·n; (2)m·(buf2数据个数－buf1数据个数)·n;由于m,n都是正数，等式只有一个成立，不妨设(1)成立．在进程p1和p2都没有运行时，两个缓冲区数据个数之差为0,因此，p1必须先运行，向buf1至少写m+1个数据后再唤醒p2运行．信号量s1表示p1一次写入的最大量,初值为n，s2表示p2一次写入的最大量,初值为-m.

The P,V code Using Pascal

begin

var mutex1=1,mutex2=1,s1=n,s2=-m:semaphore;

CHAPTER 3. 九阴真经之研究生题辑22

cobegin process p1 begin repeat get data; p(s1);

p(mutex1);

写数据到buf1; v(mutex1); v(s2); end

process p2 begin repeat; get data; p(s2);

p(mutex2); 写数据到buf2; v(mutex2); v(s1); end coend end

_思考：

p1和p2每次执行时需要进行一些额外的操作．对于p2来说，它首先必须在自己的 缓冲区buf2中写入至少m个数据，此后p1和p2的同步可简单通过两个信号量来控制．题目的一个变形是要求：-m·(buf2数据个数－buf1数据个数)·n;那么信号量的初值就变成m和n,若只有p1向buf1放入数据而p2不放入数据到buf2中，则p1最多可放m次．因此，设臵信号量s1,初值为m,此外，每当p2放入一个数据到buf2中时，则使信号量s1增１，即p1增加一次放入数据到buf1的机会．反之，若只有p2向buf2放入数据而p1不放入数据到buf1中，则p2最多可放次．因此，设臵信号量s2,初值为n,此外，每当p1放入一个数据到buf1中时，则使信号量s2增１，即p2增加一次放入数据到buf1的机会．

The P,V code Using Pascal

begin

var mutex1=1,mutex2=1,s1=m,s2=n:semaphore; cobegin process p1 begin repeat get data; p(s1);

p(mutex1); 写数据到buf1;

CHAPTER 3. 九阴真经之研究生题辑23

v(mutex1);

v(s2);//p1每放入一个数据到buf1同时使s2增加１ end

process p2

begin repeat; get data; p(s2);

p(mutex2); 写数据到buf2; v(mutex2);

v(s1);//p2每放入一个数据到buf2同时使s1增加１ end coend end

三华南理工2000

一个从键盘输入到打印机输出的数据处理流程图如图所示。其中键盘输入进程通过缓冲区buf1把数绝传送给计算进程，计算进程把处理结果通过buf2传送给打印进程。假设上述两个缓冲区的大小分别为n1和n2，试写出键盘输入进程、计算进程及打印进程间的同步算法。 问题分析：

本题解决的试具有多个缓冲区的生产者和消费者之间的多阶段同步问题。由于每个缓冲区中均有多个存储单元，因而要护持使用。所以要为每个缓冲区设臵一个互斥信号量。

The P,V code Using Pascal

Begin

var empty1,empty2,full1,full2,mutex1,mutex2:semaphore; empty1:=n1; empty2:=n2; full1:=0; full2:=0;

mutex1:=mutex2:=1; cobegin

procedure Input procedure Calculate procedure Print_Out begin begin begin

Input a data; p(full1); p(full2); p(empty1); p(mutex1); p(mutex2);

p(mutex1); Get from buf1; Get Data from buf2;

CHAPTER 3. 九阴真经之研究生题辑24

Put to buf1; v(mutex1); v(mutex2); v(mutex1); v(empty1); v(empty2);

v(full1); Calculate it; Print out the data; end p(empty2); end p(mutex2);

put result to buf2; v(mutex2);

v(full2); end coend

四真经之生产者消费者扩展(同济1996)

设有N个计算进程和M个打印进程共享同一个缓冲区，缓冲区长度为8。各计算进程不断地把计算得到的结果送入缓冲区，各打印进程不断的从缓冲区取数并打印。要求：既不漏打，也不重复打印任一个结果。并且，为了高效地工作，计算机进程在使用缓冲区的同时，允许打印进程从缓冲区中取数，反之亦然。请用P、V操作作为同步机制，并用类PASCAL或类C，描述对应于计算进程和打印进程的程序。

五真经之理发师问题扩展(电子科技大学2000)

有一个理发师,一把理发椅和n把供等候理发的顾客坐的椅子,若没有顾客,则理发师睡觉,当一个顾客到来时,必须唤醒理发师进行理发, 若理发师正在理发,又有顾客到来,则若有空椅子可坐就坐下来等,若没有空椅子就离开.

问题分析：需要设臵一个信号量barber,初值为0,用于控制理发师和顾客之间的同步关系.还需要设臵一个信号量customer,初值为0,用于离开顾客与等候顾客之间的同步控制,为了记录等候的顾客数, 应该设臵一个计数器count,初值为0.当一个顾客到达时,需要在count上做加1操作,并根据count值的不同分别采取不同的动作，当顾客离开时,要对count上做减1操作,并根据count值的不同分别采取不同的动作;由于count是共享变量,因此要互斥使用，为此设臵一个互斥信号量mutex;

The P,V code Using Pascal

begin

var barber=0,customer=0,count=0,mutex=1:semaphore; cobegin

process barber begin repeat

p(customer); p(mutex);

count = count -1; v(barber); v(mutex); 理发; until false end

CHAPTER 3. 九阴真经之研究生题辑25

process customer begin repeat; p(mutex); if(count

count = count +1; v(customer); p(barber); 理发； } else{ v(mutex); 离开； }

until false end coend end

_思考：

有3个理发师,3把理发椅子,n把供等候理发的顾客坐的椅子.由于有3位理发师,所以一次同时可以为三个顾客服务,设臵信号量max capacity, 用于表示空闲椅子的数量,初值为n.信号量barber chair表示空闲理发师(椅) 的数量,初值为3;信号量cust ready,finished,leaveb chair分别表示是否有顾客到来,理发完成,离开理发椅,它们的初值都为0;

The P,V code Using Pascal

begin

var max_capacity=n,barber_chair=3,cust_ready=0,finished=0, leave_b_chair = 0:semaphore; cobegin

process barber begin repeat

p(cust_ready); 理发; until false end

process customer begin repeat;

p(max_capacity);//是否有空闲椅子； 进入店里；

p(barber_chair);//是否有空闲的理发椅； 坐在理发椅上；

v(cust_ready);//唤醒理发师；

CHAPTER 3. 九阴真经之研究生题辑26

p(finished);//是否完成理发； 离开理发椅；

v(leave_b_chair); 离开店；

v(max_capacity); until false end coend end

六真经之读者写者问题扩展(南航2001)

问题描述：

一个主修动物行为学、辅修计算机科学的学生参加了一个课题，调查花果山的猴子是否能被教会理解死锁。他找到一处峡谷，横跨峡谷拉了一根绳索（假设为南北方向），这样猴子就可以攀着绳索越过峡谷。只要它们朝着相同的方向，同一时刻可以有多只猴子通过。但是如果在相反的方向上同时有猴子通过则会发生死锁（这些猴子将被卡在绳索中间，假设这些猴子无法在绳索上从另一只猴子身上翻过去）。如果一只猴子相越过峡谷，它必须看当前是否有别的猴子在逆向通过。请使用P/V 操作来解决该问题。 问题分析：

由于不允许两个方向的猴子同时跨越绳索，所以对绳索应该互斥使用，但同一个方向可以允许多只猴子通过，所以临界区可允许多个实例访问。本题的难点在于位于南北方向的猴子具有相同的行为，当一方有猴子在绳索上时，同方向的猴子可继续通过，但此时要防止零一方的猴子跨越绳索。类比经典的读者/写者问题，可以发现类似之处，但又不完全相同，因为没有类似的写者。进一步分析可将此题归结为两种读者间的同步与互斥问题。

The P,V code Using Pascal

Begin

var mutex,Smutex,Nmutex,SmonkeyCount,NmonkeyCount:semaphore; SmonkeyCount:=0;//从南向北攀越绳索的猴子数量 NmonkeyCount:=0;//从北向南攀越绳索的猴子数量 mutex:=1;//绳索互斥信号量

Smutex:=1;//南方向猴子间的互斥信号量 Nmutex:=1;//北方向猴子间的互斥信号量 cobegin

procedure South_i(i=1,2,3,...) begin

p(Smutex);

if SmonkeyCount==0 then p(mutex);

SmonkeyCount:=SmonkeyCount+1; v(Smutex);

Cross the cordage;

CHAPTER 3. 九阴真经之研究生题辑27

p(Smutex);

SmonkeyCount:=SmonkeyCount-1; if SmonkeyCount==0 then v(mutex); v(Nmutex); end

procedure North_j(j=1,2,3,...) begin

p(Nmutex);

if NmonkeyCount==0 then p(mutex);

NmonkeyCount:=NmonkeyCount+1; v(Nmutex);

Cross the cordage; p(Nmutex);

NmonkeyCount:=NmonkeyCount-1; if NmonkeyCount==0 then v(mutex); v(Nmutex); end coend

七真经之南航2002

进程P1和P2通过两个缓冲区给进程P11、P12、P21、P22传递信息，进程P11、P12取进程P1的信息，进程P21、P22取进程P2的信息。假定这两个缓冲区一样大小，所要传递的信息也与缓冲区一样大，同一时刻只能由一个进程往缓冲区中送信息或取信息。试用PV操作来实现这6个进程之间的同步与互斥关系。

The P,V code Using Pascal

var mutex,S11,S12,S21,S22,empty1, empty2,full1,full2:semaphore; empty1=empty2=1; full1=full2=0; sij=0;(i,j=1,2) mutex=1; cobegin

Procedure P1: procedure P2: begin begin

p(empty1); p(empty2); P(mutex); p(mutex);

put message into buff1; put message into buff2; v(mutex); v(mutex); v(S11); v(s21); v(S12); v(S22); v(fll1); v(full2);

CHAPTER 3. 九阴真经之研究生题辑28

end end

procedure Sij:(i=1,2,j=1,2) begin p(fulli); p(sij); p(mutex);

Get message from buffi; v(mutex); v(emptyi) end coend

八真经之管道通信问题(西北工大2000)

在管道通信机制中，用信号量描述读进程和写进程访问管道文件的过程，假设管道文件大小为10KB. 问题分析：

UNIX系统中，利用一个打开的共享文件来连接两个相互通信的进程，这个共享文件叫管道．作为管道输入的发送进程，以字符流的形式将信息送入管道，而作为管道输出的接收进程，从管道中获取信息．管道通信机制要提供三方面的协调能力：(1)互斥．当一个进程对管道进行读／写操作时，另一个进程必须等待．(2) 同步．当写进程把数据写

入管道后便去睡眠等待，直到输出进程取走数据后唤醒它．若一次写入的数据超过缓冲区剩余空间的大小，当缓冲区满时，写进程必须阻塞，并唤醒读进程。(3)对方是否存在．只有确定对方存在时，才能够进行通信．本题只需要考虑互斥，同步问题。由于只有一对进程访问管道，因此不需要设臵互斥信号量，只要设臵两个同步信号量empty,full．分别表示管道可写和可读．

The P,V code Using Pascal

begin

pipe:array[09] of kilobytes;

ts=10,length,in=0,out=0:integer; empty,full:semaphore=1,0; cobegin

process PipeWriter begin repeat

产生数据； p(empty);

length = data length; while(length>0 and ts>0) begin

pipe[in] = data of 1KB; in = (in+1) mod n;

ts = ts-1;

length = length - 1;

CHAPTER 3. 九阴真经之研究生题辑29

end v(full); end

process Consumer begin repeat; p(full);

从缓冲区取出一件物品; out = (out+1) mod n; ts = ts +1; v(empty); end coend end

九真经之吃水果问题(南京大学2000)

问题描述：

桌上有一空盘，允许存放一只水果。爸爸可向盘中放苹果，也可向盘中放桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定当盘空时一次只能放一只水果供吃者取用，请用P、V原语实现爸爸、儿子、女儿三个并发进程的同步。 问题分析：

在本题中，爸爸、儿子、女儿共用一个盘子，盘中一次只能放一个水果。当盘子为空时，爸爸可将一个水果放入果盘中。若放入果盘中的是桔子，则允许儿子吃，女儿必须等待；若放入果盘中的是苹果，则允许女儿吃，儿子必须等待。本题实际上是生产者-消费者问题的一种变形。这里，生产者放入缓冲区的产品有两类，消费者也有两类，每类消费者只消费其中固定的一类产品。

The P,V code Using Pascal

在本题中，应设臵三个信号量S、So、Sa，信号量S表示盘子是否为空，其初值为l；

信号量So表示盘中是否有桔子，其初值为0；信号量Sa表示盘中是否有苹果，其初值为0。

同步描述如下： S＝1; Sa＝0; So＝0; cobegin

Procedure father; /*父亲进程*/ Procedure son; /*儿子进程*/

Procedure daughter; /*女儿进程*/ coend

Procedure father: begin

while(TRUE) begin

CHAPTER 3. 九阴真经之研究生题辑30

P(S);

将水果放入盘中; if（放入的是桔子） V(So); else V(Sa); end end

Procedure son: begin

while(TRUE) begin P(So);

从盘中取出桔子; V(S); 吃桔子; end end

Procedure daughter: begin

while(TRUE) begin P(Sa);

从盘中取出苹果; V(S); 吃苹果; end end

十真经之安全岛问题(南开1997)

在南开大学至天津大学间有一条弯曲的路，每次只允许一辆自行车通过，但中间有小的安全岛M（同时允许两辆车），可供两辆车在已进入两端小车错车，设计算法并使用P，V实现。 问题分析：

由于安全岛M仅仅允许两辆车停留,本应该作为临界资源而要设臵信号量, 但根据题意,任意时刻进入安全岛的车不会超过两辆(两个方向最多各有一辆), 因此，不需要为M设臵信号量,在路口s和路口t都需要设臵信号量,以控制来自两个方向的车对路口资CHAPTER 3. 九阴真经之研究生题辑31

源的争夺.这两个信号量的初值都是1.此外，由于从s到t的一段路只允许一辆车通

过,所以还需要设臵另外的信号量用于控制,由于M的存在,可以为两端的小路分别设臵一个互斥信号量.

The P,V code Using Pascal

var T2N, N2T,L,M,K:semaphore; T2N:=1; N2T:=1; L:=1; K:=1; M:=2; cobegin

Procedure Bike T2N begin p(T2N); p(L); go T to L; p(M); go into M; V(L); P(k); go K to s; V(M); V(k); V(T2N); end

Procedure Bike N2T begin P(N2T); p(k); go v to k; p(M); go into M; V(k); P(L); go L to T; V(M); V(L); V(N2T); end coend

CHAPTER 3. 九阴真经之研究生题辑32

十一真经之珍珑棋局问题

问题描述：

在一个盒子里，混装了数量相等的黑白围棋子〃现在用自动分拣系统把黑子、白子分开，设分拣系统有二个进程P1 和P2 ，其中P1 拣白子；P2 拣黑子。规定每个进程每次拣一子；当一个进程在拣时，不允许另一个进程去拣；当一个进程拣了一子时，必须让另一个进程去拣．试写出两进程P1 和P2 能并发正确执行的程序。 问题分析：

大家熟悉了生产-消费问题(PC)，这个问题很简单。题目较为新颖，但是本质非常简单即：生产-消费问题的简化或者说是两个进程的简单同步问题。答案如下：

The P,V code Using Pascal

设信号量s1 和s2 分别表示可拣白子和黑子; 不失一般性，若令先拣白子。 var S1 , S2 : semaphore; S1 : = l; S2 ：=0; cobegin

process P1 process P2 begin begin repeat repeat P(S1); p(S2);

pick The white; pick the black; V(S2); v(s1);

until false ; until false; end end coend

十二真经之公交车问题(哈尔滨工业大学2000)

问题描述：

设公共汽车上，司机和售票员的活动分别如下：司机的活动：启动车辆：正常行车；到站停车。售票员的活动：关车门；售票；开车门。在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系？用信号量和P 、V 操作实现它们的同步。 问题分析：

CHAPTER 3. 九阴真经之研究生题辑33

在汽车行驶过程中，司机活动与售票员活动之间的同步关系为：售票员关车门后， 向司机发开车信号，司机接到开车信号后启动车辆，在汽车正常行驶过程中售票员售票，

到站时司机停车，售票员在车停后开门让乘客上下车。因此，司机启动车辆的动作必须

与售票员关车门的动作取得同步；售票员开车门的动作也必须与司机停车取得同步。应

设臵两个信号量：S1 、S2 ;

S1表示是否允许司机启动汽车（其初值为0 ) S2表示是否允许售票员开门（其初值为0 ） 用P 、v 原语描述如下：

The P,V code Using Pascal

var S1,S2 : semaphore ; S1=0；S2=0； cobegin

Procedure driver Procedure Conductor begin begin

while TRUE while TRUE begin begin

P(S1); 关车门； Start; v(s1);

Driving; 售票； Stop; p(s2);

V(S2); 开车门； end 上下乘客； end end coend

十三真经之少林寺问题

问题描述：

某寺庙，有小和尚、老和尚若干．庙内有一水缸，由小和尚提水入缸，供老和尚饮用。水缸可容纳10桶水，每次入水、取水仅为1桶，不可同时进行。水取自同一井中，水井径窄，每次只能容纳一个水桶取水。设水桶个数为3个，试用信号灯和PV操作给出老和尚和小和尚的活动。 问题分析：

CHAPTER 3. 九阴真经之研究生题辑34

从井中取水并放入水缸是一个连续的动作可以视为一个进程，从缸中取水为另一个进程。设水井和水缸为临界资源，引入mutex1,mutex2；三个水桶无论从井中取水还是放入水缸中都一次一个，应该给他们一个信号量count，抢不到水桶的进程只好为等待，水缸满了时，不可以再放水了。设empty控制入水量，水缸空了时，不可取水设full。

The P,V code Using Pascal

var mutex1,mutex2,empty,full,count:semaphore; mutex1:=mutex2:=1; empty:=10; full:=0; count:=3; cobegin

Procedure Fetch_Water Procedure Drink_Water begin begin

while true while true p(empty); p(full); P(count); p(count); P(mutex1); p(mutex2); Get Water; Get water and v(mutex1); Drink water; P(mutex2); p(mutex2);

pure water into the jar; v(empty); v(mutex2); v(count); v(count); end v(full); end coend

十四真经之过桥问题

问题描述：

一座小桥(最多只能承重两个人)横跨南北两岸，任意时刻同一方向只允许一人过桥，南侧桥段和北侧桥段较窄只能通过一人，桥中央一处宽敞，允许两个人通过或歇息。试用信号灯和PV操作写出南、北两岸过桥的同步算法。 问题分析：

桥上可能没有人，也可能有一人，也可能有两人。

CHAPTER 3. 九阴真经之研究生题辑35

两人同时过桥两人都到中间南(北)来者到北(南)段 共需要三个信号量，load用来控制桥上人数，初值为2，表示桥上最多有2人；north用来控制北段桥的使用，初值为1，用于对北段桥互斥；south用来控制南段桥的使用，初值为1，用于对南段桥互斥。

The P,V code Using Pascal

var load,north,south:semaphore; load=2; north=1; south=1; GO_South() P(load); P(north); 过北段桥; 到桥中间; V(north); P(south); 过南段桥; 到达南岸; V(south); V(load); GO_North()

v(test); end v(enter); v(computer); end end coend

十七真经之3进程问题

问题描述：

设有A、B、C三组进程, 它们互斥地使用某一独占型资源R, 使用前申请, 使用后释放.

资源分配原则如下:

k 当只有一组申请进程时, 该组申请进程依次获得R;

k 当有两组申请进程时, 各组申请进程交替获得R, 组内申请进程交替获得R; k 当有三组申请进程时, 各组申请进程轮流获得R, 组内申请进程交替获得R. 试用信号灯和PV操作分别给出各组进程的申请活动程序段和释放活动程序段.

The P,V code Using Pascal

Int Free=1;//设备状态标志 semaphore mutex=1;

semaphore qa=qb=qc=0; //各组等待队列 Int counta=countb=countc= 0;//等待队列长度 A组申请： P(mutex);

if Free==1 then begin Free=0; V(mutex); end else begin counta++; V(mutex); P(qa); end

A组释放： if countb>0 then begin countb--; V(qb); end else begin

if countc>0 then begin countc--;

CHAPTER 3. 九阴真经之研究生题辑42

V(qc); end else begin

if (counta > 0) begin counta--; V(qa); end else begin Free=1; end end end

A组进程活动可以给出B组和C组进程活动。

_思考(南大1997)：

今有三个并发进程R，M，P，它们共享了一个可循环使用的缓冲区B，缓冲区B共有N个单元。进程R负责从输入设备读信息，每读一个字符后，把它存放在缓冲区B的一个单元中；进程M负责处理读入的字符，若发现读入的字符中有空格符，则把它改成“，”；进程P负责把处理后的字符取出并打印输出。当缓冲区单元中的字符被进程P取出后，则又可用来存放下一次读入的字符。请用PV操作为同步机制写出它们能正确并发执行的程序。

The P,V code Using Pascal

var empty,full1,full2,mutex:semaphore; char buffer[n];

int in=0,out1=0,out2=0; empty=N; full1=0; full2=0; mutex=1; cobegin

procedure R; procedure M; procedure P; coend

procedure R: procedure M: procedure P: begin begin begin

while True then while True then while True then begin begin begin char x; char x; char x;

Read a char to x; p(full1); p(full2);

CHAPTER 3. 九阴真经之研究生题辑43

p(empty); p(mutex); p(mutex);

p(mutex); x=buffer[out1]; x=buffer[out2]; buffer[in]=x; if x==\in=(in+1)%N; begin v(mutex); v(mutex); x=\

v(full1); buffer[out1]=x; 输出字符x; end end end

end out1=(out1+1)%N; end v(mutex); v(full2); end end

_思考(北大1996)：

有P1、P2、P3三个进程共享一个表格F，P1对F只读不写，P2对F只写不读，P3对F先读后写。进程可同时读F，但有进程写时，其他进程不能读和写。用(1)信号量和P、V操作。(2)管程编写三进程能正确工作的程序。

The P,V code Using Pascal

答：(1)信号量和P、V操作。这是读--写者问题的变种。 其中，P3既是读者又是写者。读者与写者之间需要互斥， 写者与写者之间需要互斥，为提高进程运行的并发性， 可让读者尽量优先。

var rmutex,wmutex:semaphore; rmutex:=wmutex:=1; count:integer;count:=0; cobegin {

process P1 begin repeat P(rmutex);

count:=count+1;

if count=1 then P(wmutex); V(rmutex); Read F; P(rmutex);

count:=count-1;

if count=0 then V(wmutex); V(rmutex); untile false; end

process P2 begin repeat

CHAPTER 3. 九阴真经之研究生题辑44

P(wmutex); Write F; V(wmutex); untile false; process P3 begin repeat P(rmutex);

count:=count+1;

if count=1 then P(wmutex); V(rmutex); Read F; P(rmutex);

count:=count-1;

if count=0 then V(wmutex); V(rmutex); P(wmutex); Write F; V(wmutex); untile false; end } coend

_思考(国防科技大学1996)：

如图所示，四个进程Pi（i=0?3）和四个信箱Mj（j=0?3），进程间借助相邻信箱传递消息，即Pi每次从Mi中取一条消息，经加工后送入M(i+1)mod4，其中M0、M1、M2、M3分别可存放3、3、2、2个消息。初始状态下，M0装了三条消息，其余为空。试以PV操作为工具，写出Pi（i=0?3）的同步工作算法。

The P,V code Using Pascal

var mutexl , mutexZ , mutex3 ，mutex0 :semaphore; Mutex1＝nutex2:=mutex3:=mutex0:=1;

Empty0,empty1,empty2, empty3; semaphore; empty:=0 ; empty1:=3 ; empty:=2:=empty3:=2; full0 , full1 , full2 , full3:semphore ; full0:=3;full1:=full2:=full3:=0;

in0,in1,in2,in3,out0 ,out2,out3,;intger;

in0:=in1:＝in2:＝in3:=out0:=out1:=out2:=out3:=0; cobegin

CHAPTER 3. 九阴真经之研究生题辑45

process P0 process P1 begin begin repeat repeat P(full0); p(full);

P(mutex0); p(mutex1);

从M0[out0]取一条消息； Get a message from M[out1]; out0:=(out0+1)mod 3; out1:=(out1+1)mod 3; V(mutex0); v(mutex1); V(empty0); v(empty1); 加工消息； 加工消息； P(empty1); p(empty2); P(mutex1); p(mutex2);

消息已M1[in1]; 消息己M2[in2];

In1:=(in1+1) mod 3; In2:=(in2+1)mod 2; V(mutex1); V(mutex2); V(full1); v(full2);

untile false; until false; end end

process P2 process P3 begin begin repeat repeat P(full2); p(full3);

P(mutex2); P(mutex3);

从M2[out2]取一条消息； 从M3[out3] 取一条消息; out2:=(out2+l)mod 2; out3:=(out3+1)mod 2; V(mutex2); v(mutex3); V(empty2); v(empty3); 加工消息； 加工消息； P(empty3); p(empty0); P(mutex3); p(mutex0);

消息己M3[in3]; 消息己MO[in0];

in3:=(in3+1)mod 2 ; In0:=(in0+1)mod 3; V(mutex3); v(mutex0); V(full3); v(full0);

untile false ; until false; end end coend

_思考：

四个进程A、B、C、D都要读一个共享文件F，系统允许多个进程同时读文件F。但限制是进程A和进程C不能同时读文件F，进程B和进程D 也不能同时读文件F。为了使这四个进程并发执行时能按系统要求使用文件，现用PV操作进行管理，请回答下面的问题：

(1)如何定义信号量及初值；CHAPTER 3. 九阴真经之研究生题辑46

(2)在下列的程序中填上适当的P、V操作，以保证它们能正确并发工作： 进程A: 进程B： 进程C： 进程D： begin begin begin begin ... ... ... ...

reade F; reade F; reade F; reade F; ... ... ... ...

end end end end 解答：

(1)定义二个信号量S1、S2，初值均为1，即：S1=1，S2=1。其中进程A和C使用信号量S1，进程B和D使用信号量S2。

(2)从[1]到[8]分别为：P(S1) V(S1) P(S2) V(S2) P(S1) V(S1) P(S2) V(S2)

_思考(北大1996)：

今有k个进程，它们的标号依次为1、2、?、k，如果允许它们同时读文件file，但必须满足条件：参加同时读文件的进程的标号之和需小于K，请使用：1)信号量与P、V操作，2)管程，编写出协调多进程读文件的程序。1)：使用信号量与P、V操作

The P,V code Using Pascal

var waits,mutex:semaphore; numbersum:integer:=0; wait:=0;mutex:=1; cobegin

process readeri(var number:integer;) begin P(mutex);

L: if numbersum+number≥K then begin V(mutex); P(waits); goto L; end

else numbersum:=numbersum+number; V(mutex); Read file; P(mutex);

numbersub:=numbersum-number; V(waits); V(mutex); coend

十八真经之生产消费问题扩展(北大1994)

进程A1、A2，。。。An1通过m个缓冲区向进程B1、B2、￠ ￠ ￠ ,Bn2不断发送消

息。发送和接收工作遵循下列规则：

CHAPTER 3. 九阴真经之研究生题辑47

k 每个发送进程一次发送一个消息，写入一个缓冲区，缓冲区大小等于消息长 度

k 对每个消息，B1，B2，Bn2都须各接收一次，读入各自的数据区内 k m个缓冲区都满时，发送进程等待，没有可读消息时，接收进程等待。 试用P、V操作组织正确的发送和接收工作。 问题分析：

每个缓冲区只要写一次但要读n2次，因此，可以看成n2组缓冲区，每个发送者要同时写n2个缓冲区，而每个接收者只要读它自己的缓冲区。

The P,V code Using Pascal

Sin[n2]=m Sout[n2]=0; cobegin

procedure Aj: while (1) begin

for(i=1;i<=n2;i++) P(Sin[i]); P(mutex);

将数据放入缓冲区 V(mutex);

for(i=1;i<=n2;i++) V(Sout[2]); end

procedure Bi： while (1) begin

P(Sout[i]); P(mutex);

从缓冲区取数 V(mutex); V(Sin[i]); end coend

_思考(北大1994原题)：

判别下列用P、V操作表示同步算法是否正确？如不正确，试说明理由，并修改成正确算法。

VAR buffer : ARRAY 0..N-1 OF T; In, out:0?N-1;

VAR S1,S2:Semaphore; S1:=0;S2：=N； In：=out：=0；

PROCEDURE A：

CHAPTER 3. 九阴真经之研究生题辑48

BEGIN REPEAT

生产数据m； P（S2）；

Buffer(in):=m； In:=(in+1) MODN； V（S1）； Forever END

PROCEDURE B： BEGIN REPEAT V(S2);

m;=buffer(out); 消费m;

Out :=(out+1)MODN; P(S1); forever END

分析：本题目是一个标准的生产者―消费者问题。题中所给的算法与标准算法不同，但考生不能因此就说这个算法不正确。考生须仔细分析试题中所给出的算法。在本题中，进程B在使用缓冲区前（读缓冲区）无需进行任何P操作，即进程B不会因任何原因被阻塞。这与题目中控制要求不相符。因此这个算法实现是错误的。此外，对缓冲区的访问也没有用互斥信号量进行控制。

十九真经之流程问题(北大1991)

问题描述：

设有8个程序prog1,prog2,?prog8。c2同它们在并发系统中执行时有如下图所示的制约关系, 使用P、V操作实现这些程序间的同步。 问题分析：

本题目是用来检查考生对使用P、V操作实现进程间同步的掌握情况。一般地，若要求进程B在进程A之后方可执行时，只需在进程P操作，而在进程A执行完成时对同一信CHAPTER 3. 九阴真经之研究生题辑49

号量进行V操作即可。本题要求列出8个进程（程序）的控制关系，使题目显得较为复杂。但当对进程间的同步理解透彻后，应不难写出对应的程序。解这一类问题还应注意的一点是，要看清图示的制约关系，不要漏掉或多处制约条件。

The P,V code Using Pascal

BEGIN

var s13, s14, s15, s23, s24, s25,s36, s48, s57, s68, s78:semaphore; s13 :=0;s14 :=0;s15 :=0;

s23 :=0;s24 :=0;s25 :=0; s36 :=0; s48 :=0; s57 :=0; s68 :=0; s78 :=0; COBEGIN

prog1： prog2: prog3: prog4: BEGIN BEGIN BEGIN BEGIN do work; do work; V(S13); P(S14); V(s13); V(s23); V(S23); P(S24); V(s14); v(s24); do work; do work; v(s15); v(s25); v(s36); v(s48); END END END END

prog5： prog6 prog7 prog8 BEGIN BEGIN BEGIN BEGIN P(s15); p(s36); P(s57); P(s48); P(s25); do work; Do work; P(s68); Do work; v(s68); V(S78); P(s78); V(57); END END do work; END END COEND END

_思考(北邮2000)：

一组合作进程，执行顺序如图所示，请用P,V操作实现各个进程之间的同步关系。 | 此类问题相对易于处理，出题的样式多样，有些题目不只是让考生实现其过程有时会让考生更正其中的错误或者判断其是否有死锁的可能并更正之。

CHAPTER 3. 九阴真经之研究生题辑50

二十九阴真经之北航篇

1 智取考场

把学生和监考老师都看做进程，学生有N个人，教师1人，考场门口每次只能进出一个人，进考场原则是先来先进，当N个学生都进入考场后，教师才能发试卷。学生交卷后可以离开考场，教师要等收上来全部试卷并封装试卷后才能离开考场。

k 问共需设臵几个进程？

k 使用P,V操作解决上述问题中的同步和互斥关系.

The P,V code Using Pascal

var mutex,Beginready,Testready,Endready:semaphore; //mutex用以标示教室门这个临界资源 //beginready等待考生来全，标示考试开始 mutex:=1;

Beginready:=-(N-1); Testready:=0; Endready:=-(N-1); cobegin

Procedure Student Procedure Teacher P(mutex); P(mutex); Enter; Enter;

v(mutex); v(mutex); Waiting;

P(Beginready);

----------------------------------------------- p(Beginready); Hand Out; v(Beginready);

----------------------------------------------- p(Testready); v(Testready); 答题; 交卷; 离开;

v(Endready);

---------------------------------------------- p(Endready); 封卷离开;

2 读写者问题(2005)

我们将只读数据的进程称为“读者”进程，而写或者修改数据的进程称为“写者”进程，允许多个“读者”同时读数据，但不运行写者与其它读者或者写者进程同时访问数据。另CHAPTER 3. 九阴真经之研究生题辑51

外，要保证：一旦有写者等待，新到达的读者必须等待，直到该写者完成数据访问为止，用P,V 操作实现读者，写者同步。 问题分析：

k 互斥资源：读写者问题，隐含一个互斥资源-读写的问件 k 互斥锁：读文件时不能写，写文件时不能读文件

k 读进程：允许多个文件读，读进程时> 0时，锁定文件，读文件进程< 1时，解 锁；读进程数> 0时，说明读进程拥有锁 k 写进程:拥有锁时写文件

The P,V code Using Pascal

解答：

增加一个信号量w：=1，用以在写进程到达时封锁后续进程 cobegin

procedure Reader procedur Writer begin begin p(w); p(w);

p(rmutex); p(wmutex);

if rcount==0 then 写数据； p(wmutex); v(wmutex); v(rmutex); v(w) v(w); end 读数据； p(rmutex);

rcount:=rcount-1; if rcount==0 then v(rmutex); v(rmutex); end coend

3 吸烟者问题 这个题目很传统，和前面问题一致这里简单阐述一下。这里再给出一个简单解法。 k 三个吸烟者(A,B,C)和一个经销商(D)，三个吸烟者可以吸烟的条件不一样，具 体看经销商往桌子上放的原料

k 每个吸烟者需要一个进程，分别和经销商进行同步 k 互斥资源：桌子

k A,B,C,D四个进程，A表示烟草拥有者，B是纸拥有者，C火柴拥有者，D经销 商

k S实现互斥，表示桌子上是否放有东西

k Sad,Sbd,Scd分别表示进程AD,BD,CD之间的同步

CHAPTER 3. 九阴真经之研究生题辑52

The P,V code Using Pascal

cobegin

经销商烟草拥有者纸拥有者火柴拥有者 begin begin begin begin p(s); p(Sad); p(Sbd); p(Scd);

放原料； 取纸和火柴； 取烟草和火柴； 取纸和烟草； if(纸和火柴) v(s); v(s); v(s);

v(Sad); 吸烟； 吸烟； 吸烟； else end end end if(烟草和火柴) v(Sbd); else v(Scd); end coend

4 生产者-消费者扩展 有n+1个进程A1，A2，￠ ￠ ￠ ,An和B： k (1)A1,A2,￠ ￠ ￠ ,An通过同一个缓冲池各自不断地向B发送消息，B不断地取消 息，它必须取走发来的每个消息，刚开始时缓冲区为空，使用P,v操作实现之。

k (2)若缓冲区个数增至Ｍ个，试用P,V实现正确通讯

这个问题较为简单，请读者自行解决。这里给出参考答案。

The P,V code Using Pascal

var full,empty,mutex:semaphore; full=0; empty=1; mutex=1; cobegin

procedure A_i(i=1,...,n) procedure B: begin begin

p(empty); P(full); p(mutex); p(mutex);

put message to the buffer; Get the message; v(mutex); v(mutex); v(full); v(empty); end end

5 阅览室问题

有一个阅览室，共有100个座位，读者进入时必须先在一张登记表上登记，该表为每一个座位列一表目，包括座号和读者姓名等，读者离开时要消掉登记的信息，试问；

k (1)为描述读者的动作，应编写几个程序，设臵几个进程？

CHAPTER 3. 九阴真经之研究生题辑53

k (2)试用PV操作描述各个进程之间的同步互斥关系。 问题分析：

读者动作有两个，一个时填表进入阅览室，这时要考虑阅览室里是否有空位；一是读者阅读完毕，离开阅览室，这时的操作要考虑阅览室里是否有读者。读者在阅览室读书时，由于没有引起资源的变动，不算动作变化。

算法的信号量有三个：seats-表示阅览室时否有座位(初值为100)；readers-表示阅览室里的读者数，初值为0；用于互斥的mutex，初值为1。

The P,V code Using Pascal

var seats, raaders,mutex:semaphore; seats:=100; readers:=0; mutex:=1; cobegin

procedure Enter begin

while TRUE begin

p(seats); //没有座位则离开 p(mutex); //进入临界区 填写登记表；

进入阅览室阅读； v(mutex); //离开临界区 v(readers); end end

procedure Leave begin

while TRUE begin

p(readers); p(mutex); 消掉登记； 离开阅览室； v(mutex); v(seats); end end coend

_思考：

某超市可同时供100人购物，入口处备有篮子，每个购物者可带一个篮子入超市购物，出口时结账并归还篮子(出入口仅容一人)。

CHAPTER 3. 九阴真经之研究生题辑54

6 P,V改错(2001)

设有两个优先级相同的进程P1，P2如下。令信号S1，S2的初值为0，已知z=2，试问P1，P2并发运行结束后x=？y=？z=？ 进程P1 进程P2 y:=1； x:=1；

y:=y+2； x:=x+1； V(S1)； P(S1)； z:=y+1； x:=x+y； P(S2)； V(S2)； y:=z+y； z:=x+z；

受信号量S1和S2的控制，进程P1和P2中P,V操作的顺序应明确。但当进程P2执行v(S2)调用后，可能会产生这种情形，即P2中的语句“z:=x+z”可以在P1中的语句“y:=z+y”前面或后面执行，因而P1和P2并发运行结束后，有两种可能的结果。即： x=5、y=12、z=9或x=5、y=7、z=9。 7 面包店(2001)

面包师有很多面包，由n个销售人员推销。每人顾客进店后先取一个号，并且等待叫号。当一个销售人员空闲下来时，就叫下一个号。试设计一个使销售人员和顾客同步的算法。 问题分析：

该题目和银行排队问题一致的。解法一样！！ 8 公交车问题(2002)

在一辆公共汽车上，司机和售票员各行其职，司机负责开车和到站停车；售票员负责售票和开、关门，当售票员关好车门后，司机才能继续开车行驶。试用P、V操作实现司机与售票员之间的同步。 9 P,V改错(2002)

下面是两个并发执行的进程。它们能正确运行吗？若不能请举例说明，并改正之： parbegin var x:integer;

process P1 process P2

var y, z:integer; var t, u:integer; begin begin x:=1; x:=0; y:=0; t:=0;

if x≥1 then y:=y+1; if x≤1 then t:=t+2; z:=y; u:=t; end end parend

CHAPTER 3. 九阴真经之研究生题辑55

他们不能正确运行。因为题中的进程P1和P2之间有一个共享变量X，由于进程的并发执行，可能会产生与时间有关的错误。比如进程P1先于P2运行，程序执行完成后Z的值是1，u的值为2.但若进程P1 执行到赋值语句“X：=1”后，进程调度P2运行，此时X的值又被重新赋值为0，待进程P2运行结束后，进程P1运行，当两个进程都结束运行时，Z的值0，u的值2.若要使P1和P2能正确执行，必须设臵一互斥信号量，以便对P1和P2中的临界区互斥使用。改正后的程序如下：

The P,V code Using Pascal

parbegin var x:integer;

mutex:semaphore; process P1 process P2

var y, z:integer; var t, u:integer; begin begin

p(mutex); p(mutex); x:=1; x:=0; y:=0; t:=0;

if x≥1 then y:=y+1; if x≤1 then t:=t+2; v(mutex); v(mutex); z:=y; u:=t; end end parend__

本文来源：https://www.bwwdw.com/article/jpzo.html