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

　　虛擬任務(wù)到達(dá)事件發(fā)生時(shí)的處理：

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

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

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

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

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

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

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

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

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

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

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

2 驗(yàn)證

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

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

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

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

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

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

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

3 結(jié)論

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