操作系統(tǒng)孫鐘秀課后答案

1、.CH1 應(yīng)用題參考答案1 有一臺(tái)計(jì)算機(jī)，具有1MB內(nèi)存，操作系統(tǒng)占用200KB，每個(gè)用戶進(jìn)程各占200KB。如果用戶進(jìn)程等待I/O的時(shí)間為80%，若增加1MB內(nèi)存，則CPU的利用率提高多少？答：設(shè)每個(gè)進(jìn)程等待I/O的百分比為P，則n個(gè)進(jìn)程同時(shí)等待I/O的概率是Pn ，當(dāng)n個(gè)進(jìn)程同時(shí)等待I/O期間CPU是空閑的，故CPU的利用率為1-Pn 。由題意可知，除去操作系統(tǒng)，內(nèi)存還能容納4個(gè)用戶進(jìn)程，由于每個(gè)用戶進(jìn)程等待I/O的時(shí)間為80%，故： CPU利用率=1-(80%)4 =0.59若再增加1MB內(nèi)存，系統(tǒng)中可同時(shí)運(yùn)行9個(gè)用戶進(jìn)程，此時(shí)： CPU利用率=1-(80%)9 =0.87故增加1MB內(nèi)

2、存使CPU的利用率提高了47%： 87%÷59%=147% 147%-100%=47%2 一個(gè)計(jì)算機(jī)系統(tǒng)，有一臺(tái)輸入機(jī)和一臺(tái)打印機(jī)，現(xiàn)有兩道程序投入運(yùn)行，且程序A先開始做，程序B后開始運(yùn)行。程序A的運(yùn)行軌跡為：計(jì)算50ms、打印100ms、再計(jì)算50ms、打印100ms，結(jié)束。程序B的運(yùn)行軌跡為：計(jì)算50ms、輸入80ms、再計(jì)算100ms，結(jié)束。試說明(1)兩道程序運(yùn)行時(shí)，CPU有無空閑等待？若有，在哪段時(shí)間內(nèi)等待？為什么會(huì)等待？(2)程序A、B有無等待CPU的情況？若有，指出發(fā)生等待的時(shí)刻。答：畫出兩道程序并發(fā)執(zhí)行圖如下：處理器輸入機(jī)打印機(jī)程序A程序BA計(jì)算B計(jì)算計(jì)算計(jì)算時(shí)間(m

3、s)0 50 100 150 180 200 250 300打印計(jì)算打印輸入計(jì)算A打印A打印B輸入A計(jì)算B計(jì)算一(1) 兩道程序運(yùn)行期間，CPU存在空閑等待，時(shí)間為100至150ms之間(見圖中有色部分)。(2) 程序A無等待現(xiàn)象，但程序B有等待。程序B有等待時(shí)間段為180ms至200ms間(見圖中有色部分)。3 設(shè)有三道程序，按A、B、C優(yōu)先次序運(yùn)行，其內(nèi)部計(jì)算和I/O操作時(shí)間由圖給出。ABCC1130msC21=60msC31=20msI1240msI22=30msI32=40msC1310msC23=10msC33=20ms試畫出按多道運(yùn)行的時(shí)間關(guān)系圖（忽略調(diào)度執(zhí)行時(shí)間）。完成三道程序共

4、花多少時(shí)間？比單道運(yùn)行節(jié)省了多少時(shí)間？若處理器調(diào)度程序每次進(jìn)行程序轉(zhuǎn)換化時(shí)1ms，試畫出各程序狀態(tài)轉(zhuǎn)換的時(shí)間關(guān)系圖。答：1） 忽略調(diào)度執(zhí)行時(shí)間，多道運(yùn)行方式（搶占式）：時(shí)間 0 3 7 8 10 12 13 14 17 19 單位10 msI/O I12 I22 I32 CPU C11 C21 C13 C21 C31 C23 C33 搶占式共用去190ms，單道完成需要260ms， 節(jié)省70ms。 忽略調(diào)度執(zhí)行時(shí)間，多道運(yùn)行方式（非搶占式）：時(shí)間 0 3 7 9 10 12 13 14 16 18 單位10 msI/O I12 I22 I32 CPU C11 C21 C13 C31 C23 C

5、33 非搶占式共用去180ms，單道完成需要260ms， 節(jié)省80ms。2） 調(diào)度執(zhí)行時(shí)間1ms，多道運(yùn)行方式（搶占式）：時(shí)間 0 303132 71727374 8485 105107 127 136137 147 177178 198 單位1msI/O I12 I22 I32 CPU C11 C21 C13 C21 C31 C23 C33 OS 調(diào)度執(zhí)行時(shí)間1ms，多道運(yùn)行方式（非搶占式）：時(shí)間 0 303132 7172 939495 105106 124125127129 139 168169 189 單位1msI/O I12 I22 I32 CPU C11 C21 C21 C13 C

6、31 C31 C23 C33 OS 4 在單CPU和兩臺(tái)I/O(I1,I2)設(shè)備的多道程序設(shè)計(jì)環(huán)境下，同時(shí)投入三個(gè)作業(yè)運(yùn)行。它們的執(zhí)行軌跡如下：Job1：I2(30ms)、CPU(10ms)、I1(30ms)、CPU(10ms)、I2(20ms)Job2：I1(20ms)、CPU(20ms)、I2(40ms)Job3：CPU(30ms)、I1(20ms)、CPU(10ms)、I1(10ms)如果CPU、I1和I2都能并行工作，優(yōu)先級(jí)從高到低為Job1、Job2和Job3，優(yōu)先級(jí)高的作業(yè)可以搶占優(yōu)先級(jí)低的作業(yè)的CPU，但不搶占I1和I2。試求：(1)每個(gè)作業(yè)從投入到完成分別所需的時(shí)間。(2) 從

7、投入到完成CPU的利用率。(3)I/O設(shè)備利用率。答：畫出三個(gè)作業(yè)并行工作圖如下(圖中著色部分為作業(yè)等待時(shí)間)：CPUI1I2Job1Job2Job3時(shí)間(ms)CPU CPU0 10 20 30 40 50 60 70 80 90 100 110CPU I1I1 I1CPUCPU I2 I2CPU I1CPU I2 Job1 Job2 Job3Job2Job1Job2Job3Job1Job3 Job2Job1 Job1Job3Job3(1) Job1從投入到運(yùn)行完成需110ms，Job2從投入到運(yùn)行完成需90ms，Job3從投入到運(yùn)行完成需110ms。(2) CPU空閑時(shí)間段為：60ms至7

8、0ms，80ms至90ms，100ms至110ms。所以CPU利用率為(110-30)/110=72.7%。(3) 設(shè)備I1空閑時(shí)間段為：20ms至40ms，90ms至100ms，故I1的利用率為(110-30)/110=72.7%。設(shè)備I2空閑時(shí)間段為：30ms至50ms，故I2的利用率為(110-20)/110=81.8%。5 在單CPU和兩臺(tái)I/O(I1,I2)設(shè)備的多道程序設(shè)計(jì)環(huán)境下，同時(shí)投入三個(gè)作業(yè)運(yùn)行。它們的執(zhí)行軌跡如下：Job1：I2(30ms)、CPU(10ms)、I1(30ms)、CPU(10ms)Job2：I1(20ms)、CPU(20ms)、I2(40ms)Job3：CP

9、U(30ms)、I1(20ms)如果CPU、I1和I2都能并行工作，優(yōu)先級(jí)從高到低為Job1、Job2和Job3，優(yōu)先級(jí)高的作業(yè)可以搶占優(yōu)先級(jí)低的作業(yè)的CPU。試求：(1)每個(gè)作業(yè)從投入到完成分別所需的時(shí)間。(2) 每個(gè)作業(yè)投入到完成CPU的利用率。(3)I/O設(shè)備利用率。答：畫出三個(gè)作業(yè)并行工作圖如下(圖中著色部分為作業(yè)等待時(shí)間)：CPUI1I2Job1Job2Job3時(shí)間(ms)CPU CPU0 10 20 30 40 50 60 70 80 90 I1 I1CPUCPU I2 I2CPU I1CPU Job1 Job2 Job3Job2Job1Job2Job3Job1 Job2 Job1

10、Job3(1) Job1從投入到運(yùn)行完成需80ms，Job2從投入到運(yùn)行完成需90ms，Job3從投入到運(yùn)行完成需90ms。(2) CPU空閑時(shí)間段為：60ms至70ms，80ms至90ms。所以CPU利用率為(90-20)/90=77.78%。(3) 設(shè)備I1空閑時(shí)間段為：20ms至40ms，故I1的利用率為(90-20)/90=77.78%。設(shè)備I2空閑時(shí)間段為：30ms至50ms，故I2的利用率為(90-20)/90=77.78%。6 若內(nèi)存中有3道程序A、B、C，它們按A、B、C優(yōu)先次序運(yùn)行。各程序的計(jì)算軌跡為：A：計(jì)算(20)、I/O(30)、計(jì)算(10) B：計(jì)算(40)、I/O(

11、20)、計(jì)算(10)C：計(jì)算(10)、I/O(30)、計(jì)算(20)如果三道程序都使用相同設(shè)備進(jìn)行I/O(即程序用串行方式使用設(shè)備，調(diào)度開銷忽略不計(jì))。試分別畫出單道和多道運(yùn)行的時(shí)間關(guān)系圖。兩種情況下，CPU的平均利用率各為多少?答：分別畫出單道和多道運(yùn)行的時(shí)間圖0 20 40 50 60 80 100 120 140 160 180 190I/OCPU時(shí)間(ms)AAABBB C CC(1) 單道運(yùn)行時(shí)間關(guān)系圖單道總運(yùn)行時(shí)間為190ms。CPU利用率為(190-80)/190=57.9%(1) 單道運(yùn)行時(shí)間關(guān)系圖I/OCPU時(shí)間(ms)AAAB C0 20 40 50 60 80 100 12

12、0 140 BBCCB多道總運(yùn)行時(shí)間為140ms。CPU利用率為(140-30)/140=78.6%7 若內(nèi)存中有3道程序A、B、C，優(yōu)先級(jí)從高到低為A、B和C，它們單獨(dú)運(yùn)行時(shí)的CPU和I/O占用時(shí)間為：程序A： 60 20 30 10 40 20 20 (ms) I/O2 CPU I/O1 CPU I/O1 CPU I/O1程序B： 30 40 70 30 30 (ms) I/O1 CPU I/O2 CPU I/O2程序C： 40 60 30 70 (ms) CPU I/O1 CPU I/O2如果三道程序同時(shí)并發(fā)執(zhí)行，調(diào)度開銷忽略不計(jì)，但優(yōu)先級(jí)高的程序可中斷優(yōu)先級(jí)低的程序，優(yōu)先級(jí)與I/O設(shè)備

13、無關(guān)。試畫出多道運(yùn)行的時(shí)間關(guān)系圖，并問最早與最遲結(jié)束的程序是哪個(gè)？每道程序執(zhí)行到結(jié)束分別用了多少時(shí)間？計(jì)算三個(gè)程序全部運(yùn)算結(jié)束時(shí)的CPU利用率?答：畫出三個(gè)作業(yè)并發(fā)執(zhí)行的時(shí)間圖：.CPUI01I02ABC時(shí)間(ms)cpu0 30 60 90 120 150 180 210 240 270 300 330 I01 cpucpu I02 I02 cpu cpuI01cpu A BBA B CB C A CI01 cpu I01A C AAcpu cpu I01 cpu cpu I02I02 B C B CA(1) 最早結(jié)束的程序?yàn)锽，最后結(jié)束的程序?yàn)镃。(2) 程序A為250ms。程序B為220

14、ms。程序C為310ms。(3) CPU利用率為(310-120)/310=61.3%8 有兩個(gè)程序，A程序按順序使用：(CPU)10秒、(設(shè)備甲)5秒、(CPU)5秒、(設(shè)備乙)10秒、(CPU)10秒。B程序按順序使用：(設(shè)備甲)10秒、(CPU)10秒、(設(shè)備乙)5秒、(CPU)5秒、(設(shè)備乙)10秒。在順序環(huán)境下先執(zhí)行A，再執(zhí)行B，求出總的CPU利用率為多少?答：程序A執(zhí)行了40秒，其中CPU用了25秒。程序B執(zhí)行了40秒，其中CPU用了15秒。兩個(gè)程序共用了80秒，CPU化了40秒。故CPU利用率為40/80=50%。9 在某計(jì)算機(jī)系統(tǒng)中，時(shí)鐘中斷處理程序每次執(zhí)行的時(shí)間為2ms（包括

15、進(jìn)程切換開銷）。若時(shí)鐘中斷頻率為60HZ，試問CPU用于時(shí)鐘中斷處理的時(shí)間比率為多少?答：因時(shí)鐘中斷頻率為60HZ，所以，時(shí)鐘周期為：1/60s=50/3ms。在每個(gè)時(shí)鐘周期中，CPU花2ms執(zhí)行中斷任務(wù)。所以，CPU用于時(shí)鐘中斷處理的時(shí)間比率為：2(50/3)=6/50=12%。CH2 應(yīng)用題參考答案1 下列指令中哪些只能在核心態(tài)運(yùn)行? (1) 讀時(shí)鐘日期；（2）訪管指令；（3）設(shè)時(shí)鐘日期；（4）加載PSW；（5）置特殊寄存器；(6) 改變存儲(chǔ)器映象圖；(7) 啟動(dòng)I/O指令。答：(3)，(4)，(5)，(6)，(7)。2 假設(shè)有一種低級(jí)調(diào)度算法是讓“最近使用處理器較少的進(jìn)程”運(yùn)行，試解釋這

16、種算法對(duì)“I/O繁重”型作業(yè)有利，但并不是永遠(yuǎn)不受理“處理器繁重”型作業(yè)。答：因?yàn)镮/O繁忙型作業(yè)忙于I/O，所以它CPU用得少，按調(diào)度策略能優(yōu)先執(zhí)行。同樣原因一個(gè)進(jìn)程等待CPU足夠久時(shí)，由于它是“最近使用處理器較少的進(jìn)程”，就能被優(yōu)先調(diào)度，故不會(huì)饑餓。3 并發(fā)進(jìn)程之間有什么樣的相互制約關(guān)系?下列日常生活中的活動(dòng)是屬哪種制約關(guān)系：(1)踢足球，(2)吃自助餐，(3)圖書館借書，(4)電視機(jī)生產(chǎn)流水線工序。答：并發(fā)進(jìn)程之間的基本相互制約關(guān)系有互斥和同步兩種。其中(1)、(3)為互斥問題。(2)、(4)為同步問題。4 在按動(dòng)態(tài)優(yōu)先數(shù)調(diào)度進(jìn)程的系統(tǒng)中，每個(gè)進(jìn)程的優(yōu)先數(shù)需定時(shí)重新計(jì)算。在處理器不斷地在

17、進(jìn)程之間交替的情況下，重新計(jì)算進(jìn)程優(yōu)先數(shù)的時(shí)間從何而來?答：許多操作系統(tǒng)重新計(jì)算進(jìn)程的優(yōu)先數(shù)在時(shí)鐘中斷處理例程中進(jìn)行，由于中斷是隨機(jī)的，碰到哪個(gè)進(jìn)程，就插入哪個(gè)進(jìn)程中運(yùn)行處理程序，并把處理時(shí)間記在這個(gè)進(jìn)程的賬上。5 若后備作業(yè)隊(duì)列中等待運(yùn)行的同時(shí)有三個(gè)作業(yè)J1、J2、J3，已知它們各自的運(yùn)行時(shí)間為a、b、c，且滿足a<b<c，試證明采用短作業(yè)優(yōu)先算法調(diào)度能獲得最小平均作業(yè)周轉(zhuǎn)時(shí)間。答：采用短作業(yè)優(yōu)先算法調(diào)度時(shí)，三個(gè)作業(yè)的總周轉(zhuǎn)時(shí)間為： T1=a+(a+b)+(a+b+c)=3a+2b+c 若不按短作業(yè)優(yōu)先算法調(diào)度，不失一般性，設(shè)調(diào)度次序?yàn)椋篔2、J1、J3。則三個(gè)作業(yè)的總周轉(zhuǎn)時(shí)間為

18、：T2=b+(b+a)+(b+a+c)=3b+2a+c 令-式得到： T2-T1=b-a>0可見，采用短作業(yè)優(yōu)先算法調(diào)度才能獲得最小平均作業(yè)周轉(zhuǎn)時(shí)間。6 若有一組作業(yè)J1，Jn，其執(zhí)行時(shí)間依次為S1，Sn。如果這些作業(yè)同時(shí)到達(dá)系統(tǒng)，并在一臺(tái)單CPU處理器上按單道方式執(zhí)行。試找出一種作業(yè)調(diào)度算法，使得平均作業(yè)周轉(zhuǎn)時(shí)間最短。答：首先，對(duì)n個(gè)作業(yè)按執(zhí)行時(shí)間從小到大重新進(jìn)行排序，則對(duì)n個(gè)作業(yè)：J1，Jn，它們的運(yùn)行時(shí)間滿足：S1 S2 S(n-1)Sn。那么有： T=S1 +( S1+S2)+ (S1 + S2+ S3)+(S1 + S2+ S3+ Sn)/n =n×S1 +( n-1

19、)×S2+ (n-3)×S3+ Sn/n =(S1 + S2+ S3+ Sn)-0×S1+1×S2 +2×S3 +(n-1) Sn/n由于任何調(diào)度方式下，S1 + S2+ S3+ Sn為一個(gè)確定的數(shù)，而當(dāng)S1 S2 S(n-1)Sn 時(shí)才有：0×S1+1×S2 +2×S3 +(n-1) Sn的值最大，也就是說，此時(shí)T值最小。所以，按短作業(yè)優(yōu)先調(diào)度算法調(diào)度時(shí)，使得平均作業(yè)周轉(zhuǎn)時(shí)間最短。7 假定執(zhí)行表中所列作業(yè)，作業(yè)號(hào)即為到達(dá)順序，依次在時(shí)刻0按次序1、2、3、4、5進(jìn)入單處理器系統(tǒng)。1） 分別用先來先服務(wù)調(diào)度算法、時(shí)

20、間片輪轉(zhuǎn)算法、短作業(yè)優(yōu)先算法及非強(qiáng)占優(yōu)先權(quán)調(diào)度算法算出各作業(yè)的執(zhí)行先后次序(注意優(yōu)先權(quán)高的數(shù)值小)；2） 計(jì)算每種情況下作業(yè)的平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。作業(yè)號(hào)執(zhí)行時(shí)間優(yōu)先權(quán)1234510121531342答：(1) 采用FCFS算法調(diào)度作業(yè)，運(yùn)作情況：執(zhí)行次序 執(zhí)行時(shí)間 等待時(shí)間 開始時(shí)間 完成時(shí)間 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間 1 10 0 0 10 10 1 2 1 10 10 11 11 11 3 2 11 11 13 13 6.5 4 1 13 13 14 14 14 5 5 14 14 19 19 3.8作業(yè)平均周轉(zhuǎn)時(shí)間 T=(10+11+13+14+19)/5=13.4作業(yè)平均帶權(quán)

21、周轉(zhuǎn)時(shí)間 W=(1+11+6.5+14+3.8)/5=7.26(2) 采用RR算法調(diào)度作業(yè)，若令時(shí)間片長=1，各作業(yè)執(zhí)行情況為：1、2、3、4、5、1、3、5、1、5、1、5、1、5、1、1、1、1、1。作業(yè) 執(zhí)行時(shí)間 提交時(shí)間 完成時(shí)間 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間 1 10 0 19 19 1.9 2 1 0 2 2 2 3 2 0 7 7 3.5 4 1 0 4 4 4 5 5 0 14 14 2.8 作業(yè)平均周轉(zhuǎn)時(shí)間 T=(19+2+7+4+14)/5=9.2作業(yè)平均帶權(quán)周轉(zhuǎn)時(shí)間 W=(1.9+2+3.5+4+2.8)/5=2.84(3) 采用SJF算法調(diào)度作業(yè)，運(yùn)作情況：執(zhí)行次序 執(zhí)行時(shí)間

22、 等待時(shí)間 開始時(shí)間 完成時(shí)間 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間 2 1 0 0 1 1 1 4 1 1 1 2 2 2 3 2 2 2 4 4 2 5 5 4 4 9 9 1.8 1 10 9 9 19 19 1.9作業(yè)平均周轉(zhuǎn)時(shí)間 T=(1+2+4+9+19)/5=7作業(yè)平均帶權(quán)周轉(zhuǎn)時(shí)間 W=(1+2+2+1.8+1.9)/5=1.74(4) 采用非剝奪優(yōu)先權(quán)算法調(diào)度作業(yè)，運(yùn)作情況：執(zhí)行次序 優(yōu)先數(shù) 執(zhí)行時(shí)間 等待時(shí)間 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間 2 1 1 0 1 1 5 2 5 1 6 1.2 1 3 10 6 16 1.6 3 3 2 16 18 9 4 4 1 18 19 19 作業(yè)平均周轉(zhuǎn)時(shí)間

23、 T=(1+6+16+18+19)/5=12作業(yè)平均帶權(quán)周轉(zhuǎn)時(shí)間 W=(1+1.2+1.6+9+19)/5=6.368 對(duì)某系統(tǒng)進(jìn)行監(jiān)測(cè)后表明平均每個(gè)進(jìn)程在I/O阻塞之前的運(yùn)行時(shí)間為T。一次進(jìn)程切換的系統(tǒng)開銷時(shí)間為S。若采用時(shí)間片長度為Q的時(shí)向片輪轉(zhuǎn)法，對(duì)下列各種情況算出CPU利用率。1）Q 2）QT 3）SQT 4QS 5Q接近于0答：1）Q= CPU利用率=T/（T+S）2）Q>T CPU利用率=T/（T+S）3）T>Q>S CPU利用率=Q/（Q+S）4) Q=S CPU利用率=50%5) Q0 CPU利用率09 有5個(gè)待運(yùn)行的作業(yè)，各自預(yù)計(jì)運(yùn)行時(shí)間分別是：9、6、3、

24、5和x，采用哪種運(yùn)行次序使得平均響應(yīng)時(shí)間最短？答：按照最短作業(yè)優(yōu)先的算法可以使平均響應(yīng)時(shí)間最短。X取值不定，按照以下情況討論：1） x3 次序?yàn)椋簒，3，5，6，92） 3<x5 次序?yàn)椋?，x，5，6，93） 5<x6 次序?yàn)椋?，5，x，6，94） 6<x9 次序?yàn)椋?，5，6，x，95） 9<x 次序?yàn)椋?，5，6，9，x10 有5個(gè)批處理作業(yè)A到E均已到達(dá)計(jì)算中心，其運(yùn)行時(shí)間分別2、4、6、8和10分鐘；各自的優(yōu)先級(jí)分別被規(guī)定為1、2、3、4和5，這里5為最高級(jí)。對(duì)于1）時(shí)間片輪轉(zhuǎn)算法、2）優(yōu)先數(shù)法、3）短作業(yè)優(yōu)先算法、4）先來先服務(wù)調(diào)度算法(按到達(dá)次序C、D、

25、B、E、A)，在忽略進(jìn)程切換時(shí)間的前提下，計(jì)算出平均作業(yè)周轉(zhuǎn)時(shí)間。（對(duì)1）每個(gè)作業(yè)獲得相同的2分鐘長的時(shí)間片；對(duì)2）到4）采用單道運(yùn)行，直到結(jié)束。）答：(1)FCFS調(diào)度算法執(zhí)行次序 執(zhí)行時(shí)間 等待時(shí)間 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間 C 6 0 6 1 D 8 6 14 1.75 B 4 14 18 4.5 E 10 18 28 2.8 A 2 28 30 15作業(yè)平均周轉(zhuǎn)時(shí)間 T=(6+14+18+28+30)/5=19.2作業(yè)平均帶權(quán)周轉(zhuǎn)時(shí)間 W=(1+1.75+4.5+2.8+15)/5=5.01(2)優(yōu)先級(jí)調(diào)度算法執(zhí)行次序 執(zhí)行時(shí)間 等待時(shí)間 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間 E 10 0 10 1

26、D 8 10 18 2.25 C 6 18 24 4 B 4 24 28 7 A 2 28 30 15作業(yè)平均周轉(zhuǎn)時(shí)間 T=(10+18+24+28+30)/5=22作業(yè)平均帶權(quán)周轉(zhuǎn)時(shí)間 W=(1+2.25+4+7+15)/5=5.85(3)時(shí)間片輪轉(zhuǎn)法按次序A B C D E B C D EC D E D E E輪轉(zhuǎn)執(zhí)行。 作業(yè) 執(zhí)行時(shí)間 等待時(shí)間 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間 A 2 0 2 1 B 4 8 12 3 C 6 14 20 3.33 D 8 18 26 3.25 E 10 20 30 3作業(yè)平均周轉(zhuǎn)時(shí)間 T=(2+12+20+26+30)/5=18作業(yè)平均帶權(quán)周轉(zhuǎn)時(shí)間 W=(1+3

27、+3.33+3.25+3)/5=2.71(4)SJF調(diào)度算法 作業(yè) 執(zhí)行時(shí)間 等待時(shí)間 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間 A 2 0 2 1 B 4 2 6 1.5 C 6 6 12 2 D 8 12 20 2.5 E 10 20 30 3作業(yè)平均周轉(zhuǎn)時(shí)間 T=(2+6+12+20+30)/5=14作業(yè)平均帶權(quán)周轉(zhuǎn)時(shí)間 W=(1+1.5+2+2.5+3)/5=211 有5個(gè)批處理作業(yè)A到E均已到達(dá)計(jì)算中心，其運(yùn)行時(shí)間分別10、6、2、4和8分鐘；各自的優(yōu)先級(jí)分別被規(guī)定為3、5、2、1和4，這里5為最高級(jí)。若不考慮系統(tǒng)切換開銷，計(jì)算出平均作業(yè)周轉(zhuǎn)時(shí)間。（1）FCFS(按A、B、C、D、E)；(2)優(yōu)先級(jí)調(diào)

28、度算法，(3)時(shí)間片輪轉(zhuǎn)法(每個(gè)作業(yè)獲得相同的2分鐘長的時(shí)間片)。答：(1)FCFS調(diào)度算法執(zhí)行次序 執(zhí)行時(shí)間 等待時(shí)間 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間 A 10 0 10 1 B 6 10 16 2.66 C 2 16 18 9 D 4 18 22 5.5 E 8 22 30 3.75作業(yè)平均周轉(zhuǎn)時(shí)間 T=(10+16+18+22+30)/5=19.2作業(yè)平均帶權(quán)周轉(zhuǎn)時(shí)間 W=(1+2.66+9+5.5+3.75)/5=4.38(2)優(yōu)先級(jí)調(diào)度算法執(zhí)行次序 執(zhí)行時(shí)間 等待時(shí)間 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間 B 6 0 6 1 E 8 6 14 1.75 A 10 14 24 2.4 C 2 24 26 1

29、3 D 4 26 30 7.5作業(yè)平均周轉(zhuǎn)時(shí)間 T=(6+14+24+26+30)/5=20作業(yè)平均帶權(quán)周轉(zhuǎn)時(shí)間 W=(1+1.75+2.4+13+7.5)/5=5.13(3)時(shí)間片輪轉(zhuǎn)法按次序A B C D E A B D E A B E A E A輪轉(zhuǎn)執(zhí)行。 作業(yè) 執(zhí)行時(shí)間 等待時(shí)間 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間 A 10 20 30 3 B 6 16 22 3.66 C 2 4 6 3 D 4 12 16 4 E 8 20 28 3.5作業(yè)平均周轉(zhuǎn)時(shí)間 T=(30+22+6+16+28)/5=20.4作業(yè)平均帶權(quán)周轉(zhuǎn)時(shí)間 W=(3+3.66+3+4+3.5)/5=3.4312 (1)假定一個(gè)處

30、理器正在執(zhí)行兩道作業(yè)，一道以計(jì)算為主，另一道以輸入輸出為主，你將怎樣賦予它們占有處理器的優(yōu)先級(jí)?為什么?(2)假定一個(gè)處理器正在執(zhí)行三道作業(yè)，一道以計(jì)算為主，第二道以輸入輸出為主，第三道為計(jì)算與輸入輸出均勻。應(yīng)該如何賦予它們占有處理器的優(yōu)先級(jí)使得系統(tǒng)效率較高？答：處理器調(diào)度算法會(huì)考慮以下因素：作業(yè)響應(yīng)時(shí)間要求；讓CPU盡量和外圍設(shè)備并行工作；限制一個(gè)計(jì)算進(jìn)程長時(shí)間霸占處理器。因而，(1)I/O為主作業(yè)優(yōu)先級(jí)高。(2) 輸入輸出為主作業(yè)優(yōu)先級(jí)最高，輸入輸出均勻的作業(yè)其次，而計(jì)算為主作業(yè)的優(yōu)先級(jí)最低。13 請(qǐng)你設(shè)計(jì)一種先進(jìn)的計(jì)算機(jī)體系結(jié)構(gòu)，它使用硬件而不是中斷來完成進(jìn)程切換，則CPU需要哪些信息?

31、 請(qǐng)描述用硬件完成進(jìn)程切換的工作過程。答：該計(jì)算機(jī)有一個(gè)專用硬件寄存器，它始終存放指向當(dāng)前運(yùn)行進(jìn)程的PCB的指針。當(dāng)系統(tǒng)中發(fā)生了一個(gè)事件，如I/O結(jié)束事件，CPU便可把運(yùn)行進(jìn)程的上下文保存到專用硬件寄存器指針指向的PCB中保護(hù)起來，然后，CPU轉(zhuǎn)向中斷向量表，找到設(shè)備中斷處理程序入口，讓專用硬件寄存器指針指向(設(shè)備)中斷服務(wù)例程，于是，便可啟動(dòng)中斷服務(wù)例程工作。14 單道批處理系統(tǒng)中，下列三個(gè)作業(yè)采用先來先服務(wù)調(diào)度算法和最高響應(yīng)比優(yōu)先算法進(jìn)行調(diào)度，哪一種算法性能較好？請(qǐng)完成下表：作業(yè)提交時(shí)間運(yùn)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間123100010101025200100025平均作業(yè)周轉(zhuǎn)

32、時(shí)間平均作業(yè)帶權(quán)周轉(zhuǎn)時(shí)間W=答：FIFO作業(yè)提交時(shí)間運(yùn)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間12310001010102520010002510:0012:0013:0012:0013:0013:2522:503120/120145/60180/25平均作業(yè)周轉(zhuǎn)時(shí)間2.61平均作業(yè)帶權(quán)周轉(zhuǎn)時(shí)間W=3.54HRRF作業(yè)提交時(shí)間運(yùn)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間12310001010102520010002510:0012:2512:0012:0013:2512:2523:152120/120195/60120/25平均作業(yè)周轉(zhuǎn)時(shí)間2.41平均作業(yè)帶權(quán)周轉(zhuǎn)時(shí)間W=3.02可見HRRF

33、比FIFO要好。15 若有如表所示四個(gè)作業(yè)進(jìn)入系統(tǒng)，分別計(jì)算在FCFS、SJF和HRRF算法下的平均周轉(zhuǎn)時(shí)間與帶權(quán)平均周轉(zhuǎn)時(shí)間。(時(shí)間以十進(jìn)制表示)作業(yè) 提交時(shí)間(時(shí)) 估計(jì)運(yùn)行時(shí)間(小時(shí)) 開始執(zhí)行時(shí)間(時(shí)) 1 8.00 2.00 8.00 2 8.50 0.50 10.30 3 9.00 0.10 10.00 4 9.50 0.20 10.10答： FCFS SJF HRRF作業(yè) 開始 完成 周轉(zhuǎn) 開始 完成 周轉(zhuǎn) 開始 完成 周轉(zhuǎn)時(shí)間 時(shí)間 時(shí)間 時(shí)間 時(shí)間 時(shí)間 時(shí)間 時(shí)間 時(shí)間1 8.00 10.00 2.00 8.00 10.00 2.00 8.00 10.00 2.002 10

34、.00 10.50 2.00 10.30 10.80 2.30 10.10 10.60 2.103 10.50 10.60 1.60 10.00 10.10 1.10 10.00 10.10 1.104 10.60 10.80 1.30 10.10 10.30 0.80 10.60 10.80 1.30平均周 T=1.725 T=1.55 T=1.625轉(zhuǎn)時(shí)間=帶權(quán)平均 W=6.875 W=5.15 W=5.675周轉(zhuǎn)時(shí)間=16 Kleinrock提出一種動(dòng)態(tài)優(yōu)先權(quán)算法：進(jìn)程在就緒隊(duì)列等待時(shí)，其優(yōu)先權(quán)以速率變化； 當(dāng)進(jìn)程在處理器上運(yùn)行，時(shí)其優(yōu)先權(quán)以速率變化。給參數(shù)、賦以不同值可得到不同算法。(

35、1)若>>0是什么算法？(2) 若<<0是什么算法答：(1) 是先進(jìn)先出算法。因?yàn)樵诰途w隊(duì)列中的進(jìn)程比在CPU上運(yùn)行的進(jìn)程的優(yōu)先數(shù)提高得快，故進(jìn)程切換時(shí)，先進(jìn)入就緒隊(duì)列的進(jìn)程優(yōu)先權(quán)就越高。(2) 是后進(jìn)先出算法。因?yàn)樵诰途w隊(duì)列中的進(jìn)程比在CPU上運(yùn)行的進(jìn)程的優(yōu)先權(quán)下降得快，故后進(jìn)入就緒隊(duì)列的進(jìn)程此先進(jìn)入的進(jìn)程的優(yōu)先權(quán)高。17 17 有一個(gè)四道作業(yè)的操作系統(tǒng)，若在一段時(shí)間內(nèi)先后到達(dá)6個(gè)作業(yè)，它們的提交和估計(jì)運(yùn)行時(shí)間由下表給出：作業(yè) 提交時(shí)間 估計(jì)運(yùn)行時(shí)間(分鐘) 1 8：00 60 2 8：20 35 3 8：25 20 4 8：30 25 5 8：35 5 6 8：40

36、 10 系統(tǒng)采用SJF調(diào)度算法，作業(yè)被調(diào)度進(jìn)入系統(tǒng)后中途不會(huì)退出，但作業(yè)運(yùn)行時(shí)可被更短作業(yè)搶占。(1)分別給出6個(gè)作業(yè)的執(zhí)行時(shí)間序列、即開始執(zhí)行時(shí)間、作業(yè)完成時(shí)間、作業(yè)周轉(zhuǎn)時(shí)間。(2)計(jì)算平均作業(yè)周轉(zhuǎn)時(shí)間。答：執(zhí)行次序 提交時(shí)間 執(zhí)行時(shí)間 開始時(shí)間 完成時(shí)間 周轉(zhuǎn)時(shí)間 J1 8:00 60 8:00 9:00 60 J5 8:35 5 9:00 9:05 30 J6 8:40 10 9:05 9:15 35 J3 8:25 20 9:15 9:35 70 J4 8:30 25 9:35 10:00 90 J2 8:20 35 10:00 10:35 135作業(yè)平均周轉(zhuǎn)時(shí)間T=(60+30+35

37、+70+90+135)/6=70注意，J1被調(diào)度運(yùn)行后，直到它執(zhí)行結(jié)束，才會(huì)引出作業(yè)調(diào)度程序工作。所以，J2至J6雖在J1執(zhí)行期間進(jìn)入，但未被調(diào)度，均在等待。當(dāng)J1撤離后，作業(yè)調(diào)度程序工作，按SJF算法，顯然有執(zhí)行次序：J5、J6、J3、J4、和J2。18 有一個(gè)具有兩道作業(yè)的批處理系統(tǒng)，作業(yè)調(diào)度采用短作業(yè)優(yōu)先的調(diào)度算法，進(jìn)程調(diào)度采用以優(yōu)先數(shù)為基礎(chǔ)的搶占式調(diào)度算法，在下表所示的作業(yè)序列，作業(yè)優(yōu)先數(shù)即為進(jìn)程優(yōu)先數(shù)，優(yōu)先數(shù)越小優(yōu)先級(jí)越高。作業(yè)名 到達(dá)時(shí)間 估計(jì)運(yùn)行時(shí)間 優(yōu)先數(shù)A 10：00 40分 5B 10：20 30分 3C 10：30 50分 4D 10：50 20分 6(1)列出所有作業(yè)進(jìn)入內(nèi)存時(shí)間及結(jié)束時(shí)間。(2)計(jì)算平均周轉(zhuǎn)時(shí)間。答：每個(gè)作業(yè)運(yùn)行將經(jīng)過兩個(gè)階段：作業(yè)調(diào)度(SJF算法)和進(jìn)程調(diào)度(優(yōu)先數(shù)搶占式)。另外，批處理最多容納2道作業(yè)，更多的作業(yè)將在后備隊(duì)列等待。進(jìn)程就緒隊(duì)列作業(yè)后備隊(duì)列時(shí)間(分鐘) 10:00 10:20 10:30 10:50 11:10 12:00 12:20A B A C DA D D C CPU(1) 10:00，作業(yè)A到達(dá)并投入運(yùn)行。(2) 10:20，作業(yè)B到達(dá)且優(yōu)先權(quán)高于作業(yè)A，故作業(yè)B投入運(yùn)行而作業(yè)A在就緒隊(duì)列等待。(3) 10:30，作業(yè)C到達(dá)，因內(nèi)存中已有兩道作業(yè)，故作