TinyOS中多優先級任務隊列調度策略研究

馬文濤，李雙慶

重慶大學計算機學院，重慶 400044

TinyOS中多優先級任務隊列調度策略研究

馬文濤，李雙慶

重慶大學計算機學院，重慶 400044

1 引言

無線傳感器網絡[1]是由部署在監測區域內的大量廉價微型傳感器節點組成，通過無線通信的方式形成一種多跳的網絡系統，能夠通過協作實時監測、感知、和采集網絡分布區域內的各種環境或監測對象的信息，并對這些信息進行處理，從而獲取更詳盡而準確的信息。無線傳感器網絡操作系統（Wireless Sensor Network Operating System，WSNOS）是無線傳感器網絡節點的基本軟件環境，是眾多無線傳感器網絡應用開發的基礎，它的靈活性、高效性和實時性將直接影響到整個網絡的性能[2]。根據無線傳感器網絡節點操作系統的調度系統，調度策略可分為兩類，事件驅動單線程系統和多線程系統。作為事件驅動類型操作系統的代表，加州大學伯克利分校開發的TinyOS[3]是一個為網絡嵌入式系統定制的一個操作系統，TinyOS操作系統采用最基本的FCFS[4]（First Come First Service）調度策略；多線程系統則以MANTIS OS[5]為代表，MANTIS OS采用的是一種類UNIX的調度系統，它提供基于優先級的多線程調度和在同一優先級中時間片輪轉調度，兩類系統各有優劣。

隨著無線傳感器應用領域的不斷拓展，任務的數量和執行時間明顯增加，任務的實時性要求也大大增加，尤其是緊急情況下系統對網絡任務的響應。在實時環境中，實時性不足是TinyOS調度策略的一個重要缺陷，文獻[6]提出了基于最早截至時限優先的調度策略IS-EDF，有效改善了任務調度成功率，但在任務負載較重時難以保證關鍵任務的優先執行，同時它為每個任務分配一個堆棧空間，一定程度上增加了內存的開銷。文獻[7-8]提出了基于優先級任務調度算法來相對提高節點吞吐量以解決本地節點包過載問題。在對事件驅動單線程系統和多線程系統的優劣進行分析后，本文針對TinyOS的FCFS調度策略在實時環境應用中的不足，提出一種基于多優先級隊列調度策略，將任務隊列增加至三個優先級隊列，并引入搶占機制[9]，充分考慮任務執行時限和系統開銷，保證無線傳感器網絡實時任務及重要任務的優先運行，實驗結果表明基于多優先級隊列調度策略在不影響原來系統性能的情況下，有效提高了系統對重要任務的響應性能。

2 TinyOS內核任務調度策略

2.1 TinyOS任務事件驅動機制分析

TinyOS提供任務和事件的兩級調度[10]，任務按照先來先服務FCFS的原則，按照進入隊列的先后順序依次執行。任務在隊列中不能夠相互搶占，因此一旦任務開始執行，要運行到結束，只有當任務放棄CPU使用權的時候，才可以繼續執行下一個任務。硬件事件的執行是響應硬件的中斷，同時TinyOS把一些不需要在中斷服務程序中立即執行的代碼以函數的形式封裝成任務提交到任務隊列，它實際上是一種延遲計算機制，硬件中斷所產生的事件能夠打斷任務的運行。

圖1 TinyOS任務事件驅動機制

2.2 TinyOS調度策略的局限性

FCFS調度策略簡單易用，在TinyOS中設置一個任務隊列，調度任務時根據任務到達時刻進行調度，這種任務調度策略沒有對任務按照重要性或緊急性進行排列，會造成某些應用無法完成、短時間任務等待長時間任務和重要任務等待次要任務等問題。再加上任務之間相互平等，無法搶占，使得一些實時性要求較高的任務不能在截至期內得到處理，影響了系統的實時性。因此TinyOS無法保證重要緊急任務優先得到執行，導致任務丟失和通信吞吐率下降等問題，限制了TinyOS的應用。

3 一種基于多優先級隊列調度策略

為了改善現有TinyOS調度策略在實時環境應用中的不足，本文在TinyOS原有調度策略的基礎上，提出一種基于多優先級隊列調度策略。本調度算法分為任務準入控制器和任務調度器兩部分。相關定義如下：

假設任務集合為S={t1,t2,…,tn}，任務ti用(Pi,di,Ai,Ti,Ei,idi)描述，其中Ai為任務的提交時間；Ti為任務ti的周期；Ei表示任務ti的平均執行時間；Pi表示任務ti的隊列優先級；di表示任務ti的絕對截至時限；idi代表任務ti的編號，0≤idi≤254。

（1）任務優先級隊列

無論任務是實時任務還是非實時任務，都必須有任務隊列優先級，該參數決定任務所在優先級隊列，也表示了該任務的重要程度。基于多優先級隊列調度策略提供三個隊列優先級P1，P2，P3，如圖2，分別對應三個優先級隊列。

圖2 任務優先級隊列

圖2中P2和P3隊列中的任務按照FCFS調度策略進行調度，P1隊列針對實時要求嚴格的任務，任務按照時間因子由小至大順序排列[11-12]，表明任務重要性越高，任務越靠近隊首；P3則針對執行時間長的本地任務，對于軟實時任務可提高其優先級至P2，這樣就防止了本地任務長時間阻礙該類任務的執行。P1隊列中的任務在滿足搶占條件時可以搶占任何比其隊列優先級低的正在運行的任務，在實際應用中，將一個任務分配到多個優先級隊列將會導致更多的任務切換操作，因此基于多優先級隊列調度策略規定一個任務只能被分配到一個任務隊列中，即一個任務只有一個隊列優先級。

（2）時間因子

該參數只針對隊列中實時要求嚴格的任務，表示任務的重要和緊急程度，由任務的絕對截止時限來描述。時間因子越小，在該任務隊列中的優先級越高。若任務為非實時任務，則時間因子置為負數，以便與實時任務區分。

3.1 任務準入控制

當新任務tnew到來時候，根據以下兩個原則對任務進行準入判斷：

（2）若所有優先級高于新任務優先級的任務（包括高于新任務優先級的隊列中的任務和新任務所在任務隊列中的排列在新任務位置前的任務）執行時間之和大于任務周期Tnew，則拒絕任務tnew進入隊列。

其中，準入原則（1）是判斷隊列中是否已經存在該任務，若該任務已經存在，則拒絕其進入隊列；而原則（2）是針對循環周期性任務，在任務周期Tnew＞0時，若所有比其優先級高的任務執行時間之和大于等于其任務周期，則拒絕其進入隊列，這就意味著周期性任務只有在其周期內可以被調度時才可以進入隊列。對于非周期性任務，其周期Tnew在計算時被置為負數，入隊控制時不需要原則（2）的判斷。

非實時任務插隊調整：若新任務滿足準入原則，若隊列中存在任務的時間因子大于新任務時間因子，此時會發生插隊現象，即隊列中時間因子大的任務和非實時任務就會向隊尾移動。由于實時任務由絕對截至時限描述，新實時任務的時間因子會隨著提交時間參數的增大而增大，因此此前提交的實時任務最終會有機會得到運行。但是非實時任務時間因子初始化為負數，新實時任務到達時會一直被插隊，若插隊頻繁，則會造成非實時任務得不到調度，使其餓死，因此要對其進行插隊調整。為每個非實時任務ti設定一個參數Ci（初始為0），記錄任務被插隊次數，任務被插隊一次增加1，當Ci到達閾值C時，將任務時間因子dfi置為0，任務將不能被插隊，并最終能被執行。

算法1任務準入控制

若新任務所在隊列為非實時任務隊列，則在符合準入控制原則時將其直接插入隊列尾部，算法1所示任務準入控制流程是針對實時性要求較高的任務隊列P1中的任務入隊控制，首先判斷是否滿足準入原則（1），如果滿足（1）且任務為周期任務，再判斷是否滿足準入原則（2），如果任務滿足兩個原則，則根據其任務優先級，選擇相應的任務隊列，再根據時間因子插入相應位置，否則拒絕該任務的進入。

3.2 任務不可搶占原則

當有新任務進入任務隊列P1后，若新任務優先級比正在運行的任務優先級高，可能會發生任務搶占，進行上下文切換。上下文切換需要保存現場，會增加系統開銷，因此在設計調度策略時，要盡量減少上下文切換的次數。本調度策略在充分考慮減少系統開銷和上下文切換次數的情況下，設計兩個任務不可搶占原則，任務在滿足兩個原則其中之一的情況下就可以不進行任務的上下文切換。

（1）當新任務的隊列優先級和正在運行的任務的隊列優先級相同即Pnew=Pcur，并且不論新任務的時間因子dnew大小，都不會進行上下文的切換，而是直接將任務插入隊列的相應位置。

（2）使用e表示任務已經運行的時間，當新任務的隊列優先級高于正在執行的任務隊列優先級即Pnew=P1，Pnew＞Pcur，如果(Ecur-ecur)+Enew≥dnew-Anew，新任務可以搶占正在運行的任務，否則不可搶占。

上述原則表明，任務的搶占只能在不同任務隊列的任務間進行，只有在新任務的優先級隊列為可搶占隊列且比正在運行優先級高，并且滿足可搶占條件才可以進行搶占，這樣既保證了重要和緊急任務的實時性的同時，又減少了上下文切換的次數，從而減少了系統開銷。

任務優先級逆轉考慮：任務隊列P1可以搶占其他隊列正在運行的任務，這種情況下系統的資源訪問機制可能會造成優先級逆轉情況，即高優先級任務等待低優先級任務執行完畢后才能執行。為了避免發生優先級逆轉，本文采取優先級繼承方法，即當高優先級任務訪問被低優先級任務占用的資源時，將低優先級任務的隊列優先級提高至高優先級任務的隊列優先級，并將其置為隊列中為最高優先級任務即隊首任務，使其能夠快速優先執行完畢，將高優先級任務阻塞時間限制在一個比較小的時間間隔內，避免優先級逆轉情況的發生。

3.3 任務的調度

任務的調度要分兩種情況討論，第一種情況是當前任務執行完畢后的任務調度，此時若上下文切換次數不為0，則返回執行被打斷的任務并將上下文切換次數減1，若所有隊列都為空，系統進入睡眠節能狀態，否則任務調度器按照任務隊列優先級調度任務；另一種情況是在當前任務運行期間提交了更重要的任務，在可搶占隊列即P1隊列中，由準入控制器觸發調度事件，此時新提交任務若不滿足兩個不可搶占原則，則表明新提交任務需要搶占當前任務緊急執行，因此首先進行上下文的切換，然后調度提交的新任務，否則表明新提交任務滿足不可搶占原則，并繼續執行當前任務。

4 性能測試及結果分析

4.1 性能分析

（1）時間開銷

基于多優先級隊列調度策略時間開銷主要來自準入控制和任務調度的開銷，準入控制中原則（1）時間開銷為O(1)，原則（2）時間開銷為O(lp1+lp2+lp3)，lp1，lp2，lp3分別為三個隊列的對應長度。任務調度只需要調度隊列中最高優先級任務，所以其時間開銷為O(1)。因此基于多優先級隊列調度策略時間開銷為O(lp1+lp2+lp3)。當任務都為非實時任務時候，任務直接插入隊列尾部，此時基于多優先級隊列調度策略時間開銷和標準TinyOS調度時間開銷相同，其他情況下多優先級隊列調度策略的時間開銷會增加。

（2）內存占用

基于多優先級隊列調度策略的內存開銷主要來源于三部分，任務隊列存儲空間、任務隊列堆棧空間以及調度相關變量空間。其中任務隊列存儲空間為任務數×4 B，每個任務存儲空間比原來FCFS調度中每個任務占用空間增加3 B，任務之間最多可以搶占一次，所以增加一個堆棧空間（大小約40 B），在一般應用中系統中任務數為10個左右，此時基于多優先級隊列調度策略比標準TinyOS的FCFS調度多消耗大約80 B內存空間，占總內存空間2.05%，這表明沒有明顯增加系統內存開銷，傳統EDF調度策略中為每個任務分配一個堆棧空間，則堆棧空間大小增加任務數×40 B，很大程度上增加了系統對內存的需求。在對相關變量及堆棧空間進行統計后，如表1，在與現有的多線程系統MANTIS OS比較中，基于多優先級隊列調度策略內存開銷小于MANTIS OS內存開銷。

圖3 FCFS吞吐量

表1 內存開銷對比B

4.2 實驗測試

運用TOSSIM[13]進行仿真實驗，設計兩個針對Micaz平臺的驗證應用，對FCFS調度策略和基于多優先級調度策略在吞吐量和實時任務的響應等方面進行對比。

（1）在此應用中，在一個節點中設置三個任務，task1、task2、task3，分別分配在P1、P2、P3隊列中，每個任務每次向周圍三個特定節點發送一個數據包，數據包中包含原有隊列信息，發送頻率均為10 Hz，統計在60 s內的數據包總數并求得每秒發送數據包平均數據。

通過統計，由圖3、圖4和圖5對比顯示，FCFS調度策略沒有考慮任務重要性，將重要任務排列在隊列尾部，使得重要任務例如task1并沒有得到理想吞吐量，EDF調度策略將重要任務優先級提高并搶占正在運行的低優先級任務，但是低優先級任務執行機會極大降低，基于多優先級隊列調度策略中任務根據其重要程度分配不同隊列，高優先級隊列任務只有在滿足可搶占條件時搶占低優先級隊列中正在運行的任務，降低了低優先級任務被搶占幾率，增加了低優先級任務執行機會，并使得重要任務吞吐量明顯提高。

（2）在應用中設置三個節點如表2，分別為A、B、C節點，其中A節點向B節點發送數據包，發送頻率為8 Hz，B節點則負責轉發A節點發送的數據包到C節點，同時為B節點設置一個周期性本地任務，并設置為一般性任務，其觸發頻率8 Hz，執行時間為150 ms，目的是讓節點處于滿載狀態，C節點負責接收B節點轉發的數據包并統計接收數據包個數。

圖4 EDF調度策略吞吐量

圖5 基于多優先級隊列吞吐量

表2 節點任務設置及說明

圖6顯示了節點任務運行一段時間后在節點任務運行一段時間后的不同調度策略突發任務響應的對比，可以看出EDF調度策略和基于多優先級隊列調度策略可以對突發任務做出及時響應，而FCFS調度策略則按照到達順序對任務排列，嚴重影響了系統對突發任務的響應，通過統計分析A節點發送的數據包，B節點在時間內轉發的數據包和C節點接收到的數據包，可以發現使用FCFS策略時，B節點上接收數據包任務到來時被安排在隊列尾部，導致數據包的超時甚至丟失；EDF調度策略中突發任務截至時限小于其他任務截至時限，因此到來時搶占其他任務如本地任務優先執行，但是EDF調度策略復雜的計算和較多的上下文切換并不適用于無線傳感器網絡；基于多優先級隊列調度策略中，突發任務被分配在P1隊列中，在數據包到來時，接收數據包的任務在滿足可搶占條件時可以搶占正在執行的低優先級隊列中的任務優先執行，使數據包在有效時間內被正確處理，很好保證了系統對突發任務的及時響應，有效提高了系統的吞吐量和系統對重要任務的響應性能。

圖6 不同調度策略中突發任務響應對比

5 結束語

為了提高TinyOS在實時環境應用中的實時任務的響應速率，本文在TinyOS原有的調度策略基礎上，提出一種基于多優先級隊列調度策略，它充分考慮了任務的執行時間以及系統開銷，實驗結果表明，該調度策略在保持TinyOS原有調度策略性能的情況下，有效提高了系統對重要任務的響應性能，在任務負載較重情況下，響應性能的提高更加明顯。

[1]孫利民，李建中，陳渝，等.無線傳感器網絡[M].北京：清華大學出版社，2006.

[2]Hill J，Szewczyk R，Woo A，et al.System architecture directions for networked sensors[C]//9th Internatinal Conference Architectural Support for Programming Languages and Operating Systems.Cambridge，MA，United states：Association for Computing Machinery，2000.

[3]Levis P，Madden S，Polastre J，et al.TinyOS：an operating systemforwirelesssensornetworks[M]//WeberW，Rabaey J，Aarts E.Ambient Intelligence.New York，NY：Springer-Verlag，2005.

[4]Karlof C，Wagner D.Secure routing in wireless sensor networks：attacksandcountermeasures[C]//SensorNetwork Protocols and Applications，2003：113-127.

[5]Bhatti S，Carlson J，Dai H，et al.MANTIS OS：an embedded multithreaded operating system for wireless micro sensor platforms[C].[S.l.]：KluwerAcademicPublishers，2005：563-579.

[6]尹震宇，趙海，徐久強，等.無線傳感器網絡操作系統中搶占式任務調度策略[J].東北大學學報：自然科學版，2007，28（5）：652-655.

[7]Yan Z，Qianping W，Wei W，et al.Research on the prioritybased soft real-time task scheduling in TinyOS[C]//Information Technology and Computer Science，2009：562-565.

[8]宋風坤，陳滌.采用快速排隊算法的WSN任務調度策略研究[J].計算機工程與應用，2010，46（12）：115-117.

[9]Duffy C，Roedig U，Herbert J，et al.Adding preemption to TinyOS[C]//4th Workshop on Embedded Networked Sensors.Cork，Ireland：Association for Computing Machinery，2007：88-92.

[10]Gay D，Levis P，Culler D.Software design patterns for TinyOS[C]//2005 ACM SIGPLAN/SIGBED Conference on Languages，Compilers，and Tools for Embedded Systems.Chicago，IL，United States：Association for Computing Machinery，2005.

[11]沈卓煒.不可搶占式EDF調度算法的可調度性分析[J].計算機工程與應用，2006，42（9）：10-12.

[12]Liu C L，Layland J W.Scheduling algorithms for multiprogramming in a hard-real-time environment[J].Journal of The ACM，1973，20（1）：46-61.

[13]Levis P，Lee N，Welsh M，et al.TOSSIM：Accurate and scalable simulation of entire TinyOS applications[C]// ProceedingsoftheFirstInternationalConferenceon Embedded Networked Sensor Systems.Los Angeles，CA，United States：Association for Computing Machinery，2003.

MA Wentao，LI Shuangqing

College of Computer Science,Chongqing University,Chongqing 400044,China

Considering the deficiency that TinyOS FCFS scheduling strategy cannot timely response to important tasks,a scheduling strategy based on multi-level priority task queue is proposed and implemented on TinyOS.Multi-level priority task queue scheduling strategy expands original task queue from one to three priority queues and preemption mechanism is introduced,a task in the highest priority queue can preempt the task running in other queues only when it satisfies preemptive principles,task preemption only takes place between different queues,In this way the time of context switching decreases and important tasks can execute in time.Experiment results prove that this new scheduling strategy improves the response characteristic for important tasks of TinyOS efficiently without affecting the intrinsic performance of TinyOS. Key words：wireless sensor network;TinyOS;scheduling strategy

針對TinyOS先來先服務調度策略中重要任務不能及時響應的不足，提出一種基于多優先級任務隊列的調度策略。該調度策略將原來一個任務隊列增加為三個優先級隊列并引入搶占機制，最高優先級隊列中的任務在滿足搶占原則時才可以搶占其他隊列正在執行的任務，任務只能在不同隊列之間發生搶占，這樣既減少了上下文切換，又保證了重要任務的優先執行。實驗結果表明，該調度策略在不影響原有系統性能的情況下，提高了TinyOS對重要任務的響應性能。

無線傳感器網絡；TinyOS；調度策略

A

TP393

10.3778/j.issn.1002-8331.1212-0166

MA Wentao，LI Shuangqing.Research on multi-level priority task queue scheduling strategy in TinyOS.Computer Engineering and Applications,2014,50（22）：106-110.

國家自然科學基金（No.71102065）。

馬文濤（1988—），男，碩士研究生，主要研究領域為嵌入式系統、無線傳感器網絡；李雙慶（1969—），男，副教授，博士，主要研究領域為嵌入式系統開發、SOA/SOC、計算機網絡。E-mail：mwt0530@163.com

2012-12-13

2013-02-05

1002-8331（2014）22-0106-05

CNKI網絡優先出版：2013-03-13,http://www.cnki.net/kcms/detail/11.2127.TP.20130313.0955.020.html