作業(yè)調(diào)度實例

1、2.6 批處理作業(yè)的管理與調(diào)度批處理作業(yè)的管理與調(diào)度主要內(nèi)容主要內(nèi)容2.6.1 作業(yè)和進(jìn)程的關(guān)系作業(yè)和進(jìn)程的關(guān)系2.6.2 批處理作業(yè)的管理批處理作業(yè)的管理2.6.3 批處理作業(yè)的調(diào)度批處理作業(yè)的調(diào)度2.6.4 作業(yè)調(diào)度算法作業(yè)調(diào)度算法2.6.1 作業(yè)和進(jìn)程的關(guān)系作業(yè)和進(jìn)程的關(guān)系1、作業(yè)的概念與特點、作業(yè)的概念與特點 作業(yè)作業(yè)(JOB)：是用戶提交給是用戶提交給OS計算的計算的一個獨立任務(wù)一個獨立任務(wù) 作業(yè)步作業(yè)步(Job Step)：一般作業(yè)須經(jīng)過一般作業(yè)須經(jīng)過若干個相對獨立又相互關(guān)聯(lián)的順序加工若干個相對獨立又相互關(guān)聯(lián)的順序加工步驟才能得到結(jié)果，其中每一步驟稱為步驟才能得到結(jié)果，其中每一步驟

2、稱為作業(yè)步。作業(yè)步。 作業(yè)的組織與作業(yè)步的確定，由用戶作業(yè)的組織與作業(yè)步的確定，由用戶做。做。 作業(yè)的四個階段：作業(yè)的四個階段：提交、收容、執(zhí)行提交、收容、執(zhí)行和完成。是一個動態(tài)的概念。和完成。是一個動態(tài)的概念。2.6.1 作業(yè)和進(jìn)程的關(guān)系（作業(yè)和進(jìn)程的關(guān)系（2）2、作業(yè)與進(jìn)程的關(guān)系、作業(yè)與進(jìn)程的關(guān)系 作業(yè)是任務(wù)實體作業(yè)是任務(wù)實體，進(jìn)程是完成任務(wù)，進(jìn)程是完成任務(wù)的執(zhí)行實體；沒有作業(yè)任務(wù)，進(jìn)程無事的執(zhí)行實體；沒有作業(yè)任務(wù)，進(jìn)程無事可干，沒有進(jìn)程，作業(yè)任務(wù)沒法完成?？筛桑瑳]有進(jìn)程，作業(yè)任務(wù)沒法完成。 作業(yè)概念更多地用在批處理操作系統(tǒng)，作業(yè)概念更多地用在批處理操作系統(tǒng)，而進(jìn)程則可以用在各種多道程序設(shè)

3、計系而進(jìn)程則可以用在各種多道程序設(shè)計系統(tǒng)。統(tǒng)。2.6.2 批處理作業(yè)的管理批處理作業(yè)的管理一、幾個術(shù)語：一、幾個術(shù)語： 脫機工作：脫機工作：批處理作業(yè)多采用脫機控制批處理作業(yè)多采用脫機控制方式工作方式工作 作業(yè)控制語言作業(yè)控制語言：用于寫作業(yè)說明書用于寫作業(yè)說明書 作業(yè)說明書作業(yè)說明書：主要有用戶的各種請求、主要有用戶的各種請求、作業(yè)的控制要求等。作業(yè)的控制要求等。 批處理作業(yè)的過程：批處理作業(yè)的過程：輸入、調(diào)度、執(zhí)輸入、調(diào)度、執(zhí)行和撤離。即作業(yè)的四個階段行和撤離。即作業(yè)的四個階段 二、二、作業(yè)控制塊作業(yè)控制塊(1) 作業(yè)控制塊（作業(yè)控制塊（JCB）：）：多道批處理操作多道批處理操作系統(tǒng)具有獨

4、立的作業(yè)管理模塊，必須像進(jìn)程系統(tǒng)具有獨立的作業(yè)管理模塊，必須像進(jìn)程管理一樣為每一個作業(yè)建立作業(yè)控制塊管理一樣為每一個作業(yè)建立作業(yè)控制塊。 JCB的創(chuàng)建與撤消：的創(chuàng)建與撤消：JCB通常是在批作業(yè)通常是在批作業(yè)進(jìn)入系統(tǒng)時，由進(jìn)入系統(tǒng)時，由Spooling系統(tǒng)系統(tǒng)(P428)建立的，建立的，它是作業(yè)存在于系統(tǒng)的標(biāo)志，作業(yè)撤離時，它是作業(yè)存在于系統(tǒng)的標(biāo)志，作業(yè)撤離時，JCB也被撤銷。也被撤銷。 Spooling技術(shù)：技術(shù)： Spooling技術(shù)是用技術(shù)是用一類物一類物理設(shè)備模擬另一類設(shè)備的技術(shù)。為了存放從輸入理設(shè)備模擬另一類設(shè)備的技術(shù)。為了存放從輸入設(shè)備輸入的信息（程序、數(shù)據(jù)、作業(yè)說明書）及設(shè)備輸入的

5、信息（程序、數(shù)據(jù)、作業(yè)說明書）及作業(yè)執(zhí)行的結(jié)果，在輔助存儲器上開辟了輸入井作業(yè)執(zhí)行的結(jié)果，在輔助存儲器上開辟了輸入井（緩沖區(qū)）和輸出井，模擬輸入和輸出設(shè)備。（緩沖區(qū)）和輸出井，模擬輸入和輸出設(shè)備。二、作業(yè)控制塊二、作業(yè)控制塊(2) JCB的主要內(nèi)容：的主要內(nèi)容： (1)作業(yè)情況：作業(yè)情況：用戶名、作業(yè)名、語言名用戶名、作業(yè)名、語言名 (2)資源需求：資源需求：估計估計CPU運行時間、最遲運行時間、最遲截止期、主存量、設(shè)備類型截止期、主存量、設(shè)備類型/臺數(shù)、文件臺數(shù)、文件數(shù)和數(shù)據(jù)量、函數(shù)庫數(shù)和數(shù)據(jù)量、函數(shù)庫/實用程序等。實用程序等。 (3)資源使用情況：資源使用情況：進(jìn)入系統(tǒng)時間、開始運進(jìn)入系統(tǒng)

6、時間、開始運行時間、己運行時間。行時間、己運行時間。 (4)作業(yè)控制：作業(yè)控制：優(yōu)先數(shù)、控制方式、操作順優(yōu)先數(shù)、控制方式、操作順序、出錯處理等。序、出錯處理等。 (5)作業(yè)類型：作業(yè)類型：CPU繁忙型、繁忙型、I/O繁忙型、繁忙型、批量型、終端型。批量型、終端型。三、作業(yè)的生命周期三、作業(yè)的生命周期作業(yè)生命周期有作業(yè)生命周期有4個狀態(tài)個狀態(tài)(4個階段個階段)： 輸入狀態(tài)：輸入狀態(tài)：此時作業(yè)的信息正在從輸此時作業(yè)的信息正在從輸入設(shè)備上預(yù)輸入。入設(shè)備上預(yù)輸入。 后備狀態(tài)：后備狀態(tài)：此時作業(yè)預(yù)輸入結(jié)束但尚此時作業(yè)預(yù)輸入結(jié)束但尚未被創(chuàng)建進(jìn)程（不能執(zhí)行）未被創(chuàng)建進(jìn)程（不能執(zhí)行） 執(zhí)行狀態(tài)：執(zhí)行狀態(tài)：作業(yè)

7、已經(jīng)被選中并構(gòu)成進(jìn)作業(yè)已經(jīng)被選中并構(gòu)成進(jìn)程去競爭處理器資源以獲得運行。程去競爭處理器資源以獲得運行。 完成狀態(tài)：完成狀態(tài)：作業(yè)已經(jīng)運行結(jié)束，正在作業(yè)已經(jīng)運行結(jié)束，正在等待緩輸出。等待緩輸出。作業(yè)調(diào)度與進(jìn)程調(diào)度的關(guān)系作業(yè)調(diào)度與進(jìn)程調(diào)度的關(guān)系 緩輸出緩輸出執(zhí)行狀態(tài)執(zhí)行狀態(tài)運運行行就就緒緒等等待待輸輸入入狀狀態(tài)態(tài)后后備備狀狀態(tài)態(tài)完完成成狀狀態(tài)態(tài)進(jìn)程調(diào)度進(jìn)程調(diào)度中級調(diào)度中級調(diào)度作業(yè)調(diào)度作業(yè)調(diào)度預(yù)輸入預(yù)輸入完成完成撤消進(jìn)程撤消進(jìn)程創(chuàng)建進(jìn)程創(chuàng)建進(jìn)程2.6.3 批處理作業(yè)的調(diào)度批處理作業(yè)的調(diào)度 作業(yè)調(diào)度：作業(yè)調(diào)度：對成批進(jìn)入計算機系統(tǒng)的對成批進(jìn)入計算機系統(tǒng)的用戶作業(yè)，根據(jù)作業(yè)控制塊的信息，按用戶作業(yè)，根據(jù)作

8、業(yè)控制塊的信息，按一定的策略選取某些作業(yè)，使它們可以一定的策略選取某些作業(yè)，使它們可以去獲得處理器運行，這項工作稱為作業(yè)去獲得處理器運行，這項工作稱為作業(yè)調(diào)度。調(diào)度。 作業(yè)調(diào)度的基本目標(biāo)：作業(yè)調(diào)度的基本目標(biāo)： 對任一作業(yè)的處理要盡可能快對任一作業(yè)的處理要盡可能快（Ti要小）要?。?對所有作業(yè)完成得快對所有作業(yè)完成得快(T=Ti要小要小) 整個系統(tǒng)的效率高整個系統(tǒng)的效率高2.6.4 作業(yè)調(diào)度算法作業(yè)調(diào)度算法 一、先來先服務(wù)算法一、先來先服務(wù)算法FCFS(1)（First Come First Served） 按照作業(yè)進(jìn)入系統(tǒng)的先后次序來挑選按照作業(yè)進(jìn)入系統(tǒng)的先后次序來挑選作業(yè)，作業(yè)，先進(jìn)入系統(tǒng)的

9、作業(yè)優(yōu)先被挑選先進(jìn)入系統(tǒng)的作業(yè)優(yōu)先被挑選。 FCFS算法的優(yōu)缺點：算法的優(yōu)缺點： 算法容易實現(xiàn)。算法容易實現(xiàn)。但效率不高，只顧及但效率不高，只顧及作業(yè)等候時間，沒考慮作業(yè)要求服務(wù)時作業(yè)等候時間，沒考慮作業(yè)要求服務(wù)時間的長短。因此優(yōu)待了長作業(yè)而不利于間的長短。因此優(yōu)待了長作業(yè)而不利于短作業(yè)。短作業(yè)。 一、先來先服務(wù)算法一、先來先服務(wù)算法FCFS(2) 例如，三個作業(yè)同時到達(dá)系統(tǒng)并立即例如，三個作業(yè)同時到達(dá)系統(tǒng)并立即進(jìn)入調(diào)度：作業(yè)名進(jìn)入調(diào)度：作業(yè)名 所需所需CPU時間時間 作業(yè)作業(yè)1 28 作業(yè)作業(yè)2 9 作業(yè)作業(yè)3 3 采用采用FCFS算法，三個作業(yè)的周轉(zhuǎn)時間算法，三個作業(yè)的周轉(zhuǎn)時間分別為：分別

10、為：28、37和和40，因此，因此，平均作平均作業(yè)周轉(zhuǎn)時間業(yè)周轉(zhuǎn)時間T = (28+37+40)/3 = 35二、先來先服務(wù)算法二、先來先服務(wù)算法FCFS(3) 若三個作業(yè)提交順序改為作業(yè)若三個作業(yè)提交順序改為作業(yè)2、1、3，平均作業(yè)周轉(zhuǎn)時間約為平均作業(yè)周轉(zhuǎn)時間約為29。(9+37+40)/3 29) 若三個作業(yè)提交順序改為作業(yè)若三個作業(yè)提交順序改為作業(yè)3、2、1，平均作業(yè)周轉(zhuǎn)時間約為平均作業(yè)周轉(zhuǎn)時間約為18。(3+12+40)/3 18) FCFS調(diào)度算法的平均作業(yè)周轉(zhuǎn)時間調(diào)度算法的平均作業(yè)周轉(zhuǎn)時間與作業(yè)提交的順序有關(guān)與作業(yè)提交的順序有關(guān)。二、最短作業(yè)優(yōu)先算法二、最短作業(yè)優(yōu)先算法SJF(1)

11、SJF(Shortest Job First ) SJF算法以進(jìn)入系統(tǒng)的作業(yè)所要算法以進(jìn)入系統(tǒng)的作業(yè)所要求的求的CPU時間為標(biāo)準(zhǔn)，時間為標(biāo)準(zhǔn)，總選取估計總選取估計計算時間最短的作業(yè)投入運行計算時間最短的作業(yè)投入運行。FJF算法的優(yōu)缺點：算法的優(yōu)缺點： 算法易于實現(xiàn)。算法易于實現(xiàn)。但效率不高，主但效率不高，主要弱點是忽視了作業(yè)等待時間；要弱點是忽視了作業(yè)等待時間； 會出現(xiàn)饑餓現(xiàn)象。會出現(xiàn)饑餓現(xiàn)象。二、最短作業(yè)優(yōu)先算法二、最短作業(yè)優(yōu)先算法SJF(2) 例如，四個作業(yè)同時到達(dá)系統(tǒng)并立即進(jìn)例如，四個作業(yè)同時到達(dá)系統(tǒng)并立即進(jìn)入調(diào)度：入調(diào)度： 作業(yè)名作業(yè)名 所需所需CPU時間時間 作業(yè)作業(yè)1 9 作業(yè)作業(yè)

12、2 4 作業(yè)作業(yè)3 10 作業(yè)作業(yè)4 8 假設(shè)系統(tǒng)中沒有其他作業(yè)，現(xiàn)實施假設(shè)系統(tǒng)中沒有其他作業(yè)，現(xiàn)實施SJF調(diào)度算法，調(diào)度算法，二、最短作業(yè)優(yōu)先算法二、最短作業(yè)優(yōu)先算法SJF(3) SJF的作業(yè)調(diào)度的作業(yè)調(diào)度順序為作業(yè)順序為作業(yè)2、4、1、3， 平均作業(yè)周轉(zhuǎn)時間平均作業(yè)周轉(zhuǎn)時間 T = (4+12+21+31)/4 = 17 平均帶權(quán)作業(yè)周轉(zhuǎn)時間平均帶權(quán)作業(yè)周轉(zhuǎn)時間W=(4/4+12/8+21/9+31/10)/4 = 1.98 如果對它們?nèi)绻麑λ鼈兪┬惺┬蠪CFS調(diào)度算法調(diào)度算法， 平均作業(yè)周轉(zhuǎn)時間平均作業(yè)周轉(zhuǎn)時間 T = (9+13+23+31)/4 = 19 平均帶權(quán)作業(yè)周轉(zhuǎn)時間平均帶權(quán)

13、作業(yè)周轉(zhuǎn)時間 W = (9/9+13/4+23/10+31/8)/4 = 2.51二、最短作業(yè)優(yōu)先算法二、最短作業(yè)優(yōu)先算法SJF(4)SJF算法與算法與FCFS算法的比較：算法的比較： SJF的平均作業(yè)周轉(zhuǎn)時間比的平均作業(yè)周轉(zhuǎn)時間比FCFS要小，故它的調(diào)度性能比要小，故它的調(diào)度性能比FCFS好。好。SJF調(diào)度算法的問題：調(diào)度算法的問題： 實現(xiàn)實現(xiàn)SJF調(diào)度算法需要知道作業(yè)調(diào)度算法需要知道作業(yè)所需運行時間，否則調(diào)度就沒有依所需運行時間，否則調(diào)度就沒有依據(jù)，要精確知道一個作業(yè)的運行時據(jù)，要精確知道一個作業(yè)的運行時間是辦不到的。間是辦不到的。SJF算法進(jìn)一步討論算法進(jìn)一步討論(1) 最短剩余時間優(yōu)先

14、算法最短剩余時間優(yōu)先算法SRTF（Shortest Remaining Time First）: 把把SJF算法改為搶占式的算法改為搶占式的SJF算法算法 一個新作業(yè)進(jìn)入就緒狀態(tài)，如果新一個新作業(yè)進(jìn)入就緒狀態(tài)，如果新作業(yè)需要的作業(yè)需要的CPU時間比當(dāng)前正在執(zhí)行時間比當(dāng)前正在執(zhí)行的作業(yè)剩余下來還需的的作業(yè)剩余下來還需的CPU時間短，時間短，SRTF強占當(dāng)前正在執(zhí)行作業(yè)的強占當(dāng)前正在執(zhí)行作業(yè)的CPU。 此算法不但適用于作業(yè)此算法不但適用于作業(yè)JOB調(diào)度，調(diào)度，同樣也適用于進(jìn)程調(diào)度。同樣也適用于進(jìn)程調(diào)度。SJF算法進(jìn)一步討論算法進(jìn)一步討論(2) 例子：假如四個就緒作業(yè)其到達(dá)系統(tǒng)例子：假如四個就緒作業(yè)

15、其到達(dá)系統(tǒng)和所需和所需CPU時間如下：時間如下： 作業(yè)名作業(yè)名 到達(dá)系統(tǒng)時間到達(dá)系統(tǒng)時間 用用CPU時間時間(毫秒毫秒) - Job1 0 8 Job2 1 4 Job3 2 9 Job4 3 5JOB5101 SJF算法進(jìn)一步討論算法進(jìn)一步討論(3) 采用采用SRTF算法算法 各作業(yè)運行所需時間及運行的各作業(yè)運行所需時間及運行的起止時間：起止時間： J1 J2 J4 J1 J30151017268 4 5 7 90 1 3 0 2到達(dá)時間到達(dá)時間SJF算法進(jìn)一步討論算法進(jìn)一步討論(4) Job1從從0開始執(zhí)行，就緒隊列僅一個作業(yè)。開始執(zhí)行，就緒隊列僅一個作業(yè)。 Job2在時間在時間1到達(dá)，到

16、達(dá)，Job1剩余時間（剩余時間（7毫毫秒）大于秒）大于JOB2所需時間（所需時間（4毫秒），毫秒），Job1被剝奪，被剝奪，Job2被調(diào)度執(zhí)行。被調(diào)度執(zhí)行。 平均等待時間是（平均等待時間是（10-1）+（1-1）+（17-2）+（5-3）/4=26/4=6.5毫秒。毫秒。 采用非搶占式采用非搶占式SJF調(diào)度，那么，平均等待調(diào)度，那么，平均等待時間是時間是7.75毫秒。毫秒。(0+(8-1)+(17-2)+(12-3)/4=31/4=7.75三、響應(yīng)比最高者優(yōu)先三、響應(yīng)比最高者優(yōu)先(HRRF)算法算法HRRF（Highest Response Ratio First） FCFS與與SJF是片面的

17、調(diào)度算法是片面的調(diào)度算法。FCFS只考慮作業(yè)等候時間而忽視了作業(yè)的計只考慮作業(yè)等候時間而忽視了作業(yè)的計算時問，算時問，SJF只考慮用戶估計的作業(yè)計只考慮用戶估計的作業(yè)計算時間而忽視了作業(yè)等待時間。算時間而忽視了作業(yè)等待時間。 HRRF是介乎這兩者之間的折衷算法是介乎這兩者之間的折衷算法，既考慮作業(yè)等待時間，又考慮作業(yè)的運既考慮作業(yè)等待時間，又考慮作業(yè)的運行時間，既照顧短作業(yè)又不使長作業(yè)的行時間，既照顧短作業(yè)又不使長作業(yè)的等待時間過長，改進(jìn)了調(diào)度性能。等待時間過長，改進(jìn)了調(diào)度性能。三、三、HRRF-響應(yīng)比定義響應(yīng)比定義 作業(yè)進(jìn)入系統(tǒng)后的等待時間與估計作業(yè)進(jìn)入系統(tǒng)后的等待時間與估計運行時間之比稱作

18、響應(yīng)比運行時間之比稱作響應(yīng)比，即，即 響應(yīng)比響應(yīng)比 1+已等待時間已等待時間/估計運行時間估計運行時間 HRRF算法特點：算法特點： 短作業(yè)容易得到較高響應(yīng)比短作業(yè)容易得到較高響應(yīng)比 長作業(yè)等待時間足夠長后，也將獲得足長作業(yè)等待時間足夠長后，也將獲得足夠高的響應(yīng)比，夠高的響應(yīng)比， 饑餓現(xiàn)象不會發(fā)生。饑餓現(xiàn)象不會發(fā)生。三、三、HRRF-算法舉例算法舉例(1) 例如，以下四個作業(yè)先后到達(dá)系統(tǒng)進(jìn)入例如，以下四個作業(yè)先后到達(dá)系統(tǒng)進(jìn)入調(diào)度：調(diào)度： 作業(yè)名作業(yè)名 到達(dá)時間到達(dá)時間 所需所需CPU時間時間 作業(yè)作業(yè)1 0 20 作業(yè)作業(yè)2 5 15 作業(yè)作業(yè)3 10 5 作業(yè)作業(yè)4 15 10三、三、HRR

19、F-算法舉例算法舉例(2)假設(shè)實施假設(shè)實施SJF SJF的作業(yè)調(diào)度順序為作業(yè)的作業(yè)調(diào)度順序為作業(yè)1、3、4、2， 平均作業(yè)周轉(zhuǎn)時間平均作業(yè)周轉(zhuǎn)時間T = (20+(25-19)+(35-15)+(50-5)(20+15+20+45)4 = 25 平均帶權(quán)作業(yè)周轉(zhuǎn)時間平均帶權(quán)作業(yè)周轉(zhuǎn)時間W = (20/20+15/5+25/10+45/15)4 = 2.25三、三、HRRF-算法舉例算法舉例(3)假設(shè)實施假設(shè)實施FCFS 如果對它們施行如果對它們施行FCFS調(diào)度算法調(diào)度算法 平均作業(yè)周轉(zhuǎn)時間平均作業(yè)周轉(zhuǎn)時間T = (20+30+30+35)4 = 28.75 平均帶權(quán)作業(yè)周轉(zhuǎn)時間平均帶權(quán)作業(yè)周轉(zhuǎn)

20、時間W = (20/20+30/15+30/5+35/10)4 = 3.13三、三、HRRF-算法舉例算法舉例(4)對作業(yè)流執(zhí)行對作業(yè)流執(zhí)行HRRF調(diào)度算法調(diào)度算法開始只有開始只有作業(yè)作業(yè)1，被選中執(zhí)行時間，被選中執(zhí)行時間20ms；作業(yè)作業(yè)1執(zhí)行完畢，響應(yīng)比依次為執(zhí)行完畢，響應(yīng)比依次為1+15/15、1+10/5、1+5/10，作業(yè)作業(yè)3被選中，執(zhí)行時間被選中，執(zhí)行時間5ms；作業(yè)作業(yè)3執(zhí)行完畢，響應(yīng)比依次為執(zhí)行完畢，響應(yīng)比依次為1+20/15、1+10/10，作業(yè)作業(yè)2被選中，執(zhí)行時間被選中，執(zhí)行時間15ms；作業(yè)作業(yè)2執(zhí)行完畢，執(zhí)行完畢，作業(yè)作業(yè)4被選中，執(zhí)行時間被選中，執(zhí)行時間10ms； 平均作業(yè)周轉(zhuǎn)時間平均作業(yè)周轉(zhuǎn)時間T = (20+15+35+35)/4 = 26.25 平均帶