ch2.5處理器調(diào)度2.6批處理的管理與調(diào)度2.7低級調(diào)度

2.5處理機(jī)調(diào)度

2.5.1處理機(jī)調(diào)度的層次2.5.3高級調(diào)度2.5.3中級調(diào)度2.5.4低級調(diào)度2.5.5選擇調(diào)度算法的原則

2.5.1處理機(jī)調(diào)度的層次

高級調(diào)度(1)?作業(yè)調(diào)度、長程調(diào)度?高級調(diào)度的任務(wù)?批處理操作系統(tǒng)中的高級調(diào)度高級調(diào)度(2)分時(shí)操作系統(tǒng)中，高級調(diào)度任務(wù)：1）是否接受一個(gè)終端用戶的連接；2）一個(gè)程序能否被計(jì)算機(jī)系統(tǒng)接納并構(gòu)成進(jìn)程；3）一個(gè)新建態(tài)的進(jìn)程是否能夠加入就緒進(jìn)程隊(duì)列。中級調(diào)度(1)平衡負(fù)載調(diào)度，中程調(diào)度。決定主存儲器中所能容納的進(jìn)程數(shù)，這些進(jìn)程將允許參與競爭處理器資源。中級調(diào)度根據(jù)存儲資源量和進(jìn)程的當(dāng)前狀態(tài)來決定輔存和主存中進(jìn)程的對換。中級調(diào)度(2)中級調(diào)度決定那些進(jìn)程被允許參與競爭處理器資源，使用的方法是通過把一些進(jìn)程換出主存，使之進(jìn)入“掛起”狀態(tài)，不參與進(jìn)程調(diào)度，起到平滑和調(diào)整系統(tǒng)負(fù)荷的作用。低級調(diào)度(1)

進(jìn)程調(diào)度、短程調(diào)度。主要功能是按照某種原則決定就緒隊(duì)列中的哪個(gè)進(jìn)程或內(nèi)核級線程能獲得處理器,并將處理機(jī)出讓給它進(jìn)行工作。短程調(diào)度程序是操作系統(tǒng)最為核心的部分，短程調(diào)度策略的優(yōu)劣直接影響到整個(gè)系統(tǒng)的性能。低級調(diào)度(2)

有兩類低級調(diào)度方式：第一類稱剝奪方式：

高優(yōu)先級剝奪原則時(shí)間片剝奪原則第二類稱非剝奪方式：

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

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

高級調(diào)度中級調(diào)度低級調(diào)度運(yùn)行態(tài)就緒態(tài)終止態(tài)新建態(tài)掛起就緒態(tài)中級調(diào)度掛起等待態(tài)等待態(tài)高級調(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)度2.5.5選擇調(diào)度算法的原則(1)

l

資源利用率

CPU利用率=CPU有效工作時(shí)間/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份額或其他資源份額，不會出現(xiàn)餓死情況。

作業(yè)周轉(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ǒng)的性能，要讓若干個(gè)用戶的平均作業(yè)周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間最小。平均作業(yè)周轉(zhuǎn)時(shí)間

T=(Σti)/n作業(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)/n衡量調(diào)度算法的調(diào)度性能用平均作業(yè)周轉(zhuǎn)時(shí)間來衡量對同一作業(yè)流施行不同作業(yè)調(diào)度算法時(shí)，它們呈現(xiàn)的調(diào)度性能；用平均作業(yè)帶權(quán)周轉(zhuǎn)時(shí)間來衡量對不同作業(yè)流施行同一作業(yè)調(diào)度算法時(shí)，它們呈現(xiàn)的調(diào)度性能。這兩個(gè)數(shù)值均2.6批處理作業(yè)的管理與調(diào)度

2.6.1作業(yè)和進(jìn)程的關(guān)系2.6.2批處理作業(yè)的管理2.6.3批處理作業(yè)的調(diào)度2.6.4作業(yè)調(diào)度算法2.6.1作業(yè)和進(jìn)程的關(guān)系(1)

?作業(yè)(JOB)，?作業(yè)步(JobStep)，?作業(yè)組織，?作業(yè)的提交、收容、執(zhí)行和完成。作業(yè)和進(jìn)程的關(guān)系(2)

作業(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.6.2批處理作業(yè)的管理

批處理作業(yè)的脫機(jī)控制方式，作業(yè)控制語言，作業(yè)說明書，批處理作業(yè)的輸入，調(diào)度、執(zhí)行和撤離。

作業(yè)控制塊(1)多道批處理操作系統(tǒng)具有獨(dú)立的作業(yè)管理模塊，必須像進(jìn)程管理一樣為每一個(gè)作業(yè)建立作業(yè)控制塊（JCB）。JCB通常是在批作業(yè)進(jìn)入系統(tǒng)時(shí)，由Spooling系統(tǒng)建立的，它是作業(yè)存在于系統(tǒng)的標(biāo)志，作業(yè)撤離時(shí)，JCB也被撤銷。作業(yè)控制塊(2)

JCB的主要內(nèi)容包括：

(1)作業(yè)情況(用戶名、作業(yè)名、語言名),(2)資源需求(估計(jì)CPU運(yùn)行時(shí)間、最遲截止期、主存量、設(shè)備類型/臺數(shù)、文件數(shù)和數(shù)據(jù)量、函數(shù)庫/實(shí)用程序等),(3)資源使用情況(進(jìn)入系統(tǒng)時(shí)間、開始運(yùn)行時(shí)間、己運(yùn)行時(shí)間),作業(yè)控制(優(yōu)先數(shù)、控制方式、操作順序、出錯(cuò)處理等)。作業(yè)生命周期狀態(tài)輸入狀態(tài)：此時(shí)作業(yè)的信息正在從輸入設(shè)備上預(yù)輸入。后備狀態(tài)：此時(shí)作業(yè)預(yù)輸入結(jié)束但尚未被選中執(zhí)行。執(zhí)行狀態(tài)：作業(yè)已經(jīng)被選中并構(gòu)成進(jìn)程去競爭處理器資源以獲得運(yùn)行。完成狀態(tài)：作業(yè)已經(jīng)運(yùn)行結(jié)束，正在等待緩輸出。2.6.3批處理作業(yè)的調(diào)度(1)處于后備狀態(tài)的作業(yè)在系統(tǒng)資源滿足的前提下可以被作業(yè)調(diào)度選中進(jìn)入內(nèi)存計(jì)算。而只有處于執(zhí)行狀態(tài)的作業(yè)才真正構(gòu)成進(jìn)程獲得計(jì)算的機(jī)會。批處理作業(yè)的調(diào)度(2)作業(yè)調(diào)度選中一個(gè)作業(yè)且把它裝入主存儲器時(shí)就為該作業(yè)創(chuàng)建一個(gè)用戶進(jìn)程。這些進(jìn)程將在進(jìn)程調(diào)度的控制下占有處理器運(yùn)行。為了充分利用處理器，可以把多個(gè)作業(yè)同時(shí)裝入主存儲器，這樣就會同時(shí)有多個(gè)用戶進(jìn)程，這些進(jìn)程都要競爭處理器。批處理作業(yè)的調(diào)度(3)進(jìn)入計(jì)算機(jī)系統(tǒng)的作業(yè)只有經(jīng)過兩級調(diào)度后才能占用處理器。第一級是作業(yè)調(diào)度，使作業(yè)進(jìn)入主存儲器；第二級是處理器調(diào)度，使作業(yè)進(jìn)程占用處理器。作業(yè)調(diào)度與處理器調(diào)度的配合能實(shí)現(xiàn)多道作業(yè)的同時(shí)執(zhí)行。作業(yè)調(diào)度與進(jìn)程調(diào)度的關(guān)系

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

1

先來先服務(wù)算法(1)按照作業(yè)進(jìn)入系統(tǒng)的先后次序來挑選作業(yè)，先進(jìn)入系統(tǒng)的作業(yè)優(yōu)先被挑選。算法容易實(shí)現(xiàn)，效率不高，只顧及作業(yè)等候時(shí)間，沒考慮作業(yè)要求服務(wù)時(shí)間的長短，不利于短作業(yè)而優(yōu)待了長作業(yè)。

先來先服務(wù)算法(2)

例如，三個(gè)作業(yè)同時(shí)到達(dá)系統(tǒng)并立即進(jìn)入調(diào)度：作業(yè)名所需CPU時(shí)間作業(yè)128作業(yè)29作業(yè)33采用FCFS算法，三個(gè)作業(yè)的周轉(zhuǎn)時(shí)間分別為：28、37和40，因此，平均作業(yè)周轉(zhuǎn)時(shí)間T=(28+37+40)/3=35先來先服務(wù)算法(3)

?若三個(gè)作業(yè)提交順序改為作業(yè)2、1、3，平均作業(yè)周轉(zhuǎn)時(shí)間約為29。若三個(gè)作業(yè)提交順序改為作業(yè)3、2、1，平均作業(yè)周轉(zhuǎn)時(shí)間約為18。FCFS調(diào)度算法的平均作業(yè)周轉(zhuǎn)時(shí)間與作業(yè)提交的順序有關(guān)。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í)間。會出現(xiàn)饑餓現(xiàn)象。最短作業(yè)優(yōu)先算法(2)

例如，四個(gè)作業(yè)同時(shí)到達(dá)系統(tǒng)并立即進(jìn)入調(diào)度：作業(yè)名所需CPU時(shí)間作業(yè)19作業(yè)24作業(yè)310作業(yè)48假設(shè)系統(tǒng)中沒有其他作業(yè)，現(xiàn)實(shí)施SJF調(diào)度算法，最短作業(yè)優(yōu)先算法(3)SJF的作業(yè)調(diào)度順序?yàn)樽鳂I(yè)2、4、1、3，平均作業(yè)周轉(zhuǎn)時(shí)間

T=(4+12+21+31)/4=17

平均帶權(quán)作業(yè)周轉(zhuǎn)時(shí)間W=(4/4+12/8+21/9+31/10)/4=1.98

J2

J4

J1

J3

4122131最短作業(yè)優(yōu)先算法(4)如果對它們施行FCFS調(diào)度算法，平均作業(yè)周轉(zhuǎn)時(shí)間

T=(9+13+23+31)/4=19

平均帶權(quán)作業(yè)周轉(zhuǎn)時(shí)間

W=(9/9+13/4+23/10+31/8)/4=2.51

J1

J2J3

J4

9132331最短作業(yè)優(yōu)先算法(5)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)先算法(6)可根據(jù)每個(gè)進(jìn)程的執(zhí)行歷史來預(yù)測它的下一個(gè)CPU長度，令tn是第n個(gè)實(shí)際的執(zhí)行長度，τn是其預(yù)測值，那么，下一個(gè)CPU執(zhí)行長度的預(yù)測公式：

τn+1=αtn+(1-α)τn

其中，α(0<α<1)用于控制最近的tn和其預(yù)測值τn在預(yù)測中的作用，其值常為0.5。

SJF算法進(jìn)一步討論(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è),此算法不但適用于JOB調(diào)度，同樣也適用于進(jìn)程調(diào)度。SJF算法進(jìn)一步討論(2)一個(gè)例子,假如四個(gè)就緒作業(yè)其到達(dá)系統(tǒng)和所需CPU時(shí)間如下：作業(yè)名到達(dá)系統(tǒng)時(shí)間CPU時(shí)間(毫秒)---------------------------------------

Job108Job214Job329Job435

SJF算法進(jìn)一步討論(3)

J1J2J4J1J3015101726SJF算法進(jìn)一步討論(4)

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

響應(yīng)比最高者優(yōu)先(HRRF)算法

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í)間過長，改進(jìn)了調(diào)度性能。

響應(yīng)比定義

作業(yè)進(jìn)入系統(tǒng)后的等待時(shí)間與估計(jì)運(yùn)行時(shí)間之比稱作響應(yīng)比，現(xiàn)定義；響應(yīng)比＝1+已等待時(shí)間/估計(jì)運(yùn)行時(shí)間?短作業(yè)容易得到較高響應(yīng)比，?長作業(yè)等待時(shí)間足夠長后，也將獲得足夠高的響應(yīng)比，?饑餓現(xiàn)象不會發(fā)生。HRRF算法舉例(1)例如，以下四個(gè)作業(yè)先后到達(dá)系統(tǒng)進(jìn)入調(diào)度：作業(yè)名到達(dá)時(shí)間所需CPU時(shí)間作業(yè)10 20作業(yè)25 15作業(yè)3105作業(yè)415 10HRRF算法舉例(2)

假設(shè)實(shí)施SJFSJF的作業(yè)調(diào)度順序?yàn)樽鳂I(yè)1、3、4、2，

平均作業(yè)周轉(zhuǎn)時(shí)間T=（20+25-10+35-15+50-5）/4=25

平均帶權(quán)作業(yè)周轉(zhuǎn)時(shí)間W=（20/20+15/5+20/10+45/15）/4=2.25

HRRF算法舉例(3)

假設(shè)實(shí)施FCFS如果對它們施行FCFS調(diào)度算法，作業(yè)調(diào)度順序?yàn)樽鳂I(yè)1、2、3、4，平均作業(yè)周轉(zhuǎn)時(shí)間T=（20+35-5+40-10+50-15）/4=28.75

平均帶權(quán)作業(yè)周轉(zhuǎn)時(shí)間W=（20/20+30/15+30/5+35/10）/4=3.125

HRRF算法舉例(4)

對作業(yè)流執(zhí)行HRRF調(diào)度算法

?開始只有作業(yè)1，被選中執(zhí)行時(shí)間20；?作業(yè)1執(zhí)行完畢，響應(yīng)比依次為1+15/15、1+10/5、1+5/10，作業(yè)3被選中，執(zhí)行時(shí)間5；?作業(yè)3執(zhí)行完畢，響應(yīng)比依次為1+20/15、1+10/10，作業(yè)2被選中，執(zhí)行時(shí)間15；?作業(yè)2執(zhí)行完畢，作業(yè)4被選中，執(zhí)行時(shí)間10；

HRRF算法舉例(5)

對作業(yè)流執(zhí)行HRRF調(diào)度算法

平均作業(yè)周轉(zhuǎn)時(shí)間T=（20+25-10+40-5+50-15）/4=26.25

平均帶權(quán)作業(yè)周轉(zhuǎn)時(shí)間W=（20/20+15/5+35/15+35/10）/4=2.46

4

優(yōu)先數(shù)法(1)

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

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

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

分類調(diào)度算法

預(yù)先按一定原則把作業(yè)劃分成若干類，以達(dá)到均衡使用系統(tǒng)資源和兼顧大小作業(yè)的目的。分類原則包括作業(yè)計(jì)算時(shí)間、對內(nèi)存的需求、對外圍設(shè)備的需求等。作業(yè)調(diào)度時(shí)還可為每類作業(yè)設(shè)置優(yōu)先級，從而照顧到同類作業(yè)中的輕重緩急。6

用與不用磁帶的作業(yè)搭配作業(yè)調(diào)度時(shí)，把使用磁帶機(jī)和不使用磁帶機(jī)的作業(yè)搭配挑選。可使要用磁帶機(jī)的作業(yè)在執(zhí)行時(shí)省去等待裝磁帶的時(shí)間。顯然對縮短系統(tǒng)的平均周轉(zhuǎn)時(shí)間是有益的。2.7低級調(diào)度

2.7.1低級調(diào)度的功能2.7.2低級調(diào)度算法2.7.3實(shí)時(shí)調(diào)度2.7.4多處理器調(diào)度2.7.5實(shí)例研究：UNIXSVR4調(diào)度算法2.7.6實(shí)例研究：Windows2000/XP調(diào)度算法2.7.7實(shí)例研究：Linux調(diào)度算法2.7.1低級調(diào)度的功能低級調(diào)度負(fù)責(zé)動態(tài)地把處理器分配給進(jìn)程或內(nèi)核級線程。操作系統(tǒng)中實(shí)現(xiàn)低級調(diào)度的程序稱為進(jìn)程(線程)調(diào)度程序，或分派程序(Dispatcher)。進(jìn)程調(diào)度算法多數(shù)適用于線程調(diào)度。何時(shí)發(fā)生CPU調(diào)度呢?

有四種情況都會發(fā)生CPU調(diào)度:當(dāng)一個(gè)進(jìn)程從運(yùn)行態(tài)切換成等待態(tài)時(shí);當(dāng)一個(gè)進(jìn)程從運(yùn)行態(tài)切換成就緒態(tài)時(shí);當(dāng)一個(gè)進(jìn)程從等待態(tài)切換成就緒態(tài)時(shí);當(dāng)一個(gè)進(jìn)程中止時(shí)。

低級調(diào)度的主要功能

?記住進(jìn)程的狀態(tài)。?決定某個(gè)進(jìn)程什么時(shí)候獲得處理器，以及占用多長時(shí)間。?把處理器分配給進(jìn)程。?收回處理器。低級調(diào)度基本方式?非搶占式?搶占式?折衷方式

2.7.2低級調(diào)度算法

1

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

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

時(shí)間片調(diào)度做法是：調(diào)度程序每次把CPU分配給就緒隊(duì)列首進(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)度。2

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

例如，現(xiàn)有進(jìn)程P1、P2、P3，所需CPU時(shí)間單位為：14、10和8。采用時(shí)間片長為2個(gè)單位的輪轉(zhuǎn)法：則平均周轉(zhuǎn)時(shí)間由FCFS的23.3下降到14個(gè)CPU時(shí)間單位。

P1P2P3P1P2

P3P1P2P3P1P2P3P1P2P1P1時(shí)間片輪轉(zhuǎn)調(diào)度算法(3)輪轉(zhuǎn)策略可防止那些很少使用外圍設(shè)備的進(jìn)程過長的占用處理器而使得要使用外圍設(shè)備的那些進(jìn)程沒有機(jī)會去啟動外圍設(shè)備。輪轉(zhuǎn)策略與間隔時(shí)鐘時(shí)間片輪轉(zhuǎn)調(diào)度算法(4)基本輪轉(zhuǎn)法改進(jìn)輪轉(zhuǎn)法時(shí)間片輪轉(zhuǎn)調(diào)度算法(5)

時(shí)間片取選(1)輪轉(zhuǎn)法調(diào)度是一種剝奪式調(diào)度，系統(tǒng)耗費(fèi)在進(jìn)程切換上的開銷比較大，這個(gè)開銷與時(shí)間片的大小很有關(guān)系。時(shí)間片輪轉(zhuǎn)調(diào)度算法(6)

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

時(shí)間片取選(3)時(shí)間片大小的確定要從進(jìn)程個(gè)數(shù)、切換開銷、系統(tǒng)效率和響應(yīng)時(shí)間等方面考慮。3優(yōu)先權(quán)調(diào)度(1)

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

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

動態(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)度的可能性越小。UNIX(早期版本)動態(tài)優(yōu)先數(shù)

計(jì)算公式

p-pri=min{127,(p-cpu/16+PUSER+p-nice)}p-pri為進(jìn)程優(yōu)先數(shù)p-nice用戶調(diào)節(jié)參數(shù)PUSER為常數(shù)

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

多級反饋隊(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)度策略

低級就緒隊(duì)列高級就緒隊(duì)列中級就緒隊(duì)列等待磁盤磁帶等待其他外設(shè)運(yùn)行選中,時(shí)間片500ms超過時(shí)間片啟動磁盤磁帶啟動其他外設(shè)選中,時(shí)間片200ms選中,時(shí)間片100ms5

保證調(diào)度算法(1)

向用戶做出明確的性能保證，然后去實(shí)現(xiàn)它。容易實(shí)現(xiàn)的一種保證是：當(dāng)工作時(shí)己有n個(gè)用戶登錄在系統(tǒng)，則將獲得CPU處理能力的1/n。類似的，如果在一個(gè)有n個(gè)進(jìn)程運(yùn)行的用戶系統(tǒng)中，每個(gè)進(jìn)程將獲得CPU處理能力的1/n。保證調(diào)度算法(2)保證調(diào)度算法必須跟蹤各個(gè)進(jìn)程自創(chuàng)建以來已經(jīng)使用了多少CPU時(shí)間。計(jì)算各個(gè)進(jìn)程應(yīng)獲得的CPU時(shí)間，即自創(chuàng)建以來的時(shí)間除以n。由于各個(gè)進(jìn)程實(shí)際獲得的CPU時(shí)間已知，所以很容易計(jì)算出實(shí)際獲得的CPU時(shí)間和應(yīng)獲得的CPU時(shí)間之比，于是調(diào)度將轉(zhuǎn)向比率最低的進(jìn)程。6

彩票調(diào)度算法(1)

基本思想：為進(jìn)程發(fā)放針對各種資源（如CPU時(shí)間）的彩票。調(diào)度程序隨機(jī)選擇一張彩票，持有該彩票的進(jìn)程獲得系統(tǒng)資源。進(jìn)程都是平等的，有相同的運(yùn)行機(jī)會。如果某些進(jìn)程需要更多的機(jī)會，可被給予更多彩票，增加其中獎機(jī)會。彩票調(diào)度算法(2)

彩票調(diào)度法有趣特性：反映迅速，合作進(jìn)程可交換彩票。彩票調(diào)度算法(3)彩票調(diào)度可以解決其他算法難以解決的問題。例如，一個(gè)視頻服務(wù)器。2.7.3實(shí)時(shí)調(diào)度

實(shí)時(shí)操作系統(tǒng)的特性實(shí)時(shí)系統(tǒng)是那些時(shí)間因素非常關(guān)鍵的系統(tǒng)。實(shí)時(shí)系統(tǒng)包括監(jiān)控系統(tǒ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í)（hardrealtime）系統(tǒng)和軟實(shí)時(shí)（softrealtime）系統(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)度可的（schedulable）。軟實(shí)時(shí)系統(tǒng)一個(gè)軟實(shí)時(shí)系統(tǒng)處理三個(gè)事件流，其周期分別為100ms，200ms和500ms，如果事件處理時(shí)間分別為50ms，30ms和100ms，則這個(gè)系統(tǒng)是可調(diào)度的，因?yàn)?.5+0.15+0.2≤1如果加入周期為1秒的第4個(gè)事件，則只要其處理時(shí)間不超過150ms，該系統(tǒng)仍將時(shí)可調(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)程，并采取搶占式分配策略。實(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.7.4多處理器調(diào)度

流行的多處理器系統(tǒng)有：

?松散耦合多處理器系統(tǒng)：

?緊密耦合多處理器系統(tǒng)：現(xiàn)代操作系統(tǒng)往往采用進(jìn)程調(diào)度與線程調(diào)度相結(jié)合的方式來完成多處理器調(diào)度。1

同步的粒度

同步的粒度，就是系統(tǒng)中多個(gè)進(jìn)程之間同步的頻率，它是刻畫多處理系統(tǒng)特征和描述進(jìn)程并發(fā)度的一個(gè)重要指標(biāo)。同步粒度的劃分

?細(xì)粒度（fine-grained）：

?中粒度（medium-grained）：

?粗粒度（coarse-grained）：

?超粗粒度（verycoarse-grained）：

?獨(dú)立（independent）：

多處理器調(diào)度的設(shè)計(jì)要點(diǎn)

設(shè)計(jì)要點(diǎn)之一是如何把處理器分配給進(jìn)程：靜態(tài)分配策略動態(tài)分配策略設(shè)計(jì)要點(diǎn)之二是否要在單個(gè)處理器上支持多道程序設(shè)計(jì)。設(shè)計(jì)要點(diǎn)之三是如何指派進(jìn)程。多處理器的調(diào)度算法(1)

實(shí)驗(yàn)證明，隨著處理器數(shù)目的增多，復(fù)雜低級調(diào)度算法的有效性逐步下降。多數(shù)采取動態(tài)分配策略的多處理器系統(tǒng)中，低級調(diào)度算法往往采用最簡單的FCFS或優(yōu)先數(shù)算法。多處理器的調(diào)度算法(2)多處理器調(diào)度的主要研究對象是線程調(diào)度算法。盡管線程也給單處理器系統(tǒng)帶來很大益處，但在多處理器環(huán)境中線程的作用才真正得到充分發(fā)揮。多處理器調(diào)度算法(3)

1）負(fù)載共享調(diào)度算法

基本思想：進(jìn)程并不分配給一個(gè)特定處理器，系統(tǒng)維護(hù)一個(gè)全局性就緒線程隊(duì)列，當(dāng)一個(gè)處理器空閑時(shí)，就選擇一個(gè)就緒線程占有處理器運(yùn)行。多處理器調(diào)度算法(4)

負(fù)載共享調(diào)度算法優(yōu)點(diǎn)?

把負(fù)載均分到所有可用處理器上，保證了處理器效率的提高。?不需要集中的調(diào)度程序，一旦一個(gè)處理器空閑，調(diào)度程序就可以運(yùn)行在該處理器上以選擇下一個(gè)運(yùn)行的線程。?運(yùn)行線程的選擇可以采用各種可行的策略。

多處理器調(diào)度算法(5)

三種不同負(fù)載共享算法(1)先來先服務(wù)。(2)最少線程數(shù)優(yōu)先。(3)有剝奪的最少線程數(shù)優(yōu)先。多處理器調(diào)度算法(6)

負(fù)載共享調(diào)度算法不足?