CBS算法的RTAI內核調度器設計

近年來基于雙內核架構增強Linux操作系統實時性的RTAI[1]（RealTime Application Interface）在工業控制等硬實時領域已經得到了越來越多的應用。本文提出的調度器通過采用基于服務策略的CBS算法對RATI內核下的EDF調度器進行擴展，可以保證分配一定的CPU資源供Linux上的軟實時應用，即使在有硬實時任務并發時也能得到處理器資源。實驗結果證明了基于CBS算法擴展RTAI內核調度器的正確性。

關鍵詞 RTAI Linux CBS算法 內核調度器

引言

　　嵌入式系統大多工作在有實時性要求的環境中，有些嵌入式設備可能需要軟件在ms級時間單位內做出響應，而有些實時任務則要無任何延時地以幾ms的周期執行，這就迫切需要一個功能強大、配置方便的實時操作系統來支持。一些商業的嵌入式實時操作系統（如Windows CE、VxWorks等）價格都比較昂貴，這就促使人們轉向了改造通用嵌入式操作系統，使其滿足實時性。這種改造要求源代碼必須開放，而Linux是嵌入式應用中的通用嵌入式操作系統，源代碼開放，滿足改造研究上的需求。

　　對Linux實時化改造的方案很多，主要有兩種：一種直接修改內核，另一種是采用雙內核機制。第一種方法只能用于軟實時應用，只有雙內核架構的方案可以保障硬實時應用的截止期不被錯過。但是，雙內核架構在軟、硬實時任務混合的應用環境中還存在一些問題。由于硬實時任務工作在RTAI實時內核空間中，而軟實時任務工作在Linux內核空間中，Linux作為優先級最低的任務被頂層實時內核調度執行，在一段時間內可以分配給軟實時任務的處理器時間依賴于RTAI硬實時應用對處理器帶寬的要求，而且在不同的時間段內可用的處理器時間一般會有很大的不同。這就難以保障運行在Linux中的軟時應用達到預先設定的服務質量水平。

1? 基于服務策略算法的實時調度器

　　針對雙內核架構下增強Linux實時性時存在的問題，本文提出一種實時調度器，采用基于服務策略的CBS算法對RTAI內核下的EDF調度器進行擴展，保證在有硬實時任務的同時滿足Linux內核空間下軟實時任務的周轉時間。

1.1? 實時調度器基于的CBS算法定義

　　為了縮短混合實時任務調度中軟實時任務的響應時間，以及減少軟實時任務錯失截止期，人們提出了多種軟實時任務的調度算法。典型的有基于服務策略的算法，又稱“帶寬預留算法”。該算法在保證硬實時周期任務滿足截止期的前提下，預留出適當的處理器帶寬作為服務器來處理軟實時任務，常用的算法有CBS、TBS算法等。服務策略的含義是： 服務器把到達的任務放入一個非優先規則的隊列中，該隊列的第一個任務根據分配的截止期插入EDF調度隊列中，如果隊列的第一個任務被插入到調度隊列等待調度，則稱“服務器是合格的”，否則稱“服務器是不合格的”；如果隊列的第一個任務正在執行，則稱“服務器為活動的”。下面給出了采用CBS算法時軟實時任務在不影響硬實時任務截止期的情況下是否可以調度的判別準則。

　　假定某一實時任務Ti的處理器帶寬記為（Ci,Pi），表示任務Ti在周期Pi內最多占用Ci的處理器時間。定義實時任務Ti的處理器利用率為：

　　現假定系統中n個實時任務，記為{T1,T2,…,Tn}，對應著n個處理器帶寬參數，記為（Ci,Pi），其中i=1, 2,…,n。則此任務集可調度的條件為：

滿足上式時任務集是可調度的。其中Umax是EDF算法調度時CPU處理器利用率的最大值。

　　CBS算法步驟詳細定義如下：

　　①? 一個CBS服務器用預留執行能力cs和有序對（Qs，Ts）來表示。其中，Qs表示服務器的最大執行能力補充值，Ts表示服務器周期。服務器帶寬Us=Qs/Ts。服務器截止期的初始值ds,0=0，而任意時刻，服務器的修正截止期ds,k和服務器相關聯。
　　②? 被服務器服務的任務（隊列的第一個任務）被分配一個動態截止期di,j，該截止期等于當前服務器截止期ds,k。
　　③ ?不管一個任務什么時候執行，服務器的預留執行能力cs都以相同的數量遞減。
　　④ ?當預留執行能力cs遞減到零時，馬上被重置為最大執行能力補充值Qs，同時產生新的服務器截止期ds,k+1=ds,k+Ts。
　　⑤? 在時刻t，如果存在一個服務的任務Ji,j(ri,j≤t≤fi,j)，那么稱“CBS處于活動狀態”，否則稱為“空閑狀態”。
　　⑥? 當一個作業Ji,j到達時，如果此時服務器處于活動狀態，那么任務的服務請求進入掛起任務隊列，此隊列需是非搶先原則的隊列（如先進先出隊列）。
　　⑦ ?當一個任務Ji,j到達，且服務器處于空閑狀態時，如果cs≥（ds,k-ri,j）Us，那么服務器產生一個新的服務器截止期ds,k+1=ri,j+Ts，并且把預留執行能力cs重置為最大執行能力補充值Qs，否則服務器使用當前的服務器截止期ds,k和當前的預留執行能力cs來對任務進行服務。
　　⑧ ?當一個任務完成時，服務器利用當前的預留執行能力和截止期繼續為掛起任務隊列中的任務服務。如果掛起任務隊列中沒有任務，那么服務器變成空閑狀態。
　　⑨ ?在任何時刻，服務器分配給任務的截止期為最后生成的服務器截止期。

1.2? EDF調度器的CBS算法擴展設計

1.2.1? EDF調度器的總體結構設計

　　先引入一種“虛擬任務”的概念。所謂“虛擬任務”，就是指由RTAI底層實時小內核按EDF算法直接調度執行的一種特殊的硬實時任務，對應于Linux用戶空間的某一軟實時應用。其任務截止期由RTAI內核下的CBS服務器計算得出。

　　本文將RATI內核下的EDF調度器進行了以下擴展：

　　①? 在EDF調度層，仍然采用原RTAI內核下調度器采用的EDF調度算法，對硬實時周期任務和虛擬任務集合進行調度；而CBS服務器則按一定的比例占用處理機時間，同時通過服務器接口與一個實時應用相對應，為其提供資源服務。
　　② ?在服務器層有CBS服務器核和CBS服務器接口。

　　CBS服務器核的主要功能是根據傳入的相關調度信息維護底層實時小內核中的可用CBS服務器隊列，在任務開始、掛起、終止等調度時執行相應的事件處理函數來調整CBS服務器的屬性參數，實現CBS算法。

　　EDF調度器擴展如圖1所示。

圖1? EDF調度器擴展

　　在服務器接口中，由于硬實時任務工作在RTAI實時內核下，而軟實時任務一般工作在Linux內核下，因此服務器維護的虛擬任務為了與實際的實時任務建立對應，就需要一個接口來實現它們的映射關系。本文通過這個接口層來為Linux內核中的實時任務和RTAI內核下的虛擬任務提供映射實現。

1.2.2? EDF調度器擴展后調度主要算法步驟

　　①? 不同類型的新應用程序到達時，通過服務器接口層中的系統調用對其進行判別控制檢查，主要通過式（2）來進行。如果通過檢查，則說明調度新到達的應用程序不會影響硬實時任務的截止期。
　　②??通過判別檢查之后，CBS服務器為其創建一個與新應用程序對應的虛擬任務，并根據新應用程序傳入的調度參數和自己的調度策略，計算得到虛擬任務的任務截止期。如果此時服務器是活動的，將此新虛擬任務掛入服務器維護的先進先出隊列。取出服務器的先進先出隊列隊首虛擬任務，并根據任務截止期大小進入RTAI實時內核的EDF就緒隊列；同時，新應用程序也加入到Linux內核下相應的調度對象集合中，調度對象集合是一個由與新任務相匹配的具體調度器調度的集合，這個調度器基于某種調度算法，不是本文的討論重點，但是如果從整個系統的實現來說，這些都是必不可少的部分。本文重點實現的是RTAI內核下對軟硬實時混合調度的支持。
　　③? 虛擬任務與RATI下的硬實時周期任務一起由EDF調度器統一調度分配。

1.3? EDF調度器的擴展實現

　　根據擴展設計方案，下面討論在對EDF調度器進行擴展時所涉及的關鍵問題及解決途徑。

1.3.1? EDF調度層擴展的關鍵問題

　　首先是實時內核的虛擬任務和Linux用戶空間中的軟實時任務的映射問題。軟實時任務是運行在用戶空間的Linux進程中。它通過CBS服務器接口層中的新增系統調用rt_schedule_test()進入準入測試后，調用CBS服務器接口層的新增系統調用rt_create_virtual_task()創建虛擬任務，并且傳入軟實時應用的進程ID，應用調度器ID在虛擬任務結構體中保存下來。當虛擬任務被EDF算法調度執行時，它通過實時內核中的軟中斷模擬機制保存對應的進程ID，應用調度器ID到中斷暫存表，然后調用rt_switch_to_linux切換到Linux內核。Linux內核通過應用調度器ID找到調度器，將要調度執行的進程ID傳給此調度器，由調度器調度此進程執行，這就實現了虛擬任務與軟實時應用的對應。

1.3.2? 服務器核實現的關鍵問題

　　①? 為減少系統中的全局數據結構種類，虛擬任務與實時任務使用同樣的數據結構定義。為此，修改了RTAI的實時任務的rt_task_struct結構定義：添加了與虛擬任務相關的屬性，如對應的具體軟實時任務的ID、軟實時任務調度器ID、任務截止期和指向CBS服務器的指針；定義了服務器數據結構體rt_CBSServer，屬性參數有服務器的預留執行能力計算值、已使用的服務器預留的計算值、周期、開始時間、截止時間以及服務器先進先出隊列VTQueue。
　　② ?CBS服務器算法的實現。CBS服務器算法需要在虛擬任務到達事件、虛擬任務完成事件以及服務器預留執行能力耗盡事件發生時刻，及時對服務器的相關屬性和虛擬任務屬性進行調整，特別是虛擬任務的截止期和服務器的截止期。

　　下面介紹基于服務策略的CBS算法的偽代碼實現。

　　虛擬任務到達事件發生時的處理：

if（虛擬任務到達事件發生） {
　　把該虛擬任務加入到服務器的先進先出隊列；
　　N=N+1；//服務器的先進先出隊列任務數加1
　　if（此時服務器空閑&&N==1） {
　　　　if(c>=(dk-rj)Us) {
　　　　　　ak=rj;
　　　　　　dk=ak+Ts;
　　　　　　c=Qs;//計算服務器預留執行能力和截止期
　　　　}
　　　　else{
　　　　　　ak=rj;
　　　　　　dk=dk-1;//設置截止期
　　　　}
　　}
}

　　虛擬任務完成事件發生時的處理：

if(任務完成事件發生) {
　　從EDF調度器就緒任務隊列和服務器先進先出隊列中刪除該虛擬任務；
　　N=N-1;
　　if（N!=0）{
　　　　利用當前的服務器截止期dk調度服務器先進先出任務隊列中的下一個任務到EDF調度器就緒隊列中；
　　}
　　if（任務執行了一個時間片） {
　　　　c=c-1;//服務器預留執行能力減1
　　}
}

　　服務器預留執行能力耗盡事件發生時的處理：

if（服務器執行能力==0） {
　　dk=dk-1+Ts;
　　c=Qs;//計算截止期,并補充預留執行能力
}

其中，dk為服務器的截止期；ak表示服務器下次執行的起始時刻；rj表示任務到達時刻；c表示服務器剩余執行能力。Qs和Ts分別為CBS的最大容量預算補充值和周期；Us是這個服務器的利用率。

1.3.3? 服務器接口實現的關鍵技術

　　該層主要在RTAI內核下增加一些新的系統調用供Linux內核使用。

　　rt_create_virtual_task()： 創建虛擬任務。首先在系統內存中為服務器分配所需的內存空間；然后根據傳入參數填寫rt_task_struct{}結構,特別是與服務器相關的幾種變量值；最后將其放入系統任務隊列中。

　　rt_schedule_test()： 對新到來的應用進行準入測試。主要是通過CBS算法進行測試，如果不能通過準入測試，則失敗退出；否則調度rt_create_virtual_task()創建虛擬任務，將任務掛入相應的服務器隊列中，等待調度。

　　rt_delete_VTtask()： 在Linux內核下可調度這個函數來實現對RTAI內核下的虛擬任務的刪除。

2? 驗證

　　本文通過在硬件配置為CPU AMD Duron 1.10G、256 Mb內存，操作系統為Fedora core5、編譯器為gcc的環境下分兩次安裝RTAI內核包（分別為EDF調度器擴展前和擴展后），對軟硬實時任務并發時軟實時任務的周轉情況進行記錄并進行分析。軟實時任務采用Linux操作系統下的多媒體播放器，硬實時任務采用通過編程實現的周期性實時計算任務，運行周期為10 ms。硬實時負載由編程實現的硬實時負載程序精確得到，本實驗中進行了3種負載的測試，分別為輕負載、中度負載和重負載。

　　多媒體播放器是否正常播放可用下式衡量：

式中： ei為第i幀圖像數據解碼時產生的時間偏差，ti為第i幀圖像解碼完成時刻，ti-1為第i-1幀圖像解碼完成時刻，40 ms是正常情況下MPEG4相鄰幀圖像的標準解碼時間間隔。若時間偏差小于或等于0，則mplayer可正常播放；否則，將出現圖像抖動和斷續現象，偏差越大，異常越明顯。本實驗主要分析了時間偏差大于0時的情況。

　　使多媒體播放器運行大于30 s的時間，獲取750幀的數據。分別得到的EDF調度器擴展前和擴展后的實驗數據，如表1和表2所列。

表1? EDF調度器擴展前Linux調度下的多媒體播放器播放情況

表2? EDF調度器擴展后Linux調度下的多媒體播放器播放情況

　　對表1和表2中的數據進行分析。在輕度負載0.3時，時間偏差10 ms以下的幀數占總幀數的累計百分比基本相同，分別為99.6%和99.7%；說明對EDF調度器進行擴展前后，對多媒體播放器播放效果基本沒有差別。在中等負載0.53時，擴展前播放器解碼時間偏差在20 ms以下的幀數占總幀數的44.65%，播放效果出現異常，人眼能感覺到；擴展后，偏差在20 ms以下的幀數占總幀數的99.82%，人眼不容易覺察播放的異常。在重負載0.81下，擴展前時間偏差在20 ms以下的幀數占總幀數的0%，也就是說時間偏差都會大于20 ms，這樣每一幀圖像數據很大程度上將被延遲播放；擴展后時間偏差在20 ms以下的幀數占總幀數的99.57%，仍然可以滿足播放器的播放效果。

3? 結論

　　本文提出的基于CBS算法的EDF調度器，實現了RTAI實時內核的資源預留，可為Linux內核空間下的軟實時應用保留一定的處理器帶寬，較好地解決了雙內核架構下軟實時和硬實時混合的應用環境中軟實時應用因錯過截止期得不到響應的問題。本文重點討論了對RTAI下的EDF調度器在CBS算法上的擴展實現，而Linux內核空間下的應用調度器針對不同的軟實時應用算法也很多，且軟實時任務之間的相互依賴關系本文也沒有考慮。這些是今后工作中著重研究并加以解決的問題。李蘭英(副教授)，主要研究方向為工業企業自動化、計算機控制和嵌入式系統。