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

2、稱為作業步。作業步。 作業的組織與作業步的確定，由用戶作業的組織與作業步的確定，由用戶做。做。 作業的四個階段：作業的四個階段：提交、收容、執行提交、收容、執行和完成。是一個動態的概念。和完成。是一個動態的概念。2.6.1 作業和進程的關系（作業和進程的關系（2）2、作業與進程的關系、作業與進程的關系 作業是任務實體作業是任務實體，進程是完成任務，進程是完成任務的執行實體；沒有作業任務，進程無事的執行實體；沒有作業任務，進程無事可干，沒有進程，作業任務沒法完成。可干，沒有進程，作業任務沒法完成。 作業概念更多地用在批處理操作系統，作業概念更多地用在批處理操作系統，而進程則可以用在各種多道程序設

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

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

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

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

7、業已經被選中并構成進作業已經被選中并構成進程去競爭處理器資源以獲得運行。程去競爭處理器資源以獲得運行。 完成狀態：完成狀態：作業已經運行結束，正在作業已經運行結束，正在等待緩輸出。等待緩輸出。作業調度與進程調度的關系作業調度與進程調度的關系 緩輸出緩輸出執行狀態執行狀態運運行行就就緒緒等等待待輸輸入入狀狀態態后后備備狀狀態態完完成成狀狀態態進程調度進程調度中級調度中級調度作業調度作業調度預輸入預輸入完成完成撤消進程撤消進程創建進程創建進程2.6.3 批處理作業的調度批處理作業的調度 作業調度：作業調度：對成批進入計算機系統的對成批進入計算機系統的用戶作業，根據作業控制塊的信息，按用戶作業，根據

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

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

10、分別為：28、37和和40，因此，因此，平均作平均作業周轉時間業周轉時間T = (28+37+40)/3 = 35二、先來先服務算法二、先來先服務算法FCFS(3) 若三個作業提交順序改為作業若三個作業提交順序改為作業2、1、3，平均作業周轉時間約為平均作業周轉時間約為29。(9+37+40)/3 29) 若三個作業提交順序改為作業若三個作業提交順序改為作業3、2、1，平均作業周轉時間約為平均作業周轉時間約為18。(3+12+40)/3 18) FCFS調度算法的平均作業周轉時間調度算法的平均作業周轉時間與作業提交的順序有關與作業提交的順序有關。二、最短作業優先算法二、最短作業優先算法SJF(

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

12、作業2 4 作業作業3 10 作業作業4 8 假設系統中沒有其他作業，現實施假設系統中沒有其他作業，現實施SJF調度算法，調度算法，二、最短作業優先算法二、最短作業優先算法SJF(3) SJF的作業調度的作業調度順序為作業順序為作業2、4、1、3， 平均作業周轉時間平均作業周轉時間 T = (4+12+21+31)/4 = 17 平均帶權作業周轉時間平均帶權作業周轉時間W=(4/4+12/8+21/9+31/10)/4 = 1.98 如果對它們如果對它們施行施行FCFS調度算法調度算法， 平均作業周轉時間平均作業周轉時間 T = (9+13+23+31)/4 = 19 平均帶權作業周轉時間平均

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

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

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

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

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

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

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

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