第一部分： 實(shí)時(shí)調(diào)度算法介紹

對 于什么是實(shí)時(shí)系統(tǒng)，POSIX 1003.b作了這樣的定義：指系統(tǒng)能夠在限定的響應(yīng)時(shí)間內(nèi)提供所需水平的服務(wù)。而一個(gè)由Donald Gillies提出的更加為大家接受的定義是：一個(gè)實(shí)時(shí)系統(tǒng)是指計(jì)算的正確性不僅取決于程序的邏輯正確性，也取決于結(jié)果產(chǎn)生的時(shí)間，如果系統(tǒng)的時(shí)間約束條 件得不到滿足，將會(huì)發(fā)生系統(tǒng)出錯(cuò)。

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

一 個(gè)計(jì)算機(jī)系統(tǒng)為了提供對于實(shí)時(shí)性的支持，它的操作系統(tǒng)必須對于CPU和其他資源進(jìn)行有效的調(diào)度和管理。在多任務(wù)實(shí)時(shí)系統(tǒng)中，資源的調(diào)度和管理更加復(fù)雜。本 文下面將先從分類的角度對各種實(shí)時(shí)任務(wù)調(diào)度算法進(jìn)行討論，然后研究普通的Linux操作系統(tǒng)的進(jìn)程調(diào)度以及各種實(shí)時(shí)Linux系統(tǒng)為了支持實(shí)時(shí)特性對普通 Linux系統(tǒng)所做的改進(jìn)。最后分析了將Linux操作系統(tǒng)應(yīng)用于實(shí)時(shí)領(lǐng)域中時(shí)所出現(xiàn)的一些問題，并總結(jié)了各種實(shí)時(shí)Linux是如何解決這些問題的。

1. 實(shí)時(shí)CPU調(diào)度算法分類

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

1.1. 基于優(yōu)先級(jí)的調(diào)度算法

基于優(yōu)先級(jí)的調(diào)度算法給每個(gè)進(jìn)程分配一個(gè)優(yōu)先級(jí)，在每次進(jìn)程調(diào)度時(shí)，調(diào)度器總是調(diào)度那個(gè)具有最高優(yōu)先級(jí)的任務(wù)來執(zhí)行。根據(jù)不同的優(yōu)先級(jí)分配方法，基于優(yōu)先級(jí)的調(diào)度算法可以分為如下兩種類型[Krishna01][Wang99]：

靜態(tài)優(yōu)先級(jí)調(diào)度算法：

這 種調(diào)度算法給那些系統(tǒng)中得到運(yùn)行的所有進(jìn)程都靜態(tài)地分配一個(gè)優(yōu)先級(jí)。靜態(tài)優(yōu)先級(jí)的分配可以根據(jù)應(yīng)用的屬性來進(jìn)行，比如任務(wù)的周期，用戶優(yōu)先級(jí)，或者其它的 預(yù)先確定的策略。RM（Rate-Monotonic）調(diào)度算法是一種典型的靜態(tài)優(yōu)先級(jí)調(diào)度算法，它根據(jù)任務(wù)的執(zhí)行周期的長短來決定調(diào)度優(yōu)先級(jí)，那些具有 小的執(zhí)行周期的任務(wù)具有較高的優(yōu)先級(jí)。

動(dòng)態(tài)優(yōu)先級(jí)調(diào)度算法：

這 種調(diào)度算法根據(jù)任務(wù)的資源需求來動(dòng)態(tài)地分配任務(wù)的優(yōu)先級(jí)，其目的就是在資源分配和調(diào)度時(shí)有更大的靈活性。非實(shí)時(shí)系統(tǒng)中就有很多這種調(diào)度算法，比如短作業(yè)優(yōu) 先的調(diào)度算法。在實(shí)時(shí)調(diào)度算法中，EDF算法是使用最多的一種動(dòng)態(tài)優(yōu)先級(jí)調(diào)度算法，該算法給就緒隊(duì)列中的各個(gè)任務(wù)根據(jù)它們的截止期限（Deadline） 來分配優(yōu)先級(jí)，具有最近的截止期限的任務(wù)具有最高的優(yōu)先級(jí)。

1.2. 基于比例共享調(diào)度算法

雖然基于優(yōu)先級(jí)的調(diào)度算法簡單而有效，但這種調(diào)度算法提供的是一種硬實(shí)時(shí)的調(diào)度，在很多情況下并不適合使用這種調(diào)度算法：比如象實(shí)時(shí)多媒體會(huì)議系統(tǒng)這樣的軟實(shí)時(shí)應(yīng)用。對于這種軟實(shí)時(shí)應(yīng)用，使用一種比例共享式的資源調(diào)度算法（SD算法）更為適合。

比例共享調(diào)度算法指基于CPU使用比例的共享式的調(diào)度算法，其基本思想就是按照一定的權(quán)重（比例）對一組需要調(diào)度的任務(wù)進(jìn)行調(diào)度，讓它們的執(zhí)行時(shí)間與它們的權(quán)重完全成正比。

我們可以通過兩種方法來實(shí)現(xiàn)比例共享調(diào)度算法[Nieh01]：第一種方法是調(diào)節(jié)各個(gè)就緒進(jìn)程出現(xiàn)在調(diào)度隊(duì)列隊(duì)首的頻率，并調(diào)度隊(duì)首的進(jìn)程執(zhí)行；第二種做法就是逐次調(diào)度就緒隊(duì)列中的各個(gè)進(jìn)程投入運(yùn)行，但根據(jù)分配的權(quán)重調(diào)節(jié)分配個(gè)每個(gè)進(jìn)程的運(yùn)行時(shí)間片。

比例共享調(diào)度算法可以分為以下幾個(gè)類別：輪轉(zhuǎn)法、公平共享、公平隊(duì)列、彩票調(diào)度法（Lottery）等。

比例共享調(diào)度算法的一個(gè)問題就是它沒有定義任何優(yōu)先級(jí)的概念；所有的任務(wù)都根據(jù)它們申請的比例共享CPU資源，當(dāng)系統(tǒng)處于過載狀態(tài)時(shí)，所有的任務(wù)的執(zhí)行都會(huì)按比例地變慢。所以為了保證系統(tǒng)中實(shí)時(shí)進(jìn)程能夠獲得一定的CPU處理時(shí)間，一般采用一種動(dòng)態(tài)調(diào)節(jié)進(jìn)程權(quán)重的方法。