1、 若有如下表所示的4个作业进入系统，分别计算在FCFS，SJF和HRRF算法下的平均周转时间和平均带权周转时间。 作业 提交时间 估计运行时间/min 1 8:00 120 2 8:50 50 3 9:00 10 4 9:50 20 解：

作业 FCFS SJF HRRF 开始 完成 周转 时间 时间 时间 开始 完成 周转 时间 时间 时间 开始 完成 周转 时间 时间 时间 1 2 3 4 8:00 10:00 120 10:00 10:50 120 10:50 11:00 120 11:00 11:20 90 8:00 10:00 120 10:30 11:20 150 10:00 10:10 70 10:10 10:30 40 8:00 10:00 120 10:10 11:00 130 10:00 10:10 70 11:00 11:20 90 平均周转时间

112.5 95 102.5

平均带权周转时间

4.975 3.25 3.775

2、 有5个批处理作业A~E均已到达计算中心，其运行时间分别为2min,4min,6min,8min和10min,各自的优先级分别规定为1，2，3，4，5其中5是最高级。对于时间片轮转算法（时间片为2min），优先数法，短作业优先算法，先来先服务调度算法（按照作业到达次序C,D,B,E,A），在忽略进程切换时间的前提下，计算平均作业周转时间。 解：（1）FCFS算法 执行次序 执行时间 等待时间 周转时间 C D B E A 6 8 4 10 2 0 6 14 18 28 6 14 18 28 30 平均作业周转时间 19.2

（2）优先数法 执行次序 执行时间 等待时间 周转时间 E D C B A 10 8 6 4 2 0 10 18 24 30 10 18 24 28 30 平均作业周转时间 22

(3)时间片轮转算法 执行次序 执行时间 等待时间 周转时间 A B C D E 2 4 6 8 10 0 8 14 18 20 2 12 20 26 30 平均作业周转时间 18

按次序A B C D E B C D E C D E D E E (4)SJF算法 执行次序 执行时间 等待时间 周转时间 A B C D E 2 4 6 8 10 0 2 6 12 20 2 6 12 20 30 平均作业周转时间 14

3、 在单道批处理系统中，下列3个作业采用先来先服务调度算法和最高响应比优先算法进行调度，哪一种算法的性能最好？请完成下表。 作业 提交时间 运行时间 开始时间 完成时间 周转时间/min 带权周转时间/min 1 10:00 2:00 2 10:10 1:00 3 10:25 0:25 平均周转时间 平均带权周转时间 解：FCFS 作业 提交时间 运行时间 开始时间 完成时间 周转时间/min 带权周转时间/min 1 10:00 2:00 10:00 12:00 120 120/120 2 10:10 1:00 12:00 13:00 170 170/60 3 10:25 0:25 13:00 13:25 180 180/25 平均周转时间 470/3 平均带权周转时间 3.68 HRRF 作业 提交时间 运行时间 开始时间 完成时间 周转时间/min 带权周转时间/min 1 10:00 2:00 10:00 12:00 120 120/120 2 10:10 1:00 12:25 13:25 195 195/60 3 10:25 0:25 12:00 12:25 120 120/25 平均周转时间 435/3 平均带权周转时间 3.02

4、 一个快餐厅有4类职员：(1)领班：接受顾客点菜；（2）厨师：准备顾客的饭菜；（3）打包工：将饭菜打包；（4）出纳员：收款并提交食物。每位职员可被看做一个进程，试用一种同步机制写出能让4类职员正确并发工作的程序。 解：可设4个信号量S1,S2,S3,S4来协调进程工作。 Semophore S1,S2,S3,S4; S1=1;S2=S3=S4=0; cobegein process P1(){ while(true){ 有顾客到来； P（S1）； 接受顾客点菜； V（S2）； } } process P2(){ while(true){ P（S2）； 准备顾客的饭菜； V（S3）； } } process P3(){ while(true){ P（S3）； 将饭菜打包； V（S4）； } } process P4(){ while(true){ P（S4）； 收款并提交食品； V（S1）； } } coend 5、 系统有A,B,C,D共4种资源，在某时刻进程P0,P1,P2,P3,P4对资源的占有和需求情况如下表所示。 进程 Allocation Max Available

A B C D A B C D A B C D P0 0 0 3 2 0 0 4 4 1 6 2 2 P1 1 0 0 0 2 7 5 0 P2 1 3 5 4 3 6 10 10 P3 0 3 3 2 0 9 8 4 P4 0 0 1 4 0 6 6 10 (1) 系统此时处于安全状态吗？ (2) 若此时进程P1发出request1(1,2,2,2)，系统能分配资源给它吗？为什么？ 解：（1）利用安全性算法分析可知，此时存在一个安全序列{P0,P3,P4,P1,P2}，故系统是安全的。 进程 Work Need Allocation Work+ Allocation Finish

A B C D A B C D A B C D P0 1 6 2 2 0 0 1 2 0 0 3 2 1 6 5 4 true P3 1 6 5 4 0 6 5 2 0 3 3 2 1 9 8 6 true P4 1 9 8 6 0 6 5 6 0 0 1 4 1 9 9 10 true P1 1 9 9 10 1 7 5 0 1 0 0 0 2 9 9 10 true P2 2 9 9 10 2 3 5 6 1 3 5 4 3 12 14 14 true （2）若此时进程P1发出request1(1,2,2,2),系统按银行家算法进行检查： request1(1,2,2,2) ≮=need1(1,7,5,0)，其请求的资源数已超过其宣布的最大值，所以不能分配。 6、 给定主存空闲区，按照地址从小到大排列位：100KB,500KB,200KB,300KB,600KB。现有用户进程依次为212KB,417KB,112KB,426KB。 （1） 分别用首次适应算法，最佳适应算法和最坏适应算法将他们装入主存的哪个分区？ （2） 哪个算法能最有效的利用主存？ 解：按题意地址从小到大进行分区如图所示。 分区号 分区长 1 2 3 4 5 100KB 500KB 200KB 300KB 600KB (1) 首次适应算法 212KB 选中分区2，这时分区2还剩288KB。417KB选中分区5，这时分区5还剩183KB。112KB选中分区2，这时分区2还剩176KB。426KB无分区能满足，应该等待。 最佳适应算法 212KB 选中分区4，这时分区4还剩88KB。417KB选中分区2，这时分区2还剩83KB。112KB选中分区3，这时分区3还剩88KB。426KB选中分区5，这时分区5还剩174KB。 最坏适应算法 212KB 选中分区5，这时分区5还剩388KB。417KB选中分区2，这时分区2还剩83KB。112KB选中分区5，这时分区5还剩176KB。426KB无分区能满足，应该等待。 (2) 对于该作业队列，最佳适应算法能最有效利用主存。 7、 在一分页存储管理系统中，逻辑地址长度为16位，页面大小为4096B，现有逻辑地址2F6AH，且第0，1，2页依次存放在第10，12，14号物理块中，试问相应的物理地址是多少？ 解：因为逻辑地址长度为16位，而页面大小为4096字节，所以，前面的4位表示页号。把2F6AH转换成二进制为：0 0 1 0 1 1 1 1 0 1 1 0 1 0 1 0，可知页号为2。故放在14号物理块中，写成十六进制为EF6AH。 8、 在一个请求分页虚拟存储管理系统中，一个程序运行的页面走向是：1，2，3，1，4，5，1，2，1，4，5，3，4，5，对于分配给程序4个页框的情况，分别用FIFO，OPT和LRU算法， 求出缺页中断次数，并给出缺页时加进主存的页号。 解： （1）FIFO缺页10次，缺页时加进主存的页号见表中带星的页号。 页框 1 2 3 1 4 5 1 2 1 4 5 3 4 5

0 1* 1 1 1 1 5* 5 5 5 5 5 5 4* 4 1 2* 2 2 2 2 1* 1 1 1 1 1 1 5* 2 3* 3 3 3 3 2* 2 2 2 2 2 2 3 4* 4 4 4 4 4 4 3* 3 3 （2）OPT缺页6次，缺页时加进主存的页号见表中带星的页号。 页框 1 2 3 1 4 5 1 2 1 4 5 3 4 5

0 1* 1 1 1 1 1 1 1 1 1 1 3* 3 3 1 2* 2 2 2 2 2 2 2 2 2 2 2 2 2 3* 3 3 5* 5 5 5 5 5 5 5 5 3 4* 4 4 4 4 4 4 4 4 4 （3）LRU缺页7次，缺页时加进主存的页号见表中带星的页号。 页框 1 2 3 1 4 5 1 2 1 4 5 3 4 5

0 1* 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2* 2 2 2 5* 5 5 5 5 5 5 5 5 2 3* 3 3 3 3 2* 2 2 2 3* 3 3 3 4* 4 4 4 4 4 4 4 4 4 9、 假定磁盘有200个柱面，编号0~199，当前移动臂的位置在143号柱面上，并刚刚完成125号柱面的服务请求。如果请求队列的先后顺序时：86，147，91，177，94，150，102，175，130；试问为了完成上述请求，下列算法移动臂移动的总柱面数是多少？并计算移动臂移动的顺序。 （1） FCFS （2） SSTF （3） SCAN 解：（1）FCFS 为565，依次为143-86-147-91-177-94-150-102-175-130 （2）SSTF 为162，依次为143-147-150-130-102-94-91-86-175-177 （3）SCAN 为125（先向地址增大的方向），依次为143-147-150-175-177-130-102-94-91-86 10、一台计算机有8台磁带机。他们由N个进程竞争使用，每个进程可能需要3台磁带机。问N为多少时，系统没有死锁的危险，并说明原因。 解：N<4