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

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

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

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

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） ，記錄已進(jìn)入系統(tǒng)的各作業(yè)的情況（類型、狀態(tài)、資源請(qǐng)求與分配等）；n確定調(diào)度策略與調(diào)度算法n分配資源為被選中的作業(yè)創(chuàng)建進(jìn)程，并且為其申請(qǐng)系統(tǒng)資源；n善后處理收回作業(yè)占用的全部資源，撤銷作業(yè)控制塊以及與該作業(yè)有關(guān)的全部進(jìn)程。三三. . 作業(yè)控制塊（作業(yè)控制塊（JCBJCB，Job Control BlockJob Control Block）n每個(gè)作業(yè)進(jìn)入系統(tǒng)時(shí)由系統(tǒng)為其建立一個(gè)作業(yè)控 制 塊 J

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

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

7、點(diǎn)特點(diǎn)：每次選擇的作業(yè)是等待時(shí)間最久的，而不管作業(yè)運(yùn)行時(shí)間的長(zhǎng)短。這種調(diào)度算法突出的優(yōu)點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單實(shí)現(xiàn)簡(jiǎn)單，效率較低效率較低，在一些實(shí)際的系統(tǒng)和一般應(yīng)用程序中采用這種算法的較多。2. 2. 短作業(yè)優(yōu)先調(diào)度算法短作業(yè)優(yōu)先調(diào)度算法n策略策略：考慮作業(yè)的運(yùn)行時(shí)間，每次總是選擇一個(gè)請(qǐng)求運(yùn)行時(shí)間最小運(yùn)行時(shí)間最小的作業(yè)調(diào)入內(nèi)存（系統(tǒng)） 。n特點(diǎn)特點(diǎn)：易實(shí)現(xiàn)，系統(tǒng)吞吐量高。只考慮短作業(yè)，而沒有考慮長(zhǎng)作業(yè)的利益。相對(duì)先來先服務(wù)調(diào)度算法實(shí)現(xiàn)要困難些，如果作業(yè)的到來順序及運(yùn)行時(shí)間不合適，會(huì)出現(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)時(shí)間 / 執(zhí)行時(shí)間 1 等待時(shí)間 / 執(zhí)行時(shí)間一個(gè)作業(yè)時(shí)，計(jì)算后備作業(yè)表中每個(gè)作業(yè)的響應(yīng)比，挑選響應(yīng)比高者投入運(yùn)行。這種算法從理論上講是比較完備的，但作業(yè)調(diào)度程序要統(tǒng)計(jì)作業(yè)的等待時(shí)間，使用用戶的估計(jì)的運(yùn)行時(shí)間，并要作浮點(diǎn)運(yùn)算（這是系統(tǒng)程序最忌諱的）浪費(fèi)大量的計(jì)算時(shí)間，這是系統(tǒng)程序所不允許的。4. 4. 優(yōu)先數(shù)調(diào)度算法優(yōu)先數(shù)調(diào)度算法優(yōu)先數(shù)調(diào)度算法綜合考慮各方面的因素（作業(yè)等待時(shí)間、運(yùn)行時(shí)間、緩急程度，系統(tǒng)資源使用等），給每個(gè)作業(yè)設(shè)置一個(gè)優(yōu)先數(shù)，調(diào)度程序總是選擇一個(gè)優(yōu)先數(shù)最大（或者最小）的作業(yè)調(diào)入（系統(tǒng)）內(nèi)存。這種算法實(shí)現(xiàn)的困難在于如何終合考慮，這些因素之間的關(guān)系怎樣處理。5.

9、 5. 均衡調(diào)度算法均衡調(diào)度算法均衡調(diào)度算法是一種更為理想化的調(diào)度算法，如何實(shí)現(xiàn)更困難，并且算法本身的開銷有時(shí)會(huì)遠(yuǎn)遠(yuǎ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進(jìn)程有一個(gè)進(jìn)程優(yōu)先數(shù)p_prip_prinp_pri取值范圍是127127，其值越小，進(jìn)程的優(yōu)先級(jí)越高1. 1. 優(yōu)先數(shù)的確定優(yōu)先數(shù)的確定n進(jìn)入睡眠狀態(tài)設(shè)置優(yōu)先數(shù)0進(jìn)程（100優(yōu)先數(shù)）；資源請(qǐng)求得不到滿足的進(jìn)程，磁盤（80），打印機(jī)（20），；等待塊設(shè)備I/O完成的進(jìn)程(50)；等待字符設(shè)備I/O完成的進(jìn)程(020

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

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

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

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

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