进程同步经典习题

例题1（北京大学1999年）有一个仓库，可以存放A和B两种产品，仓库的存储空间足够大，但要求：(1)一次只能存人一种产品（(A或B);(2)一N< A产品数量一B产品数量＜M其中，N和M是正整数。

试用“存放A’和‘存放B’以及P操作和V操作描述产品A和产品B的人库过程。

解答：应先将表达式转换成制约条件，不可在程序中直接使用该表达式将表达式分解为：B产品数量—A产品数量<NA产品数量—B产品数量＜M可这样理解：(1)若只放人A产品，而不放入B产品，则A产品最多可放M—1次便被阻塞，即A进程每操作一次就应当将计数器减1（计数器初值为M—1），当计数器值为0时，进程程A被阻塞；每当放入一个B产品，则可令A产品的计数器增加1，表明A产品可以多一次放入产品的机会；同理，(2)若只放人B产品，而不放入A产品，则B产品最多可；放N一1次便被阻塞，即A进程每操作一次就应当将计数器减1（计数器初值为N—1）。

当计数器值为0时，进程B被阻塞；每当放人一个A产品，则可令B产品的计数器增加1，表明B产品可以多一次放入产品的机会。

由此可见，该问题是一个同步控制问题。

又因为一次仅允许一种产品人库，设置信号量mutex控制粮进程互斥访问临界资源（仓库）。

过程如下：beginmutex:＝1;Sa := M-1;Sb := N-1；ParbeginA产品beginrepeatP (Sa)；P (mutex)；A人库；V (mutex)；V (Sb)；Until false;End;B产品beginrepeatP (Sb)；P (mutex)；B人库；V (mutex)；V (Sa)；Until false;End;rend;例题2（华中理工大学1999年试题）设公共汽车上，司机和售票员的活动分别是：司机：售票员：启动车辆上乘客正常行车关车门到站停车售票开车门下乘客在汽车不断地到站，停车，行驶过程中，这两个活动有什么同步关系？并用信号灯的P, V操作实现它们的同步。

补充题1：有三个进程p1、p2、p3协作解决文件打印问题：系统有两个环形缓冲池，每个缓冲池有n个缓冲区；p1每次将1条记录从磁盘读入缓冲池1，p2每次将1条记录从缓冲池1复制到缓冲池2，p3每次从缓冲池2取出1条记录打印输出。

请用信号量机制实现这三个进程的同步。

信号量提示：full1、empty1、mutex1、in1、out1；full2、empty2、mutex2、in2、out2。

答：方法1,记录型信号量机制：var mutex1、mutex2、empty1、empty2、full1、full2：semaphore:=1，1，n，n，0，0；buffer1:array[0，…，n-1] of item;buffer2:array[0，…，n-1] of item;int1，out1，int2，out2:integer:=0，0，0，0；p1进程：beginrepeat……从磁盘读入一条记录到nextp；……Wait(empty1);Wait(mutex1);Buffer1(int1):=nextp;In1: =(int1+1) mod n;Signal(mutex1);Signal(full1);Until false;EndP2进程：BeginRepeatWait(full1);Wait(mutex1);Nextc:=buffer1(out1);Out1:=(out1+1) mod n;Signal(mutex1);Signal(empty1);从buffer1取出1条记录；Until false;……repeat……Wait(empty2);Wait(mutex2);Buffer2(int2):=nextp;In2: =(int2+1) mod n;Signal(mutex2);Signal(full2);把记录放入buffer2中；Until false;EndP3进程：BeginRepeatWait(full2);Wait(mutex2);Nextc:=buffer2(out2);Out2:=(out2+1) mod n;Signal(mutex2);Signal(empty2);从buffer2取出1条记录打印；Until false;End方法2,AND型信号量机制var mutex1、mutex2、empty1、empty2、full1、full2：semaphore:=1，1，n，n，0，0；buffer1:array[0，…，n-1] of item;buffer2:array[0，…，n-1] of item;int1，out1，int2，out1，out2，:integer:=0，0，0，0；p1进程：beginrepeat……从磁盘读入一条记录到nextp；……SWait(empty1，mutex1);Buffer1(int1):=nextp;In1: =(int1+1) mod n;SSignal(mutex1，full1);Until false;EndP2进程：BeginRepeatSWait(full1，mutex1);Nextc:=buffer1(out1);Out1:=(out1+1) mod n;SSignal(mutex1，empty1);从buffer1取出1条记录；Until false;…………SWait(empty2，mutex2);Buffer2(int2):=nextp;In2: =(int2+1) mod n;SSignal(mutex2 ，full2);把记录放入buffer2中；Until false;EndP3进程：BeginRepeatSWait(full2，mutex2);Nextc:=buffer2(out2);Out2:=(out2+1) mod n;SSignal(mutex2，empty2);从buffer2取出1条记录打印；Until false;End补充题2：上题中如果两个缓冲池都是单缓冲区，则如何简化各进程的描述？提示：单缓冲区，故上题中的mutex、in、out均不需要。

一、选择题1、我们把在一段时间内，只允许一个进程访问的资源，称为临界资源，因此，我们可以得出下列论述，请选择一条正确的论述。

A 、对临界资源是不能实现资源共享的B 、对临界资源，应采取互斥访问方式，来实现共享C 、为临界资源配上相应的设备控制块后，便能被共享D 、对临界资源应采取同时访问方式，来实现共享2、在多进程的系统中，为了保证公共变量的完整性，各进程应互斥进入临界区。

所谓临界区是指_______。

A 、一个缓冲区B 、一段数据区C 、同步机制D 、一段程序3、在操作系统中，信号量表示资源实体，信号量表示资源实体，是一个与队列有关的是一个与队列有关的_________变量，其值仅能用P 、V 操作来改变。

A 、实体B 、整形C 、布尔型D 、记录型4、用P 、V 操作可以解决_______互斥问题。

A 、某些B 、一个C 、一切D 、大多数5、对于记录型信号量，在执行一次P 操作时，信号量值应当_____A__A_（3）___;当其值为______B_B_（4）__时，进程应阻塞。

在执行V 操作时，信号量的值应当______C C （2）___；当其值为____D_D_（3）__时，应唤醒阻塞队列中的进程。

A 、C ：（1）不变；（2）加1；（3）减1；（4）加指定数值；（5）减指定数值B 、D ：（1）大于0；（2）大于等于0；（3）小于等于0；（4）小于0 6、对于两个并发进程，其互斥信号量为mutex ；若mutex=0，则表明_______。

A 、没有进程进入临界区B 、有一个进程进入临界区但没进程处于阻塞状态C 、一个进程进入临界区而另一个进程正处于等待进入临界区状态D 、有两个进程进入临界区7、设有5个进程共享一个互斥段，如果允许有3个进程同时进入互斥段，则所采用的互斥信号量的初值应是__________。

A 、5 B 、3 C 、1 D 、0 8、N 个进程共享某一临界资源，则互斥信号量的取值范围为_________。

1. 若有一个文件F ，供进程共享。

现把进程分成A 、B 两组，规定同组的进程可以同时读文件F ，但当有A 组(或B 组)的进程在读文件F 时不允许B 组(或A 组)的进程读文件F 。

现定义两个计数器C1和C2分别记录A 组和B 组中读文件F 的进程数。

当用P 、V 操作进行管理时需要三个信号量Sl Sl、、S2和SAB 才能保证正确的并发执行。

程序结构如下：Begin Sl ，S2S2，，SAB SAB：：semaphore semaphore；；C1C1，，C2C2：：integer integer；；S1:=1;S2:=1 ；SAB SAB：：=1;C1=1;C1：：=0=0；；C2C2：：=0=0；；cobeginprocess Ai(i=1，2，…，…) )begin((1))；C1：=C1十1;if Cl=1 then((2))；((3))；read file F((4))C1:=C1—1；if Cl=0 then((5))((6))；end ；process Bj(j=1，2，…，…) )begin((7))；C2：=C2十1;if C2=1 then((8))；((9));read file F ；((10));C2：=C2=C2——1;if C2=0 then((11))；((12))； end ；coend ；end ；回答：1．说明信号量S1，S2,SAB 的作用的作用2. 在上述程序的括号内填入适当的P 、V 操作，完善该程序。

操作，完善该程序。

2.一座山上有一个隧道，规定每次只允许一列火车过隧道，现在南方北方都有车要过隧道，如果把每个过隧道者看作一个进程，为保证安全．请用PV 操作实现正确管理。

理。

3.桌上有一个空盒，盒内只允许放一个水果，甲可向盒内放苹果，乙可向盒内放桔子。

丙专等吃盒中的苹果，丁专等吃盒中的桔子，若盒内已有水果，放者必须等待，若盒内没有自己要吃的水果，吃者必需等待，请回答下列问题：(1)(1)请给出四个之间的同步互斥关系。

（一）图书馆有100个座位，每位进入图书馆的读者要在登记表上登记，退出时要在登记表上注销。

要几个程序？有多少个进程？（答：一个程序；为每个读者设一个进程）（1）当图书馆中没有座位时，后到的读者在图书馆为等待（阻塞）（2）当图书馆中没有座位时，后到的读者不等待，立即回家。

解（1 )设信号量：S=100; MUTEX=1 P(S)P(MUTEX)登记V(MUTEX)阅读P(MUTEX)注销V(MUTEX)V(S) 解(2)设整型变量COUNT=100; 信号量：MUTEX=1;P(MUTEX);IF (COUNT==0){ V(MUTEX);RETURN;}COUNT=COUNT-1;登记V(MUTEX);阅读P(MUTEX);COUNT=COUNT+1;V(MUTEX); RETURN;（二）一家四人父、母、儿子、女儿围桌而坐；桌上有一个水果盘；（1）当水果盘空时，父亲可以放香蕉或者母亲可以放苹果，但盘中已有水果时，就不能放，父母等待。

当盘中有香蕉时，女儿可吃香蕉，否则，女儿等待；当盘中有苹果时，儿子可吃，否则，儿子等待。

解设信号量：SE=1 (空盘子)；SA＝0 （放了苹果的盘子）；SB=0 (放了香蕉的盘子)父亲REPEAT剥香蕉P(SE)放香蕉V(SB)UNTIL FALSE 母亲REPEAT削苹果P(SE)放苹果V(SA) UNTIL FALSE儿子P(SA) 拿苹果V(SE) 吃苹果女儿P(SB) 拿香蕉V(SE) 吃香蕉（2）解：再增加两个信号量：SF=0, SM=0父亲REPEATP(SF)剥香蕉P(SE)放香蕉V(SB)UNTIL FALSE 母亲REPEATP(SM)削苹果P(SE)放苹果V(SA) UNTIL FALSE儿子V(SM) P(SA) 拿苹果V(SE) 吃苹果女儿V(SF) P(SB) 拿香蕉V(SE) 吃香蕉（三）有一个超市，最多可容纳N个人进入购物，当N个顾客满员时，后到的顾客在超市外等待；超市中只有一个收银员。

1、理发店理有一位理发师、一把理发椅和n 把供等候理发的顾客坐的椅子，如果没有顾客，理发师便在理发椅上睡觉。

一个顾客到来时，它必须叫醒理发师。

如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，就坐下来等待，否则就离开。

2、苹果桔子问题桌上有一只盘子，每次只能放入一只水果；爸爸专向盘子中放苹果(apple)，妈妈专向盘子中放桔于(orange)，一个儿子专等吃盘子中的桔子，一个女儿专等吃盘子里的苹果。

使用记录型信号量解决苹果桔子问题。

3、一座山有一个隧道，规定每次允许一列火车过隧道，现在南方北方都有车要过隧道。

如果把每个过隧道火车都看作一个进程，为保证安全，请用wait和signal原语操作实现正确管理。

var waiting : integer; /*等候理发的顾客数*/ CHAIRS:integer; /*为顾客准备的椅子数*/ customers, barbers，mutex : semaphore;customers := 0; barbers := 0; waiting := 0; mutex := 1;Procedure barber;beginwhile(TRUE); /*理完一人,还有顾客吗?*/P(cutomers); /*若无顾客,理发师睡眠*/P(mutex); /*进程互斥*/waiting := waiting – 1; /* */V(barbers); /*理发师去为一个顾客理发*等候顾客数少一个/V(mutex); /*开放临界区*/cut-hair( ); /*正在理发*/end;procedure customerbeginP(mutex); /*进程互斥*/if waiting<CHAIRS begin /*看看有没有空椅子*/waiting := waiting+1; /* 等候顾客数加1*/V(customers); /*必要的话唤醒理发师*/V(mutex); /*开放临界区*/P(barbers); /*无理发师, 顾客坐着养神*/get-haircut( ); /*一个顾客坐下等理发*/endV(mutex); /*人满了,走吧!*/end;varplate : integer;sp:semaphore；/* 盘子里可以放几个水果*/sg1:semaphore; /* 盘子里有桔子*/sg2:semaphore; /* 盘子里有苹果*/sp := 1; /* 盘子里允许放一个水果*/Sg1, := 0; /* 盘子里没有桔子*/sg2 := 0; /* 盘子里没有苹果*/cobeginprocess fatherbeginL1:削一个苹果；P(sp);把苹果放入plate；V(sg2);goto L1;end;process mother beginL2:剥一个桔子；P(sp);把桔子放入plate；V(sg1);goto L2;end;process sonbeginL3: P(sg1);从plate中取桔子；V(sp);吃桔子；goto L3;end;process daughter beginL4: P(sg2);从plate中取苹果；V(sp);吃苹果；goto L4;end;coend设信号量s表示隧道的互斥信号量，初始值为1。

新版进程同步典型例题(总11页)本页仅作为文档封面，使用时可以删除This document is for reference only-rar21year.March进程同步练习题1. 在公共汽车上，司机和售票员的工作流程如图所示。

为保证乘客的安全，司机和售票员应密切配合协调工作。

请用信号量来实现司机与售票员之间的同步。

司机售票员图司机和售票员工作流程图2. 桌子上有一只盘子，盘子中只能放一只水果。

爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，一个儿子专等吃盘子中的橘子，一个女儿专等吃盘子中的苹果。

用PV操作实现他们之间的同步机制。

3. a，b两点之间是一段东西向的单行车道，现要设计一个自动管理系统，管理规则如下：（1）当ab之间有车辆在行驶时同方向的车可以同时驶入ab段，但另一方向的车必须在ab 段外等待；（2）当ab之间无车辆在行驶时，到达a点（或b点）的车辆可以进入ab段，但不能从a 点和b点同时驶入；（3）当某方向在ab段行驶的车辆驶出了ab段且暂无车辆进入ab段时，应让另一方向等待的车辆进入ab段行驶。

请用信号量为工具，对ab段实现正确管理以保证行驶安全。

4．将只读数据的进程称为“读者”进程，而写或修改数据的进程称为“写者”进程。

允许多个“读者”同时读数据，但不允许“写者”与其他“读者”或“写者”同时访问数据。

另外，要保证：一旦有“写者”等待时，新到达的“读者”必须等待，直到该“写者”完成数据访问为止。

试用P、V操作正确实现“读者”与“写者”的同步。

（第二类读者写者问题，信号量解决方法）5．一条河上架设了由若干个桥墩组成的一座桥。

若一个桥墩只能站一个人，过河的人只能沿着桥向前走而不能向后退。

过河时，只要对岸无人过，就可以过。

但不允许河对岸的两个人同时过，以防止出现死锁。

请给出两个方向的人顺利过河的同步算法。

6．有一个仓库，可以存放A和B两种产品，但要求：（1）每次只能存入一种产品（A或B）；（2）-N＜A产品数量－B产品数量＜M。

进程同步练习题1．第二类读者写者问题，信号量解决方法2．复印室里有一个操作员为顾客复印资料，有5把椅子供顾客休息等待复印。

如果没有顾客，则操作员休息。

当顾客来到复印室时，如果有空椅子则坐下来，并唤醒复印操作员；如果没有空椅子则必须离开复印室。

3．如果有三个进程R、W1、W2共享一个缓冲器B，而B中每次只能存放一个数。

当缓冲器中无数时，进程R可以将从输入设备上读入的数存放到缓冲器中。

若存放到缓冲器中的是奇数，则允许进程W1将其取出打印；若存放到缓冲器中的是偶数，则允许进程W2将其取出打印。

同时规定：进程R必须等缓冲区中的数被取出打印后才能再存放一个数；进程W1或W2对每次存入缓冲器的数只能打印一次；W1和W2都不能从空缓冲中取数。

写出这三个并发进程能正确工作的程序。

4．现有四个进程R1、R2、W1、W2，它们共享可以存放一个数的缓冲器B。

进程R1每次把来自键盘的一个数存入缓冲器B中，供进程W1打印输出；进程R2每次从磁盘上读一个数存放到缓冲器B中，供进程W2打印输出。

为防止数据的丢失和重复打印，问怎样用信号量操作来协调这四个进程的并发执行。

5．有一个仓库，可以存放A和B两种产品，但要求：（1）每次只能存入一种产品（A或B）；（2）-N＜A产品数量－B产品数量＜M。

其中，N和M是正整数。

试用同步算法描述产品A与产品B的入库过程。

6．设有两个生产者进程A、B和一个销售者进程C，他们共享一个无限大的仓库，生产者每次循环生产一个产品，然后入库供销售；销售者每次循环从仓库中取出一个产品进行销售。

如果不允许同时入库，也不允许边入库边出库；而且要求生产和消费A产品和B产品的件数都满足以下关系：-n≤A的件数－B的件数≤m，其中n、m是正整数。

1. 第二类读者写者问题，信号量解决方法答：为了使写者优先，可在原来的读优先算法的基础上增加一个互斥信号量s，初值为1，使得当至少有一个写者准备访问共享对象时，它可以使后续的读者进程等待完成；整型变量writecount，初值为0，用来对写者进行计数；互斥信号量mutex，初值为1，用来实现多个读者对写者writecount进行互斥访问。

1、测量控制系统中的数据采集任务把所采集的数据送一单缓冲区；计算任务则从该缓冲区中取出数据并进行计算。

试写出利用信号量机制实现两者共享单缓冲区的同步算法。

Var Sempty，Sfull: semaphore:= 1,0BeginParbeginCollection:beginrepeat采集一个数据；wait(Sempty);数据放入缓冲区；signal(Sfull);untill false;end;Compute:beginrepeatwait(Sfull);从缓冲区取出数据;signal(Sempty);计算;` until false;end;ParendEnd2、有一阅览室，共有100个座位。

读者进入时必须先在一种登记表上登记，该表为每一座位列一个表目，包括座号和读者姓名。

读者离开时要注销掉登记内容。

试用wait和signal原语描述读者进程的同步问题。

var mutex, readcount :semaphore := 1,100; BeginParbeginProcess Reader:beginrepeatwait(readcount);wait(mutex);<填入座号和姓名完成登记>；signal(mutex);<阅读>wait(mutex)<删除登记表中的相关表项，完成注销>signal(mutex);signal(readcount);until false;end;parend;End;1）、桌上有一空盘，只允许放一个水果，爸爸专向盘中放苹果，妈妈专向盘中放桔子；女儿专吃盘中的苹果，儿子专吃盘中的桔子；试用wait 和signal原语实现爸爸、妈妈、女儿、儿子之间的同步问题。

var Sempty, Sapple, Sorange,: semaphore:= 1,0,0; beginparbeginFather: beginrepeatwait(Sempty);<put apple in tray>;signal(Sapple);until false;end;Mother: beginrepeatwait(Sempty);<put orange in tray>;signal(Sorange);until false;end;Son: beginrepeatwait(Sorange);<take orange>;signal(Sempty);until false;end;Daughter: beginrepeatwait(Sapple);<take apple>;signal(Sempty);until false;end;parend;end;1、在4×100米接力赛中，4个运动员之间存在如下关系，运动员1跑到终点把接力棒交给运动员2；运动员2一开始处于等待状态，在接到运动员1传来的接力棒后才能往前跑，他跑完100米后交给运动员3，运动员3也只有在接到运动员2传来的棒后才能跑，他跑完100米后交给运动员4，运动员4接到棒后跑完全程。

例1：医生进程Doctor，化验进程Lab共同完成病人的诊治工作，医生开化验单，化验进程进行化验，医生根据化验结果进行诊断。

请用记录型信号量和P、V 操作实现两进程的同步。

例2 吃水果问题
例3、某集装箱仓库共有100个仓位，用同一辆吊车负责集装箱的吊进和吊出。

现有一批集装箱运来进仓，另有货主不断前来提货（按仓位顺序进出），设进仓用过程PUTIN表示，出仓用过程GETOUT表示，请用P、V操作协调上述工作。

例4、有一独木桥，每次只允许一人过桥，现在桥的南北两端随时有人要过桥（PASS），为保证安全，请用P、V操作解决如下问题：
1)只要桥上无人则允许任一方的一人过桥，桥上有人则等待。

2)两边的人交替过桥。

即某一方一人过桥后要让另一方的一个人过桥，桥上
有人则等待。

例5、有三个进程PA、PB、PC合作解决文件打印问题：PA将文件记录从磁盘读入主存的缓冲区1，每执行一次读一个记录；PB将缓冲区1的内容复制到缓冲区2，每执行一次复制一个记录；PC将缓冲区2的内容打印出来，每执行一次打印一个记录。

缓冲区的大小等于一个记录的大小。

请用P、V操作协调三个进程的工作。

例6 少林寺问题。

进程同步习题一
1、四个进程P0，P1,P2,P3和四个信箱M0,M1,M2,M3进程间借助相邻的信箱传递消息：Pi 每次从Mi 中取出一条消息，经加工送入Mi+1 （mod 4）中。

其中M0,M1,M2,M3分别设有3,3,2,2个格子，每个格子放一条消息，初始时，M0装满了三条消息，其余为空。

写出使用信号量实现进程(i=0,1,2,3)同步的算法。

2. 有一阅览室，读者进入时必须先在一张登记表上登记。

该表中每个表项代表阅览室中的一个座位。

读者离开时要消掉其登记信息。

阅览室共有50 个座位。

登记表每次仅允许一位读者进行登记或注销。

读者登记时，如果座位已满，他在阅览室外等待，直至有空位再登记进入。

试用伪代码和信号量，描述读者行为。

3. 汽车司机与售票员之间必须协同工作，一方面，只有售票员把车门关好了司机才能开车，因此，售票员关好车门应通知司机开车。

另一方面，只有当司机已经停下，售票员才能开门上下客，故司机停车后应通知售票员。

假定某辆公共汽车上有两名售票员与一名司机，汽车当前正在始发站停车上客，试设必要的信号灯及赋初值，写出他们的同步过程。

进程同步练习题1. 在公共汽车上，司机和售票员的工作流程如图所示。

为保证乘客的安全，司机和售票员应密切配合协调工作。

请用信号量来实现司机与售票员之间的同步。

①约束：怎么密切配合协调工作才能保证安全呢？a) 关车门之后再启动车辆；利用前驱图解释b) 到站停车之后再开车门；②根据约束定义信号量；关车门和启动车辆需要一个信号量进行同步S1；到站停车和开车门之间需要一个信号量进行同步S2；③建立几个进程呢？a) 为司机建立一个进程Driver ；b) 为售票员建立一个进程Conductor；Driver ：Repeat启动车辆；正常行驶；到站停车；Until false;Conductor：Repeat关车门；开车门；Until false;④加入同步关系：Var s1,s2:semorphore=0,0;Driver ：RepeatWait (s1);启动车辆；正常行驶；到站停车；Signal(s2)Until false;Conductor：Repeat 关车门；Signal(s1);Wait(s2)开车门；Until false;main(){Driver();Conductor ();}2. 桌子上有一只盘子，盘子中只能放一只水果。

爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，一个儿子专等吃盘子中的橘子，一个女儿专等吃盘子中的苹果。

用PV 操作实现他们之间的同步机制。

分析：①约束：a) 爸爸和妈妈竞争盘子，往盘子放水果，爸爸在放时，妈妈等待，或者相反；b) 爸爸和女儿要同步，即爸爸放完苹果之后通知女儿来吃；同时女儿吃完之后要通知盘子可用；c) 妈妈和儿子要同步，即妈妈放完橘子之后通知儿子来吃；同时儿子吃完之后要通知盘子可用；②经上述分析可知：需要3个信号量：S1表示临界资源盘子，初值1；爸爸和女儿需要一个信号量进行同步S2=0妈妈和儿子需要一个信号量进行同步S3=0;③建立进程？爸爸：妈妈：女儿：儿子：Repeat repeat repeat repeat取一个苹果；取一个橘子；从盘子取一个苹果；从盘子取一个橘放入盘子；放入盘子吃苹果；吃橘子；Until false; Until false; Until false; Until false;④ 加入同步关系。