CBS算法的RTAI內(nèi)核調(diào)度器設計

　　虛擬任務到達事件發(fā)生時的處理：

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

　　虛擬任務完成事件發(fā)生時的處理：

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

　　服務器預留執(zhí)行能力耗盡事件發(fā)生時的處理：

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

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

1.3.3 服務器接口實現(xiàn)的關鍵技術(shù)

　　該層主要在RTAI內(nèi)核下增加一些新的系統(tǒng)調(diào)用供Linux內(nèi)核使用。

　　rt_create_virtual_task()： 創(chuàng)建虛擬任務。首先在系統(tǒng)內(nèi)存中為服務器分配所需的內(nèi)存空間；然后根據(jù)傳入?yún)?shù)填寫rt_task_struct{}結(jié)構(gòu),特別是與服務器相關的幾種變量值；最后將其放入系統(tǒng)任務隊列中。

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

　　rt_delete_VTtask()： 在Linux內(nèi)核下可調(diào)度這個函數(shù)來實現(xiàn)對RTAI內(nèi)核下的虛擬任務的刪除。

2 驗證

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

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

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

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

表1 EDF調(diào)度器擴展前Linux調(diào)度下的多媒體播放器播放情況

表2 EDF調(diào)度器擴展后Linux調(diào)度下的多媒體播放器播放情況

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

3 結(jié)論

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