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

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

關(guān)鍵詞 RTAI Linux CBS算法 內核調度器

引言

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

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

1 基于服務(wù)策略算法的實(shí)時(shí)調度器

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

1.1 實(shí)時(shí)調度器基于的CBS算法定義

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

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

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

滿(mǎn)足上式時(shí)任務(wù)集是可調度的。其中Umax是EDF算法調度時(shí)CPU處理器利用率的最大值。

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

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

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

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

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

　　本文將RATI內核下的EDF調度器進(jìn)行了以下擴展：

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

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

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

圖1 EDF調度器擴展

　　在服務(wù)器接口中，由于硬實(shí)時(shí)任務(wù)工作在RTAI實(shí)時(shí)內核下，而軟實(shí)時(shí)任務(wù)一般工作在Linux內核下，因此服務(wù)器維護的虛擬任務(wù)為了與實(shí)際的實(shí)時(shí)任務(wù)建立對應，就需要一個(gè)接口來(lái)實(shí)現它們的映射關(guān)系。本文通過(guò)這個(gè)接口層來(lái)為L(cháng)inux內核中的實(shí)時(shí)任務(wù)和RTAI內核下的虛擬任務(wù)提供映射實(shí)現。

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

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

1.3 EDF調度器的擴展實(shí)現

　　根據擴展設計方案，下面討論在對EDF調度器進(jìn)行擴展時(shí)所涉及的關(guān)鍵問(wèn)題及解決途徑。

1.3.1 EDF調度層擴展的關(guān)鍵問(wèn)題

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

1.3.2 服務(wù)器核實(shí)現的關(guān)鍵問(wèn)題

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

　　下面介紹基于服務(wù)策略的CBS算法的偽代碼實(shí)現。