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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

pNew=PickNext(ReadyQueue);

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

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

等待時(shí)間(在就緒隊(duì)列中的時(shí)間)短

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

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

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

上下文切換代價(jià)小

時(shí)間片大時(shí)間片大

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

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

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

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

0

+p1

+p1+p2+p1+p2+p3

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

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

n+1=tn+(1-

)

n|

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

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

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

0

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

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

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

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

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

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

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

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

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

多級隊(duì)列調(diào)度按照一定的規(guī)則建立多個(gè)進(jìn)程隊(duì)列不同的隊(duì)列有固定的優(yōu)先級（高優(yōu)先級有搶占權(quán)）不同的隊(duì)列可以給不同的時(shí)間片和采用不同的調(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）更成熟的多級隊(duì)列調(diào)度

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