作業(yè)管理真題

1、第四章 作業(yè)管理真題例題4.1（華中科技大學(xué)1996年試題）填空：衡量作業(yè)調(diào)度算法性能的標(biāo)準(zhǔn)是（ ），（ ）。分析：評價作業(yè)調(diào)度算法好壞的標(biāo)準(zhǔn)有CPU利用率，吞吐量、周轉(zhuǎn)時間、平均周轉(zhuǎn)時間、帶權(quán)平均周轉(zhuǎn)時間等。通常（尤其在批處理系統(tǒng)中）更常用的是平均周轉(zhuǎn)時間和帶權(quán)平均周轉(zhuǎn)時間。 解答：平均周轉(zhuǎn)時間，帶權(quán)平均周轉(zhuǎn)時間例題4.2（華中科技大學(xué)1996年試題）選擇：在下列調(diào)度算法中，（ ）是合理的作業(yè)調(diào)度算法：（ ）是合理的進程調(diào)度算法。A先來先服務(wù) B循環(huán)輪轉(zhuǎn)調(diào)度 C短作業(yè)優(yōu)先 D最長作業(yè)優(yōu)先E優(yōu)先數(shù)調(diào)度 F后到先服務(wù)分析：常見的作業(yè)調(diào)度策略有：先來先服務(wù)，短作業(yè)優(yōu)先，響應(yīng)比高者優(yōu)先，優(yōu)先數(shù)調(diào)度等

2、；常見的進程調(diào)度策略有：進程優(yōu)先數(shù)調(diào)度算法（包括可搶占處理機和不可搶占處理機兩種情況），循環(huán)輪轉(zhuǎn)調(diào)度（包括簡單循環(huán)輪轉(zhuǎn)調(diào)度和可變時間片輪轉(zhuǎn)調(diào)度）以及多重間片循環(huán)調(diào)度等。 解答：（ACE）（BE）例題 4.3（華中科技大學(xué)1998年試題）填空：在作業(yè)調(diào)度算法中，（ ）調(diào)度算法的調(diào)度性能要好些。分析：本題是要對常見的幾種作業(yè)調(diào)度算法性能做出比較。響應(yīng)比高者優(yōu)先調(diào)度算法就是在每調(diào)度一個作業(yè)投入運行時，計算后備作業(yè)表中每個作業(yè)的響應(yīng)比，挑選響應(yīng)比高者投入運行。響應(yīng)比定義為作業(yè)響應(yīng)時間與作業(yè)運行時間的估計值的比值。響應(yīng)比高者優(yōu)先調(diào)度能解決“饑餓”現(xiàn)象，是FCFS調(diào)度算法和SJF調(diào)度算法的一個較好的折衷，

3、它既考慮了作業(yè)的到達次序，又考慮了作業(yè)的長短。 解答：相應(yīng)比高考優(yōu)先（HRF）。例題4.4（北京大學(xué)1991年試題）簡答題：什么是高級調(diào)度、中級調(diào)度和低級調(diào)度？分析：“三級調(diào)度”之間有區(qū)別，但更有聯(lián)系。舉例說明，用戶以作業(yè)的形式向操作系統(tǒng)提交任務(wù)，系統(tǒng)完成這一調(diào)度即為“高級調(diào)度”；作業(yè)進入系統(tǒng)，要建立相應(yīng)的進程，參與CPU的競爭，才能被執(zhí)行，這里又用到“進程調(diào)度”（關(guān)于“進程調(diào)度”，不光有用戶進程，還有系統(tǒng)進程）；同時，為了提高系統(tǒng)吞吐量，又出現(xiàn)了“中級調(diào)度”的概念 。因此，真正理解這三級調(diào)度，對于掌握作業(yè)管理、調(diào)度，是非常重要的。例題4.5（南京大學(xué)1999年試題）某多道程序設(shè)計系統(tǒng)配有一臺

4、處理器和兩臺外設(shè)IO1、IO2，現(xiàn)有3個優(yōu)先級由高到低的作業(yè)J1、J2和J3都已裝入了主存，它們使用資源的先后順序和占用時間分別是：J1：IO2（30 ms），CPU（10ms），IO1（30ms），CPU（10ms）.J2：IO1（20 ms），CPU（20ms），IO2（40ms）J3：CPU（30ms），IO1（20ms）處理器調(diào)度采用可搶占的優(yōu)先數(shù)算法，忽略其他輔助操作時間，回答下列問題：（1）分別計算作業(yè)J1、J2和J3從開始到完成所用的時間。（2）3個作業(yè)全部完成時CPU的利用率。（3）3個作業(yè)全部完成時外設(shè)IO1的利用率。分析 如前說述，本題在多道系統(tǒng)中的三個進程不僅要競爭使用處

5、理機，而且還要競爭使用外設(shè)，這使得進程之間的關(guān)系更加復(fù)雜。另一方面，本題為了突出進程對CPU和外設(shè)的使用，弱化了作業(yè)調(diào)度的處理，因此題目中已假設(shè)這三個進程都已經(jīng)裝入主存，從這一點看，又降低了本題的難度。分析過程如圖4.2所示（圖中水平箭頭表示實際執(zhí)行過程，水平虛線表示等待過程）。解答：（1）由圖4.2可知：J1從開始到完成的時間是080msJ2從開始到完成的時間是090msJ3從開始到完成的時間是090ms（2）三個作業(yè)全部完成時CPU的利用率是： （3）三個作業(yè)全部完成時外設(shè)IO1的利用率是：例題4.6（中國科學(xué)院計算技術(shù)研究所1996年試題）有5個批處理的作業(yè)（A、B、C、D和E）幾乎同時

6、到達一個計算中心，估計的運行時間分別為2、4、6、8、10分鐘，它們的優(yōu)先數(shù)分別為1、2、3、4、5（1為最低優(yōu)先級）。對下面的每種調(diào)度算法，分別計算作業(yè)的平均周轉(zhuǎn)時間。（1）最高優(yōu)先級優(yōu)先 （2）時間片輪轉(zhuǎn)（時間片為2分鐘）（3）FIFO（作業(yè)到達順序為C，D，B，E，A）（4）短作業(yè)優(yōu)先分析 本題是一個關(guān)于作業(yè)調(diào)度算法的評價的題目。題目給出一個實際的作業(yè)序列，由考生模擬作業(yè)的調(diào)度與執(zhí)行過程，并給出對于這個作業(yè)序列作業(yè)調(diào)度算法的平均周轉(zhuǎn)時間，從而對比不同調(diào)度算法的性能。本題可按照單道系統(tǒng)情況來處理。在題目中指出5個作業(yè)幾乎同時到達一個計算中心，其含義是任何調(diào)度算法（除了FIFO算法外）都可以

7、認(rèn)為這5個作業(yè)是同時到達的，在調(diào)度過程中不需考慮其到達的順序。本題的作業(yè)的推進過程為：0（分鐘）作業(yè)A，B，C，D，E到達作業(yè)E優(yōu)先級最高，被調(diào)入系統(tǒng)運行作業(yè)A，B，C，D等待系統(tǒng)調(diào)度10（分鐘）作業(yè)E運行完成作業(yè)D優(yōu)先級最高，被調(diào)入系統(tǒng)運行作業(yè)A，B，C等待系統(tǒng)調(diào)度18（分鐘）作業(yè)D運行完成作業(yè)C優(yōu)先級最高，被調(diào)入系統(tǒng)運行作業(yè)A，B等待系統(tǒng)調(diào)度24（分鐘）作業(yè)C運行完成作業(yè)B優(yōu)先級最高，被調(diào)入系統(tǒng)運行作業(yè)A等待系統(tǒng)調(diào)度28（分鐘）作業(yè)B運行完成作業(yè)A優(yōu)先級最高，被調(diào)入系統(tǒng)運行30（分鐘）作業(yè)A運行完成（2）時間片輪轉(zhuǎn)（時間片為2分鐘）作業(yè)ABCDE同時被調(diào)入系統(tǒng)運行，每隔10分鐘被調(diào)度執(zhí)行2

8、分鐘。因此作業(yè)開始結(jié)束時間為：0（分鐘）作業(yè)A，B，C，D，E到達，作業(yè)A開始運行，作業(yè)B，C，D，E等待2（分鐘）作業(yè)A運行結(jié)束，作業(yè)B，D，E等待4（分鐘）作業(yè)C開始運行，作業(yè)B，D，E等待6（分鐘）作業(yè)D開始運行，作業(yè)B，C，E等待8（分鐘）作業(yè)E開始運行，作業(yè)B，C，D等待10（分鐘）作業(yè)B開始運行，作業(yè)C，D，E等待12（分鐘）作業(yè)B運行結(jié)束，作業(yè)C開始運行，作業(yè)D，E等待14（分鐘）作業(yè)D開始運行，作業(yè)C，E等待16（分鐘）作業(yè)E開始運行，作業(yè)C，D等待18（分鐘）作業(yè)C開始運行，作業(yè)D，E等待20（分鐘）作業(yè)C運行結(jié)束，作業(yè)D開始運行，作業(yè)E等待22（分鐘）作業(yè)E開始運行，作業(yè)D

9、等待24（分鐘）作業(yè)D開始運行，作業(yè)E等待26（分鐘）作業(yè)D運行結(jié)束，作業(yè)E開始運行30（分鐘）作業(yè)E運行結(jié)束（3）FIFO（作業(yè)到達順序為C，D，B，E，A）0（分鐘）作業(yè)C，D，B，E，A到達作業(yè)C最先到達，被調(diào)入系統(tǒng)運行作業(yè)D，B，E，A等待系統(tǒng)調(diào)度6（分鐘）作業(yè)C運行完成作業(yè)D被調(diào)入系統(tǒng)運行作業(yè)B，E，A等待系統(tǒng)調(diào)度14（分鐘）作業(yè)D運行完成作業(yè)B被調(diào)入系統(tǒng)運行作業(yè)E，A等待系統(tǒng)調(diào)度18（分鐘）作業(yè)B運行完成作業(yè)E被調(diào)入系統(tǒng)運行作業(yè)A等待系統(tǒng)調(diào)度28（分鐘）作業(yè)E運行完成作業(yè)A被調(diào)入系統(tǒng)運行30（分鐘）作業(yè)A運行完成（4）短作業(yè)優(yōu)先0（分鐘）作業(yè)A，B，C，D，E到達作業(yè)A運行時間最短

10、，被調(diào)入系統(tǒng)運行作業(yè)B，C，D，E等待系統(tǒng)調(diào)度2（分鐘）作業(yè)A運行完成作業(yè)B運行時間最短，被調(diào)入系統(tǒng)運行作業(yè)C，D，E等待系統(tǒng)調(diào)度6（分鐘）作業(yè)B運行完成作業(yè)C運行時間最短，被調(diào)入系統(tǒng)運行作業(yè)D，E等待系統(tǒng)調(diào)度12（分鐘）作業(yè)C運行完成作業(yè)D運行時間最短，被調(diào)入系統(tǒng)運行作業(yè)E等待系統(tǒng)調(diào)度20（分鐘）作業(yè)D運行完成作業(yè)E運行時間最短，被調(diào)入系統(tǒng)運行30（分鐘）作業(yè)E運行完成解答：（1）最高優(yōu)先級優(yōu)先各作業(yè)的執(zhí)行結(jié)束時間分別為30、28、24、18、10。作業(yè)的平均周轉(zhuǎn)時間為：。（2）時間片輪轉(zhuǎn)（時間片為2分鐘）各作業(yè)的執(zhí)行結(jié)束時間分別為：2、12、20、26、30。作業(yè)的平均周轉(zhuǎn)時間為：。（3）

11、FIFO（作業(yè)到達順序為C、D、B、E、A）各作業(yè)的執(zhí)行結(jié)束時間分別為：30、18、6、14、28。作業(yè)的平均周轉(zhuǎn)時間為：。（4）短作業(yè)優(yōu)先各作業(yè)的執(zhí)行結(jié)束時間分別為：2、6、12、20、30作業(yè)的平均周轉(zhuǎn)時間為：。例題4.7（北京大學(xué)1997年試題）如果系統(tǒng)中所有作業(yè)是同時到達的，則使作業(yè)平均周轉(zhuǎn)時間最短的作業(yè)調(diào)度算法是（ ）。解答：短作業(yè)優(yōu)先。習(xí)題4.1（華中科技大學(xué)1997年試題）在一批處理系統(tǒng)中，設(shè)在一段時間內(nèi)先后有4個作業(yè)到達，它們的提交時間和運行時間由表4.7給出。用先來先服務(wù)和短作業(yè)優(yōu)先調(diào)度算法進行調(diào)度。計算在每一種調(diào)度算法下的平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。并說明哪一種算法的調(diào)

12、度性能更好些。（要求寫出必要的計算步驟）（單位：小時，以十進制計）表4.7 作業(yè)的提交時間和運行時間作業(yè)號提交時間運行時間18.002.5028.201.2038.300.3049.000.50解答：先來先服務(wù)算法下，平均周轉(zhuǎn)時間=3.3小時，帶權(quán)平均周轉(zhuǎn)時間=5.8短作業(yè)優(yōu)先算法下，平均周轉(zhuǎn)時間=2.9小時，帶權(quán)平均周轉(zhuǎn)時間=4.37因此，短作業(yè)優(yōu)先算法的調(diào)度性能更好些。習(xí)題4.2（西北工業(yè)大學(xué)2000年試題10分）假定要在一臺處理機上執(zhí)行表4.8所示作業(yè)：表4.8 作業(yè)的提交時間和運行時間作業(yè)號提交時間運行時間1103211323414552且假定這些作業(yè)在時刻0以1，2，3，4，5的順序到達。（1）說明分別使用FCFS、RR（時間片=1）、SJF以及非剝奪式優(yōu)先調(diào)度算法時，這些作業(yè)的執(zhí)行情況。（2）針對上述每種調(diào)度算法，給出平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。解答：作業(yè)號提交時間運行時間FCFS13.47.26RR（時間片=1）92.44SJF13.26.96非剝奪優(yōu)先調(diào)度12.46.24習(xí)題 4.3（南京大學(xué)2000年試題）現(xiàn)有兩道作業(yè)同時執(zhí)行，一道