操作系統(tǒng)復(fù)習(xí)習(xí)題答案1

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

3、先數(shù)法執(zhí)行次序執(zhí)行時(shí)間等待時(shí)間周轉(zhuǎn)時(shí)間EDCBA1086420101824301018242830平均作業(yè)周轉(zhuǎn)時(shí)間22(3)時(shí)間片輪轉(zhuǎn)算法執(zhí)行次序執(zhí)行時(shí)間等待時(shí)間周轉(zhuǎn)時(shí)間ABCDE24681008141820212202630平均作業(yè)周轉(zhuǎn)時(shí)間18按次序A B C D E B C D E C D E D E E(4)SJF算法執(zhí)行次序執(zhí)行時(shí)間等待時(shí)間周轉(zhuǎn)時(shí)間ABCDE246810026122026122030平均作業(yè)周轉(zhuǎn)時(shí)間143、 在單道批處理系統(tǒng)中，下列3個(gè)作業(yè)采用先來(lái)先服務(wù)調(diào)度算法和最高響應(yīng)比優(yōu)先算法進(jìn)行調(diào)度，哪一種算法的性能最好請(qǐng)完成下表。作業(yè)提交時(shí)間運(yùn)行時(shí)間開(kāi)始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間/m

4、in帶權(quán)周轉(zhuǎn)時(shí)間/min110:002:00210:101:00310:250:25平均周轉(zhuǎn)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間解：FCFS作業(yè)提交時(shí)間運(yùn)行時(shí)間開(kāi)始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間/min帶權(quán)周轉(zhuǎn)時(shí)間/min110:002:0010:0012:00120120/120210:101:0012:0013:00170170/60310:250:2513:0013:25180180/25平均周轉(zhuǎn)時(shí)間 470/3平均帶權(quán)周轉(zhuǎn)時(shí)間 HRRF作業(yè)提交時(shí)間運(yùn)行時(shí)間開(kāi)始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間/min帶權(quán)周轉(zhuǎn)時(shí)間/min110:002:0010:0012:00120120/120210:101:0012:2513:25195

5、195/60310:250:2512:0012:25120120/25平均周轉(zhuǎn)時(shí)間 435/3平均帶權(quán)周轉(zhuǎn)時(shí)間 4、 一個(gè)快餐廳有4類(lèi)職員：(1)領(lǐng)班：接受顧客點(diǎn)菜；（2）廚師：準(zhǔn)備顧客的飯菜；（3）打包工：將飯菜打包；（4）出納員：收款并提交食物。每位職員可被看做一個(gè)進(jìn)程，試用一種同步機(jī)制寫(xiě)出能讓4類(lèi)職員正確并發(fā)工作的程序。解：可設(shè)4個(gè)信號(hào)量S1,S2,S3,S4來(lái)協(xié)調(diào)進(jìn)程工作。Semophore S1,S2,S3,S4;S1=1;S2=S3=S4=0;cobegein process P1()while(true)有顧客到來(lái)；P（S1）；接受顧客點(diǎn)菜；V（S2）；process P2()w

6、hile(true)P（S2）；準(zhǔn)備顧客的飯菜；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種資源，在某時(shí)刻進(jìn)程P0,P1,P2,P3,P4對(duì)資源的占有和需求情況如下表所示。進(jìn)程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) 系統(tǒng)此時(shí)處于安全狀態(tài)嗎(2) 若此時(shí)進(jìn)程P1發(fā)出request1(1,2,2,2)，系統(tǒng)能分配資源給它嗎為什么解：（1）利用安全性算法分析可知，此時(shí)存在一個(gè)安全序列P0,P3,P4,P1,P2，故系統(tǒng)是安全的。進(jìn)程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）若此時(shí)進(jìn)程P1發(fā)出request1(1,2,2,2),系統(tǒng)按銀行家算法進(jìn)行檢查：request1(1,2,2,2) =need1(1,7,5,0)，其請(qǐng)求的資源數(shù)已超過(guò)其宣布的最大值，所以不能分配。6、 給定主存空閑區(qū)，按照地址從小到大排列位：100KB,500KB,200KB,300KB,600KB?，F(xiàn)有用戶(hù)進(jìn)程依次為212KB,417KB,112KB,426KB。（1） 分別用首次適應(yīng)算法，最佳適應(yīng)算法和最壞適應(yīng)算法將他們裝入主存的哪個(gè)分區(qū)（2） 哪個(gè)算法能最有

9、效的利用主存解：按題意地址從小到大進(jìn)行分區(qū)如圖所示。分區(qū)號(hào)分區(qū)長(zhǎng)12345100KB500KB200KB300KB600KB(1) 首次適應(yīng)算法 212KB 選中分區(qū)2，這時(shí)分區(qū)2還剩288KB。417KB選中分區(qū)5，這時(shí)分區(qū)5還剩183KB。112KB選中分區(qū)2，這時(shí)分區(qū)2還剩176KB。426KB無(wú)分區(qū)能滿(mǎn)足，應(yīng)該等待。最佳適應(yīng)算法 212KB 選中分區(qū)4，這時(shí)分區(qū)4還剩88KB。417KB選中分區(qū)2，這時(shí)分區(qū)2還剩83KB。112KB選中分區(qū)3，這時(shí)分區(qū)3還剩88KB。426KB選中分區(qū)5，這時(shí)分區(qū)5還剩174KB。最壞適應(yīng)算法 212KB 選中分區(qū)5，這時(shí)分區(qū)5還剩388KB。417K

10、B選中分區(qū)2，這時(shí)分區(qū)2還剩83KB。112KB選中分區(qū)5，這時(shí)分區(qū)5還剩176KB。426KB無(wú)分區(qū)能滿(mǎn)足，應(yīng)該等待。(2) 對(duì)于該作業(yè)隊(duì)列，最佳適應(yīng)算法能最有效利用主存。7、 在一分頁(yè)存儲(chǔ)管理系統(tǒng)種，邏輯地址長(zhǎng)度為16位，頁(yè)面大小為4096B，現(xiàn)有邏輯地址2F6AH，且第0，1，2頁(yè)依次存放在第10，12，14號(hào)物理塊種，試問(wèn)相應(yīng)的物理地址是多少解：因?yàn)檫壿嫷刂烽L(zhǎng)度為16位，而頁(yè)面大小為4096字節(jié)，所以，前面的4位表示頁(yè)號(hào)。把2F6AH轉(zhuǎn)換成二進(jìn)制為：0 0 1 0 1 1 1 1 0 1 1 0 1 0 1 0，可知頁(yè)號(hào)為2。故放在14號(hào)物理塊中，寫(xiě)成十六進(jìn)制為EF6AH。8、在一個(gè)請(qǐng)

11、求分頁(yè)虛擬存儲(chǔ)管理系統(tǒng)中，一個(gè)程序運(yùn)行的頁(yè)面走向是：1，2，3，1，4，5，1，2，1，4，5，3，4，5，對(duì)于分配給程序4個(gè)頁(yè)框的情況，分別用FIFO，OPT和LRU算法，求出缺頁(yè)中斷次數(shù)，并給出缺頁(yè)時(shí)加進(jìn)主存的頁(yè)號(hào)。解： （1）FIFO缺頁(yè)10次，缺頁(yè)時(shí)加進(jìn)主存的頁(yè)號(hào)見(jiàn)表中帶星的頁(yè)號(hào)。頁(yè)框123145121453450 1*11115*5555554*412*22221*1111115*23*33332*22222234*4444443*33（2）OPT缺頁(yè)6次，缺頁(yè)時(shí)加進(jìn)主存的頁(yè)號(hào)見(jiàn)表中帶星的頁(yè)號(hào)。頁(yè)框123145121453450 1*11111111113*3312*22222222222223*335*5555555534*444444444（3）LRU缺頁(yè)7次，缺頁(yè)時(shí)加進(jìn)主存的頁(yè)號(hào)見(jiàn)表中帶星的頁(yè)號(hào)。頁(yè)框123145121453450 1*111111111111112*2225*5555555523*33332*2223*3334*4444444449、 假定磁盤(pán)有200個(gè)柱面，編號(hào)0199，當(dāng)前移動(dòng)臂的位置在143號(hào)柱面上，并剛剛完成125號(hào)柱面的服務(wù)請(qǐng)求。如果請(qǐng)求隊(duì)列的先后順序時(shí)：86，147，91，177，94，150，102，175，130；試問(wèn)為了完成上述請(qǐng)求，下列算法移動(dòng)臂移動(dòng)的總柱面數(shù)是多少并計(jì)算移動(dòng)臂移動(dòng)