【文章內(nèi)容簡介】 12 20 E 10 20 30 3作業(yè)平均周轉(zhuǎn)時間 T=(2+6+12+20+30)/5=14作業(yè)平均帶權(quán)周轉(zhuǎn)時間 W=(1++2++3)/5=211 有5個批處理作業(yè)A到E均已到達計算中心，其運行時間分別4和8分鐘；各自的優(yōu)先級分別被規(guī)定為1和4，這里5為最高級。若不考慮系統(tǒng)切換開銷，計算出平均作業(yè)周轉(zhuǎn)時間。（1）FCFS(按A、B、C、D、E)；(2)優(yōu)先級調(diào)度算法，(3)時間片輪轉(zhuǎn)法(每個作業(yè)獲得相同的2分鐘長的時間片)。答：(1)FCFS調(diào)度算法執(zhí)行次序 執(zhí)行時間 等待時間 周轉(zhuǎn)時間 帶權(quán)周轉(zhuǎn)時間 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)時間 T=(10+16+18+22+30)/5=作業(yè)平均帶權(quán)周轉(zhuǎn)時間 W=(1++9++)/5=(2)優(yōu)先級調(diào)度算法執(zhí)行次序 執(zhí)行時間 等待時間 周轉(zhuǎn)時間 帶權(quán)周轉(zhuǎn)時間 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)時間 T=(6+14+24+26+30)/5=20作業(yè)平均帶權(quán)周轉(zhuǎn)時間 W=(1+++13+)/5=(3)時間片輪轉(zhuǎn)法按次序A B C D E A B D E A B E A E A輪轉(zhuǎn)執(zhí)行。 作業(yè) 執(zhí)行時間 等待時間 周轉(zhuǎn)時間 帶權(quán)周轉(zhuǎn)時間 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)時間 T=(30+22+6+16+28)/5=作業(yè)平均帶權(quán)周轉(zhuǎn)時間 W=(3++3+4+)/5=12 (1)假定一個處理器正在執(zhí)行兩道作業(yè)，一道以計算為主，另一道以輸入輸出為主，你將怎樣賦予它們占有處理器的優(yōu)先級?為什么?(2)假定一個處理器正在執(zhí)行三道作業(yè)，一道以計算為主，第二道以輸入輸出為主，第三道為計算與輸入輸出均勻。應該如何賦予它們占有處理器的優(yōu)先級使得系統(tǒng)效率較高？答：處理器調(diào)度算法會考慮以下因素：作業(yè)響應時間要求；讓CPU盡量和外圍設備并行工作；限制一個計算進程長時間霸占處理器。因而，(1)I/O為主作業(yè)優(yōu)先級高。(2) 輸入輸出為主作業(yè)優(yōu)先級最高，輸入輸出均勻的作業(yè)其次，而計算為主作業(yè)的優(yōu)先級最低。13 請你設計一種先進的計算機體系結(jié)構(gòu)，它使用硬件而不是中斷來完成進程切換，則CPU需要哪些信息? 請描述用硬件完成進程切換的工作過程。答：該計算機有一個專用硬件寄存器，它始終存放指向當前運行進程的PCB的指針。當系統(tǒng)中發(fā)生了一個事件，如I/O結(jié)束事件，CPU便可把運行進程的上下文保存到專用硬件寄存器指針指向的PCB中保護起來，然后，CPU轉(zhuǎn)向中斷向量表，找到設備中斷處理程序入口，讓專用硬件寄存器指針指向(設備)中斷服務例程，于是，便可啟動中斷服務例程工作。14 單道批處理系統(tǒng)中，下列三個作業(yè)采用先來先服務調(diào)度算法和最高響應比優(yōu)先算法進行調(diào)度，哪一種算法性能較好？請完成下表：作業(yè)提交時間運行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間12310∶0010∶1010∶252∶001∶000∶25平均作業(yè)周轉(zhuǎn)時間＝平均作業(yè)帶權(quán)周轉(zhuǎn)時間W=答：FIFO作業(yè)提交時間運行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間12310∶0010∶1010∶252∶001∶000∶2510:0012:0013:0012:0013:0013:2522:503120/120145/60180/25平均作業(yè)周轉(zhuǎn)時間＝平均作業(yè)帶權(quán)周轉(zhuǎn)時間W=HRRF作業(yè)提交時間運行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間12310∶0010∶1010∶252∶001∶000∶2510:0012:2512:0012:0013:2512:2523:152120/120195/60120/25平均作業(yè)周轉(zhuǎn)時間＝平均作業(yè)帶權(quán)周轉(zhuǎn)時間W=可見HRRF比FIFO要好。15 若有如表所示四個作業(yè)進入系統(tǒng)，分別計算在FCFS、SJF和HRRF算法下的平均周轉(zhuǎn)時間與帶權(quán)平均周轉(zhuǎn)時間。(時間以十進制表示)作業(yè) 提交時間(時) 估計運行時間(小時) 開始執(zhí)行時間(時) 1 2 3 4 答： FCFS SJF HRRF作業(yè) 開始 完成 周轉(zhuǎn) 開始 完成 周轉(zhuǎn) 開始 完成 周轉(zhuǎn)時間 時間 時間 時間 時間 時間 時間 時間 時間1 2 3 4 平均周 T= T= T=轉(zhuǎn)時間=帶權(quán)平均 W= W= W=周轉(zhuǎn)時間=16 Kleinrock提出一種動態(tài)優(yōu)先權(quán)算法：進程在就緒隊列等待時，其優(yōu)先權(quán)以速率α變化； 當進程在處理器上運行，時其優(yōu)先權(quán)以速率β變化。給參數(shù)α、β賦以不同值可得到不同算法。(1)若αβ0是什么算法？(2) 若αβ0是什么算法答：(1) 是先進先出算法。因為在就緒隊列中的進程比在CPU上運行的進程的優(yōu)先數(shù)提高得快，故進程切換時，先進入就緒隊列的進程優(yōu)先權(quán)就越高。(2) 是后進先出算法。因為在就緒隊列中的進程比在CPU上運行的進程的優(yōu)先權(quán)下降得快，故后進入就緒隊列的進程此先進入的進程的優(yōu)先權(quán)高。17 17 有一個四道作業(yè)的操作系統(tǒng)，若在一段時間內(nèi)先后到達6個作業(yè)，它們的提交和估計運行時間由下表給出：作業(yè) 提交時間 估計運行時間(分鐘) 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)度進入系統(tǒng)后中途不會退出，但作業(yè)運行時可被更短作業(yè)搶占。(1)分別給出6個作業(yè)的執(zhí)行時間序列、即開始執(zhí)行時間、作業(yè)完成時間、作業(yè)周轉(zhuǎn)時間。(2)計算平均作業(yè)周轉(zhuǎn)時間。答：執(zhí)行次序 提交時間 執(zhí)行時間 開始時間 完成時間 周轉(zhuǎn)時間 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)時間T=(60+30+35+70+90+135)/6=70注意，J1被調(diào)度運行后，直到它執(zhí)行結(jié)束，才會引出作業(yè)調(diào)度程序工作。所以，J2至J6雖在J1執(zhí)行期間進入，但未被調(diào)度，均在等待。當J1撤離后，作業(yè)調(diào)度程序工作，按SJF算法，顯然有執(zhí)行次序：JJJJ和J2。18 有一個具有兩道作業(yè)的批處理系統(tǒng)，作業(yè)調(diào)度采用短作業(yè)優(yōu)先的調(diào)度算法，進程調(diào)度采用以優(yōu)先數(shù)為基礎的搶占式調(diào)度算法，在下表所示的作業(yè)序列，作業(yè)優(yōu)先數(shù)即為進程優(yōu)先數(shù)，優(yōu)先數(shù)越小優(yōu)先級越高。作業(yè)名 到達時間 估計運行時間 優(yōu)先數(shù)A 10：00 40分 5B 10：20 30分 3C 10：30 50分 4D 10：50 20分 6(1)列出所有作業(yè)進入內(nèi)存時間及結(jié)束時間。(2)計算平均周轉(zhuǎn)時間。答：每個作業(yè)運行將經(jīng)過兩個階段：作業(yè)調(diào)度(SJF算法)和進程調(diào)度(優(yōu)先數(shù)搶占式)。另外，批處理最多容納2道作業(yè)，更多的作業(yè)將在后備隊列等待。進程就緒隊列作業(yè)后備隊列時間(分鐘) 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到達并投入運行。(2) 10:20，作業(yè)B到達且優(yōu)先權(quán)高于作業(yè)A，故作業(yè)B投入運行而作業(yè)A在就緒隊列等待。(3) 10:30，作業(yè)C到達，因內(nèi)存中已有兩道作業(yè)，故作業(yè)C進入作業(yè)后備隊列等待。(4) 10:50，作業(yè)B運行結(jié)束，作業(yè)D到達，按SJF短作業(yè)優(yōu)先算法，作業(yè)D被裝入內(nèi)存進入就緒隊列。而由于作業(yè)A的優(yōu)先級高于作業(yè)D，故作業(yè)A投入運行。(5) 11:10，作業(yè)A運行結(jié)束，作業(yè)C被調(diào)入內(nèi)存，且作業(yè)C的優(yōu)先級高于作業(yè)D，故作業(yè)C投入運行。(6) 12:00，作業(yè)C運行結(jié)束，作業(yè)D投入運行。(7) 12:20，作業(yè)D運行結(jié)束。作業(yè) 進入內(nèi)存時間 運行結(jié)束時間 A 10:00 11:10 B 10:20 10。50 C 11:10 12:00 D 10:50 12:20各作業(yè)周轉(zhuǎn)時間為：作業(yè)A 70，作業(yè)B 30，作業(yè)C 90，作業(yè)D 90。平均作業(yè)周轉(zhuǎn)時間為70分鐘。19 某多道程序設計系統(tǒng)供用戶使用的主存為100K，磁帶