操作系统复习题及答案

操作系统复习题

1、 若有如下表所示的4个作业进入系统，分别计算在FCFS，SJF和HRRF算法下的平均

周转时间和平均带权周转时间。 作业 提交时间 估计运行时间/min 1 2 3 4 解：

FCFS 作业 开始 完成 周转 时间 时间 时间 1 2 3 4 8:00 10:00 120 10:00 10:50 120 10:50 11:00 120 11:00 11:20 90 SJF 开始 完成 周转 时间 时间 时间 8:00 10:00 120 10:30 11:20 150 10:00 10:10 70 10:10 10:30 40 95 HRRF 开始 完成 周转 时间 时间 时间 8:00 10:00 120 10:10 11:00 130 10:00 10:10 70 11:00 11:20 90 102.5 8:00 8:50 9:00 9:50 120 50 10 20 平均112.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算法节 （2）优先数法 执行次序 执行时间 等待时间 周转时间 C D B E A 6 8 4 10 2 0 6 14 18 28 6 14 18 28 30 执行次序 执行时间 等待时间 周转时间 E D C B A 10 8 6 4 2 0 10 18 24 30 10 18 24 28 30 平均作业19.2 周转时间

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

3、 在单道批处理系统中，下列3个作业采用先来先服务调度算法和最高响应比优先算法进

行调度，哪一种算法的性能最好？请完成下表。 作业 提交时间 运行时间 开始时间 完成时间 周转时间/min 带权周转时间/min 1 2 3 10:00 10:10 10:25 2:00 1:00 0:25 平均周转时间 平均带权周转时间 解：FCFS 作业 提交时间 运行时间 开始时间 完成时间 周转时间/min 带权周转时间/min 1 2 3 10:00 10:10 10:25 2:00 1:00 0:25 10:00 12:00 13:00 12:00 13:00 13:25 120 170 180 120/120 170/60 180/25 平均周转时间 470/3 平均带权周转时间 3.68 HRRF 作业 提交时间 运行时间 开始时间 完成时间 周转时间/min 带权周转时间/min 1 2 3 10:00 10:10 10:25 2:00 1:00 0:25 10:00 12:25 12:00 12:00 13:25 12:25 120 195 120 120/120 195/60 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对资源的占有和需求情况如

下表所示。 进程 P0 P1 P2 P3 P4 Allocation A B C D 0 0 3 2 1 3 5 4 0 3 3 2 0 0 1 4 Max A B C D 0 0 4 4 3 6 10 10 0 9 8 4 0 6 6 10 Available A B C D 1 6 2 2 1 0 0 0 2 7 5 0 (1) 系统此时处于安全状态吗？

(2) 若此时进程P1发出request1(1,2,2,2)，系统能分配资源给它吗？为什么？ 解：（1）利用安全性算法分析可知，此时存在一个安全序列{P0,P3,P4,P1,P2}，故系统是安全的。 进程 Work Need Allocation Work+ Allocation Finish P0 P3 P4 P1 P2 1 6 2 2 1 6 5 4 1 9 8 6 1 9 9 10 2 9 9 10 A B C D 0 0 1 2 0 6 5 2 0 6 5 6 1 7 5 0 2 3 5 6 A B C D 0 0 3 2 0 3 3 2 0 0 1 4 1 3 5 4 A B C D 1 6 5 4 1 9 8 6 1 9 9 10 3 12 14 14 true true true true true 1 0 0 0 2 9 9 10 （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 2 3 1* 1 2 1 1 1 2 2 5* 5 2 3 3 4 5 5 5 5 5 1 1 1 1 4* 4 1 2 5* 2 3 2* 2 3 1 1* 1 4 3* 3 3 2* 2 2 2 2 4* 4 5 1 2 4 4 4 3* 3 4 5 2 2 5 5 4 4 4 5 1 1 5 5 4 4 （2）OPT缺页6次，缺页时加进主存的页号见表中带星的页号。 页框 1 0 1 2 3 1 4 1 1 2 2 1 2 1 4 5 3 2 2 2 2 2 2 4 4 4 4 4 4 1 2 1 1 1 4 5 3 1 1 1 1 5 5 5 5 4 4 4 4 1* 1 2 1 1 1 1 1 3* 3 3 2* 2 3 1 3* 3 3 5* 5 5 5 5 5 5 4* 4 5 1 3 （3）LRU缺页7次，缺页时加进主存的页号见表中带星的页号。 页框 1 0 1 2 3 1 4 1 1 2 2 1* 1 2* 2 5* 5 5 4 4 3* 3 3 3 2* 2 2 2 3* 3 3 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为多少时，系统没有死锁的危险，并说明原因。 解：

本文来源：https://www.bwwdw.com/article/hmy3.html