操作系统复习习题答案1

1、1、 若有如下表所示的4个作业进入系统，分别计算在FCFS，SJF和HRRF算法下的平均周转时间和平均带权周转时间。作业提交时间估计运行时间/min18:0012028:505039:001049:5020解：作业FCFSSJFHRRF开始 完成 周转时间 时间 时间 开始 完成 周转时间 时间 时间开始 完成 周转时间 时间 时间12348:00 10:00 120 10:00 10:50 12010:50 11:00 12011:00 11:20 908:00 10:00 120 10:30 11:20 15010:00 10:10 7010:10 10:30 408:00 10:00 1

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

3、先数法执行次序执行时间等待时间周转时间EDCBA1086420101824301018242830平均作业周转时间22(3)时间片轮转算法执行次序执行时间等待时间周转时间ABCDE24681008141820212202630平均作业周转时间18按次序A B C D E B C D E C D E D E E(4)SJF算法执行次序执行时间等待时间周转时间ABCDE246810026122026122030平均作业周转时间143、 在单道批处理系统中，下列3个作业采用先来先服务调度算法和最高响应比优先算法进行调度，哪一种算法的性能最好请完成下表。作业提交时间运行时间开始时间完成时间周转时间/m

4、in带权周转时间/min110:002:00210:101:00310:250:25平均周转时间平均带权周转时间解：FCFS作业提交时间运行时间开始时间完成时间周转时间/min带权周转时间/min110:002:0010:0012:00120120/120210:101:0012:0013:00170170/60310:250:2513:0013:25180180/25平均周转时间 470/3平均带权周转时间 HRRF作业提交时间运行时间开始时间完成时间周转时间/min带权周转时间/min110:002:0010:0012:00120120/120210:101:0012:2513:25195

5、195/60310:250:2512:0012:25120120/25平均周转时间 435/3平均带权周转时间 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()w

6、hile(true)P（S2）；准备顾客的饭菜；V（S3）；process P3()while(true)P（S3）；将饭菜打包；V（S4）；process P4()while(true)P（S4）；收款并提交食品；V（S1）；coend5、 系统有A,B,C,D共4种资源，在某时刻进程P0,P1,P2,P3,P4对资源的占有和需求情况如下表所示。进程AllocationMaxAvailableA B C DA B C DA B C DP00 0 3 20 0 4 41 6 2 2P11 0 0 0 2 7 5 0P21 3 5 43 6 10 10P30 3 3 20 9 8 4P40 0

7、1 40 6 6 10(1) 系统此时处于安全状态吗(2) 若此时进程P1发出request1(1,2,2,2)，系统能分配资源给它吗为什么解：（1）利用安全性算法分析可知，此时存在一个安全序列P0,P3,P4,P1,P2，故系统是安全的。进程WorkNeedAllocationWork+ AllocationFinishA B C DA B C DA B C DP01 6 2 20 0 1 20 0 3 21 6 5 4trueP31 6 5 40 6 5 20 3 3 2 1 9 8 6trueP41 9 8 60 6 5 60 0 1 41 9 9 10trueP11 9 9 101 7

8、 5 01 0 0 0 2 9 9 10trueP22 9 9 102 3 5 61 3 5 43 12 14 14true（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） 哪个算法能最有

9、效的利用主存解：按题意地址从小到大进行分区如图所示。分区号分区长12345100KB500KB200KB300KB600KB(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。417K

10、B选中分区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、在一个请

11、求分页虚拟存储管理系统中，一个程序运行的页面走向是：1，2，3，1，4，5，1，2，1，4，5，3，4，5，对于分配给程序4个页框的情况，分别用FIFO，OPT和LRU算法，求出缺页中断次数，并给出缺页时加进主存的页号。解： （1）FIFO缺页10次，缺页时加进主存的页号见表中带星的页号。页框123145121453450 1*11115*5555554*412*22221*1111115*23*33332*22222234*4444443*33（2）OPT缺页6次，缺页时加进主存的页号见表中带星的页号。页框123145121453450 1*11111111113*3312*22222222222223*335*5555555534*444444444（3）LRU缺页7次，缺页时加进主存的页号见表中带星的页号。页框123145121453450 1*111111111111112*2225*5555555523*33332*2223*3334*4444444449、 假定磁盘有200个柱面，编号0199，当前移动臂的位置在143号柱面上，并刚刚完成125号柱面的服务请求。如果请求队列的先后顺序时：86，147，91，177，94，150，102，175，130；试问为了完成上述请求，下列算法移动臂移动的总柱面数是多少并计算移动臂移动