基于 Linux 的實時系統

越來越多的開發者在基于 Linux 系統構造嵌入式實時應用，他們迫切地需要一份基于 Linux系統構造嵌入式實時系統的指南性的文章?？紤]到這種需求，本文在介紹了幾種基本的實時進程調度算法的基礎上，研究了普通的 Linux操作系統的進程調度，并十分全面地調查了各種實時 Linux 系統為了支持實時特性對普通 Linux 系統所做的改進。文章分析了將 Linux操作系統應用于實時領域中時所出現的一些問題，并總結了各種實時 Linux是如何解決這些問題的，最后對于如何將這些已有的研究成果應用與實際的研究和開發工作中作了很好的建議。

作者 : 張煥強 (zhq@iscas.ac.cn )
中科院軟件研究所多媒體通信和網絡工程研究中心

越來越多的開發者在基于 Linux 系統構造嵌入式實時應用，他們迫切地需要一份基于 Linux系統構造嵌入式實時系統的指南性的文章?？紤]到這種需求，本文在介紹了幾種基本的實時進程調度算法的基礎上，研究了普通的 Linux操作系統的進程調度，并十分全面地調查了各種實時 Linux 系統為了支持實時特性對普通 Linux 系統所做的改進。文章分析了將 Linux操作系統應用于實時領域中時所出現的一些問題，并總結了各種實時 Linux是如何解決這些問題的，最后對于如何將這些已有的研究成果應用與實際的研究和開發工作中作了很好的建議。

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

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

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

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

1. 實時 CPU 調度算法分類

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

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

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

靜態優先級調度算法：

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

動態優先級調度算法：

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

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

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

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

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

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

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

1.3. 基于時間的進程調度算法

對于那些具有穩定、已知輸入的簡單系統，可以使用時間驅動（Time-driven:TD）的調度算法，它能夠為數據處理提供很好的預測性。這種調度算法本質上是一種設計時就確定下來的離線的靜態調度方法。在系統的設計階段，在明確系統中所有的處理情況下，對于各個任務的開始、切換、以及結束時間等就事先做出明確的安排和設計。這種調度算法適合于那些很小的嵌入式系統、自控系統、傳感器等應用環境。

這種調度算法的優點是任務的執行有很好的可預測性，但最大的缺點是缺乏靈活性，并且會出現有任務需要被執行而 CPU 卻保持空閑的情況。

2. 通用 Linux 系統中的 CPU 調度

通用 Linux 系統支持實時和非實時兩種進程，實時進程相對于普通進程具有絕對的優先級。對應地，實時進程采用 SCHED_FIFO 或者 SCHED_RR 調度策略，普通的進程采用 SCHED_OTHER 調度策略。

在調度算法的實現上，Linux 中的每個任務有四個與調度相關的參數，它們是 rt_priority、policy、priority（nice）、counter。調度程序根據這四個參數進行進程調度。

在SCHED_OTHER 調度策略中，調度器總是選擇那個 priority+counter值最大的進程來調度執行。從邏輯上分析，SCHED_OTHER 調度策略存在著調度周期（epoch），在每一個調度周期中，一個進程的priority 和 counter 值的大小影響了當前時刻應該調度哪一個進程來執行，其中 priority是一個固定不變的值，在進程創建時就已經確定，它代表了該進程的優先級，也代表這該進程在每一個調度周期中能夠得到的時間片的多少；counter是一個動態變化的值，它反映了一個進程在當前的調度周期中還剩下的時間片。在每一個調度周期的開始，priority 的值被賦給counter，然后每次該進程被調度執行時，counter 值都減少。當 counter值為零時，該進程用完自己在本調度周期中的時間片，不再參與本調度周期的進程調度。當所有進程的時間片都用完時，一個調度周期結束，然后周而復始。另外可以看出 Linux 系統中的調度周期不是靜態的，它是一個動態變化的量，比如處于可運行狀態的進程的多少和它們 priority 值都可以影響一個epoch 的長短。值得注意的一點是，在 2.4 以上的內核中，priority 被 nice 所取代，但二者作用類似。

可見 SCHED_OTHER 調度策略本質上是一種比例共享的調度策略，它的這種設計方法能夠保證進程調度時的公平性--一個低優先級的進程在每一個epoch 中也會得到自己應得的那些CPU執行時間，另外它也提供了不同進程的優先級區分，具有高 priority值的進程能夠獲得更多的執行時間。

對于實時進程來說，它們使用的是基于實時優先級 rt_priority 的優先級調度策略，但根據不同的調度策略，同一實時優先級的進程之間的調度方法有所不同：

SCHED_FIFO：不同的進程根據靜態優先級進行排隊，然后在同一優先級的隊列中，誰先準備好運行就先調度誰，并且正在運行的進程不會被終止直到以下情況發生：1.被有更高優先級的進程所強占 CPU；2.自己因為資源請求而阻塞；3.自己主動放棄 CPU（調用 sched_yield）；
SCHED_RR：這種調度策略跟上面的 SCHED_FIFO 一模一樣，除了它給每個進程分配一個時間片，時間片到了正在執行的進程就放棄執行；時間片的長度可以通過 sched_rr_get_interval 調用得到；

由于 Linux 系統本身是一個面向桌面的系統，所以將它應用于實時應用中時存在如下的一些問題：
Linux 系統中的調度單位為10ms，所以它不能夠提供精確的定時；
當一個進程調用系統調用進入內核態運行時，它是不可被搶占的；
Linux 內核實現中使用了大量的封中斷操作會造成中斷的丟失；
由于使用虛擬內存技術，當發生頁出錯時，需要從硬盤中讀取交換數據，但硬盤讀寫由于存儲位置的隨機性會導致隨機的讀寫時間，這在某些情況下會影響一些實時任務的截止期限；
雖然 Linux 進程調度也支持實時優先級，但缺乏有效的實時任務的調度機制和調度算法；它的網絡子系統的協議處理和其它設備的中斷處理都沒有與它對應的進程的調度關聯起來，并且它們自身也沒有明確的調度機制；

3. 各種實時 Linux 系統

3.1. RT- Linux 和 RTAI

RT-Linux 是新墨西哥科技大學（New Mexico Institute of Technology）的研究成果[RT LinuxWeb][Barabanov97]。它的基本思想是，為了在 Linux系統中提供對于硬實時的支持，它實現了一個微內核的小的實時操作系統（我們也稱之為 RT- Linux 的實時子系統），而將普通 Linux系統作為一個該操作系統中的一個低優先級的任務來運行。另外普通 Linux 系統中的任務可以通過 FIFO 和實時任務進行通信。RT-Linux 的框架如圖 1所示：

javascript:window.open(this.src);" style="CURSOR: pointer" onload="return imgzoom(this,550)">
圖 1 RT- Linux 結構

RT-Linux 的關鍵技術是通過軟件來模擬硬件的中斷控制器。當 Linux 系統要封鎖CPU的中斷時時，RT- Linux中的實時子系統會截取到這個請求，把它記錄下來，而實際上并不真正封鎖硬件中斷，這樣就避免了由于封中斷所造成的系統在一段時間沒有響應的情況，從而提高了實時性。當有硬件中斷到來時，RT- Linux 截取該中斷，并判斷是否有實時子系統中的中斷例程來處理還是傳遞給普通的 Linux內核進行處理。另外，普通 Linux 系統中的最小定時精度由系統中的實時時鐘的頻率決定，一般 Linux 系統將該時鐘設置為每秒來 100個時鐘中斷，所以 Linux 系統中一般的定時精度為 10ms，即時鐘周期是 10ms，而 RT- Linux通過將系統的實時時鐘設置為單次觸發狀態，可以提供十幾個微秒級的調度粒度。

RT- Linux 實時子系統中的任務調度可以采用 RM、EDF 等優先級驅動的算法，也可以采用其他調度算法。

RT-Linux 對于那些在重負荷下工作的專有系統來說，確實是一個不錯的選擇，但他僅僅提供了對于 CPU 資源的調度；并且實時系統和普通 Linux系統關系不是十分密切，這樣的話，開發人員不能充分利用 Linux 系統中已經實現的功能，如協議棧等。所以 RT- Linux適合與工業控制等實時任務功能簡單，并且有硬實時要求的環境中，但如果要應用與多媒體處理中還需要做大量的工作。

意大利的RTAI ( Real-Time Application Interface ) 源于 RT- Linux ，它在設計思想上和 RT-Linux 完全相同。它當初設計目的是為了解決 RT- Linux 難于在不同 Linux 版本之間難于移植的問題，為此，RTAI 在Linux 上定義了一個實時硬件抽象層，實時任務通過這個抽象層提供的接口和 Linux 系統進行交互，這樣在給 Linux內核中增加實時支持時可以盡可能少地修改 Linux 的內核源代碼。

3.2. Kurt- Linux

Kurt-Linux 由 Kansas 大學開發，它可以提供微秒級的實時精度 [KurtWeb] [Srinivasan]。不同于 RT- Linux單獨實現一個實時內核的做法，Kurt - Linux 是在通用 Linux 系統的基礎上實現的，它也是第一個可以使用普通 Linux系統調用的基于 Linux 的實時系統。

Kurt- Linux 將系統分為三種狀態：正常態、實時態和混合態，在正常態時它采用普通的 Linux 的調度策略，在實時態只運行實時任務，在混合態實時和非實時任務都可以執行；實時態可以用于對于實時性要求比較嚴格的情況。

為了提高 Linux系統的實時特性，必須提高系統所支持的時鐘精度。但如果僅僅簡單地提高時鐘頻率，會引起調度負載的增加，從而嚴重降低系統的性能。為了解決這個矛盾，Kurt- Linux 采用 UTIME 所使用的提高 Linux 系統中的時鐘精度的方法[UTIMEWeb]：它將時鐘芯片設置為單次觸發狀態（One shotmode），即每次給時鐘芯片設置一個超時時間，然后到該超時事件發生時在時鐘中斷處理程序中再次根據需要給時鐘芯片設置一個超時時間。它的基本思想是一個精確的定時意味著我們需要時鐘中斷在我們需要的一個比較精確的時間發生，但并非一定需要系統時鐘頻率達到此精度。它利用 CPU 的時鐘計數器TSC (Time Stamp Counter) 來提供精度可達 CPU 主頻的時間精度。

對于實時任務的調度，Kurt- Linux 采用基于時間（TD）的靜態的實時 CPU 調度算法。實時任務在設計階段就需要明確地說明它們實時事件要發生的時間。這種調度算法對于那些循環執行的任務能夠取得較好的調度效果。

Kurt-Linux 相對于 RT- Linux 的一個優點就是可以使用 Linux系統自身的系統調用，它本來被設計用于提供對硬實時的支持，但由于它在實現上只是簡單的將 Linux調度器用一個簡單的時間驅動的調度器所取代，所以它的實時進程的調度很容易受到其它非實時任務的影響，從而在有的情況下會發生實時任務的截止期限不能滿足的情況，所以也被稱作嚴格實時系統（Firm Real-time）。目前基于 Kurt- Linux 的應用有：ARTS（ATMReference Traffic System）、多媒體播放軟件等。另外 Kurt- Linux所采用的這種方法需要頻繁地對時鐘芯片進行編程設置。

3.3. RED- Linux

RED-Linux 是加州大學Irvine分校開發的實時 Linux 系統 [REDWeb][ Wang99]，它將對實時調度的支持和 Linux很好地實現在同一個操作系統內核中。它同時支持三種類型的調度算法，即：Time-Driven、Priority-Dirven、Share-Driven。

為了提高系統的調度粒度，RED- Linux 從RT- Linux那兒借鑒了軟件模擬中斷管理器的機制，并且提高了時鐘中斷頻率。當有硬件中斷到來時，RED- Linux的中斷模擬程序僅僅是簡單地將到來的中斷放到一個隊列中進行排隊，并不執行真正的中斷處理程序。

另外為了解決 Linux 進程在內核態不能被搶占的問題， RED- Linux 在 Linux 內核的很多函數中插入了搶占點原語，使得進程在內核態時，也可以在一定程度上被搶占。通過這種方法提高了內核的實時特性。

RED- Linux 的設計目標就是提供一個可以支持各種調度算法的通用的調度框架，該系統給每個任務增加了如下幾項屬性，并將它們作為進程調度的依據：
Priority：作業的優先級；
Start-Time：作業的開始時間；
Finish-Time：作業的結束時間；
Budget：作業在運行期間所要使用的資源的多少；

通過調整這些屬性的取值及調度程序按照什么樣的優先順序來使用這些屬性值，幾乎可以實現所有的調度算法。這樣的話，可以將三種不同的調度算法無縫、統一地結合到了一起。

RED- Linux 調度程序的框架結構如圖 2 所示：



圖 2 RED- Linux 調度框架

RED- Linux 的調度程序由兩部分組成，其中 Schedule Allocator 初始化到來的job中的屬性值；Schedule Dispatcher 根據job的屬性值選擇一個 job 進行執行；

3.4. Linux /RK

Linux /RK 由卡內基梅隆大學實時和多媒體系統實驗室所開發 [RKWeb][ Oikawa98]。它是該實驗室資源內核（ResourceKernel）[Rajkumar98] 思想在 Linux 系統中的具體實現。他們最先在 RT-MACH中實現了資源內核的思想，后來又用資源內核的思想對 Linux進行了修改。資源內核的概念是網絡中資源預留思想在操作系統領域的擴展，應用程序先向操作系統請求預留資源，而操作系統內核在給應用進行資源預留，并能給應用提供有及時的、保證的資源訪問。

資源內核中有兩個基本的概念：資源預留和資源集。一個資源預留代表一份計算資源，這個資源可以是CPU、內存、磁盤、網絡帶寬等。在內核中，一個資源預留有對應的描述它的數據結構，而一個資源集指一組資源預留的集合。一般情況下我們將某一個應用程序所請求的所有資源預留組合在一起組成一個資源集，這樣方便管理和分配。

Linux /RK 增強了普通 Linux內核的功能，從而使 Linux 內核可以提供對于系統中各種計算資源的準入控制、資源預留和統計管理。 Linux /RK 由兩部分組成：普通的Linux 內核以及可移植的資源內核；這兩個部分之間通過回調鉤子函數（Callback hooks）進行交互。類似于 RT- Linux，為了防止 Linux 內核中的封中操作以及提高調度精度， Linux /RK也截取系統中的中斷，并提高了系統時鐘頻率，只有在需要的時侯才將中斷送給 Linux 內核。另外它使用 Proc文件系統來顯示資源預留和使用的情況；

3.5. Q Linux

Q Linux 是由 AT&T、德州大學分布式多媒體計算實驗室和馬薩諸塞大學高級系統軟件實驗室聯合開發出來的一種軟實時 (soft real-time) 核心[Q Linux Web]。它能夠為實時多媒體應用提供 QoS 支持。
Q Linux 實現了近年來操作系統領域內一些最新的研究成果，包括：

- H-SFQ 資源調度算法（Hierarchical Start-time Fair Queuing）[Goyal96]；

- 網絡包的延遲處理技術（Lazy Receiver Processing:LRP）[Druschel96]；

- Cello 磁盤調度算法 [Shenoy98]；



圖 3 Q Linux 系統結構

H-SFQ資源調度算法由由德州大學的 Pawan Goyal等人提出，它采用了一種分級調度的思想，先將資源在不同的應用類別之間進行按比例分配，并在應用類別之間提供對于資源使用的隔離，同時在每一個應用類別中還可以使用不同的資源調度算法。這樣做的目的是為了在多媒體系統中提供 QoS 支持。

LRP 技術是一種新穎的設計 OS 網絡子系統的思想，它由 Rice 大學計算機系的 Peter Druschel 等人提出，其目的是為了解決普通 Unix 和類 Unix 系統中網絡包接收的問題。

傳統的 Unix 系統沒有對到來的網絡包的協議處理的顯式調度，它們一般采用中斷驅動的機制。當網卡有中斷時，CPU就立刻進行一系列由網卡中斷程序啟動的包接收和協議處理操作，將最終的數據送給等待接收的進程，并喚醒該進程。但這種處理方式會影響應用程序資源調度的性能，并在系統處于過載狀態時可能會引起一些應用層任務的饑餓，降低網絡吞吐率，甚至會讓系統沒有響應。為了解決這些問題，LRP 的核心思想就是每一個Socket 有一個 IP包的隊列，只有當上層應用程序請求數據時才進行協議處理，同時對協議處理操作以請求數據的應用的優先級進行顯式的調度。通過這種途徑增強了資源調度的公平性，能夠提供一定程度的流量隔離，同時能夠提高系統過載狀態時的吞吐量。

Cello 磁盤調度算法由德州大學 Prashant J. Shenoy 等人提出。它能夠支持多種應用類別，比如：交互式盡力而為應用、大吞吐量盡力而為應用、以及軟實時應用等類別，并公平地給各個類別的應用分配磁盤訪問帶寬。

在結構上 Cello 磁盤調度采用的是一種兩級式的調度方式，它由多個與應用類別相關的調度器以及一個與應用類別無關的調度器組成（如圖 4所示）。



圖 4 Cello 磁盤調度

Cello調度算法中應用類別無關的調度器管理時間上粗粒度的磁盤的調度，而應用相關的調度器控制著小粒度上磁盤調度。如上圖中有n個應用類別，Cello使用一個應用無關的調度器C和n個類別相關的調度器，系統中有n+1個調度隊列。類別無關的調度器C決定你了何時以及多少磁盤請求被從等待隊列（pendingqueue）移到調度隊列（scheduledqueue）；類別相關的調度器Si對等待隊列中的請求進行排序，并根據調度隊列的狀態來決定磁盤請求被插入到調度隊列的什么位置。

3.6. Linux -SRT

Linux-SRT是劍橋大學David Ingram的博士論文項目 [SRTWeb][Ingram00]，基本上是一個實驗性的東西，自從 Ingram在 2000 年從劍橋畢業以后，該項目就再沒有人維護。跟 Q Linux 一樣， Linux -SRT 屬于軟實時的 Linux。

在Linux -SRT 中可以給一個任務分配一定百分比的 CPU 時間，它通過 RM 算法實現了一種基于速率的調度機制來保證給所有多媒體應用的QoS 需求；另外由于 CPU 并非唯一影響多媒體應用的資源，對于那些做圖形顯示的應用，X 服務器中的資源調度也十分關鍵，所以 Linux-SRT 對 XFree86 最了擴展，讓 X 服務器可以對來自不同X客戶的圖形顯示請求進行優先級排序；另外為了方便用戶管理各個進程的 CPU分配情況， Linux -SRT 提供了一個圖形界面的程序。下面對于 Linux -SRT 對于普通 Linux 所作的修改做一具體說明。

Linux -SRT 也提高了系統的定時精度。但它并沒有采用慣用的將時鐘芯片置于單次觸發模式的做法，而是簡單地修改了 Linux 內核中HZ的定義，將 Linux 的時鐘頻率由每秒 100 次提高到了 1024。

另外 Linux -SRT 在原有的 Linux 系統中的 SCHED_OTHER、SCHED_FIFO、SCHED_RR這三個調度策略的基礎上，給 Linux增加了一些新的調度策略：SCHED_PAUSE、SCHED_IDLE、SCHED_QOS、SCHED_VAR；策略為 SCHED_PAUSE的進程在調度時被調度程序忽略，不參與調度執行；使用 SCHED_QOS 調度策略的進程能夠得到有保證的 CPU 執行時間；使用SCHED_IDLE 策略的進程優先級最低，它被分配給那些只在系統空閑時才能夠被調度執行的進程，比如一些批處理程序；SCHED_VAR是一個可變優先級的策略，它被用于解決由于臨界資源訪問時所產生的優先級倒置問題，即一個高優先級的任務等待低優先級任務占用的某種臨界資源，但低優先級任務又得不到CPU處理時間所造成的死鎖問題；這時通過該調度策略將低優先級任務的優先級置為等待資源的高優先級任務的優先級（優先級繼承）來解決死鎖問題。

對于使用 SCHED_QOS調度策略的實時任務，采用RM靜態優先級調度算法進行調度；另外在進行調度時，它還采用了一種雙調度策略的方案，即當一個實時任務在當前的調度周期中用完自己所有的時間片之后，在下次調度周期到來之前，并非簡單地不調度執行它，而是使用它進程屬性中的 Fallback policy所定義的調度策略來調度它，讓它以該策略參與本輪的剩余時間的調度。

Linux -SRT 按照 POSIX推薦的方式擴展了傳統的幾個用戶設置進程調度屬性的系統調度，讓用戶或者編程人員可以在后向兼容的情況下使用這些新添加的調度特性。另外為了使用的方便，它還提出了 reserve 的概念，一個 reserve 在 /proc 文件系統中有一個結點，它包含有關資源分配的情況；reserve獨立與進程，一個進程可以通過新增加的 reserve 相關的系統調用申請加入（使用）或退出一個 reserve。

3.7. Hard-hat Linux

HardhatLinux 是 MontaVista 公司所發布的一款主要面向各種嵌入式應用的 Linux 發布[HardHatWeb][Morgan01]。Hard-hat Linux 最大的貢獻在于：為了解決 Linux在內核態不可被搶占的問題，它開發了一種搶占式（Preemptible）的內核，有人認為它的這種方法充其量也就是一種能夠被搶占（Preemptable）的內核。

其基本思想就是讓調度程序獲得更多的執行機會，從而減少了從一個事件發生到調度程序被執行的時間間隔?？蓳屨純群说难a丁包修改了 spinlock的宏定義以及中斷返回處理代碼，當當前進程可以被"安全"地搶占并且有一個等待處理的重新調度請求，系統就會調用調度程序進行進程調度。

那么什么情況下可以認為一個進程可以被 "安全" 地搶占？最早的 Linux內核代碼認為，一旦進入內核態執行，不管是由于陷入（trap）還是中斷處理，當前執行進程都不會被切換，直到內核認為可以安全地進行重新調度為止。這種思想可以使得內核代碼對一些數據結構進行操作時比較簡單，即不需要使用互斥原語（比如旋轉鎖spinlock）進行數據的修改保護就可以安全地存取數據。但隨著內核源代碼的發展，不使用保護機制的內核數據訪問代碼越來越少，所以在搶占式內核中，認為如果內核不是在一個中斷處理程序中，并且不再 spinlock 保護的代碼中，就認為可以"安全"地進行進程切換。

搶占式內核對普通 Linux 內核作了如下的一些修改：
搶占式內核給task struct數據結構增加了一個數據項：preempt_count。該數據項由宏preempt_disable()、preempt_enable()、以及 preempt_enable_no_resched()所使用。preempt_disable 對 preempt_count 計數進行遞增，preempt_enable 對preempt_count 進行遞減。preempt_enable 宏查看當前進程的 preempt_count和need_resched域的內容，如果 preempt_count 為 0 并且 need_resched 為 1，則調用 preempt_schedule()函數。該函數將給當前進程的 preempt_count 項增加一個很大的值（比如讓preempt_counter=preempt_counter + 0x4000000），然后調用進程調度函數schedule()，在schedule函數返回后從該進程 preempt_count 中再減去該值?？蓳屨純群艘残薷牧?schedule函數，它檢測進程的 preempt_counter是否很大（這是為了屏蔽一些普通調度流程中對于搶占式調度來說是冗余的那些操作），然后執行搶占式調度。
搶占式內核補丁也修改了 spinlock 的代碼。在 spin_lock() 和 spin_try_lock 中增加了對于 preempt_disable 的調用，在 spin_unlock() 中增加了對于 preempt_enable 的調用。
另外搶占式內核補丁還修改了中斷返回的代碼，在其中增加了對于 preempt_enable 的調用。

所以我們根據上面的三個修改可以看出，內核的搶占式調度發生在如下情況：在釋放 spinlock 時，或者當中斷返回時，如果當前執行進程的 need_resched 被標記，則進行搶占式調度。

3.8. SILK

SILK代表 SCOUT In Linux Kernel，它是普林斯頓大學支持 PATH 調度的垂直結構操作系統 SCOUT 在 Linux中的一個實現[SILKWeb][Bavier01]。它將 SCOUT 操作系統作為 Linux 的一個模塊來實現。

SILK系統的主要目的就是為一些網絡 QoS 提供支持，它支持對于網絡包處理的顯式的調度，并且這個調度是以 PATH 為單位進行的。PATH概念的新穎之處在于，不像傳統的基于任務的調度方式，它從另外一個角度進行系統的資源調度，即以網絡的數據流及其處理為單位進行調度。詳細來說，一個PATH 由一串當數據流流經系統時進行數據處理或者數據轉換的代碼模塊組成，并且對應的數據流所消耗的資源也歸該 PATH。研究表明，PATH這種體系結構特別適用于有 QoS 要求的分布式多媒體系統以及軟件路由設備中。下圖對于什么是 PATH 作了一個圖示，它說明了一個 TCPPATH：



圖 5 一個TCP PATH

在實現上，SILK 系統將 Linux 系統中的網絡子系統替換成了自己的協議棧。 Linux 應用程序通過 Socket 來創建和使用 PATHs，幾乎不用對應用程序本身作任何修改。

圖6 說明了 SILK 系統的結構。在圖的左半部分，SILK 模塊和網絡設備驅動、SOCKET 接口層、以及包過濾接口 netfilter通過標準的方式交換數據。SILK 還修改了 Linux 任務的調度參數，以便影響 Linux 進程調度程序的調度決策。圖的右半部分示意了SILK 中的兩個 PATH。SILK 模塊有自己的CPU調度器，它和 Linux 系統中的 CPU 調度器進行合作和協調。這個合作由圖中的Linux thread 代表，通過執行這個線程，SILK 將控制轉給 Linux 調度程序。



圖 6 SILK 系統結構示意圖

SILK在操作系統中提供了一個新的 SOCKET 協議族以便上層應用程序調用下層的 SCOUT PATH。為了在 Linux 進行網絡包處理之前截獲IP 包，SILK 通過 Linux 2.4 內核的 netfilter 接口插入了一個 netfilterhook，所有到來的IP包會被重定向到該 hook 上，如果SILK找到一個對應于該網絡包的 PATH，就讓 Linux 內核丟棄該包，而由SILK 對包進行處理。

關于 CPU 調度，SILK 有著自己的CPU調度程序和線程包，它們和 Linux系統的調度程序并存，在有 SILK 的 Linux 系統中，我們一般把由 SILK 調度的歸屬于某個 PATH 的處理叫做 SILK線程（thread），而普通的由 Linux 調度程序調度的東西都叫做任務（task）；SILK 在一個 Linux內核任務的基礎上實現它的線程調度，這個內核任務當 SILK 進行初始化的時候創建，并且將該內核任務的優先級設為優先級最高的實時任務，所以SILK 的內核任務幾乎是只要它就緒就可以投入運行，并且只有當該內核任務主動初讓 CPU 時 Linux系統中的其他普通任務才能夠得以運行。SILK 將 CPU 出讓給普通的 Linux 任務是通過調度 SILK thread 中的一個叫做Linux thread 的線程來實現的，該 Linux thread 本質上就是在 SILK 的調度空間中代表 Linux的普通調度程序。SILK 在調用 Linux thread 之后，代表SILK的內核任務就被 Linux的進程調度程序設置為非就緒狀態，直到它運行一個其他的進程之后，高優先級得 SILK 內核任務就又得到 CPU。所以這種實現機制可以讓SILK在調度 Linux thread 時，Linux 調度程序可以有機會調度一個其他的進程執行。

4. 實時 Linux 實現方案的總結

總結上述的各種實時 Linux 的實現，它們針對不同的設計目標，從不同的側重點解決了通用 Linux 操作系統對實時性支持的問題。

針對 Linux 系統定時粒度過大的問題，一般的解決辦法都是將實時時鐘編程為單次觸發的狀態，然后利用 CPU 的時鐘計數寄存器提供高達 CPU 時鐘頻率的定時精度。像 RT- Linux 和 Kurt- Linux 采用的就是這種方法。

對于 Linux 進程在進入內核態時不能被搶占的問題，目前的解決辦法有 RED- Linux 在內核函數中插入搶占點的方法，另外 Hardhat 也通過修改 spinlock 的宏定義以及中斷返回處理代碼，實現了一種可搶占的內核；

對于 Linux 驅動程序中的封中斷的方法，RT- Linux 所使用的軟件模擬中斷控制器的方法可以有效地解決這個問題；

對于 Linux 系統中缺乏實時調度機制和調度算法的問題，目前有很多新穎的操作系統調度框架和調度算法都有 Linux 實現，比如 RED-Linux 所定義的一個通用的實時調度框架；Q Linux 所采用的分層式的 CPU 調度框架，及新穎的調度算法如 H-SFQ，以及Cello 磁盤調度算法等；SILK 所使用的將對一個包的網絡處理抽象成 PATH，然后在 PATH 之間進行調度。

對于內核中協議處理以及中斷處理的調度，解決辦法基本上是一種延遲處理的技術，即到來的協議包在網卡中斷處理中僅僅將它拷貝到一個隊列中，只有當上層的應用程序請求數據包時才進行協議處理，并將對協議的處理時間記到對應的進程中。另外SILK對于那些網絡路由結點，由于路由等的處理并沒有對應的上層應用程序，所以SILK在內核的網絡處理之間進行明確的調度。

所以，總的來說，從發展方向上來說，實時 Linux 的發展有如下四個思路：
提供對于硬實時的支持，具體辦法有：提高時鐘精度，解決封中斷和內核態不能被搶占的問題，代表系統 RT- Linux 、Kurt- Linux，其實大部分實時 Linux 都使用了類似與 RT- Linux 的提高時鐘精度和軟件中斷管理器的思想；總的來說，讓內核支持硬實時和使用傳統的Linux 的豐富的系統調用之間存在著矛盾，以至于像 RT- Linux就是單獨實現了一個獨立的小的硬實時操作系統；但由于軟件模擬終端控制器、提高時鐘精度、以及可搶占內核等思想的引入，這個矛盾慢慢地得到化解。
提供對于實時多媒體應用的支持，舉措：引入新穎的調度算法（網絡包調度，進程調度，磁盤調度），代表系統：Q Linux 、 Linux -SRT；
引入新穎的調度框架以及資源管理思想以更好地支持網絡系統中的 QoS 要求，比如SILK中的垂直結構的操作系統調度的思想，Q Linux中的分級調度的思想，以及 RED- Linux 所提出來的一個通用的調度框架和 Linux /RK 中所使用的資源預留的思想；
方便的任務 QoS 管理接口函數和管理程序的實現，比如 Linux /RK 提出的操作系統中各種資源的資源預留的概念； Linux -SRT 中為了用戶方便地使用新增加的實時調度支持而增加了 API，以及提出的 reserve 的概念等；

在實際的系統中，具體使用那種實時 Linux技術，需要根據具體的系統需求而定。如果目標系統是像機床控制或者導彈飛行姿態控制這樣的硬實時系統，那基于 RT- Linux是一個不錯的方案；如果一個系統對于實時性的要求不是那么嚴格，但又不是軟實時系統，那么可以借鑒 Kurt- Linux 的想想以及一些為了提高Linux響應速度而提出的可搶占內核的想法；如果目標系統是一個像實時多媒體系統這樣的軟實時應用，或者一個希望能夠在高負載狀態下提供更好的吞吐率的服務器系統，那么 Q Linux 和 RED- Linux 的思想提供了很好的參考；如果是將 Linux 應用于像路由器這樣的網絡結點中，可以借鑒SILK 的實現思想。

參考文獻

[Wang99]
Yu-Chung Wangand Kwei-Jay Lin, Implementing a General Real-Time Scheduling Frameworkin the RED- Linux Real-Time Kernel, IEEE Real-Time Systems Symposium,1999

[Gopalan01]
Kartik Gopalan, Real-Time Support in General Purpose Operating Systems, Tech Report, 2001

[Krishna01]
C.M.Krishna, Kang G.Shin, Real-time Systems, Tsinghua Press, 2001

[Nieh01]
JasonNieh, Chris Vaill, Hua Zhong, Virtual-Time Round-Robin: An O(1)Proportional Share Scheduler, Proceedings of the 2001 USENIX AnnualTechnical Conference, 2001

[RT Linux Web]
http://www.rt Linux .org/ or http://fsmlabs.com/

[Barabanov97]
MichaelBarabanov, A Linux -based Real-Time Operating System, A Master Thesis,New Mexico Institute of Mining and Technology, Socorro, New Mexico,1997

[KurtWeb]
http://www.ittc.ku.edu/kurt/

[Srinivasan]
BalajiSrinivasan, A Firm Real-Time System Implementation using CommercialOff-The-Shelf Hardware and Free Software, Master Thesis, Department ofElectrical Engineering and Computer Science, University of Kansas, Feb,1998

[REDWeb]
http:// Linux .ece.uci.edu/RED- Linux/

[RKWeb]
http://www-2.cs.cmu.edu/~rajkumar/ Linux -rk.html

[Rajkumar98]
RajRajkumar, Kanaka Juvva, Anastasio Molano and Shui Oikawa, ResourceKernels: A Resource-Centric Approach to Real-Time Systems, InProceedings of the SPIE/ACM Conference on Multimedia Computing andNetworking January 1998

[Oikawa98]
Shui Oikawa and RajRajkumar, Linux /RK: A Portable Resource Kernel in Linux , In IEEEReal-Time Systems Symposium Work-In-Progress, Madrid, December 1998

[Q Linux Web]
http://lass.cs.umass.edu/software/qLinux/

[Goyal96]
P.Goyal and X. Guo and H.M. Vin, A Hierarchical CPU Scheduler forMultimedia Operating Systems, Proceedings of 2nd Symposium on OperatingSystem Design and Implementation (OSDI'96), Seattle, WA, pages 107-122,October 1996.

[Druschel96]
Peter Druschel, Gaurav Banga,Lazy Receiver Processing(LRP): A Network Subsystem Architecture forServer Systems, Proceedings of the 2nd Symposium on Operating SystemDesign and Implementation (OSDI'96), Seattle, WA, Pages 261-275,October 1996

[Shenoy98]
P Shenoy and H M. Vin, Cello: ADisk Scheduling Framework for Next Generation Operating Systems,Proceedings of ACM SIGMETRICS Conference, Madison, WI, pages 44-55,June 1998.

[SRTWeb]
http://www.srcf.ucam.org/~dmi1000/ Linux -srt/

[Ingram00]
David Ingram, Integrated Quality of Service Management, Ph.D. Thesis, Jesus College, University of Cambridge, 2000

[HardHatWeb]
http://www.montavista.com/

[Morgan01]
Kevin Morgan, Preemptible Linux : A Reality Check, MontaVista White Paper, 2001

[SILKWeb]
http://www.cs.princeton.edu/nsg/scout/

[Bavier01]
AndyBavier, Thiemo Voigt, Mike Wawrzoniak, Larry Peterson, SILK: ScoutPaths in the Linux Kernel, Technical Report, Nov 2001

[UTIMEWeb]
http://www.ittc.ku.edu/utime/

作者信息

張煥強，男，中國科學院軟件研究所多媒體通信和網絡工程研究中心博士，研究興趣為家庭網絡、實時系統、視頻會議等。通過 zhq@iscas.ac.cn 可以和他聯系。

全文出自 : IBM DeveloperWorks 中國網站

原文轉自：http://www.anti-gravitydesign.com