2.5處理機調度

2.5.1處理機調度的層次2.5.3高級調度2.5.3中級調度2.5.4低級調度2.5.5選擇調度算法的原則

2.5.1處理機調度的層次

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

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

有兩類低級調度方式：第一類稱剝奪方式：

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

處理器調度的層次

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

高級調度中級調度低級調度運行態(tài)就緒態(tài)終止態(tài)新建態(tài)掛起就緒態(tài)中級調度掛起等待態(tài)等待態(tài)高級調度高級調度中級調度處理器的調度模型

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

l

資源利用率

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

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

2

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

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

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

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

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

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

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

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

作業(yè)帶權周轉時間如果作業(yè)i的周轉時間為ti，所需運行時間為tk，則稱wi=ti/tk為該作業(yè)的帶權周轉時間。ti是等待時間與運行時間之和，故帶權周轉時間總大于1。平均作業(yè)帶權周轉時間W=(Σwi)/n衡量調度算法的調度性能用平均作業(yè)周轉時間來衡量對同一作業(yè)流施行不同作業(yè)調度算法時，它們呈現(xiàn)的調度性能；用平均作業(yè)帶權周轉時間來衡量對不同作業(yè)流施行同一作業(yè)調度算法時，它們呈現(xiàn)的調度性能。這兩個數(shù)值均2.6批處理作業(yè)的管理與調度

2.6.1作業(yè)和進程的關系2.6.2批處理作業(yè)的管理2.6.3批處理作業(yè)的調度2.6.4作業(yè)調度算法2.6.1作業(yè)和進程的關系(1)

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

作業(yè)是任務實體，進程是完成任務的執(zhí)行實體;沒有作業(yè)任務，進程無事可干，沒有進程，作業(yè)任務沒法完成。作業(yè)概念更多地用在批處理操作系統(tǒng)，而進程則可以用在各種多道程序設計系統(tǒng)。2.6.2批處理作業(yè)的管理

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

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

JCB的主要內容包括：

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

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

1

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

先來先服務算法(2)

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

?若三個作業(yè)提交順序改為作業(yè)2、1、3，平均作業(yè)周轉時間約為29。若三個作業(yè)提交順序改為作業(yè)3、2、1，平均作業(yè)周轉時間約為18。FCFS調度算法的平均作業(yè)周轉時間與作業(yè)提交的順序有關。2

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

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

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

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

平均帶權作業(yè)周轉時間W=(4/4+12/8+21/9+31/10)/4=1.98

J2

J4

J1

J3

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

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

平均帶權作業(yè)周轉時間

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

J1

J2J3

J4

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

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

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

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

Job108Job214Job329Job435

SJF算法進一步討論(3)

J1J2J4J1J3015101726SJF算法進一步討論(4)

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

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

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

響應比定義

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

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

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

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

HRRF算法舉例(3)

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

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

HRRF算法舉例(4)

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

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

HRRF算法舉例(5)

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

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

平均帶權作業(yè)周轉時間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)綜合考慮有關因素來確定用戶作業(yè)的優(yōu)先數(shù)。5

分類調度算法

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

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

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

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

低級調度的主要功能

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

2.7.2低級調度算法

1

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

時間片輪轉調度算法(1)

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

時間片輪轉調度算法(2)

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

P1P2P3P1P2

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

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

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

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

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

優(yōu)先權調度(2)

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

計算公式

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

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

多級反饋隊列調度

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

一個三級反饋隊列調度策略

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

保證調度算法(1)

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

彩票調度算法(1)

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

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

實時操作系統(tǒng)的特性實時系統(tǒng)是那些時間因素非常關鍵的系統(tǒng)。實時系統(tǒng)包括監(jiān)控系統(tǒng)、自動駕駛系統(tǒng)、安全控制系統(tǒng)等，這些系統(tǒng)中，遲到的響應即使正確，也和沒有響應一樣糟糕。硬實時系統(tǒng)和軟實時系統(tǒng)實時系統(tǒng)通常分為硬實時（hardrealtime）系統(tǒng)和軟實時（softrealtime）系統(tǒng)。前者意味著存在必須滿足的時間限制；后者意味著偶爾超過時間限制時可以容忍的。

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

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

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

實時調度算法(1)

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

2）限期調度算法

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

3）最少裕度法

基本思想：首先計算各個進程的富裕時間，即裕度（laxity），然后選擇裕度最少的進程執(zhí)行。裕度=截止時間-(就緒時間+計算時間)2.7.4多處理器調度

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

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

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

同步的粒度

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

?細粒度（fine-grained）：

?中粒度（medium-grained）：

?粗粒度（coarse-grained）：

?超粗粒度（verycoarse-grained）：

?獨立（independent）：

多處理器調度的設計要點

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

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

1）負載共享調度算法

基本思想：進程并不分配給一個特定處理器，系統(tǒng)維護一個全局性就緒線程隊列，當一個處理器空閑時，就選擇一個就緒線程占有處理器運行。多處理器調度算法(4)

負載共享調度算法優(yōu)點?

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

多處理器調度算法(5)

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

負載共享調度算法不足?