《计算机操作系统教程第三版》答案作者左万历 周长林(4)

15. 试用信号灯与 PV 操作实现司机与售票员之间的同步问题。设公共汽车上有一个司机和一个售票员，其活动如下图所示。 为了安全起见，显然要求 : (1)关车门后方能启动车辆; (2)到站停车后方能开车门。 亦即“启动车辆”这一活动应当在“关车门”这一活动之后，“开车门”这一活动应当在“到站停车”这一活动之后。 semaphore s1=0,s2=0; 司机： 售票员： while(1){ while(1){ p(s1); 关车门; 启动车辆； v(s1); 正常行驶； 售 票； 到站停车； p(s2); v(s2); 开车门； } }

16. 设有A、B、C三组进程, 它们互斥地使用某一独占型资源R, 使用前申请, 使用后释放. 资源分配原则如下: (1) 当只有一组申请进程时, 该组申请进程依次获得R; (2) 当有两组申请进程时, 各组申请进程交替获得R, 组内申请进程交替获得R; (3) 当有三组申请进程时, 各组申请进程轮流获得R, 组内申请进程交替获得R.试用信号灯和PV操作分别给出各组进程的申请活动程序段和释放活动程序段.int free=1;//设备状态标志semaphore mutex=1;semaphore qa=qb=qc=0; //各组等待队列int counta=countb=countc=0;//等待队列长度 A组申请：

P(mutex);if(free==1){free=0;V(mutex);}else{counta+

+;V(mutex);P(qa);} A组释放：if(countb>0){countb- -;V(qb);}else{if(countc>0){countc- -;V(qc);}else{if(counta>0){counta-

-V(qa);}else{ free=1;}}}

A组进程活动可以给出B组和C组进程活动。

17. 设自行车生产线上有一只箱子，其中有 N 个位置 ( N ≥ 3)，每个位置可存放一个车架或一个车轮;

又设有三个工人，其活动分别为: 工人 1活动： do { 加工一个车架 ; 工人 2活动： do { 加工一个车轮 ; 工人 3活动： do { 箱中取一车架 ; 车架放入箱中 ; } while (1) 车轮放入箱中 ; } while (1) 箱中取二车轮 ; 组装为一台车 ; }

while (1)

试分别用信号灯与 PV 操作、管程、会合实现三个工人的合作，要求解中不含死锁。 一、用信号灯与 PV 操作实现三个工人的合作 首先不考虑死锁问题，工人 1与工人3、工人2与工人3构成生产者与消费者关系，这两对生产/消费关系通过共同的缓冲区相联系。从资源的角度来看，箱字中的空位置相当于工人1和工人2的资源，而车架和车轮相当于工人3的资源。定义三个信号灯如下： semaphore empty=N;

semaphore wheel=0; semaphore frame=0; 三位工人的活动分别为： 工人 1活动： do { 加工一个车架 ; 工人 2活动： do { 加工一个车轮 ; 工人 3活动： do { P(frame); 箱中取P(empty); 车架放入箱中 ; P(empty); 车轮放入箱中 ; 一车架 ; V(empty); P(wheel); V(frame); } while (1) V(wheel); } while (1) P(wheel); 箱中取二车轮 ;

V(empty); V(empty); 组装为一台

车 ; } while (1)

分析上述解法易见，当工人 1推进速度较快时，箱中空位置可能完全被车架占满或只留有一个存放车轮的位置，而当此时工人3同时取2个车轮时将无法得到，而工人2又无法将新加工的车轮放入箱中；当工人2推进速度较快时，箱中空位置可能完全被车轮占满，而当此时工人3同取车架时将无法得到，而工人1又无法将新加工的车架放入箱中 。上述两种情况都意味着死锁。 为防止死锁的发生，箱中车架的数量不可超过 N-2，车轮的数量不可超过N-1，这些限制可以用两个信号灯来表达。 semaphore s1=N-2;

semaphore s2=N-1; 如此，可以给出不含死锁的完整解法如下：

工人 1活动： do { 加工一个车架 ; 工人 2活动： do { 加工一个车轮 ; 工人 3活动： do { P(frame); 箱中取P(s1); P(empty); 车架放入箱中 ; P(s2); P(empty); 车轮放入箱中 ; 一车架 ; V(empty); V(s1); V(frame); } while (1) V(wheel); } while (1) P(wheel); P(wheel); 箱中取二车

轮 ; V(empty); V(empty); V(s2);

V(s2); 组装为一台车 ; } while (1)

详细描述还应考虑对箱子单元的描述以及访问互斥问题。建议车架放在箱子的一端，车轮放在箱子的另

一端，车架与车轮都采用后进先出的管理方式。Semaphore s1=N-2，s2=N-1，mutex=1;int in1=0，

in2=N-1;int buf[N]; 工人 1活动： do { 加工一个车架 ; 工人 2活动： do { 加工一个车轮 ; 工人 3活动： do { P(frame); P(s1); P(s2); P(empty); P(mutex);Temp1=Buf[in1-1]；P(empty);P(mutex);Buf[in1]=车架；P(mutex);Buf[in2]=车轮；in1=in1-1; V(mutex); V(empty); in1=in1+1; V(mutex); V(frame); } in2=in2-1; V(mutex);V(wheel); } V(s1); P(wheel); P(wheel); while (1) while (1) P(mutex);Temp2=Buf[in2+1];in2=in2

+1;Temp3=Buf[in2+1];In2=in2+1;V(m

utex);V(empty); V(empty); V(s2);

V(s2); 组装为一台车 ; } while (1)

18. 一座小桥(最多只能承重两个人)横跨南北两岸，任意时刻同一方向只允许一人过桥，南侧桥段和北侧桥段较窄只能通过一人，桥中央一处宽敞，允许两个人通过或歇息．试用信号灯和PV操作写出南、北两岸过桥的同步算法． semaphore

south=1; load=2;semaphore north=1;semaphore

tosouth(){P(load);P(north);过北段桥;到桥中tonorth(){P(load);P(south);过南段桥;到桥中间间;V(north);P(south);过南段桥;到达南岸V(south);P(north);过北段桥;到达北岸V(south);V(load);} V(north);V(load);}

19. 某寺庙，有小和尚、老和尚若干．庙内有一水缸，由小和尚提水入缸，供老和尚饮用．水缸可容纳 30 桶水，每次入水、取水仅为1桶，不可同时进行。水取自同一井中，水井径窄，每次只能容纳一个水桶取

水。设水桶个数为5个，试用信号灯和 PV 操作给出老和尚和小和尚的活动。 semaphore empty=30; // 表示缸中目前还能装多少桶水，初始时

能装 30 桶水 semaphore full=0; // 表示缸中有多少桶水，初

始时缸中没有水 semaphore buckets=5; // 表示有多少只空桶可

用，初始时有 5 只桶可用 semaphore mutex_well=1; // 用于实

现对井的互斥操作 semaphore mutex_bigjar=1; // 用于实现对

缸的互斥操作 semaphore mutex_bucket=1; //用于实现对桶的互

斥操作

young_monk() { while(1){ P(empty); old_monk() { while(){ P(full); P(buckets); P(buckets);P(mutex_bucket); 取一个桶； V(mutex_bucket); P(mutex_bucket); get a bucket; go to the well; P(mutex_well); get water; V(mutex_well); go V(mutex_bucket); P(mutex_bigjar); get water; to the temple; P(mutex_bigjar); pure the water into the big V(mutex_bigjar); V(buckets); V(empty); } } jar; V(mutex_bigjar); V(buckets); V(full); } }

20. 设系统中有5台类型相同的打印机，依次编号为1～5。 又设系统中有n个使用打印机的进程，使用前申请，使用后释放。 每个进程有一个进程标识，用于区别不同的进程。 每个进程还有一个优先数，不同进程的优先数各异。当有多个进程同时申请时，按照进程优先数由高到低的次序实施分配。 试用信号灯和PV操作实现对于打印机资源的管理，即要求编写如下函数和过程:(1) 函数 require(pid，pri): 申请一台打印机。参数pid为进 …… 此处隐藏：4025字，全部文档内容请下载后查看。喜欢就下载吧 ……