【文章內(nèi)容簡(jiǎn)介】 12 20 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++2++3)/5=211 有5個(gè)批處理作業(yè)A到E均已到達(dá)計(jì)算中心，其運(yùn)行時(shí)間分別4和8分鐘；各自的優(yōu)先級(jí)分別被規(guī)定為1和4，這里5為最高級(jí)。若不考慮系統(tǒng)切換開(kāi)銷(xiāo)，計(jì)算出平均作業(yè)周轉(zhuǎn)時(shí)間。（1）FCFS(按A、B、C、D、E)；(2)優(yōu)先級(jí)調(diào)度算法，(3)時(shí)間片輪轉(zhuǎn)法(每個(gè)作業(yè)獲得相同的2分鐘長(zhǎng)的時(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 C 2 16 18 9 D 4 18 22 E 8 22 30 作業(yè)平均周轉(zhuǎn)時(shí)間 T=(10+16+18+22+30)/5=作業(yè)平均帶權(quán)周轉(zhuǎn)時(shí)間 W=(1++9++)/5=(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 A 10 14 24 C 2 24 26 13 D 4 26 30 作業(yè)平均周轉(zhuǎn)時(shí)間 T=(6+14+24+26+30)/5=20作業(yè)平均帶權(quán)周轉(zhuǎn)時(shí)間 W=(1+++13+)/5=(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 C 2 4 6 3 D 4 12 16 4 E 8 20 28 作業(yè)平均周轉(zhuǎn)時(shí)間 T=(30+22+6+16+28)/5=作業(yè)平均帶權(quán)周轉(zhuǎn)時(shí)間 W=(3++3+4+)/5=12 (1)假定一個(gè)處理器正在執(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)程長(zhǎng)時(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)，它使用硬件而不是中斷來(lái)完成進(jìn)程切換，則CPU需要哪些信息? 請(qǐng)描述用硬件完成進(jìn)程切換的工作過(guò)程。答：該計(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ù)起來(lái)，然后，CPU轉(zhuǎn)向中斷向量表，找到設(shè)備中斷處理程序入口，讓專用硬件寄存器指針指向(設(shè)備)中斷服務(wù)例程，于是，便可啟動(dòng)中斷服務(wù)例程工作。14 單道批處理系統(tǒng)中，下列三個(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í)間帶權(quán)周轉(zhuǎn)時(shí)間12310∶0010∶1010∶252∶001∶000∶25平均作業(yè)周轉(zhuǎn)時(shí)間＝平均作業(yè)帶權(quán)周轉(zhuǎn)時(shí)間W=答：FIFO作業(yè)提交時(shí)間運(yùn)行時(shí)間開(kāi)始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間12310∶0010∶1010∶252∶001∶000∶2510:0012:0013:0012:0013:0013:2522:503120/120145/60180/25平均作業(yè)周轉(zhuǎn)時(shí)間＝平均作業(yè)帶權(quán)周轉(zhuǎn)時(shí)間W=HRRF作業(yè)提交時(shí)間運(yùn)行時(shí)間開(kāi)始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間12310∶0010∶1010∶252∶001∶000∶2510:0012:2512:0012:0013:2512:2523:152120/120195/60120/25平均作業(yè)周轉(zhuǎn)時(shí)間＝平均作業(yè)帶權(quán)周轉(zhuǎn)時(shí)間W=可見(jiàn)HRRF比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í)) 開(kāi)始執(zhí)行時(shí)間(時(shí)) 1 2 3 4 答： FCFS SJF HRRF作業(yè) 開(kāi)始 完成 周轉(zhuǎn) 開(kāi)始 完成 周轉(zhuǎn) 開(kāi)始 完成 周轉(zhuǎn)時(shí)間 時(shí)間 時(shí)間 時(shí)間 時(shí)間 時(shí)間 時(shí)間 時(shí)間 時(shí)間1 2 3 4 平均周 T= T= T=轉(zhuǎn)時(shí)間=帶權(quán)平均 W= W= W=周轉(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ù)α、β賦以不同值可得到不同算法。(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 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í)間序列、即開(kāi)始執(zhí)行時(shí)間、作業(yè)完成時(shí)間、作業(yè)周轉(zhuǎn)時(shí)間。(2)計(jì)算平均作業(yè)周轉(zhuǎn)時(shí)間。答：執(zhí)行次序 提交時(shí)間 執(zhí)行時(shí)間 開(kāi)始時(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+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í)行次序：JJJJ和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)過(guò)兩個(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è)，故作業(yè)C進(jìn)入作業(yè)后備隊(duì)列等待。(4) 10:50，作業(yè)B運(yùn)行結(jié)束，作業(yè)D到達(dá)，按SJF短作業(yè)優(yōu)先算法，作業(yè)D被裝入內(nèi)存進(jìn)入就緒隊(duì)列。而由于作業(yè)A的優(yōu)先級(jí)高于作業(yè)D，故作業(yè)A投入運(yùn)行。(5) 11:10，作業(yè)A運(yùn)行結(jié)束，作業(yè)C被調(diào)入內(nèi)存，且作業(yè)C的優(yōu)先級(jí)高于作業(yè)D，故作業(yè)C投入運(yùn)行。(6) 12:00，作業(yè)C運(yùn)行結(jié)束，作業(yè)D投入運(yùn)行。(7) 12:20，作業(yè)D運(yùn)行結(jié)束。作業(yè) 進(jìn)入內(nèi)存時(shí)間 運(yùn)行結(jié)束時(shí)間 A 10:00 11:10 B 10:20 10。50 C 11:10 12:00 D 10:50 12:20各作業(yè)周轉(zhuǎn)時(shí)間為：作業(yè)A 70，作業(yè)B 30，作業(yè)C 90，作業(yè)D 90。平均作業(yè)周轉(zhuǎn)時(shí)間為70分鐘。19 某多道程序設(shè)計(jì)系統(tǒng)供用戶使用的主存為100K，磁帶