2.5 調度機制

在多道程序設計系統中，操作系統需要為各個進程合理分配各種資源，從而使得不僅不會讓它們的運行相互產生沖突，而且還能對這些資源進行充分利用。在計算機系統中，最寶貴并且最容易引起各進程競爭的資源就是處理器。如何公平合理地分配給各進程足夠的處理器時間，并且盡可能提高處理器的利用率同樣是操作系統原理研究的重要內容，而這個任務是由操作系統的調度機制完成的。

調度機制一向都是學術研究的熱點，人們已經提出了很多調度算法，現在主要集中在多處理器調度上，同時還有進程的實時調度方面。

2.5.1 調度類型

前面已經講過了，調度是多道程序設計的關鍵，可以將調度大致分為4種類型（表2-2），其中I/O調度留在后面的I/O設備章節闡述。這里主要闡述單處理器調度、多處理器調度和實時調度都會遇見的3種類型，即長期調度、中期調度和短期調度。長期調度在一個進程創建時起作用，它將決定哪一個程序會被系統選中并創建一個新的進程來運行它；中期調度則是決定進程在內存中的換入、換出，其主要機制在內存管理章節已經有闡述，歸根到底中期調度是一個內存分頁的換入、換出機制問題；短期調度則是真正決定哪個等待進程該獲得處理器控制權的關鍵，這就是通常所說的調度，包括單處理器調度（Uniprocessor Scheduling）、多處理器調度（Multiprocessor Scheduling）和實時調度（Real-Time Scheduling）等。調度通過影響進程的行為來影響系統的性能。

下面來著重看看短期調度及其評價標準。

通常當某個事件的發生導致需要掛起某個進程或者需要某個進程以搶占式方式替換另外一個正在運行中的進程以取得處理器控制權的時候，短期調度就被激活。這樣的事件可以是時鐘中斷、I/O中斷、操作系統調用或者信號等。

短期調度的衡量標準是雙重的，可以按照是用戶相關還是系統相關來分，也可以按照是否是性能相關來分。用戶相關的標準主要是以用戶的主觀感受為準，例如響應時間就是一個很典型的用戶相關的評價標準；系統相關的標準主要是看處理器的使用效率等因素，例如計算任務的吞吐量。在不同的系統中，這兩種評價標準所占有的地位顯然是不一樣的。比如說，在單用戶系統中，我們評價一個調度算法的好壞主要看系統的響應時間，而不會去關心處理器的利用效率有多高。

系統性能相關的標準主要是一些可以量化的，并且通常是可以很方便測量出來的量，如反應時間和吞吐量。非系統性能相關的標準則是一些本質上的不能量化的或者不能很方便測量出來的量，如可預測性等。表2-4給出了按照這些標準的組合，一共有9項。

2.5.2 單處理器調度

已提出的單處理器調度算法主要包括這么幾種：FCFS（First Come First Served）、SPN（Shortest Process Next）、SRT（Shortest Remaining Time）、HRRN（Highest Response Ratio First）、反饋算法（Feedback）和循環執行算法（Round Robin），下面分別給予闡述。

1.FCFS算法

FCFS算法是一種非常簡單的調度算法，通常也被稱為FIFO（First In First Out）。當一個進程轉為就緒（準備）狀態的時候，它就被加到一個等待進程隊列的隊尾。當某個正在運行中的進程停止運行時，根據FCFS調度算法，隊首的一個進程，也是等待時間最長的那個進程將會出列并開始運行。該算法是非搶占式的。

2.循環執行算法

循環執行算法的基本指導思想是，將處理器時間分成一個一個的時間片（Time Slice），它從等待進程隊列中選擇下一個運行進程的方法和FCFS一樣，所不同的是每一個被選中的進程一次所占有的處理器時間頂多是一個時間片，而后，下一個被選中的進程將會以搶占式的方式來頂替該進程取得處理器的控制權。將處理器時間分片是靠定時器中斷來實現的，即每當一個時間片耗完之后，會有一個中斷產生，告知調度程序，然后調度算法就會被激活，進而選取下一個要運行的進程，開始新一輪循環。

循環執行算法有一個缺點就是，它在處理I/O操作密集型進程時和處理器使用密集型進程時會帶來資源使用的不平衡。I/O密集型進程會導致I/O設備忙，而處理器使用卻很少；處理器使用密集型進程則會讓處理器連軸轉，而I/O設備卻往往處于空閑狀態。這會導致該算法在進程間的公平性和資源使用的平衡度方面表現比較差，于是就有人提出了虛擬循環執行算法（圖2-7）。

虛擬循環執行算法的進程創建、入列，以及被選中的運行部分與FCFS算法別無二致，所不同的是加入了一個輔助進程隊列。這樣，如果一個原來因為I/O操作掛起的進程申請的I/O操作已經完成的話，它不是進入普通的等待進程隊列，而是進入輔助進程隊列。當一個新的處理器時間片來臨的時候，輔助進程隊列里的進程比普通的等待進程隊列里的進程優先獲取處理器控制權，而其運行時間將不會超過它在上一次自己獲取的時間片里用剩下來的時間。循環執行算法和虛擬循環執行算法都是搶占式的。

3.SPN算法

SPN算法是在一個進程運行完畢之后，選擇需要最短運行時間的進程運行。SPN算法實踐起來的一個難點就是如何對進程的運行時間進行估量。可以通過程序員來進行估量，但是這樣做并不保險，因為可能會出現偏差。現在比較常用的方法就是通過實驗，多次重復得到一組時間值，要么直接取平均，要么取加權平均，以便獲得較為客觀的運行時間估計。

SPN算法實施起來有一個危險，就是因為不斷會有運行時間較短的進程出現在等待隊列中，所以某些運行時間較長的進程可能會永遠得不到處理器時間片。解決方法也不是沒有，比如說可以對每個進程可等待的時間做一個上限，當達到這個上限值之后，不管三七二十一，它就得運行。該算法是非搶占式的。

4.SRT算法

SRT算法可以看做SPN算法的一個搶占式版本。在這個算法中，調度程序總是選擇剩余時間最短的進程運行。當一個新的進程加入到等待進程隊列時，它可能比現在正在運行的進程所需要的剩余時間更短，這個時候，調度程序就會中斷現在正在運行的進程轉而執行新加入的進程。和SPN算法類似，SRT算法仍然需要估算進程運行所需的時間。同樣也面臨需要較長運行時間的進程很難得到處理器時間的問題。

5.HRRN算法

HRRN算法的基本思想就是調度程序選擇下一個運行進程時遵循最高響應時間比率原則。下面我們給出響應時間比率的計算方法。

其中，w是進程等待獲取處理器控制權所耗費的時間，s是進程運行所耗費的時間預期。

6.反饋算法

如果我們事先不知道各進程運行時的時間參數，例如運行耗費時間、等待時間等，那么這個時候SPN、SRT、HRRN等算法是沒法使用的。反饋算法的提出就是希望能夠通過對進程運行已經耗費的時間進行統計，從而決定下一個運行進程該是哪一個，其指導原則就是過去運行總時間最短者最先得到處理器時間。

反饋算法的一個比較簡單的實現可以是：當一個進程被創建時，它進入優先級最高的等待隊列，每運行完一段時間后，它會被放入一個優先級較低的等待隊列等待下一次運行，如此遞推，直到它執行完任務為止。這里需要明確的一點就是，優先級高的等待隊列里的進程比優先級較低的等待隊列里的進程優先得到處理器控制權，這樣使得運行時間比較短的進程可以更早地完成任務。

2.5.3 多處理器調度

多處理器系統按照各處理器之間的關系一般可以分為兩類。

● 松耦合型：這樣的系統通常是一些自治子系統的組合，每個子系統都有自己獨立的處理器、內存、I/O及操作系統。

● 緊耦合型：這樣的系統通常是一組處理器共用一個內存，并處于一個操作系統的控制之下。

緊耦合型多處理器系統仍然可以進一步劃分成兩種。其中一種是主/從型，即其中一塊處理器屬于通用型，功能比較強，而另外的處理器則屬于專用型，功能相對單一，兩種類型的處理器組成主從關系。另外一種緊耦合型多處理系統是對等型系統，即各處理器在功能等方面是對等的，沒有差別。我們后面要講的多處理器調度算法就是針對這樣一種對等型緊耦合多處理器系統的。

1.總體設計

多處理器系統與單處理器系統相比給調度算法的設計帶來了幾個新問題，一般需要考慮3方面的事情：按處理器分配進程問題、單個處理器上的多道程序設計問題和進程實際分派問題。不管是哪個問題，需要明白的就是具體算法的設計同具體應用的特點及處理器的個數是相關的。

（1）按處理器分配進程

如何將進程的運行和具體的處理器對應起來是多處理系統調度算法首先要考慮的問題。在對等型緊耦合多處理器系統中，最簡單的調用方法就是將多個處理器統看成一個處理器資源庫，當有進程需要使用處理器時，就從這個庫中拿出相應的資源分配給它。這樣，處理器的分配方法就有兩種，即靜態方法和動態方法。

處理器分配的靜態方法是指當某個進程一旦分配到某個處理器上運行之后，在它的整個生命周期中，該進程不會再更改處理器了。靜態分配方法比較簡單，這是它的優勢所在。但是卻有一個缺點，就是它會經常導致各處理器負荷不均衡，也就是說，某些處理器可能一直忙著，而有的處理器則可能閑置著。處理器分配的動態方法則允許進程在其運行過程中可以選擇不同的處理器。由于在緊耦合多處理器系統中，處理器共享內存，所以進程的各類信息對各個處理器都是可見的，且遷移代價是可以忽略的。

進程間的地位并非是平等的，有些是核心進程，有些只是一般的用戶進程。不同種類的進程如何去占用處理器呢？其主要有兩種方式。一種是主/從方式，在這種方式中，操作系統的核心部分總是運行在一個特定的處理器上，而另外的處理器只運行用戶進程。這種方式比較簡單，但是問題是，如果這個特定的處理器出現故障的話，將會導致整個系統崩潰，并且主處理器可能會存在性能瓶頸。另外一種方式就是對等方式，即操作系統可以在任何一個處理器上運行，并且每一個進程自己從處理器資源庫中選擇處理器以實現自動調度。這種方式比較復雜，事實上很多系統的實現是取這兩種極端方式的折衷。

（2）單處理器上的多道程序設計

當采用處理器分配的靜態方法時，一個新問題就隨之而來：各個處理器是否應該采用多道程序設計？在單處理器系統中，如果不采用多道程序設計的話，處理器可能會因為進程在長時間等待某個I/O操作而造成計算資源的浪費。那么，在多處理器系統中是否也一定需要有這樣的考慮呢？

在傳統的多處理器系統中，各個處理器之間要求同步的頻率很低，或者說各處理器之間相對獨立地工作著。在這種情況下，每個處理器在功能上等同于一個單處理器系統，這個時候希望它們能夠采用多道程序設計方式運作，這樣能夠顯著提高處理器的利用率。但是如果各處理器之間的聯系屬于緊耦合型，需要不斷地進行同步，這個時候，是不是要采用多道程序設計就不好說了。當有很多處理器存在的時候，主要關心的事情并不是某個或者某些處理器的利用率，而是這個系統整體上的性能。當一個應用程序是多線程時，只有當所有線程都在運行時，程序的性能才會有顯著提高，反之，可能會表現很次。

（3）進程分派

首先需要明確的一點是，在單處理器系統中性能較好的調度算法在多處理器系統中并不見得就一樣能取得好的性能。在單處理器系統中，基于優先級或者基于反饋的調度算法比起先到先運行這樣的簡單算法，性能更優越。但是在多處理系統中，可能一些簡單的算法會更好一些，而類似基于反饋這樣的算法反而可能會導致系統性能的下降。另外，需要注意的是，在多線程調度中，還有一些新的問題需要考慮。

2.進程調度

在很多傳統的多處理器系統中，進程并不是直接分配給處理器的。所有的處理器統一起來形成一個計算資源庫，進程則按照一定的規則，比如說FIFO或者基于優先級等，形成一個或者若干個隊列，按照某種調度算法，這些進程會被一一選中在這個計算資源庫中的某個特定的處理器上運行。不管怎么講，都可以將這樣的系統稱為提供給進程隊列的多路計算服務器。研究表明，調度算法的差異所帶來的多處理器系統性能上的差異不是很明顯，并且隨著處理器數目的增加，這種影響會變得越來越小。

3.線程調度

現在針對多處理器系統的線程調度是學術界的一個研究熱點，產生了很多方案。這其中有4種方案比較突出，即負荷共同承擔法（Load Sharing）、組調度法（Gang Scheduling）、處理器指定分配法（Dedicated Processor Assignment）及動態調度法（Dynamic Scheduling），下面分別給予介紹。

（1）負荷共同承擔

在這個調度方法中，進程并不會分配給某個特定的處理器，而是所有等待運行的線程用一個統一的等待隊列來維護。當某個處理器空閑時，它會從這個隊列中按照一定的規則選取一個線程來運行，而不需要去管這個線程到底是屬于哪個進程的。

采用這個線程調度算法主要有這么3個優點。

● 系統的計算負荷在所有處理器中可以很方便地實現平均分布。

● 不需要有一個中央級的調度程序存在，當某個處理器空閑時，調度程序就在這個處理器上運行并選擇下一個需要運行的線程。

● 該調度算法和單處理器調度算法存在天然聯系，因此，單處理器調度算法可以很容易地推廣到這里來使用。

但是，這個調度算法也存在一些缺點。例如，由于等待線程隊列統一管理，所以對于多處理器而言，必須要有互斥控制。如果同時訪問該隊列的處理器數目較多，就會產生性能上的瓶頸，而且，所有線程統一管理就會使得一個應用程序的所有線程不大可能同時都獲得處理器控制權，這樣就會導致程序性能上的損失。

（2）組調度

組調度就是將一些相互存在耦合的線程同時一對一地指定給同樣數目的處理器運行。組調度策略存在一些優點，比如說，對于幾個相互關聯的進程，如果并行處理的話，就會減少同步阻塞、減少進程切換，從而提高性能。另外，由于一個調度決策會同時影響一組進程，從而也就降低了調度程序執行的頻度。

（3）處理器指定分配

處理器指定分配算法是組調度策略的一個極端情況，其主要思想是，在一個應用程序的生命周期中，將一組處理器都分配給該程序。也就是說，讓這個程序的執行進程的每個線程在其生命周期中都能夠占用一個處理器。盡管有的時候某個線程為了等待I/O操作的完成進入阻塞狀態使得它所占用的處理器處于空閑狀態造成了計算資源的浪費，但在處理器數目較多的情況下，應用程序的性能比單個處理器的利用率更重要，并且由于這種方式可以減少進程切換，從而提高了應用程序的性能，所以，采用這么一種調度方式在多處理器系統中還是不錯的。

（4）動態調度

在某些應用中，可以借助一些編程語言工具或者系統工具對其中進程所擁有的線程數目做實時修改。這樣就可以在進程運行過程中實時調整系統的負荷，從而使系統資源得到最大限度的利用，這就是動態調度的基本思想。

2.5.4 實時調度

實時系統逐漸成為人們研究的熱點，而其中的操作系統，更確切地說是操作系統中的調度部分是實時系統的重中之重。小到實驗室設備，大到航空航天，實時系統得到了廣泛的應用。那么什么是實時系統呢？人們一般認為，實時系統的特征有兩點，那就是系統不僅需要給出合乎邏輯的計算結果，而且其處理時間還需要滿足一定的要求，例如不能超過某個截止時間等。可以把實時系統分為兩類，一類是硬實時（Hard Real-Time），另外一類則是軟實時（Soft Real-Time）。所謂硬實時是指如果系統對某個實時任務的處理未能在某個截止時間開始或者結束的話，最終的結果將是災難性的，這就意味著即便是處理結果合乎邏輯但是仍然毫無意義。但在軟實時系統中，處理任務啟動或者結束的截止時間只是一個期望值，并不見得必須滿足，即便處理時間超過了截止時間，也是有意義的。

另外還可以按照處理任務的特點將實時系統劃分為周期性（Periodic）和非周期性（Aperiodic）兩種。一個非周期性的任務啟動或者結束必須要有一個截止時間；周期性任務則是指處理任務需要在某個時間周期里面完成。

1.實時操作系統的特點

實時操作系統與普通操作系統的區別主要表現在5個方面，即其任務處理的確定性、響應靈敏度、用戶參與控制、可靠性及故障保護措施。實時操作系統應當能夠做到這一點：實時任務處理的開始時間和結束時間應當是確定的、可預測的。這在實時處理上顯得非常重要。從這方面來講，在實時操作系統中，系統的吞吐量和確定的任務處理相比要次要得多，實時操作系統的任務處理具備一定的確定性。

衡量系統的確定性有一個比較好的指標，就是系統從接到要求處理的中斷和對應的處理任務啟動這兩個事件發生的時間間隔。一般操作系統的這個時間參數很大，而且可能會有幾個數量級的變動。但在實時操作系統中，它應當很小，并且比較穩定，有一個上限值。和系統的確定性相關聯的是系統的響應靈敏度，它可以定義為系統響應請求的時間。它所關心的是，系統在確認任務請求之后，需要花費多長時間來處理完相關的計算任務。不難看出，系統的確定性和系統的響應靈敏度共同構成了系統對外界的反應時間。用戶參與控制是實時操作系統不同于一般操作系統的又一重要特點。在一般操作系統中，用戶所能做的只能是希望系統如何，而最后系統完成的如何，那就看系統自己的了。但實時操作系統就不同了。當用戶發出控制指令后，系統應嚴格按照指令辦事，并且用戶可以實現對系統盡可能多的控制，甚至于在系統的調度算法上。

實時操作系統為了完成一些對處理時間敏感的計算任務，必須要強調可靠性。對于一般的系統而言，某個運行錯誤可能導致的系統重啟或者處理能力下降等問題對系統本身影響并不大，而在實時系統中，這樣的錯誤可能是災難性的。

計算機系統在運行過程中，難免會出現某些運行故障，并且這些突發故障可能會帶來災難性的后果。一般實時系統都有比較完備的故障保護措施，用于系統發生運行故障之后，盡可能多地保護系統的運行結果，從而為系統的再恢復打下基礎。另外，有些系統會有冗余設計，以便降低系統運行的故障率。

2.實時調度

在考察實時調度（Real-Time Scheduling）算法時，可以從3個方面對各種各樣的調度算法進行分類：首先看系統是否做調度分析；如果有的話，就看是靜態分析還是動態分析；最后看這個分析結果是否直接影響到進程的實時分派。據此，可以將各種實時調度算法大體上分為4類，即ST類、SPP類、DP類、DBE類。

（1）ST（Static Table-driven）類

ST（Static Table-driven）類調度算法就是根據相關信息做出一個切實可行的實時調度計劃表，并在系統實時運行時嚴格按照這個表來調度進程，這類方法比較適合周期性任務。調度分析所需要的信息包括周期性到達時間、執行時間、周期性結束時間，以及各個任務的優先級等。調度算法希望能夠制定出一個進程調度計劃表來滿足所有周期任務的要求，這個方法是確定性的，可以預測實際運行效果，但是卻不靈活，并且如果某個任務的特征有所改變的話，就需要把整個調度計劃表重新編制。

（2）SPP（Static Priority-driven Preemptive）類

SPP（Static Priority-driven Preemptive）類調度算法也需要做出一個靜態調度計劃表，但是這么一個表只是在賦予各個任務優先級的時候提供參考，在系統實際運行時，則按賦予任務的優先級來進行搶占式調度。這類調度算法的典型代表就是后面要講到的RMS調度算法。

（3）DP（Dynamic Planning-based）類

在DP（Dynamic Planning-based）類調度算法中，一個實際有效的調度計劃不是在系統運行之前制定的，而是在運行中動態規劃的。一個新的計算任務只有當它提出的要求能夠被滿足時才會被系統接受并處理，調度算法將決定何時會分派該任務。

（4）DBE（Dynamic Best Effort）類

在DBE（Dynamic Best Effort）類調度算法中，不需要做任何調度分析，系統竭力去滿足所有計算任務所提出的要求，并且會毫不留情地將不可能滿足要求的進程丟棄掉，即便這樣的進程已經被啟動了。這類算法是很多商業化實時操作系統所廣泛應用的，比較容易實現，但是有一個缺點，就是對任務的截止時間等參數無法預知，這樣就會在一些沒法滿足條件的任務身上花費不必要的處理器時間。

3.時限調度（Deadline Scheduling）

目前大多數的實時操作系統都有一個相同的設計目標，那就是獲得盡可能快的中斷處理和任務分派速度。事實上，這對實時操作系統的性能并不見得有益，實時操作系統更關心的是能否在規定的時間內完成處理任務，并且不會受系統負荷變化的干擾。近些年來有一些很好的實時調度算法出現，只是這些算法需要提供關于任務本身的更多的信息，這其中包括以下內容。

● 任務準備運行的時間。

● 任務開始處理的時間上限。

● 任務完成處理的時間上限。

● 任務處理所耗費的時間。

● 資源需求。

● 任務的優先級。

● 一個計算任務最好能夠分成兩個子任務：一個是迫切需要處理的部分，這部分一般有一個硬性的時限規定；一個是有更多選擇余地的部分。

在進行實時調度時，如果考慮各種時間上限的話，就需要認真回答幾個問題，例如下一個供調度的任務是誰，選擇何種搶占方式？

對于第一個問題的回答，這里給出一個不僅在單處理器系統而且在多處理器系統中都成立的結論，即下一個供調度的任務的時間上限與調度時刻離得越近，最終未能滿足時間上限要求的任務所占的比例就越少。

另一個問題是關于搶占方式的選擇的。如果強調的是任務開始處理的時間上限，那么一個非搶占式的調度方法就很有效。在這種情況下，獲得處理器控制權的任務可以在它處理完自己迫切需要處理掉的部分之后進入阻塞狀態，從而使得其他任務得以盡快啟動。

4.RMS調度

RMS調度（Rate Monotonic Scheduling）算法前面已經提過，它采用靜態調度法賦予各個任務在實時運行時所需要的優先級，各個任務在實際運行時依照這個優先級來實現運行時的調度。優先級的指定是以任務的周期時間為基礎的，顯而易見，RMS方法是面向周期性處理任務的，圖2-8 給出了周期性任務的相關參數。一個周期性任務的任務周期是指這樣一個任務相鄰兩次重復處理的開始時間的間隔，其對應的處理頻率（赫茲）則是這個周期的倒數（周期單位取秒），其中處理時間是指周期性任務的實際處理所占用的時間。

在RMS調度算法中，任務的優先級的高低與其任務周期的長短成反比，也就是說，一個任務的任務周期越短，它的優先級就越高。按照優先級的規定，如果有多個任務等待處理，那么總是任務周期最短的那個先開始處理。

一個判別周期性調度算法是否有效的依據就是看是否所有的硬性截止時間要求都被滿足了。假設有n個周期性任務，每一個都有一個固定的周期和一個固定的執行時間，則要使這個依據成立的前提就是下面這個不等式必須成立。

其中，Ck是第k個任務的處理時間，Tk是第k個任務的任務周期，k=1，2，…，n。

也就是說如果一個周期性調度算法能夠滿足所有的硬性截止時間的要求，那么所有任務對處理器的利用率的總和應該不會超過1這個上限，而對于一個具體的算法而言，這個上限會更低一些。比如說，對于RMS，就有下面這個不等式成立。

不等式中的各個變量和下標的意義與上同。