第六章 處理機調(diào)度

1、第六章第六章 處理機調(diào)度處理機調(diào)度（一）（一） 處理機的多級調(diào)度處理機的多級調(diào)度（二）（二） 作業(yè)調(diào)度作業(yè)調(diào)度（三）（三） 進程調(diào)度進程調(diào)度（一）（一） 處理機的多級調(diào)度處理機的多級調(diào)度一一. . 處理機調(diào)度的功能處理機調(diào)度的功能n 確定數(shù)據(jù)結(jié)構(gòu)n 制定調(diào)度策略（調(diào)度原則）n 給出調(diào)度算法n 具體的實施處理機分派不同類型的操作系統(tǒng)往往采用不同的處理機分配方法。二二. . 處理機調(diào)度的分層實現(xiàn)處理機調(diào)度的分層實現(xiàn)只有內(nèi)存的程序才能在CPU上運行。因此，處理機的調(diào)度通常分為兩層：n 宏觀上：作業(yè)調(diào)度 對存放在輔存設(shè)備上的大量作業(yè)，以一定的策略進行挑選，分配主存等必要的資源，建立作業(yè)對應(yīng)的進程，使其

2、投入運行。n 微觀上：進程調(diào)度 對進入注冊的所有進程，確定哪個進程在什么時候獲得處理機，使用多長時間。三三. . 批處理系統(tǒng)中的處理機調(diào)度批處理系統(tǒng)中的處理機調(diào)度四四. . 多任務(wù)操作系統(tǒng)中的處理機調(diào)度多任務(wù)操作系統(tǒng)中的處理機調(diào)度在分時系統(tǒng)或支持多任務(wù)并發(fā)執(zhí)行的個人計算機操作系統(tǒng)中，系統(tǒng)將用戶提交的任務(wù)處理為進程，一個進程又可以創(chuàng)建多個子進程，形成可以并發(fā)執(zhí)行的多進程。進程調(diào)度的任務(wù)任務(wù)是：當處理機空閑時，以某種策略選擇一個就緒進程去運行，并分配處理機的時間。另外，由于分時系統(tǒng)中的作業(yè)調(diào)度功能很弱（甚至沒有），因此有些分時系統(tǒng)會將進程在內(nèi)、外存之間進行交換。由于進程仍然存在，也與處理機的分配無

3、關(guān)，故稱為中級調(diào)度。五五. . 多線程操作系統(tǒng)中的處理機調(diào)度多線程操作系統(tǒng)中的處理機調(diào)度在支持多線程運行的系統(tǒng)中，每個進程都創(chuàng)建一個線程，也可以創(chuàng)建多個線程。系統(tǒng)為進程分配它所需要的資源，而處理機的分配的對象則為線程。系統(tǒng)提供線程調(diào)度程序，其功能是當處理機空閑時，以某種策略選擇一個就緒線程去運行，并分配處理機時間。（二）（二） 作業(yè)調(diào)度作業(yè)調(diào)度一一. . 作業(yè)的狀態(tài)作業(yè)的狀態(tài) 作業(yè)在整個活動期間一共有四種狀態(tài)：提交狀態(tài)提交狀態(tài)：用戶將自己的程序和數(shù)據(jù)提交給系統(tǒng)，等待輸入。后備狀態(tài)后備狀態(tài)：作業(yè)已存放在磁盤上，等待掉進主存。執(zhí)行狀態(tài)執(zhí)行狀態(tài)：作業(yè)在主存中運行。完成狀態(tài)完成狀態(tài)：作業(yè)計算完成開始，

4、退出主存。作業(yè)調(diào)度的主要任務(wù)是完成作業(yè)從后備狀態(tài)到執(zhí)行狀態(tài)和從執(zhí)行狀態(tài)到完成狀態(tài)的轉(zhuǎn)變。二二. . 作業(yè)調(diào)度的功能作業(yè)調(diào)度的功能n確定數(shù)據(jù)結(jié)構(gòu)建立作業(yè)控制塊（JCB，Job Control Block） ，記錄已進入系統(tǒng)的各作業(yè)的情況（類型、狀態(tài)、資源請求與分配等）；n確定調(diào)度策略與調(diào)度算法n分配資源為被選中的作業(yè)創(chuàng)建進程，并且為其申請系統(tǒng)資源；n善后處理收回作業(yè)占用的全部資源，撤銷作業(yè)控制塊以及與該作業(yè)有關(guān)的全部進程。三三. . 作業(yè)控制塊（作業(yè)控制塊（JCBJCB，Job Control BlockJob Control Block）n每個作業(yè)進入系統(tǒng)時由系統(tǒng)為其建立一個作業(yè)控 制 塊 J

5、 C B （ J o b Control Block)，它是存放作業(yè)控制和管理信息的數(shù)據(jù)結(jié)構(gòu)，是作業(yè)存在的標志，主要信息見右圖。四四. . 作業(yè)調(diào)度算法性能的衡量作業(yè)調(diào)度算法性能的衡量作業(yè)調(diào)度算法規(guī)定了從后備作業(yè)中選擇作業(yè)進入系統(tǒng)內(nèi)存的原則。1. 1. 確定調(diào)度算法時應(yīng)考慮的因素確定調(diào)度算法時應(yīng)考慮的因素(1) 應(yīng)與系統(tǒng)的整體設(shè)計目標一致(2) 考慮系統(tǒng)中各種資源的負載均勻(3) 保證作業(yè)的執(zhí)行(4) 對一些專用資源的使用特性的考慮2. 2. 調(diào)度性能的衡量調(diào)度性能的衡量通常采用平均周轉(zhuǎn)時間和帶權(quán)平均周轉(zhuǎn)時間來衡量作業(yè)調(diào)度算法性能的好壞。(1) 周轉(zhuǎn)時間周轉(zhuǎn)時間：一個作業(yè)提交給計算機系統(tǒng)到該作

6、業(yè)的結(jié)果返回給用戶所需要的時間。n定義定義： ti = tci-tsi ti：作業(yè)周轉(zhuǎn)時間tci：作業(yè)完成時間 tsi: 作業(yè)提交時間n意義意義：說明作業(yè)i在系統(tǒng)中停留的時間長短n平均周轉(zhuǎn)時間平均周轉(zhuǎn)時間：n定義定義：一個作業(yè)的周轉(zhuǎn)時間與其運行時間的比值比值n意義意義：說明作業(yè)i在系統(tǒng)中的相對相對等待時間。(3)平均帶權(quán)周轉(zhuǎn)時間平均帶權(quán)周轉(zhuǎn)時間：n精確度精確度：高于周轉(zhuǎn)時間和平均周轉(zhuǎn)時間另外，還可以用CPU的利用率和吞吐量來衡量。五五. . 作業(yè)調(diào)度算法作業(yè)調(diào)度算法1. 1. 先來先服務(wù)調(diào)度算法先來先服務(wù)調(diào)度算法(FCFS)(FCFS)：n策略策略：作業(yè)來到的先后次序來到的先后次序進行調(diào)度n特

7、點特點：每次選擇的作業(yè)是等待時間最久的，而不管作業(yè)運行時間的長短。這種調(diào)度算法突出的優(yōu)點是實現(xiàn)簡單實現(xiàn)簡單，效率較低效率較低，在一些實際的系統(tǒng)和一般應(yīng)用程序中采用這種算法的較多。2. 2. 短作業(yè)優(yōu)先調(diào)度算法短作業(yè)優(yōu)先調(diào)度算法n策略策略：考慮作業(yè)的運行時間，每次總是選擇一個請求運行時間最小運行時間最小的作業(yè)調(diào)入內(nèi)存（系統(tǒng)） 。n特點特點：易實現(xiàn)，系統(tǒng)吞吐量高。只考慮短作業(yè)，而沒有考慮長作業(yè)的利益。相對先來先服務(wù)調(diào)度算法實現(xiàn)要困難些，如果作業(yè)的到來順序及運行時間不合適，會出現(xiàn)餓死餓死現(xiàn)象。3. 3. 響應(yīng)比高者優(yōu)先調(diào)度算法響應(yīng)比高者優(yōu)先調(diào)度算法響應(yīng)比高者優(yōu)先調(diào)度算法是介于這兩種算法之間的一種折衷

8、的算法。響應(yīng)比 響應(yīng)時間 / 執(zhí)行時間 1 等待時間 / 執(zhí)行時間一個作業(yè)時，計算后備作業(yè)表中每個作業(yè)的響應(yīng)比，挑選響應(yīng)比高者投入運行。這種算法從理論上講是比較完備的，但作業(yè)調(diào)度程序要統(tǒng)計作業(yè)的等待時間，使用用戶的估計的運行時間，并要作浮點運算（這是系統(tǒng)程序最忌諱的）浪費大量的計算時間，這是系統(tǒng)程序所不允許的。4. 4. 優(yōu)先數(shù)調(diào)度算法優(yōu)先數(shù)調(diào)度算法優(yōu)先數(shù)調(diào)度算法綜合考慮各方面的因素（作業(yè)等待時間、運行時間、緩急程度，系統(tǒng)資源使用等），給每個作業(yè)設(shè)置一個優(yōu)先數(shù)，調(diào)度程序總是選擇一個優(yōu)先數(shù)最大（或者最?。┑淖鳂I(yè)調(diào)入（系統(tǒng)）內(nèi)存。這種算法實現(xiàn)的困難在于如何終合考慮，這些因素之間的關(guān)系怎樣處理。5.

9、 5. 均衡調(diào)度算法均衡調(diào)度算法均衡調(diào)度算法是一種更為理想化的調(diào)度算法，如何實現(xiàn)更困難，并且算法本身的開銷有時會遠遠大于先來先服務(wù)和小作業(yè)優(yōu)先調(diào)度算法的不足，這也是這兩種算法被眾多系統(tǒng)采用的最根本的原因。UnixUnix調(diào)度算法調(diào)度算法nUNIX系統(tǒng)采用優(yōu)先數(shù)調(diào)度算法優(yōu)先數(shù)調(diào)度算法n進程有一個進程優(yōu)先數(shù)p_prip_prinp_pri取值范圍是127127，其值越小，進程的優(yōu)先級越高1. 1. 優(yōu)先數(shù)的確定優(yōu)先數(shù)的確定n進入睡眠狀態(tài)設(shè)置優(yōu)先數(shù)0進程（100優(yōu)先數(shù)）；資源請求得不到滿足的進程，磁盤（80），打印機（20），；等待塊設(shè)備I/O完成的進程(50)；等待字符設(shè)備I/O完成的進程(020

10、）；所有處于用戶態(tài)運行進程同步（一般情況下為大于100）。目的目的 充分利用系統(tǒng)資源，即提高系統(tǒng)資源的使用效率2. 2. 優(yōu)先數(shù)的計算優(yōu)先數(shù)的計算（1）計算公式：p_pri = min127, (p_cpu/16+p_nice+PUSER)其中：p_cpu 進程占用CPU的程度R1: R1=Tu/(Tu+Tnu)Tu:進程創(chuàng)建后占用CPU的累計值Tnu：進程生成后沒有占用CPU的累計值p_nice 用戶通過系統(tǒng)調(diào)用nice(priority)設(shè)置的進程優(yōu)先數(shù)。PUSER 常數(shù)，其值為100大量的統(tǒng)計工作，并且要做浮點運算UINXUINX系統(tǒng)中對系統(tǒng)中對p_cpup_cpu的處理：的處理：每個時

11、鐘中斷當前占用處理機的進程的 p_cpu+; 每秒鐘（時鐘中斷）（對所有進程）： if(p_cpu-SCHMAG 0處理機調(diào)度處理機調(diào)度switch（）（）保護現(xiàn)場、形成調(diào)用中斷處理程序的參數(shù)調(diào)具體中斷處理程序中斷返回NNY YNNY Y防止優(yōu)先級反轉(zhuǎn)，強迫調(diào)度runrun標志大于0是說明系統(tǒng)中處于就緒狀態(tài)的進程的優(yōu)先級高于現(xiàn)運行進程的優(yōu)先級，這時要進行強迫調(diào)度。兩種可能（調(diào)度時機）： 睡眠進程喚醒后； 重新計算進程的優(yōu)先數(shù)后(包括當一個進程占用一段時間的CPU后，它的優(yōu)先級要降低)。四四. . 調(diào)度用的進程狀態(tài)變遷圖調(diào)度用的進程狀態(tài)變遷圖右圖中新創(chuàng)建的進程進入低優(yōu)就緒狀態(tài)，一個運行進程因時間

12、片到（實際上是計算量大的進程）而轉(zhuǎn)換成低優(yōu)就緒；進程因等待I/O完成而轉(zhuǎn)換高優(yōu)就緒.通過進程調(diào)度變遷圖，可反映系統(tǒng)的進程調(diào)度的各種特征。1. 1. 隊列結(jié)構(gòu)隊列結(jié)構(gòu)nI/O等待對列一個進程如果請求I/O，則進入I/O等待隊列；n低優(yōu)先就緒隊列一個進程如果在運行中超過了分配給它的時間片，就進入低優(yōu)先就緒n高優(yōu)先就緒隊列當進程從等待狀態(tài)變?yōu)榫途w狀態(tài)時，則進入高優(yōu)先就緒隊列。2. 2. 進程調(diào)度算法進程調(diào)度算法n當CPU空閑時，若高優(yōu)先就緒隊列非空，則從高優(yōu)先就緒隊列中選擇一個進程運行，分配時間片為100ms。n當CPU空閑時，若高優(yōu)先就緒隊列為空，則從低優(yōu)先就緒隊列中選擇一個進程運行，分配時間片為

13、500ms。優(yōu)先調(diào)度與時間片調(diào)度相結(jié)合的調(diào)度策略優(yōu)先調(diào)度與時間片調(diào)度相結(jié)合的調(diào)度策略3. 3. 調(diào)度效果調(diào)度效果優(yōu)先照顧了I/O量大的進程；適當照顧了計算量大的進程。五五. . 進程調(diào)度算法進程調(diào)度算法1. 進程優(yōu)先數(shù)調(diào)度算法進程優(yōu)先數(shù)調(diào)度算法是目前操作系統(tǒng)廣泛采用的一種進程調(diào)度算法，這種算法按照某種原則由系統(tǒng)（或用戶、或系統(tǒng)與用戶結(jié)合）賦予每個進程一個優(yōu)先數(shù)，在處理機空閑時，進程調(diào)度程序就從就緒進程中選擇一個優(yōu)先數(shù)最大（或者最?。┑倪M程占用CPU（該進程就從就緒狀態(tài)轉(zhuǎn)換成運行狀態(tài)）。 采用這種調(diào)度算法的關(guān)鍵是如何確定進程的優(yōu)先數(shù)、一個進程的優(yōu)先數(shù)確定之后是固定的，還是隨著該進程運行的情況的變

14、化而變化。n靜態(tài)：n進程的優(yōu)先數(shù)在進程創(chuàng)建時確定后就不再變化n確定進程優(yōu)先數(shù)：系統(tǒng)確定系統(tǒng)確定：（運行時間、使用資源，進程的類型）用戶確定用戶確定：（緊迫程度，計費與進程優(yōu)先數(shù)有關(guān)）系統(tǒng)與用戶結(jié)合（用戶可以為本用戶的進程設(shè)置優(yōu)先數(shù)，但不是作調(diào)度用，系統(tǒng)還要根據(jù)系統(tǒng)情況把用戶設(shè)置的進程優(yōu)先數(shù)作為確定進程優(yōu)先數(shù)的一個參數(shù)）n動態(tài)動態(tài)：系統(tǒng)在運行的過程中，根據(jù)系統(tǒng)的設(shè)計目標，不斷地調(diào)整進程的優(yōu)先數(shù)，這種方法的優(yōu)點是能比較客觀地反映進程的實際情況和保證達到系統(tǒng)設(shè)計目標2. 循環(huán)輪轉(zhuǎn)調(diào)度算法循環(huán)輪轉(zhuǎn)調(diào)度算法循環(huán)輪轉(zhuǎn)調(diào)度實際上是一種先來先服務(wù)算法的調(diào)度算法，它把系統(tǒng)的響應(yīng)時間分成大小相等（或不相等）的時間單位，稱為時間片。每個進程被調(diào)度到后，占用一個時間片，片用完后，該進程讓出CPU，由運行狀態(tài)轉(zhuǎn)換成就緒狀態(tài)，排在就緒隊列的隊尾。多個進程循環(huán)輪轉(zhuǎn)。簡單循環(huán)輪轉(zhuǎn)調(diào)度n 實現(xiàn)簡單、系統(tǒng)開銷小。n 不靈活，當系統(tǒng)中進程較多時，系統(tǒng)開銷變大。n 可變時間片輪轉(zhuǎn)調(diào)度n時間片的大小可變，系統(tǒng)可根據(jù)系統(tǒng)中當前的進程數(shù)來確定時間片的大小。例：Q=T/NnT：系統(tǒng)響應(yīng)時間，一般為1秒，具體大小由系統(tǒng)設(shè)計時根據(jù)系統(tǒng)設(shè)計目標確定。nN：系統(tǒng)中進程的個數(shù)，也由系統(tǒng)設(shè)計時確定，或者通過系統(tǒng)配