第一部分： 實時調度算法介紹 對於什麼是實時系統，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處理時間，一般采用一種動態調節進程權重的方法。 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）的研究成果[RTLinuxWeb][Barabanov97]。它的基本思想是，為了在Linux系統中提供對於硬實時的支持，它實現了一個微內核的小的實時操作系統（我們也稱之為RT-Linux的實時子系統），而將普通Linux系統作為一個該操作系統中的一個低優先級的任務來運行。另外普通Linux系統中的任務可以通過FIFO和實時任務進行通信。RT-Linux的框架如圖 1所示：
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 shot mode），即每次給時鐘芯片設置一個超時時間，然後到該超時事件發生時在時鐘中斷處理程序中再次根據需要給時鐘芯片設置一個超時時間。它的基本思想是一個精確的定時意味著我們需要時鐘中斷在我們需要的一個比較精確的時間發生，但並非一定需要系統時鐘頻率達到此精度。它利用CPU的時鐘計數器TSC(Time Stamp Counter)來提供精度可達CPU主頻的時間精度。 對於實時任務的調度，Kurt-Linux采用基於時間（TD）的靜態的實時CPU調度算法。實時任務在設計階段就需要明確地說明它們實時事件要發生的時間。這種調度算法對於那些循環執行的任務能夠取得較好的調度效果。 Kurt-Linux相對於RT-Linux的一個優點就是可以使用Linux系統自身的系統調用，它本來被設計用於提供對硬實時的支持，但由於它在實現上只是簡單的將Linux調度器用一個簡單的時間驅動的調度器所取代，所以它的實時進程的調度很容易受到其它非實時任務的影響，從而在有的情況下會發生實時任務的截止期限不能滿足的情況，所以也被稱作嚴格實時系統（Firm Real-time）。目前基於Kurt-Linux的應用有：ARTS（ATM Reference 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所示：
RED-Linux的調度程序由兩部分組成，其中Schedule Allocator初始化到來的job中的屬性值；Schedule Dispatcher根據job的屬性值選擇一個job進行執行； 3.4. Linux/RK Linux/RK由卡內基梅隆大學實時和多媒體系統實驗室所開發[RKWeb][ Oikawa98]。它是該實驗室資源內核（Resource Kernel）[Rajkumar98]思想在Linux系統中的具體實現。他們最先在RT-MACH中實現了資源內核的思想，後來又用資源內核的思想對Linux進行了修改。資源內核的概念是網絡中資源預留思想在操作系統領域的擴展，應用程序先向操作系統請求預留資源，而操作系統內核在給應用進行資源預留，並能給應用提供有及時的、保證的資源訪問。 資源內核中有兩個基本的概念：資源預留和資源集。一個資源預留代表一份計算資源，這個資源可以是CPU、內存、磁盤、網絡帶寬等。在內核中，一個資源預留有對應的描述它的數據結構，而一個資源集指一組資源預留的集合。一般情況下我們將某一個應用程序所請求的所有資源預留組合在一起組成一個資源集，這樣方便管理和分配。 Linux/RK增強了普通Linux內核的功能，從而使Linux內核可以提供對於系統中各種計算資源的准入控制、資源預留和統計管理。Linux/RK由兩部分組成：普通的Linux內核以及可移植的資源內核；這兩個部分之間通過回調鉤子函數（Callback hooks）進行交互。類似於RT-Linux，為了防止Linux內核中的封中操作以及提高調度精度，Linux/RK也截取系統中的中斷，並提高了系統時鐘頻率，只有在需要的時侯才將中斷送給Linux內核。另外它使用Proc文件系統來顯示資源預留和使用的情況； 3.5. Qlinux Qlinux是由AT&T、德州大學分布式多媒體計算實驗室和馬薩諸塞大學高級系統軟件實驗室聯合開發出來的一種軟實時(soft real-time)核心[QLinuxWeb]。它能夠為實時多媒體應用提供QoS支持。 QLinux實現了近年來操作系統領域內一些最新的研究成果，包括： - H-SFQ資源調度算法（Hierarchical Start-time Fair Queuing）[Goyal96]； - 網絡包的延遲處理技術（Lazy Receiver Processing:LRP）[Druschel96]； - Cello磁盤調度算法[Shenoy98]；
圖 3 QLinux系統結構
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決定你了何時以及多少磁盤請求被從等待隊列（pending queue）移到調度隊列（scheduled queue）；類別相關的調度器Si對等待隊列中的請求進行排序，並根據調度隊列的狀態來決定磁盤請求被插入到調度隊列的什麼位置。 3.6. Linux-SRT Linux-SRT是劍橋大學David Ingram的博士論文項目[SRTWeb][Ingram00]，基本上是一個實驗性的東西，自從Ingram在2000年從劍橋畢業以後，該項目就再沒有人維護。跟QLinux一樣，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 Hardhat Linux是MontaVista公司所發布的一款主要面向各種嵌入式應用的Linux發布[HardHatWeb][Morgan01]。Hard-hat Linux最大的貢獻在於：為了解決Linux在內核態不可被搶占的問題，它開發了一種搶占式（Preemptible）的內核，有人認為它的這種方法充其量也就是一種能夠被搶占（Preemptable）的內核。 其基本思想就是讓調度程序獲得更多的執行機會，從而減少了從一個事件發生到調度程序被執行的時間間隔。可搶占內核的補丁包修改了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作了一個圖示，它說明了一個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接口插入了一個netfilter hook，所有到來的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所定義的一個通用的實時調度框架；QLinux所采用的分層式的CPU調度框架，及新穎的調度算法如H-SFQ，以及Cello磁盤調度算法等；SILK所使用的將對一個包的網絡處理抽象成PATH，然後在PATH之間進行調度。 對於內核中協議處理以及中斷處理的調度，解決辦法基本上是一種延遲處理的技術，即到來的協議包在網卡中斷處理中僅僅將它拷貝到一個隊列中，只有當上層的應用程序請求數據包時才進行協議處理，並將對協議的處理時間記到對應的進程中。另外SILK對於那些網絡路由結點，由於路由等的處理並沒有對應的上層應用程序，所以SILK在內核的網絡處理之間進行明確的調度。 所以，總的來說，從發展方向上來說，實時Linux的發展有如下四個思路： 提供對於硬實時的支持，具體辦法有：提高時鐘精度，解決封中斷和內核態不能被搶占的問題，代表系統RT-Linux、Kurt-Linux，其實大部分實時Linux都使用了類似與RT-Linux的提高時鐘精度和軟件中斷管理器的思想；總的來說，讓內核支持硬實時和使用傳統的Linux的豐富的系統調用之間存在著矛盾，以至於像RT-Linux就是單獨實現了一個獨立的小的硬實時操作系統；但由於軟件模擬終端控制器、提高時鐘精度、以及可搶占內核等思想的引入，這個矛盾慢慢地得到化解。 提供對於實時多媒體應用的支持，舉措：引入新穎的調度算法（網絡包調度，進程調度，磁盤調度），代表系統：QLinux、Linux-SRT； 引入新穎的調度框架以及資源管理思想以更好地支持網絡系統中的QoS要求，比如SILK中的垂直結構的操作系統調度的思想，QLinux中的分級調度的思想，以及RED-Linux所提出來的一個通用的調度框架和Linux/RK中所使用的資源預留的思想； 方便的任務QoS管理接口函數和管理程序的實現，比如Linux/RK提出的操作系統中各種資源的資源預留的概念；Linux-SRT中為了用戶方便地使用新增加的實時調度支持而增加了API，以及提出的reserve的概念等； 在實際的系統中，具體使用那種實時Linux技術，需要根據具體的系統需求而定。如果目標系統是像機床控制或者導彈飛行姿態控制這樣的硬實時系統，那基於RT-Linux是一個不錯的方案；如果一個系統對於實時性的要求不是那麼嚴格，但又不是軟實時系統，那麼可以借鑒Kurt-Linux的想想以及一些為了提高Linux響應速度而提出的可搶占內核的想法；如果目標系統是一個像實時多媒體系統這樣的軟實時應用，或者一個希望能夠在高負載狀態下提供更好的吞吐率的服務器系統，那麼QLinux和RED-Linux的思想提供了很好的參考；如果是將Linux應用於像路由器這樣的網絡結點中，可以借鑒SILK的實現思想。
