操作系統(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í)間1等待時(shí)間執(zhí)行時(shí)間周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間110:0012:000m120m120m156. 7m210:1013:00110m60m170m310:2513:25155m25m18

2、0m短作業(yè)優(yōu)先：1） 初 始 只 有 作 業(yè) 1 , 所 以 先 執(zhí) 行 作 業(yè) 1 , 結(jié) 束 時(shí) 間 是 1 2 : 0 0 , 此 時(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è)

3、1；2） 12:00 時(shí)有作業(yè) 2 和 3，作業(yè) 2:等待時(shí)間=12:00-10:10=110m 響應(yīng)比=1+11060=2.8;作業(yè) 3:等待時(shí)間=12:00-10:25=95m,響應(yīng)比=1+9525=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）

4、短作業(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)時(shí)間平均周轉(zhuǎn)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)18;009:000m60m60m151m3.37528:309:3030m30m60m239:009:4230m12m42m3.549:069:4836m6m42m71.有三個(gè)批處理作業(yè)，第一個(gè)作業(yè)10:00 到達(dá)，需要執(zhí)行 2 小時(shí)；第二個(gè)作業(yè)在10:10 到短作業(yè)優(yōu)先:作業(yè)順序：4、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

5、短，所以先執(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:4848m30m78m2.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+3030=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è)

6、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+246=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:000m60m60m149.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

7、。在 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ǔ)上,若進(jìn)程 P1 請(qǐng)求資源（0,2,0）,是否能實(shí)施資源分配？為什么？解：現(xiàn)有資源：E（17,5,20）可用資源：A（2,3,3）進(jìn)程所需資源ABCP1347P2134P3006P4221P5110(1) A 滿足 P4, P4 結(jié)束,A(4,3,7);A 滿足 P5

8、, 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,3,2),進(jìn)程所需資源ABCP1347P2134P3006P4020P5110存在安全序列：P4,P2,P3,P5,P1 所以可以分配資源?？捎觅Y源：A(0,3,2)(0,2,0 能滿足 P1 需求，假設(shè)分配，A(0,1,2),進(jìn)程所需資源ABCP1327P2134P3006

9、P4020P5110剩余資源不能滿足任意進(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 均發(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:

10、(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；)存在安全序列：P2,P1,P3,P4 所以答應(yīng) P2 的請(qǐng)求。(3)假設(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)入

11、阻塞狀態(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)程的資源最大需求量依次為 7 和&現(xiàn)假定它們對(duì)資源的請(qǐng)示序列如下表所示：4、為了避免死鎖，系統(tǒng)分配資源時(shí)采用銀行家算法。如果申請(qǐng)資源得不到滿足，進(jìn)程就轉(zhuǎn)入阻塞 態(tài)。根據(jù)上述信息，試描述各步驟結(jié)束時(shí)，申請(qǐng)資源的進(jìn)程是得到滿足，還是轉(zhuǎn)入阻塞狀態(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:阻塞 Q,若答應(yīng)