基于優(yōu)先級(jí)可搶占式調(diào)度策略的設(shè)計(jì)

翟 月

（1、合肥工業(yè)大學(xué)，安徽 合肥 230009 2、安徽電子信息職業(yè)技術(shù)學(xué)院，安徽 蚌埠 233000）

1 設(shè)計(jì)基礎(chǔ)

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

1.1 TinyOS調(diào)度機(jī)制

事件驅(qū)動(dòng)的TinyOS采用兩級(jí)調(diào)度：任務(wù)和硬件事件處理。任務(wù)是一些可以被搶占的函數(shù)，一旦被調(diào)度，任務(wù)運(yùn)行完成彼此之間不能相互搶占。硬件事件處理被執(zhí)行去響應(yīng)硬件中斷，可以搶占任務(wù)的運(yùn)行或者其他硬件事件處理。TinyOS的任務(wù)調(diào)度隊(duì)列只是采用簡(jiǎn)單的先入先出算法。任務(wù)事件的調(diào)度過程如圖1所示。TinyOS的任務(wù)隊(duì)列如果為空，則進(jìn)入極低功耗的Sleep模式。當(dāng)被事件觸發(fā)后，在 TinyOS中發(fā)出信號(hào)的事件關(guān)聯(lián)的所有任務(wù)被迅速處理。當(dāng)這個(gè)事件和所有任務(wù)被處理完成，未被使用的CPU循環(huán)被置于睡眠狀態(tài)而不是積極尋找下一個(gè)活躍的事件。

1.2 TinyOS的局限性

盡管 TinyOS被廣泛使用，得到了認(rèn)可，但這并不意味著 TinyOS能適用于無(wú)線傳感器網(wǎng)絡(luò)所有的應(yīng)用場(chǎng)景。事實(shí)上，在某些場(chǎng)合TinyOS并不能工作得很好，而可能出現(xiàn)過載，導(dǎo)致任務(wù)丟失、通信吞吐量下降等問題：

1.2.1 某些任務(wù)執(zhí)行時(shí)間很長(zhǎng)，這時(shí)如果某些實(shí)時(shí)任務(wù)在該任務(wù)之后才進(jìn)入任務(wù)隊(duì)列，就會(huì)影響實(shí)時(shí)性；對(duì)于數(shù)據(jù)包的收發(fā)，就會(huì)影響波特率。

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

1.2.3 任務(wù)隊(duì)列中某個(gè)任務(wù)如果意外出現(xiàn)阻塞或異常時(shí)，會(huì)影響后續(xù)任務(wù)的運(yùn)行，甚至導(dǎo)致系統(tǒng)癱瘓。

2 基于優(yōu)先級(jí)可搶占式分級(jí)調(diào)度策略設(shè)計(jì)

為了滿足無(wú)線傳感器網(wǎng)絡(luò)要求，傳感器節(jié)點(diǎn)的設(shè)計(jì)必須是能量有效的。然而，能量有效性并不是傳感器網(wǎng)絡(luò)設(shè)計(jì)的唯一目標(biāo)。在特定的應(yīng)用環(huán)境下，實(shí)時(shí)的過程和感知信息的報(bào)告也是常常需要的。這樣，感知的數(shù)據(jù)從某個(gè)節(jié)點(diǎn)，通過多跳網(wǎng)絡(luò)，最終傳送到基站的過程中，我們可能需要保證一個(gè)盡可能長(zhǎng)的傳輸時(shí)間。

事件驅(qū)動(dòng)的操作系統(tǒng)被認(rèn)為是建立能量有效的傳感器網(wǎng)絡(luò)的最佳選擇，因?yàn)樗鼈冎恍枰苌俚膬?nèi)存和

處理資源。這樣，事件驅(qū)動(dòng)的操作系統(tǒng)TinyOS成為了當(dāng)前傳感器網(wǎng)絡(luò)操作系統(tǒng)的首選。事件驅(qū)動(dòng)的操作系統(tǒng)在任務(wù)實(shí)時(shí)性要求較高的環(huán)境下就不是很有效了。由于所有的任務(wù)都是按照次序順序執(zhí)行的，具有優(yōu)先級(jí)的重要的任務(wù)要保證在時(shí)限之內(nèi)被處理是不可能的。

基于優(yōu)先級(jí)的可搶占式分級(jí)調(diào)度策略結(jié)合了事件驅(qū)動(dòng)、分級(jí)調(diào)度和多線程的思想，將操作系統(tǒng)可處理的任務(wù)分為不同的優(yōu)先級(jí)別，高優(yōu)先級(jí)任務(wù)先得到響應(yīng)?？紤]到實(shí)時(shí)性要求嚴(yán)格的任務(wù)，搶占機(jī)制被引入到該調(diào)度系統(tǒng)中，即任務(wù)級(jí)別依次分為高優(yōu)先級(jí)可搶占、高優(yōu)先級(jí)不可搶占和一般優(yōu)先級(jí)。高優(yōu)先級(jí)可搶占任務(wù)能夠搶占當(dāng)前正在執(zhí)行的任務(wù)而先執(zhí)行；高優(yōu)先級(jí)不可搶占任務(wù)具有先

得到響應(yīng)的權(quán)利，但不對(duì)當(dāng)前正在執(zhí)行的任務(wù)進(jìn)行搶占；一般優(yōu)先級(jí)任務(wù)即對(duì)應(yīng)于一般Tiny OS任務(wù)。

我們使用一個(gè)基于組件的優(yōu)先級(jí)層次調(diào)度器（PL調(diào)度器）來(lái)代替TinyOS系統(tǒng)提供的標(biāo)準(zhǔn)的先入先出調(diào)度器。PL調(diào)度器可以被嵌入應(yīng)用程序中對(duì)任務(wù)首先執(zhí)行的情況來(lái)達(dá)到更好的控制。PL調(diào)度器提供了以下幾種不同的優(yōu)先級(jí)別：

（P1）高優(yōu)先級(jí)可搶占

（P2）高優(yōu)先級(jí)非可搶占

（P3）基本優(yōu)先級(jí)（標(biāo)準(zhǔn)TinyOS任務(wù)使用）

在每個(gè)層次中，任務(wù)按照先進(jìn)先出的方式進(jìn)行調(diào)度?；緝?yōu)先級(jí)層次的調(diào)度是必須實(shí)現(xiàn)的，因?yàn)樗械臉?biāo)準(zhǔn)TinyOS任務(wù)都將默認(rèn)在這個(gè)隊(duì)列中。相鄰的優(yōu)先級(jí)層次提供了一個(gè)不可搶占的高優(yōu)先級(jí)的隊(duì)列和一個(gè)可搶占的高優(yōu)先級(jí)隊(duì)列。這樣，這三個(gè)層次中的任意任務(wù)都能按照他們的優(yōu)先級(jí)進(jìn)行調(diào)度，但不會(huì)搶占正在執(zhí)行的任務(wù)，正如圖2所示。高優(yōu)先級(jí)可搶占任務(wù)隊(duì)列是用來(lái)調(diào)度搶占一般任務(wù)的。一個(gè)高優(yōu)先級(jí)可搶占的任務(wù)將會(huì)從優(yōu)先級(jí)低于它的任務(wù)層次中搶占任何正在運(yùn)行的任務(wù)，并且這些層次中的任何任務(wù)可以優(yōu)先于任何一個(gè)優(yōu)先級(jí)低于自身的任務(wù)而先得到響應(yīng)。

結(jié)合上述設(shè)計(jì)思想，設(shè)計(jì)出基于優(yōu)先級(jí)的可搶占式分級(jí)調(diào)度系統(tǒng)，實(shí)現(xiàn)面向調(diào)度器的線程以及分層調(diào)度系統(tǒng)的智能構(gòu)造算法。它實(shí)現(xiàn)了一個(gè)基于事件驅(qū)動(dòng)系統(tǒng)的多線程調(diào)度系統(tǒng)，其結(jié)構(gòu)如圖3所示。

某個(gè)組件通過配置一個(gè)優(yōu)先級(jí)任務(wù)接口到PL調(diào)度器組件中來(lái)指定一個(gè)優(yōu)先級(jí)任務(wù)，并執(zhí)行事件runTask()函數(shù)接口。這個(gè)程序在任務(wù)和調(diào)度器方面和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優(yōu)先級(jí)任務(wù)結(jié)構(gòu)

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優(yōu)先級(jí)調(diào)度器結(jié)構(gòu)

算法1給出了一個(gè)實(shí)現(xiàn)了的優(yōu)先級(jí)任務(wù)的例子。某個(gè)組件要使用優(yōu)先級(jí)任務(wù)，它就必須實(shí)現(xiàn)優(yōu)先級(jí)任務(wù)接口，并且指明任務(wù)的優(yōu)先級(jí)作為接口的參數(shù)（算法1，第2行）。這個(gè)接口提供了和基本任務(wù)語(yǔ)法post[task name]相同的postTask函數(shù)（算法1，第6行），和存儲(chǔ)任務(wù)功能的runtask事件處理器（算法1，第9行）。當(dāng)任務(wù)將要被調(diào)度執(zhí)行的時(shí)候，事件處理器由調(diào)度器激活。

每個(gè)任務(wù)都必須被配置到由PL調(diào)度器提供的五個(gè)帶參數(shù)的任務(wù)優(yōu)先級(jí)接口中去（算法2，第2-6行）。配置過程在某種程度上往往被普通優(yōu)先級(jí)任務(wù)組件簡(jiǎn)化了（算法1，第16行），它利用接口參數(shù)信息來(lái)確定任務(wù)的優(yōu)先級(jí)并且唯一的配置每個(gè)任務(wù)到合適的調(diào)度器接口中去。

3 系統(tǒng)性能分析

為了驗(yàn)證本文提出的這種調(diào)度算法的改進(jìn)效果，我們采用中科院計(jì)算所WSN課題組研發(fā)的GAINS節(jié)點(diǎn)作為實(shí)驗(yàn)平臺(tái)。

為了檢驗(yàn)分級(jí)調(diào)度算法的效果，我們把49個(gè)GAINS節(jié)點(diǎn)節(jié)點(diǎn)，每隔20m一個(gè)，部署在120m×120m的二維監(jiān)測(cè)區(qū)域，并對(duì)其通訊情況作了記錄、統(tǒng)計(jì)。

3.1 實(shí)時(shí)性

我們使用了三種不同優(yōu)先級(jí)別的任務(wù)，T0（轉(zhuǎn)發(fā)接收到的數(shù)據(jù)包），T1（接收待轉(zhuǎn)發(fā)的路由數(shù)據(jù)包），T2（處理本地?cái)?shù)據(jù)并將其發(fā)送），分別對(duì)應(yīng)高優(yōu)先級(jí)可搶占任務(wù)，高優(yōu)先級(jí)非可搶占任務(wù)和一般任務(wù)。三種任務(wù)依次按照T0，T1，T2的順序每隔時(shí)間t循環(huán)發(fā)送，而每個(gè)任務(wù)的執(zhí)行時(shí)間為2t。我們對(duì)比了分級(jí)調(diào)度算法和TinyOS的響應(yīng)情況，其實(shí)時(shí)任務(wù)響應(yīng)情況如圖4所示 ：

圖4 實(shí)時(shí)任務(wù)斷響應(yīng)比較

由此可以看出，分級(jí)調(diào)度策略能夠?qū)?shí)時(shí)任務(wù)及時(shí)響應(yīng)，而TinyOS任務(wù)由于嚴(yán)格按照次序調(diào)度，實(shí)時(shí)任務(wù)不能得到優(yōu)先響應(yīng)。

3.2 可調(diào)度性

我們對(duì)分級(jí)調(diào)度算法和TinyOS在通訊中的丟包率做了統(tǒng)計(jì)，發(fā)現(xiàn)隨著任務(wù)數(shù)量的增多，任務(wù)數(shù)據(jù)包會(huì)發(fā)生丟失。分級(jí)調(diào)度中為每種任務(wù)分配單獨(dú)的隊(duì)列，且實(shí)時(shí)任務(wù)能夠及時(shí)得到響應(yīng)，所以實(shí)時(shí)任務(wù)數(shù)據(jù)包的丟失率很低。而TinyOS中并不能對(duì)實(shí)時(shí)任務(wù)進(jìn)行區(qū)別處理，從而不能保證實(shí)時(shí)任務(wù)的安全性。實(shí)時(shí)任務(wù)丟包率和執(zhí)行時(shí)間之間的關(guān)系如圖5所示：

由此可見，分級(jí)調(diào)度系統(tǒng)始終能滿足任務(wù)集可調(diào)度性。TinyOS由于其不可搶占性，任務(wù)集可調(diào)度性隨利用率上升而下降。

圖5 可調(diào)度性比較

3.3 靈活性

TinyOS，Mantis OS，SOS，Contiki均使用固定的調(diào)度系統(tǒng)，沒有提供調(diào)度系統(tǒng)的定制機(jī)制。分級(jí)調(diào)度器的構(gòu)造隨傳感器網(wǎng)絡(luò)應(yīng)用環(huán)境的不同可以很方便的進(jìn)行變化。在實(shí)時(shí)要求低的環(huán)境下，可以退化為TinyOS的完全非搶占調(diào)度隊(duì)列，所需子調(diào)度器數(shù)量為1。在實(shí)時(shí)要求高的情況，則構(gòu)造出滿足實(shí)時(shí)要求的可搶占層次調(diào)度體系，各子調(diào)度器能夠采用不同的調(diào)度策略，根據(jù)實(shí)際應(yīng)用兼顧實(shí)時(shí)性與內(nèi)存空間限制的要求，是一個(gè)靈活有效的調(diào)度體系。

3.4 資源消耗

TinyOS中僅需在內(nèi)存中分配一個(gè)任務(wù)隊(duì)列，而分級(jí)調(diào)度策略根據(jù)不同的應(yīng)用需要配置2-4個(gè)任務(wù)隊(duì)列，需要更多的內(nèi)存資源。在能量消耗方面，雖然都采用了事件驅(qū)動(dòng)機(jī)制，但是TinyOS中任務(wù)是依次執(zhí)行，而分級(jí)調(diào)度中存在搶占，因此會(huì)出現(xiàn)內(nèi)容交換，會(huì)增加能耗。因此，相對(duì)于TinyOS來(lái)說，分級(jí)調(diào)度策略會(huì)消耗更多的能量。與MANTIS OS等多線程調(diào)度系統(tǒng)來(lái)說，分級(jí)調(diào)度的能量消耗又會(huì)比較少。

本實(shí)驗(yàn)基于TOSSIM仿真環(huán)境來(lái)比較原有Tiny OS調(diào)度算法和改進(jìn)后分級(jí)調(diào)度算法的節(jié)點(diǎn)能量消耗,通過模擬無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)運(yùn)行并結(jié)合Power-TOSSIM來(lái)監(jiān)控節(jié)點(diǎn)的能耗。我們每隔5 s對(duì)數(shù)據(jù)進(jìn)行統(tǒng)計(jì),圖表示的是網(wǎng)絡(luò)中一個(gè)節(jié)點(diǎn)每2 s的能量消耗。

從圖6中可以看出,采用分級(jí)調(diào)度算法所用的能量要略高于原有Tiny OS算法,這是因?yàn)楦倪M(jìn)的算法要進(jìn)行時(shí)限的計(jì)算,系統(tǒng)開銷相對(duì)大一些,但平均所耗能量也只比原有增加4%左右,仍在可接受范圍內(nèi)。

圖6 節(jié)點(diǎn)能量消耗比較

總之，分級(jí)調(diào)度策略不能在每個(gè)方面都更加優(yōu)秀，它是在各個(gè)性能方面根據(jù)實(shí)際需求做出一個(gè)平衡的方案。

4 總結(jié)

本文以一種典型的無(wú)線傳感器網(wǎng)絡(luò)操作系統(tǒng)--TinyOS為研究對(duì)象，對(duì)其任務(wù)調(diào)度機(jī)制進(jìn)行了分析，并指出了其特點(diǎn)和不足，進(jìn)而提出了一種基于優(yōu)先級(jí)的可搶占式分級(jí)調(diào)度策略。并通過仿真實(shí)驗(yàn)對(duì)改進(jìn)前后調(diào)度策略進(jìn)行了比較分析。實(shí)驗(yàn)結(jié)果表明，該改進(jìn)方案能有效提高系統(tǒng)的實(shí)時(shí)性和可調(diào)度性，不失為一種可行的方案。

[1]李建中,高宏.無(wú)線傳感器網(wǎng)絡(luò)的研究進(jìn)展[J].計(jì)算機(jī)研究與發(fā)展,2008,45(1):1-15.

[2]孫利民,李建中,陳渝,朱紅松.無(wú)線傳感器網(wǎng)絡(luò)[M].北京:清華大學(xué)出版社,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]陳喜貞,王書茂.徐勇軍.無(wú)線傳感器網(wǎng)絡(luò)操作系統(tǒng)調(diào)度策略研究[EB/OL].中國(guó)科技論文在線.http://www.paper.edu.cn.

[7]羅曉華.支持無(wú)線網(wǎng)絡(luò)傳感器的γOS操作系統(tǒng)若干關(guān)鍵軟件技術(shù)的研究和實(shí)現(xiàn) [D].浙江大學(xué),2006.

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