2022年2022年进程同步典型例题 .pdf

进程同步练习题1. 在公共汽车上，司机和售票员的工作流程如图所示。为保证乘客的安全，司机和售票员应密切配合协调工作。请用信号量来实现司机与售票员之间的同步。司机启动车辆正常行车到站停车售票员关车门售票开车门图司机和售票员工作流程图 约束：怎么密切配合协调工作才能保证安全呢？a)关车门 之后再 启动车辆 ；利用前驱图解释b)到站停车 之后再 开车门 ； 根据约束定义信号量；关车门 和启动车辆需要一个信号量进行同步S1； 到站停车 和开车门之间需要一个信号量进行同步 S2； 建立几个进程呢？a)为司机 建立一个进程 Driver；b)为售票员 建立一个进程 Conductor；Driver：Repeat 启动车辆；正常行驶；到站停车；Until false; Conductor：Repeat 关车门；售票；开车门；Until false; 加入同步关系：Var s1,s2:semorphore=0,0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 20 页 - - - - - - - - - Driver：Repeat Wait (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 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 20 页 - - - - - - - - - 取一个苹果；取一个橘子；从盘子取一个苹果；从盘子取一个橘子；放入盘子；放入盘子吃苹果；吃橘子；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); Until 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 两点的单行车道是一种临界资源；两端的车辆对该资源进行竞争；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 repeat Wait(S1) Wait(s2) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 20 页 - - - - - - - - - abcount=abcount+1; bacount=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一条河上架设了由若干个桥墩组成的一座桥。若一个桥墩只能站一个人， 过河的人只能沿着桥向前走而不能向后退。过河时，只要对岸无人过，就可以过。但不允许河对岸的两个人同时过，以防止出现死锁。请给出两个方向的人顺利过河的同步算法。分析： 约束：a)桥属于临界资源，两岸的人对该资源进行竞争；b)桥上的人数是有限制的，设这个桥由N 个桥墩构成，桥上同时只能有N 个人过桥，其它人要进行等待。相当于共享资源数。 设置信号量信号量 s：互斥使用桥，初值为1 变量 count1：方向 1 上过河人计数器变量 count2：方向 2 上过河人计数器信号量 scount1 ：对方向 1 上过河人计数器count1的互斥使用，初值为1 信号量 scount2 ：对方向 2 上过河人计数器count2的互斥使用，初值为1 信号量 scount ：代表桥上过河人的计数信号量，初值为桥墩个数N 建立进程Semaphore s, scount1, scount2, scount; int count1, count2; s=1; scount1=1; scount2=1; scount=N; count1=0; count2=0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 20 页 - - - - - - - - - void direct1(int i) wait(scount1); count1+; if(count1=1) wait(s); signal(scount1); wait(scount); 上桥，过桥，下桥；signal(scount); wait(scount1); 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); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 20 页 - - - - - - - - - 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)A 产品数量不能比B 产品数量多M 个以上即A 产品数量比B 产品数量最多多M-1 个； A 产品数量不能比B 产品数量少N 个以上即B 产品数量比A 产品最多多 N-1 个。 设置信号量设置互斥信号量 mutex 互斥使用仓库；设置两个信号量来控制A、B 产品的存放数量，sa表示当前允许 A 产品比 B 产品多入库的数量（当前允许A 产品入库数量）；sb表示当前允许 B 产品比 A 产品多入库的数量（当前允许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) 取一个产品；wait(sa); wait(mutex); 将产品入库；名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 20 页 - - - - - - - - - signal(mutex); signal(sb); process putb() while(1) 取一个产品；wait(sb); wait(mutex); 将产品入库；signal(mutex); signal(sa); main() cobegin puta(); putb(); 4将只读数据的进程称为“读者”进程，而写或修改数据的进程称为“写者”进程。允许多个“读者”同时读数据，但不允许“写者”与其他“读者”或“写者”同时访问数据。另外，要保证： 一旦有“写者”等待时，新到达的“读者”必须等待，直到该“写者”完成数据访问为止。 试用 P、V 操作正确实现“读者”与“写者”的同步。 （第二类读者写者问题，信号量解决方法）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 20 页 - - - - - - - - - 分析： 约束：a)写者与写者之间需要互斥访问；b)读者与写者之间需要互斥； （有一个读者在读就让写者等待） ，因此，此时需要一个计数变量记录读者的数量。c)允许多个读者同时读数据；d)一旦有“写者”等待时，新到达的“读者”必须等待，直到该“写者”完成数据访问为止。 建立进程Write: Repeat 执行读操作Until false; Read: Repeat 执行写操作；Until false; 设置信号量a)设置互斥信号量 mutex=1 实现写者与写者之间的互斥访问；Write: Repeat Wait(mutex) 执行读操作；Signal(mutex); Until false; b)实现读者与写者之间的互斥， 设置整型变量 readcount=0记录读者数量， if readcount=1 then wait(mutex) Read：Repeat readcount+; if(readcount=1) wait(mutex); 执行读操作；readcount- -; if(readcount=0) signal(mutex);名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 20 页 - - - - - - - - - until false; 由于 readcount 是共享变量，所以读者之间要互斥访问， 因此设置一个互斥信号量rmutex=1. Read：Repeat Wait(rmutex) readcount+; if(readcount=1) wait(mutex); signal(rmutex) 执行读操作；Wait(rmutex) readcount- -; if(readcount=0) signal(mutex); signal(rmutex) until false; c)要想实现 d） 的互斥，需让读者和写者再共享一个互斥信号量s， 因此设置 互斥信号量 s=1，一旦有写者等待时，就wait（s）让读者等待。Write: Repeat wait(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：Repeat 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 20 页 - - - - - - - - - Wait(s); Wait(rmutex) readcount+; if(readcount=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(readcount=0)signal(mutex); signal(rmutex); Process writer() while(1) wait(wmutex); writecount+; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 20 页 - - - - - - - - - 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(); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 20 页 - - - - - - - - - 1、在公共汽车上，司机和售票员的工作流程如图所示。为保证乘客的安全，司机和售票员应密切配合协调工作。请用信号量来实现司机与售票员之间的同步。司机启动车辆正常行车到站停车售票员关车门售票开车门图司机和售票员工作流程图【答案】设置两个 资源信号量： 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)；开车门； 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 20 页 - - - - - - - - - main() cobegin Driver(); 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); void daughter() 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 20 页 - - - - - - - - - while(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）当某方向在 ab 段行驶的车辆驶出了ab段且暂无车辆进入ab 段时，应让另一方向等待的车辆进入 ab段行驶。请用信号量为工具，对ab 段实现正确管理以保证行驶安全。【答案】名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 20 页 - - - - - - - - - 此题是读者 -写者问题的变形。设置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) 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); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 20 页 - - - - - - - - - signal(S2); main() cobegin Pab(); Pba(); 4. 将只读数据的进程称为“读者”进程，而写或修改数据的进程称为“写者”进程。允许多个“读者”同时读数据，但不允许“写者”与其他“读者”或“写者”同时访问数据。另外，要保证：一旦有“写者”等待时，新到达的“读者”必须等待，直到该“写者”完成数据访问为止。试用P、V 操作正确实现“读者”与“写者”的同步。（第二类读者写者问题，信号量解决方法）【答案】为了使写者优先， 可在原来的读优先算法的基础上增加一个互斥信号量 s，初值为 1，使得当至少有一个写者准备访问共享对象时，它可以使后续的 读者进程等待；整型变量 writecount，初值为 0，用来对写者进行计数；互斥信号量 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); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 20 页 - - - - - - - - - Process writer() while(1) wait(wmutex); if(writecount=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. 一条河上架设了由若干个桥墩组成的一座桥。若一个桥墩只能站一个人，过河的人只能沿着桥向前走而不能向后退。过河时，只要对岸无人过，就可以过。但不允许河对岸的两个人同时过，以防止出现死锁。请给出两个方向的人顺利过河的同步算法。【答案】信号量 s：互斥使用桥，初值为1 信号量 scount1 ：对方向 1 上过河人计数器count1的互斥使用，初值为1 信号量 scount2 ：对方向 2 上过河人计数器count2的互斥使用，初值为1 信号量 scount ：代表桥上过河人的计数信号量，初值为桥墩个数N 变量 count1：方向 1 上过河人计数器名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 20 页 - - - - - - - - - 变量 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(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); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 20 页 - - - - - - - - - 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 产品不入库的情况下，还可以允许 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) 取一个产品；名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 20 页 - - - - - - - - - wait(sa); wait(mutex); 将产品入库；signal(mutex); signal(sb); process putb() while(1) 取一个产品；wait(sb); wait(mutex); 将产品入库；signal(mutex); signal(sa); main() cobegin puta(); putb(); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 20 页 - - - - - - - - -