摘要：本文分析了現(xiàn)有構(gòu)件化嵌入式操作系統(tǒng)所用調(diào)度算法存在的缺點，提出搶占閾值調(diào)度算法是更為合適的算法。通過仿真實驗比較搶占閾值調(diào)度算法、非搶占式調(diào)度算法和FIFO（First-In-First-Out）調(diào)度算法的性能，證明了上述結(jié)論。通過分析現(xiàn)有嵌入式系統(tǒng)構(gòu)件模型的特點，提出了一種構(gòu)件模型以及將構(gòu)件映射成任務的方式，還提出了一種設計方法。整個方案能提高構(gòu)件化嵌入式操作系統(tǒng)的性能。

關鍵詞：構(gòu)件化嵌入式操作系統(tǒng);搶占閾值調(diào)度;FIFO調(diào)度;構(gòu)件模型

1前言

　　如何將構(gòu)件技術(shù)成功地應用到嵌入式操作系統(tǒng)開發(fā)中得到越來越多的重視?，F(xiàn)有的工作大部分著重于從結(jié)構(gòu)的角度分解系統(tǒng)成若干構(gòu)件，并重用構(gòu)件。實際嵌入式實時系統(tǒng)的處理器資源和內(nèi)存資源是有限的，同時系統(tǒng)還有實時性需求。另外，當前成熟的實時調(diào)度算法都是基于任務模型分析系統(tǒng)的可調(diào)度性。所以，在嵌入式實時系統(tǒng)中應用構(gòu)件技術(shù)時，還需要研究如何從時間（運行）的角度將構(gòu)件映射成任務，以及為底層構(gòu)件化嵌入式實時操作系統(tǒng)選擇合適的調(diào)度算法。

　　本文首先分析了現(xiàn)有構(gòu)件化嵌入式操作系統(tǒng)的特點，著重分析了TinyOS[1]的調(diào)度內(nèi)核。通過仿真實驗比較了搶占閾值（簡稱PT）調(diào)度算法[2]、非搶占式（簡稱NP）調(diào)度算法和FIFO調(diào)度方式的性能，證明了當任務之間無共享資源時，搶占閾值調(diào)度算法適合作為構(gòu)件化嵌入式操作系統(tǒng)的實時調(diào)度算法。之后，本文論述了嵌入式實時系統(tǒng)對構(gòu)件模型的需求，提出了一種構(gòu)件模型。通過分析比較現(xiàn)有的映射方式，提出了一個將構(gòu)件映射成任務的方式和一種設計方法。

2適合構(gòu)件化嵌入式操作系統(tǒng)的調(diào)度算法

　　首先定義單處理器靜態(tài)優(yōu)先級實時系統(tǒng)的任務模型，定義G=｛t1,t2,…,tn｝為一個包含n個相互獨立的周期性或者偶發(fā)性（sporadic）任務的集合，集合中的任務用ti=（Ti,Ci,Di）（i=1,2,…n）表示，其中，Ti表示ti的周期（對于偶發(fā)性任務就是最小到達間隔），Ci表示ti的最壞情況執(zhí)行時間，Di表示ti的相對截止期。我們假定大的數(shù)值表示高的優(yōu)先級，對于集合G，最小的優(yōu)先級是1，最大的優(yōu)先級是n。周期任務的一次執(zhí)行，稱作任務的一個實例。任務實例從進入系統(tǒng)到結(jié)束執(zhí)行所用的時間稱作實例的響應時間（responsetime）。在一個系統(tǒng)的整個運行過程中，任務的最壞情況響應時間等于其所有實例中最大的響應時間。

　　2.1TinyOS存在的問題

　　當前的構(gòu)件化嵌入式操作系統(tǒng)主要有TinyOS和Echidna[5]兩種。TinyOS是為無線傳感器網(wǎng)絡（WirelessSensorNetwork，簡稱WSN）開發(fā)的構(gòu)件化嵌入式操作系統(tǒng)，適用于內(nèi)存資源和處理能力有限，電池供電的嵌入式系統(tǒng)。其內(nèi)核支持兩級調(diào)度，任務按照FIFO的方式執(zhí)行，目的是減少對內(nèi)存的使用量，但造成系統(tǒng)實時性差。Echidna與TinyOS一樣使用FIFO的方式調(diào)度任務，因此存在相同的缺點。

　　V.Subramonian等人在文獻[6]中研究了FIFO調(diào)度方式對TinyOS系統(tǒng)性能的影響。在使用TinyOS的系統(tǒng)中，當需要處理的數(shù)據(jù)量較大時，如果超過其計算能力，則會出現(xiàn)過載（overload）現(xiàn)象。處理過載的較好方式一般是保證關鍵任務的執(zhí)行，放棄非關鍵任務。而FIFO調(diào)度方式不能做到這一點，因為這種方式無法區(qū)分關鍵任務和非關鍵任務。下面通過分析TinyOS對通信數(shù)據(jù)包的處理來說明其缺點。

　　發(fā)送數(shù)據(jù)包由應用層產(chǎn)生并傳遞給底層發(fā)送構(gòu)件，當成功發(fā)送后，后者會觸發(fā)一個任務實例來通知應用層發(fā)送完畢。應用層在收到這一事件之前將一直等待，不能繼續(xù)發(fā)送數(shù)據(jù)。即，只有通知任務實例得到執(zhí)行，應用層才能繼續(xù)發(fā)送數(shù)據(jù)。如果TinyOS當前需要處理的數(shù)據(jù)量較大，有較多的任務實例需要執(zhí)行，則通知任務實例會排在FIFO隊列的最后，等到前面的任務實例執(zhí)行完才得以執(zhí)行。這樣就延緩了發(fā)送數(shù)據(jù)的過程，降低了通信數(shù)據(jù)包的吞吐量。在極端情況下，其它任務實例會將整個FIFO隊列占滿，通知任務實例到達時會被調(diào)度內(nèi)核放棄，造成應用層發(fā)送數(shù)據(jù)的終止。從無線信道接收數(shù)據(jù)時同樣會出現(xiàn)這種情況。

　　文獻[6]中提出了一種改進措施，給任務分配優(yōu)先級，將調(diào)度內(nèi)核升級為優(yōu)先級驅(qū)動的非搶占式調(diào)度。這樣與FIFO調(diào)度方式相比，能提高任務集合的可調(diào)度性，但仍會出現(xiàn)任務集合不可調(diào)度的情況。

　　2.2搶占閾值調(diào)度算法適合構(gòu)件化嵌入式操作系統(tǒng)

　　利用搶占閾值進行任務調(diào)度時，不但給集合G中的任務ti分配任務優(yōu)先級piÎ[1,2,…,n]，還分配搶占閾值gi，并且pi£gi，即，giÎ[pi,…,n]。這樣就實現(xiàn)了一個雙優(yōu)先級系統(tǒng)。其中的pi用于搶占其它的任務，而gi是任務運行中的有效優(yōu)先級。如果當前正在運行的任務是ti，那么對于就緒任務tj，必須有pj>gi，tj才能搶占ti。對于周期任務ti，每次開始執(zhí)行后，其優(yōu)先級將從pi提升為gi，執(zhí)行完后，優(yōu)先級再從gi下降為pi。

　　當任務的搶占閾值等于其任務優(yōu)先級時，就是搶占式調(diào)度;當任務的搶占閾值是系統(tǒng)最高優(yōu)先級時，就是非搶占式調(diào)度。所以搶占調(diào)度和非搶占調(diào)度是使用搶占閾值調(diào)度模型的兩個特例。實際中，搶占閾值調(diào)度能同時利用搶占式調(diào)度和非搶占式調(diào)度的優(yōu)點，通過調(diào)節(jié)任務搶占閾值，減少不必要的任務搶占，提高整個任務集合的可調(diào)度性。能運行搶占和非搶占式調(diào)度算法都不能調(diào)度的任務集合[2]。在文獻[3]描述的仿真環(huán)境下，搶占閾值調(diào)度算法與搶占式調(diào)度算法相比，處理器利用率提高15%-20%。搶占閾值調(diào)度模型中，任務集合被分割成數(shù)目很少的非搶占組（Non-PreemptiveGroup，簡稱NPG）。組內(nèi)任務之間是非搶占的，能共享一個棧空間，減少了任務集合對內(nèi)存資源的消耗。在文獻[4]的仿真環(huán)境下，當任務最大周期為100時，平均100個任務被分割成14.3個NPG。

　　在構(gòu)件化嵌入式操作系統(tǒng)的應用環(huán)境中，希望能在提高任務集合可調(diào)度性的同時，使用盡可能少的內(nèi)存資源。根據(jù)這一要求，本文提出了在實時調(diào)度內(nèi)核中使用搶占閾值調(diào)度算法。為了說明該算法較其它調(diào)度算法更適于構(gòu)件化嵌入式操作系統(tǒng)，提出了如下的指標，以比較各種算法的性能：非搶占式調(diào)度中，所有任務共享一個線程棧空間，節(jié)省了內(nèi)存資源。對于搶占閾值調(diào)度，如果任務集合生成一個非搶占組，則會使用與非搶占式調(diào)度相同的內(nèi)存資源。為此，在每個測試點，針對相同一組隨機產(chǎn)生的任務集合，比較搶占閾值調(diào)度生成一個非搶占組的次數(shù)除以整個產(chǎn)生的任務集合個數(shù)（用NAT表示）得到的百分率，與非搶占式調(diào)度以及FIFO調(diào)度方式下可調(diào)度任務集合個數(shù)除以NAT得到的百分率，稱作單線程比率（OneThreadRate，簡稱OTR）。來說明不同算法在保證任務集合可調(diào)度的前提下，只使用一個線程的能力。

　　使用隨機產(chǎn)生的任務集合。生成任務時，任務個數(shù)totalTasks從2開始，以2為步長遞增到50;任務集合的最大周期maxPeriod取為1000。任務個數(shù)和最大周期的取值構(gòu)成一個測試點。在每個測試點，任務集合按如下規(guī)則產(chǎn)生：（1）在[1,maxPeriod]之間均勻、隨機地選擇任務周期Ti。（2）在[0.1/totoalTasks,2.0/totalTask]之間均勻、隨機地選擇任務利用率Ui，任務執(zhí)行時間Ci=Ui＊Ti。用任務個數(shù)來調(diào)整取值，以免產(chǎn)生過多的不可調(diào)度任務集合。（3）任務截至期Di=Ti。

　　在每個測試點，從100次獨立仿真實驗中獲得各調(diào)度算法的性能指標值，以進行性能比較。

　　圖1給出了針對相同一組任務集合，搶占閾值、非搶占式和FIFO等3種調(diào)度算法下產(chǎn)生的單線程比率?？梢钥闯?，F(xiàn)IFO調(diào)度方式的性能最差。在大部分測試點，搶占閾值調(diào)度下產(chǎn)生的使用一個線程的任務集合個數(shù)等于非搶占調(diào)度下生成的可調(diào)度任務集合個數(shù)。只在少數(shù)幾個測試點，前者產(chǎn)生的OTR值略低于后者。所以，在此指標下，搶占閾值調(diào)度具有與非搶占式調(diào)度接近的性能。但搶占閾值調(diào)度能提高任務集合的可調(diào)度性?？傊?，搶占閾值調(diào)度能在提高任務集合可調(diào)度性的同時，使用較少的內(nèi)存資源。與其它兩種調(diào)度算法相比，更適合作為構(gòu)件化嵌入式操作系統(tǒng)的實時調(diào)度算法

圖1比較3種算法得到的OTR值

3構(gòu)件模型和映射成任務的方式

　　一般基于構(gòu)件的軟件開發(fā)中，使用已生成并被證明是可靠的構(gòu)件來”建造”整個系統(tǒng)軟件。這需要一個定義構(gòu)件的方法，即，構(gòu)件模型。研究和實踐證明，構(gòu)件模型必須有信息隱藏的能力和明確定義的接口。前者使構(gòu)件能在不同的系統(tǒng)中替換和重用，而后者是構(gòu)件與環(huán)境交互的通道。外界只能通過接口訪問構(gòu)件，這也是對信息隱藏的輔助支持。對于實時系統(tǒng)來說，構(gòu)架模型還應包含時間屬性，例如：構(gòu)件執(zhí)行時間、最終截止期和周期等，從而能在構(gòu)造完系統(tǒng)后，進行可調(diào)度性分析。通常的實時軟件開發(fā)中，任務是構(gòu)造系統(tǒng)的基本單元，因此模型還應定義將構(gòu)件映射成任務的方式。與桌面/企業(yè)級應用不同，開發(fā)嵌入式系統(tǒng)適合用源代碼級構(gòu)件。因為：（1）開發(fā)者可以訪問構(gòu)件源碼（不是修改構(gòu)件），通過”白盒”測試來發(fā)現(xiàn)錯誤。而使用二進制代碼構(gòu)件進行”黑盒”測試，將減弱開發(fā)者對系統(tǒng)行為的控制能力。（2）嵌入式系統(tǒng)是在資源有限的節(jié)點上運行復雜可靠的控制應用，不需動態(tài)配置，只需在一組靜態(tài)配置的模式間切換。所以為了更好地支持系統(tǒng)的可分析性、可測試性和減少內(nèi)存消耗，應該在運行前（編譯時）配置構(gòu)件的行為和相互之間的連接。這也需要使用源代碼級構(gòu)件。

　　因為管道和過濾模型[7]適于控制應用，而大部分嵌入式系統(tǒng)是控制系統(tǒng)。所以，我們基于管道和過濾模型為構(gòu)件化嵌入式操作系統(tǒng)的應用層定義一種實時構(gòu)件模型。該構(gòu)件模型是源代碼級的，每個構(gòu)件包括：（1）名稱，作為構(gòu)件的身份標識。（2）一組輸入和輸出端口，前者用于接收數(shù)據(jù)，后者用于產(chǎn)生數(shù)據(jù)，端口不會緩存數(shù)據(jù)，構(gòu)件之間通過端口通信。（3）一組構(gòu)件屬性，存儲構(gòu)件的元數(shù)據(jù)信息，包括構(gòu)件所用內(nèi)存大小、執(zhí)行時間、最終截至期、釋放時間和周期等。（4）一個行為體，實現(xiàn)構(gòu)件功能，被輸入端口數(shù)據(jù)（事件）觸發(fā)，根據(jù)當前操作模式處理數(shù)據(jù)，并產(chǎn)生觸發(fā)下一構(gòu)件的輸出數(shù)據(jù)（事件）。通信數(shù)據(jù)在構(gòu)件之間傳遞，由底層調(diào)度內(nèi)核通過對行為體的邏輯調(diào)用來引導。

　　當前存在將多個構(gòu)件映射成一個任務[8]和將一個構(gòu)件映射成多個任務[9]的方式，我們考慮這些映射方式的目的都是希望能在簡化結(jié)構(gòu)分析和減少運行時系統(tǒng)開銷之間獲得一個適當?shù)恼壑?。將一個構(gòu)件映射成一個任務能簡化結(jié)構(gòu)分析，但可能造成系統(tǒng)運行時任務較多，如果底層實時操作系統(tǒng)采用搶占式調(diào)度算法，則會增加任務之間相互搶占的次數(shù)，從而增加現(xiàn)場切換等系統(tǒng)開銷，降低處理器的利用率，影響任務集合的可調(diào)度性。另外，還會增加對系統(tǒng)內(nèi)存的消耗。所以我們提出了一種設計方法：構(gòu)件是被動的，不包含自己的線程，裝配時才將構(gòu)件分配到線程，每個構(gòu)件映射成一個任務，這使系統(tǒng)結(jié)構(gòu)清晰，并能簡化分析過程;而系統(tǒng)運行時出現(xiàn)的上述問題，通過為底層構(gòu)件化嵌入式實時操作系統(tǒng)選擇合適的調(diào)度模型來解決，例如選擇非搶占式調(diào)度算法能減少內(nèi)存消耗，而選擇搶占閾值調(diào)度算法既能提高任務集合的可調(diào)度性，又能減少對系統(tǒng)內(nèi)存的使用。

　　映射完成后，構(gòu)件屬性就成為任務的屬性。執(zhí)行期間，系統(tǒng)保證輸入端口上的數(shù)據(jù)不會改變，以避免數(shù)據(jù)的不一致。對于相互連接的構(gòu)件，利用編譯程序創(chuàng)建系統(tǒng)任務，以完成構(gòu)件之間的數(shù)據(jù)通信，并根據(jù)互連構(gòu)件的特性指定這些任務的釋放時間、周期、執(zhí)行時間和最終截止期等參數(shù)。圖2給出了構(gòu)件模型的示例圖。圖2的右側(cè)表示了任務（構(gòu)件）執(zhí)行體包含的程序結(jié)構(gòu)。

圖2構(gòu)件模型示例圖

4總結(jié)

　　嵌入式系統(tǒng)開發(fā)使用構(gòu)件技術(shù)時，不但要從結(jié)構(gòu)的角度將系統(tǒng)分解成若干構(gòu)件;還要從運行的角度將構(gòu)件映射成任務，為底層內(nèi)核選擇適當?shù)膶崟r調(diào)度算法，根據(jù)算法給任務分配優(yōu)先級，并判定任務集合的可調(diào)度性。當前對后者研究較少。針對這一問題，本文首先通過比較3種調(diào)度算法，得出搶占閾值調(diào)度更適合構(gòu)件化嵌入式操作系統(tǒng)的結(jié)論。仿真實驗證明了這一觀點。然后根據(jù)已有工程實踐，提出一種適合于嵌入式實時系統(tǒng)的軟件構(gòu)件模型以及將構(gòu)件映射成任務的方式。本文論述的模型和算法構(gòu)成了一個較完整的方案，對構(gòu)件化嵌入式實時系統(tǒng)的開發(fā)有一定參考價值。

參考文獻：

　　[1]JasonHill,RobertSzewczyk,AlecWoo,SethHollar,DavidE.Culler,andKristoferS.J.Pister.Systemarchitecturedirectionsfornetworkedsensors.InArchitecturalSupportforProgrammingLanguagesandOperatingSystems,pages93-104,2000.

　　[2]Y.Wang,M.Saksena.Schedulingfixed-prioritytaskswithpreemptionthreshold.In:GakkaiJS,ed.Proc.ofthe6thInt’lConf.onReal-TimeComputingSystemsandApplication.LosAlamitos:IEEEComputerSociety,1999.328～335.

　　[3]Y.WangandM.Saksena.Schedulingfixed-prioritytaskswithpreemptionthreshold:anattractivetechnology?http:///wpall.html

　　[4]ManasSaksenaandYunWang.Scalablereal-timesystemdesignusingpreemptionthreshold.InProceedingsoftheRealTimeSystemsSymposium,December2000

　　[5]Echidna:areal-timeoperatingsystemtosupportreconfigurablesoftwareonmicrocontrollersanddigitalsignalprocessors.http://www.ee.umd.edu/serts/research/echidna/index.shtml

　　[6]V.Subramonian,H.-M.Huang,S.Datar,andC.Lu.Priorityschedulingintinyos-acasestudy.DepartmentofComputerScience,WashingtonUniversity,St.Louis.MO

　　[7]AndersMöller,MikaelÅkerholm,JohanFredriksson,MikaelNolin.Anindustrialevaluationofcomponenttechnologiesforembeddedsystems.MRTCReportISSN1404-3041ISRNMDH-MRTC-155/2004-1-SE

　　[8]ShigeWang,KangG.Shin.Anarchitectureforembeddedsoftwareintegrationusingreusablecomponents.CASES2000:110-118

　　[9]HideyukiTokuda,CliffordW.Mercer.ARTS:adistributedreal-timekernel.OperatingSystemsReview,1989,23（3）:29-53