操作系統(tǒng)教程4版1-2章ch22.72.8處理器調(diào)度

1、2.7處理機(jī)調(diào)度2.7.1 處理機(jī)調(diào)度的層次2.7.2 選擇調(diào)度算法的原則2.7.3 作業(yè)和進(jìn)程的關(guān)系2.7.4 作業(yè)的管理與調(diào)度2.7.1 處理機(jī)調(diào)度的層次 作業(yè)從進(jìn)入系統(tǒng)成為后備作業(yè)開始，直到運(yùn)行結(jié)束退出系統(tǒng)為止，需經(jīng)歷不同級別的調(diào)度。 高級調(diào)度 中級調(diào)度 低級調(diào)度處理器三級調(diào)度模型處理器低級調(diào)度高級調(diào)度完成超時(shí)掛起就緒隊(duì)列掛起等待隊(duì)列等待隊(duì)列就緒隊(duì)列等待事件交互式用戶事件出現(xiàn)后備作業(yè)隊(duì)列中級調(diào)度處理器兩級調(diào)度模型等待事件事件發(fā)生進(jìn)程完成后備作業(yè)隊(duì)列 就緒 隊(duì)列高級調(diào)度低級調(diào)度 等待 隊(duì)列CPU時(shí)間片完2.7.2 選擇調(diào)度算法的原則(1) l資源利用率 CPU利用率= CPU有效工作時(shí)間/

2、CPU總的運(yùn)行時(shí)間， CPU總的運(yùn)行時(shí)間=CPU有效工作時(shí)間+CPU空閑等待時(shí)間。 選擇調(diào)度算法的原則(2) 2響應(yīng)時(shí)間 交互式進(jìn)程從提交一個(gè)請求(命令)到接收到響應(yīng)之間的時(shí)間間隔稱響應(yīng)時(shí)間。 使交互式用戶的響應(yīng)時(shí)間盡可能短，或盡快處理實(shí)時(shí)任務(wù)。 這是分時(shí)系統(tǒng)和實(shí)時(shí)系統(tǒng)衡量調(diào)度性能的一個(gè)重要指標(biāo)。選擇調(diào)度算法的原則(3) 3周轉(zhuǎn)時(shí)間批處理用戶從作業(yè)提交給系統(tǒng)開始，到作業(yè)完成為止的時(shí)間間隔稱作業(yè)周轉(zhuǎn)時(shí)間，應(yīng)使作業(yè)周轉(zhuǎn)時(shí)間或平均作業(yè)周轉(zhuǎn)時(shí)間盡可能短。這是批處理系統(tǒng)衡量調(diào)度性能的一個(gè)重要指標(biāo)。 選擇調(diào)度算法的原則(4) 4吞吐率單位時(shí)間內(nèi)處理的作業(yè)數(shù)。 5公平性確保每個(gè)用戶每個(gè)進(jìn)程獲得合理的CPU份

3、額或其他資源份額，不會(huì)出現(xiàn)餓死情況。 作業(yè)周轉(zhuǎn)與平均周轉(zhuǎn)時(shí)間如果作業(yè)i提交給系統(tǒng)的時(shí)刻是ts，完成時(shí)刻是tf，該作業(yè)的周轉(zhuǎn)時(shí)間ti為：ti = tf - ts 實(shí)際上，它是作業(yè)在系統(tǒng)里的等待時(shí)間與運(yùn)行時(shí)間之和。平均作業(yè)周轉(zhuǎn)時(shí)間 T = (ti) / n為了提高系統(tǒng)的性能，要讓若干個(gè)用戶的平均作業(yè)周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間最小。 作業(yè)帶權(quán)周轉(zhuǎn)時(shí)間和平均作業(yè)帶權(quán)周轉(zhuǎn)時(shí)間如果作業(yè)i的周轉(zhuǎn)時(shí)間為ti，所需運(yùn)行時(shí)間為tk，則稱wi=ti /tk為該作業(yè)的帶權(quán)周轉(zhuǎn)時(shí)間。ti是等待時(shí)間與運(yùn)行時(shí)間之和，故帶權(quán)周轉(zhuǎn)時(shí)間總大于1。 平均作業(yè)帶權(quán)周轉(zhuǎn)時(shí)間W = (wi) / n2.7.3 作業(yè)和進(jìn)程的關(guān)系作業(yè)管理任

4、務(wù)： 一、作業(yè)組織； 二、作業(yè)調(diào)度； 三、運(yùn)行控制。作業(yè)和進(jìn)程的關(guān)系 作業(yè)(JOB) ， 作業(yè)步(Job Step)， 作業(yè)組織， 作業(yè)的提交、收容、執(zhí)行和完成。作業(yè)是任務(wù)實(shí)體，進(jìn)程是完成任務(wù)的執(zhí)行實(shí)體；沒有作業(yè)任務(wù)，進(jìn)程無事可干，沒有進(jìn)程，作業(yè)任務(wù)沒法完成。作業(yè)概念更多地用在批處理操作系統(tǒng)，而進(jìn)程則可以用在各種多道程序設(shè)計(jì)系統(tǒng)。2.7.4 作業(yè)組織、調(diào)度和控制1.批作業(yè)的組織和管理1)批作業(yè)的輸入2)批作業(yè)的建立作業(yè)控制語言作業(yè)說明書作業(yè)控制塊 作業(yè)控制塊多道批處理操作系統(tǒng)具有獨(dú)立的作業(yè)管理模塊，必須像進(jìn)程管理一樣為每一個(gè)作業(yè)建立作業(yè)控制塊（JCB）。JCB通常是在批作業(yè)進(jìn)入系統(tǒng)時(shí)，由Spo

5、oling系統(tǒng)建立的，它是作業(yè)存在于系統(tǒng)的標(biāo)志，作業(yè)撤離時(shí)，JCB也被撤銷。 JCB的主要內(nèi)容包括： (1)作業(yè)情況 (2)資源需求 (3)資源使用情況作業(yè)生命周期狀態(tài)輸入狀態(tài)：后備狀態(tài)：執(zhí)行狀態(tài)：完成狀態(tài)：批作業(yè)的調(diào)度(1) 選擇作業(yè)： (2) 分配資源： (3) 創(chuàng)建進(jìn)程： (4) 作業(yè)控制：(5) 后續(xù)處理： 作業(yè)調(diào)度與進(jìn)程調(diào)度的關(guān)系 進(jìn)程調(diào)度運(yùn)行就緒等待輸入狀態(tài)后備狀態(tài)完成狀態(tài)預(yù)輸入完成作業(yè)控制作業(yè)調(diào)度(選中并創(chuàng)建進(jìn)程)作業(yè)調(diào)度(作業(yè)終止并撤離)SPOOLing作業(yè)預(yù)輸入SPOOLing作業(yè)緩輸出2.交互作業(yè)的組織和管理分時(shí)系統(tǒng)的作業(yè)就是用戶的一次上機(jī)交互過程，可認(rèn)為終端進(jìn)程的創(chuàng)建是一

6、個(gè)交互型作業(yè)的開始，退出命令運(yùn)行結(jié)束代表用戶交互型作業(yè)的中止。交互作業(yè)的情況和資源需求通過操作命令告知系統(tǒng)，分時(shí)用戶逐條輸入命令，即提交作業(yè)(步)和控制作業(yè)運(yùn)行，系統(tǒng)則逐條執(zhí)行并給出應(yīng)答，每鍵入一條或一組有關(guān)操作命令，便在系統(tǒng)內(nèi)部創(chuàng)建一個(gè)進(jìn)程或若干進(jìn)程來完成相應(yīng)命令。鍵盤命令有：作業(yè)控制類；資源申請類；文件操作類；目錄操作類；設(shè)備控制類等。2.8處理器調(diào)度算法2.8.1 低級調(diào)度的功能和類型2.8.2 作業(yè)調(diào)度和低級調(diào)度算法2.8.3 實(shí)時(shí)調(diào)度算法2.8.4 多處理機(jī)調(diào)度算法 2.8.1 低級調(diào)度的功能和類型1 低級調(diào)度的主要功能 調(diào)度程序兩項(xiàng)任務(wù)：調(diào)度和分派。 調(diào)度實(shí)現(xiàn)調(diào)度策略，確定就緒進(jìn)程

7、/線程競爭使用處理器的次序的裁決原則，即進(jìn)程/線程何時(shí)應(yīng)放棄CPU和選擇哪個(gè)來執(zhí)行； 分派實(shí)現(xiàn)調(diào)度機(jī)制，確定如何時(shí)分復(fù)用CPU，處理上下文交換細(xì)節(jié)，完成進(jìn)程/線程和CPU的綁定和放棄的實(shí)際工作。調(diào)度機(jī)制邏輯功能程序模塊組成 隊(duì)列管理程序：上下文切換程序：分派程序：2 低級調(diào)度的基本類型第一類稱剝奪式： 兩種處理器剝奪原則， 一是高優(yōu)先級進(jìn)程/線程可剝奪低優(yōu)先級進(jìn)程/線程， 二是當(dāng)運(yùn)行進(jìn)程/線程時(shí)間片用完后被剝奪。第二類稱非剝奪式： 2.8.2 作業(yè)調(diào)度和低級調(diào)度算法1先來先服務(wù)算法3個(gè)作業(yè)同時(shí)到達(dá)系統(tǒng)并立即進(jìn)入調(diào)度，作業(yè)名/所需CPU時(shí)間:作業(yè)1/28，作業(yè)2/9，作業(yè)3/3。采用FCFS算法

8、，平均作業(yè)周轉(zhuǎn)時(shí)間為35。 FCFS調(diào)度算法的平均作業(yè)周轉(zhuǎn)時(shí)間與作業(yè)提交的順序有關(guān)。 若3個(gè)作業(yè)提交順序改為作業(yè)2、1、3，平均作業(yè)周轉(zhuǎn)時(shí)間約為29。若3個(gè)作業(yè)提交順序改為作業(yè)3、2、1，平均作業(yè)周轉(zhuǎn)時(shí)間約為18。 2最短作業(yè)優(yōu)先算法(1)SJF算法以進(jìn)入系統(tǒng)的作業(yè)所要求的CPU時(shí)間為標(biāo)準(zhǔn)，總選取估計(jì)計(jì)算時(shí)間最短的作業(yè)投入運(yùn)行。算法易于實(shí)現(xiàn)，效率不高，主要弱點(diǎn)是忽視了作業(yè)等待時(shí)間。會(huì)出現(xiàn)饑餓現(xiàn)象。SJF的平均作業(yè)周轉(zhuǎn)時(shí)間比FCFS要小，故它的調(diào)度性能比FCFS好。實(shí)現(xiàn)SJF調(diào)度算法需要知道作業(yè)所需運(yùn)行時(shí)間，否則調(diào)度就沒有依據(jù)，要精確知道一個(gè)作業(yè)的運(yùn)行時(shí)間是辦不到的。最短作業(yè)優(yōu)先算法(2)4個(gè)作

9、業(yè)同時(shí)到達(dá)系統(tǒng)并進(jìn)入調(diào)度： 作業(yè)名/所需CPU時(shí)間:作業(yè)1/9，作業(yè)2/4，作業(yè)3/10，作業(yè)4/8。SJF作業(yè)調(diào)度順序?yàn)樽鳂I(yè)2、4、1、3， 平均作業(yè)周轉(zhuǎn)時(shí)間T = 17，平均帶權(quán)作業(yè)周轉(zhuǎn)時(shí)間W= 1.98。如果施行FCFS調(diào)度算法，平均作業(yè)周轉(zhuǎn)時(shí)間T =19，平均帶權(quán)作業(yè)周轉(zhuǎn)時(shí)間 W = 2.61。3最短剩余時(shí)間優(yōu)先算法(1)SRTF把SJF算法改為搶占式的。一個(gè)新作業(yè)進(jìn)入就緒狀態(tài)，如果新作業(yè)需要的CPU時(shí)間比當(dāng)前正在執(zhí)行的作業(yè)剩余下來還需的CPU時(shí)間短，SRTF強(qiáng)行趕走當(dāng)前正在執(zhí)行作業(yè)。稱最短剩余時(shí)間優(yōu)先算法此算法不但適用于JOB調(diào)度，同樣也適用于進(jìn)程調(diào)度。最短剩余時(shí)間優(yōu)先算法(2)4個(gè)

10、作業(yè)其到達(dá)系統(tǒng)/所需CPU時(shí)間如下：Job1-0/8，Job2-1/4， Job3- 2/ 9，Job4-3/5。SRTF調(diào)度平均等待時(shí)間=6.5 (10-1)+(1-1)+(17-2)+(5-3) /4 平均周轉(zhuǎn)時(shí)間=13SJF平均等待時(shí)間=7.75 平均周轉(zhuǎn)時(shí)間=14.25J1 J2 J4 J1 J30151017264響應(yīng)比最高者優(yōu)先算法FCFS與SJF是片面的調(diào)度算法。FCFS只考慮作業(yè)等候時(shí)間而忽視了作業(yè)的計(jì)算時(shí)問，SJF只考慮用戶估計(jì)的作業(yè)計(jì)算時(shí)間而忽視了作業(yè)等待時(shí)間。HRRF是介乎這兩者之間的折衷算法，既考慮作業(yè)等待時(shí)間，又考慮作業(yè)的運(yùn)行時(shí)間，既照顧短作業(yè)又不使長作業(yè)的等待時(shí)間過

11、長，改進(jìn)了調(diào)度性能。 響應(yīng)比定義 響應(yīng)比 1+已等待時(shí)間/估計(jì)運(yùn)行時(shí)間 短作業(yè)容易得到較高響應(yīng)比， 長作業(yè)等待時(shí)間足夠長后，也將獲得足夠高的響應(yīng)比， 饑餓現(xiàn)象不會(huì)發(fā)生。HRRF算法舉例 4個(gè)作業(yè)到達(dá)系統(tǒng)時(shí)間/所需CPU時(shí)間:作業(yè)1-0/20，作業(yè)2-5/15，作業(yè)3-10 /5，作業(yè)4- 15/ 10。SJF調(diào)度順序?yàn)樽鳂I(yè)1、3、4、2，平均作業(yè)周轉(zhuǎn)時(shí)間T=25， 平均帶權(quán)作業(yè)周轉(zhuǎn)時(shí)間W=2.25 。FCFS調(diào)度順序?yàn)樽鳂I(yè)1、2、3、4，平均作業(yè)周轉(zhuǎn)時(shí)間T=28.75， 平均帶權(quán)作業(yè)周轉(zhuǎn)時(shí)間W=3.125 。HRRF調(diào)度順序?yàn)樽鳂I(yè)1、3、2、4，平均作業(yè)周轉(zhuǎn)時(shí)間T=26.25， 平均帶權(quán)作業(yè)周

12、轉(zhuǎn)時(shí)間W=2.46 。5 優(yōu)先級調(diào)度算法(1) 靜態(tài)優(yōu)先數(shù)法使用外圍設(shè)備頻繁者優(yōu)先數(shù)大，這樣有利于提高效率重要算題程序的進(jìn)程優(yōu)先數(shù)大，這樣有利于用戶交互式用戶的進(jìn)程優(yōu)先數(shù)大，這樣有利于終端用戶的響應(yīng)時(shí)間等等 優(yōu)先級調(diào)度算法(2) 動(dòng)態(tài)優(yōu)先數(shù)法根據(jù)進(jìn)程占有CPU時(shí)間多少來決定:當(dāng)進(jìn)程占有CPU時(shí)間愈長，那么，在它被阻塞之后再次獲得調(diào)度的優(yōu)先級就越低，反之，進(jìn)程獲得調(diào)度的可能性越大；根據(jù)進(jìn)程等待CPU時(shí)間多少來決定:當(dāng)進(jìn)程在就緒隊(duì)列中等待時(shí)間愈長，那么，在它被阻塞之后再次獲得調(diào)度的優(yōu)先級就越高，反之，進(jìn)程獲得調(diào)度的可能性越小。6時(shí)間片輪轉(zhuǎn)調(diào)度算法時(shí)間片調(diào)度做法是：調(diào)度程序每次把CPU分配給就緒隊(duì)列

13、首進(jìn)程使用一個(gè)時(shí)間片。例如100ms，就緒隊(duì)列中的每個(gè)進(jìn)程輪流地運(yùn)行一個(gè)時(shí)間片。當(dāng)這個(gè)時(shí)間片結(jié)束時(shí)，強(qiáng)迫一個(gè)進(jìn)程讓出處理器，讓它排列到就緒隊(duì)列的尾部，等候下一輪調(diào)度輪轉(zhuǎn)策略可防止那些很少使用外圍設(shè)備的進(jìn)程過長的占用處理器而使得要使用外圍設(shè)備的那些進(jìn)程沒有機(jī)會(huì)去啟動(dòng)外圍設(shè)備輪轉(zhuǎn)策略與間隔時(shí)鐘(時(shí)間片) 7 多級反饋隊(duì)列調(diào)度又稱反饋循環(huán)隊(duì)列或多隊(duì)列策略。主要思想是將就緒進(jìn)程分為兩級或多級，系統(tǒng)相應(yīng)建立兩個(gè)或多個(gè)就緒進(jìn)程隊(duì)列，較高優(yōu)先級的隊(duì)列一般分配給較短的時(shí)間片。處理器調(diào)度先從高級就緒進(jìn)程隊(duì)列中選取可占有處理器的進(jìn)程，只有在選不到時(shí)，才從較低級的就緒進(jìn)程隊(duì)列中選取。一個(gè)三級反饋隊(duì)列調(diào)度策略 低級就

14、緒隊(duì)列高級就緒隊(duì)列中級就緒隊(duì)列等待磁盤磁帶等待其他外設(shè)運(yùn)行選中,時(shí)間片500ms超過時(shí)間片啟動(dòng)磁盤磁帶啟動(dòng)其他外設(shè)選中,時(shí)間片200ms選中,時(shí)間片100ms8 彩票調(diào)度算法基本思想：為進(jìn)程發(fā)放針對各種資源（如CPU時(shí)間）的彩票。調(diào)度程序隨機(jī)選擇一張彩票，持有該彩票的進(jìn)程獲得系統(tǒng)資源。進(jìn)程都是平等的，有相同的運(yùn)行機(jī)會(huì)。如果某些進(jìn)程需要更多的機(jī)會(huì)，可被給予更多彩票，增加其中獎(jiǎng)機(jī)會(huì)。2.8.3 實(shí)時(shí)調(diào)度算法實(shí)時(shí)系統(tǒng)是那些時(shí)間因素非常關(guān)鍵的系統(tǒng)。實(shí)時(shí)系統(tǒng)包括監(jiān)控系統(tǒng)、自動(dòng)駕駛系統(tǒng)、安全控制系統(tǒng)等，這些系統(tǒng)中，遲到的響應(yīng)即使正確，也和沒有響應(yīng)一樣糟糕。硬實(shí)時(shí)系統(tǒng)和軟實(shí)時(shí)系統(tǒng)實(shí)時(shí)系統(tǒng)通常分為硬實(shí)時(shí)系統(tǒng)和

15、軟實(shí)時(shí)系統(tǒng)。前者意味著存在必須滿足的時(shí)間限制；后者意味著偶爾超過時(shí)間限制時(shí)可以容忍的。 周期性和非周期性事件實(shí)時(shí)系統(tǒng)響應(yīng)的事件可劃分為周期性事件和非周期性事件。例如，m個(gè)周期性事件，事件i的周期為Pi，每個(gè)事件需要Ci秒的CPU時(shí)間來處理，則只有滿足以下條件： C1/P1 + C2/P2 + + Cm/Pm 1 時(shí)，才可能處理所有的負(fù)載。滿足該條件的實(shí)時(shí)系統(tǒng)稱作任務(wù)可調(diào)度的。實(shí)時(shí)調(diào)度算法(1) 1）單比率調(diào)度算法 基本思想：為每個(gè)進(jìn)程分配一個(gè)與事件發(fā)生頻率成正比的優(yōu)先數(shù)。 例如，周期為20ms的進(jìn)程優(yōu)先數(shù)為50，周期為100ms的進(jìn)程優(yōu)先數(shù)為10，運(yùn)行時(shí)調(diào)度程序總是調(diào)度優(yōu)先數(shù)最高的就緒進(jìn)程，并

16、采取搶占式分配策略。實(shí)時(shí)調(diào)度算法(2) 2）限期調(diào)度算法 基本思想：當(dāng)一個(gè)事件發(fā)生時(shí)，對應(yīng)的進(jìn)程就按照截止期限被加入就緒進(jìn)程隊(duì)列。對于一個(gè)周期性事件，其截止期限即為事件下一次發(fā)生的時(shí)間。 該調(diào)度算法首先運(yùn)行隊(duì)首進(jìn)程，即截止時(shí)間最近的那個(gè)進(jìn)程。實(shí)時(shí)調(diào)度算法(3) 3）最少裕度法 基本思想：首先計(jì)算各個(gè)進(jìn)程的富裕時(shí)間，即裕度（laxity），然后選擇裕度最少的進(jìn)程執(zhí)行。 裕度=截止時(shí)間-(就緒時(shí)間+計(jì)算時(shí)間) 2.8.4 多處理器調(diào)度1多處理機(jī)調(diào)度的設(shè)計(jì)要點(diǎn) 1)如何為進(jìn)程分配處理機(jī) 2)在單個(gè)處理機(jī)上是否使用多道程序設(shè)計(jì)技術(shù) 3)如何實(shí)際指派進(jìn)程多處理器調(diào)度算法(1)1）負(fù)載共享調(diào)度算法基本思想

17、：進(jìn)程并不指派到特定處理機(jī)上，系統(tǒng)維護(hù)全局性進(jìn)程就緒隊(duì)列，當(dāng)處理機(jī)空閑時(shí)，就選擇進(jìn)程的一個(gè)線程去運(yùn)行。 多處理器調(diào)度算法(2)2）群調(diào)度算法 基本思想：一群相關(guān)線程基于一對一的原則，被同時(shí)調(diào)度到一組處理機(jī)上運(yùn)行。它具有的優(yōu)點(diǎn)： 當(dāng)緊密相關(guān)的進(jìn)程同時(shí)執(zhí)行時(shí)，同步造成的等待將減少，進(jìn)程切換也相應(yīng)減少，系統(tǒng)性能得到提高。 由于一次性同時(shí)調(diào)度一組處理器，調(diào)度的代價(jià)也將減少。多處理器調(diào)度算法(3)3）處理器專派調(diào)度算法基本思想：給同屬一個(gè)進(jìn)程的一組線程，同時(shí)分派到一組處理機(jī)上運(yùn)行，每個(gè)線程獲得一個(gè)處理機(jī)，且它專用于處理這個(gè)線程，直到進(jìn)程運(yùn)行結(jié)束，這是群調(diào)度的一種極端形式。 采用這一算法，處理器將不適用多道程序設(shè)計(jì)，即該應(yīng)用的一個(gè)線程阻塞后，線程對應(yīng)的處理器不會(huì)被調(diào)度給其他線程，而處于空閑狀態(tài)。多處理器調(diào)度算法(4)4）動(dòng)態(tài)調(diào)