进程同步典型例题操作系统.docx

1、进程同步典型例题操作系统进程同步练习题1. 在公共汽车上，司机和售票员的工作流程如图所示。为保证乘客的安全，司机和售票员应密切配合协调工作。请用信号量来实现司机与售票员之间的同步。图 司机和售票员工作流程图1 约束：怎么密切配合协调工作才能保证安全呢？a) 关车门之后再启动车辆；利用前驱图解释b) 到站停车之后再开车门；2 根据约束定义信号量；关车门和启动车辆需要一个信号量进行同步S1；到站停车和开车门之间需要一个信号量进行同步S2；3 建立几个进程呢？a) 为司机建立一个进程Driver；b) 为售票员建立一个进程Conductor；Driver： Repeat 启动车辆；正常行驶； 到站停

2、车； Until false;Conductor： Repeat关车门； 售票； 开车门； Until false;4 加入同步关系：Var s1,s2:semorphore=0,0; Driver： Repeat Wait (s1); 启动车辆；正常行驶； 到站停车； Signal(s2) Until false;Conductor： Repeat关车门； Signal(s1); 售票；Wait(s2) 开车门； Until false;main() Driver(); Conductor ();2. 桌子上有一只盘子，盘子中只能放一只水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，一个儿

3、子专等吃盘子中的橘子，一个女儿专等吃盘子中的苹果。用PV操作实现他们之间的同步机制。分析：约束：a) 爸爸和妈妈竞争盘子，往盘子放水果，爸爸在放时，妈妈等待，或者相反；b) 爸爸和女儿要同步，即爸爸放完苹果之后通知女儿来吃；同时女儿吃完之后要通知盘子可用；c) 妈妈和儿子要同步，即妈妈放完橘子之后通知儿子来吃；同时儿子吃完之后要通知盘子可用； 经上述分析可知： 需要3个信号量：S1表示临界资源盘子，初值1；爸爸和女儿需要一个信号量进行同步S2=0妈妈和儿子需要一个信号量进行同步S3=0;3 建立进程？爸爸： 妈妈： 女儿： 儿子： Repeat repeat repeat repeat 取一个

4、苹果； 取一个橘子； 从盘子取一个苹果； 从盘子取一个橘子； 放入盘子； 放入盘子 吃苹果； 吃橘子； Until false; Until false; Until false; Until false; 加入同步关系。爸爸： 妈妈： 女儿： 儿子： Repeat repeat repeat repeat wait(S2); wait(S3); 取一个苹果； 取一个橘子； 从盘子取一个苹果； 从盘子取一个橘子； Wait(S1); Wait(S1); signal(S1); signal(S1); 放入盘子； 放入盘子 吃苹果； 吃橘子； Signal(S2); Signal(S3); Un

5、til false; Until false; Until false; Until false;3. a，b两点之间是一段东西向的单行车道，现要设计一个自动管理系统，管理规则如下：（1）当ab之间有车辆在行驶时同方向的车可以同时驶入ab段，但另一方向的车必须在ab段外等待；（2）当ab之间无车辆在行驶时，到达a点（或b点）的车辆可以进入ab段，但不能从a点和b点同时驶入；（3）当某方向在ab段行驶的车辆驶出了ab段且暂无车辆进入ab段时，应让另一方向等待的车辆进入ab段行驶。请用信号量为工具，对ab段实现正确管理以保证行驶安全。分析： 约束：a) ab两点的单行车道是一种临界资源；两端的车辆

6、对该资源进行竞争；b) 同步关系：（1），（3）； 经上述分析可知：首先，设置互斥信号量Sab=1，用于a、b点的车辆互斥进入ab段；然后，分别设置共享变量ab=0用于记录当前ab段上由a点进入的车辆数量；共享变量ba=0用于记录当前ab=段上由b点进入车辆的数量；最后，设置互斥信号量S1=1用于ab段的车辆互斥访问共享变量ab；设置互斥信号量S2=1用于ba段的车辆互斥访问共享变量ba建立进程？semaphore S1=1,S2=1,Sab=1;int ab=ba=0;Pab： pba：Repeat repeatWait(S1) Wait(s2)abcount=abcount+1; baco

7、unt=bacount+1;if abcount=1 then wait(sab) if bacount=1 then wait(sab)signal(S1) signal(s2)进入车道行驶； 进入车道行驶；Wait(s1) Wait(s2)abcount=abcount-1; bacount=bacount-1;if abcount=0 then signal(sab) if bacount=0 then signal(sab) signal(s1) signal(s2); until false; until false;main() Pab(); Pba();5一条河上架设了由若干个桥

8、墩组成的一座桥。若一个桥墩只能站一个人，过河的人只能沿着桥向前走而不能向后退。过河时，只要对岸无人过，就可以过。但不允许河对岸的两个人同时过，以防止出现死锁。请给出两个方向的人顺利过河的同步算法。分析：1 约束：a) 桥属于临界资源，两岸的人对该资源进行竞争；b) 桥上的人数是有限制的，设这个桥由N个桥墩构成，桥上同时只能有N个人过桥，其它人要进行等待。相当于共享资源数。2 设置信号量信号量s：互斥使用桥，初值为1变量count1：方向1上过河人计数器变量count2：方向2上过河人计数器信号量scount1：对方向1上过河人计数器count1的互斥使用，初值为1信号量scount2：对方向2

9、上过河人计数器count2的互斥使用，初值为1信号量scount：代表桥上过河人的计数信号量，初值为桥墩个数N 建立进程Semaphore s, scount1, scount2, scount;int count1, count2;s=1; scount1=1; scount2=1; scount=N;count1=0; count2=0;void direct1(int i)wait(scount1);count1+;if(count1=1) wait(s);signal(scount1);wait(scount); 上桥，过桥，下桥；signal(scount);wait(scount1

10、);count1-;if(count1=0) signal(s);signal(scount1);void direct2(int i)wait(scount2);count2+;if(count2=1) wait(s);signal(scount2);wait(scount);上桥，过桥，下桥；signal(scount);wait(scount2);count2-;if(count2=0) signal(s);signal(scount2);main() cobegin direct1(1); direct1(n); direct2(1); direct2(m); 6有一个仓库，可以存放A

11、和B两种产品，但要求：（1）每次只能存入一种产品（A或B）；（2）-NA产品数量B产品数量M。其中，N和M是正整数。试用同步算法描述产品A与产品B的入库过程。分析： 约束：a) 仓库是一种临界资源，两种产品为之竞争；b) A产品数量不能比B产品数量多M个以上即A产品数量比B产品数量最多多M-1个；A产品数量不能比B产品数量少N个以上即B产品数量比A产品最多多N-1个。2 设置信号量设置互斥信号量mutex互斥使用仓库；设置两个信号量来控制A、B产品的存放数量，sa表示当前允许A产品比B产品多入库的数量（当前允许A产品入库数量）；sb表示当前允许B产品比A产品多入库的数量（当前允许B产品入库数量

12、）。初始时，sa为M一1，sb为N一1。当往库中存放入一个A产品时，则允许存入B产品的数量也增加1;当往库中存放入一个B产品时，则允许存入A产品的数量也增加1。 建立进程semaphore mutex=1，sa=M-1， sb=N-1;process puta() while(1) 取一个产品； wait(sa); wait(mutex); 将产品入库； signal(mutex); signal(sb); process putb() while(1) 取一个产品； wait(sb); wait(mutex); 将产品入库； signal(mutex); signal(sa); main()

13、 cobegin puta(); putb();4将只读数据的进程称为“读者”进程，而写或修改数据的进程称为“写者”进程。允许多个“读者”同时读数据，但不允许“写者”与其他“读者”或“写者”同时访问数据。另外，要保证：一旦有“写者”等待时，新到达的“读者”必须等待，直到该“写者”完成数据访问为止。试用P、V操作正确实现“读者”与“写者”的同步。（第二类读者写者问题，信号量解决方法）分析：1 约束：a) 写者与写者之间需要互斥访问；b) 读者与写者之间需要互斥；（有一个读者在读就让写者等待），因此，此时需要一个计数变量记录读者的数量。c) 允许多个读者同时读数据；d) 一旦有“写者”等待时，新到

14、达的“读者”必须等待，直到该“写者”完成数据访问为止。2 建立进程Write:Repeat 执行读操作Until false;Read:Repeat 执行写操作；Until false;3 设置信号量a) 设置互斥信号量mutex=1实现写者与写者之间的互斥访问；Write:Repeat Wait(mutex) 执行读操作； Signal(mutex);Until false;b) 实现读者与写者之间的互斥，设置整型变量readcount=0记录读者数量，if readcount=1 then wait(mutex)Read：Repeatreadcount+;if(readcount=1) w

15、ait(mutex);执行读操作；readcount- -;if(readcount=0) signal(mutex); until false; 由于readcount 是共享变量，所以读者之间要互斥访问，因此设置一个互斥信号量rmutex=1.Read：RepeatWait(rmutex)readcount+;if(readcount=1) wait(mutex);signal(rmutex)执行读操作；Wait(rmutex)readcount- -;if(readcount=0) signal(mutex);signal(rmutex) until false;c) 要想实现d）的互斥

16、，需让读者和写者再共享一个互斥信号量s，因此设置互斥信号量s=1，一旦有写者等待时，就wait（s）让读者等待。Write:Repeatwait(wmutex);writecount+;if(writecount=1) wait(s);signal(wmutex); Wait(mutex) 执行读操作； Signal(mutex);wait(wmutex);writecount- -;if(writecount=0)signal(s);signal(wmutex);Until false;Read：RepeatWait(s);Wait(rmutex)readcount+;if(readcoun

17、t=1) wait(mutex);signal(rmutex)signal(s);执行读操作；Wait(rmutex)readcount- -;if(readcount=0) signal(mutex);signal(rmutex) until false; 完整代码Process reader() while(1) wait(s);wait(rmutex);if(readcount=0)wait(mutex);readcount+;signal(rmutex);signal(s);perform read operation;wait(rmutex);readcount- -;if(read

18、count=0)signal(mutex);signal(rmutex); Process writer() while(1) wait(wmutex);writecount+;if(writecount=1) wait(s);signal(wmutex); wait(mutex);perform write operation;signal(mutex);wait(wmutex);writecount- -;if(writecount=0)signal(s);signal(wmutex);Main( )cobegin reader(); writer(); 1、在公共汽车上，司机和售票员的工

19、作流程如图所示。为保证乘客的安全，司机和售票员应密切配合协调工作。请用信号量来实现司机与售票员之间的同步。图 司机和售票员工作流程图【答案】设置两个资源信号量：S1、S2。 S1表示是否允许司机启动汽车，其初值为0；S2表示是否允许售票员开门，其初值为0.semaphoere S1=S2=0;void Driver() while(1) wait(S1); 启动车辆； 正常行车； 到站停车； signal(S2); void Busman() while(1) 关车门； signal(S1)； 售票； wait(S2)； 开车门； main() cobegin Driver(); Busman

20、(); 2. 桌子上有一只盘子，盘子中只能放一只水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，一个儿子专等吃盘子中的橘子，一个女儿专等吃盘子中的苹果。用PV操作实现他们之间的同步机制。【答案】信号量S用来实现盘子的互斥访问，S1表示盘子中苹果个数，S2表示盘子中橘子的个数。semaphore S=1,S1=S2=0;void father() while(1) 准备苹果; wait(S); 将苹果放在盘子内； signal(S1); void mother() while(1) 准备橘子; wait(S); 将橘子放在盘子内； signal(S2); void daughter() whi

21、le(1) wait(Sl); 从盘子里拿走苹果； signal(S); 吃苹果; void son() while(1) wait(S2); 从盘子里拿走橘子； signal(S); 吃橘子; main() cobegin father(); mother(); daughter(); son(); 3. a，b两点之间是一段东西向的单行车道，现要设计一个自动管理系统，管理规则如下：（1）当ab之间有车辆在行驶时同方向的车可以同时驶入ab段，但另一方向的车必须在ab段外等待；（2）当ab之间无车辆在行驶时，到达a点（或b点）的车辆可以进入ab段，但不能从a点和b点同时驶入；（3）当某方向在a

22、b段行驶的车辆驶出了ab段且暂无车辆进入ab段时，应让另一方向等待的车辆进入ab段行驶。请用信号量为工具，对ab段实现正确管理以保证行驶安全。【答案】此题是读者-写者问题的变形。设置3个信号量S1、S2和Sab，分别用于从a点进入的车互斥访问共享变量ab（用于记录当前ab段上由a点进入车辆的数量），从b点进入的车互斥访问共享变量ba（用于记录当前ab段上由b点进入车辆的数量）和a、b点的车辆互斥进入ab段。3个信号量的初值分别为1、1和1，两个共享变量ab和ba的初值分别为0、0。semaphore S1=1,S2=1,Sab=1;int ab=ba=0;void Pab() while(1)

23、 wait(S1); if(ab=0) wait(Sab); ab=ab+1; signal(S1); 车辆从a点驶向b点; wait(S1); ab=ab-1; if(ab=0) signal(Sab); signal(S1); void Pba() while(1) wait(S2); if(ba=0) wait(Sab); ba=ba+1; signal(S2); 车辆从b点驶向a点; wait(S2); ba=ba-1; if(ba=0) signal(Sab); signal(S2); main() cobegin Pab(); Pba(); 4. 将只读数据的进程称为“读者”进程，

24、而写或修改数据的进程称为“写者”进程。允许多个“读者”同时读数据，但不允许“写者”与其他“读者”或“写者”同时访问数据。另外，要保证：一旦有“写者”等待时，新到达的“读者”必须等待，直到该“写者”完成数据访问为止。试用P、V操作正确实现“读者”与“写者”的同步。（第二类读者写者问题，信号量解决方法）【答案】为了使写者优先，可在原来的读优先算法的基础上增加一个互斥信号量s，初值为1，使得当至少有一个写者准备访问共享对象时，它可以使后续的读者进程等待；整型变量writecount，初值为0，用来对写者进行计数；互斥信号量wmutex，初值为1，用来实现多个写者对writecount进行互斥访问。P

25、rocess reader() while(1) wait(s);wait(rmutex);if(readcount=0)wait(mutex);readcount+;signal(rmutex);signal(s);perform read operation;wait(rmutex);readcount-;if(readcount=0)signal(mutex);signal(rmutex); Process writer() while(1) wait(wmutex);if(writecount=0)wait(s);writecount+;signal(wmutex);wait(mute

26、x);perform write operation;signal(mutex);wait(wmutex);writecount-;if(writecount=0)signal(s);signal(wmutex);Main( )cobegin reader(); writer(); 5. 一条河上架设了由若干个桥墩组成的一座桥。若一个桥墩只能站一个人，过河的人只能沿着桥向前走而不能向后退。过河时，只要对岸无人过，就可以过。但不允许河对岸的两个人同时过，以防止出现死锁。请给出两个方向的人顺利过河的同步算法。【答案】信号量s：互斥使用桥，初值为1信号量scount1：对方向1上过河人计数器coun

27、t1的互斥使用，初值为1信号量scount2：对方向2上过河人计数器count2的互斥使用，初值为1信号量scount：代表桥上过河人的计数信号量，初值为桥墩个数N变量count1：方向1上过河人计数器变量count2：方向2上过河人计数器Semaphore s, scount1, scount2, scount;int count1, count2;s=1; scount1=1; scount2=1; scount=N;count1=0; count2=0;void direct1(int i)wait(scount1);if(count1=0) wait(s);count1+;signal

28、(scount1);wait(scount); 上桥，过桥，下桥；signal(scount);wait(scount1);count1-;if(count1=0) signal(s);signal(scount1);void direct2(int i)wait(scount2);if(count2=0) wait(s);count2+;signal(scount2);wait(scount);上桥，过桥，下桥；signal(scount);wait(scount2);count2-;if(count2=0) signal(s);signal(scount2);main() cobegin direct1(1); direct1(n); direct2(1); direct2(m); 6、有一个仓库，可以存放A和B两种产品，但要求：（1）每次只能存入一种产品（A或B）；（2）-NA产品数量B产品数量M。其中，N和M是正整数。试用同步算法描述产品A与产品B的入库过程。【答案】A产品的数量不能比B产品的数量少N个以上，A产品的数量不能比B产品的数量多M个以上设置两个信号量来控制A、B产品的存放数量，sa表示当前允许A产品比B产品多入库的数量（当前允许A产品入库数量），即在当前库存量和B产品