操作系統精髓與設計原理--單處理器調度

概述

        在多道程序設計系統里，內存有多個進程，且或者在處理器上運行，或者在等待某種事件的發生（如I/O完成）。當處理器（或組）通過執行某個進程而保持忙狀態，則其他的進程處于等待狀態。

        多道程序設計的關鍵是調度，操作系統根據進程的執行有三種類型的處理器調度方案和一種I/O調度方案：

• 長調度方案：確定何時允許一個新進程進入系統

• 中調度方案：負責內存的交換功能，確定何時將一個程序的部分或全部取進內存。

• 短調度方案：確定哪個就緒進程下一次被處理器執行。

• I/O調度方案：決定哪一個進程掛起的I/O請求將被可用的I/O設備處理

        這里對處理器調度方案的進行總結，且短調度方案占主要部分，I/O調度方案將總結于下一次有關I/O問題的總結里。

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

調度方案的關聯圖

進程狀態和調度轉換圖

調度方案的嵌套圖

用于調度的隊列圖

長程調度

        由于決定了哪個程序可以進入系統里處理，因此控制了系統并發度。

        長程調度程序運行時創建相應的進程，此過程涉及兩個決策：決定什么時候操作系統能接受一個或多個進程、決定接受哪個作業或哪些作業并轉為進程。

        對于決定什么時候操作系統接受一個或多個進程，通常由系統的并發度來驅動。進程越多則每個進程執行事件所占百分比越小（更多的進程競爭同樣數量的處理器時間）。為了給當前的進程集提供適合的處理器資源，長程調度可能限制系統并發度，當一個作業終止或處理器的空閑時間片超過一定閾值后，會限制系統并發度或啟動長程調度程序。

        對于允許哪個作業進入的決策可以基于簡單的先來先服務原則，或者基于管理系統性能的工具（包括優先級、期待執行時間、I/O需求）。

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

中程調度

        是交換功能的一部分，典型情況下換入取決于管理系統并發度需求，在不使用虛擬內存的系統里，系統管理也是一個問題。因此換入決定將考慮換出進程的存儲需求。

短程調度

        主要目標是按照優化系統的若干方面行為的方式來分配處理器時間，當可能導致當前進程阻塞或可能搶占當前運行進程的事件發生時，調用短程調度程序，事件包括時鐘中斷、I/O中斷、操作系統調用、信號等。

短程調度的設計準則

        設計時要對可能被評估的各種調度策略建立一系列規則。該準則按兩種維度分類：一個維度是面向用戶或面向系統，另一個維度是與性能直接相關或非直接相關。

面向用戶與面向系統的準則

        面向用戶的準則：與的那個用戶或進程感知到的系統行為相關，如交互式系統的響應時間，此時間數量對用戶是可見的。對于響應時間可以定義一個閾值，則調度機制的目標是使平均響應時間小于等于此閾值的用戶數量最大。

        面向系統的準則：重點是處理器的使用的效果和效率，如吞吐量，即進程完成的速度。該準則是系統管理員所關注的。

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

與性能直接或非直接相關

        與性能直接相關的準則是定量且通常易于度量的，如響應時間和吞吐量。

        與性能非直接相關的準則是定性的且不易于測量與分析，如可預測性，即服務隨時間改變時表現出一貫相同的特性，且與系統執行的其他工作無關（可以通過計算負載函數的變化量來度量，但不像吞吐率或相應時間關于工作量的函數一樣直接）。

相互依賴的調度準則

        以上的調度準則不可能 同時讓它們達到最優，如提供好的響應時間則可能要調度算法在進程間頻繁的切換而增加了系統開銷，降低吞吐量。以下是一些比較重要的調度準則。

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

• 響應時間：對于交互進程，指提交一個請求后到開始接收響應之間的時間間隔。通常進程處理請求時就開始給用戶一些輸出，對于用戶的角度是更好的度量。此調度準則試圖達到較低的響應時間，在可接受的時間里使交互的用戶數量最大。

• 最后期限：進程完成的最后期限，調度原則將降低其他目標的執行，使滿足最后期限的作業數目執行百分比最大。

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

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

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

• 公平性：在沒有來自用戶的指導或其他系統提供的指導是，進程要被平等的對的，沒有進程處于饑餓。

• 強制優先級：當進程被指定優先級后，調度策略要優先選擇高優先級進程。

• 平衡資源：調度策略保持系統資源處于忙狀態，較少使用緊缺資源的進程要優先調度。同樣適用于長程調度和中程調度。

短程調度算法

        選擇上取決于預期的性能和實現的復雜度。

各種調度策略的特點

w:進程等待時間；e:當前已執行的時間；s:進程所需的總服務時間，包括e

先來先服務 FCFS

        會選擇等待時間最長的進程，當一個進程停止時，就從就緒隊列里取存在時間最長的進程執行。對于執行短進程，執行一個長進程的效果更好，當執行有長進程先執行時，短進程就不得不等待長進程執行完，短進程歸一化周轉時間（周轉時間/服務時間）比長進程多得多。

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

輪轉 RR

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

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

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

        對此的改進是虛擬輪轉法，和簡單的輪轉策略不同的是，當沒有用完一個時間片且被阻塞后，就緒時進入一個FCFS輔助隊列，當進行一次調度決策時，輔助隊列優先于就緒隊列的進程，并在剩余的時間片時間上執行。

最短進程優先 SPN

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

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

最短剩余時間 SRT

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

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

最高響應比優先 HRRN

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

        調度規則每次選擇R最大的就緒進程，此方法的一個特點是參考了進程的執行歷史。當偏向短作業是（s小，比值大），長進程由于得不到服務而增加等待時間，從而增加了比值（分子大，比值大），最終被會優于短進程而被調度。

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

反饋 FB

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

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

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

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

• 即使給較低隊列執行較多的時間，長進程仍然有饑餓的情況存在，另一個方法是當一個進程在當前就緒隊列里等待服務的時間超過一定的量后，就提高此進程的優先級。