进程管理习题 图书馆有100个座位，有一张登记表，要求： 用P、V原语描述一个读者的使用过程 阅读者进入时登记，取得座位号； 出来时，注销；

Presentation on theme: "进程管理习题 图书馆有100个座位，有一张登记表，要求： 用P、V原语描述一个读者的使用过程 阅读者进入时登记，取得座位号； 出来时，注销；"— Presentation transcript:

1 进程管理习题 图书馆有100个座位，有一张登记表，要求： 用P、V原语描述一个读者的使用过程 阅读者进入时登记，取得座位号； 出来时，注销；
登记表同时只能由一个人使用； 用P、V原语描述一个读者的使用过程

2 进程管理习题 信号量SN，表示可用座位数，初值为100；信号量sb, 表示登记表是否正在使用，初值为1； enter( ) { P(SN)
P(sb) 登记； V(sb)； } outer( ) { P(sb); 注销； V(sb); V(SN); } reader(int i) { enter()； 阅读; outer() }

3 进程管理习题 有3个进程PA，PB和PC合作解决文件打印问题： 请用P，V操作来保证文件的正确打印

4 进程管理习题 设置4个信号量：empty1、empty2、full1、full2
缓冲区1 缓冲区2 PA 从磁盘读入 PB 复制 PC 打印 设置4个信号量：empty1、empty2、full1、full2 empty1及empty2分别表示缓冲区1及缓冲区2是否为空，初值为1 full1，full2分别表示缓冲区1及缓冲区2是否有记录可供处理，其初值为0

5 进程管理习题 缓冲区1 缓冲区2 PA 从磁盘读入 PB 复制 PC 打印 PA() 从磁盘读一 个记录； P(empty1)； 将记录存入
缓冲区1； V(full1)； PB() P(full1)； 从缓冲区1中 取出记录； V(empty1)； P(empty2)； 将记录存入缓 冲区2； V(full2); PC() P(full2); 从缓冲区2 取一个记录； V(empty2); 打印记录;

6 进程管理习题 公共汽车上，司机和售票员的活动分别为： 司机： 启动车辆； 司机P1 售票员P2 启动 关门 正常运行 售票 到站停 开门
正常行驶， 到站停车 司机P 售票员P 启动 关门 正常运行 售票 到站停 开门 售票员： 关车门； 售票； 开车门；

7 进程管理习题 设信号量S1：是否允许司机启动汽车，初值为0， S2：是否允许售票员开门，初值为0 Driver() { While (1)
{ P(S1); 启动汽车； 正常行车； 到站停车； V(S2); } Busman() { 关车门; V(S1)； 售票； P(S2)； 开车门； 上下乘客； Int s1=0; Int s2=0; Main( ) { Cobegin Driver(); Busman(); Coend

8 进程管理习题 三个进程P1、P2、P3互斥使用一个包含N（N>0）个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某已空单元中；P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数；P3每次用geteven()从该缓冲区中取出一个偶数并用counteven()统计偶数个数。请用信号量机制实现这三个进程的同步和互斥活动，并说明所定义信号量的含义。要求用伪码描述。

9 进程管理习题 互斥信号量：mutex初值为1；
同步信号量：P1、P2因奇数的放与取而同步，设置信号量odd；P1、P3因偶数的放与取而同步，设置信号量even；P1、P2、P3因共享缓冲区而同步，设置信号量empty。

10 进程管理习题 互斥信号量：mutex初值为1； 同步信号量：P1、P2因奇数的放与取而同步，设置信号量
odd；P1、P3因偶数的放与取而同步，设 置信号量even；P1、P2、P3因共享缓冲 区而同步，设置信号量empty。 P1： P(empty); P(mutex); put(); V(mutex); If number%2==0 V(even) Else V(odd); P2： P(odd); P(mutex); getodd(); V(mutex); V(empty); countodd(); P3： P(even); P(mutex); geteven(); V(mutex); V(empty); counteven();

11 进程管理习题 设自行车生产线上有一支箱子，其中有N个位置（N≥3），每个位置可存放一个车架或一个车轮；又设有三个工人，其活动分别为：
工人1活动： Do{ 加工一个车架； 车架放入箱中； } while(1); 工人2活动： Do{ 加工一个车轮； 车轮放入箱中； } while(1); 工人3活动： Do{ 箱中取一车架； 箱中取二车轮； 组装为一台车； } while(1); 试用信号量与P、V操作实现三个工人的合作

12 进程管理习题 工人1与工人3、工人2与工人3构成生产者与消费者关系，通过共同的缓冲区相联系。从资源的角度看，箱子中的空位置相当于工人1和工人2的资源，而车架和车轮相当于工人3的资源。 定义3个信号量： empty=N；（空位置） wheel=0；（车轮） frame=0；（车架）

13 进程管理习题 是否会死锁？ empty=N；wheel=0；frame=0； 工人1： 加工一个车架； P(empy)； 车架放入箱中；
V(frame)； 工人2： 加工一个车轮； 车轮放入箱中； V(wheel)； 工人3： P(frame)； 箱中取一车架； P(wheel)； 箱中取二车轮； V(empty)； 组装为一台车； 是否会死锁？

14 进程管理习题 为防止死锁，箱中车架的数量不能超过N-2，车轮的数量不能超过N-1，所以设置： s1=N-2，s2=N-1 工人1：
加工一个车架； P(s1)； 车架放入箱中； V(frame)； 工人2： 加工一个车轮； P(s2)； 车轮放入箱中； V(wheel)； 工人3： P(frame)； 箱中取一车架； V(s1)； P(wheel)； 箱中取二车轮； V(s2)； 组装为一台车；

15 进程管理习题 为防止死锁，箱中车架的数量不能超过N-2，车轮的数量不能超过N-1，所以设置： s1=N-2，s2=N-1，empty=N
工人1： 加工一个车架； P(s1)； P(empty)； 车架放入箱中； V(frame)； 工人2： 加工一个车轮； P(s2)； 车轮放入箱中； V(wheel)； 工人3： P(frame)； 箱中取一车架； V(empty)； V(s1)； P(wheel)； 箱中取二车轮； V(empty); V(s2)； 组装为一台车；

16 进程管理习题 桌上有一空盘，允许存放一只水果。爸爸可向盘中放苹果，也可向盘中放桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定当盘空时一次只能放一只水果供吃者取用，请用P，V原语实现爸爸，儿子女儿三个进程的同步。

17 进程管理习题 设三个信号量： S：表示盘子是否为空，初值为1； int s=1;int sa=0;int so=0; main() {
cobegin father(); son(); daughter(); coend }

18 进程管理习题 father() { While (1) { P(s); 将水果放入盘中； if (放入的是桔子) v(so)
else v(sa); } son() { While (1) { P(so); 从盘中取出桔子； v(s); 吃桔子； } daughter() { While (1) { P(sa); 从盘中取出苹果； v(s); 吃苹果； }

19 进程管理习题 设有一个可以装A、B两种物品的仓库，其容量无限大，但要求仓库中A、B两种物品的数量满足下述不等式：
-M ≤ A物品数量-B物品数量≤N 其中，M和N为正整数。试用信号量和P、V操作描述A、B两种物品的入库过程。

20 进程管理习题 已知条件 -M ≤ A物品数量-B物品数量≤N 可以拆分成两个不等式，即： A物品数量-B物品数量≤N
B物品数量-A物品数量≤M 这两个不等式的含义是：仓库中A物品可以比B物品多，但不能超过N个； B物品可以比A物品多，但不能超过M个。

21 进程管理习题 设两个信号量：a=N；b=M 如果没有B，A最多只能N个；如果没有A，B最多只能M个。 A物品入库： P(a); A物品入库；
V(b); B物品入库： P(b); B物品入库； V(a);

22 进程管理习题 一座小桥（最多只能承重两个人）横跨南北两岸，任意时刻同一方向只允许一人过桥，南侧桥段和北侧桥段较窄只能通过一人，桥中央一处宽敞，允许两个人通过或歇息。试用信号量和P、V操作写出南、北两岸过桥的同步算法。

23 进程管理习题 load控制桥上人数，north控制北段的互斥使用，south控制南段互斥使用
To 南： P(load)； P(north)； 过北桥段； 到桥中间； V(north)； P(south)； 过南桥段； 到达南岸； V(south)； V(load)； To 北： 到达北岸；

24 进程管理习题 某银行提供一个服务窗口和10个供顾客等待的座位。顾客到达银行时，若有空座位，则到取号机上领取一个号。等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为其服务。顾客和营业员的活动过程描述为： 请添加必要的信号量和P、V（或wait()、signal()）操作，实现上述过程的的互斥与同步。要求写出完整的过程，说明信号量的含义并赋初值。 Cobegin { process 顾客 {从取号机获得一个号码; 等待叫号; 获得服务; } process 营业员 { while (TRUE) { 叫号； 为顾客服务； } coend

25 进程管理习题 互斥资源：取号机（一次只允许一位顾客领号），因此，设一个互斥信号量mutex； 同步问题
顾客需要获得空座位等待叫号，当营业员空闲时，将选取一位顾客并为其服务。空座位的有、无影响等待顾客数量，顾客的有、无决定了营业员是否能开始服务，故分别设置信号量empty和full来实现这一同步关系； 顾客获得空座位后，需要等待叫号和被服务。这样，顾客与营业员就服务何时开始又构成了一个同步关系，定义信号量service来完成这一同步过程。

26 进程管理习题 semaphore mutex=1; //互斥使用取号机 semaphore empty=10; //空座位的数量
semaphore full=0; //已占座位的数量 semaphore service=0; //等待叫号 cobegin { process 顾客 process 营业员 { { P(empty); while(TRUE) P(mutex); { 从取号机获得一个号； P(full); V(mutex); V(empty); V(full); V(service); //叫号 P(service); //等待叫号 为顾客服务； 获得服务； } } } }coend

27 进程管理习题 评分说明 ①能正确给出互斥信号量定义、含义及初值，给1分。 ②能正确给出3个同步信号量定义、含义及初值，给2分。
③营业员进程描述正确的，给2分。 ④顾客进程描述中，互斥描述正确的，给1分；同步描述正确的，给2分；共3分。 ⑤其他正确解答，参照①- ④的标准给分。

28 进程管理习题 某系统有R1、R2和R3共3种资源，在T0时刻P1、P2、P3和P4这4个进程对资源的占用和需求情况见下页表，此时系统的可用资源向量为 (2, 1, 2)，问题： 将系统各种资源总数和此刻各进程对资源的需求数目用向量或矩阵表示出来； 如果此时P1和P2均发出资源请求向量Request (1,0,1)，为保证系统的安全性，应如何分配资源给这两个进程？说明采用策略的原因。

29 进程管理习题 ① 资源总量 (2,1,2)+(1,0,0)+(4,1,1)+(2,1,1)+(0,0,2)=(9,3,6) 3 2 2
Max Used (Allocation) R R R3 R R R3 P1 P2 P3 P4 ① 资源总量 (2,1,2)+(1,0,0)+(4,1,1)+(2,1,1)+(0,0,2)=(9,3,6) Need= 3 2 2 6 1 3 3 1 4 4 2 2 1 0 0 4 1 1 2 1 1 0 0 2 2 2 2 2 0 2 1 0 3 4 2 0 - =

30 进程管理习题 ② Request1(1,0,1)≤Need1(2,2,2)
Max Used (Allocation) Need R R R3 R1 R2 R3 P1 P2 P3 P4 ② Request1(1,0,1)≤Need1(2,2,2) Request1(1,0,1)≤Available(2,1,2) Available(1,1,1),不能满足任何进程，系统进入不安全状态，所以不能分配给P1 Used= 2 0 1 4 1 1 2 1 1 0 0 2 Need= 1 2 1 2 0 2 1 0 3

31 进程管理习题 ② Request2(1,0,1)≤Need1(2,0,2)
Max Used (Allocation) Need R R R3 R1 R2 R3 P1 P2 P3 P4 ② Request2(1,0,1)≤Need1(2,0,2) Request2(1,0,1)≤Available(2,1,2) Available(1,1,1),存在一个安全序列：{P2, P3, P4, P1}，所以能分配给P2 Used= 1 0 0 5 1 2 2 1 1 0 0 2 Need= 2 2 2 1 0 1 1 0 3