【正文】 A C DA D D C CPU(1) 10:00，作業(yè)A到達(dá)并投入運(yùn)行。答：每個作業(yè)運(yùn)行將經(jīng)過兩個階段：作業(yè)調(diào)度(SJF算法)和進(jìn)程調(diào)度(優(yōu)先數(shù)搶占式)。作業(yè)名 到達(dá)時間 估計(jì)運(yùn)行時間 優(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)存時間及結(jié)束時間。當(dāng)J1撤離后，作業(yè)調(diào)度程序工作，按SJF算法，顯然有執(zhí)行次序：JJJJ和J2。答：執(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)度運(yùn)行后，直到它執(zhí)行結(jié)束，才會引出作業(yè)調(diào)度程序工作。(1)分別給出6個作業(yè)的執(zhí)行時間序列、即開始執(zhí)行時間、作業(yè)完成時間、作業(yè)周轉(zhuǎ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)高。因?yàn)樵诰途w隊(duì)列中的進(jìn)程比在CPU上運(yùn)行的進(jìn)程的優(yōu)先數(shù)提高得快，故進(jìn)程切換時，先進(jìn)入就緒隊(duì)列的進(jìn)程優(yōu)先權(quán)就越高。給參數(shù)α、β賦以不同值可得到不同算法。15 若有如表所示四個作業(yè)進(jìn)入系統(tǒng)，分別計(jì)算在FCFS、SJF和HRRF算法下的平均周轉(zhuǎn)時間與帶權(quán)平均周轉(zhuǎn)時間。當(dāng)系統(tǒng)中發(fā)生了一個事件，如I/O結(jié)束事件，CPU便可把運(yùn)行進(jìn)程的上下文保存到專用硬件寄存器指針指向的PCB中保護(hù)起來，然后，CPU轉(zhuǎn)向中斷向量表，找到設(shè)備中斷處理程序入口，讓專用硬件寄存器指針指向(設(shè)備)中斷服務(wù)例程，于是，便可啟動中斷服務(wù)例程工作。13 請你設(shè)計(jì)一種先進(jìn)的計(jì)算機(jī)體系結(jié)構(gòu)，它使用硬件而不是中斷來完成進(jìn)程切換，則CPU需要哪些信息? 請描述用硬件完成進(jìn)程切換的工作過程。因而，(1)I/O為主作業(yè)優(yōu)先級高。 作業(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è)，一道以計(jì)算為主，另一道以輸入輸出為主，你將怎樣賦予它們占有處理器的優(yōu)先級?為什么?(2)假定一個處理器正在執(zhí)行三道作業(yè)，一道以計(jì)算為主，第二道以輸入輸出為主，第三道為計(jì)算與輸入輸出均勻。（1）FCFS(按A、B、C、D、E)；(2)優(yōu)先級調(diào)度算法，(3)時間片輪轉(zhuǎn)法(每個作業(yè)獲得相同的2分鐘長的時間片)。 作業(yè) 執(zhí)行時間 等待時間 周轉(zhuǎn)時間 帶權(quán)周轉(zhuǎn)時間 A 2 0 2 1 B 4 8 12 3 C 6 14 20 D 8 18 26 E 10 20 30 3作業(yè)平均周轉(zhuǎn)時間 T=(2+12+20+26+30)/5=18作業(yè)平均帶權(quán)周轉(zhuǎn)時間 W=(1+3+++3)/5=(4)SJF調(diào)度算法 作業(yè) 執(zhí)行時間 等待時間 周轉(zhuǎn)時間 帶權(quán)周轉(zhuǎn)時間 A 2 0 2 1 B 4 2 6 C 6 6 12 2 D 8 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均已到達(dá)計(jì)算中心，其運(yùn)行時間分別4和8分鐘；各自的優(yōu)先級分別被規(guī)定為1和4，這里5為最高級。（對1）每個作業(yè)獲得相同的2分鐘長的時間片；對2）到4）采用單道運(yùn)行，直到結(jié)束。X取值不定，按照以下情況討論：1） x≤3 次序?yàn)椋簒，3，5，6，92） 3x≤5 次序?yàn)椋?，x，5，6，93） 5x≤6 次序?yàn)椋?，5，x，6，94） 6x≤9 次序?yàn)椋?，5，6，x，95） 9x 次序?yàn)椋?，5，6，9，x10 有5個批處理作業(yè)A到E均已到達(dá)計(jì)算中心，其運(yùn)行時間分別8和10分鐘；各自的優(yōu)先級分別被規(guī)定為4和5，這里5為最高級。若采用時間片長度為Q的時向片輪轉(zhuǎn)法，對下列各種情況算出CPU利用率。作業(yè) 執(zhí)行時間 提交時間 完成時間 周轉(zhuǎn)時間 帶權(quán)周轉(zhuǎn)時間 1 10 0 19 19 2 1 0 2 2 2 3 2 0 7 7 4 1 0 4 4 4 5 5 0 14 14 作業(yè)平均周轉(zhuǎn)時間 T=(19+2+7+4+14)/5=作業(yè)平均帶權(quán)周轉(zhuǎn)時間 W=(+2++4+)/5=采用SJF算法調(diào)度作業(yè)，運(yùn)作情況：執(zhí)行次序 執(zhí)行時間 等待時間 開始時間 完成時間 周轉(zhuǎn)時間 帶權(quán)周轉(zhuǎn)時間 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 10 9 9 19 19 作業(yè)平均周轉(zhuǎn)時間 T=(1+2+4+9+19)/5=7作業(yè)平均帶權(quán)周轉(zhuǎn)時間 W=(1+2+2++)/5=(2) 采用非剝奪優(yōu)先權(quán)算法調(diào)度作業(yè)，運(yùn)作情況：執(zhí)行次序 優(yōu)先數(shù) 執(zhí)行時間 等待時間 周轉(zhuǎn)時間 帶權(quán)周轉(zhuǎn)時間 2 1 1 0 1 1 5 2 5 1 6 1 3 10 6 16 3 3 2 16 18 9 4 4 1 18 19 19 作業(yè)平均周轉(zhuǎn)時間 T=(1+6+16+18+19)/5=12作業(yè)平均帶權(quán)周轉(zhuǎn)時間 W=(1+++9+19)/5=8 對某系統(tǒng)進(jìn)行監(jiān)測后表明平均每個進(jìn)程在I/O阻塞之前的運(yùn)行時間為T。1） 分別用先來先服務(wù)調(diào)度算法、時間片輪轉(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)時間和平均帶權(quán)周轉(zhuǎn)時間。所以，按短作業(yè)優(yōu)先調(diào)度算法調(diào)度時，使得平均作業(yè)周轉(zhuǎn)時間最短。答：首先，對n個作業(yè)按執(zhí)行時間從小到大重新進(jìn)行排序，則對n個作業(yè)：J1’，…，Jn’，它們的運(yùn)行時間滿足：S1’≤ S2’≤… ≤S(n1)’≤Sn’。如果這些作業(yè)同時到達(dá)系統(tǒng)，并在一臺單CPU處理器上按單道方式執(zhí)行。則三個作業(yè)的總周轉(zhuǎn)時間為：T2=b+(b+a)+(b+a+c)=3b+2a+c ②令②①式得到： T2T1=ba0可見，采用短作業(yè)優(yōu)先算法調(diào)度才能獲得最小平均作業(yè)周轉(zhuǎn)時間。5 若后備作業(yè)隊(duì)列中等待運(yùn)行的同時有三個作業(yè)JJJ3，已知它們各自的運(yùn)行時間為a、b、c，且滿足abc，試證明采用短作業(yè)優(yōu)先算法調(diào)度能獲得最小平均作業(yè)周轉(zhuǎn)時間。4 在按動態(tài)優(yōu)先數(shù)調(diào)度進(jìn)程的系統(tǒng)中，每個進(jìn)程的優(yōu)先數(shù)需定時重新計(jì)算。其中(1)、(3)為互斥問題。3 并發(fā)進(jìn)程之間有什么樣的相互制約關(guān)系?下列日常生活中的活動是屬哪種制約關(guān)系：(1)踢足球，(2)吃自助餐，(3)圖書館借書，(4)電視機(jī)生產(chǎn)流水線工序。答：因?yàn)镮/O繁忙型作業(yè)忙于I/O，所以它CPU用得少，按調(diào)度策略能優(yōu)先執(zhí)行。答：(3)，(4)，(5)，(6)，(7)。所以，CPU用于時鐘中斷處理的時間比率為：2(50/3)=6/50=12%。若時鐘中斷頻率為60HZ，試問CPU用于時鐘中斷處理的時間比率為多少?答：因時鐘中斷頻率為60HZ，所以，時鐘周期為：1/60s=50/3ms。故CPU利用率為40/80=50%。程序B執(zhí)行了40秒，其中CPU用了15秒。B程序按順序使用：(設(shè)備甲)10秒、(CPU)10秒、(設(shè)備乙)5秒、(CPU)5秒、(設(shè)備乙)10秒。程序C為310ms。(2) 程序A為250ms。CPU利用率為(14030)/140=%7 若內(nèi)存中有3道程序A、B、C，優(yōu)先級從高到低為A、B和C，它們單獨(dú)運(yùn)行時的CPU和I/O占用時間為：程序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如果三道程序同時并發(fā)執(zhí)行，調(diào)度開銷忽略不計(jì)，但優(yōu)先級高的程序可中斷優(yōu)先級低的程序，優(yōu)先級與I/O設(shè)備無關(guān)。兩種情況下，CPU的平均利用率各為多少?答：分別畫出單道和多道運(yùn)行的時間圖0 2