操作系統(tǒng)之調(diào)度算法和死鎖中的銀行家算法習(xí)題答案

1、1. 有三個(gè)批處理作業(yè)，第一個(gè)作業(yè)10:00到達(dá)，需要執(zhí)行2小時(shí)；第二個(gè)作業(yè)在10:10到達(dá)，需要執(zhí)行1小時(shí)；第三個(gè)作業(yè)在10:25到達(dá)，需要執(zhí)行25分鐘。分別采用先來先 服務(wù)，短作業(yè)優(yōu)先和最高響應(yīng)比優(yōu)先三種調(diào)度算法，各自的平均周轉(zhuǎn)時(shí)間是多少？解：先來先服務(wù)：（結(jié)束時(shí)間=上一個(gè)作業(yè)的結(jié)束時(shí)間+執(zhí)行時(shí)間周轉(zhuǎn)時(shí)間=結(jié)束時(shí)間-到達(dá)時(shí)間=等待時(shí)間+執(zhí)行時(shí)間）按到達(dá)先后，執(zhí)行順序：1-2-3作業(yè)到達(dá)時(shí)間結(jié)束時(shí)間等待時(shí)間執(zhí)行時(shí)間周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間110:0012:000m120m120m156. 7m210:1013:00110m60m170m310:2513:25155m25m180m短作業(yè)優(yōu)先：1）

2、初始只有作業(yè)1,所以先執(zhí)行作業(yè)1,結(jié)束時(shí)間是12:00，此時(shí)有作業(yè)2和3；2）作業(yè)3需要時(shí)間短，所以先執(zhí)行；3）最后執(zhí)行作業(yè)2作業(yè)到達(dá)時(shí)間結(jié)束時(shí)間等待時(shí)間執(zhí)行時(shí)間周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間110:0012:000m120m120m145m310:2512:2595m25m120m210:1013:25135m60m195m最高響應(yīng)比優(yōu)先：高響應(yīng)比優(yōu)先調(diào)度算法既考慮作業(yè)的執(zhí)行時(shí)間也考慮作業(yè)的等待時(shí)間，綜合了先來先服務(wù) 和最短作業(yè)優(yōu)先兩種算法的特點(diǎn)。1）10:00只有作業(yè)1到達(dá)，所以先執(zhí)行作業(yè)1；2）12:00時(shí)有作業(yè)2和3，作業(yè) 2:等待時(shí)間=12:00-10:10=110m響應(yīng)比=1+110/60=

3、2.8;作業(yè) 3:等待時(shí)間=12:00-10:25=95m,響應(yīng)比=1+95/25=4.8;所以先執(zhí)行作業(yè)33）執(zhí)行作業(yè)2作業(yè)到達(dá)時(shí)間結(jié)束時(shí)間等待時(shí)間執(zhí)行時(shí)間周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間110:0012:000m120m120m145m310:2512:2595m25m120m210:1013:25135m60m195m2. 在一單道批處理系統(tǒng)中，一組作業(yè)的提交時(shí)刻和運(yùn)行時(shí)間如下表所示。試計(jì)算一下三種 作業(yè)調(diào)度算法的平均周轉(zhuǎn)時(shí)間 T和平均帶權(quán)周轉(zhuǎn)時(shí)間 W。（1）先來先服務(wù)；（2）短作業(yè)優(yōu)先 （3）高響應(yīng)比優(yōu)先 解：先來先服務(wù)：作業(yè)順序：1,2,3,4作業(yè)到達(dá)時(shí)間結(jié)束時(shí)間等待時(shí)間執(zhí)行時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)

4、時(shí)間平均周轉(zhuǎn)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)18;009:000m60m60m151m3.37528:309:3030m30m60m239:009:4230m12m42m3.549:069:4836m6m42m7短作業(yè)優(yōu)先：作業(yè)順序：1）8:00只有作業(yè)1,所以執(zhí)行作業(yè)1;2）9:00有作業(yè)2和3,作業(yè)3短，所以先執(zhí)行3;3）9:12有作業(yè)2和4,作業(yè)4短，所以先執(zhí)行4;4）執(zhí)行作業(yè)2作業(yè)到達(dá)時(shí)間結(jié)束時(shí)間等待時(shí)間執(zhí)行時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)18;009:000m60m60m140.5m1.6539:009:120m12m12m149:069:186m6m12m228:309:484

5、8m30m78m2.6高響應(yīng)比優(yōu)先： 作業(yè)順序：1） 8:00只有作業(yè)1,所以執(zhí)行作業(yè)1；2）9:00有作業(yè)2和3作業(yè)2等待時(shí)間=9:00-8:30=30m,響應(yīng)比=1+30/30=2;作業(yè)3等待時(shí)間=9:00-9:00=0m,響應(yīng)比=1+0/12=1 ； 所以執(zhí)行作業(yè)2；3）9:30有作業(yè)3和4作業(yè) 3 等待時(shí)間=9:30-9:00=30m,響應(yīng)比=1+30/12=3.5； 作業(yè)4等待時(shí)間=9:30-9:06=24m,響應(yīng)比=1+24/6=5； 所以執(zhí)行作業(yè)44） 執(zhí)行作業(yè)3作業(yè)到達(dá)時(shí)間結(jié)束時(shí)間等待時(shí)間執(zhí)行時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)18;009:000m60m60m1

6、49.5m328:309:3030m30m60m249:069:3624m6m30m539:009:4836m12m48m43.設(shè)系統(tǒng)中有3種類型的資源（A, B, C）和5個(gè)進(jìn)程（P1, P2, P3, P4, P5）, A資源的數(shù)量為17, B資源的數(shù)量為5, C資源的數(shù)量為20。在T0時(shí)刻系統(tǒng)狀態(tài)表 如下表所示。系統(tǒng)采用銀行家算法試試死鎖避免策略。（1）T0時(shí)刻是否為安全狀態(tài)？若是，請(qǐng)給出安全序列。2）在T0時(shí)刻若進(jìn)程P2請(qǐng)求資源（0,3,4）,是否能實(shí)施資源分配？為什么？（3） 在（2）的基礎(chǔ)上，若進(jìn)程 P4請(qǐng)求資源（2,0,1）,是否能實(shí)施資源分配？為什 么？（4） 在（3）的基礎(chǔ)上

7、，若進(jìn)程 P1請(qǐng)求資源（0,2,0）,是否能實(shí)施資源分配？為什 么？解：現(xiàn)有資源：E （17, 5, 20） 可用資源：A （2, 3, 3）進(jìn)程所需資源ABCP1347P2134P3006P4221P5110 A 滿足 P4, P4 結(jié)束,A(4,3,7);A 滿足 P5, P5 結(jié)束,A(7,4,11);A 滿足 P2, P2 結(jié)束,A(11,4,13);A 滿足 P3, P3 結(jié)束,A(15,4,18);A 滿足 P1, P1 結(jié)束,A(17,5,20)TO時(shí)刻是安全狀態(tài)，存在安全序列 P4,P5,P2,P3,P1.可用資源A (2, 3, 3) (2,0,1)，假設(shè)分配給 P4,A(0

8、,3,2),進(jìn)程所需資源ABCP1347P2134P3006P4020P5110存在安全序列：P4,P2,P3,P5,P1 所以可以分配資源。 可用資源：A(0,3,2)(0,2,0)能滿足P1需求，假設(shè)分配，A(0,1,2),進(jìn)程所需資源ABCP1327P2134P3006P4020P5110剩余資源不能滿足任意進(jìn)程需求，進(jìn)程將會(huì)死鎖4.某系統(tǒng)有R1,R2,R3共3類資源，在T0時(shí)刻P1,P2,P3和P4這4個(gè)進(jìn)程對(duì)資源的占用 和需求情況見下表，此刻系統(tǒng)可用資源向量為(2,1,2)。問題：(1) 將系統(tǒng)中各種資源總量和此刻各進(jìn)程對(duì)各資源的需求數(shù)目用向量或矩陣表示出來(2) 如果此時(shí)P1,P2

9、均發(fā)出資源請(qǐng)求向量 Request(1,0,1)為了保持系統(tǒng)的安全性應(yīng)該如 何分配資源？說明你所采用策略的原因。(3) 如果(2)中兩個(gè)請(qǐng)求立刻得到滿足后，系統(tǒng)此刻是否處于死鎖狀態(tài)？ 解：(1)可用資源A(2,1,2);資源總量E(需求資源R:(2) 假設(shè)資源分配給 P1 貝U, A=(2,1,2)-(1,0,1)=(1,1,1)需求資源R：A不能滿足任何進(jìn)程的需求，所以進(jìn)程死鎖，所以拒絕P1的請(qǐng)求。假設(shè)資源分配給 P2 貝U, A=(2,1,2)-(1,0,1)=(1,1,1)需求資源R：A滿足P2要求，P2完成，A (6,2,3)存在安全序列：P2,P1,P3,P4所以答應(yīng)P2的請(qǐng)求。(3

10、) 假設(shè)資源分配給 P1 貝U, A=(2,1,2)-(1,0,1)-(1,0,1)=(0,1,0)需求資源R：系統(tǒng)此刻并沒有立即進(jìn)入死鎖狀態(tài)，因?yàn)檫@時(shí)所有進(jìn)程沒有提出新的資源申請(qǐng)，全部 進(jìn)程均沒有因資源請(qǐng)求沒得到滿足而進(jìn)入阻塞狀態(tài)。只有當(dāng)進(jìn)程提出資源申請(qǐng)且全部 進(jìn)程都進(jìn)入阻塞狀態(tài)時(shí)，系統(tǒng)才處于死鎖狀態(tài)5.設(shè)有3個(gè)進(jìn)程P、Q、R,它們共享10個(gè)同類資源，P、Q、R進(jìn)程的資源最 大需求量依次為4、7和8?，F(xiàn)假定它們對(duì)資源的請(qǐng)示序列如下表所示：為了避免死鎖，系統(tǒng)分配資源時(shí)采用銀行家算法。如果申請(qǐng)資源得不到滿足，進(jìn)程就轉(zhuǎn)入阻塞態(tài)。根據(jù)上述信息，試描述各步驟結(jié)束時(shí)，申請(qǐng)資源的進(jìn)程是得到滿足，還是轉(zhuǎn)入阻

11、塞狀態(tài)，為什么？(起始狀態(tài)：各進(jìn)程均不擁有資源，無進(jìn)程處于阻塞態(tài))(如果剩余資源即可用資源大于當(dāng)前狀態(tài)任何進(jìn)程的需求，則進(jìn)程不會(huì)死鎖，且安全 序列任意，因?yàn)橐坏M足某個(gè)進(jìn)程的需求使其結(jié)束后，進(jìn)程返還占用資源，剩余資源 不變(返還資源為0)或增多，以此類推即可)需求資源R(4,7,8)資源總數(shù)E=10,也是可用資源步驟1:滿足P,剩余資源可使各進(jìn)程運(yùn)行結(jié)束，所以P得到2個(gè)資源，E =,8R： (2,7,8) 步驟2:滿足Q,剩余資源可使各進(jìn)程運(yùn)行結(jié)束，所以 Q得到4個(gè)資源，E： =4R： (2,3,8) 步驟3,滿足R,剩余資源可使各進(jìn)程運(yùn)行結(jié)束，所以 R得到2個(gè)資源，E： =2R： (2,3,6) 步驟4