《操作系統(tǒng)》第五章：CPU調(diào)度

第5章CPU調(diào)度5.1基本概念（1）什么是CPU調(diào)度？

每當CPU空閑時，操作系統(tǒng)必須按照一定的策略從

就緒隊列當中選擇一個進程來執(zhí)行。調(diào)度的對象：進程或線程。其方式與原則是一樣的。

故經(jīng)常以進程來說明：進程調(diào)度<==>CPU調(diào)度（2）CPU調(diào)度遵循什么原則？

總原則：資源高效、公平合理具體一般包括：提高CPU利用率提高系統(tǒng)運算的吞吐量縮短進程的周轉(zhuǎn)時間縮短進程的等待時間提高用戶的響應(yīng)滿意度

……5.1基本概念（3）CPU-I/O區(qū)間周期

程序代碼可以分為計算類代碼和I/O類代碼進程執(zhí)行過程由CPU執(zhí)行和I/O等待周期組成

CPU區(qū)間和I/O區(qū)間

CPU約束型程序以計算為主，CPU區(qū)間會較

多，還會有少量長的CPU區(qū)間

I/O約束型程序以I/O為主，但配合I/O處理會

有大量短的CPU區(qū)間區(qū)間區(qū)間區(qū)間區(qū)間區(qū)間區(qū)間5.1基本概念（3）CPU-I/O區(qū)間周期（續(xù)）

實驗證明：進程中短的CPU區(qū)間出現(xiàn)的幾率極高區(qū)間持續(xù)長度（ms）出現(xiàn)頻率（次數(shù)）調(diào)度情況1：因等待某些事件而讓出CPUsum(等待文件輸出)(等待文件輸出)PCB1RegistersPCB6RegistersHeadTail磁盤等待隊列PCB4RegistersPCB8RegistersPCB7RegistersHeadTail就緒隊列物理CPUPCB6RegistersPCB4Registers5.1基本概念（4）非搶占式調(diào)度與搶占式調(diào)度PCB4RegistersPCB8RegistersPCB7RegistersHeadTail就緒隊列物理CPUPCB7RegistersPCB4Registers調(diào)度情況2：規(guī)定的時間片到了

調(diào)度情況3：出現(xiàn)了優(yōu)先級更高的進程5.1基本概念（4）非搶占式調(diào)度與搶占式調(diào)度（續(xù)）PCB4RegistersPCB8RegistersPCB7RegistersHeadTail就緒隊列物理CPUPCB7RegistersPCB4Registers調(diào)度情況4：進程的任務(wù)完成了，自動終止退出僵死隊列HeadTailPCB10Registers5.1基本概念（4）非搶占式調(diào)度與搶占式調(diào)度（續(xù)）調(diào)度情況1：因等待某些事件而讓出CPU

調(diào)度情況4：進程的任務(wù)完成了，自動終止退出

非搶占式調(diào)度：由于主動讓出CPU的情況發(fā)生，致使調(diào)度程

序?qū)PU分配給某就緒進程的調(diào)度方式

早期的多道批處理操作系統(tǒng)；Windows3.X版等5.1基本概念（4）非搶占式調(diào)度與搶占式調(diào)度（續(xù)）調(diào)度情況2：規(guī)定的時間片到了

調(diào)度情況3：出現(xiàn)了優(yōu)先級更高的進程

搶占式調(diào)度：操作系統(tǒng)將正在運行的進程強行暫停，由調(diào)

度程序?qū)PU分配給其他就緒進程的調(diào)度方式

大多數(shù)現(xiàn)代操作系統(tǒng)采用：

Windows95及之后版本；MacOS-X；Linux等讓出CPU的具體實現(xiàn)externQueueReadyQueue;externQueueDiskWaitQueue;...DiskWaitQueue.EnQueue(pCur);Dispatch();...Dispatch(){

pNew=PickNext(ReadyQueue);

Switch(pCur,pNew);}分派程序調(diào)用“進程選擇函數(shù)”完成調(diào)度該函數(shù)就是CPU調(diào)度，調(diào)度就是下一步該選擇哪一個進程或線程來執(zhí)行(分配CPU資源)!進程和線程都可能是調(diào)度單位，統(tǒng)稱為任務(wù)PickNext()的直觀思考簡單想一想!應(yīng)該有很多種策略優(yōu)先級該怎么設(shè)定?Priority?FIFO?FIFO顯然是公平的策略FIFO顯然沒有考慮進程(線程)執(zhí)行的任務(wù)的區(qū)別許多算法：評價準則是什么?5.2調(diào)度準則CPU調(diào)度策略的設(shè)計準則公平性：“合理”的分配CPU響應(yīng)時間短(交互式)，周轉(zhuǎn)時間短(批處理)響應(yīng)時間:從用戶輸入到產(chǎn)生反應(yīng)的時間周轉(zhuǎn)時間:從任務(wù)開始到任務(wù)結(jié)束的時間吞吐量大吞吐量:單位時間完成的任務(wù)數(shù)量吞吐量大

CPU使用率高+上下文切換代價小周轉(zhuǎn)(響應(yīng))時間短

等待時間(在就緒隊列中的時間)短

存在矛盾的目標集合響應(yīng)時間短與公平性之間的矛盾響應(yīng)時間短

前臺任務(wù)的優(yōu)先級高前臺任務(wù)優(yōu)先調(diào)度

后臺任務(wù)得不到CPU吞吐量和響應(yīng)時間之間的矛盾吞吐量大

上下文切換代價小

時間片大時間片大

響應(yīng)時間長(1010msvs.10500ms)……協(xié)調(diào)多個目標是操作系統(tǒng)之所以復雜的一個重要原因，也是復雜系統(tǒng)的一個基本特點CPU調(diào)度應(yīng)綜合考慮

任務(wù)特點任務(wù)可以分為交互式任務(wù)和批處理任務(wù)交互式任務(wù)注重對用戶的響應(yīng)：如WORD批處理任務(wù)注重對任務(wù)吞吐量：如gcc有趣的問題是許多系統(tǒng)中既有交互式任務(wù)，又有批處理任務(wù)前臺任務(wù)+后臺任務(wù)CPU調(diào)度應(yīng)綜合考慮

任務(wù)特點(續(xù))任務(wù)的CPU-IO區(qū)間的周期特性任務(wù)生存期:I/O(載入),CPU,I/O,CPU,..,CPU(exit())CPU區(qū)間長度(ms)頻率CPU-約束I/O-約束指數(shù)衰減!CPU區(qū)間CPU區(qū)間CPU調(diào)度應(yīng)綜合考慮

調(diào)度算法的實現(xiàn)復雜調(diào)度算法vs.調(diào)度程序執(zhí)行時間兼顧許多特點會造成復雜的調(diào)度算法調(diào)度程序執(zhí)行時間應(yīng)盡量短就緒隊列的數(shù)據(jù)結(jié)構(gòu):隊列、多級隊列、樹、無序鏈表不可能設(shè)計完美的調(diào)度算法，只能根據(jù)應(yīng)用的特征進行折中權(quán)衡。這是操作系統(tǒng)等復雜系統(tǒng)的設(shè)計精髓!CPU調(diào)度應(yīng)綜合考慮……….CPU調(diào)度算法

（1）先到先服務(wù)調(diào)度FCFS

（2）最短作業(yè)優(yōu)先調(diào)度SJF

（3）優(yōu)先級調(diào)度

（4）轉(zhuǎn)輪法調(diào)度RR

（5）多級隊列調(diào)度

（6）多級反饋隊列調(diào)度5.3調(diào)度算法（1）FIFO或FirstCome,FirstServed(FCFS)調(diào)度的順序就是任務(wù)到達就緒隊列的順序調(diào)度結(jié)果P1P2P3106103942P449P5一個實例假定任務(wù)的到達順序為:P1，P2，P3，P4，P5；到達時刻都為0。任務(wù)CPU區(qū)間(ms)P110P229P33P47P512（1）FIFO或FirstCome,FirstServed(FCFS)調(diào)度的順序就是任務(wù)到達就緒隊列的順序調(diào)度結(jié)果P1P2P3106103942P449P5一個實例假定任務(wù)的到達順序為:P1，P2，P3，P4，P5；到達時刻都為0。任務(wù)CPU區(qū)間(ms)P110P229P33P47P512FCFS的分析P1P2P3106103942P449P5平均等待時間:(0+10+39+42+49)/5=28公平、簡單(FIFO隊列)、非搶占、不適合交互式P1P3P2106101342P449P5平均等待時間:(0+10+13+42+49)/5=22.8未考慮任務(wù)特性，平均等待時間可以縮短（2）ShortestJobFirst(SJF)最短的作業(yè)(CPU區(qū)間長度最小)最先調(diào)度調(diào)度結(jié)果P3P4P136101020P532P2一個實例假定任務(wù)的到達順序為:P1，P2，P3，P4，P5；到達時刻都為0。任務(wù)CPU區(qū)間(ms)P110P229P33P47P512（2）ShortestJobFirst(SJF)最短的作業(yè)(CPU區(qū)間長度最小)最先調(diào)度調(diào)度結(jié)果P3P4P136101020P532P2一個實例假定任務(wù)的到達順序為:P1，P2，P3，P4，P5；到達時刻都為0。任務(wù)CPU區(qū)間(ms)P110P229P33P47P512SJF的分析SJF可以保證最小的平均等待時間P3P4P136101020P532P2平均等待時間:(0+3+10+20+32)/5=13證明:設(shè)p1p2…pn是調(diào)度結(jié)果序列，pi是任務(wù)CPU區(qū)間大小。顯然該調(diào)度序列的平均等待時間為:

0

+p1

+p1+p2+p1+p2+p3

+….=(n-i)pi如果存在i<j而pi>pj，交換pi,pj調(diào)度順序會減小上值。

SJF:任務(wù)到達的時間有先后怎么辦?ShortestRemainingJobFirst(SRJF)SJF的可搶占版本一個實例假定任務(wù)P1，P2，P3，P4，P5的到達順序為:任務(wù)CPU區(qū)間(ms)P110P229P33P47P512到達時間(ms)005530調(diào)度結(jié)果P1P3P15610813P420P2P230P542SJF:任務(wù)到達的時間有先后怎么辦?ShortestRemainingJobFirst(SRJF)SJF的可搶占版本一個實例假定任務(wù)P1，P2，P3，P4，P5的到達順序為:任務(wù)CPU區(qū)間(ms)P110P229P33P47P512到達時間(ms)005530調(diào)度結(jié)果P1P3P15610813P420P2P230P542SJFvs.SRJF任務(wù)CPU區(qū)間(ms)P110P229P33P47P512到達時間(ms)005530P1P3P15610813P420P2P230P542P1P31061013P420P5P249SRJFSJF平均等待時間(SRJF):(3+32+0+8+0)/5=8.6平均等待時間(SJF):(0+20+5+8+19)/5=10.4搶占顯然具有優(yōu)點SJF(SRJF):如何知道下一CPU區(qū)間大小

n+1=tn+(1-

)

n|

n+1是預(yù)測值，tn是當前CPU區(qū)間根據(jù)歷史進行預(yù)測:指數(shù)平均法

n+1=tn+(1-)tn+...+(1-)j

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

0

用來控制最近信息和歷史對預(yù)測的作用

=0-忽略近期，關(guān)注歷史；

=1-只跟當前有關(guān)；通常

=0.5CPU區(qū)間(ti):64641313

13預(yù)測結(jié)果(

i-1):10866591112（3）SJF的一般化:優(yōu)先權(quán)調(diào)度每個任務(wù)關(guān)聯(lián)一個優(yōu)先權(quán)，調(diào)度優(yōu)先權(quán)最高的任務(wù)實例1:I/Obound任務(wù)應(yīng)獲得更大的優(yōu)先權(quán)，使得I/O盡量忙，并和CPU并行工作。優(yōu)先級設(shè)為1/f，f為CPU區(qū)間所占的比重。實例2:

定義多個優(yōu)先隊列:前臺任務(wù)、后臺任務(wù)。只有高優(yōu)先級隊列為空時才調(diào)度其他任務(wù)。優(yōu)先級3優(yōu)先級2優(yōu)先級1優(yōu)先級4優(yōu)先權(quán)調(diào)度引起的一個有趣問題優(yōu)先權(quán)太低的任務(wù)一直就緒，得不到運行:饑餓FCFS是RR的特例，SJF是優(yōu)先權(quán)調(diào)度的特例。這些調(diào)度算法都不適合于交互式系統(tǒng)。一個有趣故事:1973年關(guān)閉的MIT的IBM7094時，發(fā)現(xiàn)有一個進程在1967年提交但一直未運行。處理辦法:

優(yōu)先級動態(tài)調(diào)整。最常見的方法是“老化”(aging)技術(shù):

任務(wù)的優(yōu)先級會隨等待時間增長而不斷增高。（4）適合交互式的調(diào)度:Round-Robin(RR)RR:按時間片來輪轉(zhuǎn)調(diào)度（“輪叫”算法）一個實例假定任務(wù)的到達順序為:P1，P2，P3，P4，P5；到達時刻都為0，時間片為10。任務(wù)CPU區(qū)間(ms)P110P229P33P47P512調(diào)度結(jié)果P1P4P2236101020P330P540P250P552P2（4）適合交互式的調(diào)度:Round-Robin(RR)RR:按時間片來輪轉(zhuǎn)調(diào)度（“輪叫”算法）一個實例假定任務(wù)的到達順序為:P1，P2，P3，P4，P5；到達時刻都為0，時間片為10。任務(wù)CPU區(qū)間(ms)P110P229P33P47P512調(diào)度結(jié)果P1P4P2236101020P330P540P250P552P2RR的分析RR優(yōu)點:定時有響應(yīng)，等待時間較短P1P4P2236101020P330P540P250P552P2平均等待時間:(0+32+20+23+40)/5=23SJF的平均等待時間:13;FCFS的平均等待時間:28RR缺點:上下文切換次數(shù)較多(7次vs.4次)P3P4P136101020P532P2RR中的時間片該如何設(shè)定?響應(yīng)時間太長時間片太大時間片太小吞吐量變小，周轉(zhuǎn)時間變長如時間片500ms10任務(wù)，響應(yīng)需要5秒如時間片20ms，上下文切換5ms，20%的切換代價折中:時間片10-100ms，切換時間0.1-1ms(1%)RR調(diào)度例子：周轉(zhuǎn)時間隨著時間片大小而變化時間片進程切換過程12345678910111213141516171P1P2P3P4P1P2P4P1P2P4P1P4P1P4P1P4P42P1P2P3P4P1P2P4P1P4P43P1P2P3P4P1P4P44P1P2P3P4P1P45P1P2P3P4P1P46P1P2P3P4P47P1P2P3P4時間片（時間單位）進程平均周轉(zhuǎn)時間（時間單位）時間片P1周轉(zhuǎn)時間P2周轉(zhuǎn)時間P3周轉(zhuǎn)時間P4周轉(zhuǎn)時間平均周轉(zhuǎn)時間115931744/4=11.02141051746/4=11.5313671743/4=10.75414781746/4=11.5515891749/4=12.25669101742/4=10.5769101742/4=10.5當時間片≥7時等同F(xiàn)CFS?。?）混合多種調(diào)度算法

多級隊列調(diào)度按照一定的規(guī)則建立多個進程隊列不同的隊列有固定的優(yōu)先級（高優(yōu)先級有搶占權(quán)）不同的隊列可以給不同的時間片和采用不同的調(diào)度方法

交互式任務(wù)批處理任務(wù)系統(tǒng)任務(wù)最高優(yōu)先級最低優(yōu)先級if(!IsEmpty(KernelQ)){next=Pri();return;}if(!IsEmpty(ResponseQ)){next=RR();return;}if(!IsEmpty(BatchQ)){next=SJF();return;}...存在問題1：沒法區(qū)分I/Obound和CPUbound。存在問題2：也存在一定程度的“饑餓”現(xiàn)象（6）更成熟的多級隊列調(diào)度

多級反饋隊列任務(wù)可以在隊列之間移動，更細致的區(qū)分任務(wù)可以根據(jù)“享用”CPU時間多少來移動隊列，阻止“饑餓”最通用的調(diào)度算法，多數(shù)OS都使用該方法或其變形，如UNIX、Windows等。系統(tǒng)任務(wù)隊列2用戶任務(wù)(時間片為8)系統(tǒng)任務(wù)隊列1用戶任務(wù)(時間片為16)用戶任務(wù)(FCFS)優(yōu)先權(quán)可近似SJF，可使I/Obound停留在高優(yōu)先級…來看一種實際的調(diào)度算法?Linux調(diào)度算法概述每個進程有一個信用度counter采用優(yōu)先權(quán)的、基于信用度的、可搶占的RR調(diào)度調(diào)度時選擇信用度最大的進程每次定時器中斷，運行進程信用度減1進程信用度為0時，進程暫停并被搶占counter