計(jì)算機(jī)操作系統(tǒng)原理教程第6章 CPU調(diào)度

韓都衣舍官方旗艦店

韓都衣舍女裝您值得擁有

/

好狗友

/

廣東韓都衣舍批發(fā)

/

韓都衣舍旗艦店

/

1第6章CPU調(diào)度主要內(nèi)容基本概念調(diào)度準(zhǔn)則調(diào)度算法多處理器調(diào)度實(shí)時(shí)調(diào)度算法評(píng)估進(jìn)程調(diào)度模型26.1基本概念1、CPU-I/O區(qū)間周期進(jìn)程的觀測(cè)屬性：進(jìn)程執(zhí)行由CPU執(zhí)行和I/O等待周期組成。CPU區(qū)間－I/O區(qū)間－CPU區(qū)間－I/O區(qū)間－……－CPU區(qū)間通常具有大量短CPU區(qū)間和少量長(zhǎng)CPU區(qū)間2、CPU調(diào)度程序當(dāng)CPU變?yōu)榭臻e時(shí)，操作系統(tǒng)必須從就緒隊(duì)列中選擇一個(gè)進(jìn)程來執(zhí)行，進(jìn)程選擇是由CPU調(diào)度程序來執(zhí)行的，又稱為短期調(diào)度程序（short-termscheduler）就緒隊(duì)列可實(shí)現(xiàn)為FIFO隊(duì)列、優(yōu)先隊(duì)列、樹或無序鏈表等形式33、可搶占式調(diào)度CPU調(diào)度決策發(fā)生的環(huán)境當(dāng)一個(gè)進(jìn)程從運(yùn)行狀態(tài)切換到等待狀態(tài)當(dāng)一個(gè)進(jìn)程從運(yùn)行狀態(tài)切換到就緒狀態(tài)當(dāng)一個(gè)進(jìn)程從等待狀態(tài)切換到就緒狀態(tài)當(dāng)一個(gè)進(jìn)程終止時(shí)非搶占（nonpreemptive）調(diào)度（1、4情況）可搶占（preemptive）調(diào)度（2、3情況）可搶占調(diào)度的代價(jià)共享數(shù)據(jù)的不一致性問題影響操作系統(tǒng)內(nèi)核的設(shè)計(jì)44、分派程序分派程序負(fù)責(zé)將CPU的控制交給由短期調(diào)度程序所選擇的進(jìn)程，其功能包括：切換上下文切換到用戶模式跳轉(zhuǎn)到用戶程序的合適位置以重新啟動(dòng)這個(gè)程序分派延遲（dispatchlatency）：分派程序停止一個(gè)進(jìn)程而啟動(dòng)另一個(gè)進(jìn)程執(zhí)行所要花費(fèi)的時(shí)間56.2調(diào)度準(zhǔn)則常用的調(diào)度準(zhǔn)則CPU使用率：CPU實(shí)際使用時(shí)間與總占用時(shí)間之比吞吐量：一個(gè)時(shí)間單元內(nèi)所完成進(jìn)程的數(shù)量周轉(zhuǎn)時(shí)間：從進(jìn)程提交到進(jìn)程完成的時(shí)間間隔等待時(shí)間：在就緒隊(duì)列中等待所花時(shí)間之和響應(yīng)時(shí)間：從提交請(qǐng)求到產(chǎn)生第一響應(yīng)的時(shí)間希望最大化CPU使用率和吞吐量，最小化周轉(zhuǎn)時(shí)間、等待時(shí)間和響應(yīng)時(shí)間絕大多數(shù)情況下，要優(yōu)化平均度量值有時(shí)需要優(yōu)化最小值或最大值本書使用平均等待時(shí)間來度量（有時(shí)用平均周轉(zhuǎn)時(shí)間）66.3調(diào)度算法1、先到先服務(wù)調(diào)度（first-come,first-served,FCFS）先請(qǐng)求CPU的進(jìn)程被首先分配到CPU，可用FIFO隊(duì)列來實(shí)現(xiàn)平均等待時(shí)間通常相當(dāng)長(zhǎng)非搶占調(diào)度例

進(jìn)程

區(qū)間時(shí)間P124P23P33P1P2P30242730平均等待時(shí)間(0+24+27)/3=17P2P3P103630平均等待時(shí)間(0+3+6)/3=372、最短作業(yè)優(yōu)先調(diào)度（shortest-job-first,SJF）當(dāng)CPU可用時(shí)，賦給具有最短后續(xù)CPU區(qū)間（最短下一個(gè)CPU區(qū)間）的進(jìn)程；如果兩個(gè)進(jìn)程具有同樣長(zhǎng)度的CPU區(qū)間，可使用FCFS調(diào)度來處理SJF調(diào)度算法最佳，平均等待時(shí)間最短困難：如何確定下一個(gè)CPU請(qǐng)求的長(zhǎng)度指數(shù)平均（exponentialaverage）n+1=tn+(1-)n常用于長(zhǎng)期調(diào)度，短期調(diào)度很難實(shí)現(xiàn)SJF算法可能是搶占或非搶占的，可搶占SJF調(diào)度有時(shí)稱為最短剩余時(shí)間優(yōu)先（shortest-remaining-time-first）調(diào)度8非搶占調(diào)度例：進(jìn)程

區(qū)間時(shí)間P16P28P37P43搶占調(diào)度例：進(jìn)程

到達(dá)時(shí)間

區(qū)間時(shí)間P108P214P329P435P4P1P3P2P1P2P4P1P30391624平均等待時(shí)間：(3+16+9+0)/4=7015101726平均等待時(shí)間：((10-1)+(1-1)+(17-2)+(5-3))/4=7.7591、設(shè)作業(yè)J1和J2的運(yùn)行時(shí)間t1<=t2，當(dāng)采用短作業(yè)優(yōu)先時(shí)，調(diào)度順序?yàn)镴1、J2，平均周轉(zhuǎn)時(shí)間為(t1+(t1+t2))/2=(2t1+t2)/2。不采用短作業(yè)優(yōu)先時(shí)，調(diào)度順序?yàn)镴2、J1，平均周轉(zhuǎn)時(shí)間為(t2+(t2+t1))/2＝(t1+2t2)/2。顯然，得證。2、假設(shè)當(dāng)n=k時(shí)成立，則當(dāng)n=k+1時(shí)，J1，J2，……，Jk，Jk+1，它們的運(yùn)行時(shí)間分別為：t1，t2，……，tk，

tk+1。(ti<=

ti+1)當(dāng)采用短作業(yè)優(yōu)先時(shí)，調(diào)度順序?yàn)镴1，J2，……，Jk，Jk+1，所有作業(yè)的平均周轉(zhuǎn)時(shí)間為：T=[T1+T2+…+Tk+Tk+1]/n=

[t1+(t1+t2)+…+(t1+t2+…+tk)+(t1+t2+…+tk+tk+1)]/n不采用短作業(yè)優(yōu)先時(shí)，假設(shè)調(diào)度順序?yàn)镴1,J2,…,Jk+1,Jk。

所有作業(yè)的平均周轉(zhuǎn)時(shí)間為：T’=[T1+T2+…+Tk+1+Tk]/n=

[t1+(t1+t2)+…+(t1+t2+…+tk+1)+(t1+t2+…+tk+1+tk)]/n則：T’-T=[(tk+1+tk+1+tk)-(tk+tk+tk+1)]/n=(tk+1-tk)/n>=0。

得證。證明：采用SJF調(diào)度算法可以使平均周轉(zhuǎn)時(shí)間最少。10補(bǔ)充：最高響應(yīng)比優(yōu)先算法響應(yīng)比R=周轉(zhuǎn)時(shí)間/執(zhí)行時(shí)間=（執(zhí)行時(shí)間＋等待時(shí)間）/執(zhí)行時(shí)間每次調(diào)度前計(jì)算響應(yīng)比，選值最高的調(diào)度執(zhí)行，例：A運(yùn)行完，計(jì)算BCD的響應(yīng)比：B=(70+50)/50=2.4；C=(60+10)/10=7；D=(10+20)/20=1.5。調(diào)度C。C運(yùn)行完，計(jì)算BD的響應(yīng)比：B=(80+50)/50=2.6；D=(20+20)/20=2。先調(diào)度B后調(diào)度D。進(jìn)程提交時(shí)間執(zhí)行時(shí)間A8:00120B8:5050C9:0010D9:5020開始時(shí)間結(jié)束時(shí)間等待時(shí)間周轉(zhuǎn)時(shí)間8:0010:00012010:1011:008013010:0010:10607011:0011:207090平均52.5102.5113、優(yōu)先權(quán)調(diào)度（priority-schedulingalgorithm）每個(gè)進(jìn)程都有一個(gè)優(yōu)先權(quán)與其關(guān)聯(lián)，具有最高優(yōu)先權(quán)的進(jìn)程會(huì)被分配到CPU。具有相同優(yōu)先權(quán)的進(jìn)程按FCFS順序調(diào)度低數(shù)字表示高優(yōu)先權(quán)優(yōu)先權(quán)定義：內(nèi)部或外部?jī)?yōu)先權(quán)調(diào)度可以是搶占或非搶占優(yōu)先權(quán)調(diào)度的一個(gè)主要問題：無窮阻塞（indefiniteblocking）或稱為饑餓（starvation），即低優(yōu)先權(quán)進(jìn)程可能無窮等待饑餓的解決方案：老化（aging）即逐漸增加在系統(tǒng)中等待很長(zhǎng)時(shí)間的進(jìn)程的優(yōu)先權(quán)，例如UNIX系統(tǒng)中，每秒計(jì)算一次優(yōu)先權(quán)：

p_pri=min{127,(p_cpu/16+PUSER+p_nice)}

每過一個(gè)時(shí)鐘嘀嗒加1用戶優(yōu)先權(quán)基數(shù)調(diào)節(jié)參數(shù)12優(yōu)先權(quán)調(diào)度例:進(jìn)程

區(qū)間時(shí)間

優(yōu)先權(quán)P1103P211P324P415P552P2P5P1P3P4016161819平均等待時(shí)間：(6+0+16+18+1)/5=8.213優(yōu)先權(quán)調(diào)度練習(xí)進(jìn)程到達(dá)時(shí)間CPU區(qū)間時(shí)間優(yōu)先級(jí)

P1833P2911P31023P41114P51242注：搶占和非搶占兩種情況141）搶占式P1P2P1P5P3P4891012161819平均等待時(shí)間:[(0+(10-9))+0+(16-10)+(18-11)+0]/5=2.8進(jìn)程到達(dá)時(shí)間CPU區(qū)間時(shí)間優(yōu)先級(jí)

P1833P2911P31023P41114P51242152）非搶占式P1P2P5P3P481112161819平均等待時(shí)間:[(0+(11-9))+(16-10)+(18-11)+0]/5=3進(jìn)程到達(dá)時(shí)間CPU區(qū)間時(shí)間優(yōu)先級(jí)

P1833P2911P31023P41114P51242164、輪轉(zhuǎn)法調(diào)度（round-robin,RR）類似于FCFS調(diào)度，但通過為每個(gè)進(jìn)程分配時(shí)間量（timequantum）或稱為時(shí)間片，增加搶占以在進(jìn)程間切換CPU調(diào)度程序循環(huán)就緒隊(duì)列，為每個(gè)進(jìn)程分配不超過一個(gè)時(shí)間片間隔的CPU平均等待時(shí)間通常相當(dāng)長(zhǎng)RR調(diào)度算法是可搶占的性能很大程度上依賴于時(shí)間片的大小例(時(shí)間片為4ms)：

進(jìn)程

區(qū)間時(shí)間P124P23P33P1P2P3P1P1P1P1P1047101418222630平均等待時(shí)間:[(0+(10-4))+4+7]/3=5.6617輪轉(zhuǎn)法調(diào)度練習(xí)（時(shí)間片為2、5）進(jìn)程CPU區(qū)間時(shí)間

P110P21P32P41P55181）時(shí)間片為2P1P2P3P4P5P1P5P1P5P1P1023568101214151819平均等待時(shí)間:{[(0+(8-2))+(12-10)+(15-14)]+2+3+5+[6+(14-12)+(10-8)]}/5=5.8進(jìn)程CPU區(qū)間時(shí)間

P110P21P32P41P55192）時(shí)間片為5P1P2P3P4P5P1056891419平均等待時(shí)間:[(0+(14-5))+5+6+8+9]/5=7.4進(jìn)程CPU區(qū)間時(shí)間

P110P21P32P41P55205、多級(jí)隊(duì)列調(diào)度

（multilevelqueue-schedulingalgorithm）根據(jù)進(jìn)程的某些屬性，將其永久的分配到一個(gè)隊(duì)列，每個(gè)隊(duì)列有自己的調(diào)度算法隊(duì)列之間通常采用固定優(yōu)先權(quán)可搶占調(diào)度來實(shí)現(xiàn)也可以在隊(duì)列之間劃分時(shí)間片216、多級(jí)反饋隊(duì)列調(diào)度（multilevelfeedbackqueuescheduling）多級(jí)隊(duì)列調(diào)度算法中，進(jìn)程進(jìn)入系統(tǒng)后，被永久的分配到一個(gè)隊(duì)列，優(yōu)點(diǎn)是低調(diào)度開銷，缺點(diǎn)是不夠靈活多級(jí)反饋隊(duì)列調(diào)度允許進(jìn)程在隊(duì)列之間移動(dòng)，根據(jù)不同CPU區(qū)間特點(diǎn)以區(qū)分進(jìn)程定義時(shí)需要考慮的參數(shù)隊(duì)列數(shù)量每個(gè)隊(duì)列的調(diào)度算法用以確定何時(shí)升級(jí)到較高優(yōu)先權(quán)隊(duì)列的方法用以確定進(jìn)程何時(shí)降級(jí)到較低優(yōu)先權(quán)隊(duì)列的方法用以確定進(jìn)程在需要服務(wù)時(shí)應(yīng)進(jìn)入哪個(gè)隊(duì)列的方法最通用的CPU調(diào)度算法，但也是最復(fù)雜的22常用調(diào)度算法小結(jié)先來先處理（FCFS）——非搶占最短作業(yè)優(yōu)先（SJF）優(yōu)先權(quán)搶占或非搶占時(shí)間片輪轉(zhuǎn)（RR）——搶占多級(jí)隊(duì)列多級(jí)反饋隊(duì)列236.4多處理器調(diào)度限定同構(gòu)系統(tǒng)，即處理器功能相同任何可用處理器可用于運(yùn)行隊(duì)列內(nèi)的任何進(jìn)程通用內(nèi)存訪問（uniformmemoryaccess,UMA）負(fù)載分配（loadsharing）為每個(gè)處理器提供獨(dú)立的隊(duì)列使用一個(gè)共同就緒隊(duì)列針對(duì)2）的兩種調(diào)度方法每個(gè)處理器自我調(diào)度主－從結(jié)構(gòu)，即選擇一個(gè)處理器為其他處理器進(jìn)行調(diào)度非對(duì)稱多處理（asymmetricmultiprocessing）：主服務(wù)器246.5實(shí)時(shí)調(diào)度實(shí)時(shí)計(jì)算分為硬實(shí)時(shí)（hardreal-time）和軟實(shí)時(shí)（softreal-time）實(shí)現(xiàn)軟實(shí)時(shí)功能要求系統(tǒng)必須有優(yōu)先權(quán)調(diào)度，且實(shí)時(shí)進(jìn)程必須有最高的優(yōu)先權(quán)分派延遲必須小為了讓分派延遲保持很小，需要允許系統(tǒng)可搶占，實(shí)現(xiàn)方法有在長(zhǎng)時(shí)間系統(tǒng)調(diào)用內(nèi)插入搶占點(diǎn)（preemptionpoint）－內(nèi)核安全位置使整個(gè)內(nèi)核可搶占－同步機(jī)制保護(hù)內(nèi)核數(shù)據(jù)結(jié)構(gòu)254、實(shí)時(shí)調(diào)度策略優(yōu)先級(jí)+時(shí)間片輪轉(zhuǎn)調(diào)度：獲得秒級(jí)的響應(yīng)時(shí)間基于優(yōu)先權(quán)的非搶占調(diào)度：數(shù)秒~數(shù)百毫秒級(jí)的響應(yīng)時(shí)間基于優(yōu)先權(quán)的固定點(diǎn)搶占調(diào)度：數(shù)十毫秒級(jí)基于優(yōu)先權(quán)的立即搶占調(diào)度：獲得毫秒級(jí)的響應(yīng)時(shí)間時(shí)限調(diào)度算法時(shí)限要求最近的任務(wù)優(yōu)先占用處理機(jī)最少裕度調(diào)度算法：選擇裕度（laxity）最少的進(jìn)程執(zhí)行裕度=截止時(shí)間-(就緒時(shí)間+計(jì)算時(shí)間)266.7進(jìn)程調(diào)度模型Solaris2：基于優(yōu)先級(jí)的、可搶占的進(jìn)程調(diào)度Windows2000：基于優(yōu)先權(quán)的、可搶占的調(diào)度算法Linux分時(shí)：優(yōu)先權(quán)的、基于信用度的調(diào)度算法實(shí)時(shí)：先到先處理（FCFS）和輪轉(zhuǎn)（RR）每一次定時(shí)器中斷，信用減1，當(dāng)信用減為0時(shí)，暫停該進(jìn)程，其它進(jìn)程搶占若無可運(yùn)行進(jìn)程有信用，重新計(jì)算所有進(jìn)程的信用：信用=信用/2+優(yōu)先級(jí)每次調(diào)度選擇信用多的進(jìn)程27綜合練習(xí)題進(jìn)程到達(dá)時(shí)間CPU區(qū)間時(shí)間優(yōu)先級(jí)

P10202P25153P31051P415104

FCFS、SJF（搶占、非搶占）、優(yōu)先級(jí)（搶占、非搶占）、RR（時(shí)間片＝5）281、FCFSP1P2P3P4020354050平均等待時(shí)間:[0+(20-5)+(35-10)+(40-15)]/4=65/4=16.25進(jìn)程到達(dá)時(shí)間CPU區(qū)間時(shí)間優(yōu)先級(jí)

P10202P25153P31051P415104292、SJF（非搶占）P1P3P4P2020253550平均等待時(shí)間:[0+(35-5)+(20-10)+(25-15)]/4=50/4=12.5進(jìn)程到達(dá)時(shí)間CPU區(qū)間時(shí)間優(yōu)先級(jí)

P10202P25153P31051P415104302、SJF（搶占）P1P3P1P4P201015253550平均等待時(shí)間:[(0+(15-10))+(35-5)+(10-10)+(25-15)]=45/4=11.25進(jìn)程到達(dá)時(shí)間CPU區(qū)間時(shí)間優(yōu)先級(jí)

P10202P25153P31051P415104313、優(yōu)先級(jí)（非搶占）P1P3P2P4020254050平均等待時(shí)間:[0+(25-5)+(20-10)+(40-15)]/4=55/4=13.75進(jìn)程到達(dá)時(shí)間CPU區(qū)間時(shí)間優(yōu)先級(jí)

P10202P2