四章處理機(jī)調(diào)度ppt課件

1、第四章第四章 處理機(jī)調(diào)度處理機(jī)調(diào)度第四章第四章 處置機(jī)調(diào)度處置機(jī)調(diào)度4.1 4.1 作業(yè)的概念及其形狀作業(yè)的概念及其形狀4.2 4.2 作業(yè)調(diào)度作業(yè)調(diào)度4.3 4.3 進(jìn)程調(diào)度進(jìn)程調(diào)度4.4 4.4 調(diào)度算法調(diào)度算法第四章第四章 處理機(jī)調(diào)度處理機(jī)調(diào)度4.1 .1 4.1 .1 作業(yè)與作業(yè)步作業(yè)與作業(yè)步作業(yè)作業(yè): : 就是要求計算機(jī)給以計算就是要求計算機(jī)給以計算( (或處置或處置) )的一個相對獨立的義務(wù)的一個相對獨立的義務(wù). . 也是一個相對獨立的計算義務(wù)在計算機(jī)上的執(zhí)行過程也是一個相對獨立的計算義務(wù)在計算機(jī)上的執(zhí)行過程作業(yè)步作業(yè)步: :是一個作業(yè)在執(zhí)行過程中是一個作業(yè)在執(zhí)行過程中, ,從邏輯

2、上可以細(xì)分成一個一個從邏輯上可以細(xì)分成一個一個 順序處置的根本單位順序處置的根本單位. .這個根本單位稱為作業(yè)步這個根本單位稱為作業(yè)步. .典型的作業(yè)控制過程：典型的作業(yè)控制過程： “編譯、編譯、“銜接裝配、銜接裝配、“運(yùn)轉(zhuǎn)。運(yùn)轉(zhuǎn)。4.1 4.1 作業(yè)的概念及其形狀作業(yè)的概念及其形狀第四章第四章 處理機(jī)調(diào)度處理機(jī)調(diào)度. 典型的作業(yè)步編譯編譯銜接裝配銜接裝配運(yùn)轉(zhuǎn)運(yùn)轉(zhuǎn)目的目的程序程序段段目的目的程序程序源程序源程序輸入數(shù)據(jù)輸入數(shù)據(jù)子程序子程序庫函數(shù)庫函數(shù)動態(tài)庫函數(shù)動態(tài)庫函數(shù)計算結(jié)果計算結(jié)果在作業(yè)執(zhí)行過程中，各個作業(yè)之間聯(lián)絡(luò)親密，上一作業(yè)步的執(zhí)行結(jié)果作為下一步的執(zhí)行前提。第四章第四章 處理機(jī)調(diào)度處理

3、機(jī)調(diào)度作業(yè)、作業(yè)步與進(jìn)程之間的關(guān)系用戶作業(yè)作業(yè)作業(yè)步作業(yè)步.作業(yè)進(jìn)程進(jìn)程.第四章第四章 處理機(jī)調(diào)度處理機(jī)調(diào)度4.1 .2 4.1 .2 作業(yè)控制方式作業(yè)控制方式作業(yè)的類型與組織方式作業(yè)的類型與組織方式脫機(jī)作業(yè)：是指用戶不能和計算機(jī)直接交互需求經(jīng)過操作員從中干涉的作業(yè)是指用戶不能和計算機(jī)直接交互需求經(jīng)過操作員從中干涉的作業(yè)聯(lián)機(jī)作業(yè)：是用戶經(jīng)過外圍設(shè)備直接與計算機(jī)系統(tǒng)進(jìn)展交互，并且控制造業(yè)是用戶經(jīng)過外圍設(shè)備直接與計算機(jī)系統(tǒng)進(jìn)展交互，并且控制造業(yè)的運(yùn)轉(zhuǎn)，這種作業(yè)也叫交互型作業(yè)。的運(yùn)轉(zhuǎn)，這種作業(yè)也叫交互型作業(yè)。聯(lián)機(jī)作業(yè)多出如今分時系統(tǒng)中，而脫機(jī)作業(yè)經(jīng)常出如今批處置系統(tǒng)中。聯(lián)機(jī)作業(yè)多出如今分時系統(tǒng)中，而

4、脫機(jī)作業(yè)經(jīng)常出如今批處置系統(tǒng)中。第四章第四章 處理機(jī)調(diào)度處理機(jī)調(diào)度作業(yè)的組成：程序、數(shù)據(jù)和作業(yè)闡明書程序、數(shù)據(jù)和作業(yè)闡明書作業(yè)闡明書：作業(yè)闡明書：作業(yè)根本情況描畫作業(yè)控制描畫作業(yè)資源要求描畫作業(yè)闡明書是用戶用作業(yè)控制言語編寫的。作業(yè)闡明書是用戶用作業(yè)控制言語編寫的。第四章第四章 處理機(jī)調(diào)度處理機(jī)調(diào)度4.1 .3 4.1 .3 作業(yè)的形狀作業(yè)的形狀作業(yè)在整個活動期間閱歷的四種形狀是：作業(yè)在整個活動期間閱歷的四種形狀是：提交形狀：把一個作業(yè)輸入到計算機(jī)中的一個過程。后備形狀：作業(yè)在磁盤上的后備隊列中所處的形狀。執(zhí)行形狀：把處于后備形狀的作業(yè)調(diào)入內(nèi)存的形狀。完成形狀：一個作業(yè)的主進(jìn)程執(zhí)行結(jié)果時所處的

5、形狀。第四章第四章 處理機(jī)調(diào)度處理機(jī)調(diào)度提交形狀后備形狀完成形狀運(yùn)轉(zhuǎn)形狀運(yùn)轉(zhuǎn)就緒等待作業(yè)調(diào)度Spooling作業(yè)的形狀及轉(zhuǎn)換第四章第四章 處理機(jī)調(diào)度處理機(jī)調(diào)度4.1 .4 4.1 .4 作業(yè)控制塊作業(yè)控制塊JCB)JCB)l作業(yè)控制塊JCB：Job Control Blockl 用以標(biāo)識作業(yè)的存在，記錄了與該作業(yè)有關(guān)的信息，其具l 體內(nèi)容根據(jù)作業(yè)調(diào)度的要求而定。對于不同的系統(tǒng)，JCBl 的內(nèi)容有所不同。第四章第四章 處理機(jī)調(diào)度處理機(jī)調(diào)度作業(yè)控制塊作業(yè)名資源要求估計完成時間最遲完成時間要求的主存要求的外設(shè)類型與臺數(shù)要求的文件數(shù)量和輸出量作業(yè)類型控制方式作業(yè)類型資源使用情況進(jìn)入系統(tǒng)時間開始執(zhí)行時間

6、已執(zhí)行時間主存地址外設(shè)臺數(shù)當(dāng)前狀態(tài)優(yōu)先級占用CPU的時間作業(yè)提交之后，有一定的調(diào)度戰(zhàn)略，總得在一定的時間內(nèi)完成。程序執(zhí)行時需求為作業(yè)調(diào)度提供一定的調(diào)度根據(jù)脫機(jī)還是聯(lián)機(jī)的長作業(yè)還是短作業(yè)I/O型還是計算型和資源要求配合運(yùn)用作業(yè)調(diào)度對一個作業(yè)而言只運(yùn)用一次進(jìn)程調(diào)度對一個進(jìn)程而言能夠運(yùn)用多次。留意：第四章第四章 處理機(jī)調(diào)度處理機(jī)調(diào)度4.2 .1 4.2 .1 作業(yè)調(diào)度的功能作業(yè)調(diào)度的功能4.2 4.2 作業(yè)調(diào)度作業(yè)調(diào)度作業(yè)調(diào)度：作業(yè)管理程序按一定戰(zhàn)略從后備作業(yè)中挑選一個作業(yè)，作業(yè)調(diào)度：作業(yè)管理程序按一定戰(zhàn)略從后備作業(yè)中挑選一個作業(yè)， 把它裝入內(nèi)存并且為它們分配必要的資源，并為作業(yè)創(chuàng)把它裝入內(nèi)存并且為

7、它們分配必要的資源，并為作業(yè)創(chuàng) 建一個主進(jìn)程以便它可以執(zhí)行。建一個主進(jìn)程以便它可以執(zhí)行。作業(yè)調(diào)度的功能：作業(yè)調(diào)度的功能： 經(jīng)過調(diào)度算法從后備隊列中挑選一個作業(yè)投入運(yùn)轉(zhuǎn)為選中的作業(yè)做好運(yùn)轉(zhuǎn)前的預(yù)備任務(wù)。在作業(yè)終了時做好善后任務(wù)回收資源作業(yè)調(diào)度的作用：作業(yè)調(diào)度的作用：完成作業(yè)從后備形狀到執(zhí)行形狀和從執(zhí)行態(tài)到完成完成作業(yè)從后備形狀到執(zhí)行形狀和從執(zhí)行態(tài)到完成形狀的轉(zhuǎn)換形狀的轉(zhuǎn)換第四章第四章 處理機(jī)調(diào)度處理機(jī)調(diào)度作業(yè)從后備態(tài)到執(zhí)行形狀作業(yè)從后備態(tài)到執(zhí)行形狀算法算法1 1：BEGIN 從后備隊列中選出一個作業(yè); While (資源要求不滿足 放棄該作業(yè); If 后備作業(yè)隊列為空 EXIT 按調(diào)度算法從后備

8、隊列中挑出一個作業(yè)； 調(diào)用存儲管理，設(shè)備管理程序看能否滿足資源要求； 分配資源； 調(diào)用進(jìn)程管理程序建立進(jìn)程； 進(jìn)程調(diào)度；END第四章第四章 處理機(jī)調(diào)度處理機(jī)調(diào)度作業(yè)從執(zhí)行形狀到完成形狀作業(yè)從執(zhí)行形狀到完成形狀算法算法2 2：BEGIN 回收分給該作業(yè)各個進(jìn)程的全部資源； 計算該作業(yè)的執(zhí)行時間； 撤銷一切進(jìn)程及作業(yè)的JCB; 轉(zhuǎn)入調(diào)用下一個作業(yè)；END第四章第四章 處理機(jī)調(diào)度處理機(jī)調(diào)度4.2 .2 4.2 .2 衡量調(diào)度性能的目的衡量調(diào)度性能的目的1 1、調(diào)度算法應(yīng)到達(dá)的目的、調(diào)度算法應(yīng)到達(dá)的目的每次運(yùn)轉(zhuǎn)盡能夠多的作業(yè)讓處置機(jī)堅持忙碌形狀使輸入輸出設(shè)備得以充分利用對一切的作業(yè)公平合理吞吐量利用率

9、問題公平性原那么2 2、確定調(diào)度算法時應(yīng)思索的要素、確定調(diào)度算法時應(yīng)思索的要素調(diào)度算法應(yīng)與系統(tǒng)的總體設(shè)計目的一致留意系統(tǒng)資源的平衡運(yùn)用，使輸入輸出忙碌的作業(yè)與CPU忙碌的作業(yè)搭配運(yùn)轉(zhuǎn)應(yīng)保證進(jìn)入系統(tǒng)的作業(yè)在規(guī)定的截至?xí)r間內(nèi)運(yùn)轉(zhuǎn)終了第四章第四章 處理機(jī)調(diào)度處理機(jī)調(diào)度3 3、調(diào)度算法性能的衡量、調(diào)度算法性能的衡量批處置系統(tǒng)中衡量作業(yè)調(diào)度算法性能的兩個目的：批處置系統(tǒng)中衡量作業(yè)調(diào)度算法性能的兩個目的：平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間1 1周轉(zhuǎn)時間：周轉(zhuǎn)時間：i i作業(yè)的周轉(zhuǎn)時間定義為：作業(yè)的周轉(zhuǎn)時間定義為：Ti=Tsi-TtiTi=Tsi-Tti其中：其中：TsiTsi為為

10、i i作業(yè)完成時間，作業(yè)完成時間，TtiTti為作業(yè)的提交時間。為作業(yè)的提交時間。 平均周轉(zhuǎn)時間：平均周轉(zhuǎn)時間：T=T=1 1n ni=1i=1n nTiTi第四章第四章 處理機(jī)調(diào)度處理機(jī)調(diào)度一個作業(yè)的周轉(zhuǎn)時間可分為一個作業(yè)的周轉(zhuǎn)時間可分為2 2部分：部分：1 1等待時間從后備態(tài)到執(zhí)行態(tài)；等待時間從后備態(tài)到執(zhí)行態(tài)；2 2執(zhí)行時間執(zhí)行時間可以表示為：可以表示為：Ti=Twi+TriTi=Twi+Tri2 2帶權(quán)周轉(zhuǎn)時間：帶權(quán)周轉(zhuǎn)時間：i=i=其中：其中：Ti是作業(yè)周轉(zhuǎn)時間是作業(yè)周轉(zhuǎn)時間, Tri是作業(yè)執(zhí)行時間是作業(yè)執(zhí)行時間TiTiTriTri平均帶權(quán)周轉(zhuǎn)時間：平均帶權(quán)周轉(zhuǎn)時間：n ni=1i=1

11、1 1n nW=i i第四章第四章 處理機(jī)調(diào)度處理機(jī)調(diào)度4.2 .3 4.2 .3 作業(yè)調(diào)度算法作業(yè)調(diào)度算法1 1、先來先效力調(diào)度算法：、先來先效力調(diào)度算法：嚴(yán)厲按照作業(yè)先來后到的次序進(jìn)展調(diào)度。嚴(yán)厲按照作業(yè)先來后到的次序進(jìn)展調(diào)度。例：例：有四個作業(yè)，它們的提交、執(zhí)行時間如下有四個作業(yè)，它們的提交、執(zhí)行時間如下作業(yè)號提交時間執(zhí)行時間111.02.0211.21.0311.40.5411.50.3帶權(quán)周轉(zhuǎn)時間1.02.86.211.0完成時間13.014.014.514.8周轉(zhuǎn)時間2.02.83.13.3開始時間11.013.014.014.5第四章第四章 處理機(jī)調(diào)度處理機(jī)調(diào)度2 2、短作業(yè)優(yōu)先調(diào)

12、度算法：、短作業(yè)優(yōu)先調(diào)度算法：選取執(zhí)行時間最短的作業(yè)作為下次效力的對象選取執(zhí)行時間最短的作業(yè)作為下次效力的對象例：例：有四個作業(yè)，它們的提交、執(zhí)行時間如下有四個作業(yè)，它們的提交、執(zhí)行時間如下作業(yè)號提交時間執(zhí)行時間開始時間111.02.011.0完成時間13.013.313.814.8周轉(zhuǎn)時間2.01.82.43.6帶權(quán)周轉(zhuǎn)時間1.06.04.83.6411.50.313.0311.40.513.3211.21.013.8作業(yè)號提交時間執(zhí)行時間111.02.0211.21.0311.40.5411.50.3第四章第四章 處理機(jī)調(diào)度處理機(jī)調(diào)度3 3、呼應(yīng)比高者優(yōu)先調(diào)度算法：、呼應(yīng)比高者優(yōu)先調(diào)度算法

13、：介于介于(FCFS)(FCFS)和短作業(yè)優(yōu)先調(diào)度算法和短作業(yè)優(yōu)先調(diào)度算法(SJF)(SJF)之間的算法之間的算法, ,是對二者的折中是對二者的折中呼應(yīng)比呼應(yīng)比= =( (等待時間等待時間+ +執(zhí)行時間執(zhí)行時間) )執(zhí)行時間執(zhí)行時間= =1+1+等待時間等待時間執(zhí)行時間執(zhí)行時間例：例：有四個作業(yè)，它們的提交、執(zhí)行時間下表有四個作業(yè)，它們的提交、執(zhí)行時間下表, ,如采用呼應(yīng)比高者優(yōu)先調(diào)度算法如采用呼應(yīng)比高者優(yōu)先調(diào)度算法(HRN)(HRN)來計算平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間來計算平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間( (其中時間單位為小時其中時間單位為小時, ,按十按十進(jìn)制計算進(jìn)制計算. .作業(yè)號提交

14、時間執(zhí)行時間18.02.028.30.538.50.149.00.4第四章第四章 處理機(jī)調(diào)度處理機(jī)調(diào)度作業(yè)號提交時間執(zhí)行時間18.02.0開始時間8.0周轉(zhuǎn)時間2.0響應(yīng)比1.0r2=1+(10.0-8.3)/0.5=4.4r2=1+(10.0-8.3)/0.5=4.4r3=1+(10.0-8.5)/0.1=16r3=1+(10.0-8.5)/0.1=16r4=1+(10.0-9.0)/0.4=3.75r4=1+(10.0-9.0)/0.4=3.75此時此時, ,各作業(yè)的呼應(yīng)比為各作業(yè)的呼應(yīng)比為: :作業(yè)號提交時間執(zhí)行時間18.02.038.50.1開始時間8.010.0周轉(zhuǎn)時間2.01.6響

15、應(yīng)比1.016第四章第四章 處理機(jī)調(diào)度處理機(jī)調(diào)度作業(yè)號提交時間執(zhí)行時間18.02.038.50.1開始時間8.010.0周轉(zhuǎn)時間2.01.6響應(yīng)比1.016r2=1+(10.1-8.3)/0.5=4.6r2=1+(10.1-8.3)/0.5=4.6r4=1+(10.1-9.0)/0.4=3.75r4=1+(10.1-9.0)/0.4=3.75此時此時, ,各作業(yè)的呼應(yīng)比為各作業(yè)的呼應(yīng)比為: :作業(yè)號提交時間執(zhí)行時間18.02.038.50.1開始時間8.010.0周轉(zhuǎn)時間2.01.6響應(yīng)比1.01628.30.510.12.34.6第四章第四章 處理機(jī)調(diào)度處理機(jī)調(diào)度r4=1+(10.6-9.0

16、)/0.4=5r4=1+(10.6-9.0)/0.4=5此時此時, ,各作業(yè)的呼應(yīng)比為各作業(yè)的呼應(yīng)比為: :作業(yè)號提交時間執(zhí)行時間18.02.038.50.1開始時間8.010.0周轉(zhuǎn)時間2.01.6響應(yīng)比1.01628.30.510.12.34.649.00.410.62.05.0平均周轉(zhuǎn)時間為平均周轉(zhuǎn)時間為(2.0+1.6+2.3+2.0)/5=1.975(2.0+1.6+2.3+2.0)/5=1.975第四章第四章 處理機(jī)調(diào)度處理機(jī)調(diào)度4 4、優(yōu)先數(shù)調(diào)度算法：、優(yōu)先數(shù)調(diào)度算法：可以綜合思索有關(guān)要素可以綜合思索有關(guān)要素, ,如作業(yè)緩急程序如作業(yè)緩急程序, ,作業(yè)長短作業(yè)長短, ,等待時間的

17、長短等待時間的長短, ,外部設(shè)外部設(shè)備備, ,運(yùn)用情況等運(yùn)用情況等, ,并根據(jù)系統(tǒng)設(shè)計目的分析這些要素的重要程度并根據(jù)系統(tǒng)設(shè)計目的分析這些要素的重要程度, ,按比例確定按比例確定各作業(yè)的優(yōu)先數(shù)各作業(yè)的優(yōu)先數(shù), ,系統(tǒng)按優(yōu)先數(shù)高來調(diào)度作業(yè)系統(tǒng)按優(yōu)先數(shù)高來調(diào)度作業(yè). .例：例：在后備作業(yè)隊列中等待運(yùn)轉(zhuǎn)的同時有在后備作業(yè)隊列中等待運(yùn)轉(zhuǎn)的同時有3 3個作業(yè)個作業(yè)1 1、2 2、3 3，知它們的各自運(yùn)，知它們的各自運(yùn)轉(zhuǎn)時間為轉(zhuǎn)時間為a a、b b、c c，且，且a b c.a b 0第四章第四章 處理機(jī)調(diào)度處理機(jī)調(diào)度例：例：有一個具有有一個具有2 2道作業(yè)的批處置系統(tǒng)，作業(yè)調(diào)度采用短作業(yè)優(yōu)先的調(diào)度算道作

18、業(yè)的批處置系統(tǒng)，作業(yè)調(diào)度采用短作業(yè)優(yōu)先的調(diào)度算法，進(jìn)程調(diào)度采用高優(yōu)先級優(yōu)先的搶占式調(diào)度算法。在下表所示的作業(yè)法，進(jìn)程調(diào)度采用高優(yōu)先級優(yōu)先的搶占式調(diào)度算法。在下表所示的作業(yè)序列作業(yè)優(yōu)先數(shù)即為進(jìn)程優(yōu)先數(shù)，優(yōu)先數(shù)越小，優(yōu)先級越高。序列作業(yè)優(yōu)先數(shù)即為進(jìn)程優(yōu)先數(shù)，優(yōu)先數(shù)越小，優(yōu)先級越高。作業(yè)名到達(dá)時間估計運(yùn)行時間優(yōu)先數(shù)A10：0040（分）5B10：20303C10：30504D10：50206進(jìn)入內(nèi)存時間10：0010：2011：1010：50列出一切作業(yè)進(jìn)入內(nèi)存時間及終了時間計算平均周轉(zhuǎn)時間結(jié)束時間11：1010：5012：0012：20第四章第四章 處理機(jī)調(diào)度處理機(jī)調(diào)度各作業(yè)的周轉(zhuǎn)時間為：各作業(yè)的

19、周轉(zhuǎn)時間為：作業(yè)A：20執(zhí)行30內(nèi)存內(nèi)等待20執(zhí)行70作業(yè)B：30執(zhí)行作業(yè)C：20內(nèi)存外等待B執(zhí)行20內(nèi)存外等待A執(zhí)行50執(zhí)行90作業(yè)D：20內(nèi)存為等待A執(zhí)行50內(nèi)存內(nèi)等待C執(zhí)行20執(zhí)行90作業(yè)的平均周轉(zhuǎn)時間為：作業(yè)的平均周轉(zhuǎn)時間為：7070303090909090/4/47070分鐘分鐘第四章第四章 處理機(jī)調(diào)度處理機(jī)調(diào)度例：例：在某多道程序系統(tǒng)中，供用戶運(yùn)用的內(nèi)存空間為在某多道程序系統(tǒng)中，供用戶運(yùn)用的內(nèi)存空間為100K,100K,磁帶機(jī)磁帶機(jī)2 2臺，打印臺，打印機(jī)機(jī)1 1臺。系統(tǒng)采用可變式分區(qū)分配方式管理內(nèi)存，對磁帶機(jī)和打印機(jī)采臺。系統(tǒng)采用可變式分區(qū)分配方式管理內(nèi)存，對磁帶機(jī)和打印機(jī)采用靜

20、態(tài)分配方式，并假設(shè)輸入、輸出操作的時間忽略不計?，F(xiàn)有一作業(yè)用靜態(tài)分配方式，并假設(shè)輸入、輸出操作的時間忽略不計?，F(xiàn)有一作業(yè)序列如下表所示。序列如下表所示。作業(yè)號到達(dá)時間要求計算時間要求內(nèi)存申請磁帶機(jī)申請打印機(jī)18：0025（分）15K1128：201030K-138：202060K1-48：302020K1-58：351510K11第四章第四章 處理機(jī)調(diào)度處理機(jī)調(diào)度寫出作業(yè)調(diào)度選中的作業(yè)調(diào)度次序假設(shè)把一個作業(yè)的周轉(zhuǎn)時間定義為到達(dá)系統(tǒng)至計算完成的時間，那么最大和最小的作業(yè)周轉(zhuǎn)時間是多少？作業(yè)全部執(zhí)行終了的時間是多少？假設(shè)作業(yè)調(diào)度采用先來先效力算法，優(yōu)先分配內(nèi)存的低地址區(qū)域且不準(zhǔn)假設(shè)作業(yè)調(diào)度采用先來

21、先效力算法，優(yōu)先分配內(nèi)存的低地址區(qū)域且不準(zhǔn)挪動已在內(nèi)存中的作業(yè)，在內(nèi)存中的作業(yè)平分挪動已在內(nèi)存中的作業(yè)，在內(nèi)存中的作業(yè)平分CPUCPU時間，問：時間，問：8 8：0000時，作業(yè)時，作業(yè)1 1到達(dá)。到達(dá)。作業(yè)10 015K15K100K-1100K-18 8：0000內(nèi)存分配情況內(nèi)存分配情況剩余資源：剩余資源：1 1臺磁帶機(jī)臺磁帶機(jī)第四章第四章 處理機(jī)調(diào)度處理機(jī)調(diào)度8 8：2020時，作業(yè)時，作業(yè)3 3到達(dá)。到達(dá)。作業(yè)10 015K15K100K-1100K-18 8：2020內(nèi)存分配情況內(nèi)存分配情況剩余資源：無剩余資源：無8 8：2020時，作業(yè)時，作業(yè)2 2到達(dá)。懇求的資源打印機(jī)被作業(yè)到達(dá)

22、。懇求的資源打印機(jī)被作業(yè)1 1占用，作業(yè)占用，作業(yè)2 2等待等待作業(yè)375K75K第四章第四章 處理機(jī)調(diào)度處理機(jī)調(diào)度8 8：3030時，作業(yè)時，作業(yè)1 1運(yùn)轉(zhuǎn)終了。運(yùn)轉(zhuǎn)終了。0 015K15K100K-1100K-18 8：3030內(nèi)存分配情況內(nèi)存分配情況剩余資源：無剩余資源：無作業(yè)375K75K作業(yè)作業(yè)2 2等待。等待。第四章第四章 處理機(jī)調(diào)度處理機(jī)調(diào)度8 8：3030時，作業(yè)時，作業(yè)4 4到達(dá)。而作業(yè)到達(dá)。而作業(yè)2 2的內(nèi)存資源不滿足，繼續(xù)等待。的內(nèi)存資源不滿足，繼續(xù)等待。0 015K15K100K-1100K-18 8：3030內(nèi)存分配情況內(nèi)存分配情況作業(yè)375K75K作業(yè)495K95K

23、8 8：3535時，作業(yè)時，作業(yè)5 5到達(dá)。而作業(yè)到達(dá)。而作業(yè)2 2的內(nèi)存資源不滿足，繼續(xù)等待。同時作的內(nèi)存資源不滿足，繼續(xù)等待。同時作業(yè)業(yè)5 5要求的磁帶機(jī)資源不滿足，作業(yè)要求的磁帶機(jī)資源不滿足，作業(yè)5 5等待。等待。第四章第四章 處理機(jī)調(diào)度處理機(jī)調(diào)度9 9：0000時，作業(yè)時，作業(yè)3 3運(yùn)轉(zhuǎn)終了，釋放占用的資源和內(nèi)存。運(yùn)轉(zhuǎn)終了，釋放占用的資源和內(nèi)存。0 0100K-1100K-19 9：0000內(nèi)存分配情況內(nèi)存分配情況75K75K作業(yè)495K95K第四章第四章 處理機(jī)調(diào)度處理機(jī)調(diào)度9 9：0000時，根據(jù)先來先效力調(diào)度算法，由于資源都能得到滿足，選中等待作業(yè)時，根據(jù)先來先效力調(diào)度算法，由于

24、資源都能得到滿足，選中等待作業(yè)中的作業(yè)中的作業(yè)2 2進(jìn)入內(nèi)存。作業(yè)進(jìn)入內(nèi)存。作業(yè)5 5繼續(xù)等待繼續(xù)等待0 0100K-1100K-19 9：0000內(nèi)存分配情況內(nèi)存分配情況75K75K作業(yè)495K95K作業(yè)230K30K第四章第四章 處理機(jī)調(diào)度處理機(jī)調(diào)度9 9：1010時，作業(yè)時，作業(yè)4 4運(yùn)轉(zhuǎn)終了。作業(yè)運(yùn)轉(zhuǎn)終了。作業(yè)5 5懇求的打印機(jī)資源被作業(yè)懇求的打印機(jī)資源被作業(yè)2 2占用，作業(yè)占用，作業(yè)5 5繼續(xù)等待。繼續(xù)等待。0 0100K-1100K-19 9：1010分內(nèi)存分配情況分內(nèi)存分配情況75K75K95K95K作業(yè)230K30K9 9：1515時，作業(yè)時，作業(yè)2 2運(yùn)轉(zhuǎn)終了。作業(yè)運(yùn)轉(zhuǎn)終了。

25、作業(yè)5 5懇求的一切資源可用，作業(yè)懇求的一切資源可用，作業(yè)5 5進(jìn)入內(nèi)存執(zhí)行至進(jìn)入內(nèi)存執(zhí)行至9 9：3030終終了。了。第四章第四章 處理機(jī)調(diào)度處理機(jī)調(diào)度 作業(yè)選中的次序：作業(yè)選中的次序：1342513425 作業(yè)作業(yè)1 1的周轉(zhuǎn)時間：的周轉(zhuǎn)時間：8:308:308:008:003030 作業(yè)作業(yè)2 2的周轉(zhuǎn)時間：的周轉(zhuǎn)時間：9:159:158:208:205555 作業(yè)作業(yè)3 3的周轉(zhuǎn)時間：的周轉(zhuǎn)時間：9:009:008:208:204040 作業(yè)作業(yè)4 4的周轉(zhuǎn)時間：的周轉(zhuǎn)時間：9:109:108:308:304040 作業(yè)作業(yè)1 1的周轉(zhuǎn)時間：的周轉(zhuǎn)時間：9:309:308:358:35

26、5555 作業(yè)全部執(zhí)行終了的時間：作業(yè)全部執(zhí)行終了的時間：9 9：3030第四章第四章 處理機(jī)調(diào)度處理機(jī)調(diào)度 在多道程環(huán)境下，進(jìn)程數(shù)目往往多于處置機(jī)數(shù)目，致使它們爭用途置機(jī)。這就要求系統(tǒng)能按某種算法，動態(tài)地把處置機(jī)分配給就緒隊列中的一個進(jìn)程，使之執(zhí)行。分配處置機(jī)的義務(wù)是由進(jìn)程調(diào)度程序完成的。它是操作系統(tǒng)設(shè)計的中心問題之一。進(jìn)程調(diào)度要處理的問題進(jìn)程調(diào)度要處理的問題WHATWHAT：按什么原那么分配：按什么原那么分配CPUCPU 進(jìn)程調(diào)度算法進(jìn)程調(diào)度算法WHENWHEN：何時分配：何時分配CPUCPU 進(jìn)程調(diào)度的時機(jī)進(jìn)程調(diào)度的時機(jī)HOWHOW： 如何分配如何分配CPUCPU CPU CPU調(diào)度過程

27、進(jìn)程的上下文切換調(diào)度過程進(jìn)程的上下文切換4.3 進(jìn)程調(diào)度進(jìn)程調(diào)度第四章第四章 處理機(jī)調(diào)度處理機(jī)調(diào)度1、進(jìn)程調(diào)度的義務(wù)、進(jìn)程調(diào)度的義務(wù)2、確定調(diào)度算法的原那么、確定調(diào)度算法的原那么具有公平性。具有公平性。資源利用率高特別是資源利用率高特別是CPUCPU的利用率。的利用率。在交互式系統(tǒng)情況下要追求呼應(yīng)時間越短越好。在交互式系統(tǒng)情況下要追求呼應(yīng)時間越短越好。在批處置系統(tǒng)情況下要追求系統(tǒng)吞吐量。在批處置系統(tǒng)情況下要追求系統(tǒng)吞吐量。就是控制協(xié)調(diào)進(jìn)程對就是控制協(xié)調(diào)進(jìn)程對CPU的競爭即按一定的調(diào)度算法從就緒隊列中選中一個進(jìn)的競爭即按一定的調(diào)度算法從就緒隊列中選中一個進(jìn)程，把程，把CPU的運(yùn)用權(quán)交給被選中的進(jìn)

28、程。的運(yùn)用權(quán)交給被選中的進(jìn)程。第四章第四章 處理機(jī)調(diào)度處理機(jī)調(diào)度3 、進(jìn)程調(diào)度算法、進(jìn)程調(diào)度算法l先進(jìn)先出先進(jìn)先出(FIFO)算法算法l最高優(yōu)先權(quán)優(yōu)先調(diào)度算法最高優(yōu)先權(quán)優(yōu)先調(diào)度算法l時間片輪轉(zhuǎn)算法時間片輪轉(zhuǎn)算法 l多級反響隊列多級反響隊列 調(diào)度算法調(diào)度算法第四章第四章 處理機(jī)調(diào)度處理機(jī)調(diào)度1.先進(jìn)先出(FIFO)算法l 該算法總是把處置機(jī)分配給最先進(jìn)入就緒隊列的進(jìn)程，一個進(jìn)程一旦分得處置機(jī)，便執(zhí)行下去，直到該進(jìn)程完成或阻塞時，才釋放處置機(jī)。l 優(yōu)點:實現(xiàn)簡單. 缺陷:沒思索進(jìn)程的優(yōu)先級2.基于優(yōu)先數(shù)的調(diào)度算法HPF):確定優(yōu)先數(shù)的方法：確定優(yōu)先數(shù)的方法：靜態(tài)優(yōu)先數(shù)法：在進(jìn)程創(chuàng)建時指定優(yōu)先數(shù)，在

29、進(jìn)程運(yùn)轉(zhuǎn)時優(yōu)先數(shù)靜態(tài)優(yōu)先數(shù)法：在進(jìn)程創(chuàng)建時指定優(yōu)先數(shù)，在進(jìn)程運(yùn)轉(zhuǎn)時優(yōu)先數(shù)不變。不變。動態(tài)優(yōu)先數(shù)法：在進(jìn)程創(chuàng)建時創(chuàng)建一個優(yōu)先數(shù)，但在其生命周期動態(tài)優(yōu)先數(shù)法：在進(jìn)程創(chuàng)建時創(chuàng)建一個優(yōu)先數(shù)，但在其生命周期內(nèi)優(yōu)先數(shù)可以動態(tài)變化。內(nèi)優(yōu)先數(shù)可以動態(tài)變化。優(yōu)先選擇就緒隊列中優(yōu)先級最高的進(jìn)程投入運(yùn)轉(zhuǎn)。優(yōu)先選擇就緒隊列中優(yōu)先級最高的進(jìn)程投入運(yùn)轉(zhuǎn)。第四章第四章 處理機(jī)調(diào)度處理機(jī)調(diào)度占用占用CPU的方式的方式l非剝奪方式：分派程序一旦把處置機(jī)分配給某進(jìn)程后便讓它非剝奪方式：分派程序一旦把處置機(jī)分配給某進(jìn)程后便讓它l 不斷運(yùn)轉(zhuǎn)下去，直到進(jìn)程完成或發(fā)生某事件而不斷運(yùn)轉(zhuǎn)下去，直到進(jìn)程完成或發(fā)生某事件而l 阻塞時，才把處置機(jī)

30、分配給另一個進(jìn)程。阻塞時，才把處置機(jī)分配給另一個進(jìn)程。l剝奪方式：當(dāng)一個進(jìn)程正在運(yùn)轉(zhuǎn)時，系統(tǒng)可以基于某種原剝奪方式：當(dāng)一個進(jìn)程正在運(yùn)轉(zhuǎn)時，系統(tǒng)可以基于某種原l 那么，剝奪已分配給它的處置機(jī)，將之分配給其它進(jìn)那么，剝奪已分配給它的處置機(jī)，將之分配給其它進(jìn)程。程。l 剝奪原那么有：優(yōu)先權(quán)原那么、短進(jìn)程優(yōu)先原那么、剝奪原那么有：優(yōu)先權(quán)原那么、短進(jìn)程優(yōu)先原那么、l 時間片原那么。時間片原那么。第四章第四章 處理機(jī)調(diào)度處理機(jī)調(diào)度3、時間片輪轉(zhuǎn)調(diào)度算法: 時間片選擇問題：時間片選擇問題：固定時間片固定時間片可變時間片可變時間片與時間片大小有關(guān)的要素與時間片大小有關(guān)的要素系統(tǒng)呼應(yīng)時間系統(tǒng)呼應(yīng)時間就緒進(jìn)程個數(shù)

31、就緒進(jìn)程個數(shù)CPUCPU才干才干 把把CPUCPU劃分成假設(shè)干個時間片，并且按順序賦給就緒隊列中的劃分成假設(shè)干個時間片，并且按順序賦給就緒隊列中的 每個進(jìn)程，進(jìn)程輪番占有每個進(jìn)程，進(jìn)程輪番占有CPUCPU，當(dāng)時間片用完時，即使進(jìn)程未執(zhí)，當(dāng)時間片用完時，即使進(jìn)程未執(zhí)行終了，系統(tǒng)也剝奪該進(jìn)程的行終了，系統(tǒng)也剝奪該進(jìn)程的CPUCPU，將該進(jìn)程排在就緒隊列未尾，將該進(jìn)程排在就緒隊列未尾，同時系統(tǒng)選擇另一進(jìn)程運(yùn)轉(zhuǎn)。同時系統(tǒng)選擇另一進(jìn)程運(yùn)轉(zhuǎn)。第四章第四章 處理機(jī)調(diào)度處理機(jī)調(diào)度4、多級反響隊列調(diào)度算法： 首先系統(tǒng)中設(shè)置多個就緒隊列首先系統(tǒng)中設(shè)置多個就緒隊列每個就緒隊列分配給不同時間片，優(yōu)先級高的為第一隊列，

32、時間片最每個就緒隊列分配給不同時間片，優(yōu)先級高的為第一隊列，時間片最小，隨著隊列級別的降低，時間片加大。小，隨著隊列級別的降低，時間片加大。各個隊列按照先進(jìn)先出調(diào)度算法各個隊列按照先進(jìn)先出調(diào)度算法一個新進(jìn)程就緒后進(jìn)入第一級隊列一個新進(jìn)程就緒后進(jìn)入第一級隊列進(jìn)程由于等待而放棄進(jìn)程由于等待而放棄CPUCPU后，進(jìn)入等待隊列，一旦等待的事件發(fā)生，后，進(jìn)入等待隊列，一旦等待的事件發(fā)生，者進(jìn)入到一級隊列中去。者進(jìn)入到一級隊列中去。當(dāng)有一個優(yōu)先級更高的進(jìn)程就緒時，可以搶占當(dāng)有一個優(yōu)先級更高的進(jìn)程就緒時，可以搶占CPUCPU，被搶占進(jìn)程回到，被搶占進(jìn)程回到原來一級就緒隊列未尾。原來一級就緒隊列未尾。當(dāng)?shù)谝患?/p>

33、隊列為空時，就去調(diào)度第二級隊列，如此類推。當(dāng)?shù)谝患夑犃袨榭諘r，就去調(diào)度第二級隊列，如此類推。當(dāng)時間片到時，進(jìn)程放棄當(dāng)時間片到時，進(jìn)程放棄CPUCPU，回到下一級隊列。，回到下一級隊列。 將就緒隊列分為將就緒隊列分為N N級，每個就緒隊列分配給不同的時間片，隊級，每個就緒隊列分配給不同的時間片，隊列級別越高，時間越長，級別越小，時間片越小。最后一級采列級別越高，時間越長，級別越小，時間片越小。最后一級采用時間片輪轉(zhuǎn)，其他隊列采用先進(jìn)先出；系統(tǒng)從第一級調(diào)度，用時間片輪轉(zhuǎn)，其他隊列采用先進(jìn)先出；系統(tǒng)從第一級調(diào)度，當(dāng)?shù)谝患墳榭諘r，系統(tǒng)轉(zhuǎn)向第二個隊列當(dāng)?shù)谝患墳榭諘r，系統(tǒng)轉(zhuǎn)向第二個隊列,當(dāng)運(yùn)轉(zhuǎn)進(jìn)程用完一個

34、當(dāng)運(yùn)轉(zhuǎn)進(jìn)程用完一個時間片，放棄時間片，放棄CPUCPU時，進(jìn)入下一級隊列；等待進(jìn)程被喚醒時，進(jìn)時，進(jìn)入下一級隊列；等待進(jìn)程被喚醒時，進(jìn)入原來的就緒隊列；當(dāng)進(jìn)程第一次就緒時，進(jìn)入第一級隊列。入原來的就緒隊列；當(dāng)進(jìn)程第一次就緒時，進(jìn)入第一級隊列。 第四章第四章 處理機(jī)調(diào)度處理機(jī)調(diào)度時間片時間片小小大大優(yōu)先級優(yōu)先級高高低低運(yùn)運(yùn)轉(zhuǎn)轉(zhuǎn)等等待待1 1級級2 2級級3 3級級假設(shè)：假設(shè)：1 1級隊列中無進(jìn)程級隊列中無進(jìn)程選擇優(yōu)先級最大的進(jìn)程選擇優(yōu)先級最大的進(jìn)程資源得不到滿足等待等待某個事件資源得不到滿足等待等待某個事件時間片用盡時間片用盡有更高優(yōu)先級進(jìn)入有更高優(yōu)先級進(jìn)入處于等待形狀進(jìn)程進(jìn)入就緒態(tài)時，排在第處

35、于等待形狀進(jìn)程進(jìn)入就緒態(tài)時，排在第1 1級隊列中級隊列中第四章第四章 處理機(jī)調(diào)度處理機(jī)調(diào)度特點：特點： 采用短作業(yè)優(yōu)先的方法采用短作業(yè)優(yōu)先的方法 照顧了照顧了I/OI/O型的作業(yè)型的作業(yè) 照顧了長作業(yè)照顧了長作業(yè)例例1 1：假設(shè)有一臺計算機(jī)，它有假設(shè)有一臺計算機(jī)，它有1M1M內(nèi)存，操作系統(tǒng)占用內(nèi)存，操作系統(tǒng)占用200K,200K,每個用戶進(jìn)程每個用戶進(jìn)程也占用也占用200K200K，用戶進(jìn)程等待，用戶進(jìn)程等待I/OI/O的時間為的時間為8080，假設(shè)添加，假設(shè)添加1M1M內(nèi)存，那么內(nèi)存，那么CPUCPU的利用率將提高多少？的利用率將提高多少？例例2 2：假設(shè)就緒隊列中有假設(shè)就緒隊列中有1010個進(jìn)程，系統(tǒng)將時間片設(shè)為個進(jìn)程，系統(tǒng)將時間片設(shè)為200ms,CPU200ms,CPU進(jìn)展進(jìn)程進(jìn)展進(jìn)程切換要破費切換要破費10ms,10ms,問：系統(tǒng)開銷所占的比率為多少？問：系統(tǒng)開銷所占的比率為多少？第四章第四章 處理機(jī)調(diào)度處理機(jī)調(diào)度進(jìn)程調(diào)度的時機(jī)進(jìn)程調(diào)度的時機(jī)當(dāng)一個進(jìn)程運(yùn)轉(zhuǎn)終了，或由于某種錯誤而終止運(yùn)轉(zhuǎn)。當(dāng)一個進(jìn)程運(yùn)轉(zhuǎn)終了，或由于某種錯誤而終