第5章作業(yè)調(diào)度

1、第第5 5章章 作業(yè)調(diào)度作業(yè)調(diào)度 主講：房道偉主講：房道偉Daowei_操作系統(tǒng)原理操作系統(tǒng)原理主要內(nèi)容n作業(yè)的狀態(tài)與處理流程作業(yè)的狀態(tài)與處理流程n作業(yè)的調(diào)度作業(yè)的調(diào)度n進程的調(diào)度進程的調(diào)度n選擇調(diào)度算法時應(yīng)考慮的問題選擇調(diào)度算法時應(yīng)考慮的問題n調(diào)度算法調(diào)度算法 在大型通用系統(tǒng)中，可能有數(shù)百個批處理作業(yè)存放在磁盤的作業(yè)隊列中，有數(shù)百個終端同主機相聯(lián)接。因此如何從這些作業(yè)中挑選作業(yè)進入主存運行、如何在作業(yè)或進程間分配處理等，問題無疑是操作系統(tǒng)的資源管理功能中的一個重要問題。本章主要討論處理機分配問題，或稱處理機調(diào)度。一般來說，處理機調(diào)度可以分成三級：(1) 高級調(diào)度：高級調(diào)度：又稱作業(yè)調(diào)度，其主

2、要功能是按照某種原則從磁盤某些盤區(qū)的作業(yè)隊列中選取作業(yè)進入主存，并為作業(yè)做好運行前的準備工作和作業(yè)完成后的善后工作。(2) 中級調(diào)度：中級調(diào)度：它決定哪些進程被允許參與競爭處理機資源。中級調(diào)度主要只是起到短期調(diào)整系統(tǒng)負荷的作用，以平順系統(tǒng)的操作。其所使用的方法是通過“ 掛起 ” 和“ 解除掛起 ” 一些進程，來達到平順系統(tǒng)操作的目的。(3) 低級調(diào)度：低級調(diào)度：又稱進程調(diào)度，其主要功能是按照某種原則將處理機分配給就緒進程。執(zhí)行低級調(diào)度功能的程序稱為進程調(diào)度程序，由它實現(xiàn)處理機在進程間的轉(zhuǎn)換。它必須常駐主存，是操作系統(tǒng)內(nèi)核的主要部分。RUNreadyablockedareadysblokeds后

3、備完成作業(yè)后備狀態(tài)執(zhí)行內(nèi)存時間片到I/O請求I/O完成高級調(diào)度(作業(yè)調(diào)度)掛起解掛掛起解掛進程調(diào)度低級調(diào)度中級調(diào)度5.1 作業(yè)的狀態(tài)與處理流程作業(yè)的狀態(tài)與處理流程一、一、 作業(yè)狀態(tài)作業(yè)狀態(tài)提交收容執(zhí)行完成提交狀態(tài)后備狀態(tài)運行狀態(tài)完成狀態(tài) 作業(yè)從提交給系統(tǒng)直到它完成后離開系統(tǒng)前的整個活動常劃分為若干階段。作業(yè)在每一階段中所處的狀況稱為作業(yè)的狀態(tài)。系統(tǒng)中的作業(yè)通常分為四種狀態(tài)：(1) 提交狀態(tài)：提交狀態(tài)：一個作業(yè)被提交給機房后或用戶通過終端鍵盤向計算機中鍵入其作業(yè)時所處的狀態(tài)為提交狀態(tài)。(2) 后備狀態(tài)：后備狀態(tài)：作業(yè)的全部信息都已通過輸入機輸入，并由操作系統(tǒng)將其存放在磁盤的某些盤區(qū)中等待運行，則

4、稱為后備狀態(tài)。(3) 運行狀態(tài)：運行狀態(tài)：作業(yè)一旦被作業(yè)調(diào)度程序先中而被送入主存中投入運行，稱之為運行狀態(tài)。(4) 完成狀態(tài)：完成狀態(tài)：作業(yè)完成其全部運行，釋放出其所占用的全部資源，準備退出系統(tǒng)的作業(yè)狀況稱為完成狀態(tài)。5.2 作業(yè)的調(diào)度作業(yè)的調(diào)度 系統(tǒng)中往往有成百個作業(yè)被收容在磁盤輸入井中，為了管理和調(diào)度作業(yè)，就必須記錄已進入系統(tǒng)的各作業(yè)的情況。因此同進程中的情況類似，系統(tǒng)也為每個作業(yè)設(shè)置一個作業(yè)控制塊 (記為JCB)，它記錄了作業(yè)的有關(guān)信息。不同系統(tǒng)的 JCB 所包含的信息有所不同，這取決系統(tǒng)對作業(yè)調(diào)度的要求。JCB結(jié)構(gòu) 見書P122 圖6.8 JCB 是在作業(yè)進入系統(tǒng)時由 SPOOL 系統(tǒng)

5、為其建立的。其內(nèi)容由作業(yè)控制卡中得到。同樣 JCB 也是作業(yè)存在于系統(tǒng)的標志，作業(yè)進入系統(tǒng)時，則為之建立 JCB。當作業(yè)退出系統(tǒng)時，則其 JCB 也被撤消。 在磁盤輸入井中的所有后備作業(yè)按作業(yè)類型將它們組成一個或多個后備作業(yè)隊列。所謂后備作業(yè)隊列是由作業(yè)控制塊 JCB 用表格或鏈指針組成的隊列。作業(yè)隊列可按優(yōu)先數(shù)大小和作業(yè)到達系統(tǒng)的時間順序排列。根據(jù)系統(tǒng)內(nèi)所有資源的使用情況， 按照某種調(diào)度算法選擇一個后備作業(yè)進入系統(tǒng)， 并為其創(chuàng)造一個進程。 為此，作業(yè)調(diào)度還要為選中的作業(yè)分配資源，作好作業(yè)支行前的準備。完成作業(yè)調(diào)度功能的程序稱為作業(yè)調(diào)度程序。作業(yè)調(diào)度程序要完成以下工作：(1) 按照某種調(diào)度算法

6、從后備作業(yè)隊列中挑選作業(yè)。(2) 為選中的作業(yè)分配主存和外設(shè)資源。(3) 為選中的作業(yè)建立相應(yīng)的進程。(4) 構(gòu)造和填寫作業(yè)運行時所需的有關(guān)表格。(如作業(yè)表)(5) 作業(yè)結(jié)束時完成該作業(yè)的善后處理工作，如收回資源，輸出必要的信息，撤消該作業(yè)的全部進程 (PCB) 和作業(yè)控制塊 JCB。5.3 進程調(diào)度進程調(diào)度 作業(yè)調(diào)度程序在挑選作業(yè)進入主存運行時，要為該作業(yè)建立相應(yīng)的進程。在作業(yè)完成后要撤消該作業(yè)的全部進程。因此作業(yè)調(diào)度程序要調(diào)用操作系統(tǒng)內(nèi)核所提供的有關(guān)的進程管理原語。由于進程只能由其父進程建立，所以在一般系統(tǒng)中，作業(yè)調(diào)度程序都以進程的形式在系統(tǒng)中存在和活動，稱為作業(yè)調(diào)度進程。作業(yè)調(diào)度進程可以

7、說是系統(tǒng)中的祖先進程，由它完成作業(yè)調(diào)度的諸多功能。 一個進程被建立后，系統(tǒng)為了便于對進程的管理，將系統(tǒng)中的所有進程按其狀態(tài)，將其組織成不同的進程隊列。于是系統(tǒng)中有運行進程隊列、就緒進程隊列和各種事件的進程等待隊列。 進程調(diào)度的功能是從就緒隊列中挑選一個進程到處理機上運行。負責進程調(diào)度功能的內(nèi)核程序稱為進程序調(diào)度程序。 所謂作業(yè)調(diào)度程序挑選作業(yè)進主存運行是個宏觀的概念，實際上被選進主存運行的作業(yè)只是具有了競爭處理機的機會(將來真正在處理機上運行的是該作業(yè)的一個進程)。而進程調(diào)度程序才是真正讓某個就緒進程到處理機上運行。5.4 選擇調(diào)度算法時應(yīng)考慮的問題選擇調(diào)度算法時應(yīng)考慮的問題 目前比較普遍使用

8、的幾種調(diào)度算法，對于作業(yè)調(diào)度和進程調(diào)度大致上都是適用的。 在設(shè)計系統(tǒng)的調(diào)度程序時，首先要決定選擇何種調(diào)度算法，依據(jù)此算法來編制相應(yīng)的調(diào)度程序。而調(diào)度算法實際上就是系統(tǒng)所采取的調(diào)度策略，選擇時所要考慮的因素很多。如系統(tǒng)各類資源的均衡使用；對用戶公平并使用戶滿意；用戶作業(yè)到達系統(tǒng)的時間；作業(yè)的優(yōu)先數(shù)；對主存和外設(shè)的要求；以及整個系統(tǒng)的效率等。 設(shè)計時應(yīng)將那些對系統(tǒng)運行影響較大的關(guān)鍵因素作為調(diào)度算法考慮的主要依據(jù)。(1) 設(shè)計目標：設(shè)計目標：目標不同，系統(tǒng)的設(shè)計要求自然不同。如批處理系統(tǒng)所追求的是充分發(fā)揮和提高計算機的效率；實時系統(tǒng)所關(guān)心的是不要丟失實時信息并及時給以處理；而分時系統(tǒng)則側(cè)重于保證用戶

9、的請示及時給予響應(yīng)；計算中心要求系統(tǒng)吞吐量在大等等。(2) 資源利用率：資源利用率：在考慮設(shè)計目標的前提下應(yīng)充分發(fā)揮各種資源的效能，最大限度地使它們忙碌。科學計算型作業(yè)和數(shù)據(jù)處理型作業(yè)搭配運行就是一種方法。(3) 均衡地處理系統(tǒng)和用戶的要求：均衡地處理系統(tǒng)和用戶的要求：例如個別用戶可能要求使用系統(tǒng)中的幾乎全部外設(shè)，卻只要求很少的主存。系統(tǒng)若滿足這類用戶的愿望，勢必影響主存利用率，從而降低系統(tǒng)效率，所以一般都不得不推遲這種作業(yè)的運行時間，等到有要求內(nèi)存多而外設(shè)少的作業(yè)與之搭配運行。但是我們選擇的算法也不應(yīng)使一個作業(yè)的運行被無限制地推遲。(4) 在使用優(yōu)先級的系統(tǒng)中，每個進程都有一個優(yōu)先數(shù)，調(diào)度算

10、法應(yīng)優(yōu)先運行高優(yōu)先級進程。(5) 在使用優(yōu)先數(shù)的系統(tǒng)中，調(diào)度策略還分為“ 可搶占 ” 和“ 不可搶占 ” 兩種方式。搶占策略通常使用于需要迅速響應(yīng)高優(yōu)先級進程的系統(tǒng)中。1. 目標目標: 每天運行盡可能多的作業(yè) 選擇短作業(yè)(吞吐量) 使處理機保持“ 忙” 選擇大運輸量(I/O少) 使I/O保持“ 忙” 選大I/O效率效率:5.5 調(diào)度算法調(diào)度算法 公平性 FCFS(先來先服務(wù)) 對所有進程公平2. 調(diào)度算法的衡量調(diào)度算法的衡量盡量縮短周轉(zhuǎn)時間周轉(zhuǎn)時間: 作業(yè)提交作業(yè)完成之間的時間(1) 作業(yè)平均周轉(zhuǎn)時間:nTTnii)(1其中 n 作業(yè)流中的作業(yè)數(shù)Ti 第i個作業(yè)周轉(zhuǎn)時間Ti= tci tsi其

11、中 tsi 作業(yè)i提交時間tci 作業(yè)i完成時間(2) 平均帶權(quán)周轉(zhuǎn)時間:ntTnwwniRiinii)()(11其中: tRi 作業(yè)i的實際運行時間wi 作業(yè)i的帶權(quán)周轉(zhuǎn)時間3. 作業(yè)調(diào)度算法及衡量作業(yè)調(diào)度算法及衡量 (1) FCFS 先來先服務(wù)先來先服務(wù) 先來先服務(wù)算法是最簡單的調(diào)度方法。其基本原則是按照作業(yè)到達系統(tǒng)或進程進入就緒隊列的先后次序來選擇。FCFS 策略是屬于不可搶占策略不可搶占策略。作業(yè)提交時間運行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間ts(時)tR(時)tB(時)tC(時)ti(時)Wi(Z)12348.008.509.009.502.000.500.100.208.00

12、10.0010.5010.6010.0010.5010.6010.802.002.001.601.306.901.004.0016.006.5027.50平均周轉(zhuǎn)時間 T=6.90/4=1.725(小時)平均帶權(quán)時間 W=27.5/4=6.875 從表面上來說，對于所有進程和作業(yè)都是公平的，并且一個作業(yè)的等待時間是可以預(yù)告估計的。另一方面來說這個方法也不見得公平，當一個大作業(yè)先到達系統(tǒng)時就會使許多小作業(yè)等待很長時間，提高了平均的作業(yè)周轉(zhuǎn)時間，會使許多小作業(yè)的用戶不滿。 先來先服務(wù)算法已很少作主要的調(diào)度策略，常被結(jié)合在其它的調(diào)度策略中使用。例如，在使用優(yōu)先級作為調(diào)度策略的系統(tǒng)中，往往對許多具有相

13、同優(yōu)先級的進程，使用先來先服務(wù)的原則。(2) 優(yōu)先級調(diào)度算法優(yōu)先級調(diào)度算法 按照進程的優(yōu)先級大小來調(diào)度，使高優(yōu)先級進程得到優(yōu)先的處理的高度策略稱為優(yōu)先級調(diào)度算法。 但在許多采用優(yōu)先級調(diào)度的系統(tǒng)中，通常采用動態(tài)優(yōu)先數(shù)策略。進程的優(yōu)先級不是固定的，往往隨許多因素的變化而變化。尤其隨作業(yè)（進程）的等待時間、已使用的處理機時間或其它資源的使用情況而定。優(yōu)先級調(diào)度方法又可分為： 非搶占的優(yōu)先級調(diào)度法：即一旦某個高優(yōu)先級的進程占有了處理機，就一直運行下去，直到由于其自身的原因而主動讓出處理機時(任務(wù)完成或等待事件)才讓另一高優(yōu)先級進程運行。 可搶占的優(yōu)先級調(diào)度法：任何時刻都嚴格按照高優(yōu)先級進程在處理機上運

14、行的原則進行進程的調(diào)度。例：某些I/O繁忙型的進程，它們大部分時間是在等待I/O操作完成，對于這一類進程，當它們要求CPU運行時，應(yīng)立即給予滿足，以便讓它們開始下一個I/O操作和其它計算型的進程并行工作。否則，這些I/O繁忙型的進程將長時間占據(jù)存儲器，降低系統(tǒng)并行度。一個行之有效的算法是在進程每次獲取CPU運行后，重新指定該進程的優(yōu)先級為 1/f。這里的f表示進程上次在CPU上實際運行時間與時間片之比。例如，若時間片為100毫秒，進程上次在CPU上的實際運行時間為2毫秒，則它的優(yōu)稱級為50；若它上次實際運行時間為50毫秒，則它的優(yōu)級為2。由于I/O繁忙型的進程每次在CPU上運行的時間很短，依此

15、算法，它們的優(yōu)先級將較高，從而優(yōu)先得到服務(wù)。(3) 時間片輪轉(zhuǎn)法時間片輪轉(zhuǎn)法 輪轉(zhuǎn)法是最簡單又最公平的進程調(diào)度算法，因此也是使用得最多的算法之一。 輪轉(zhuǎn)法分配給每一進程在CPU上運行的時間長度，稱之為時間片。諸進程以此時間片為限制，輪流使用CPU。如果時間片到期時，進程尚未完成運行，調(diào)度程序?qū)儕Z它正在使用的CPU，轉(zhuǎn)讓給另一進程使用；如果進程在使用完它的某一時間片之前已經(jīng)完成運行或已阻塞，CPU也立即轉(zhuǎn)讓給另一進程使用。 輪轉(zhuǎn)法在實現(xiàn)上也很容易，調(diào)度程序只要維護一個先進先出的隊列數(shù)據(jù)結(jié)構(gòu)，將就緒進程排隊，每當一個進程的時間片運行完后，便把它從原來的隊頭位置移到隊尾，然后把現(xiàn)在處于隊頭位置的進

16、程調(diào)度到CPU上運行。時間片的計數(shù)則可通過定時中斷實現(xiàn)。 輪轉(zhuǎn)法的性能取決于時間片長度的選擇，進程間的CPU上的切換需要時間。若一次切換時間為5毫秒，時間片長度選擇為20毫秒，則20的CPU時間花費于進程調(diào)度程序。為了改善CPU的利用率，可以增大時間片，比如說為500毫秒，此時CPU利用率達99之多，但每一進程的響應(yīng)時間也因之增大。若就緒隊列中共有10個進程，則每一進程需要等待5秒鐘，才能在CPU上服務(wù)一次。 通常來說，選擇時間片為100毫秒左右比較適宜。 實際中，優(yōu)先級算法常和輪轉(zhuǎn)法結(jié)合使用，也就是按優(yōu)先級將進程分組，組間采用優(yōu)先級調(diào)度算法，而組內(nèi)優(yōu)先級相同的進程則按輪轉(zhuǎn)法調(diào)度。顯然，若優(yōu)先

17、級不動態(tài)地進行調(diào)整，則優(yōu)先級低的就緒進程就可能餓死。輪轉(zhuǎn)法輪轉(zhuǎn)法 (Round Robin) 簡單輪轉(zhuǎn)法 分配給就緒隊列，每一進程一個時間片(每一進程在CPU上運行的時間長度)輪流執(zhí)行。時間qT = N q就緒隊列q足夠大到每一進程執(zhí)行完，F(xiàn)CFC (先到先服務(wù))q 適當 進程均勻執(zhí)行q 太小 開銷太大，有切換時間，CPU利用率低。例：切換t = 5ms, q = 20ms, 則CPU利率率80，有20花費在進程調(diào)度程序。 決定q 大小因素：響應(yīng)時間T (進程等待時間)、隊列長度N、輪換時間 (切換時間)、CPU能力 (運算速度)。例：上例中為改善CPU的利用率，可增大時間片，設(shè)q = 500

18、ms，此時CPU利用率為99之多，但每個P 的相應(yīng)時間也因而增大。若N = 10，則每個P 的相應(yīng)時間需等5秒，才能在CPU上服務(wù)一次。 考慮上述條件，選擇時間片為100ms左右比較適宜。 固定周期輪轉(zhuǎn)法q 為時間片， T 為周期， N 為進程數(shù)固定T ：maxNTq 固定T，N q，開銷減少(4) SJF最短作業(yè)優(yōu)先的調(diào)度算法最短作業(yè)優(yōu)先的調(diào)度算法 要求運行時間最短的作業(yè)作為下一次服務(wù)的對象對于上述作業(yè)流，作業(yè)1運行結(jié)束后，后備作業(yè)表中已有作業(yè)2， 3， 4， 因為作業(yè)3要求運行時間最短， 故選3， 4， 2。tstRtBTiWi12348.008.509.009.502.000.500.1

19、00.208.0010.3010.0010.102.002.301.100.806.201.004.6011.004.0020.60T = 1.55 W=5.15優(yōu): 比FCFS， T W缺: 有的作業(yè)始終得不到運行tc10.0010.8010.1010.30作業(yè)提交時間運行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間(5) 最短剩余時間優(yōu)先調(diào)度算法最短剩余時間優(yōu)先調(diào)度算法 最短剩余時間優(yōu)先調(diào)度算法是把最短作業(yè)優(yōu)稱算法使用于分時環(huán)境中的變型。其基本思想是讓運行到作業(yè)完成時所需的運行時間最短的進程優(yōu)先得到處理，其中包括新進入系統(tǒng)的進程。在最短作業(yè)優(yōu)先策略中，一個作業(yè)一旦得到處理機就一直運行到完成（或等待事件）而不能被搶占（除非主動讓出處理機）。而最短剩余時間優(yōu)先策略是可以被一個新進入系統(tǒng)的，并且其運行時間少于當前運行進程的剩余運行時間的進程所搶占。 本策略的優(yōu)點是可以用于分時系統(tǒng)，保證及時響應(yīng)用戶要求。缺點是系統(tǒng)開銷增加，首先要保存進程的運行情況記錄，以比較其剩余時間大小。其次，搶占本身也要消耗處理機時間。這個策略使短作業(yè)一進入系統(tǒng)就能立即得到服務(wù)，從而降低作業(yè)的平均等待時間。(6) 響應(yīng)比高者優(yōu)先響應(yīng)比高者優(yōu)先(HRN)算法算法響應(yīng)比作業(yè)運行時間作業(yè)等待時間作業(yè)運行時間作業(yè)響應(yīng)時間1pR上題: 順序1-3-2-412