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

1、淮海工學院計算機科學系,第三章 處理機調(diào)度與死鎖,3.1 處理機調(diào)度的基本概念 3.2 調(diào)度算法 3.3 實時調(diào)度 3.4 多處理機系統(tǒng)中的調(diào)度 3.5 產(chǎn)生死鎖的原因和必要條件 3.6 預(yù)防死鎖的方法 3.7 死鎖的檢測與解除,淮海工學院計算機科學系,作業(yè)的狀態(tài)及其轉(zhuǎn)換,批處理系統(tǒng)才有作業(yè)的概念，分時系統(tǒng)沒有作業(yè)的概念；作業(yè)的狀態(tài)分為：提交、后備、運行和完成,3.1 處理機調(diào)度的基本概念,淮海工學院計算機科

2、學系,提交狀態(tài)：作業(yè)在輸入設(shè)備上并準備進入外存輸入井前的狀態(tài)。用戶作業(yè)通常包括：程序、數(shù)據(jù)和作業(yè)說明書后備狀態(tài)：由SPOOLing輸入程序輸入到外存輸入井中，為其建立作業(yè)控制塊（JCB），并將JCB插入到后備作業(yè)隊列中的狀態(tài)運行狀態(tài)：作業(yè)被作業(yè)調(diào)度程序選中，由外存輸入井調(diào)入到內(nèi)存，為其分配了所需的資源并建立了進程，此時作業(yè)就進入到運行狀態(tài)。完成狀態(tài)：當作業(yè)正常結(jié)束或異常終止時，就進入完成狀態(tài)。由作業(yè)調(diào)度程序做收尾工作：撤銷JCB、

3、回收分給該作業(yè)的系統(tǒng)資源等。,淮海工學院計算機科學系,作業(yè)的狀態(tài)及其轉(zhuǎn)換,,,,,,,,提交,,,后備,,,運行,,,就緒,,,阻塞,,,就緒,,,阻塞,,,完成,,,,,,,,,,,,,,,,,SPOOLing,程序,作業(yè)調(diào)度程序,進程調(diào)度,程序,,,,,,中級調(diào)度,,外存,,外存輸,入井,,輸入設(shè),備,,內(nèi)存,,,,,,,淮海工學院計算機科學系,在多道批處理系統(tǒng)中，一個作業(yè)可能需要經(jīng)歷三級調(diào)度： 1. 高級調(diào)度（High Sche

4、duling) 高級調(diào)度又稱為作業(yè)調(diào)度或宏觀調(diào)度或長程調(diào)度（多道批處理系統(tǒng)需要作業(yè)調(diào)度；分時系統(tǒng)和實時系統(tǒng)一般不需要高級調(diào)度。 ）2. 中級調(diào)度(Intermediate-Level Scheduling) 引入中級調(diào)度的主要目的是為了提高內(nèi)存的利用率和系統(tǒng)吞吐量。3.低級調(diào)度(Low Level Scheduling) 低級調(diào)度又稱進程調(diào)度或微觀調(diào)度或短程調(diào)度,3.1.1 處理機調(diào)度的層

5、次,淮海工學院計算機科學系,4、進程調(diào)度方式,非搶占方式（Nonpreemptive）：在這種調(diào)度方式下，一旦一個進程被選中運行，它就一直運行下去，直到它運行結(jié)束并自愿放棄CPU，或者因等待某一事件而被阻塞或終止時為止，才把CPU出讓給其他進程，即得到CPU的進程不管運行多長時間，都一直運行下去，不會因為當前進程以外的原因而被迫讓出CPU。引起調(diào)度的原因：1）當前進程運行結(jié)束或發(fā)生某事件而終止；2）當前進程因提出I/O請求而阻塞；3）

6、進程之間通信或同步而由于執(zhí)行原語而等待。,淮海工學院計算機科學系,搶占方式（Preemptive）：搶占方式允許調(diào)度程序根據(jù)某種策略中止當前進程的執(zhí)行，將其移入就緒隊列，并將處理機分派給另一個進程使之投入運行。 搶占原則：1）優(yōu)先權(quán)原則：允許高優(yōu)先權(quán)進程搶占低優(yōu)先權(quán)的CPU；2）短作業(yè)原則：允許短進程搶占長進程的處理機；3）時間片原則：分時系統(tǒng)中的當前進程，若時間片規(guī)定的時間用完，不管是否運行結(jié)束，都要立即中止放到就緒隊列中，再將CP

7、U分派給其它進程。,淮海工學院計算機科學系,3.1.2 調(diào)度隊列模型,不同OS對高級、中級和低級調(diào)度的選取形成了不同的調(diào)度隊列模型，共有3種類型。1.僅有進程調(diào)度的調(diào)度隊列模型 2. 具有高級和低級調(diào)度的調(diào)度隊列模型3. 同時具有三級調(diào)度的調(diào)度隊列模型,淮海工學院計算機科學系,,具有三級調(diào)度時的調(diào)度隊列模型,淮海工學院計算機科學系,3.1.3 選擇調(diào)度方式和調(diào)度算法的若干準則,1. 面向用戶的準則,周轉(zhuǎn)時間短：周轉(zhuǎn)時間是指作業(yè)從提

8、交給系統(tǒng)開始，到作業(yè)完成為止所消耗的時間。常用于衡量系統(tǒng)性能、作業(yè)調(diào)度算法的優(yōu)劣的重要指標。,可把平均周轉(zhuǎn)時間描述為：,作業(yè)的周轉(zhuǎn)時間T與系統(tǒng)為它提供服務(wù)的時間TS之比，即W=T/TS，稱為帶權(quán)周轉(zhuǎn)時間，而平均帶權(quán)周轉(zhuǎn)時間則可表示為:,淮海工學院計算機科學系,響應(yīng)時間快：分時系統(tǒng)性能的主要評價指標。響應(yīng)時間指用戶從鍵盤鍵入一個命令開始，到系統(tǒng)首次給出響應(yīng)信息為止這段時間。截止時間的保證：評價實時系統(tǒng)性能的重要指標。截止時間是指系統(tǒng)為處

9、理某事件/任務(wù)必須開始執(zhí)行的最遲時間，或必須完成的最遲時間。 優(yōu)先權(quán)準則：批處理、分時和實時系統(tǒng)中的調(diào)度算法都應(yīng)該遵循的原則。這種調(diào)度思想就是“急事急辦”，優(yōu)先權(quán)高者為急。,淮海工學院計算機科學系,2. 面向系統(tǒng)的準則,系統(tǒng)吞吐量高：評價批處理系統(tǒng)整體性能的重要指標。吞吐量是指單位時間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)。作業(yè)調(diào)度算法對系統(tǒng)吞吐量有直接影響，選擇確定時應(yīng)考慮這一準則。處理機利用率好：CPU的利用率是衡量大中型系統(tǒng)性能的重要指標。

10、各類資源的平衡利用：選擇適當調(diào)度算法，保證各種資源的利用都處于忙碌狀態(tài)。,,淮海工學院計算機科學系,3.2 調(diào)度算法,1、先來先服務(wù)（FCFS）調(diào)度算法適應(yīng)范圍：適應(yīng)作業(yè)調(diào)度和進程調(diào)度；調(diào)度過程：FCFS用于作業(yè)（進程）調(diào)度時，從后備（就緒）隊列中選擇若干或一個先到來的作業(yè)（進程）投入運行。進程在分派到CPU進入運行過程中，只有當進程運行結(jié)束或因某事件發(fā)生而被阻塞才放棄CPU。算法特點：算法容易實現(xiàn)，但效率不高；只顧及作業(yè)等候時

11、間，沒考慮作業(yè)要求服務(wù)時間的長短，不利于短作業(yè)而優(yōu)待了長作業(yè)(CPU繁忙型作業(yè))；作業(yè)調(diào)度不分輕重緩急，人人平等；FCFS為非搶占式調(diào)度。,淮海工學院計算機科學系,先來先服務(wù)（FCFS）調(diào)度算法效率舉例,表注：周轉(zhuǎn)時間=完成時間-到達時間；帶權(quán)周轉(zhuǎn)時間=周轉(zhuǎn)時間/服務(wù)時間,這兩個時間都是越小越好！,淮海工學院計算機科學系,2、短作業(yè)/進程（SJF/SPF）優(yōu)先調(diào)度算法,適應(yīng)范圍：適應(yīng)作業(yè)調(diào)度和進程調(diào)度。SJF/SPF算法以進入系統(tǒng)的作業(yè)

12、/進程所要求的CPU時間為標準，總選取估計計算時間最短的作業(yè)/進程投入運行。算法特點：算法易于實現(xiàn)，效率不高；忽視長作業(yè)等待時間，會出現(xiàn)饑餓現(xiàn)象；不考慮緊迫作業(yè)/進程的需求；長短時間人為估計，不可靠，會出現(xiàn)以長亂短。SPF算法類型：搶占或非搶占式。搶占式SPF調(diào)度算法在新進程進入就緒隊列時，將其運行時間與當前進程的剩余運行時間相比，若更短時，可搶占CPU；非搶占式SPF算法允許當前運行進程先執(zhí)行直到釋放CPU為止?？蓳屨糞PF調(diào)度有

13、時稱為最短剩余時間優(yōu)先（shortest-remaining-time-first）調(diào)度。,淮海工學院計算機科學系,FCFS和SJF調(diào)度算法的性能分析,淮海工學院計算機科學系,例題：假如5個就緒進程其到達系統(tǒng)和所需CPU時間如下表所示（單位：毫秒），如果忽略I/O以及其他開銷，分別計算采用FCFS、非搶占式SPF和搶占式SPF調(diào)度算法進行CPU調(diào)度的平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。進程到達和運行時間,淮海工學院計算機科學系,解答如下：

14、（1）采用FCFS的調(diào)度順序為：,平均周轉(zhuǎn)時間為： T=((3-0)+(9-2)+(13-4)+(18-6)+(20-8))/5=8.6帶權(quán)平均周轉(zhuǎn)時間為：W=2.56,淮海工學院計算機科學系,（2）采用非搶占SJF的調(diào)度順序為：,A,B,E,C,D,0,3,9,11,15,20,平均周轉(zhuǎn)時間為：T=7.6帶權(quán)平均周轉(zhuǎn)時間為：W=1.84,淮海工學院計算機科學系,（3）采用搶占SJF的調(diào)度順序為：,平均周轉(zhuǎn)時間為：T=7.2

15、帶權(quán)平均周轉(zhuǎn)時間為：W=1.59,淮海工學院計算機科學系,3、高優(yōu)先權(quán)優(yōu)先調(diào)度算法（priority-scheduling algorithm）,1）優(yōu)先權(quán)調(diào)度算法的類型非搶占式優(yōu)先權(quán)算法：系統(tǒng)一旦把CPU分配給就緒隊列中優(yōu)先權(quán)最高的進程后，該進程便一直執(zhí)行下去，直至完成或因發(fā)生某事件使該進程放棄處理機時。主要用于批處理系統(tǒng)中；也可用于某些對實時性要求不嚴的實時系統(tǒng)中。 搶占式優(yōu)先權(quán)算法：系統(tǒng)把處理機分配給優(yōu)先權(quán)最高的進程使之執(zhí)行。

16、只要又有更高優(yōu)先權(quán)新進程進入就緒隊列，進程調(diào)度程序就立即停止當前進程的執(zhí)行，將處理機重新分配。適應(yīng)較嚴格的實時系統(tǒng)、性能要求較高的批處理和分時系統(tǒng)。,淮海工學院計算機科學系,2）優(yōu)先權(quán)的類型,靜態(tài)優(yōu)先權(quán) 靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進程時確定的，且在進程的整個運行期間保持不變。優(yōu)先權(quán)的確定準則：系統(tǒng)進程者優(yōu)先；資源需求少者優(yōu)先；用戶需求緊迫者優(yōu)先。動態(tài)優(yōu)先權(quán)：動態(tài)優(yōu)先權(quán)是指在創(chuàng)建進程時所賦予的優(yōu)先權(quán)，可以隨進程的推進而改變

17、的，以便獲得更好的調(diào)度性能。（如等待時間與優(yōu)先權(quán)成正比）,淮海工學院計算機科學系,4、高響應(yīng)比優(yōu)先調(diào)度算法,動態(tài)優(yōu)先權(quán)的變化規(guī)律可描述為：,系統(tǒng)對作業(yè)的響應(yīng)時間=等待時間+服務(wù)時間，故該優(yōu)先權(quán)又相當于響應(yīng)比RP。據(jù)此，優(yōu)先權(quán)變化規(guī)律又可表示為：,淮海工學院計算機科學系,高響應(yīng)比優(yōu)先調(diào)度算法特點：如果作業(yè)的等待時間相同，則要求服務(wù)的時間愈短，其優(yōu)先權(quán)愈高，因而該算法有利于短作業(yè)；當要求服務(wù)的時間相同時，作業(yè)的優(yōu)先權(quán)決定于其等待時間，等

18、待時間愈長，其優(yōu)先權(quán)愈高，因而它實現(xiàn)的是先來先服務(wù)；對于長作業(yè)，作業(yè)的優(yōu)先級可以隨等待時間的增加而提高，當其等待時間足夠長時，其優(yōu)先級便可升到很高， 從而也可獲得處理機，避免了長作業(yè)饑餓現(xiàn)象。,淮海工學院計算機科學系,5、基于時間片的輪轉(zhuǎn)調(diào)度算法,時間片調(diào)度算法適用于分時系統(tǒng)。劃分為時間片輪轉(zhuǎn)和多級反饋隊列調(diào)度算法1）時間片輪轉(zhuǎn)法（Round Robin）輪轉(zhuǎn)法調(diào)度做法是：系統(tǒng)將所有的就緒進程按FIFO原則排隊，每次調(diào)度時，把C

19、PU分配給隊首進程，并令其執(zhí)行一個時間片（如20ms）。當執(zhí)行的時間片用完時，停止該進程的執(zhí)行，并將它送往就緒隊尾；然后，再把處理機分配給就緒隊列中新的隊首進程，同時也讓它執(zhí)行一個時間片。如此反復(fù)和輪轉(zhuǎn)，就可以保證就緒隊列中的所有進程，在一給定的時間內(nèi)，均能獲得一時間片的處理機執(zhí)行時間。,淮海工學院計算機科學系,2）多級反饋隊列調(diào)度算法,多級反饋隊列調(diào)度算法是目前公認的一種性能比較優(yōu)良的調(diào)度算法，兼?zhèn)淞饲笆龈鞣N算法的優(yōu)點。原理如下：設(shè)

20、置多個就緒隊列，并賦予不同的優(yōu)先級和時間片：第一個隊列的優(yōu)先級最高，第二個隊列次之，其余各隊列的優(yōu)先權(quán)逐個降低。該算法賦予各個隊列中進程執(zhí)行時間片的大小也各不相同，在優(yōu)先權(quán)愈高的隊列中，為每個進程所規(guī)定的執(zhí)行時間片就愈小。圖 3-5 是多級反饋隊列算法的示意。,淮海工學院計算機科學系,多級反饋隊列調(diào)度算法,新進程進入,（64ms）,,,,淮海工學院計算機科學系,調(diào)度原則：當一個新進程進入內(nèi)存后，首先將它放入第一隊列的末尾，按FCFS原則

21、等待調(diào)度。當輪到該進程執(zhí)行時，如它能在該時間片內(nèi)完成，便可準備撤離系統(tǒng)；如果它在一個時間片結(jié)束時尚未完成，調(diào)度程序便將該進程轉(zhuǎn)入第二隊列的末尾，再同樣地按FCFS原則等待調(diào)度執(zhí)行；如果它在第二隊列中運行一個時間片后仍未完成，再依次將它放入第三隊列，……，如此下去，當一個長作業(yè)(進程)從第一隊列依次降到第n隊列后，在第n隊列中便采取按時間片輪轉(zhuǎn)的方式運行。,淮海工學院計算機科學系,搶占原則：僅當?shù)谝魂犃锌臻e時，調(diào)度程序才調(diào)度第二隊列中的

22、進程運行； 僅當?shù)?~i 隊列均空時，才會調(diào)度第i+1隊列中的進程運行。如果處理機正在第i隊列中為某進程服務(wù)時，又有新進程進入優(yōu)先權(quán)較高的隊列(第1~(i-1)中的任何一個隊列)，則此時新進程將搶占正在運行進程的處理機，即由調(diào)度程序把正在運行的進程放回到第i隊列的末尾，把處理機分配給新到的高優(yōu)先權(quán)進程。,淮海工學院計算機科學系,多級反饋隊列調(diào)度算法的性能與特點,終端型作業(yè)用戶：短小作業(yè)及時完成，用戶滿意。 (2) 短批處理作業(yè)用戶：