摘 要：本文分析了現(xiàn)有構件化嵌入式操作系統(tǒng)所用調度算法存在的缺點，提出搶占閾值調度算法是更為合適的算法。通過仿真實驗比較搶占閾值調度算法、非搶占式調度算法和FIFO（First-In-First-Out）調度算法的性能，證明了上述結論。通過分析現(xiàn)有嵌入式系統(tǒng)構件模型的特點，提出了一種構件模型以及將構件映射成任務的方式，還提出了一種設計方法。整個方案能提高構件化嵌入式操作系統(tǒng)的性能。 關鍵詞：構件化嵌入式操作系統(tǒng); 搶占閾值調度; FIFO調度; 構件模型 1 前言 　　如何將構件技術成功地應用到嵌入式操作系統(tǒng)開發(fā)中得到越來越多的重視?，F(xiàn)有的工作大部分著重于從結構的角度分解系統(tǒng)成若干構件，并重用構件。實際嵌入式實時系統(tǒng)的處理器資源和內存資源是有限的，同時系統(tǒng)還有實時性需求。另外，當前成熟的實時調度算法都是基于任務模型分析系統(tǒng)的可調度性。所以，在嵌入式實時系統(tǒng)中應用構件技術時，還需要研究如何從時間（運行）的角度將構件映射成任務，以及為底層構件化嵌入式實時操作系統(tǒng)選擇合適的調度算法。 　　本文首先分析了現(xiàn)有構件化嵌入式操作系統(tǒng)的特點，著重分析了TinyOS[1]的調度內核。通過仿真實驗比較了搶占閾值（簡稱PT）調度算法[2]、非搶占式（簡稱NP）調度算法和FIFO調度方式的性能，證明了當任務之間無共享資源時，搶占閾值調度算法適合作為構件化嵌入式操作系統(tǒng)的實時調度算法。之后，本文論述了嵌入式實時系統(tǒng)對構件模型的需求，提出了一種構件模型。通過分析比較現(xiàn)有的映射方式，提出了一個將構件映射成任務的方式和一種設計方法。 2 適合構件化嵌入式操作系統(tǒng)的調度算法 　　首先定義單處理器靜態(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)到結束執(zhí)行所用的時間稱作實例的響應時間（response time）。在一個系統(tǒng)的整個運行過程中，任務的最壞情況響應時間等于其所有實例中最大的響應時間。 　　2.1 TinyOS存在的問題 　　當前的構件化嵌入式操作系統(tǒng)主要有TinyOS和Echidna[5]兩種。TinyOS是為無線傳感器網(wǎng)絡（Wireless Sensor Network，簡稱WSN）開發(fā)的構件化嵌入式操作系統(tǒng)，適用于內存資源和處理能力有限，電池供電的嵌入式系統(tǒng)。其內核支持兩級調度，任務按照FIFO的方式執(zhí)行，目的是減少對內存的使用量，但造成系統(tǒng)實時性差。Echidna與TinyOS一樣使用FIFO的方式調度任務，因此存在相同的缺點。 　　V. Subramonian等人在文獻[6]中研究了FIFO調度方式對TinyOS系統(tǒng)性能的影響。在使用TinyOS的系統(tǒng)中，當需要處理的數(shù)據(jù)量較大時，如果超過其計算能力，則會出現(xiàn)過載（overload）現(xiàn)象。處理過載的較好方式一般是保證關鍵任務的執(zhí)行，放棄非關鍵任務。而FIFO調度方式不能做到這一點，因為這種方式無法區(qū)分關鍵任務和非關鍵任務。下面通過分析TinyOS對通信數(shù)據(jù)包的處理來說明其缺點。 　　發(fā)送數(shù)據(jù)包由應用層產(chǎn)生并傳遞給底層發(fā)送構件，當成功發(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隊列占滿，通知任務實例到達時會被調度內核放棄，造成應用層發(fā)送數(shù)據(jù)的終止。從無線信道接收數(shù)據(jù)時同樣會出現(xiàn)這種情況。 　　文獻[6]中提出了一種改進措施，給任務分配優(yōu)先級，將調度內核升級為優(yōu)先級驅動的非搶占式調度。這樣與FIFO調度方式相比，能提高任務集合的可調度性，但仍會出現(xiàn)任務集合不可調度的情況。 　　2.2 搶占閾值調度算法適合構件化嵌入式操作系統(tǒng) 　　利用搶占閾值進行任務調度時，不但給集合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)先級時，就是搶占式調度;當任務的搶占閾值是系統(tǒng)最高優(yōu)先級時，就是非搶占式調度。所以搶占調度和非搶占調度是使用搶占閾值調度模型的兩個特例。實際中，搶占閾值調度能同時利用搶占式調度和非搶占式調度的優(yōu)點，通過調節(jié)任務搶占閾值，減少不必要的任務搶占，提高整個任務集合的可調度性。能運行搶占和非搶占式調度算法都不能調度的任務集合[2]。在文獻[3]描述的仿真環(huán)境下，搶占閾值調度算法與搶占式調度算法相比，處理器利用率提高15%-20%。搶占閾值調度模型中，任務集合被分割成數(shù)目很少的非搶占組（Non-Preemptive Group，簡稱NPG）。組內任務之間是非搶占的，能共享一個棧空間，減少了任務集合對內存資源的消耗。在文獻[4]的仿真環(huán)境下，當任務最大周期為100時，平均100個任務被分割成14.3個NPG。 　　在構件化嵌入式操作系統(tǒng)的應用環(huán)境中，希望能在提高任務集合可調度性的同時，使用盡可能少的內存資源。根據(jù)這一要求，本文提出了在實時調度內核中使用搶占閾值調度算法。為了說明該算法較其它調度算法更適于構件化嵌入式操作系統(tǒng)，提出了如下的指標，以比較各種算法的性能：非搶占式調度中，所有任務共享一個線程棧空間，節(jié)省了內存資源。對于搶占閾值調度，如果任務集合生成一個非搶占組，則會使用與非搶占式調度相同的內存資源。為此，在每個測試點，針對相同一組隨機產(chǎn)生的任務集合，比較搶占閾值調度生成一個非搶占組的次數(shù)除以整個產(chǎn)生的任務集合個數(shù)（用NAT表示）得到的百分率，與非搶占式調度以及FIFO調度方式下可調度任務集合個數(shù)除以NAT得到的百分率，稱作單線程比率（One Thread Rate，簡稱OTR）。來說明不同算法在保證任務集合可調度的前提下，只使用一個線程的能力。 　　使用隨機產(chǎn)生的任務集合。生成任務時，任務個數(shù)totalTasks從2開始，以2為步長遞增到50;任務集合的最大周期maxPeriod取為1000。任務個數(shù)和最大周期的取值構成一個測試點。在每個測試點，任務集合按如下規(guī)則產(chǎn)生：（1）在[1, maxPeriod]之間均勻、隨機地選擇任務周期Ti。（2）在[0.1/totoalTasks, 2.0/totalTask]之間均勻、隨機地選擇任務利用率Ui，任務執(zhí)行時間Ci=Ui＊Ti。用任務個數(shù)來調整取值，以免產(chǎn)生過多的不可調度任務集合。（3）任務截至期Di=Ti。 　　在每個測試點，從100次獨立仿真實驗中獲得各調度算法的性能指標值，以進行性能比較。 　　圖1給出了針對相同一組任務集合，搶占閾值、非搶占式和FIFO等3種調度算法下產(chǎn)生的單線程比率?？梢钥闯?，F(xiàn)IFO調度方式的性能最差。在大部分測試點，搶占閾值調度下產(chǎn)生的使用一個線程的任務集合個數(shù)等于非搶占調度下生成的可調度任務集合個數(shù)。只在少數(shù)幾個測試點，前者產(chǎn)生的OTR值略低于后者。所以，在此指標下，搶占閾值調度具有與非搶占式調度接近的性能。但搶占閾值調度能提高任務集合的可調度性?？傊瑩屨奸撝嫡{度能在提高任務集合可調度性的同時，使用較少的內存資源。與其它兩種調度算法相比，更適合作為構件化嵌入式操作系統(tǒng)的實時調度算法 [align=center] 圖1比較3種算法得到的OTR值[/align] 3 構件模型和映射成任務的方式 　　一般基于構件的軟件開發(fā)中，使用已生成并被證明是可靠的構件來”建造”整個系統(tǒng)軟件。這需要一個定義構件的方法，即，構件模型。研究和實踐證明，構件模型必須有信息隱藏的能力和明確定義的接口。前者使構件能在不同的系統(tǒng)中替換和重用，而后者是構件與環(huán)境交互的通道。外界只能通過接口訪問構件，這也是對信息隱藏的輔助支持。對于實時系統(tǒng)來說，構架模型還應包含時間屬性，例如：構件執(zhí)行時間、最終截止期和周期等，從而能在構造完系統(tǒng)后，進行可調度性分析。通常的實時軟件開發(fā)中，任務是構造系統(tǒng)的基本單元，因此模型還應定義將構件映射成任務的方式。與桌面/企業(yè)級應用不同，開發(fā)嵌入式系統(tǒng)適合用源代碼級構件。因為：（1）開發(fā)者可以訪問構件源碼（不是修改構件），通過”白盒”測試來發(fā)現(xiàn)錯誤。而使用二進制代碼構件進行”黑盒”測試，將減弱開發(fā)者對系統(tǒng)行為的控制能力。（2）嵌入式系統(tǒng)是在資源有限的節(jié)點上運行復雜可靠的控制應用，不需動態(tài)配置，只需在一組靜態(tài)配置的模式間切換。所以為了更好地支持系統(tǒng)的可分析性、可測試性和減少內存消耗，應該在運行前（編譯時）配置構件的行為和相互之間的連接。這也需要使用源代碼級構件。 　　因為管道和過濾模型[7]適于控制應用，而大部分嵌入式系統(tǒng)是控制系統(tǒng)。所以，我們基于管道和過濾模型為構件化嵌入式操作系統(tǒng)的應用層定義一種實時構件模型。該構件模型是源代碼級的，每個構件包括：（1）名稱，作為構件的身份標識。（2）一組輸入和輸出端口，前者用于接收數(shù)據(jù)，后者用于產(chǎn)生數(shù)據(jù)，端口不會緩存數(shù)據(jù)，構件之間通過端口通信。（3）一組構件屬性，存儲構件的元數(shù)據(jù)信息，包括構件所用內存大小、執(zhí)行時間、最終截至期、釋放時間和周期等。（4）一個行為體，實現(xiàn)構件功能，被輸入端口數(shù)據(jù)（事件）觸發(fā)，根據(jù)當前操作模式處理數(shù)據(jù)，并產(chǎn)生觸發(fā)下一構件的輸出數(shù)據(jù)（事件）。通信數(shù)據(jù)在構件之間傳遞，由底層調度內核通過對行為體的邏輯調用來引導。 　　當前存在將多個構件映射成一個任務[8]和將一個構件映射成多個任務[9]的方式，我們考慮這些映射方式的目的都是希望能在簡化結構分析和減少運行時系統(tǒng)開銷之間獲得一個適當?shù)恼壑?。將一個構件映射成一個任務能簡化結構分析，但可能造成系統(tǒng)運行時任務較多，如果底層實時操作系統(tǒng)采用搶占式調度算法，則會增加任務之間相互搶占的次數(shù)，從而增加現(xiàn)場切換等系統(tǒng)開銷，降低處理器的利用率，影響任務集合的可調度性。另外，還會增加對系統(tǒng)內存的消耗。所以我們提出了一種設計方法：構件是被動的，不包含自己的線程，裝配時才將構件分配到線程，每個構件映射成一個任務，這使系統(tǒng)結構清晰，并能簡化分析過程;而系統(tǒng)運行時出現(xiàn)的上述問題，通過為底層構件化嵌入式實時操作系統(tǒng)選擇合適的調度模型來解決，例如選擇非搶占式調度算法能減少內存消耗，而選擇搶占閾值調度算法既能提高任務集合的可調度性，又能減少對系統(tǒng)內存的使用。 　　映射完成后，構件屬性就成為任務的屬性。執(zhí)行期間，系統(tǒng)保證輸入端口上的數(shù)據(jù)不會改變，以避免數(shù)據(jù)的不一致。對于相互連接的構件，利用編譯程序創(chuàng)建系統(tǒng)任務，以完成構件之間的數(shù)據(jù)通信，并根據(jù)互連構件的特性指定這些任務的釋放時間、周期、執(zhí)行時間和最終截止期等參數(shù)。圖2給出了構件模型的示例圖。圖2的右側表示了任務（構件）執(zhí)行體包含的程序結構。 [align=center] 圖2 構件模型示例圖[/align] 4 總結 　　嵌入式系統(tǒng)開發(fā)使用構件技術時，不但要從結構的角度將系統(tǒng)分解成若干構件;還要從運行的角度將構件映射成任務，為底層內核選擇適當?shù)膶崟r調度算法，根據(jù)算法給任務分配優(yōu)先級，并判定任務集合的可調度性。當前對后者研究較少。針對這一問題，本文首先通過比較3種調度算法，得出搶占閾值調度更適合構件化嵌入式操作系統(tǒng)的結論。仿真實驗證明了這一觀點。然后根據(jù)已有工程實踐，提出一種適合于嵌入式實時系統(tǒng)的軟件構件模型以及將構件映射成任務的方式。本文論述的模型和算法構成了一個較完整的方案，對構件化嵌入式實時系統(tǒng)的開發(fā)有一定參考價值。 參考文獻： 　　[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