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

(0+24+27)/3=17

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

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

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