进程管理习题

1、设有一个可以装设有一个可以装A、B两种物品的仓库，其两种物品的仓库，其容量无限大，但要求仓库中容量无限大，但要求仓库中A、B两种物品两种物品的数量满足下述不等式：的数量满足下述不等式： -M A物品数量物品数量-B物品数量物品数量N 其中，其中，M和和N为正整数。试用信号量和为正整数。试用信号量和P、V操作描述操作描述A、B两种物品的入库过程。两种物品的入库过程。已知条件已知条件 -M A物品数量物品数量-B物品数量物品数量N可以拆分成两个不等式，即：可以拆分成两个不等式，即： A物品数量物品数量-B物品数量物品数量N B物品数量物品数量-A物品数量物品数量M 这两个不等式的含义是：仓库中这两

2、个不等式的含义是：仓库中A物品可物品可以比以比B物品多，但不能超过物品多，但不能超过N个；个； B物品可物品可以比以比A物品多，但不能超过物品多，但不能超过M个。个。A物品入库：物品入库： P(a); A物品入库；物品入库； V(b);B物品入库：物品入库： P(b); B物品入库；物品入库； V(a); 设两个信号量：设两个信号量：a=N；b=M如果没有如果没有B，A最多只能最多只能N个；个；如果没有如果没有A，B最多只能最多只能M个。个。设自行车生产线上有一支箱子，其中有设自行车生产线上有一支箱子，其中有N个位置个位置（N3），每个位置可存放一个车架或一个车轮；），每个位置可存放一个车架或

3、一个车轮；又设有三个工人，其活动分别为：又设有三个工人，其活动分别为：工人工人1活动：活动：Do 加工一个车架；加工一个车架； 车架放入箱中；车架放入箱中； while(1);工人工人2活动：活动：Do 加工一个车轮；加工一个车轮； 车轮放入箱中；车轮放入箱中； while(1);工人工人3活动：活动：Do 箱中取一车架；箱中取一车架； 箱中取二车轮；箱中取二车轮； 组装为一台车；组装为一台车； while(1);试用信号量与试用信号量与P、V操作实现三个工人的合作操作实现三个工人的合作首先不考虑死锁问题，工人首先不考虑死锁问题，工人1与工人与工人3、工人、工人2与工人与工人3构成生产者与消费

4、者关系，通过共构成生产者与消费者关系，通过共同的缓冲区相联系。从资源的角度看，箱子同的缓冲区相联系。从资源的角度看，箱子中的空位置相当于工人中的空位置相当于工人1和工人和工人2的资源，而的资源，而车架和车轮相当于工人车架和车轮相当于工人3的资源。的资源。定义定义3个信号量：个信号量： empty=N；（空位置）；（空位置） wheel=0；（车轮）；（车轮） frame=0；（车架）；（车架） empty=N；wheel=0；frame=0；工人工人1： 加工一个车架；加工一个车架； P(empy)； 车架放入箱中；车架放入箱中； V(frame)；工人工人2： 加工一个车轮；加工一个车轮；

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

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

7、： 加工一个车轮；加工一个车轮； P(s2)； P(empty)； 车轮放入箱中；车轮放入箱中； V(wheel)；工人工人3： P(frame)； 箱中取一车架；箱中取一车架； V(empty)； V(s1)； P(wheel)； P(wheel)； 箱中取二车轮；箱中取二车轮； V(empty); V(empty); V(s2)； V(s2)； 组装为一台车；组装为一台车；一座小桥（最多只能承重两个人）横跨南一座小桥（最多只能承重两个人）横跨南北两岸，任意时刻同一方向只允许一人过北两岸，任意时刻同一方向只允许一人过桥，南侧桥段和北侧桥段较窄只能通过一桥，南侧桥段和北侧桥段较窄只能通过一人，

8、桥中央一处宽敞，允许两个人通过或人，桥中央一处宽敞，允许两个人通过或歇息。试用信号量和歇息。试用信号量和P、V操作写出南、北操作写出南、北两岸过桥的同步算法。两岸过桥的同步算法。load控制桥上人控制桥上人数，数，north控制北控制北段的互斥使用，段的互斥使用，south控制南段互控制南段互斥使用斥使用初始值：初始值：load=2, north=1, south=1To 南：南： P(load)； P(north)； 过北桥段；过北桥段； 到桥中间；到桥中间； V(north)； P(south)； 过南桥段；过南桥段； 到达南岸；到达南岸； V(south)； V(load)；To 北：北

9、： P(load)； P(south)； 过南桥段；过南桥段； 到桥中间；到桥中间； V(south)； P(north)； 过北桥段；过北桥段； 到达北岸；到达北岸； V(north)； V(load)；有有3个进程个进程PA，PB和和PC合作解决文件打印问合作解决文件打印问题：题：PA将文件记录从磁盘读入主存的缓冲区将文件记录从磁盘读入主存的缓冲区1，每执，每执行一次读一个记录；行一次读一个记录；PB将缓冲区将缓冲区1的内容复制到缓冲区的内容复制到缓冲区2，每执行一，每执行一次复制一个记录；次复制一个记录；PC将缓冲区将缓冲区2的内容打印出来，每执行一次打印的内容打印出来，每执行一次打印一

10、个记录。缓冲区的大小等于一个记录大小；一个记录。缓冲区的大小等于一个记录大小；请用请用P，V操作来保证文件的正确打印操作来保证文件的正确打印设置设置4个信号量：个信号量：empty1、empty2、full1、full2empty1及及empty2分别表示缓冲区分别表示缓冲区1及缓冲区及缓冲区2是否为空，初值为是否为空，初值为1full1，full2分别表示缓冲区分别表示缓冲区1及缓冲区及缓冲区2是否是否有记录可供处理，其初值为有记录可供处理，其初值为0缓冲区缓冲区1缓冲区缓冲区2PA从磁盘读入从磁盘读入PB复制复制PC打印打印PA() 从磁盘读一从磁盘读一 个记录；个记录； P(empty1

11、)； 将记录存入将记录存入 缓冲区缓冲区1； V(full1)；PB() P(full1)； 从缓冲区从缓冲区1中中 取出记录；取出记录； V(empty1)； P(empty2)； 将记录存入缓将记录存入缓 冲区冲区2； V(full2);PC() P(full2); 从缓冲区从缓冲区2 取一个记录；取一个记录； V(empty2); 打印记录打印记录;缓冲区缓冲区1缓冲区缓冲区2PA从磁盘读入从磁盘读入PB复制复制PC打印打印公共汽车上，司机和售票员的活动分别为：公共汽车上，司机和售票员的活动分别为：司机：司机：启动车辆；启动车辆；正常行驶，正常行驶，到站停车到站停车售票员：售票员： 关车

12、门；关车门； 售票；售票； 开车门；开车门；设信号量设信号量S1：是否允许司机启动汽车，初值为：是否允许司机启动汽车，初值为0， S2：是否允许售票员开门，初值为：是否允许售票员开门，初值为0Driver() While (1) P(S1); 启动汽车；启动汽车； 正常行车；正常行车； 到站停车；到站停车； V(S2); Busman() While (1) 关车门关车门; V(S1)； 售票；售票； P(S2)； 开车门；开车门； 上下乘客；上下乘客； Int s1=0;Int s2=0;Main( ) Cobegin Driver(); Busman(); Coend 桌上有一空盘，允许存

13、放一只水果。爸爸桌上有一空盘，允许存放一只水果。爸爸可向盘中放苹果，也可向盘中放桔子，儿可向盘中放苹果，也可向盘中放桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定当盘空时一次只能放一只水果苹果。规定当盘空时一次只能放一只水果供吃者取用，请用供吃者取用，请用P，V原语实现爸爸，儿原语实现爸爸，儿子女儿三个进程的同步。子女儿三个进程的同步。设三个信号量：设三个信号量： S：表示盘子是否：表示盘子是否为空，初值为为空，初值为1； So：表示盘中是：表示盘中是否有桔子，初值否有桔子，初值为为0 ； Sa：表示盘中是：表示盘中是否有苹果，初值否有苹果，初值为为

14、0。int s=1;int sa=0;int so=0;main() cobegin father(); son(); daughter(); coend 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); 吃苹果；吃苹果； 图书馆有图书馆有100个座位，有一张登记表，要求：个座位，

15、有一张登记表，要求：阅读者进入时登记，取得座位号；阅读者进入时登记，取得座位号；出来时，注销；出来时，注销；登记表同时只能由一个人使用；登记表同时只能由一个人使用；用用P、V原语描述一个读者的使用过程原语描述一个读者的使用过程信号量信号量SN，表示可用座位数，初值为，表示可用座位数，初值为100；信号量信号量sb, 表示登记表是否正在使用，初值表示登记表是否正在使用，初值为为1；reader(int i) enter()； 阅读阅读; outer()enter( ) P(SN) P(sb) 登记；登记； V(sb)；outer( ) P(sb); 注销；注销； V(sb); V(SN);三个进

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

17、的同步和互斥活动，并说明所定义信号量的含义。要求用伪码描述。含义。要求用伪码描述。互斥信号量：互斥信号量：mutex初值为初值为1；同步信号量：同步信号量：P1、P2因奇数的放与取而同因奇数的放与取而同步，设置信号量步，设置信号量odd；P1、P3因偶数的放与因偶数的放与取而同步，设置信号量取而同步，设置信号量even；P1、P2、P3因共享缓冲区而同步，设置信号量因共享缓冲区而同步，设置信号量empty。互斥信号量：互斥信号量：mutex初值为初值为1；同步信号量：同步信号量：P1、P2因奇数的放与取而同步，设置信号量因奇数的放与取而同步，设置信号量 odd；P1、P3因偶数的放与取而同步，

18、设因偶数的放与取而同步，设 置信号量置信号量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();某银行提供一个服务窗口和某银行提供一个服务窗口和

19、10个个供顾客等待的座位。顾客到达银供顾客等待的座位。顾客到达银行时，若有空座位，则到取号机行时，若有空座位，则到取号机上领取一个号。等待叫号。取号上领取一个号。等待叫号。取号机每次仅允许一位顾客使用。当机每次仅允许一位顾客使用。当营业员空闲时，通过叫号选取一营业员空闲时，通过叫号选取一位顾客，并为其服务。顾客和营位顾客，并为其服务。顾客和营业员的活动过程描述为：业员的活动过程描述为：请添加必要的信号量和请添加必要的信号量和P、V（或（或wait()、signal()）操作，实现上述）操作，实现上述过程的的互斥与同步。要求写出过程的的互斥与同步。要求写出完整的过程，说明信号量的含义完整的过程，

20、说明信号量的含义并赋初值。并赋初值。Cobegin process 顾客顾客 从取号机获得一个号码从取号机获得一个号码; 等待叫号等待叫号; 获得服务获得服务; process 营业员营业员 while (TRUE) 叫号；叫号； 为顾客服务；为顾客服务； coend互斥资源：取号机（一次只允许一位顾客互斥资源：取号机（一次只允许一位顾客领号），因此，设一个互斥信号量领号），因此，设一个互斥信号量mutex；同步问题同步问题顾客需要获得空座位等待叫号，当营业员空闲顾客需要获得空座位等待叫号，当营业员空闲时，将选取一位顾客并为其服务。空座位的有、时，将选取一位顾客并为其服务。空座位的有、无影响等

21、待顾客数量，顾客的有、无决定了营无影响等待顾客数量，顾客的有、无决定了营业员是否能开始服务，故分别设置信号量业员是否能开始服务，故分别设置信号量empty和和full来实现这一同步关系；来实现这一同步关系；顾客获得空座位后，需要等待叫号和被服务。顾客获得空座位后，需要等待叫号和被服务。这样，顾客与营业员就服务何时开始又构成了这样，顾客与营业员就服务何时开始又构成了一个同步关系，定义信号量一个同步关系，定义信号量service来完成这一来完成这一同步过程。同步过程。semaphore mutex=1; /互斥使用取号机互斥使用取号机semaphore empty=10; /空座位的数量空座位的数

22、量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评分说明评分说明能正确给出互斥信号量定义、含义及初值，能正确给出互斥信号量定义、

23、含义及初值，给给1分。分。能正确给出能正确给出3个同步信号量定义、含义及初个同步信号量定义、含义及初值，给值，给2分。分。营业员进程描述正确的，给营业员进程描述正确的，给2分。分。顾客进程描述中，互斥描述正确的，给顾客进程描述中，互斥描述正确的，给1分；分；同步描述正确的，给同步描述正确的，给2分；共分；共3分。分。其他正确解答，参照其他正确解答，参照- 的标准给分。的标准给分。某系统有某系统有R1、R2和和R3共共3种资源，在种资源，在T0时刻时刻P1、P2、P3和和P4这这4个进程对资源的个进程对资源的占用和需求情况见下页表，此时系统的可占用和需求情况见下页表，此时系统的可用资源向量为用资源向量为 (2, 1, 2)，问题：，问题： 将系统各种资源总数和此刻各进程对资将系统各种资源总数和此刻各进程对资源的需求数目用向量或矩阵表示出来；源的需求数目用向量或矩阵表示出来； 如果此时如果此时P1和和P2均发出资源请求向量均发出资源请求向量Request (1,0,1)，为保证系统的安全性，为保证系统的安全性，应如何分配资源给这两个进程？说明采应如何分配资源给这两个进程？说明采用策略的原因。用策略的原因。MaxUsed (Allocation) R1 R2 R3 R1 R2 R3P1 3 2 2