摘 要：本文分析了現(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í)間（response time）。在一個(gè)系統(tǒng)的整個(gè)運(yùn)行過程中，任務(wù)的最壞情況響應(yīng)時(shí)間等于其所有實(shí)例中最大的響應(yīng)時(shí)間。 　　2.1 TinyOS存在的問題 　　當(dāng)前的構(gòu)件化嵌入式操作系統(tǒng)主要有TinyOS和Echidna[5]兩種。TinyOS是為無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，簡稱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-Preemptive Group，簡稱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得到的百分率，稱作單線程比率（One Thread Rate，簡稱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)度算法 [align=center] 圖1比較3種算法得到的OTR值[/align] 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)錯(cuò)誤。而使用二進(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)。 [align=center] 圖2 構(gòu)件模型示例圖[/align] 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] Jason Hill, Robert Szewczyk, Alec Woo, Seth Hollar, David E. Culler, and Kristofer S. J. Pister. System architecture directions for networked sensors. In Architectural Support for Programming Languages and Operating Systems, pages 93-104, 2000. 　　[2] Y. Wang, M. Saksena. Scheduling fixed-priority tasks with preemption threshold. In: Gakkai JS, ed. Proc. of the 6th Int’l Conf. on Real-Time Computing Systems and Application. Los Alamitos: IEEE Computer Society, 1999. 328～335. 　　[3] Y. Wang and M. Saksena. Scheduling fixed-priority tasks with preemption threshold: an attractive technology? http://www.expresslogic.com/wpall.html 　　[4] Manas Saksena and Yun Wang. Scalable real-time system design using preemption threshold. In Proceedings of the Real Time Systems Symposium, December 2000 　　[5] Echidna: a real-time operating system to support reconfigurable software on microcontrollers and digital signal processors. http://www.ee.umd.edu/serts/research/echidna/index.shtml 　　[6] V. Subramonian, H.-M. Huang, S. Datar, and C. Lu. Priority scheduling in tinyos - a case study. Department of Computer Science, Washington University, St. Louis. MO 　　[7] Anders Möller, Mikael Åkerholm, Johan Fredriksson, Mikael Nolin. An industrial evaluation of component technologies for embedded systems. MRTC Report ISSN 1404-3041 ISRN MDH-MRTC-155/2004-1-SE 　　[8] Shige Wang, Kang G. Shin. An architecture for embedded software integration using reusable components. CASES 2000: 110-118 　　[9] Hideyuki Tokuda, Clifford W. Mercer. ARTS: a distributed real-time kernel. Operating Systems Review, 1989, 23（3）: 29-53