操作系統(tǒng)原理：第六章 CPU調(diào)度

操作系統(tǒng)概念第六章：CPU調(diào)度本章主要內(nèi)容基本概念調(diào)度準(zhǔn)則調(diào)度算法多處理器調(diào)度實(shí)時(shí)調(diào)度算法評(píng)估進(jìn)程調(diào)度模型2CPU調(diào)度why？計(jì)算機(jī)得以完成計(jì)算，必須依賴CPU需要運(yùn)行的程序數(shù)>>計(jì)算機(jī)CPU個(gè)數(shù)Possible？CPU的速度>>用戶的速度CPU與I/O可以并發(fā)原則讓CPU不停地忙，公平地做有用功，考慮任務(wù)的輕重緩急車(chē)輪戰(zhàn)，以一敵百6.1基本概念利用多道程序最大化CPU使用率。CPU–I/O周期－進(jìn)程執(zhí)行由CPU執(zhí)行和I/O等待周期組成。CPU區(qū)間分布情況4CPU區(qū)間和I/O區(qū)間的交替序列5CPU區(qū)間時(shí)間直方圖6什么時(shí)候調(diào)度？記得我們的原則：讓CPU不停忙、公平做有用功、考慮輕重緩急讓出CPU讓出CPU剝奪CPU可能剝奪別的CPUCPU調(diào)度程序調(diào)度程序從內(nèi)存中就緒可執(zhí)行的進(jìn)程里選擇一個(gè)，并為其中之一分配CPU。CPU調(diào)度決策可以如下四種情況下發(fā)生當(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í)。當(dāng)調(diào)度只能發(fā)生在第一和第四兩種情況時(shí)，稱調(diào)度方法是非搶占的（nonpreemptive）否則調(diào)度方案就是可搶占（preemptive）的。8分派程序（Dispatcher）分派程序是一個(gè)模塊，用來(lái)將CPU的控制交給由短期調(diào)度程序所選擇的進(jìn)程。其功能包括切換上下文切換到用戶模式跳轉(zhuǎn)到用戶程序的合適位置以重新啟動(dòng)這個(gè)程序分派延遲（dispatchlatency）－分派程序停止一個(gè)進(jìn)程而啟動(dòng)另一個(gè)進(jìn)程執(zhí)行所要花費(fèi)的時(shí)間。96.2調(diào)度準(zhǔn)則（SchedulingCriteria）CPU使用率：使CPU盡可能忙吞吐量（Throughput）：?jiǎn)挝粫r(shí)間完成進(jìn)程的數(shù)量周轉(zhuǎn)時(shí)間（Turnaroundtime）：從進(jìn)程提交到進(jìn)程完成的時(shí)間間隔稱為周轉(zhuǎn)時(shí)間等待時(shí)間（Waitingtime）：是在就緒隊(duì)列中等待所花時(shí)間之和。響應(yīng)時(shí)間（Responsetime）：從提交請(qǐng)求到產(chǎn)生第一響應(yīng)的時(shí)間。10優(yōu)化準(zhǔn)則（OptimizationCriteria）最大化CPU使用率最大化吞吐量最小化周轉(zhuǎn)時(shí)間最小化等待時(shí)間最小化響應(yīng)時(shí)間116.3調(diào)度算法先到先服務(wù)調(diào)度（FirstCome,FirstServed,FCFS）最短作業(yè)優(yōu)先調(diào)度（Shortest-Job-First,SJR）優(yōu)先權(quán)調(diào)度（PriorityScheduling）輪轉(zhuǎn)法調(diào)度（RoundRobin,RR）多級(jí)隊(duì)列調(diào)度（multilevelqueue-scheduling）多級(jí)反饋隊(duì)列調(diào)度（multilevelfeedbackqueuescheduling）12先來(lái)先服務(wù)調(diào)度（FCFS）進(jìn)程區(qū)間時(shí)間P124P23P33假設(shè)進(jìn)程按P1、P2、P3的順序到達(dá)。則該調(diào)度的Gantt圖如下：13等待時(shí)間：P1=0;P2=24;P3=27平均等待時(shí)間：

(0+24+27)/3=17

假設(shè)進(jìn)程按P2,P3,P1的順序到來(lái)，則其調(diào)度的Gannt圖如下14等待時(shí)間：P1=6;P2=0;P3=3平均等待時(shí)間：(6+0+3)/3=3優(yōu)于前一種情況由于所有其他進(jìn)程都等待一個(gè)大進(jìn)程釋放CPU，就會(huì)產(chǎn)生護(hù)航效果（convoyeffect）。與允許較短進(jìn)程先行相比，這種效果會(huì)導(dǎo)致CPU和設(shè)備的使用率變得更低最短作業(yè)優(yōu)先調(diào)度(Shortest-Job-First,SJR)將每個(gè)進(jìn)程與其下一個(gè)CPU區(qū)間段相關(guān)聯(lián)。當(dāng)CPU為可用時(shí)，它會(huì)賦給具有最短后續(xù)CPU區(qū)間的進(jìn)程。如果兩個(gè)進(jìn)程具有同樣長(zhǎng)度的CPU區(qū)間，那么可以使用FCFS調(diào)度來(lái)處理。兩種方式非搶占式：一旦進(jìn)程獲得CPU就一直占據(jù)CPU，直到其CPU區(qū)間完成為止搶占式：如果一個(gè)新來(lái)的進(jìn)程其CPU區(qū)間小于當(dāng)前進(jìn)程的CPU區(qū)間，則搶占之。這種調(diào)度方式稱為最短剩余時(shí)間作業(yè)優(yōu)先（ShortestRemainingTimeFirst,SRTF）SJF是最佳的：對(duì)于給定的一組進(jìn)程，SJF算法的平均等待時(shí)間最小。15

Process ArrivalTime

BurstTime

P1 0.0 7

P2 2.0 4

P3 4.0 1

P4 5.0 4SJF(non-preemptive)Averagewaitingtime=(0+6+3+7)/4=4ExampleofNon-PreemptiveSJFP1P3P273160P481216ExampleofPreemptiveSJF（更徹底SJF）

Process ArrivalTime

BurstTime

P1 0.0 7

P2 2.0 4

P3 4.0 1

P4 5.0 4SJF(preemptive)Averagewaitingtime=(9+1+0+2)/4=3P1P3P242110P457P2P1165452152451654預(yù)見(jiàn)未來(lái)未來(lái)歷史18確定下一CPU區(qū)間的長(zhǎng)度只能估計(jì)CPU區(qū)間的長(zhǎng)度，無(wú)法精確計(jì)算下一CPU區(qū)間的長(zhǎng)度通?？深A(yù)測(cè)為以前CPU區(qū)間的測(cè)量長(zhǎng)度的指數(shù)平均19下一個(gè)CPU區(qū)間長(zhǎng)度的預(yù)測(cè)20指數(shù)平均計(jì)算的實(shí)例21優(yōu)先級(jí)調(diào)度（PriorityScheduling）每個(gè)進(jìn)程被賦予一個(gè)優(yōu)先級(jí)數(shù)字（優(yōu)先權(quán)）SJF是一種特定的優(yōu)先權(quán)調(diào)度方法CPU分配給優(yōu)先權(quán)高的進(jìn)程（優(yōu)先級(jí)數(shù)字越小，則優(yōu)先權(quán)越大）搶占式非搶占式該算法存在的問(wèn)題：饑餓（starvation）低優(yōu)先權(quán)的進(jìn)程可能永遠(yuǎn)無(wú)法執(zhí)行解決辦法：老化（aging）隨著時(shí)間的推進(jìn)，進(jìn)程的優(yōu)先權(quán)逐漸提高22輪轉(zhuǎn)法調(diào)度（RoundRobin）輪轉(zhuǎn)法是專門(mén)為分時(shí)系統(tǒng)而設(shè)計(jì)的。每個(gè)進(jìn)程獲得一小片CPU時(shí)間量（timequantum），通常為10-100毫秒。時(shí)間片結(jié)束后，進(jìn)程被搶占并放入到就緒隊(duì)列的最后重新參加調(diào)度。如果就緒隊(duì)列中有n個(gè)進(jìn)程，其時(shí)間片為q，則每個(gè)進(jìn)程會(huì)得到1/n的CPU時(shí)間，每個(gè)長(zhǎng)度不超過(guò)q時(shí)間單元。每個(gè)進(jìn)程必須等待CPU的時(shí)間不會(huì)超過(guò)(n-1)q個(gè)時(shí)間單元，直到它的下一個(gè)時(shí)間片為止。性能依賴于時(shí)間片的大小如果時(shí)間片非常大（無(wú)限），那么RR策略與FCFS策略一樣。如果時(shí)間片很小，那么RR方法稱處理器共享。n個(gè)進(jìn)程對(duì)于用戶來(lái)說(shuō)都有它自己的處理器，速度各為真正處理器速度的1/nq必須大于上下文切換所需時(shí)間23RoundRobin(RR)時(shí)間片＝20時(shí)的RR實(shí)例25上下文切換開(kāi)銷(xiāo)與周轉(zhuǎn)時(shí)間26切換開(kāi)銷(xiāo)周轉(zhuǎn)時(shí)間多級(jí)隊(duì)列調(diào)度就緒隊(duì)列分成幾個(gè)相對(duì)獨(dú)立的隊(duì)列前臺(tái)（或交互式）后臺(tái)（或批處理）每個(gè)隊(duì)列有自己的調(diào)度算法前臺(tái)：RR后臺(tái)：FCFS隊(duì)列之間必須有調(diào)度通常采用固定優(yōu)先權(quán)可搶占調(diào)度來(lái)實(shí)現(xiàn)。另一種可能是在隊(duì)列之間劃分時(shí)間片。每個(gè)隊(duì)列都有一定的CPU時(shí)間，這可用于調(diào)度隊(duì)列內(nèi)的不同進(jìn)程20％給后臺(tái)，80％給前臺(tái)27多級(jí)隊(duì)列調(diào)度示意圖28多級(jí)反饋隊(duì)列調(diào)度進(jìn)程可以在不同隊(duì)列間移動(dòng)通常，多級(jí)反饋隊(duì)列調(diào)度程序可由下列參數(shù)來(lái)定義：隊(duì)列數(shù)量每個(gè)隊(duì)列的調(diào)度算法用以確定進(jìn)程何時(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ì)列的方法29多級(jí)反饋隊(duì)列調(diào)度的實(shí)例三個(gè)隊(duì)列Q0：時(shí)間片為8毫秒Q1：時(shí)間片為16毫秒Q2：FCFS調(diào)度進(jìn)入就緒隊(duì)列的進(jìn)程被放在隊(duì)列Q0內(nèi)。隊(duì)列0的每個(gè)進(jìn)程都有8ms的時(shí)間片。如果一個(gè)進(jìn)程不能在這一時(shí)間內(nèi)完成，那么它就被移到隊(duì)列1的尾部。如果隊(duì)列0為空，隊(duì)列1頭部進(jìn)程會(huì)得到一個(gè)16ms的時(shí)間片。如果它不能完成，那么它將被搶占，并被放到隊(duì)列2中。只有當(dāng)隊(duì)0和隊(duì)1為空時(shí)，隊(duì)列2內(nèi)的進(jìn)程才可根據(jù)FCFS來(lái)運(yùn)行。30多級(jí)反饋隊(duì)列示意圖316.4多處理器調(diào)度多處理器調(diào)度問(wèn)題更復(fù)雜主要討論處理器功能相同的系統(tǒng)。負(fù)載分配（LoadSharing）非對(duì)稱多道程序：只有一個(gè)處理器訪問(wèn)系統(tǒng)數(shù)據(jù)結(jié)構(gòu)，減輕了數(shù)據(jù)共享的需要。326.5實(shí)時(shí)調(diào)度硬實(shí)時(shí)系統(tǒng)：需要在保證的時(shí)間內(nèi)完成關(guān)鍵任務(wù)在提交進(jìn)程時(shí)，同時(shí)有一條語(yǔ)句告訴系統(tǒng)用來(lái)完成或執(zhí)行I/O所需要的時(shí)間。接著，調(diào)度程序或者允許進(jìn)程并保證進(jìn)程能按時(shí)完成，或者因不可能而拒絕請(qǐng)求。（資源預(yù)約）軟實(shí)時(shí)系統(tǒng)：要保證關(guān)鍵進(jìn)程擁有比其他進(jìn)程更高的優(yōu)先權(quán)要求仔細(xì)設(shè)計(jì)調(diào)度程序和操作系統(tǒng)有關(guān)方面。第一、系統(tǒng)必須有優(yōu)先權(quán)調(diào)度，且實(shí)時(shí)進(jìn)程必須有最高的優(yōu)先權(quán)。實(shí)時(shí)進(jìn)程的優(yōu)先權(quán)不能隨時(shí)間而下降，盡管非實(shí)時(shí)進(jìn)程的優(yōu)先權(quán)可以。實(shí)時(shí)進(jìn)程不應(yīng)該老化第二、分派延遲必須小。內(nèi)核搶占33分派延遲346.6算法評(píng)估確定性建模：采用特定預(yù)先確定的負(fù)荷，定義在給定負(fù)荷下每個(gè)算法的性能。簡(jiǎn)單快速，給出了確切數(shù)字，以允許算法被比較但通常過(guò)分特殊且要求過(guò)多精確知識(shí)，故用處有限排隊(duì)模型：在許多系統(tǒng)上運(yùn)行的進(jìn)程每天都在變化，因此沒(méi)有靜態(tài)的進(jìn)程集合和時(shí)間用于確定性建模。n為平均隊(duì)列長(zhǎng)度（不包括正在服務(wù)的進(jìn)程）Ｗ為隊(duì)列的平均等待時(shí)間λ為新進(jìn)程到達(dá)隊(duì)列的平均到達(dá)率n=λ×W(Little公式)可用于比較調(diào)度算法，但計(jì)算結(jié)果的精確性值得懷疑35通過(guò)模擬來(lái)評(píng)估CPU調(diào)度算法36實(shí)現(xiàn)即使模擬其精確度也是有限的。針對(duì)評(píng)估調(diào)度算法，惟一完全精確的方法是對(duì)它進(jìn)行程序編碼，將其放在操作系統(tǒng)內(nèi)，并觀測(cè)它如何工作。主要困難是這種方法的代價(jià)對(duì)算法編碼、修改操作系統(tǒng)以支持該算法用戶對(duì)不斷變化的操作系統(tǒng)的反應(yīng)另一困難是算法所使用的環(huán)境會(huì)變化最為靈活的調(diào)度算法可以為系統(tǒng)管理員或用戶所改變37OperatingSystemExamplesSolarisschedulingWindowsXPschedulingLinuxscheduling38Solaris2Scheduling39SolarisDispatchTableMultilevelfeedbackqueuefortheInteractiveandtime-sharingclass40WindowsXPPriorities41Linux調(diào)度兩種算法：分時(shí)與實(shí)時(shí)分時(shí)基于信用度的算法（信用=信用/2+優(yōu)先級(jí)）信用度隨著定時(shí)器中斷的發(fā)生而降低當(dāng)可運(yùn)行進(jìn)程的信用度都為0的時(shí)候，則對(duì)所有進(jìn)程重新計(jì)算信用度這種算法似乎混合了兩個(gè)因素：進(jìn)程歷史和它的優(yōu)先級(jí)實(shí)時(shí)軟實(shí)時(shí)實(shí)現(xiàn)了兩種POSIX.1b所要求的實(shí)時(shí)調(diào)度類型：FCFS和RR高優(yōu)先級(jí)的進(jìn)程總是最先運(yùn)行42Linux內(nèi)核在實(shí)時(shí)性方面的不足1）Linux分為用戶態(tài)和內(nèi)核態(tài)兩種模式，進(jìn)程運(yùn)行在用戶態(tài)時(shí)，實(shí)時(shí)進(jìn)程具有高的優(yōu)先級(jí)，能進(jìn)行進(jìn)程搶占，故可以較好的完成任務(wù)；運(yùn)行在內(nèi)核態(tài)時(shí)，如系統(tǒng)調(diào)用，實(shí)時(shí)進(jìn)程不能搶占該進(jìn)程。因此，從實(shí)質(zhì)上來(lái)說(shuō)，Linux內(nèi)核是非搶占式的。內(nèi)核kernel將系統(tǒng)的一些關(guān)鍵性程序分離出來(lái)構(gòu)成操作系統(tǒng)內(nèi)核

.內(nèi)核必須完成下面的一些任務(wù)：管理對(duì)文件系統(tǒng)的讀寫(xiě)，把對(duì)文件系統(tǒng)的操作映射成對(duì)磁盤(pán)或其他塊設(shè)備的操作管理程序的運(yùn)行，為程序分配資源，并且處理程序之間的通訊管理存儲(chǔ)器，為程序分配內(nèi)存，并且管理虛擬內(nèi)存管理輸入輸出，將設(shè)備映射成設(shè)備文件管理網(wǎng)絡(luò)

2）在定時(shí)器方面，有下列幾方面缺陷：第一，Linux的周期模式定時(shí)器頻率僅為100Hz，遠(yuǎn)不能滿足多種實(shí)時(shí)應(yīng)用的要求。第二，軟定時(shí)由時(shí)鐘定時(shí)器完成，當(dāng)軟定時(shí)器較多時(shí)，勢(shì)必引起共享時(shí)鐘定時(shí)器的沖突。第三，Linux中斷句柄不可調(diào)度，但在實(shí)時(shí)系統(tǒng)中，期望能在一個(gè)可調(diào)度整體內(nèi)處理這些中斷句柄，從而能更有效的區(qū)分不同實(shí)時(shí)任務(wù)的緊迫度，分配不同的優(yōu)先級(jí)。因此，單純縮短時(shí)間片在對(duì)實(shí)時(shí)性能?chē)?yán)格要求的場(chǎng)合是不受歡迎的。（3）Linux進(jìn)程采用多級(jí)輪轉(zhuǎn)調(diào)度算法，該調(diào)度算法，僅能獲得秒級(jí)響應(yīng)時(shí)間，一個(gè)實(shí)時(shí)進(jìn)程在一個(gè)時(shí)間片內(nèi)未完成，其優(yōu)先級(jí)將降低，從而可能造成到截止時(shí)間無(wú)法完成。4）Linux雖然給實(shí)時(shí)進(jìn)程提供了較高的優(yōu)先級(jí)，但是，并沒(méi)有加入時(shí)間限制。例如完成的最后期限、應(yīng)在多長(zhǎng)時(shí)間內(nèi)完成、執(zhí)行周期等等。同時(shí)，其它大量的非實(shí)時(shí)進(jìn)程也可能對(duì)實(shí)時(shí)進(jìn)程造成阻塞，無(wú)法確保實(shí)時(shí)進(jìn)程的響應(yīng)時(shí)間。另外，當(dāng)有多個(gè)實(shí)時(shí)進(jìn)程互斥請(qǐng)求共享資