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

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

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

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

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

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

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

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

7 进程管理习题 为防止死锁，箱中车架的 数量不能超过 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) ； 组装为一台车；

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

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

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

11 进程管理习题 有 3 个进程 PA ， PB 和 PC 合作解决文件打印问 题： PA 将文件记录从磁盘读入主存的缓冲区 1 ，每执 行一次读一个记录； PB 将缓冲区 1 的内容复制到缓冲区 2 ，每执行一次 复制一个记录； PC 将缓冲区 2 的内容打印出来，每执行一次打印 一个记录。缓冲区的大小等于一个记录大小； 请用 P ， V 操作来保证文件的正确打印

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

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

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

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

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

17 进程管理习题 设三个信号量： S ：表示盘子是否 为空，初值为 1 ； So ：表示盘中是 否有桔子，初值 为 0 ； Sa ：表示盘中是 否有苹果，初值 为 0 。 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 进程管理习题 图书馆有 100 个座位，有一张登记表，要求： 阅读者进入时登记，取得座位号； 出来时，注销； 登记表同时只能由一个人使用； 用 P 、 V 原语描述一个读者的使用过程

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

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

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

23 进程管理习题 互斥信号量： 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();

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 进程管理习题 MaxUsed (Allocation) R1 R2 R3 P1 3 2 2 1 0 0 P2 6 1 3 4 1 1 P3 3 1 4 2 1 1 P4 4 2 2 0 0 2 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 - = ① 资源总量 (2,1,2)+(1,0,0)+(4,1,1)+(2,1,1)+(0,0,2)=(9,3,6)

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

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