基于ＲＴＡＩ的實時調度策略研究與改進

摘要:該文通過對RTAI 實時調度策略研究，針對單處理器下的實時調度算法進行了分析與比較，指出了在處理實時任務時RTAI所采取的調度策略存在的問題和不足，提出了用最小空閑時間調度算法MLLF (Modified Least Laxity First)引入到RTAI的調度調度策略中，以提高系統的實時性能。

關鍵詞:實時化技術;調度策略;調度算法;顛簸

中圖分類號: TP316.2 文獻標識碼: A 文章編號:1009-3044(2009)15-4049-03

Disquisition and Improvement on the RTAI Based Real-time Scheduling Policy

XU Feng-mei

(Wuhan Software Vocational College， Wuhan 430205，China)

Abstract: This thesis has performed a research on the RTAI Based Real-time Scheduling Policy， collated and analyzed the real-time scheduling algorithm in single processor environment. It has also stated briefly the disadvantage of the policy employed by RTAI when manipulating real time tasks， founded on which brought forward the introduction of MLLF (Modified Least Laxity First) into RTAI， which aimed on the promotion of the real-time performance of the system.

Key words: Real-timized; scheduling policy; scheduling algorithm; wobble

1 引言

Linux 操作系統的源代碼開放、內核模塊化設計及內核的高度可裁減性使其在嵌入式實時操作系統領域備受重視。但是，Linux面向通用多任務分時系統的設計思想限制了它在實時環境中的應用。因此，在具體的實際應用中，需對其進行有效的實時改進，以符合嵌入式系統對操作系統實時性能的要求。

對 Linux 進行實時化，目前主要有以下兩種技術方案:

1) 對標準 Linux 內核進行直接修改，優化 Linux 的實時性能;

2) 采用雙內核方案:增加一個實時內核，所有有實時要求的任務都在這個實時內核上運行，標準 Linux 內核作為這個實時內核優先級最低的一個進程。

致力于軟實時支持的方案，如RED-Linux、KURT、MV-Linux、Linux-SRT。這幾種方法的實現思路大不相同，但都是通過直接修改Linux內核源代碼，替換與時間或調度相關的代碼段。這樣的方式雖然也能夠實現一定程度的實時支持，但實現的實時性能有限，且不利于在其基礎上進一步改進。

致力于硬實時支持的方案，如RT-Linux和RTAI。它們在Linux內核之外單獨實現了一個精簡的實時內核，兩個內核同時存在，依靠優先級的不同完成不同的任務。這類方案的優點是結構層次清晰，對基本的實時性能支持明確，且可預測。另外在調度機制方面已經實現了基本的優先級調度。

2 RTAI 實時化技術

RTAI的基本思想是:為了在Linux系統中提供對于硬實時的支持，它實現了一個微內核的小的實時操作系統，而將普通Linux系統作為一個該操作系統中的一個低優先級的任務來運行。另外普通Linux系統中的任務可以通過FIFO和實時任務進行通信。

2.1 RTAI 系統結構與實現機制

RTAI是Real Time Application Interface的縮寫。顧名思義它為應用程序提供了一套實時的系統調用接口。嚴格來講，它還不是一個完整的操作系統，而只是一個具備了操作系統核心功能的一個實時的系統內核。RTAI是一個獨立的系統內核，并且接管了系統的所有硬件資源。RTAI的任務調度器把Linux操作系統內核作為一個空閑任務，即優先級最低的任務來運行。Linux當且僅當沒有實時任務運行時，才能運行。

RTAI系統結構如圖1 所示。

這樣，RTAI在運行實時任務的同時又可以利用Linux來運行非實時的任務。在Linux和RTAI組成的雙內核系統上實時任務由RTAI直接調度運行，非實時任務由Linux內核調度運行。因此RTAI和Linux的結合構成了一個可以充分發揮Linux諸多優點的完整的硬實時操作系統。

2.2 實時硬件抽象層RTHAL

RTAI 的關鍵技術是通過軟件來模擬硬件的中斷控制器。當 Linux 系統要封鎖CPU 的中斷時時，RTAI 中的實時子系統會截取到這個請求，把它記錄下來，而實際上并不真正封鎖硬件中斷，這樣就避免了由于封中斷所造成的系統在一段時間沒有響應的情況，從而提高了實時性。當有硬件中斷到來時，RTAI 截取該中斷，并判斷是否由實時子系統中的中斷例程來處理還是傳遞給普通的 Linux 內核進行處理。

RTAI通過創建一組實時硬件抽象層RTHAL (Real Time Hardware Abstraction Laye )來解決中斷捕獲的問題。硬件抽象層定義了本系統同硬件之間的抽象接口，主要用來截取硬件中斷，并且依據實時內核調度器的需求，重定向為基本內核任務或是實時任務。實時任務的中斷將直接發送給實時任務，如果不是實時任務的中斷將像往常一樣發送給Linux系統。通過這種方式，RTHAL為RTAI提供了一個能完全搶占Linux的框架。

3 基于RTAI的實時調度策略研究與改進

RTAI 實時調度是通過調度模塊schedulers()來對實時任務進行調度的。RTAI 包括三種不同的基于優先級的可搶占的調度算法:單處理器算法調度算法、多處理器調度算法以及SMP調度算法，其中每一種調度算法分別對應一種CPU 構架。每一種都結合了 RTAI 的調度服務:resume、yield、suspend、make_periodic、wait 等。

本文討論的是單處理器下的實時調度。

3.1 RTAI實時調度策略

RTAI的實時調度策略主要采用了基于優先級的RM(Rate-monotonic)調度算法和EDF(Earliest Deadline First)調度算法。

1) 單調速率算法RM:針對周期任務的優先級調度算法。任務的調度優先級由任務周期確定，周期越短的任務，優先級越高;周期越長的任務，優先級越低。這種定義優先級的方法容易理解，周期任務總應該在下一個周期到來之前完成當前這個周期，否則就會錯過時限，較短周期的任務應該盡量先調度先完成，以免錯過任務時限。

2) 最早時限優先調度算法EDF

EDF算法是一種基于動態優先級調度算法，它以最后期限(Deadline)的順序指定優先級。最后期限(Deadline) 時刻離當前時間最近的任務優先級最高，任務是可搶占的。在任務的執行期間可根據它的啟動時間改變優先級。優先級最高的任務是距離最后期限最近的任務，優先級最低的任務是距離最后期限最遠的任務。調度程序將每個新到達的任務加入等待任務隊列中，該隊列按照任務的截止期限排序，最近的時限在最前面(對周期性任務，其截止期限定為它下次發生的時間)。

3.2 RTAI的調度調度策略的不足與改進

3.2.1 RTAI調度策略的不足

RTAI采用的RM 算法和 EDF 算法是兩種經典的單處理器(CPU)調度算法。

RM算法適用于周期性，可搶占的任務。任務的最后期限(Deadline)為其周期，是一種靜態優先級算法。但RM 算法僅考慮了周期性任務，對于非周期性任務則將其看作周期性任務，其周期為任務最小的間隔時間[17]。另外的方法是把非周期性任務看作優先級最高的周期性任務，為其分配一個周期，僅在這個周期內才能執行非周期性任務。RM算法的CPU利用率比較低，對于非周期性任務其執行間隔不確定，很可能產生系統負載過大的情況。

EDF算法是一種動態調度算法，可以實現很高的CPU利用率，可以調度RM算法不能合理調度的任務集，可實現較復雜的調度，具有效率高、容易計算和推斷的優點。EDF算法的實現要比RM算法復雜得多，主要問題在于如何使任務按照到達最后期限的時間排序，因為任務到達期限的時間在執行期間是變化的，這樣任務就無法給以事先排序，每一個任務結束時，優先級都必須重新計算。操作系統在調度過程的最后一步選擇優先級最高的就緒進程執行。因此它的系統開銷比較大，很難診斷出即將過載的可能性，所以EDF比較適用于軟實時系統。由于其不能預先診斷出即將錯過截止期的任務，從而導致在系統負載較重或因為部分任務的錯過截止期而導致大量的任務錯過截止期，將引起系統性能急劇下降。

3.2.2 RTAI調度策略的改進

如今隨著嵌入式實時系統應用的不斷深入發展，多類型的軟實時任務、硬實時任務共存于同一系統中的應用越來越廣泛，實時系統所要處理的情況也越來越復雜，這就對實時操作系統的調度策略提出了更高的要求，處理好系統在重負載或超載時的調度也就顯得更加重要。

針對上述對RTAI調度策略中的不足，本文將把一種改進的最小空閑時間調度算法MLLF (Modified Least Laxity First)引入到RTAI的調度調度策略中，對其進行改進，以增強系統在重負載或超載時的調度性能。

1) 最小空閑時間優先調度算法LLF (Least Laxity First)

LLF調度算法按照任務的空閑時間的非降順序動態地分配優先級，空閑時間越短，任務的優先級就越高。空閑時間的意義在于測量任務需要被調度的緩急程度。假設一個特定的任務在變為活動任務時，處理器下被具有更高優先級的其他任務所占用，從而阻止了該任務接受調度處理。隨著時間的推移，這個等待任務的空閑時間穩定地減小直到小于正占用CPU的任務的空閑時間時，按照LLF調度算法，處理器必須切換到調度執行該等待任務;當該任務的空閑時間減小到0時，意味著該任務在其截止期前剛好能夠完成，此時，該任務需要立即搶占CPU資源以便在其截止期前完成。如果處理器在此關鍵時刻還不開始調度該任務，那么該任務的空閑時間將變為負值，當空閑時間為負時，意味著該任務不可能在其截止期前完成，此時，沒有必要讓空閑時間為負的任務占用CPU資源，以免造成CPU資源的浪費。

2) EDF算法和LLF算法的比較

LLF算法和EDF算法可看作是同類型的調度算法。EDF調度算法以最近時限的任務作為最先調度的任務，它保證的是截止期最早的任務優先執行:LLF算法是以空閑時間最少的任務作為最先調度的任務，它保證的是緊急任務的執行。

EDF算法相對于LLF算法具有實現相對容易的優點，缺點在于EDF算法不能解決過載的問題，當系統負載較重或發生過載時，EDF算法的性能退化得很快。EDF算法還有一個嚴重的缺陷，它可能會因為一個任務錯過截止期而導致其他很多任務錯過截止期。

LLF算法理論上分析，具有在系統重負載的情況下工作較好的優點，具有在調度時能判斷出任務是否能被調度的問題，并且具有夭折不能調度的實時任務，使過載問題得以解決的能力。但是，由于等待任務的空閑時間是嚴格遞減的，其等待執行的緩急程度也隨著時間越來越緊急，因此在系統執行的過程中，等待任務隨時可能會搶占當前執行的任務。LLF算法造成任務之間頻繁切換或稱為顛簸(thrashing) 現象較為嚴重。顛簸現象增大了系統的開銷，使得LLF的實用性大為降低，限制了LLF算法的應用。

3) LLF算法顛簸現象分析

由于等待任務的空閑時間是隨著時間嚴格遞減的，而當前執行任務(假設為Ti)的空閑時間保持不變，并假設不為0。隨著調度的執行，總會有某個等待任務(假設為巧)的空閑時間Sj穩定地下降到小于Si。此時，根據LLF調度算法，將發生一次任務切換，Tj將搶占Ti占用CPU資源。經此任務切換后，Tj成為當前執行任務，而Ti成為新的等待任務。在Tj執行期間，其空閑時間Sj保持不變，而Ti的空閑時間Si將隨著時間嚴格遞減，當Si減小到小于Sj時，Ti將搶占Tj重新占用CPU資源，從而又發生一次任務切換，這樣Ti與Tj相互搶占執行。當Ti與Tj相互搶占執行時，其他等待任務的空閑時間也一直保持嚴格遞減，這樣將會出現多個任務相互交叉搶占執行的現象，每次搶占都發生一次任務切換。如果它們之間沒有搶占執行，它們就將一個接一個地滿足其截止期。任務切換次數的增加意味著浪費計算資源，從而顯示出較差的調度性能，這使LLF算法的實用性幾乎為0。因此，許多文章對LLF算法提出了改進，以減小其任務的切換次數，去除顛簸現象以使其能實用化。下面就介紹一種改進型的最小空閑時間優先調度算法。

4) LLF算法的改進——改進型的最小空閑時間調度算法MLLF (Modified Least Laxity First)

為了減輕顛簸現象造成的資源浪費，需要對LLF算法進行改進，這種改進將確保任務在盡可能少相互搶占的情況下連續被執行。這種緩解顛簸現象不能通過簡單地臨時非搶占來實現，因為在任務的空閑時間降為0時，利用非搶占LLF算法可能會造成任務錯過截止期。

改進型的最小空閑時間調度算法MLLF的主要思想是:通過允許空閑時間反轉(即正在運行的任務如果大于就緒任務的空閑時間，也可以不立即被搶占)宋盡量延遲任務搶占，從而避免了頻繁的任務切換。該方法中的空閑時間反轉可以直到某一不能再延遲的時刻為止。這一最后的時刻就是滿足任務隊列中的就緒任務絕不能因而錯過截止期。

4 結束語

本文通過對RTAI所采用的RM(Rate-Monotonic)調度算法和EDF(Earliest Deadline First)調度算法的分析，指出了RM 算法對非周期性任務調度時，由于其執行間隔不確定，很可能產生系統負載過大的情況;而EDF算法由于不能預先診斷出即將錯過截止期的任務，從而導致在系統負載較重或因為部分任務錯過截止期而導致大量的任務錯過截止期，引起系統性能急劇下降。針對RTAI調度算法的缺陷，選擇最小空閑時間優先調度算法LLF(Least Laxity First)替換RTAI中原有的EDF調度算法，同時對LLF調度算法存在的顛簸現象進行了改進，將改進后的最小空閑時間調度算法MLLF(Modified Least Laxity First)引入到RTAI中，通過允許空閑時間反轉的策略來避免頻繁的任務切換引起的顛簸現象。

參考文獻:

[1] 徐曉磊， 董兆華， 吳建峰，等. Linux 可搶占內核的分析. 計算機工程， 2003， 29(15):14-18.

[2] 葉步財， 楊晨暉. 基于RTAI可擴展的實時調度模型的研究與實現. 廈門大學學報(自然科學版)， 2005， 4(1):289-293.

[3] 林滸， 蔡光起等. 實時化的Linux系統及其實時性能的研究. 小型微型計算機系統， 2004， 25(8):1454-1457.

[4] 王濟勇， 林濤等. EDF調度算法搶占行為的研究及其改進. 電子學報， 2004， 32(7): 64-68.

[5] 須文波， 張星燁， 歐愛輝. 基于 RTAI-Linux 的實時操作系統的分析與研究. 現代計算機， 2003，12(4):56-58.

[6] 楊承玉， 楊武. 一種嵌入式硬實時內核的實現. 微計算機信息， 2005， 22(6): 128-131.