第4章處理器調(diào)度

第四章處理機調(diào)度4.1處理機調(diào)度的層次4.2作業(yè)調(diào)度4.3低級調(diào)度4.4實時調(diào)度算法

14.1處理機調(diào)度的層次高級調(diào)度中級調(diào)度低級調(diào)度2高級調(diào)度?作業(yè)調(diào)度、長程調(diào)度?高級調(diào)度的任務(wù)?批處理操作系統(tǒng)中的高級調(diào)度3高級調(diào)度

分時操作系統(tǒng)中，高級調(diào)度任務(wù)：1）是否接受一個終端用戶的連接；2）一個程序能否被計算機系統(tǒng)接納并構(gòu)成進程；3）一個新建態(tài)的進程是否能夠加入就緒進程隊列。4中級調(diào)度平衡負載調(diào)度，中程調(diào)度。決定主存儲器中所能容納的進程數(shù)，這些進程將允許參與競爭處理器資源。中級調(diào)度根據(jù)存儲資源量和進程的當前狀態(tài)來決定輔存和主存中進程的對換。5中級調(diào)度中級調(diào)度決定那些進程被允許參與競爭處理器資源，使用的方法是通過把一些進程換出主存，使之進入“掛起”狀態(tài)，不參與進程調(diào)度，起到平滑和調(diào)整系統(tǒng)負荷的作用。6低級調(diào)度進程調(diào)度、短程調(diào)度。主要功能是按照某種原則決定就緒隊列中的哪個進程或內(nèi)核級線程能獲得處理器,并將處理機出讓給它進行工作。短程調(diào)度程序是操作系統(tǒng)最為核心的部分，短程調(diào)度策略的優(yōu)劣直接影響到整個系統(tǒng)的性能。7低級調(diào)度

有兩類低級調(diào)度方式：第一類稱剝奪方式：高優(yōu)先級剝奪原則時間片剝奪原則第二類稱非剝奪方式：

8處理器調(diào)度的層次

中級調(diào)度新建態(tài)掛起就緒態(tài)掛起等待態(tài)高級調(diào)度低級調(diào)度運行態(tài)就緒態(tài)等待態(tài)終止態(tài)9處理器調(diào)度與進程狀態(tài)轉(zhuǎn)換高級調(diào)度中級調(diào)度低級調(diào)度運行就緒終止新建掛起就緒中級調(diào)度掛起等待等待高級調(diào)度高級調(diào)度中級調(diào)度10處理器的調(diào)度模型

中級調(diào)度處理器低級調(diào)度高級調(diào)度完成超時掛起就緒隊列掛起等待隊列等待隊列就緒隊列等待事件交互式用戶事件出現(xiàn)后備作業(yè)隊列中級調(diào)度11選擇調(diào)度算法的原則(1)1、資源利用率

CPU利用率=CPU有效工作時間/CPU總的運行時間，CPU總的運行時間=CPU有效工作時間+CPU空閑等待時間。12選擇調(diào)度算法的原則(2)

2、周轉(zhuǎn)時間?批處理用戶從作業(yè)提交給系統(tǒng)開始，到作業(yè)完成為止的時間間隔稱作業(yè)周轉(zhuǎn)時間，應(yīng)使作業(yè)周轉(zhuǎn)時間或平均作業(yè)周轉(zhuǎn)時間盡可能短。?這是批處理系統(tǒng)衡量調(diào)度性能的一個重要指標。3、吞吐率單位時間內(nèi)處理的作業(yè)數(shù)。

13

選擇調(diào)度算法的原則(3)4、響應(yīng)時間?交互式進程從提交一個請求(命令)到接收到響應(yīng)之間的時間間隔稱響應(yīng)時間。?使交互式用戶的響應(yīng)時間盡可能短，或盡快處理實時任務(wù)。?這是分時系統(tǒng)和實時系統(tǒng)衡量調(diào)度性能的一個重要指標。14選擇調(diào)度算法的原則(4)

5、公平性確保每個用戶每個進程獲得合理的CPU份額或其他資源份額，不會出現(xiàn)餓死情況。15

作業(yè)周轉(zhuǎn)時間如果作業(yè)i提交給系統(tǒng)的時刻是ts，完成時刻是tf，該作業(yè)的周轉(zhuǎn)時間ti為：ti=tf-ts

實際上，它是作業(yè)在系統(tǒng)里的等待時間與運行時間之和。16平均作業(yè)周轉(zhuǎn)時間為了提高系統(tǒng)的性能，要讓若干個用戶的平均作業(yè)周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間最小。

平均作業(yè)周轉(zhuǎn)時間T=(Σti)/n17作業(yè)帶權(quán)周轉(zhuǎn)時間和平均

作業(yè)帶權(quán)周轉(zhuǎn)時間如果作業(yè)i的周轉(zhuǎn)時間為ti，所需運行時間為tk，則稱wi=ti/tk為該作業(yè)的帶權(quán)周轉(zhuǎn)時間。ti是等待時間與運行時間之和，故帶權(quán)周轉(zhuǎn)時間總大于1。

平均作業(yè)帶權(quán)周轉(zhuǎn)時間W=(Σwi)/n18衡量調(diào)度算法的調(diào)度性能用平均作業(yè)周轉(zhuǎn)時間來衡量對同一作業(yè)流施行不同作業(yè)調(diào)度算法時，它們呈現(xiàn)的調(diào)度性能；用平均作業(yè)帶權(quán)周轉(zhuǎn)時間來衡量對不同作業(yè)流施行同一作業(yè)調(diào)度算法時，它們呈現(xiàn)的調(diào)度性能。194.2批處理作業(yè)的管理與調(diào)度作業(yè)生命周期狀態(tài)輸入狀態(tài)：此時作業(yè)的信息正在從輸入設(shè)備上預(yù)輸入。后備狀態(tài)：此時作業(yè)預(yù)輸入結(jié)束但尚未被選中執(zhí)行。執(zhí)行狀態(tài)：作業(yè)已經(jīng)被選中并構(gòu)成進程去競爭處理器資源以獲得運行。完成狀態(tài)：作業(yè)已經(jīng)運行結(jié)束，正在等待緩輸出。20多道批處理的處理機調(diào)度包括作業(yè)調(diào)度和進程調(diào)度兩個層次處于后備狀態(tài)的作業(yè)在系統(tǒng)資源滿足的前提下可以被作業(yè)調(diào)度選中進入內(nèi)存計算。而只有處于執(zhí)行狀態(tài)的作業(yè)才真正構(gòu)成進程獲得計算的機會。21多道批處理的處理機調(diào)度包括作業(yè)調(diào)度和進程調(diào)度兩個層次作業(yè)調(diào)度選中一個作業(yè)且把它裝入主存儲器時就為該作業(yè)創(chuàng)建一個用戶進程。這些進程將在進程調(diào)度的控制下占有處理器運行。為了充分利用處理器，可以把多個作業(yè)同時裝入主存儲器，這樣就會同時有多個用戶進程，這些進程都要競爭處理器。22多道批處理的處理機調(diào)度包括作業(yè)調(diào)度和進程調(diào)度兩個層次進入計算機系統(tǒng)的作業(yè)只有經(jīng)過兩級調(diào)度后才能占用處理器。第一級是作業(yè)調(diào)度，使作業(yè)進入主存儲器；第二級是處理器調(diào)度，使作業(yè)進程占用處理器。作業(yè)調(diào)度與處理器調(diào)度的配合能實現(xiàn)多道作業(yè)的同時執(zhí)行。23作業(yè)調(diào)度與進程調(diào)度的關(guān)系

執(zhí)行狀態(tài)運行就緒等待輸入狀態(tài)后備狀態(tài)完成狀態(tài)進程調(diào)度中級調(diào)度緩輸出作業(yè)調(diào)度預(yù)輸入完成24作業(yè)調(diào)度算法

1

先來先服務(wù)算法(1)按照作業(yè)進入系統(tǒng)的先后次序來挑選作業(yè)，先進入系統(tǒng)的作業(yè)優(yōu)先被挑選。

25先來先服務(wù)算法(2)例如，三個作業(yè)依次到達系統(tǒng)并立即進入調(diào)度：作業(yè)名所需CPU時間作業(yè)128作業(yè)29作業(yè)3326先來先服務(wù)算法(3)采用FCFS算法，三個作業(yè)的周轉(zhuǎn)時間分別為：28、37和40，因此，平均作業(yè)周轉(zhuǎn)時間T=(28+37+40)/3=3527算法特點：算法容易實現(xiàn)，效率不高，只顧及作業(yè)等候時間，沒考慮作業(yè)要求服務(wù)時間的長短，不利于短作業(yè)而優(yōu)待了長作業(yè)。28?若三個作業(yè)提交順序改為作業(yè)2、1、3，平均作業(yè)周轉(zhuǎn)時間約為29。若三個作業(yè)提交順序改為作業(yè)3、2、1，平均作業(yè)周轉(zhuǎn)時間約為18。FCFS調(diào)度算法的平均作業(yè)周轉(zhuǎn)時間與作業(yè)提交的順序有關(guān)。292

最短作業(yè)優(yōu)先算法(1)SJF算法以進入系統(tǒng)的作業(yè)所要求的CPU時間為標準，總選取估計計算時間最短的作業(yè)投入運行。30最短作業(yè)優(yōu)先算法(2)

例如，四個作業(yè)依次到達系統(tǒng)并立即進入調(diào)度：作業(yè)名所需CPU時間作業(yè)19作業(yè)24作業(yè)310作業(yè)48假設(shè)系統(tǒng)中沒有其他作業(yè)，現(xiàn)實施SJF調(diào)度算法31最短作業(yè)優(yōu)先算法(3)SJF的作業(yè)調(diào)度順序為作業(yè)2、4、1、3，平均作業(yè)周轉(zhuǎn)時間T=(4+12+21+31)/4=17平均帶權(quán)作業(yè)周轉(zhuǎn)時間W=(4/4+12/8+21/9+31/10)/4=1.98如果對它們施行FCFS調(diào)度算法，平均作業(yè)周轉(zhuǎn)時間T=(9+13+23+31)/4=19平均帶權(quán)作業(yè)周轉(zhuǎn)時間W=(9/9+13/4+23/10+31/8)/4=2.5132最短作業(yè)優(yōu)先算法特點算法易于實現(xiàn)，效率不高，主要弱點是忽視了作業(yè)等待時間。會出現(xiàn)饑餓現(xiàn)象。SJF的平均作業(yè)周轉(zhuǎn)時間比FCFS要小，故它的調(diào)度性能比FCFS好。實現(xiàn)SJF調(diào)度算法需要知道作業(yè)所需運行時間，否則調(diào)度就沒有依據(jù)，要精確知道一個作業(yè)的運行時間是辦不到的。33SJF算法進一步討論SRTF把SJF算法改為搶占式的。一個新作業(yè)進入就緒狀態(tài)，如果新作業(yè)需要的CPU時間比當前正在執(zhí)行的作業(yè)剩余下來還需的CPU時間短，SRTF強行趕走當前正在執(zhí)行作業(yè),此算法不但適用于JOB調(diào)度，同樣也適用于進程調(diào)度。34SJF算法進一步討論——搶占式一個例子,假如四個就緒作業(yè)其到達系統(tǒng)和所需CPU時間如下：作業(yè)名到達系統(tǒng)時間CPU時間(毫秒)---------------------------------------Job108Job214Job329Job435

35SJF算法進一步討論

J1J2J4J1J301510172636SJF算法進一步討論Job1從0開始執(zhí)行，就緒隊列僅一個作業(yè)。Job2在時間1到達，Job1剩余時間（7毫秒）大于JOB2所需時間（4毫秒），Job1被剝奪，Job2被調(diào)度執(zhí)行。平均等待時間是（（10-1）+（1-1）+（17-2）+（5-3））/4=26/4=6.5毫秒。采用非搶占式SJF調(diào)度，那么，平均等待時間是7.75毫秒。373

響應(yīng)比最高者優(yōu)先(HRRF)算法FCFS與SJF是片面的調(diào)度算法。FCFS只考慮作業(yè)等候時間而忽視了作業(yè)的計算時間，SJF只考慮用戶估計的作業(yè)計算時間而忽視了作業(yè)等待時間。HRRF是介乎這兩者之間的折衷算法，既考慮作業(yè)等待時間，又考慮作業(yè)的運行時間，既照顧短作業(yè)又不使長作業(yè)的等待時間過長，改進了調(diào)度性能。38

響應(yīng)比定義

作業(yè)進入系統(tǒng)后的等待時間與估計運行時間之比稱作響應(yīng)比，現(xiàn)定義；響應(yīng)比＝1+已等待時間/估計運行時間

39HRRF算法舉例(1)

例如，以下四個作業(yè)先后到達系統(tǒng)進入調(diào)度：作業(yè)名到達時間所需CPU時間作業(yè)10 20作業(yè)25 15作業(yè)3105作業(yè)415 1040HRRF算法舉例(2)假設(shè)實施SJFSJF的作業(yè)調(diào)度順序為作業(yè)1、3、4、2，平均作業(yè)周轉(zhuǎn)時間T=(20+15+20+45)/4=25平均帶權(quán)作業(yè)周轉(zhuǎn)時間W=(20/20+15/5+25/10+45/15)/4=2.2541HRRF算法舉例(3)假設(shè)實施FCFS如果對它們施行FCFS調(diào)度算法，平均作業(yè)周轉(zhuǎn)時間T=(20+30+30+35)/4=38.75平均帶權(quán)作業(yè)周轉(zhuǎn)時間W=(20/20+30/15+30/5+35/10)/4=3.1342

HRRF算法舉例(4)

對作業(yè)流執(zhí)行HRRF調(diào)度算法?開始只有作業(yè)1，被選中執(zhí)行時間20；?作業(yè)1執(zhí)行完畢，響應(yīng)比依次為1+15/15、1+10/5、1+5/10，作業(yè)3被選中，執(zhí)行時間5；?作業(yè)3執(zhí)行完畢，響應(yīng)比依次為1+20/15、1+10/10，作業(yè)2被選中，執(zhí)行時間15；?作業(yè)2執(zhí)行完畢，作業(yè)4被選中，執(zhí)行時間10；平均作業(yè)周轉(zhuǎn)時間T=(20+15+35+35)/4=26.25平均帶權(quán)作業(yè)周轉(zhuǎn)時間W=(20/20+15/5+35/15+35/10)/4=2.4243HRRF算法特點短作業(yè)容易得到較高響應(yīng)比，長作業(yè)等待時間足夠長后，也將獲得足夠高的響應(yīng)比，饑餓現(xiàn)象不會發(fā)生。444

優(yōu)先數(shù)法(1)這種算法是根據(jù)確定的優(yōu)先數(shù)來選取作業(yè)，每次總是選擇優(yōu)先數(shù)高的作業(yè)。

45優(yōu)先數(shù)法(2)

規(guī)定用戶作業(yè)優(yōu)先數(shù)的方法：一種是由用戶自己提出作業(yè)的優(yōu)先數(shù)。另一種是由系統(tǒng)綜合考慮有關(guān)因素來確定用戶作業(yè)的優(yōu)先數(shù)。464.3低級調(diào)度

1低級調(diào)度的功能2低級調(diào)度算法3實時調(diào)度

474.3.1低級調(diào)度的功能低級調(diào)度負責(zé)動態(tài)地把處理器分配給進程或內(nèi)核級線程。操作系統(tǒng)中實現(xiàn)低級調(diào)度的程序稱為進程(線程)調(diào)度程序，或分派程序(Dispatcher)。進程調(diào)度算法多數(shù)適用于線程調(diào)度。48何時發(fā)生CPU調(diào)度呢?

有四種情況都會發(fā)生CPU調(diào)度:當一個進程從運行態(tài)切換成等待態(tài)時;當一個進程從運行態(tài)切換成就緒態(tài)時;當一個進程從等待態(tài)切換成就緒態(tài)時;當一個進程中止時。49

低級調(diào)度的主要功能?記住進程的狀態(tài)。?決定某個進程什么時候獲得處理器，以及占用多長時間。?把處理器分配給進程。?收回處理器。50低級調(diào)度基本方式

非搶占式搶占式

514.3.2低級調(diào)度算法1

先來先服務(wù)算法按照進程進入就緒隊列的先后次序分配處理器。先進入就緒隊列的進程優(yōu)先被挑選，運行進程一旦占有處理器將一直運行直到結(jié)束或阻塞。算法容易實現(xiàn)，效率不高，不利于I/O頻繁的進程。522

時間片輪轉(zhuǎn)調(diào)度算法(1)

時間片調(diào)度做法是：調(diào)度程序每次把CPU分配給就緒隊列首進程使用一個時間片，例如100ms，就緒隊列中的每個進程輪流地運行一個時間片。當這個時間片結(jié)束時，強迫一個進程讓出處理器，讓它排列到就緒隊列的尾部，等候下一輪調(diào)度。53時間片輪轉(zhuǎn)調(diào)度算法(2)輪轉(zhuǎn)策略可防止那些很少使用外圍設(shè)備的進程過長的占用處理器而使得要使用外圍設(shè)備的那些進程沒有機會去啟動外圍設(shè)備。輪轉(zhuǎn)策略與間隔時鐘54時間片輪轉(zhuǎn)調(diào)度算法(3)

時間片取選(1)

輪轉(zhuǎn)法調(diào)度是一種剝奪式調(diào)度，系統(tǒng)耗費在進程切換上的開銷比較大，這個開銷與時間片的大小很有關(guān)系。55時間片輪轉(zhuǎn)調(diào)度算法(4)

時間片取選(2)時間片取值太小，多數(shù)進程不能在一個時間片內(nèi)運行完畢，切換就會頻繁，開銷顯著增大，從系統(tǒng)效率來看，時間片取大一點好。時間片取值較大，隨就緒隊列里進程數(shù)目增加，輪轉(zhuǎn)一次的總時間增大，對進程的響應(yīng)速度放慢了。為滿足響應(yīng)時間要求，要么限制就緒隊列中進程數(shù)量，要么采用動態(tài)時間片法，根據(jù)負載狀況，及時調(diào)整時間片的大小。56時間片輪轉(zhuǎn)調(diào)度算法(5)

時間片取選(3)時間片大小的確定要從進程個數(shù)、切換開銷、系統(tǒng)效率和響應(yīng)時間等方面考慮。573

優(yōu)先權(quán)調(diào)度(1)

靜態(tài)優(yōu)先數(shù)法使用外圍設(shè)備頻繁者優(yōu)先數(shù)大，這樣有利于提高效率；重要算題程序的進程優(yōu)先數(shù)大，這樣有利于用戶；進入計算機時間長的進程優(yōu)先數(shù)大，這樣有利于縮短作業(yè)完成的時間；交互式用戶的進程優(yōu)先數(shù)大，這樣有利于終端用戶的響應(yīng)時間等等,

58優(yōu)先權(quán)調(diào)度(2)

動態(tài)優(yōu)先數(shù)法基本原則：①根據(jù)進程占有CPU時間多少來決定,當進程占有CPU時間愈長,那么，在它被阻塞之后再次獲得調(diào)度的優(yōu)先級就越低，反之,進程獲得調(diào)度的可能性越大;②根據(jù)進程等待CPU時間多少來決定,當進程在就緒隊列中等待時間愈長,那么，在它被阻塞之后再次獲得調(diào)度的優(yōu)先級就越高，反之,進程獲得調(diào)度的可能性越小。59UNIX(早期版本)動態(tài)優(yōu)先數(shù)計算公式

p-pri=min{127,(p-cpu/16+PUSER+p-nice)}p-pri為進程優(yōu)先數(shù)p-nice用戶調(diào)節(jié)參數(shù)PUSER為常數(shù)p-cpu反映進程使用處理機的程度60UNIX動態(tài)優(yōu)先數(shù)調(diào)度效果

(1)如果一個進程連續(xù)占用處理機較長時間，那么，它的p-cpu值就增大，計算出的p-pri也增大，于是優(yōu)先權(quán)下降。(2)如果一個進程長時間未被調(diào)用到或者雖頻繁調(diào)度到，但每次占用的時間都小于200ms，那么，p-cpu就較小甚至為0，從而，計算出的p-pri也較小，于是優(yōu)先權(quán)上升。61UNIX系統(tǒng)計算優(yōu)先數(shù)的時機一是對所有優(yōu)先數(shù)大于100的進程，系統(tǒng)每秒鐘重新計算一次它的優(yōu)先數(shù)；二是每次系統(tǒng)調(diào)用命令處理完畢之時，就重新對現(xiàn)進程的優(yōu)先數(shù)進行計算。624

多級反饋隊列調(diào)度

又稱反饋循環(huán)隊列或多隊列策略。主要思想是將就緒進程分為兩級或多級，系統(tǒng)相應(yīng)建立兩個或多個就緒進程隊列，較高優(yōu)先級的隊列一般分配給較短的時間片。處理器調(diào)度先從高級就緒進程隊列中選取可占有處理器的進程，只有在選不到時，才從較低級的就緒進程隊列中選取。634.4實時調(diào)度

實時操作系統(tǒng)的特性實時系統(tǒng)是那些時間因素非常關(guān)鍵的系統(tǒng)。實時系統(tǒng)包括監(jiān)控系統(tǒng)、自動駕駛系統(tǒng)、安全控制系統(tǒng)等，這些系統(tǒng)中，遲到的響應(yīng)即使正確，也和沒有響應(yīng)一樣糟糕。64硬實時系統(tǒng)和軟實時系統(tǒng)實時系統(tǒng)通常分為硬實