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

CBS算法的RTAI內(nèi)核調(diào)度器設(shè)計CBS算法的RTAI內(nèi)核調(diào)度器設(shè)計近年來基于雙內(nèi)核架構(gòu)增強Linux操作系統(tǒng)實時性的RTAI[1]（RealTimeApplicationInterface）在工業(yè)控制等硬實時領(lǐng)域已經(jīng)得到了越來越多的應(yīng)用。本文提出的調(diào)度器通過采用基于服務(wù)策略的CBS算法對RATI內(nèi)核下的EDF調(diào)度器進行擴展，可以保證分配一定的CPU資源供Linux上的軟實時應(yīng)用，即使在有硬實時任務(wù)并發(fā)時也能得到處理器資源。實驗結(jié)果證明了基于CBS算法擴展RTAI內(nèi)核調(diào)度器的正確性。關(guān)鍵詞RTAILinuxCBS算法內(nèi)核調(diào)度器引言嵌入式系統(tǒng)大多工作在有實時性要求的環(huán)境中，有些嵌入式設(shè)備可能需要軟件在ms級時間單位內(nèi)做出響應(yīng)，而有些實時任務(wù)則要無任何延時地以幾ms的周期執(zhí)行，這就迫切需要一個功能強大、配置方便的實時操作系統(tǒng)來支持。一些商業(yè)的嵌入式實時操作系統(tǒng)（如WindowsCE、VxWorks等）價格都比較昂貴，這就促使人們轉(zhuǎn)向了改造通用嵌入式操作系統(tǒng)，使其滿足實時性。這種改造要求源代碼必須開放，而Linux是嵌入式應(yīng)用中的通用嵌入式操作系統(tǒng)，源代碼開放，滿足改造研究上的需求。對Linux實時化改造的方案很多，主要有兩種：一種直接修改內(nèi)核，另一種是采用雙內(nèi)核機制。第一種方法只能用于軟實時應(yīng)用，只有雙內(nèi)核架構(gòu)的方案可以保障硬實時應(yīng)用的截止期不被錯過。但是，雙內(nèi)核架構(gòu)在軟、硬實時任務(wù)混合的應(yīng)用環(huán)境中還存在一些問題。由于硬實時任務(wù)工作在RTAI實時內(nèi)核空間中，而軟實時任務(wù)工作在Linux內(nèi)核空間中，Linux作為優(yōu)先級最低的任務(wù)被頂層實時內(nèi)核調(diào)度執(zhí)行，在一段時間內(nèi)可以分配給軟實時任務(wù)的處理器時間依賴于RTAI硬實時應(yīng)用對處理器帶寬的要求，而且在不同的時間段內(nèi)可用的處理器時間一般會有很大的不同。這就難以保障運行在Linux中的軟時應(yīng)用達到預(yù)先設(shè)定的服務(wù)質(zhì)量水平。1

基于服務(wù)策略算法的實時調(diào)度器針對雙內(nèi)核架構(gòu)下增強Linux實時性時存在的問題，本文提出一種實時調(diào)度器，采用基于服務(wù)策略的CBS算法對RTAI內(nèi)核下的EDF調(diào)度器進行擴展，保證在有硬實時任務(wù)的同時滿足Linux內(nèi)核空間下軟實時任務(wù)的周轉(zhuǎn)時間。1.1

實時調(diào)度器基于的CBS算法定義為了縮短混合實時任務(wù)調(diào)度中軟實時任務(wù)的響應(yīng)時間，以及減少軟實時任務(wù)錯失截止期，人們提出了多種軟實時任務(wù)的調(diào)度算法。典型的有基于服務(wù)策略的算法，又稱“帶寬預(yù)留算法”。該算法在保證硬實時周期任務(wù)滿足截止期的前提下，預(yù)留出適當?shù)奶幚砥鲙捵鳛榉?wù)器來處理軟實時任務(wù)，常用的算法有CBS、TBS算法等。服務(wù)策略的含義是：服務(wù)器把到達的任務(wù)放入一個非優(yōu)先規(guī)則的隊列中，該隊列的第一個任務(wù)根據(jù)分配的截止期插入EDF調(diào)度隊列中，如果隊列的第一個任務(wù)被插入到調(diào)度隊列等待調(diào)度，則稱“服務(wù)器是合格的”，否則稱“服務(wù)器是不合格的”；如果隊列的第一個任務(wù)正在執(zhí)行，則稱“服務(wù)器為活動的”。下面給出了采用CBS算法時軟實時任務(wù)在不影響硬實時任務(wù)截止期的情況下是否可以調(diào)度的判別準則。假定某一實時任務(wù)Ti的處理器帶寬記為（Ci,Pi），表示任務(wù)Ti在周期Pi內(nèi)最多占用Ci的處理器時間。定義實時任務(wù)Ti的處理器利用率為：現(xiàn)假定系統(tǒng)中n個實時任務(wù)，記為{T1,T2,…,Tn}，對應(yīng)著n個處理器帶寬參數(shù)，記為（Ci,Pi），其中i=1,2,…,n。則此任務(wù)集可調(diào)度的條件為：滿足上式時任務(wù)集是可調(diào)度的。其中Umax是EDF算法調(diào)度時CPU處理器利用率的最大值。CBS算法步驟詳細定義如下：①

一個CBS服務(wù)器用預(yù)留執(zhí)行能力cs和有序?qū)Γ≦s，Ts）來表示。其中，Qs表示服務(wù)器的最大執(zhí)行能力補充值，Ts表示服務(wù)器周期。服務(wù)器帶寬Us=Qs/Ts。服務(wù)器截止期的初始值ds,0=0，而任意時刻，服務(wù)器的修正截止期ds,k和服務(wù)器相關(guān)聯(lián)。

②

被服務(wù)器服務(wù)的任務(wù)（隊列的第一個任務(wù)）被分配一個動態(tài)截止期di,j，該截止期等于當前服務(wù)器截止期ds,k。

③

不管一個任務(wù)什么時候執(zhí)行，服務(wù)器的預(yù)留執(zhí)行能力cs都以相同的數(shù)量遞減。

④

當預(yù)留執(zhí)行能力cs遞減到零時，馬上被重置為最大執(zhí)行能力補充值Qs，同時產(chǎn)生新的服務(wù)器截止期ds,k+1=ds,k+Ts。

⑤

在時刻t，如果存在一個服務(wù)的任務(wù)Ji,j(ri,j≤t≤fi,j)，那么稱“CBS處于活動狀態(tài)”，否則稱為“空閑狀態(tài)”。

⑥

當一個作業(yè)Ji,j到達時，如果此時服務(wù)器處于活動狀態(tài)，那么任務(wù)的服務(wù)請求進入掛起任務(wù)隊列，此隊列需是非搶先原則的隊列（如先進先出隊列）。

⑦

當一個任務(wù)Ji,j到達，且服務(wù)器處于空閑狀態(tài)時，如果cs≥（ds,k-ri,j）Us，那么服務(wù)器產(chǎn)生一個新的服務(wù)器截止期ds,k+1=ri,j+Ts，并且把預(yù)留執(zhí)行能力cs重置為最大執(zhí)行能力補充值Qs，否則服務(wù)器使用當前的服務(wù)器截止期ds,k和當前的預(yù)留執(zhí)行能力cs來對任務(wù)進行服務(wù)。

⑧

當一個任務(wù)完成時，服務(wù)器利用當前的預(yù)留執(zhí)行能力和截止期繼續(xù)為掛起任務(wù)隊列中的任務(wù)服務(wù)。如果掛起任務(wù)隊列中沒有任務(wù)，那么服務(wù)器變成空閑狀態(tài)。

⑨

在任何時刻，服務(wù)器分配給任務(wù)的截止期為最后生成的服務(wù)器截止期。1.2

EDF調(diào)度器的CBS算法擴展設(shè)計1.2.1

EDF調(diào)度器的總體結(jié)構(gòu)設(shè)計先引入一種“虛擬任務(wù)”的概念。所謂“虛擬任務(wù)”，就是指由RTAI底層實時小內(nèi)核按EDF算法直接調(diào)度執(zhí)行的一種特殊的硬實時任務(wù)，對應(yīng)于Linux用戶空間的某一軟實時應(yīng)用。其任務(wù)截止期由RTAI內(nèi)核下的CBS服務(wù)器計算得出。本文將RATI內(nèi)核下的EDF調(diào)度器進行了以下擴展：①

在EDF調(diào)度層，仍然采用原RTAI內(nèi)核下調(diào)度器采用的EDF調(diào)度算法，對硬實時周期任務(wù)和虛擬任務(wù)集合進行調(diào)度；而CBS服務(wù)器則按一定的比例占用處理機時間，同時通過服務(wù)器接口與一個實時應(yīng)用相對應(yīng)，為其提供資源服務(wù)。

②

在服務(wù)器層有CBS服務(wù)器核和CBS服務(wù)器接口。CBS服務(wù)器核的主要功能是根據(jù)傳入的相關(guān)調(diào)度信息維護底層實時小內(nèi)核中的可用CBS服務(wù)器隊列，在任務(wù)開始、掛起、終止等調(diào)度時執(zhí)行相應(yīng)的事件處理函數(shù)來調(diào)整CBS服務(wù)器的屬性參數(shù)，實現(xiàn)CBS算法。EDF調(diào)度器擴展如圖1所示。

圖1

EDF調(diào)度器擴展在服務(wù)器接口中，由于硬實時任務(wù)工作在RTAI實時內(nèi)核下，而軟實時任務(wù)一般工作在Linux內(nèi)核下，因此服務(wù)器維護的虛擬任務(wù)為了與實際的實時任務(wù)建立對應(yīng)，就需要一個接口來實現(xiàn)它們的映射關(guān)系。本文通過這個接口層來為Linux內(nèi)核中的實時任務(wù)和RTAI內(nèi)核下的虛擬任務(wù)提供映射實現(xiàn)。1.2.2

EDF調(diào)度器擴展后調(diào)度主要算法步驟①

不同類型的新應(yīng)用程序到達時，通過服務(wù)器接口層中的系統(tǒng)調(diào)用對其進行判別控制檢查，主要通過式（2）來進行。如果通過檢查，則說明調(diào)度新到達的應(yīng)用程序不會影響硬實時任務(wù)的截止期。

②

通過判別檢查之后，CBS服務(wù)器為其創(chuàng)建一個與新應(yīng)用程序?qū)?yīng)的虛擬任務(wù)，并根據(jù)新應(yīng)用程序傳入的調(diào)度參數(shù)和自己的調(diào)度策略，計算得到虛擬任務(wù)的任務(wù)截止期。如果此時服務(wù)器是活動的，將此新虛擬任務(wù)掛入服務(wù)器維護的先進先出隊列。取出服務(wù)器的先進先出隊列隊首虛擬任務(wù)，并根據(jù)任務(wù)截止期大小進入RTAI實時內(nèi)核的EDF就緒隊列；同時，新應(yīng)用程序也加入到Linux內(nèi)核下相應(yīng)的調(diào)度對象集合中，調(diào)度對象集合是一個由與新任務(wù)相匹配的具體調(diào)度器調(diào)度的集合，這個調(diào)度器基于某種調(diào)度算法，不是本文的討論重點，但是如果從整個系統(tǒng)的實現(xiàn)來說，這些都是必不可少的部分。本文重點實現(xiàn)的是RTAI內(nèi)核下對軟硬實時混合調(diào)度的支持。

③

虛擬任務(wù)與RATI下的硬實時周期任務(wù)一起由EDF調(diào)度器統(tǒng)一調(diào)度分配。1.3

EDF調(diào)度器的擴展實現(xiàn)根據(jù)擴展設(shè)計方案，下面討論在對EDF調(diào)度器進行擴展時所涉及的關(guān)鍵問題及解決途徑。1.3.1

EDF調(diào)度層擴展的關(guān)鍵問題首先是實時內(nèi)核的虛擬任務(wù)和Linux用戶空間中的軟實時任務(wù)的映射問題。軟實時任務(wù)是運行在用戶空間的Linux進程中。它通過CBS服務(wù)器接口層中的新增系統(tǒng)調(diào)用rt_schedule_test()進入準入測試后，調(diào)用CBS服務(wù)器接口層的新增系統(tǒng)調(diào)用rt_create_virtual_task()創(chuàng)建虛擬任務(wù)，并且傳入軟實時應(yīng)用的進程ID，應(yīng)用調(diào)度器ID在虛擬任務(wù)結(jié)構(gòu)體中保存下來。當虛擬任務(wù)被EDF算法調(diào)度執(zhí)行時，它通過實時內(nèi)核中的軟中斷模擬機制保存對應(yīng)的進程ID，應(yīng)用調(diào)度器ID到中斷暫存表，然后調(diào)用rt_switch_to_linux切換到Linux內(nèi)核。Linux內(nèi)核通過應(yīng)用調(diào)度器ID找到調(diào)度器，將要調(diào)度執(zhí)行的進程ID傳給此調(diào)度器，由調(diào)度器調(diào)度此進程執(zhí)行，這就實現(xiàn)了虛擬任務(wù)與軟實時應(yīng)用的對應(yīng)。1.3.2

服務(wù)器核實現(xiàn)的關(guān)鍵問題①

為減少系統(tǒng)中的全局數(shù)據(jù)結(jié)構(gòu)種類，虛擬任務(wù)與實時任務(wù)使用同樣的數(shù)據(jù)結(jié)構(gòu)定義。為此，修改了RTAI的實時任務(wù)的rt_task_struct結(jié)構(gòu)定義：添加了與虛擬任務(wù)相關(guān)的屬性，如對應(yīng)的具體軟實時任務(wù)的ID、軟實時任務(wù)調(diào)度器ID、任務(wù)截止期和指向CBS服務(wù)器的指針；定義了服務(wù)器數(shù)據(jù)結(jié)構(gòu)體rt_CBSServer，屬性參數(shù)有服務(wù)器的預(yù)留執(zhí)行能力計算值、已使用的服務(wù)器預(yù)留的計算值、周期、開始時間、截止時間以及服務(wù)器先進先出隊列VTQueue。

②

CBS服務(wù)器算法的實現(xiàn)。CBS服務(wù)器算法需要在虛擬任務(wù)到達事件、虛擬任務(wù)完成事件以及服務(wù)器預(yù)留執(zhí)行能力耗盡事件發(fā)生時刻，及時對服務(wù)器的相關(guān)屬性和虛擬任務(wù)屬性進行調(diào)整，特別是虛擬任務(wù)的截止期和服務(wù)器的截止期。下面介紹基于服務(wù)策略的CBS算法的偽代碼實現(xiàn)。虛擬任務(wù)到達事件發(fā)生時的處理：if（虛擬任務(wù)到達事件發(fā)生）{

把該虛擬任務(wù)加入到服務(wù)器的先進先出隊列；

N=N+1；//服務(wù)器的先進先出隊列任務(wù)數(shù)加1

if（此時服務(wù)器空閑&&N==1）{

if(c>=(dk-rj)Us){

ak=rj;

dk=ak+Ts;

c=Qs;//計算服務(wù)器預(yù)留執(zhí)行能力和截止期

}

else{

ak=rj;

dk=dk-1;//設(shè)置截止期

}

}

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

從EDF調(diào)度器就緒任務(wù)隊列和服務(wù)器先進先出隊列中刪除該虛擬任務(wù)；

N=N-1;

if（N!=0）{

利用當前的服務(wù)器截止期dk調(diào)度服務(wù)器先進先出任務(wù)隊列中的下一個任務(wù)到EDF調(diào)度器就緒隊列中；

}

if（任務(wù)執(zhí)行了一個時間片）{

c=c-1;//服務(wù)器預(yù)留執(zhí)行能力減1

}

}服務(wù)器預(yù)留執(zhí)行能力耗盡事件發(fā)生時的處理：if（服務(wù)器執(zhí)行能力==0）{

dk=dk-1+Ts;

c=Qs;//計算截止期,并補充預(yù)留執(zhí)行能力

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

服務(wù)器接口實現(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ù)隊列中。rt_schedule_test()：對新到來的應(yīng)用進行準入測試。主要是通過CBS算法進行測試，如果不能通過準入測試，則失敗退出；否則調(diào)度rt_create_virtual_task()創(chuàng)建虛擬任務(wù)，將任務(wù)掛入相應(yīng)的服務(wù)器隊列中，等待調(diào)度。rt_delete_VTtask()：在Linux內(nèi)核下可調(diào)度這個函數(shù)來實現(xiàn)對RTAI內(nèi)核下的虛擬任務(wù)的刪除。2

驗證本文通過在硬件配置為CPUAMDDuron1.10G、256Mb內(nèi)存，操作系統(tǒng)為Fedoracore5、編譯器為gcc的環(huán)境下分兩次安裝RTAI內(nèi)核包（分別為EDF調(diào)度器擴展前和擴展后），對軟硬實時任務(wù)并發(fā)時軟實時任務(wù)的周轉(zhuǎn)情況進行記錄并進行分析。軟實時任務(wù)采用Linux操作系統(tǒng)下的多媒體播放器，硬實時任務(wù)采用通過編程實現(xiàn)的周期性實時計算任務(wù)，運行周期為10ms。硬實時負載由編程實現(xiàn)的硬實時負載程序精確得到，本實驗中進行了3種負載的測試，分別為輕負載、中度負載和重負載。多媒體播放器是否正常播放可用下式衡量：式中：ei為第i幀圖像數(shù)據(jù)解碼時產(chǎn)生的時間偏差，ti為第i幀圖像解碼完成時刻，ti-1為第i-1幀圖像解碼完成時刻，40ms是正常情況下MPEG4相鄰幀圖像的標準解碼時間間隔。若時間偏差小于或等于0，則mplayer可正常播放；否則，將出現(xiàn)圖像抖動和斷續(xù)現(xiàn)象，偏差越大，異常越明顯。本實驗主要分析了時間偏差大于0時的情況。使多媒體播放器運行大于30s的時間，獲取750幀的數(shù)據(jù)。分別得到的EDF調(diào)度器擴展前和擴展后的實驗數(shù)據(jù)，如表1和表2所列。表1

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

表2

EDF調(diào)度器擴