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