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

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

3、制塊JCB(Job Control Block) 存放作業(yè)控制和管理信息 作業(yè)存在的標(biāo)志,四. 作業(yè)調(diào)度算法性能的衡量,作業(yè)調(diào)度算法規(guī)定從后備作業(yè)中選擇作業(yè)進(jìn)入系統(tǒng)內(nèi)存的原則。 1. 確定調(diào)度算法時(shí)應(yīng)考慮的因素 (1) 與系統(tǒng)的整體設(shè)計(jì)目標(biāo)一致 (2) 考慮系統(tǒng)中各種資源的負(fù)載均勻 (3) 保證作業(yè)的執(zhí)行 (4) 對(duì)一些專用資源的使用特性的考慮,面向用戶：周轉(zhuǎn)時(shí)間、響應(yīng)時(shí)間、截止時(shí)間 面向系統(tǒng)：吞吐量、利用率、設(shè)備的均衡利用 調(diào)度算法：易于實(shí)現(xiàn)、執(zhí)行開銷,2. 調(diào)度性能的衡量,通常采用平均周轉(zhuǎn)時(shí)間和帶權(quán)平均周轉(zhuǎn)時(shí)間來(lái)衡量作業(yè)調(diào)度算法性能的好壞。 (1) 周轉(zhuǎn)時(shí)間： 一個(gè)作業(yè)提交給計(jì)算機(jī)系統(tǒng)到該

4、作業(yè)的結(jié)果返回給用戶所需要的時(shí)間。 定義： ti = tci-tsi ti ：作業(yè)周轉(zhuǎn)時(shí)間 tci：作業(yè)完成時(shí)間 tsi: 作業(yè)提交時(shí)間 意義：說(shuō)明作業(yè)i在系統(tǒng)中停留的時(shí)間長(zhǎng)短 平均周轉(zhuǎn)時(shí)間：,(2) 帶權(quán)周轉(zhuǎn)時(shí)間,定義：一個(gè)作業(yè)的周轉(zhuǎn)時(shí)間與其運(yùn)行時(shí)間的比值 意義：說(shuō)明作業(yè)i在系統(tǒng)中的相對(duì)等待時(shí)間 (3)平均帶權(quán)周轉(zhuǎn)時(shí)間： 精確度：高于周轉(zhuǎn)時(shí)間和平均周轉(zhuǎn)時(shí)間,五. 作業(yè)調(diào)度算法,1. 先來(lái)先服務(wù)調(diào)度算法(FCFS)： 策略： 按照作業(yè)來(lái)到的先后次序進(jìn)行調(diào)度 特點(diǎn)： 每次選擇等待時(shí)間最久的作業(yè)，而不考慮作業(yè)運(yùn)行時(shí)間的長(zhǎng)短 實(shí)現(xiàn)簡(jiǎn)單，效率較低，在一些實(shí)際的系統(tǒng)和一般應(yīng)用程序中應(yīng)用較多,2. 短作業(yè)

5、優(yōu)先調(diào)度算法,策略： 考慮作業(yè)的運(yùn)行時(shí)間，每次總選擇一個(gè)請(qǐng)求運(yùn)行時(shí)間最小的作業(yè)調(diào)入內(nèi)存（系統(tǒng)） 。 特點(diǎn)： 易實(shí)現(xiàn)，系統(tǒng)吞吐量高 只考慮短作業(yè)，而沒(méi)有考慮長(zhǎng)作業(yè)的利益 相對(duì)先來(lái)先服務(wù)調(diào)度算法實(shí)現(xiàn)要困難些，如果作業(yè)的到來(lái)順序及運(yùn)行時(shí)間不合適，會(huì)出現(xiàn)餓死現(xiàn)象,討論在兩種調(diào)度算法下的周轉(zhuǎn)時(shí)間與帶權(quán)周轉(zhuǎn)時(shí)間,3. 響應(yīng)比高者優(yōu)先調(diào)度算法,介于這兩種算法之間的一種折衷的算法。 響應(yīng)比 響應(yīng)時(shí)間 / 執(zhí)行時(shí)間 1 等待時(shí)間 / 執(zhí)行時(shí)間 每調(diào)度一個(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)算（這是

6、系統(tǒng)程序最忌諱的）浪費(fèi)大量的計(jì)算時(shí)間，這是系統(tǒng)程序不允許的。,4. 優(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)存。 困難在于如何綜合考慮，這些因素之間的關(guān)系如何處理。,5. 均衡調(diào)度算法,一種更為理想化的調(diào)度算法，如何實(shí)現(xiàn)更困難，并且算法本身的開銷有時(shí)會(huì)遠(yuǎn)遠(yuǎn)大于先來(lái)先服務(wù)和小作業(yè)優(yōu)先調(diào)度算法的不足，這也是這兩種算法被眾多系統(tǒng)采用的最根本的原因。,(三) 進(jìn)程調(diào)度,一. 調(diào)度/分派結(jié)構(gòu) 處理機(jī)分配由調(diào)度和分派兩個(gè)功能組成。 1. 調(diào)度： 組織和維護(hù)就緒進(jìn)程隊(duì)列。

7、包括確定調(diào)度算法、按調(diào)度算法組織和維護(hù)就緒進(jìn)程隊(duì)列。（按調(diào)度原則選擇進(jìn)程） 2. 分派： 當(dāng)處理機(jī)空閑時(shí)，從就緒隊(duì)列隊(duì)首中移一個(gè)PCB，并將該進(jìn)程投入運(yùn)行。 （賦予使用處理機(jī)的權(quán)限）,二. 進(jìn)程調(diào)度的功能,1. 記錄和保持系統(tǒng)中所有進(jìn)程的有關(guān)情況和狀態(tài)特征 2. 決定分配（處理機(jī)）策略 調(diào)度策略的不同，組織就緒進(jìn)程隊(duì)列的方式也不同。 先來(lái)先服務(wù)調(diào)度：就緒進(jìn)程按等待時(shí)間大小的順序排隊(duì) 優(yōu)先數(shù)調(diào)度：就緒進(jìn)程按優(yōu)先數(shù)的先后次序排隊(duì) 3. 實(shí)施處理機(jī)的分配和回收 總而言之，進(jìn)程調(diào)度包括： 調(diào)度算法的選擇（調(diào)度算法） 調(diào)度時(shí)機(jī)的選擇（調(diào)度時(shí)機(jī)） 實(shí)施進(jìn)程調(diào)度（調(diào)度程序）,三. 進(jìn)程調(diào)度方式,非剝奪方式

8、優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單，系統(tǒng)開銷小 缺點(diǎn)：難以滿足緊急任務(wù)的要求 剝奪方式 優(yōu)點(diǎn)：及時(shí)響應(yīng)緊急任務(wù) 缺點(diǎn)：增加了系統(tǒng)開銷 實(shí)現(xiàn)中還可采用選擇可搶占策略。,四. 進(jìn)程調(diào)度算法,1. 進(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)行的情況的變化而變化。,靜態(tài)： 進(jìn)程的優(yōu)先數(shù)在進(jìn)程創(chuàng)建時(shí)確定后就不再變化 確定

9、進(jìn)程優(yōu)先數(shù)： 系統(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ù)） 動(dòng)態(tài)： 系統(tǒng)運(yùn)行過(guò)程中，根據(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)度算法,系統(tǒng)的響應(yīng)時(shí)間分成大小相等（或不等）的時(shí)間片。每個(gè)進(jìn)程被調(diào)度到后，占用一個(gè)時(shí)間片，時(shí)間片用完后，該進(jìn)程讓出CPU，排在就緒隊(duì)列的隊(duì)尾。多個(gè)進(jìn)程循環(huán)輪轉(zhuǎn)。 T(響應(yīng)時(shí)間)=N(進(jìn)程數(shù)目)*q(時(shí)間片),

10、簡(jiǎn)單循環(huán)輪轉(zhuǎn)調(diào)度 實(shí)現(xiàn)簡(jiǎn)單、系統(tǒng)開銷小 不靈活，當(dāng)系統(tǒng)中進(jìn)程較多時(shí)，系統(tǒng)開銷變大 可變時(shí)間片輪轉(zhuǎn)調(diào)度 根據(jù)系統(tǒng)當(dāng)前的進(jìn)程數(shù)動(dòng)態(tài)確定時(shí)間片的大小,3. 多級(jí)反饋算法,多個(gè)簡(jiǎn)單算法的綜合和發(fā)展,五. 調(diào)度用的進(jìn)程狀態(tài)變遷圖,通過(guò)進(jìn)程調(diào)度變遷圖，可反映系統(tǒng)進(jìn)程調(diào)度的各種特征。,1. 隊(duì)列結(jié)構(gòu),I/O等待對(duì)列 進(jìn)程如果請(qǐng)求I/O，則進(jìn)入I/O等待隊(duì)列 低優(yōu)先就緒隊(duì)列 進(jìn)程如果在運(yùn)行中超過(guò)了分配給它的時(shí)間片，就進(jìn)入低優(yōu)先就緒 高優(yōu)先就緒隊(duì)列 進(jìn)程從等待狀態(tài)變?yōu)榫途w狀態(tài)時(shí)，進(jìn)入高優(yōu)先就緒隊(duì)列,2. 進(jìn)程調(diào)度算法,當(dāng)CPU空閑時(shí)，若高優(yōu)先就緒隊(duì)列非空，則從高優(yōu)先就緒隊(duì)列中選擇一個(gè)進(jìn)程運(yùn)行，分配時(shí)間片為100

11、ms。 當(dāng)CPU空閑時(shí)，若高優(yōu)先就緒隊(duì)列為空，則從低優(yōu)先就緒隊(duì)列中選擇一個(gè)進(jìn)程運(yùn)行，分配時(shí)間片為500ms。 優(yōu)先調(diào)度與時(shí)間片調(diào)度相結(jié)合的調(diào)度策略 3. 調(diào)度效果 優(yōu)先照顧了I/O量大的進(jìn)程； 適當(dāng)照顧了計(jì)算量大的進(jìn)程。,Unix調(diào)度算法,UNIX系統(tǒng)采用優(yōu)先數(shù)調(diào)度算法 進(jìn)程有一個(gè)進(jìn)程優(yōu)先數(shù)p_pri p_pri取值范圍是127127，其值越小，進(jìn)程的優(yōu)先級(jí)越高,1. 優(yōu)先數(shù)的確定,進(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）； 所有處于用戶態(tài)運(yùn)行進(jìn)程同

12、步（一般情況下為大于100）。,目的 充分利用系統(tǒng)資源，即提高系統(tǒng)資源的使用效率,2. 優(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)程生成后沒(méi)有占用CPU的累計(jì)值 p_nice 用戶通過(guò)系統(tǒng)調(diào)用nice(priority)設(shè)置的進(jìn)程優(yōu)先數(shù)。 PUSER 常數(shù)，其值為100,大量的統(tǒng)計(jì)工作，并且要做浮點(diǎn)運(yùn)算,UINX系統(tǒng)中對(duì)p_cpu的處理：,每個(gè)時(shí)鐘中斷當(dāng)前占用處理機(jī)的進(jìn)程的 p_cpu+; 每秒鐘（時(shí)鐘中斷）（對(duì)所有進(jìn)程）： p_cpu=p_cpu-10; if(p_cpu-SCHMAG 0 ) p_cpu = 0; 其中：SCHMAG 調(diào)度魔數(shù)10,這種負(fù)反饋的效果使得系統(tǒng)中在用戶態(tài)下運(yùn)行的進(jìn)程能均衡地得到處理機(jī),