1、进程同步练习题1. 在公共汽车上，司机和售票员的工作流程如图所示。为保证乘客的安全，司机和售票员应密切配合协调工作。请用信号量来实现司机与售票员之间的同步。 司 机 启 动 车 辆 正 常 行 车 到 站 停 车 售 票 员 关 车 门 售 票 开 车 门 图 司机和售票员工作流程图2. 桌子上有一只盘子，盘子中只能放一只水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，一个儿子专等吃盘子中的橘子，一个女儿专等吃盘子中的苹果。用 PV 操作实现他们之间的同步机制。3. a，b 两点之间是一段东西向的单行车道，现要设计一个自动管理系统，管理规则如下：（1）当 ab 之间有车辆在行驶时同方向的车可
2、以同时驶入 ab 段，但另一方向的车必须在 ab段外等待；（2）当 ab 之间无车辆在行驶时，到达 a 点（或 b 点）的车辆可以进入 ab 段，但不能从 a点和 b 点同时驶入；（3）当某方向在 ab 段行驶的车辆驶出了 ab 段且暂无车辆进入 ab 段时，应让另一方向等待的车辆进入 ab 段行驶。请用信号量为工具，对 ab 段实现正确管理以保证行驶安全。4将只读数据的进程称为“读者”进程，而写或修改数据的进程称为“写者”进程。允许多个“读者”同时读数据，但不允许“写者”与其他“读者”或“写者”同时访问数据。另外，要保证：一旦有“写者”等待时，新到达的“读者”必须等待，直到该“写者”完成数据
3、访问为止。试用 P、V 操作正确实现“读者”与“写者”的同步。 （第二类读者写者问题，信号量解决方法）5一条河上架设了由若干个桥墩组成的一座桥。若一个桥墩只能站一个人，过河的人只能沿着桥向前走而不能向后退。过河时，只要对岸无人过，就可以过。但不允许河对岸的两个人同时过，以防止出现死锁。请给出两个方向的人顺利过河的同步算法。6有一个仓库，可以存放 A 和 B 两种产品，但要求：（1）每次只能存入一种产品（A 或 B） ；（2）-NA 产品数量B 产品数量M。其中， N 和 M 是正整数。试用同步算法描述产品 A 与产品 B 的入库过程。1、在公共汽车上，司机和售票员的工作流程如图所示。为保证乘客
4、的安全，司机和售票员应密切配合协调工作。请用信号量来实现司机与售票员之间的同步。 司 机 启 动 车 辆 正 常 行 车 到 站 停 车 售 票 员 关 车 门 售 票 开 车 门 图 司机和售票员工作流程图【答案】设置两个资源信号量：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)；开车门；ma
5、in()cobeginDriver();Busman();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)
6、;void daughter()while(1)wait(Sl);从盘子里拿走苹果；signal(S);吃苹果;void son()while(1)wait(S2);从盘子里拿走橘子；signal(S);吃橘子;main()cobeginfather();mother();daughter();son();3. a，b 两点之间是一段东西向的单行车道，现要设计一个自动管理系统，管理规则如下：（1）当 ab 之间有车辆在行驶时同方向的车可以同时驶入 ab 段，但另一方向的车必须在 ab段外等待；（2）当 ab 之间无车辆在行驶时，到达 a 点（或 b 点）的车辆可以进入 ab 段，但不能从 a点
7、和 b 点同时驶入；（3）当某方向在 ab 段行驶的车辆驶出了 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 的初值分别
8、为0、0。semaphore S1=1,S2=1,Sab=1;int ab=ba=0;void Pab()while(1)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);mai
9、n()cobeginPab();Pba();4. 将只读数据的进程称为“读者”进程，而写或修改数据的进程称为“写者”进程。允许多个“读者”同时读数据，但不允许“写者”与其他“读者”或“写者”同时访问数据。另外，要保证：一旦有“写者”等待时，新到达的“读者”必须等待，直到该“写者”完成数据访问为止。试用 P、V 操作正确实现“读者”与“写者”的同步。 （第二类读者写者问题，信号量解决方法）【答案】为了使写者优先，可在原来的读优先算法的基础上增加一个互斥信号量 s，初值为 1，使得当至少有一个写者准备访问共享对象时，它可以使后续的读者进程等待；整型变量 writecount，初值为 0，用来对写者
10、进行计数；互斥信号量 wmutex，初值为 1，用来实现多个写者对 writecount 进行互斥访问。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(readcount=0)signal(mutex);signal(rmutex);Process writer() while(1)wait(wmutex);if(writeco
11、unt=0)wait(s);writecount+;signal(wmutex);wait(mutex);perform write operation;signal(mutex);wait(wmutex);writecount-;if(writecount=0)signal(s);signal(wmutex);Main( )cobegin reader();writer();5. 一条河上架设了由若干个桥墩组成的一座桥。若一个桥墩只能站一个人，过河的人只能沿着桥向前走而不能向后退。过河时，只要对岸无人过，就可以过。但不允许河对岸的两个人同时过，以防止出现死锁。请给出两个方向的人顺利过河的同步
12、算法。【答案】信号量 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=
13、0;void direct1(int i)wait(scount1);if(count1=0) wait(s);count1+;signal(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(sc
14、ount2);count2-;if(count2=0)signal(s);signal(scount2);main()cobegindirect1(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 个
15、以 上 设置两个信号量来控制 A、B 产品的存放数量，sa 表示当前允许 A 产品比 B 产品多入库的数量（当前允许 A 产品入库数量） ，即在当前库存量和 B 产品不入库的情况下，还可以允许 sa 个 A 产品入库；sb 表示当前允许 B 产品比 A 产品多入库的数量（当前允许 B 产品入库数量） ，即在当前库存量和 A 产品不入库的情况下，还可以允许 sb 个 B 产品入库。初始时，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)
