操作系统进程同步算法习题精选

1、 进程同步算法习题课【例题1】司机进程：司机进程：while(1)while(1) 启动车辆启动车辆正常驾驶正常驾驶到站停车到站停车售票员进程：售票员进程：while(1)while(1) 关门关门售票售票开门开门用用P P、V V操作解决司机与售票员的问题操作解决司机与售票员的问题分析：分析： 为保证车辆行驶安全，售票员必须关好车门，然后通知司机启动车辆，在行驶过程中售票员不能打开车门，待车到站停稳后，司机通知售票员才能打开车门，如此不断重复。为此，须设置两个信号量S1，S2用来控制司机和售票员的行为，初值都为0。解: 算法如下：司机进程：司机进程：while(1) P(S1) 启动车辆启动

2、车辆正常驾驶正常驾驶 到站停车到站停车 P(S2)售票员进程：售票员进程：while(1)关门关门 P(S1)售票售票 P(S2)开门开门【例题2】1.用P、V操作解决下图之同步问题提示：分别考虑对缓冲区S和T的同步，再合并考虑getcopyputst解:设置四个信号量Sin=1，Sout=0，Tin=1，Tout=0； get： while（1） P(Sin）; 将数放入将数放入S; V(Sout); copy： while（1） P(Sout）; P (Tin）; 将数从将数从S取出放入取出放入T; V (Tout); V(Sin); put： while（1） P(Tout）; 将数从将

3、数从T取走取走; V(Tin); 思考题：思考题： 如果S和T是由多个缓冲区组成的缓冲池，上述算法将如何修改？【例题3】 桌上有一空盘，最多允许存放一只水果。爸爸可向盘中放一个苹果或放一个桔子，儿子专等吃盘中的桔子，女儿专等吃苹果。 试用P、V操作实现爸爸、儿子、女儿三个并发进程的同步。分析：分析： 设置一个信号量S表示空盘子数，一个信号量So表示盘中桔子数，一个信号量Sa表示盘中苹果数，初值分别为1，0，0。解: 算法如下：Father() while(1) P(S); 将水果放入盘中; if(是桔子)P(So); else P(Sa); Son() while(1) P(So) 取桔子 V

4、(S); 吃桔子; Daughter() while(1) P(Sa) 取苹果 V(S); 吃苹果; 【例题4】有一个仓库，可以存放有一个仓库，可以存放A和和B两种产品，但要求：两种产品，但要求：（1 1） 每次只能存入一种产品（每次只能存入一种产品（A或或B）（2 2） NA产品数量产品数量B产品数量产品数量M。其中，其中，N和和M是正整数。试用是正整数。试用P、V操作描述产操作描述产品品A与与B的入库过程。的入库过程。解:分析：设两个同步信号量分析：设两个同步信号量SaSa、SbSb，其中：，其中：SaSa表示允许表示允许A产品比产品比B产品多入库的数量，初值为产品多入库的数量，初值为M-

5、1M-1。SbSb表示允许表示允许B产品比产品比A产品多入库的数量，初值为产品多入库的数量，初值为N-1N-1。设互斥信号量设互斥信号量mutexmutex，初值为，初值为1 1。 B产品入库进程：产品入库进程： j = 0; while (1) 生产产品生产产品; P(Sb); P(mutex); B产品入库产品入库 V(mutex); V(Sa);A产品入库进程：产品入库进程：i = 0;while (1) 生产产品生产产品; P(Sa); P(mutex); A产品入库产品入库 V(mutex); V(Sb); ;算法如下：算法如下：例题5 进程A1、A2， An1通过m个缓冲区向进程B

6、1、B2、 Bn2不断发送消息。发送和接收工作遵循下列规则：（1） 每个发送进程一次发送一个消息，写入一个缓冲区，缓冲区大小等于消息长度。（2） 对每个消息，B1，B2， Bn2都须各接收一次，读入各自的数据区内。（3） m个缓冲区都满时，发送进程等待，没有可读消息时，接收进程等待。试用P、V操作组织正确的发送和接收工作。分析：分析：每个缓冲区只要写一次但要读n2次，因此，可以看成n2组缓冲区，每个发送者要同时写n2个缓冲区，而每个接收者只要读它自己的缓冲区。Sinn2=m；表示每个读进程开始有m个空缓冲区。Soutn2=0；表示每个读进程开始有0个可接收的消息。解：先将问题简化： 设缓冲区的

7、大小为1 有一个发送进程A1 有二个接收进程B1、B2 设有信号量Sin1 、Sin2 初值为1 设有信号量Sout1 、Sout2 初值为0Bi： while (1) P(Souti);从缓冲区取数从缓冲区取数 V(Sini);A1:while (1) P(Sin1); P(Sin2);将数据放入缓冲区 V(Sout1); V(Sout2);向目标前进一步: 设缓冲区的大小为m 有一个发送进程A1 有二个接收进程B1、B2 设有信号量Sin1 、Sin2 初值为m 设有信号量Sout1 、Sout2 初值为0Bi： while (1) P(Souti); P(mutex);从缓冲区取数从缓冲

8、区取数 V(mutex); V(Sini);A1:while (1) P(Sin1); P(Sin2); P(mutex);将数据放入缓冲区 V(mutex); V(Sout1); V(Sout2);到达目标 设缓冲区的大小为m 有n1个发送进程A1.An1 有n2个接收进程B1Bn2 设有n2个信号量Sinn2 初值均为m 设有n2个信号量Soutn2 初值均为0Bi： while (1) P(Souti); V(mutex);从缓冲区取数从缓冲区取数 P(mutex); V(Sini); ;Aj:while (1) for(i=1;i=n2;i+) P(Sini); P(mutex);将数

9、据放入缓冲区 V(mutex); for(i=1;i=n2;i+) V(Sout2);a，b两点之间是一段东西向的单行车道，现要设计一个自两点之间是一段东西向的单行车道，现要设计一个自动管理系统，管理规则如下：动管理系统，管理规则如下：（1）当）当ab之间有车辆在行驶时同方向的车可以同时驶入之间有车辆在行驶时同方向的车可以同时驶入ab段，但另一方向的车必须在段，但另一方向的车必须在ab段外等待；段外等待；（2）当）当ab之间无车辆在行驶时，到达之间无车辆在行驶时，到达a点（或点（或b点）的车辆点）的车辆可以进入可以进入ab段，但不能从段，但不能从a点和点和b点同时驶入；点同时驶入；（3）当某方

10、向在）当某方向在ab段行驶的车辆驶出了段行驶的车辆驶出了ab段且暂无车辆进段且暂无车辆进入入ab段时，应让另一方向等待的车辆进入段时，应让另一方向等待的车辆进入ab段行驶。段行驶。请用信号量为工具，对请用信号量为工具，对ab段实现正确管理以保证行驶安全。段实现正确管理以保证行驶安全。例题6此题是读者此题是读者-写者问题的变形。设置写者问题的变形。设置3个信号量个信号量S1、S2和和Sab，分别用于从，分别用于从a点进入的车互斥访问共享变点进入的车互斥访问共享变量量ab（用于记录当前（用于记录当前ab段上由段上由a点进入车辆的数量），点进入车辆的数量），从从b点进入的车互斥访问共享变量点进入的车

11、互斥访问共享变量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) P(S1); if(ab=0) P(Sab); ab=ab+1; V(S1); 车辆从车辆从a点驶向点驶向b点点; P(S1); ab=ab-1; if(ab=0) V(Sab); V(S1); voi

12、d Pba() while(1) P(S2); if(ba=0) P(Sab); ba=ba+1; VS2); 车辆从车辆从b点驶向点驶向a点点; PS2); ba=ba-1; if(ba=0) V(Sab); V(S2); 一条河上架设了由若干个桥墩组成的一座桥。若一个一条河上架设了由若干个桥墩组成的一座桥。若一个桥墩只能站一个人，过河的人只能沿着桥向前走而不桥墩只能站一个人，过河的人只能沿着桥向前走而不能向后退。过河时，只要对岸无人过，就可以过。但能向后退。过河时，只要对岸无人过，就可以过。但不允许河对岸的两个人同时过，以防止出现死锁。请不允许河对岸的两个人同时过，以防止出现死锁。请给出两

13、个方向的人顺利过河的同步算法。给出两个方向的人顺利过河的同步算法。例题7信号量信号量s：互斥使用桥，初值为：互斥使用桥，初值为1信号量信号量scount1：对方向：对方向1上过河人计数器上过河人计数器count1的互斥使用，的互斥使用， 初值为初值为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)P(scount1);if(count1=0) P(s);count1+;V(scount1);P(scount); 上桥，过桥，下桥；上桥，过桥，下桥；V(scoun