一種提高構(gòu)件化嵌入式操作系統(tǒng)性能的方案

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

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

1前言

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

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

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

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

　　2.1TinyOS存在的問題

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

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

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

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

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

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

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

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

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

　　在每個(gè)測試點(diǎn)，從100次獨(dú)立仿真實(shí)驗(yàn)中獲得各調(diào)度算法的性能指標(biāo)值，以進(jìn)行性能比較。

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

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

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

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

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

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

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

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

4總結(jié)

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

參考文獻(xiàn)：

　　[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