第一部分： 實時調度算法介紹

對 于什么是實時系統，POSIX 1003.b作了這樣的定義：指系統能夠在限定的響應時間內提供所需水平的服務。而一個由Donald Gillies提出的更加為大家接受的定義是：一個實時系統是指計算的正確性不僅取決于程序的邏輯正確性，也取決于結果產生的時間，如果系統的時間約束條 件得不到滿足，將會發生系統出錯。

實 時系統根據其對于實時性要求的不同，可以分為軟實時和硬實時兩種類型。硬實時系統指系統要有確保的最壞情況下的服務時間，即對于事件的響應時間的截止期限 是無論如何都必須得到滿足。比如航天中的宇宙飛船的控制等就是現實中這樣的系統。其他的所有有實時特性的系統都可以稱之為軟實時系統。如果明確地來說，軟 實時系統就是那些從統計的角度來說，一個任務（在下面的論述中，我們將對任務和進程不作區分）能夠得到有確保的處理時間，到達系統的事件也能夠在截止期限 到來之前得到處理，但違反截止期限并不會帶來致命的錯誤，像實時多媒體系統就是一種軟實時系統。

一 個計算機系統為了提供對于實時性的支持，它的操作系統必須對于CPU和其他資源進行有效的調度和管理。在多任務實時系統中，資源的調度和管理更加復雜。本 文下面將先從分類的角度對各種實時任務調度算法進行討論，然后研究普通的Linux操作系統的進程調度以及各種實時Linux系統為了支持實時特性對普通 Linux系統所做的改進。最后分析了將Linux操作系統應用于實時領域中時所出現的一些問題，并總結了各種實時Linux是如何解決這些問題的。

1. 實時CPU調度算法分類

各 種實時操作系統的實時調度算法可以分為如下三種類別[Wang99][Gopalan01]：基于優先級的調度算法（Priority-driven scheduling-PD）、基于CPU使用比例的共享式的調度算法（Share-driven scheduling-SD）、以及基于時間的進程調度算法（Time-driven scheduling-TD），下面對這三種調度算法逐一進行介紹。

1.1. 基于優先級的調度算法

基于優先級的調度算法給每個進程分配一個優先級，在每次進程調度時，調度器總是調度那個具有最高優先級的任務來執行。根據不同的優先級分配方法，基于優先級的調度算法可以分為如下兩種類型[Krishna01][Wang99]：

靜態優先級調度算法：

這 種調度算法給那些系統中得到運行的所有進程都靜態地分配一個優先級。靜態優先級的分配可以根據應用的屬性來進行，比如任務的周期，用戶優先級，或者其它的 預先確定的策略。RM（Rate-Monotonic）調度算法是一種典型的靜態優先級調度算法，它根據任務的執行周期的長短來決定調度優先級，那些具有 小的執行周期的任務具有較高的優先級。

動態優先級調度算法：

這 種調度算法根據任務的資源需求來動態地分配任務的優先級，其目的就是在資源分配和調度時有更大的靈活性。非實時系統中就有很多這種調度算法，比如短作業優 先的調度算法。在實時調度算法中，EDF算法是使用最多的一種動態優先級調度算法，該算法給就緒隊列中的各個任務根據它們的截止期限（Deadline） 來分配優先級，具有最近的截止期限的任務具有最高的優先級。

1.2. 基于比例共享調度算法

雖然基于優先級的調度算法簡單而有效，但這種調度算法提供的是一種硬實時的調度，在很多情況下并不適合使用這種調度算法：比如象實時多媒體會議系統這樣的軟實時應用。對于這種軟實時應用，使用一種比例共享式的資源調度算法（SD算法）更為適合。

比例共享調度算法指基于CPU使用比例的共享式的調度算法，其基本思想就是按照一定的權重（比例）對一組需要調度的任務進行調度，讓它們的執行時間與它們的權重完全成正比。

我們可以通過兩種方法來實現比例共享調度算法[Nieh01]：第一種方法是調節各個就緒進程出現在調度隊列隊首的頻率，并調度隊首的進程執行；第二種做法就是逐次調度就緒隊列中的各個進程投入運行，但根據分配的權重調節分配個每個進程的運行時間片。

比例共享調度算法可以分為以下幾個類別：輪轉法、公平共享、公平隊列、彩票調度法（Lottery）等。

比例共享調度算法的一個問題就是它沒有定義任何優先級的概念；所有的任務都根據它們申請的比例共享CPU資源，當系統處于過載狀態時，所有的任務的執行都會按比例地變慢。所以為了保證系統中實時進程能夠獲得一定的CPU處理時間，一般采用一種動態調節進程權重的方法。