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

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

最小化等待時(shí)間

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

進(jìn)程

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

P124

P23

P33

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

那么Gantt圖為:

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

等待時(shí)間：

P1=6;

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

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

進(jìn)程

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

CPU區(qū)間長(zhǎng)度

P1

0.0 7

P22.0 4

P34.0 1

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

進(jìn)程

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

CPU區(qū)間長(zhǎng)度

P1

0.0 7

P22.0 4

P34.0 1

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

=0

n+1=n近來(lái)的歷史對(duì)預(yù)測(cè)沒(méi)有影響

=1

n+1=tn只參考前一個(gè)CPU區(qū)間的實(shí)際長(zhǎng)度如果展開(kāi)公式，得到：

n+1=tn

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

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

0因?yàn)?/p>

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

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

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

FIFOq很小

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

Process

CPU區(qū)間長(zhǎng)度

P153

P217

P368

P424Gantt圖為：

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

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

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

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

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

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

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

...

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

Priority

Comment

Thread.MIN_PRIORITY

最低優(yōu)先級(jí)

Thread.MAX_PRIORITY

最高優(yōu)先級(jí)

Thread.NORM_PRIORITY