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

2.5處理機調(diào)度

2.5.1處理機調(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處理機調(diào)度的層次

高級調(diào)度(1)?作業(yè)調(diào)度、長程調(diào)度?高級調(diào)度的任務(wù)?批處理操作系統(tǒng)中的高級調(diào)度高級調(diào)度(2)分時操作系統(tǒng)中，高級調(diào)度任務(wù)：1）是否接受一個終端用戶的連接；2）一個程序能否被計算機系統(tǒng)接納并構(gòu)成進(jìn)程；3）一個新建態(tài)的進(jìn)程是否能夠加入就緒進(jìn)程隊列。中級調(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)度。主要功能是按照某種原則決定就緒隊列中的哪個進(jìn)程或內(nèi)核級線程能獲得處理器,并將處理機出讓給它進(jìn)行工作。短程調(diào)度程序是操作系統(tǒng)最為核心的部分，短程調(diào)度策略的優(yōu)劣直接影響到整個系統(tǒng)的性能。低級調(diào)度(2)

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

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

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

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

高級調(diào)度中級調(diào)度低級調(diào)度運行態(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)度完成超時掛起就緒隊列掛起等待隊列等待隊列就緒隊列等待事件交互式用戶事件出現(xiàn)后備作業(yè)隊列中級調(diào)度2.5.5選擇調(diào)度算法的原則(1)

l

資源利用率

CPU利用率=CPU有效工作時間/CPU總的運行時間，

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

2

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

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

選擇調(diào)度算法的原則(4)

4吞吐率單位時間內(nèi)處理的作業(yè)數(shù)。

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

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

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

T=(Σti)/n作業(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)/n衡量調(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)度性能。這兩個數(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ù)實體，進(jìn)程是完成任務(wù)的執(zhí)行實體;沒有作業(yè)任務(wù)，進(jìn)程無事可干，沒有進(jìn)程，作業(yè)任務(wù)沒法完成。作業(yè)概念更多地用在批處理操作系統(tǒng)，而進(jìn)程則可以用在各種多道程序設(shè)計系統(tǒng)。2.6.2批處理作業(yè)的管理

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

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

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

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

執(zhí)行狀態(tài)運行就緒等待輸入狀態(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)先被挑選。算法容易實現(xiàn)，效率不高，只顧及作業(yè)等候時間，沒考慮作業(yè)要求服務(wù)時間的長短，不利于短作業(yè)而優(yōu)待了長作業(yè)。

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

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

?若三個作業(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)。2

最短作業(yè)優(yōu)先算法(1)

SJF算法以進(jìn)入系統(tǒng)的作業(yè)所要求的CPU時間為標(biāo)準(zhǔn)，總選取估計計算時間最短的作業(yè)投入運行。算法易于實現(xiàn)，效率不高，主要弱點是忽視了作業(yè)等待時間。會出現(xiàn)饑餓現(xiàn)象。最短作業(yè)優(yōu)先算法(2)

例如，四個作業(yè)同時到達(dá)系統(tǒng)并立即進(jìn)入調(diào)度：作業(yè)名所需CPU時間作業(yè)19作業(yè)24作業(yè)310作業(yè)48假設(shè)系統(tǒng)中沒有其他作業(yè)，現(xiàn)實施SJF調(diào)度算法，最短作業(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

J2

J4

J1

J3

4122131最短作業(yè)優(yōu)先算法(4)如果對它們施行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.51

J1

J2J3

J4

9132331最短作業(yè)優(yōu)先算法(5)SJF的平均作業(yè)周轉(zhuǎn)時間比FCFS要小，故它的調(diào)度性能比FCFS好。實現(xiàn)SJF調(diào)度算法需要知道作業(yè)所需運行時間，否則調(diào)度就沒有依據(jù)，要精確知道一個作業(yè)的運行時間是辦不到的。最短作業(yè)優(yōu)先算法(6)可根據(jù)每個進(jìn)程的執(zhí)行歷史來預(yù)測它的下一個CPU長度，令tn是第n個實際的執(zhí)行長度，τn是其預(yù)測值，那么，下一個CPU執(zhí)行長度的預(yù)測公式：

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

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

SJF算法進(jìn)一步討論(1)SRTF把SJF算法改為搶占式的。一個新作業(yè)進(jìn)入就緒狀態(tài)，如果新作業(yè)需要的CPU時間比當(dāng)前正在執(zhí)行的作業(yè)剩余下來還需的CPU時間短，SRTF強行趕走當(dāng)前正在執(zhí)行作業(yè),此算法不但適用于JOB調(diào)度，同樣也適用于進(jìn)程調(diào)度。SJF算法進(jìn)一步討論(2)一個例子,假如四個就緒作業(yè)其到達(dá)系統(tǒng)和所需CPU時間如下：作業(yè)名到達(dá)系統(tǒng)時間CPU時間(毫秒)---------------------------------------

Job108Job214Job329Job435

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

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

Job1從0開始執(zhí)行，就緒隊列僅一個作業(yè)。Job2在時間1到達(dá)，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毫秒。3

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

FCFS與SJF是片面的調(diào)度算法。FCFS只考慮作業(yè)等候時間而忽視了作業(yè)的計算時問，SJF只考慮用戶估計的作業(yè)計算時間而忽視了作業(yè)等待時間。HRRF是介乎這兩者之間的折衷算法，既考慮作業(yè)等待時間，又考慮作業(yè)的運行時間，既照顧短作業(yè)又不使長作業(yè)的等待時間過長，改進(jìn)了調(diào)度性能。

響應(yīng)比定義

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

假設(shè)實施SJFSJF的作業(yè)調(diào)度順序為作業(yè)1、3、4、2，

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

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

HRRF算法舉例(3)

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

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

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；

HRRF算法舉例(5)

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

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

平均帶權(quán)作業(yè)周轉(zhuǎn)時間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è)計算時間、對內(nèi)存的需求、對外圍設(shè)備的需求等。作業(yè)調(diào)度時還可為每類作業(yè)設(shè)置優(yōu)先級，從而照顧到同類作業(yè)中的輕重緩急。6

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

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

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

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

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

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

1

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

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

時間片調(diào)度做法是：調(diào)度程序每次把CPU分配給就緒隊列首進(jìn)程使用一個時間片，例如100ms，就緒隊列中的每個進(jìn)程輪流地運行一個時間片。當(dāng)這個時間片結(jié)束時，強迫一個進(jìn)程讓出處理器，讓它排列到就緒隊列的尾部，等候下一輪調(diào)度。2

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

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

P1P2P3P1P2

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

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

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

時間片取選(3)時間片大小的確定要從進(jìn)程個數(shù)、切換開銷、系統(tǒng)效率和響應(yīng)時間等方面考慮。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ìn)程優(yōu)先數(shù)大，這樣有利于縮短作業(yè)完成的時間；交互式用戶的進(jìn)程優(yōu)先數(shù)大，這樣有利于終端用戶的響應(yīng)時間等等,

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

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

計算公式

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

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

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

一個三級反饋隊列調(diào)度策略

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

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

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

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

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

彩票調(diào)度法有趣特性：反映迅速，合作進(jìn)程可交換彩票。彩票調(diào)度算法(3)彩票調(diào)度可以解決其他算法難以解決的問題。例如，一個視頻服務(wù)器。2.7.3實時調(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)一樣糟糕。硬實時系統(tǒng)和軟實時系統(tǒng)實時系統(tǒng)通常分為硬實時（hardrealtime）系統(tǒng)和軟實時（softrealtime）系統(tǒng)。前者意味著存在必須滿足的時間限制；后者意味著偶爾超過時間限制時可以容忍的。

周期性和非周期性事件實時系統(tǒng)響應(yīng)的事件可劃分為周期性事件和非周期性事件。例如，m個周期性事件，事件i的周期為Pi，每個事件需要Ci秒的CPU時間來處理，則只有滿足以下條件：

C1/P1+C2/P2+…+Cm/Pm≤1

時，才可能處理所有的負(fù)載。滿足該條件的實時系統(tǒng)稱作任務(wù)可調(diào)度可的（schedulable）。軟實時系統(tǒng)一個軟實時系統(tǒng)處理三個事件流，其周期分別為100ms，200ms和500ms，如果事件處理時間分別為50ms，30ms和100ms，則這個系統(tǒng)是可調(diào)度的，因為0.5+0.15+0.2≤1如果加入周期為1秒的第4個事件，則只要其處理時間不超過150ms，該系統(tǒng)仍將時可調(diào)度的。

實時調(diào)度算法(1)

1）單比率調(diào)度算法基本思想：為每個進(jìn)程分配一個與事件發(fā)生頻率成正比的優(yōu)先數(shù)。例如，周期為20ms的進(jìn)程優(yōu)先數(shù)為50，周期為100ms的進(jìn)程優(yōu)先數(shù)為10，運行時調(diào)度程序總是調(diào)度優(yōu)先數(shù)最高的就緒進(jìn)程，并采取搶占式分配策略。實時調(diào)度算法(2)

2）限期調(diào)度算法

基本思想：當(dāng)一個事件發(fā)生時，對應(yīng)的進(jìn)程就按照截止期限被加入就緒進(jìn)程隊列。對于一個周期性事件，其截止期限即為事件下一次發(fā)生的時間。該調(diào)度算法首先運行隊首進(jìn)程，即截止時間最近的那個進(jìn)程。實時調(diào)度算法(3)

3）最少裕度法

基本思想：首先計算各個進(jìn)程的富裕時間，即裕度（laxity），然后選擇裕度最少的進(jìn)程執(zhí)行。裕度=截止時間-(就緒時間+計算時間)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)中多個進(jìn)程之間同步的頻率，它是刻畫多處理系統(tǒng)特征和描述進(jìn)程并發(fā)度的一個重要指標(biāo)。同步粒度的劃分

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

?中粒度（medium-grained）：

?粗粒度（coarse-grained）：

?超粗粒度（verycoarse-grained）：

?獨立（independent）：

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

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

實驗證明，隨著處理器數(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)程并不分配給一個特定處理器，系統(tǒng)維護一個全局性就緒線程隊列，當(dāng)一個處理器空閑時，就選擇一個就緒線程占有處理器運行。多處理器調(diào)度算法(4)

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

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

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

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

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