1前言

如何將構(gòu)件技術(shù)成功地應(yīng)用到嵌入式操作系統(tǒng)開(kāi)發(fā)中得到越來(lái)越多的重視?，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)核。通過(guò)仿真實(shí)驗(yàn)比較了搶占閾值（簡(jiǎn)稱(chēng)PT）調(diào)度算法［2］、非搶占式（簡(jiǎn)稱(chēng)NP）調(diào)度算法和FIFO調(diào)度方式的性能，證明了當(dāng)任務(wù)之間無(wú)共享資源時(shí)，搶占閾值調(diào)度算法適合作為構(gòu)件化嵌入式操作系統(tǒng)的實(shí)時(shí)調(diào)度算法。之后，本文論述了嵌入式實(shí)時(shí)系統(tǒng)對(duì)構(gòu)件模型的需求，提出了一種構(gòu)件模型。通過(guò)分析比較現(xiàn)有的映射方式，提出了一個(gè)將構(gòu)件映射成任務(wù)的方式和一種設(shè)計(jì)方法。

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

首先定義單處理器靜態(tài)優(yōu)先級(jí)實(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的周期（對(duì)于偶發(fā)性任務(wù)就是最小到達(dá)間隔），Ci表示ti的最壞情況執(zhí)行時(shí)間，Di表示ti的相對(duì)截止期。我們假定大的數(shù)值表示高的優(yōu)先級(jí)，對(duì)于集合G，最小的優(yōu)先級(jí)是1，最大的優(yōu)先級(jí)是n。周期任務(wù)的一次執(zhí)行，稱(chēng)作任務(wù)的一個(gè)實(shí)例。任務(wù)實(shí)例從進(jìn)入系統(tǒng)到結(jié)束執(zhí)行所用的時(shí)間稱(chēng)作實(shí)例的響應(yīng)時(shí)間（responsetime）。在一個(gè)系統(tǒng)的整個(gè)運(yùn)行過(guò)程中，任務(wù)的最壞情況響應(yīng)時(shí)間等于其所有實(shí)例中最大的響應(yīng)時(shí)間。

2.1TinyOS存在的問(wèn)題

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

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

發(fā)送數(shù)據(jù)包由應(yīng)用層產(chǎn)生并傳遞給底層發(fā)送構(gòu)件，當(dāng)成功發(fā)送后，后者會(huì)觸發(fā)一個(gè)任務(wù)實(shí)例來(lái)通知應(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í)例會(huì)排在FIFO隊(duì)列的最后，等到前面的任務(wù)實(shí)例執(zhí)行完才得以執(zhí)行。這樣就延緩了發(fā)送數(shù)據(jù)的過(guò)程，降低了通信數(shù)據(jù)包的吞吐量。在極端情況下，其它任務(wù)實(shí)例會(huì)將整個(gè)FIFO隊(duì)列占滿(mǎn)，通知任務(wù)實(shí)例到達(dá)時(shí)會(huì)被調(diào)度內(nèi)核放棄，造成應(yīng)用層發(fā)送數(shù)據(jù)的終止。從無(wú)線信道接收數(shù)據(jù)時(shí)同樣會(huì)出現(xiàn)這種情況。

文獻(xiàn)［6］中提出了一種改進(jìn)措施，給任務(wù)分配優(yōu)先級(jí)，將調(diào)度內(nèi)核升級(jí)為優(yōu)先級(jí)驅(qū)動(dòng)的非搶占式調(diào)度。這樣與FIFO調(diào)度方式相比，能提高任務(wù)集合的可調(diào)度性，但仍會(huì)出現(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)先級(jí)pi?［1，2，…，n］，還分配搶占閾值gi，并且pi￡gi，即，gi?［pi，…，n］。這樣就實(shí)現(xiàn)了一個(gè)雙優(yōu)先級(jí)系統(tǒng)。其中的pi用于搶占其它的任務(wù)，而gi是任務(wù)運(yùn)行中的有效優(yōu)先級(jí)。如果當(dāng)前正在運(yùn)行的任務(wù)是ti，那么對(duì)于就緒任務(wù)tj，必須有pj》gi，tj才能搶占ti。對(duì)于周期任務(wù)ti，每次開(kāi)始執(zhí)行后，其優(yōu)先級(jí)將從pi提升為gi，執(zhí)行完后，優(yōu)先級(jí)再?gòu)膅i下降為pi。

當(dāng)任務(wù)的搶占閾值等于其任務(wù)優(yōu)先級(jí)時(shí)，就是搶占式調(diào)度;當(dāng)任務(wù)的搶占閾值是系統(tǒng)最高優(yōu)先級(jí)時(shí)，就是非搶占式調(diào)度。所以搶占調(diào)度和非搶占調(diào)度是使用搶占閾值調(diào)度模型的兩個(gè)特例。實(shí)際中，搶占閾值調(diào)度能同時(shí)利用搶占式調(diào)度和非搶占式調(diào)度的優(yōu)點(diǎn)，通過(guò)調(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，簡(jiǎn)稱(chēng)NPG）。組內(nèi)任務(wù)之間是非搶占的，能共享一個(gè)?？臻g，減少了任務(wù)集合對(duì)內(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)度算法。為了說(shuō)明該算法較其它調(diào)度算法更適于構(gòu)件化嵌入式操作系統(tǒng)，提出了如下的指標(biāo)，以比較各種算法的性能：非搶占式調(diào)度中，所有任務(wù)共享一個(gè)線程?？臻g，節(jié)省了內(nèi)存資源。對(duì)于搶占閾值調(diào)度，如果任務(wù)集合生成一個(gè)非搶占組，則會(huì)使用與非搶占式調(diào)度相同的內(nèi)存資源。為此，在每個(gè)測(cè)試點(diǎn)，針對(duì)相同一組隨機(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得到的百分率，稱(chēng)作單線程比率（OneThreadRate，簡(jiǎn)稱(chēng)OTR）。來(lái)說(shuō)明不同算法在保證任務(wù)集合可調(diào)度的前提下，只使用一個(gè)線程的能力。

使用隨機(jī)產(chǎn)生的任務(wù)集合。生成任務(wù)時(shí)，任務(wù)個(gè)數(shù)totalTasks從2開(kāi)始，以2為步長(zhǎng)遞增到50;任務(wù)集合的最大周期maxPeriod取為1000。任務(wù)個(gè)數(shù)和最大周期的取值構(gòu)成一個(gè)測(cè)試點(diǎn)。在每個(gè)測(cè)試點(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ù)來(lái)調(diào)整取值，以免產(chǎn)生過(guò)多的不可調(diào)度任務(wù)集合。（3）任務(wù)截至期Di=Ti。

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

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

因?yàn)楣艿篮瓦^(guò)濾模型［7］適于控制應(yīng)用，而大部分嵌入式系統(tǒng)是控制系統(tǒng)。所以，我們基于管道和過(guò)濾模型為構(gòu)件化嵌入式操作系統(tǒng)的應(yīng)用層定義一種實(shí)時(shí)構(gòu)件模型。該構(gòu)件模型是源代碼級(jí)的，每個(gè)構(gòu)件包括：（1）名稱(chēng)，作為構(gòu)件的身份標(biāo)識(shí)。（2）一組輸入和輸出端口，前者用于接收數(shù)據(jù)，后者用于產(chǎn)生數(shù)據(jù)，端口不會(huì)緩存數(shù)據(jù)，構(gòu)件之間通過(guò)端口通信。（3）一組構(gòu)件屬性，存儲(chǔ)構(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)核通過(guò)對(duì)行為體的邏輯調(diào)用來(lái)引導(dǎo)。

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

映射完成后，構(gòu)件屬性就成為任務(wù)的屬性。執(zhí)行期間，系統(tǒng)保證輸入端口上的數(shù)據(jù)不會(huì)改變，以避免數(shù)據(jù)的不一致。對(duì)于相互連接的構(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)開(kāi)發(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)先級(jí)，并判定任務(wù)集合的可調(diào)度性。當(dāng)前對(duì)后者研究較少。針對(duì)這一問(wèn)題，本文首先通過(guò)比較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è)較完整的方案，對(duì)構(gòu)件化嵌入式實(shí)時(shí)系統(tǒng)的開(kāi)發(fā)有一定參考價(jià)值。