基于優先級可搶占式調度策略的設計

翟 月

（1、合肥工業大學，安徽 合肥 230009 2、安徽電子信息職業技術學院，安徽 蚌埠 233000）

1 設計基礎

TinyOS采用基于組件的架構方式，以快速實現各種應用。它的組件包括兩類：模塊(module)和配置(configuration}，組件間通過配置文件連接在一起，形成可執行程序。組件提供或使用接口，這些接口是雙向的并且是訪問組件的唯一途徑。每個接口都定義了一系列函數，包括命令(command)和事件(event)兩類。

1.1 TinyOS調度機制

事件驅動的TinyOS采用兩級調度：任務和硬件事件處理。任務是一些可以被搶占的函數，一旦被調度，任務運行完成彼此之間不能相互搶占。硬件事件處理被執行去響應硬件中斷，可以搶占任務的運行或者其他硬件事件處理。TinyOS的任務調度隊列只是采用簡單的先入先出算法。任務事件的調度過程如圖1所示。TinyOS的任務隊列如果為空，則進入極低功耗的Sleep模式。當被事件觸發后，在 TinyOS中發出信號的事件關聯的所有任務被迅速處理。當這個事件和所有任務被處理完成，未被使用的CPU循環被置于睡眠狀態而不是積極尋找下一個活躍的事件。

1.2 TinyOS的局限性

盡管 TinyOS被廣泛使用，得到了認可，但這并不意味著 TinyOS能適用于無線傳感器網絡所有的應用場景。事實上，在某些場合TinyOS并不能工作得很好，而可能出現過載，導致任務丟失、通信吞吐量下降等問題：

1.2.1 某些任務執行時間很長，這時如果某些實時任務在該任務之后才進入任務隊列，就會影響實時性；對于數據包的收發，就會影響波特率。

1.2.2 本地任務發生頻率過高，任務隊列很快被本地任務填滿，其它任務就可能丟失；此外，如果本地任務過多(例如多個通道同時進行采集，則本地任務數量多)，也會影響通信的正常進行。

1.2.3 任務隊列中某個任務如果意外出現阻塞或異常時，會影響后續任務的運行，甚至導致系統癱瘓。

2 基于優先級可搶占式分級調度策略設計

為了滿足無線傳感器網絡要求，傳感器節點的設計必須是能量有效的。然而，能量有效性并不是傳感器網絡設計的唯一目標。在特定的應用環境下，實時的過程和感知信息的報告也是常常需要的。這樣，感知的數據從某個節點，通過多跳網絡，最終傳送到基站的過程中，我們可能需要保證一個盡可能長的傳輸時間。

事件驅動的操作系統被認為是建立能量有效的傳感器網絡的最佳選擇，因為它們只需要很少的內存和

處理資源。這樣，事件驅動的操作系統TinyOS成為了當前傳感器網絡操作系統的首選。事件驅動的操作系統在任務實時性要求較高的環境下就不是很有效了。由于所有的任務都是按照次序順序執行的，具有優先級的重要的任務要保證在時限之內被處理是不可能的。

基于優先級的可搶占式分級調度策略結合了事件驅動、分級調度和多線程的思想，將操作系統可處理的任務分為不同的優先級別，高優先級任務先得到響應。考慮到實時性要求嚴格的任務，搶占機制被引入到該調度系統中，即任務級別依次分為高優先級可搶占、高優先級不可搶占和一般優先級。高優先級可搶占任務能夠搶占當前正在執行的任務而先執行；高優先級不可搶占任務具有先

得到響應的權利，但不對當前正在執行的任務進行搶占；一般優先級任務即對應于一般Tiny OS任務。

我們使用一個基于組件的優先級層次調度器（PL調度器）來代替TinyOS系統提供的標準的先入先出調度器。PL調度器可以被嵌入應用程序中對任務首先執行的情況來達到更好的控制。PL調度器提供了以下幾種不同的優先級別：

（P1）高優先級可搶占

（P2）高優先級非可搶占

（P3）基本優先級（標準TinyOS任務使用）

在每個層次中，任務按照先進先出的方式進行調度。基本優先級層次的調度是必須實現的，因為所有的標準TinyOS任務都將默認在這個隊列中。相鄰的優先級層次提供了一個不可搶占的高優先級的隊列和一個可搶占的高優先級隊列。這樣，這三個層次中的任意任務都能按照他們的優先級進行調度，但不會搶占正在執行的任務，正如圖2所示。高優先級可搶占任務隊列是用來調度搶占一般任務的。一個高優先級可搶占的任務將會從優先級低于它的任務層次中搶占任何正在運行的任務，并且這些層次中的任何任務可以優先于任何一個優先級低于自身的任務而先得到響應。

結合上述設計思想，設計出基于優先級的可搶占式分級調度系統，實現面向調度器的線程以及分層調度系統的智能構造算法。它實現了一個基于事件驅動系統的多線程調度系統，其結構如圖3所示。

某個組件通過配置一個優先級任務接口到PL調度器組件中來指定一個優先級任務，并執行事件runTask()函數接口。這個程序在任務和調度器方面和TinyOS增加建議（TEP）106是一致的。

1:Module SomeComponentC{

2:use interface PriorityTask;

3:}

4:Implementation{

5: event void someEvent(){

6: call PriorityTask.postTask()

7:}

8:

9:event PriorityTask.runTask(){

10://task code

11:}

12:}

13:Configuration SomeComponent{

14:}

15:implementation{

16:components new PriorityTask()as PremptingTask;

17: components SomeComponentC，....

18: SomeComponentC.PriorityTask ->PremptingTask;….

19:}

算法1優先級任務結構

1:Module PLScheduler{

2: provides interface TaskPriority[id];

3: provides interface TaskPriority[id];

4:provides interface TaskBasic[id];

5: provides interface TaskPriority[id];

6: provides interface TaskPriority[id];

7:}

算法2優先級調度器結構

算法1給出了一個實現了的優先級任務的例子。某個組件要使用優先級任務，它就必須實現優先級任務接口，并且指明任務的優先級作為接口的參數（算法1，第2行）。這個接口提供了和基本任務語法post[task name]相同的postTask函數（算法1，第6行），和存儲任務功能的runtask事件處理器（算法1，第9行）。當任務將要被調度執行的時候，事件處理器由調度器激活。

每個任務都必須被配置到由PL調度器提供的五個帶參數的任務優先級接口中去（算法2，第2-6行）。配置過程在某種程度上往往被普通優先級任務組件簡化了（算法1，第16行），它利用接口參數信息來確定任務的優先級并且唯一的配置每個任務到合適的調度器接口中去。

3 系統性能分析

為了驗證本文提出的這種調度算法的改進效果，我們采用中科院計算所WSN課題組研發的GAINS節點作為實驗平臺。

為了檢驗分級調度算法的效果，我們把49個GAINS節點節點，每隔20m一個，部署在120m×120m的二維監測區域，并對其通訊情況作了記錄、統計。

3.1 實時性

我們使用了三種不同優先級別的任務，T0（轉發接收到的數據包），T1（接收待轉發的路由數據包），T2（處理本地數據并將其發送），分別對應高優先級可搶占任務，高優先級非可搶占任務和一般任務。三種任務依次按照T0，T1，T2的順序每隔時間t循環發送，而每個任務的執行時間為2t。我們對比了分級調度算法和TinyOS的響應情況，其實時任務響應情況如圖4所示 ：

圖4 實時任務斷響應比較

由此可以看出，分級調度策略能夠對實時任務及時響應，而TinyOS任務由于嚴格按照次序調度，實時任務不能得到優先響應。

3.2 可調度性

我們對分級調度算法和TinyOS在通訊中的丟包率做了統計，發現隨著任務數量的增多，任務數據包會發生丟失。分級調度中為每種任務分配單獨的隊列，且實時任務能夠及時得到響應，所以實時任務數據包的丟失率很低。而TinyOS中并不能對實時任務進行區別處理，從而不能保證實時任務的安全性。實時任務丟包率和執行時間之間的關系如圖5所示：

由此可見，分級調度系統始終能滿足任務集可調度性。TinyOS由于其不可搶占性，任務集可調度性隨利用率上升而下降。

圖5 可調度性比較

3.3 靈活性

TinyOS，Mantis OS，SOS，Contiki均使用固定的調度系統，沒有提供調度系統的定制機制。分級調度器的構造隨傳感器網絡應用環境的不同可以很方便的進行變化。在實時要求低的環境下，可以退化為TinyOS的完全非搶占調度隊列，所需子調度器數量為1。在實時要求高的情況，則構造出滿足實時要求的可搶占層次調度體系，各子調度器能夠采用不同的調度策略，根據實際應用兼顧實時性與內存空間限制的要求，是一個靈活有效的調度體系。

3.4 資源消耗

TinyOS中僅需在內存中分配一個任務隊列，而分級調度策略根據不同的應用需要配置2-4個任務隊列，需要更多的內存資源。在能量消耗方面，雖然都采用了事件驅動機制，但是TinyOS中任務是依次執行，而分級調度中存在搶占，因此會出現內容交換，會增加能耗。因此，相對于TinyOS來說，分級調度策略會消耗更多的能量。與MANTIS OS等多線程調度系統來說，分級調度的能量消耗又會比較少。

本實驗基于TOSSIM仿真環境來比較原有Tiny OS調度算法和改進后分級調度算法的節點能量消耗,通過模擬無線傳感器網絡節點運行并結合Power-TOSSIM來監控節點的能耗。我們每隔5 s對數據進行統計,圖表示的是網絡中一個節點每2 s的能量消耗。

從圖6中可以看出,采用分級調度算法所用的能量要略高于原有Tiny OS算法,這是因為改進的算法要進行時限的計算,系統開銷相對大一些,但平均所耗能量也只比原有增加4%左右,仍在可接受范圍內。

圖6 節點能量消耗比較

總之，分級調度策略不能在每個方面都更加優秀，它是在各個性能方面根據實際需求做出一個平衡的方案。

4 總結

本文以一種典型的無線傳感器網絡操作系統--TinyOS為研究對象，對其任務調度機制進行了分析，并指出了其特點和不足，進而提出了一種基于優先級的可搶占式分級調度策略。并通過仿真實驗對改進前后調度策略進行了比較分析。實驗結果表明，該改進方案能有效提高系統的實時性和可調度性，不失為一種可行的方案。

[1]李建中,高宏.無線傳感器網絡的研究進展[J].計算機研究與發展,2008,45(1):1-15.

[2]孫利民,李建中,陳渝,朱紅松.無線傳感器網絡[M].北京:清華大學出版社,2006.

[3]LEV IS P,MADDEN S,POLASTRE J et al.TinyOS: an operating system fo wirelesssensornetworks [C /OL ]/WEBER W,RABAEY J,AARTS E.Ambien Intelligence.New York,NY:Sp ringer2Verlag 2005.http://bwrc.eecs.berkeley.edu classes/ee290q/Readings/culler.pdf.

[4]GAYD,LEV IS P,CULLER D.Softwar design patterns for TinyOS [C ] /Proceedings of the 2005 ACM SIGPLAN SIGBED Conference on Languages,Compilers and Tools for Embedded Systems(LCTES05)USA:ACM Press,2005:40-49.

[5]Tiny Microthreading Operating System TinyOS[Z].http://tinyos.millennium.berkeley.edu 2004.

[6]陳喜貞,王書茂.徐勇軍.無線傳感器網絡操作系統調度策略研究[EB/OL].中國科技論文在線.http://www.paper.edu.cn.

[7]羅曉華.支持無線網絡傳感器的γOS操作系統若干關鍵軟件技術的研究和實現 [D].浙江大學,2006.

[8]Cormac Duffy,Utz Roedig,John Herbert Cormac J.Sreenan.Adding Preemption t TinyOS[C].EmNets'97.2007:88-92.