操作系統(tǒng)復習題答案

1、1、 若有如下表所示的4個作業(yè)進入系統(tǒng)，分別計算在FCFS，SJF和HRRF算法下的平均周轉時間和平均帶權周轉時間。作業(yè)提交時間估計運行時間/min18:0012028:505039:001049:5020解：作業(yè)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平均周轉時間112.595102.5平均帶權周轉時間4.9753.253.7752、 有5個批處理作業(yè)AE均已到達計算中心，其運行時間分別為2min,4min,6min,8min和10min,各自的優(yōu)先級分別規(guī)定為1，2，3，4，5其中5是最高級。對于時間片輪轉算法（時間片為2min），優(yōu)先數(shù)法，短作業(yè)優(yōu)先算法，先來先服務調度算法（按照作業(yè)到達次序C,D,B,E,A），在忽略進程切換時間的前提下，計算平均作業(yè)周轉時間。解：（1）FCFS算法執(zhí)行次序執(zhí)行時間等待時間周轉時間CDBEA68410206141

3、828614182830平均作業(yè)周轉時間19.2（2）優(yōu)先數(shù)法執(zhí)行次序執(zhí)行時間等待時間周轉時間EDCBA1086420101824301018242830平均作業(yè)周轉時間22(3)時間片輪轉算法執(zhí)行次序執(zhí)行時間等待時間周轉時間ABCDE24681008141820212202630平均作業(yè)周轉時間18按次序A B C D E B C D E C D E D E E(4)SJF算法執(zhí)行次序執(zhí)行時間等待時間周轉時間ABCDE246810026122026122030平均作業(yè)周轉時間143、 在單道批處理系統(tǒng)中，下列3個作業(yè)采用先來先服務調度算法和最高響應比優(yōu)先算法進行調度，哪一種算法的性能最好？請

4、完成下表。作業(yè)提交時間運行時間開始時間完成時間周轉時間/min帶權周轉時間/min110:002:00210:101:00310:250:25平均周轉時間平均帶權周轉時間解：FCFS作業(yè)提交時間運行時間開始時間完成時間周轉時間/min帶權周轉時間/min110:002:0010:0012:00120120/120210:101:0012:0013:00170170/60310:250:2513:0013:25180180/25平均周轉時間 470/3平均帶權周轉時間 3.68HRRF作業(yè)提交時間運行時間開始時間完成時間周轉時間/min帶權周轉時間/min110:002:0010:0012:00

5、120120/120210:101:0012:2513:25195195/60310:250:2512:0012:25120120/25平均周轉時間 435/3平均帶權周轉時間 3.024、 一個快餐廳有4類職員：(1)領班：接受顧客點菜；（2）廚師：準備顧客的飯菜；（3）打包工：將飯菜打包；（4）出納員：收款并提交食物。每位職員可被看做一個進程，試用一種同步機制寫出能讓4類職員正確并發(fā)工作的程序。解：可設4個信號量S1,S2,S3,S4來協(xié)調進程工作。Semophore S1,S2,S3,S4;S1=1;S2=S3=S4=0;cobegein process P1()while(true)有

6、顧客到來；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）；coend5、 系統(tǒng)有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

7、 3 5 43 6 10 10P30 3 3 20 9 8 4P40 0 1 40 6 6 10(1) 系統(tǒng)此時處于安全狀態(tài)嗎？(2) 若此時進程P1發(fā)出request1(1,2,2,2)，系統(tǒng)能分配資源給它嗎？為什么？解：（1）利用安全性算法分析可知，此時存在一個安全序列P0,P3,P4,P1,P2，故系統(tǒng)是安全的。進程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

8、60 6 5 60 0 1 41 9 9 10trueP11 9 9 101 7 5 01 0 0 0 2 9 9 10trueP22 9 9 102 3 5 61 3 5 43 12 14 14true（2）若此時進程P1發(fā)出request1(1,2,2,2),系統(tǒng)按銀行家算法進行檢查：request1(1,2,2,2) =need1(1,7,5,0)，其請求的資源數(shù)已超過其宣布的最大值，所以不能分配。6、 給定主存空閑區(qū)，按照地址從小到大排列位：100KB,500KB,200KB,300KB,600KB?，F(xiàn)有用戶進程依次為212KB,417KB,112KB,426KB。（1） 分別用首次適

9、應算法，最佳適應算法和最壞適應算法將他們裝入主存的哪個分區(qū)？（2） 哪個算法能最有效的利用主存？解：按題意地址從小到大進行分區(qū)如圖所示。分區(qū)號分區(qū)長12345100KB500KB200KB300KB600KB(1) 首次適應算法 212KB 選中分區(qū)2，這時分區(qū)2還剩288KB。417KB選中分區(qū)5，這時分區(qū)5還剩183KB。112KB選中分區(qū)2，這時分區(qū)2還剩176KB。426KB無分區(qū)能滿足，應該等待。最佳適應算法 212KB 選中分區(qū)4，這時分區(qū)4還剩88KB。417KB選中分區(qū)2，這時分區(qū)2還剩83KB。112KB選中分區(qū)3，這時分區(qū)3還剩88KB。426KB選中分區(qū)5，這時分區(qū)5還剩

10、174KB。最壞適應算法 212KB 選中分區(qū)5，這時分區(qū)5還剩388KB。417KB選中分區(qū)2，這時分區(qū)2還剩83KB。112KB選中分區(qū)5，這時分區(qū)5還剩176KB。426KB無分區(qū)能滿足，應該等待。(2) 對于該作業(yè)隊列，最佳適應算法能最有效利用主存。7、 在一分頁存儲管理系統(tǒng)種，邏輯地址長度為16位，頁面大小為4096B，現(xiàn)有邏輯地址2F6AH，且第0，1，2頁依次存放在第10，12，14號物理塊種，試問相應的物理地址是多少？解：因為邏輯地址長度為16位，而頁面大小為4096字節(jié)，所以，前面的4位表示頁號。把2F6AH轉換成二進制為：0 0 1 0 1 1 1 1 0 1 1 0 1

11、0 1 0，可知頁號為2。故放在14號物理塊中，寫成十六進制為EF6AH。8、在一個請求分頁虛擬存儲管理系統(tǒng)中，一個程序運行的頁面走向是：1，2，3，1，4，5，1，2，1，4，5，3，4，5，對于分配給程序4個頁框的情況，分別用FIFO，OPT和LRU算法，求出缺頁中斷次數(shù)，并給出缺頁時加進主存的頁號。解： （1）FIFO缺頁10次，缺頁時加進主存的頁號見表中帶星的頁號。頁框123145121453450 1*11115*5555554*412*22221*1111115*23*33332*22222234*4444443*33（2）OPT缺頁6次，缺頁時加進主存的頁號見表中帶星的頁號。頁框

12、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；試問為了完成上述請求，下列算法移動臂移動的總柱面數(shù)是多少？并計算移動臂移動的順序。（1） FCFS（2） SSTF（3） SCAN解：（1）FCFS 為565，依次為143-86-147-91-177-94-150-