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

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

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內核空間下的應用調度器針對不同的軟實時應用算法也很多，且軟實時任務之間的相互依賴關系本文也沒有考慮。這些是今后工作中著重研究并加以解決的問題。李蘭英(副教授)，主要研究方向為工業企業自動化、計算機控制和嵌入式系統。