操作系統(tǒng)精髓與設(shè)計原理--單處理器調(diào)度

概述

        在多道程序設(shè)計系統(tǒng)里，內(nèi)存有多個進(jìn)程，且或者在處理器上運行，或者在等待某種事件的發(fā)生（如I/O完成）。當(dāng)處理器（或組）通過執(zhí)行某個進(jìn)程而保持忙狀態(tài)，則其他的進(jìn)程處于等待狀態(tài)。

        多道程序設(shè)計的關(guān)鍵是調(diào)度，操作系統(tǒng)根據(jù)進(jìn)程的執(zhí)行有三種類型的處理器調(diào)度方案和一種I/O調(diào)度方案：

• 長調(diào)度方案：確定何時允許一個新進(jìn)程進(jìn)入系統(tǒng)

• 中調(diào)度方案：負(fù)責(zé)內(nèi)存的交換功能，確定何時將一個程序的部分或全部取進(jìn)內(nèi)存。

• 短調(diào)度方案：確定哪個就緒進(jìn)程下一次被處理器執(zhí)行。

• I/O調(diào)度方案：決定哪一個進(jìn)程掛起的I/O請求將被可用的I/O設(shè)備處理

        這里對處理器調(diào)度方案的進(jìn)行總結(jié)，且短調(diào)度方案占主要部分，I/O調(diào)度方案將總結(jié)于下一次有關(guān)I/O問題的總結(jié)里。

        考慮到執(zhí)行的頻繁程度，長調(diào)度程序執(zhí)行的頻率相對較低（僅僅粗略地決定是否接受新進(jìn)程以及接受哪一個）；中程度調(diào)度方案執(zhí)行的略為頻繁（決定進(jìn)程的交換）；短調(diào)度程序（分派程序）只執(zhí)行的最頻繁（精確地決定下一次執(zhí)行哪一個進(jìn)程）。長調(diào)度與中調(diào)度方案主要由系統(tǒng)并發(fā)度相關(guān)性能驅(qū)動，之后會給出三種調(diào)度方案的關(guān)聯(lián)。由于多處理器對的使用有額外的復(fù)雜度，這里參考單處理器系統(tǒng)的調(diào)度情況，以更清楚地發(fā)現(xiàn)調(diào)度算法的區(qū)別。

調(diào)度方案的關(guān)聯(lián)圖

進(jìn)程狀態(tài)和調(diào)度轉(zhuǎn)換圖

調(diào)度方案的嵌套圖

用于調(diào)度的隊列圖

長程調(diào)度

        由于決定了哪個程序可以進(jìn)入系統(tǒng)里處理，因此控制了系統(tǒng)并發(fā)度。

        長程調(diào)度程序運行時創(chuàng)建相應(yīng)的進(jìn)程，此過程涉及兩個決策：決定什么時候操作系統(tǒng)能接受一個或多個進(jìn)程、決定接受哪個作業(yè)或哪些作業(yè)并轉(zhuǎn)為進(jìn)程。

        對于決定什么時候操作系統(tǒng)接受一個或多個進(jìn)程，通常由系統(tǒng)的并發(fā)度來驅(qū)動。進(jìn)程越多則每個進(jìn)程執(zhí)行事件所占百分比越?。ǜ嗟倪M(jìn)程競爭同樣數(shù)量的處理器時間）。為了給當(dāng)前的進(jìn)程集提供適合的處理器資源，長程調(diào)度可能限制系統(tǒng)并發(fā)度，當(dāng)一個作業(yè)終止或處理器的空閑時間片超過一定閾值后，會限制系統(tǒng)并發(fā)度或啟動長程調(diào)度程序。

        對于允許哪個作業(yè)進(jìn)入的決策可以基于簡單的先來先服務(wù)原則，或者基于管理系統(tǒng)性能的工具（包括優(yōu)先級、期待執(zhí)行時間、I/O需求）。

        對于分時系統(tǒng)的交互程序，用戶試圖連接到系統(tǒng)的動作可能產(chǎn)生一個進(jìn)程創(chuàng)建的請求，分時下的用戶不是僅僅排隊等待，直到系統(tǒng)接收他們。相反操作系統(tǒng)會接收所有的授權(quán)用戶，直到系統(tǒng)飽和為止。此時用戶再次連接會得到操作系統(tǒng)已經(jīng)飽和并要求用戶重試的消息。

中程調(diào)度

        是交換功能的一部分，典型情況下?lián)Q入取決于管理系統(tǒng)并發(fā)度需求，在不使用虛擬內(nèi)存的系統(tǒng)里，系統(tǒng)管理也是一個問題。因此換入決定將考慮換出進(jìn)程的存儲需求。

短程調(diào)度

        主要目標(biāo)是按照優(yōu)化系統(tǒng)的若干方面行為的方式來分配處理器時間，當(dāng)可能導(dǎo)致當(dāng)前進(jìn)程阻塞或可能搶占當(dāng)前運行進(jìn)程的事件發(fā)生時，調(diào)用短程調(diào)度程序，事件包括時鐘中斷、I/O中斷、操作系統(tǒng)調(diào)用、信號等。

短程調(diào)度的設(shè)計準(zhǔn)則

        設(shè)計時要對可能被評估的各種調(diào)度策略建立一系列規(guī)則。該準(zhǔn)則按兩種維度分類：一個維度是面向用戶或面向系統(tǒng)，另一個維度是與性能直接相關(guān)或非直接相關(guān)。

面向用戶與面向系統(tǒng)的準(zhǔn)則

        面向用戶的準(zhǔn)則：與的那個用戶或進(jìn)程感知到的系統(tǒng)行為相關(guān)，如交互式系統(tǒng)的響應(yīng)時間，此時間數(shù)量對用戶是可見的。對于響應(yīng)時間可以定義一個閾值，則調(diào)度機(jī)制的目標(biāo)是使平均響應(yīng)時間小于等于此閾值的用戶數(shù)量最大。

        面向系統(tǒng)的準(zhǔn)則：重點是處理器的使用的效果和效率，如吞吐量，即進(jìn)程完成的速度。該準(zhǔn)則是系統(tǒng)管理員所關(guān)注的。

        面向用戶的準(zhǔn)則在所有系統(tǒng)中都非常重要，而面向系統(tǒng)的原則在單用戶系統(tǒng)的重要性較低。在單用戶系統(tǒng)里，只要系統(tǒng)對用戶應(yīng)用程序的響應(yīng)時間可以接受，則實現(xiàn)處理器的高利用率或高吞吐量可能并不重要。

與性能直接或非直接相關(guān)

        與性能直接相關(guān)的準(zhǔn)則是定量且通常易于度量的，如響應(yīng)時間和吞吐量。

        與性能非直接相關(guān)的準(zhǔn)則是定性的且不易于測量與分析，如可預(yù)測性，即服務(wù)隨時間改變時表現(xiàn)出一貫相同的特性，且與系統(tǒng)執(zhí)行的其他工作無關(guān)（可以通過計算負(fù)載函數(shù)的變化量來度量，但不像吞吐率或相應(yīng)時間關(guān)于工作量的函數(shù)一樣直接）。

相互依賴的調(diào)度準(zhǔn)則

        以上的調(diào)度準(zhǔn)則不可能 同時讓它們達(dá)到最優(yōu)，如提供好的響應(yīng)時間則可能要調(diào)度算法在進(jìn)程間頻繁的切換而增加了系統(tǒng)開銷，降低吞吐量。以下是一些比較重要的調(diào)度準(zhǔn)則。

• 周轉(zhuǎn)時間：一個進(jìn)程從提交到完成之間的時間間隔，包括實際執(zhí)行時間、等待資源時間，對于批處理作業(yè)是很適宜的度量。

• 響應(yīng)時間：對于交互進(jìn)程，指提交一個請求后到開始接收響應(yīng)之間的時間間隔。通常進(jìn)程處理請求時就開始給用戶一些輸出，對于用戶的角度是更好的度量。此調(diào)度準(zhǔn)則試圖達(dá)到較低的響應(yīng)時間，在可接受的時間里使交互的用戶數(shù)量最大。

• 最后期限：進(jìn)程完成的最后期限，調(diào)度原則將降低其他目標(biāo)的執(zhí)行，使?jié)M足最后期限的作業(yè)數(shù)目執(zhí)行百分比最大。

• 可預(yù)測性：無論系統(tǒng)的負(fù)載如何，一個給定工作運行的總時間和總開銷是相同的，即響應(yīng)時間后周轉(zhuǎn)時間變化不能太大，可能需要在系統(tǒng)工作負(fù)載大范圍抖動時發(fā)出信號或需要系統(tǒng)來處理不穩(wěn)定性。

• 吞吐量：室每個時間單位里完成的進(jìn)程數(shù)目最大，是對可以執(zhí)行多少工作的一種度量。主要取決于一個進(jìn)程的平均執(zhí)行長度，也受調(diào)度策略的影響（會影響處理器的利用率）。

• 處理器利用率：處理器忙的百分比，對于昂貴的共享系統(tǒng)是一個重要的準(zhǔn)則，對于單用戶系統(tǒng)和其他系統(tǒng)（如實時系統(tǒng)）則不太重要。

• 公平性：在沒有來自用戶的指導(dǎo)或其他系統(tǒng)提供的指導(dǎo)是，進(jìn)程要被平等的對的，沒有進(jìn)程處于饑餓。

• 強(qiáng)制優(yōu)先級：當(dāng)進(jìn)程被指定優(yōu)先級后，調(diào)度策略要優(yōu)先選擇高優(yōu)先級進(jìn)程。

• 平衡資源：調(diào)度策略保持系統(tǒng)資源處于忙狀態(tài)，較少使用緊缺資源的進(jìn)程要優(yōu)先調(diào)度。同樣適用于長程調(diào)度和中程調(diào)度。

短程調(diào)度算法

        選擇上取決于預(yù)期的性能和實現(xiàn)的復(fù)雜度。

各種調(diào)度策略的特點

w:進(jìn)程等待時間；e:當(dāng)前已執(zhí)行的時間；s:進(jìn)程所需的總服務(wù)時間，包括e

先來先服務(wù) FCFS

        會選擇等待時間最長的進(jìn)程，當(dāng)一個進(jìn)程停止時，就從就緒隊列里取存在時間最長的進(jìn)程執(zhí)行。對于執(zhí)行短進(jìn)程，執(zhí)行一個長進(jìn)程的效果更好，當(dāng)執(zhí)行有長進(jìn)程先執(zhí)行時，短進(jìn)程就不得不等待長進(jìn)程執(zhí)行完，短進(jìn)程歸一化周轉(zhuǎn)時間（周轉(zhuǎn)時間/服務(wù)時間）比長進(jìn)程多得多。

        對于I/O密集型進(jìn)程，相比處理器密集型不利于調(diào)度。當(dāng)同時有I/O密集型和處理器密集型的進(jìn)程時，如果此時處理器密集型程序正在運行，則I/O密集型必須等待。有的I/O密集型進(jìn)程可能在I/O隊里，且處理器密集型進(jìn)程正在執(zhí)行時進(jìn)入了就緒隊里，I/O設(shè)備就有可能是空閑的，即使有其他進(jìn)程要使用。當(dāng)前的進(jìn)程執(zhí)行完后，等待的I/O密集型進(jìn)程會快速通過運行態(tài)，再次進(jìn)入到I/O隊列里，期間對處理器的使用時間并不長。如果處理器密集型進(jìn)程阻塞了，則處理器和I/O設(shè)備都會空閑。

輪轉(zhuǎn) RR

        為了減少FCFS對短作業(yè)不利的情況，一個簡單的方法是采用基于時鐘的搶占策略，最簡單的方法是輪轉(zhuǎn)算法。以一個周期性間隔產(chǎn)生時鐘中斷，中斷發(fā)生時當(dāng)前運行的進(jìn)程被置于就緒隊列里，然后基于FCFS策略選擇下一個就緒作業(yè)運行。此技術(shù)也叫做時間片，每個進(jìn)程被搶占前被分給一定的時間。

        其主要的設(shè)計問題時使用的時間片長度，較短則短作業(yè)會較快的通過系統(tǒng)。同時處理時鐘中斷、執(zhí)行調(diào)度和分派函數(shù)都需要處理器開銷，因此要避免過短的時間片。較好的思想是時間片要略大于一次典型交互所要時間，如果小于則大多數(shù)進(jìn)行要至少兩個時間片長度；如果過長會退化成FCFS策略。該策略在通用的分時系統(tǒng)或事務(wù)處理系統(tǒng)特別有效。

        輪轉(zhuǎn)策略的一個缺點是依賴于處理器密集型的進(jìn)程和I/O秘籍型的進(jìn)程的不同。如果兩者都存在的話會有如下情況：一個I/O秘籍型進(jìn)程用了很短的處理器時間后，進(jìn)入到I/O隊列，等待I/O操作完成后進(jìn)入就緒隊列；同時，一個處理器密集型進(jìn)程在執(zhí)行過程中使用了一個完整的處理器時間后，進(jìn)入就緒隊列。因此對于這兩類進(jìn)程，占用的處理器分時間并不平等，I/O密集型進(jìn)程獲得處理器的時間不等，等待的時間受就緒進(jìn)程數(shù)的影響，使I/O密集型進(jìn)程性能降低、使用I/O設(shè)備低效、響應(yīng)時間的變化大。

        對此的改進(jìn)是虛擬輪轉(zhuǎn)法，和簡單的輪轉(zhuǎn)策略不同的是，當(dāng)沒有用完一個時間片且被阻塞后，就緒時進(jìn)入一個FCFS輔助隊列，當(dāng)進(jìn)行一次調(diào)度決策時，輔助隊列優(yōu)先于就緒隊列的進(jìn)程，并在剩余的時間片時間上執(zhí)行。

最短進(jìn)程優(yōu)先 SPN

        減少FCFS固有對長進(jìn)程偏向的另一種方法是最短進(jìn)程優(yōu)先，是一個非搶占策略，原則是選擇下一次預(yù)計處理時間最短的進(jìn)程。短進(jìn)程會優(yōu)先于長進(jìn)程執(zhí)行，因此響應(yīng)的波動增加，可預(yù)測性降低。

        SPN策略難點在于預(yù)測每個進(jìn)程所需要的執(zhí)行時間。對于批處理作為，系統(tǒng)要求程序員估計該值并提供給操作系統(tǒng)。如果值遠(yuǎn)低于實際值則可能提前終止此作業(yè)。在生產(chǎn)環(huán)境中，相同的作業(yè)頻繁運行，可以收集它們的統(tǒng)計值，對于交互進(jìn)程，操作系統(tǒng)可以為為每個進(jìn)程保留一個運行平均值。

最短剩余時間 SRT

        針對SPN添加的搶占機(jī)制，此時調(diào)度程序總是選擇預(yù)期剩余時間最短的進(jìn)程。當(dāng)一個新進(jìn)程進(jìn)入就緒隊列時，就可能比當(dāng)前運行的進(jìn)程剩余時間要短。所以每次有新進(jìn)程進(jìn)入到就緒隊列里，調(diào)度程序就可能搶占當(dāng)前正在運行的進(jìn)程。和SPN一樣，需要有關(guān)處理時間的估計，同時有長進(jìn)程饑餓的可能。

        由于SRT不會像FSFC那樣偏向于長進(jìn)程，也不會像RR那樣產(chǎn)生額外的中斷，從而減少了開銷；同時它必須記錄過去的服務(wù)時間而增加了開銷。從周轉(zhuǎn)時間上來看，SRT比SPN有更好的性能，因為相對于正在運行的長進(jìn)程，短進(jìn)程可以被選擇運行。

最高響應(yīng)比優(yōu)先 HRRN

        歸一化周轉(zhuǎn)時間是周轉(zhuǎn)時間和實際服務(wù)時間的比率（R=(w+s)/s，R為歸一化周轉(zhuǎn)時間，w為等待時間，s為預(yù)期的服務(wù)時間），可作為性能度量，且每個進(jìn)程和所有進(jìn)程的平均值都越小越好。

        調(diào)度規(guī)則每次選擇R最大的就緒進(jìn)程，此方法的一個特點是參考了進(jìn)程的執(zhí)行歷史。當(dāng)偏向短作業(yè)是（s小，比值大），長進(jìn)程由于得不到服務(wù)而增加等待時間，從而增加了比值（分子大，比值大），最終被會優(yōu)于短進(jìn)程而被調(diào)度。

        和SPN、SRT一樣，需要估計服務(wù)時間。

反饋 FB

        如果沒有關(guān)于個個進(jìn)程的相對長度的任何信息，則SPN、SRT、HRRN都不能使用。另一種使短作業(yè)優(yōu)先的方法是降低長作業(yè)的優(yōu)先級，即不能獲得剩余執(zhí)行時間，則關(guān)注已執(zhí)行時間。

        調(diào)度基于按時間片的搶占原則，同時有動態(tài)的優(yōu)先級機(jī)制。當(dāng)一個進(jìn)程第一次進(jìn)入系統(tǒng)中時被放置在RQ0（優(yōu)先級最高的就緒隊列），當(dāng)被搶占后就緒時放入到RQ1里（優(yōu)先級次于RQ0的就緒隊列），以此類推指定放入到優(yōu)先級最低的的就緒隊列RQN，并在此隊列使用FCFS調(diào)度策略。由于一個短進(jìn)程很快就執(zhí)行完，以此優(yōu)先級不會降低很多，而長進(jìn)程由于執(zhí)行時間較長則優(yōu)先級會降得較多。

        簡單的反饋策略依據(jù)時間片長度輪轉(zhuǎn)，同時有其他變體。簡單的返回策略存在一個問題，長進(jìn)程的周轉(zhuǎn)時間會不斷增加，如果頻繁的有新進(jìn)程進(jìn)入系統(tǒng)，則可能產(chǎn)生饑餓。為解決此問題，有以下幾個變體策略

• 按照隊列改變搶占次數(shù)，如每個進(jìn)程每次在RO0隊列允許執(zhí)行一個時間單位、RO1允許2個時間單位、RON允許2^n個時間單位等。

• 即使給較低隊列執(zhí)行較多的時間，長進(jìn)程仍然有饑餓的情況存在，另一個方法是當(dāng)一個進(jìn)程在當(dāng)前就緒隊列里等待服務(wù)的時間超過一定的量后，就提高此進(jìn)程的優(yōu)先級。