操作系統(tǒng)復(fù)習(xí)應(yīng)用題

1、1若程序若程序A和B單獨(dú)執(zhí)行時(shí)分別需要單獨(dú)執(zhí)行時(shí)分別需要1小時(shí)和小時(shí)和1.51.5小時(shí)，其中小時(shí)，其中CPUCPU工作時(shí)間分別為工作時(shí)間分別為1818分鐘和鐘和2727分鐘。若采用多道程序設(shè)計(jì)方法，讓分鐘。若采用多道程序設(shè)計(jì)方法，讓A和B并行工作，假定并行工作，假定CPUCPU利用率達(dá)到利用率達(dá)到5050％，另加％，另加1515分鐘系統(tǒng)開(kāi)銷，請(qǐng)問(wèn)系統(tǒng)效率能提高多少分鐘系統(tǒng)開(kāi)銷，請(qǐng)問(wèn)系統(tǒng)效率能提高多少解：在多道系統(tǒng)中，程序A和B共用的CP

2、U時(shí)間為：(18十27)／50％＝90分鐘系統(tǒng)效率提高＝(A和B單獨(dú)執(zhí)行的時(shí)間總和－多道方式下總時(shí)間)／A和B單獨(dú)執(zhí)行的時(shí)間總和，即((60十90)－(90十15))／(60十90)＝45／150＝30％1.1.假定在單假定在單CPUCPU條件下有下列要執(zhí)行的作業(yè)：條件下有下列要執(zhí)行的作業(yè)：作業(yè)運(yùn)行時(shí)間優(yōu)先級(jí)1102243330作業(yè)到來(lái)的時(shí)間是按作業(yè)編號(hào)順序進(jìn)行的作業(yè)到來(lái)的時(shí)間是按作業(yè)編號(hào)順序進(jìn)行的(即后面作業(yè)依次比前一個(gè)作業(yè)遲到一個(gè)時(shí)

3、間即后面作業(yè)依次比前一個(gè)作業(yè)遲到一個(gè)時(shí)間單位單位)。(1)(1)用一個(gè)執(zhí)行時(shí)間圖描述在采用非搶占式優(yōu)先級(jí)算法時(shí)執(zhí)行這些作業(yè)的情況。用一個(gè)執(zhí)行時(shí)間圖描述在采用非搶占式優(yōu)先級(jí)算法時(shí)執(zhí)行這些作業(yè)的情況。(2)(2)對(duì)于上述算法，各個(gè)作業(yè)的周轉(zhuǎn)時(shí)間是多少對(duì)于上述算法，各個(gè)作業(yè)的周轉(zhuǎn)時(shí)間是多少平均周轉(zhuǎn)時(shí)間是多少平均周轉(zhuǎn)時(shí)間是多少(3)(3)對(duì)于上述算法，各個(gè)作業(yè)的帶權(quán)周轉(zhuǎn)時(shí)間是多少對(duì)于上述算法，各個(gè)作業(yè)的帶權(quán)周轉(zhuǎn)時(shí)間是多少平均帶權(quán)周轉(zhuǎn)時(shí)間是多少平

4、均帶權(quán)周轉(zhuǎn)時(shí)間是多少解：(1)非搶占式優(yōu)先級(jí)算法作業(yè)的執(zhí)行情況如下：作業(yè)到達(dá)時(shí)間運(yùn)行時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間101010101.021417164.032313113.7平均周轉(zhuǎn)時(shí)間12.3平均帶權(quán)周轉(zhuǎn)時(shí)間2.92若在后備作業(yè)隊(duì)列中等待運(yùn)行的同時(shí)有三個(gè)作業(yè)若在后備作業(yè)隊(duì)列中等待運(yùn)行的同時(shí)有三個(gè)作業(yè)1、2、3，已知它們各自的運(yùn)行時(shí)間，已知它們各自的運(yùn)行時(shí)間為a、b、c，且滿足關(guān)系，且滿足關(guān)系a＜b＜c，試證明采用短作業(yè)優(yōu)先調(diào)度算法

5、能獲得最小平均周轉(zhuǎn)時(shí)，試證明采用短作業(yè)優(yōu)先調(diào)度算法能獲得最小平均周轉(zhuǎn)時(shí)間。間。證明：由于短作業(yè)優(yōu)先調(diào)度算法總是在后備作業(yè)隊(duì)列中選擇運(yùn)行時(shí)間最短的作業(yè)作為調(diào)度對(duì)象，因此對(duì)短作業(yè)優(yōu)先調(diào)度算法而言，這三個(gè)作業(yè)的總周轉(zhuǎn)時(shí)間為T1=a(ab)(abc)=3a2bc……(1)若不按短作業(yè)優(yōu)先調(diào)度算法來(lái)調(diào)度這三個(gè)作業(yè)，不失一般性，假定調(diào)度順序?yàn)?、l、3，則其周轉(zhuǎn)時(shí)間為T2=b(ba)(bac)=3b2ac……(2)由(1)、(2)兩式可得：T2T1

6、=ba0由此可見(jiàn)，短作業(yè)優(yōu)先調(diào)度算法能獲得最小平均周轉(zhuǎn)時(shí)間。3設(shè)有設(shè)有4道作業(yè)，它們的提交時(shí)間及執(zhí)行時(shí)間如下：道作業(yè)，它們的提交時(shí)間及執(zhí)行時(shí)間如下：試計(jì)算在單道程序環(huán)境下，采用先來(lái)先服務(wù)調(diào)度算法和最短作業(yè)優(yōu)先調(diào)度算法時(shí)的平均周試計(jì)算在單道程序環(huán)境下，采用先來(lái)先服務(wù)調(diào)度算法和最短作業(yè)優(yōu)先調(diào)度算法時(shí)的平均周(1)(1)列出所有作業(yè)進(jìn)入內(nèi)存時(shí)間及結(jié)束時(shí)間列出所有作業(yè)進(jìn)入內(nèi)存時(shí)間及結(jié)束時(shí)間(2)(2)計(jì)算平均周轉(zhuǎn)時(shí)間。計(jì)算平均周轉(zhuǎn)時(shí)間。分析:在

7、本題中，每個(gè)作業(yè)的運(yùn)行將經(jīng)歷兩級(jí)調(diào)度：作業(yè)調(diào)度和進(jìn)程調(diào)度。作業(yè)調(diào)度采用短作業(yè)優(yōu)先調(diào)度算法，進(jìn)程調(diào)度采用基于優(yōu)先數(shù)的搶占式調(diào)度算法，高優(yōu)先級(jí)的進(jìn)程可以搶占系統(tǒng)處理機(jī)。只有當(dāng)作業(yè)調(diào)度程序?qū)⒆鳂I(yè)裝入內(nèi)存后，方能參與進(jìn)程調(diào)度。本題中的批處理系統(tǒng)是兩道作業(yè)系統(tǒng)，因此每次只能有兩道作業(yè)進(jìn)入系統(tǒng)內(nèi)存。本題中的作業(yè)和進(jìn)程推進(jìn)順序如下：10：00時(shí)，A作業(yè)到達(dá)。因系統(tǒng)的后備作業(yè)隊(duì)列中沒(méi)有其他作業(yè)，進(jìn)程就緒隊(duì)列中也沒(méi)有進(jìn)程，故作業(yè)調(diào)度程序?qū)⒆鳂I(yè)A調(diào)入內(nèi)存并

8、將它排在就緒隊(duì)列上，進(jìn)程調(diào)度程序調(diào)度它運(yùn)行。10：20時(shí)，B作業(yè)到達(dá)。因系統(tǒng)的后備作業(yè)隊(duì)列中沒(méi)有其他作業(yè)，故作業(yè)調(diào)度程序?qū)⒆鳂I(yè)B調(diào)入內(nèi)存并將它排在就緒隊(duì)列上。而作業(yè)B的優(yōu)先級(jí)高于作業(yè)A的優(yōu)先級(jí)，進(jìn)程調(diào)度程序停止作業(yè)A的運(yùn)行，將作業(yè)A放入就緒隊(duì)列，調(diào)度作業(yè)B運(yùn)行。此時(shí)，系統(tǒng)中已有兩道作業(yè)在內(nèi)存中運(yùn)行，作業(yè)A已運(yùn)行20分鐘，還需運(yùn)行20分鐘才能完成。10：30時(shí)，C作業(yè)到達(dá)。因系統(tǒng)中已有兩道作業(yè)在內(nèi)存中運(yùn)行，故作業(yè)C只能在后備作業(yè)隊(duì)列中等待

9、作業(yè)調(diào)度。此時(shí)，作業(yè)B已運(yùn)行了10分針并將繼續(xù)運(yùn)行，還需運(yùn)行20分鐘才能完成，作業(yè)A已等待10分針并將繼續(xù)等待、還需運(yùn)行20分鐘才能完成。10：50時(shí)，B作業(yè)運(yùn)行30分鐘結(jié)束運(yùn)行，D作業(yè)到達(dá)。因系統(tǒng)中只有作業(yè)A在內(nèi)存中運(yùn)行，作業(yè)后備隊(duì)列中有C、D兩道作業(yè)，按短作業(yè)優(yōu)先的作業(yè)調(diào)度策略，作業(yè)D被作業(yè)調(diào)度程序選中，裝入內(nèi)存運(yùn)行，作業(yè)C仍在后備作業(yè)隊(duì)列中等待作業(yè)調(diào)度。在內(nèi)存中，作業(yè)A的優(yōu)先級(jí)高于作業(yè)D，進(jìn)程調(diào)度程序調(diào)度作業(yè)A運(yùn)行，作業(yè)D在就緒隊(duì)

10、列中等待進(jìn)程調(diào)度。此時(shí)，作業(yè)A已運(yùn)行了20分鐘，在就緒隊(duì)列中等待了30分鐘，還需運(yùn)行20分鐘才能完成；作業(yè)C已在后備隊(duì)列中等待了20分鐘并將繼續(xù)等待11：10時(shí)，A作業(yè)運(yùn)行40分針結(jié)束運(yùn)行。因系統(tǒng)中只有作業(yè)D在內(nèi)存中運(yùn)行，作業(yè)后備隊(duì)列中只有作業(yè)C在等待，作業(yè)調(diào)度程序?qū)⒆鳂I(yè)C裝入內(nèi)存運(yùn)行。因作業(yè)C的優(yōu)先級(jí)高于作業(yè)D，進(jìn)程調(diào)度程序調(diào)度作業(yè)C運(yùn)行，作業(yè)D仍在就緒隊(duì)列中等待進(jìn)程調(diào)度。此時(shí)作業(yè)D已在就緒隊(duì)列中等待了20分鐘并將繼續(xù)等待。12：00