四川大學(xué) 計算機(jī)學(xué)院 操作系統(tǒng)課件 CPU調(diào)度

CPU調(diào)度四川大學(xué)計算機(jī)學(xué)院左劼6.2基本概念多道程序設(shè)計的目標(biāo)是任何時候都有一個進(jìn)程在運行，以使CPU使用率最大化CPU–I/O區(qū)間周期：進(jìn)程執(zhí)行由CPU執(zhí)行和I/O等待周期組成CPU區(qū)間分布CPU和I/O區(qū)間交替序列CPU區(qū)間時間直方圖CPU調(diào)度器從就緒隊列中選擇一個進(jìn)程，分配CPU資源給它，讓他開始執(zhí)行就緒隊列不一定是一個先進(jìn)先出的隊列，根據(jù)不同的調(diào)度算法，可實現(xiàn)為FIFO隊列、優(yōu)先隊列、樹等CPU調(diào)度決策發(fā)生的4種環(huán)境：1.從運行狀態(tài)切換到等待狀態(tài)2.從運行狀態(tài)切換到就緒狀態(tài)3.從等待狀態(tài)切換到就緒狀態(tài)4.進(jìn)程終止調(diào)度只能發(fā)生在1、4兩種情況的稱為非搶占調(diào)度(nonpreemptive).否則稱為可搶占的(preemptive)搶占式調(diào)度需要考慮的問題兩個進(jìn)程共享數(shù)據(jù)進(jìn)行系統(tǒng)調(diào)用或者I/O請求的時候搶占發(fā)生時，進(jìn)程可能正在進(jìn)行系統(tǒng)調(diào)用系統(tǒng)調(diào)用能否被搶占？中斷處理(幾乎任何時候都可能發(fā)生)受中斷影響的代碼必須保護(hù)禁止中斷在多CPU環(huán)境中代價很高分派程序(Dispatcher)即調(diào)度程序的執(zhí)行者進(jìn)行上下文切換切換到用戶態(tài)跳轉(zhuǎn)到用戶程序的相應(yīng)位置，并開始執(zhí)行分派延遲(Dispatchlatency)：停止一個進(jìn)程而啟動另一個進(jìn)程執(zhí)行所花費的時間6.2調(diào)度準(zhǔn)則CPU利用率：盡量讓CPU忙吞吐量：單位時間內(nèi)完成的進(jìn)程數(shù)量周轉(zhuǎn)時間：進(jìn)程從提交到完成的時間等待時間：進(jìn)程就緒隊列中等待的時間響應(yīng)時間：從進(jìn)程提交到第一次響應(yīng)的時間優(yōu)化準(zhǔn)則最大化CPU使用率最大化吞吐量最小化周轉(zhuǎn)時間

最小化等待時間

最小化響應(yīng)時間調(diào)度算法

進(jìn)程

區(qū)間時間

P124

P23

P33

假設(shè)進(jìn)程到來的順序是:P1,P2,P3

那么Gantt圖為:

等待時間：P1:0;P2:24;P3:27平均等待時間:(0+24+27)/3=17P1P2P32427300先來先服務(wù)調(diào)度假設(shè)進(jìn)程到來的順序為：P2,P3,P1，則Gantt圖為

等待時間：

P1=6;

P2=0;P3=3平均等待時間:(6+0+3)/3=3FCFS調(diào)度是非搶占的P1P3P263300最短作業(yè)優(yōu)先調(diào)度

(SJF)CPU賦給具有最短后續(xù)CPU區(qū)間的進(jìn)程兩種模式:非搶占的：一旦分配了CPU給某一個進(jìn)程的CPU區(qū)間，就只好等待它完成搶占的：如果有心的進(jìn)程進(jìn)入，并且具有更短的CPU區(qū)間長度，那么就搶占掉當(dāng)前進(jìn)程，除鞥為最短剩余時間優(yōu)先調(diào)度(Shortest-Remaining-Time-First)SJF是最優(yōu)的：對指定的進(jìn)程集合，能得到最短平均等待時間非搶占SJF的例子

進(jìn)程

到達(dá)時間

CPU區(qū)間長度

P1

0.0 7

P22.0 4

P34.0 1

P45.0 4Gantt圖為平均等待時間：(0+6+3+7)/4=4P1P3P273160P4812搶占式SJF的例子

進(jìn)程

到達(dá)時間

CPU區(qū)間長度

P1

0.0 7

P22.0 4

P34.0 1

P45.0 4Gantt圖為平均等待時間：(9+1+0+2)/4=3P1P3P242110P457P2P116如何確定下一個CPU區(qū)間的長度只能對長度進(jìn)行估計可以通過以前的CPU區(qū)間長度進(jìn)行估計，使用指數(shù)平均算法指數(shù)平均的例子

=0

n+1=n近來的歷史對預(yù)測沒有影響

=1

n+1=tn只參考前一個CPU區(qū)間的實際長度如果展開公式，得到：

n+1=tn

+(1-)tn-1+…+(1-)j

tn-j+…+(1-)n+1

0因為

和1-都小于1，后面的項的權(quán)比前面的項的權(quán)要小優(yōu)先權(quán)調(diào)度每一個進(jìn)程都有一個優(yōu)先權(quán)和其相關(guān)CPU資源分配給優(yōu)先權(quán)最高的進(jìn)搶占還是非搶占SJF是一種優(yōu)先權(quán)調(diào)度，優(yōu)先權(quán)時下以CPU區(qū)間長度的預(yù)測值問題：餓死

–低優(yōu)先級的進(jìn)程沒有機(jī)會運行解決方法：老化

–逐漸增加系統(tǒng)中等待長時間進(jìn)程的優(yōu)先級輪轉(zhuǎn)調(diào)度(Round-Robin)每一個進(jìn)程分配一小塊CPU時間單元(時間片，通常10-100毫秒)，時間片完成之后，進(jìn)程被搶占，并且被添加到就緒隊列尾部如果有n個進(jìn)程在就緒隊列中，且時間片為q，那么每個進(jìn)程會得到1/n的CPU時間，并且每輪每個長度不超過q，每個進(jìn)程必須等待的時間不超過(n-1)qq很大

FIFOq很小

處理器共享，但必須考慮q和上下文切換開銷之間的比列，不能太低。時間片為20的RR調(diào)度例子

Process

CPU區(qū)間長度

P153

P217

P368

P424Gantt圖為：

平均周轉(zhuǎn)時間比SJF高，但能得到更好的響應(yīng)時間P1P2P3P4P1P3P4P1P3P302037577797117121134154162更短的時間片導(dǎo)致更多的上下文切換周轉(zhuǎn)時間隨時間片的變化多級隊列調(diào)度(MultilevelQueue)就緒隊列被分成多個隊列每個隊列執(zhí)行自己的調(diào)度算法

隊列之間也需要執(zhí)行調(diào)度算法固定優(yōu)先級：先服務(wù)高優(yōu)先級再服務(wù)低優(yōu)先級

可能導(dǎo)致餓死時間片：給每個隊列都有一定的時間片例如80%給前臺進(jìn)程，采用RR20%給后臺，采用FCFS五個優(yōu)先級別的多級隊列多級反饋(Feedback)隊列一個進(jìn)程可以在隊列之間移動(老化算法的一種方法)多級反饋隊列的參數(shù)：隊列數(shù)量每個隊列的調(diào)度算法確定什么時候升級一個進(jìn)程的方法確定什么時候?qū)⒓壱粋€進(jìn)程的方法確定進(jìn)程需要服務(wù)時應(yīng)該進(jìn)入那一個隊列的方法一個多級反饋隊列的例子三個隊列:Q0–時間片8毫秒Q1–時間片16毫秒Q2–FCFS調(diào)度一個新作業(yè)進(jìn)入Q0隊列，并按FCFS調(diào)度，當(dāng)他獲得CPU，就得到8毫秒的時間，如果8毫秒內(nèi)沒有結(jié)束，作業(yè)就移動到隊列Q1在Q1

中仍然按照FCFS進(jìn)行調(diào)度，并且得到16毫秒的時間，如果他仍然沒有結(jié)束，將被搶占并移動到隊列

Q2多處理器(Multiple-Processor)調(diào)度當(dāng)由多個CPU的時候，CPU調(diào)度將復(fù)雜得多對稱多處理器(SymmetricMulti-processing,SMP)：每個CPU自己進(jìn)行自己的調(diào)度選擇非對稱多處理器：只有一個處理器可以訪問系統(tǒng)數(shù)據(jù)結(jié)構(gòu)，進(jìn)行調(diào)度處理，分配任務(wù)給其他的CPU，以避免對系統(tǒng)數(shù)據(jù)的共享訪問實時(Real-Time)調(diào)度硬實時系統(tǒng)：對關(guān)鍵任務(wù)的完成時間有保障軟實時系統(tǒng)：關(guān)鍵任務(wù)的優(yōu)先級比其他任務(wù)的優(yōu)先級高優(yōu)先權(quán)調(diào)度，并且要保證實時進(jìn)程的絕對優(yōu)先級分派延遲必須小因為很多系統(tǒng)有些系統(tǒng)調(diào)用很慢需要允許系統(tǒng)調(diào)用是可搶占的分派延遲線程調(diào)度本地調(diào)度：線程庫決定哪一個線程和LWP聯(lián)系起來全局調(diào)度：內(nèi)河決定下一步讓那一個內(nèi)核線程得到CPU資源進(jìn)行執(zhí)行Solaris2調(diào)度四類調(diào)度：實時，系統(tǒng)，分時和交互每一個類有不同的優(yōu)先級和調(diào)度算法分時的調(diào)度策略采用多級反饋隊列，動態(tài)地調(diào)整優(yōu)先級別和時間片的長度

交互式進(jìn)程通常具有較高的優(yōu)先級別使用系統(tǒng)類來運行內(nèi)核進(jìn)程，如調(diào)度程序和換頁后臺服務(wù)。調(diào)度策略是不分時的實時類型的線程具有最高的優(yōu)先級從類型優(yōu)先級轉(zhuǎn)換到全局優(yōu)先級Solaris2調(diào)度Java線程調(diào)度JVM使用基于優(yōu)先級的可搶占的調(diào)度算法如果有很多線程具有相同的優(yōu)先級，那么采用FIFO隊列來處理線程Java線程調(diào)度JVM進(jìn)行線程調(diào)度的時機(jī):當(dāng)前運行的線程離開可執(zhí)行狀態(tài)有一個更高優(yōu)先級的線程進(jìn)入可執(zhí)行狀態(tài)注意：JVM規(guī)范并沒有指定線程是否是分時執(zhí)行的JVM中的分時問題對于不是分時的JVM，yield()方法就需要被使用到

while(true){//執(zhí)行CPU密集任務(wù)

...

Thread.yield();}yield()方法將暫停當(dāng)前線程的執(zhí)行，讓出CPU資源給其他相同優(yōu)先級的線程這是協(xié)作式多任務(wù)的一種實現(xiàn)方式Java線程優(yōu)先級優(yōu)先級列表:

Priority

Comment

Thread.MIN_PRIORITY

最低優(yōu)先級

Thread.MAX_PRIORITY

最高優(yōu)先級

Thread.NORM_PRIORITY