馬文濤，李雙慶

重慶大學(xué)計(jì)算機(jī)學(xué)院，重慶 400044

TinyOS中多優(yōu)先級(jí)任務(wù)隊(duì)列調(diào)度策略研究

馬文濤，李雙慶

重慶大學(xué)計(jì)算機(jī)學(xué)院，重慶 400044

1 引言

無(wú)線傳感器網(wǎng)絡(luò)[1]是由部署在監(jiān)測(cè)區(qū)域內(nèi)的大量廉價(jià)微型傳感器節(jié)點(diǎn)組成，通過(guò)無(wú)線通信的方式形成一種多跳的網(wǎng)絡(luò)系統(tǒng)，能夠通過(guò)協(xié)作實(shí)時(shí)監(jiān)測(cè)、感知、和采集網(wǎng)絡(luò)分布區(qū)域內(nèi)的各種環(huán)境或監(jiān)測(cè)對(duì)象的信息，并對(duì)這些信息進(jìn)行處理，從而獲取更詳盡而準(zhǔn)確的信息。無(wú)線傳感器網(wǎng)絡(luò)操作系統(tǒng)（Wireless Sensor Network Operating System，WSNOS）是無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的基本軟件環(huán)境，是眾多無(wú)線傳感器網(wǎng)絡(luò)應(yīng)用開發(fā)的基礎(chǔ)，它的靈活性、高效性和實(shí)時(shí)性將直接影響到整個(gè)網(wǎng)絡(luò)的性能[2]。根據(jù)無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)操作系統(tǒng)的調(diào)度系統(tǒng)，調(diào)度策略可分為兩類，事件驅(qū)動(dòng)單線程系統(tǒng)和多線程系統(tǒng)。作為事件驅(qū)動(dòng)類型操作系統(tǒng)的代表，加州大學(xué)伯克利分校開發(fā)的TinyOS[3]是一個(gè)為網(wǎng)絡(luò)嵌入式系統(tǒng)定制的一個(gè)操作系統(tǒng)，TinyOS操作系統(tǒng)采用最基本的FCFS[4]（First Come First Service）調(diào)度策略；多線程系統(tǒng)則以MANTIS OS[5]為代表，MANTIS OS采用的是一種類UNIX的調(diào)度系統(tǒng)，它提供基于優(yōu)先級(jí)的多線程調(diào)度和在同一優(yōu)先級(jí)中時(shí)間片輪轉(zhuǎn)調(diào)度，兩類系統(tǒng)各有優(yōu)劣。

隨著無(wú)線傳感器應(yīng)用領(lǐng)域的不斷拓展，任務(wù)的數(shù)量和執(zhí)行時(shí)間明顯增加，任務(wù)的實(shí)時(shí)性要求也大大增加，尤其是緊急情況下系統(tǒng)對(duì)網(wǎng)絡(luò)任務(wù)的響應(yīng)。在實(shí)時(shí)環(huán)境中，實(shí)時(shí)性不足是TinyOS調(diào)度策略的一個(gè)重要缺陷，文獻(xiàn)[6]提出了基于最早截至?xí)r限優(yōu)先的調(diào)度策略IS-EDF，有效改善了任務(wù)調(diào)度成功率，但在任務(wù)負(fù)載較重時(shí)難以保證關(guān)鍵任務(wù)的優(yōu)先執(zhí)行，同時(shí)它為每個(gè)任務(wù)分配一個(gè)堆?？臻g，一定程度上增加了內(nèi)存的開銷。文獻(xiàn)[7-8]提出了基于優(yōu)先級(jí)任務(wù)調(diào)度算法來(lái)相對(duì)提高節(jié)點(diǎn)吞吐量以解決本地節(jié)點(diǎn)包過(guò)載問(wèn)題。在對(duì)事件驅(qū)動(dòng)單線程系統(tǒng)和多線程系統(tǒng)的優(yōu)劣進(jìn)行分析后，本文針對(duì)TinyOS的FCFS調(diào)度策略在實(shí)時(shí)環(huán)境應(yīng)用中的不足，提出一種基于多優(yōu)先級(jí)隊(duì)列調(diào)度策略，將任務(wù)隊(duì)列增加至三個(gè)優(yōu)先級(jí)隊(duì)列，并引入搶占機(jī)制[9]，充分考慮任務(wù)執(zhí)行時(shí)限和系統(tǒng)開銷，保證無(wú)線傳感器網(wǎng)絡(luò)實(shí)時(shí)任務(wù)及重要任務(wù)的優(yōu)先運(yùn)行，實(shí)驗(yàn)結(jié)果表明基于多優(yōu)先級(jí)隊(duì)列調(diào)度策略在不影響原來(lái)系統(tǒng)性能的情況下，有效提高了系統(tǒng)對(duì)重要任務(wù)的響應(yīng)性能。

2 TinyOS內(nèi)核任務(wù)調(diào)度策略

2.1 TinyOS任務(wù)事件驅(qū)動(dòng)機(jī)制分析

TinyOS提供任務(wù)和事件的兩級(jí)調(diào)度[10]，任務(wù)按照先來(lái)先服務(wù)FCFS的原則，按照進(jìn)入隊(duì)列的先后順序依次執(zhí)行。任務(wù)在隊(duì)列中不能夠相互搶占，因此一旦任務(wù)開始執(zhí)行，要運(yùn)行到結(jié)束，只有當(dāng)任務(wù)放棄CPU使用權(quán)的時(shí)候，才可以繼續(xù)執(zhí)行下一個(gè)任務(wù)。硬件事件的執(zhí)行是響應(yīng)硬件的中斷，同時(shí)TinyOS把一些不需要在中斷服務(wù)程序中立即執(zhí)行的代碼以函數(shù)的形式封裝成任務(wù)提交到任務(wù)隊(duì)列，它實(shí)際上是一種延遲計(jì)算機(jī)制，硬件中斷所產(chǎn)生的事件能夠打斷任務(wù)的運(yùn)行。

圖1 TinyOS任務(wù)事件驅(qū)動(dòng)機(jī)制

2.2 TinyOS調(diào)度策略的局限性

FCFS調(diào)度策略簡(jiǎn)單易用，在TinyOS中設(shè)置一個(gè)任務(wù)隊(duì)列，調(diào)度任務(wù)時(shí)根據(jù)任務(wù)到達(dá)時(shí)刻進(jìn)行調(diào)度，這種任務(wù)調(diào)度策略沒(méi)有對(duì)任務(wù)按照重要性或緊急性進(jìn)行排列，會(huì)造成某些應(yīng)用無(wú)法完成、短時(shí)間任務(wù)等待長(zhǎng)時(shí)間任務(wù)和重要任務(wù)等待次要任務(wù)等問(wèn)題。再加上任務(wù)之間相互平等，無(wú)法搶占，使得一些實(shí)時(shí)性要求較高的任務(wù)不能在截至期內(nèi)得到處理，影響了系統(tǒng)的實(shí)時(shí)性。因此TinyOS無(wú)法保證重要緊急任務(wù)優(yōu)先得到執(zhí)行，導(dǎo)致任務(wù)丟失和通信吞吐率下降等問(wèn)題，限制了TinyOS的應(yīng)用。

3 一種基于多優(yōu)先級(jí)隊(duì)列調(diào)度策略

為了改善現(xiàn)有TinyOS調(diào)度策略在實(shí)時(shí)環(huán)境應(yīng)用中的不足，本文在TinyOS原有調(diào)度策略的基礎(chǔ)上，提出一種基于多優(yōu)先級(jí)隊(duì)列調(diào)度策略。本調(diào)度算法分為任務(wù)準(zhǔn)入控制器和任務(wù)調(diào)度器兩部分。相關(guān)定義如下：

假設(shè)任務(wù)集合為S={t1,t2,…,tn}，任務(wù)ti用(Pi,di,Ai,Ti,Ei,idi)描述，其中Ai為任務(wù)的提交時(shí)間；Ti為任務(wù)ti的周期；Ei表示任務(wù)ti的平均執(zhí)行時(shí)間；Pi表示任務(wù)ti的隊(duì)列優(yōu)先級(jí)；di表示任務(wù)ti的絕對(duì)截至?xí)r限；idi代表任務(wù)ti的編號(hào)，0≤idi≤254。

（1）任務(wù)優(yōu)先級(jí)隊(duì)列

無(wú)論任務(wù)是實(shí)時(shí)任務(wù)還是非實(shí)時(shí)任務(wù)，都必須有任務(wù)隊(duì)列優(yōu)先級(jí)，該參數(shù)決定任務(wù)所在優(yōu)先級(jí)隊(duì)列，也表示了該任務(wù)的重要程度?；诙鄡?yōu)先級(jí)隊(duì)列調(diào)度策略提供三個(gè)隊(duì)列優(yōu)先級(jí)P1，P2，P3，如圖2，分別對(duì)應(yīng)三個(gè)優(yōu)先級(jí)隊(duì)列。

圖2 任務(wù)優(yōu)先級(jí)隊(duì)列

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

（2）時(shí)間因子

該參數(shù)只針對(duì)隊(duì)列中實(shí)時(shí)要求嚴(yán)格的任務(wù)，表示任務(wù)的重要和緊急程度，由任務(wù)的絕對(duì)截止時(shí)限來(lái)描述。時(shí)間因子越小，在該任務(wù)隊(duì)列中的優(yōu)先級(jí)越高。若任務(wù)為非實(shí)時(shí)任務(wù)，則時(shí)間因子置為負(fù)數(shù)，以便與實(shí)時(shí)任務(wù)區(qū)分。

3.1 任務(wù)準(zhǔn)入控制

當(dāng)新任務(wù)tnew到來(lái)時(shí)候，根據(jù)以下兩個(gè)原則對(duì)任務(wù)進(jìn)行準(zhǔn)入判斷：

（2）若所有優(yōu)先級(jí)高于新任務(wù)優(yōu)先級(jí)的任務(wù)（包括高于新任務(wù)優(yōu)先級(jí)的隊(duì)列中的任務(wù)和新任務(wù)所在任務(wù)隊(duì)列中的排列在新任務(wù)位置前的任務(wù)）執(zhí)行時(shí)間之和大于任務(wù)周期Tnew，則拒絕任務(wù)tnew進(jìn)入隊(duì)列。

其中，準(zhǔn)入原則（1）是判斷隊(duì)列中是否已經(jīng)存在該任務(wù)，若該任務(wù)已經(jīng)存在，則拒絕其進(jìn)入隊(duì)列；而原則（2）是針對(duì)循環(huán)周期性任務(wù)，在任務(wù)周期Tnew＞0時(shí)，若所有比其優(yōu)先級(jí)高的任務(wù)執(zhí)行時(shí)間之和大于等于其任務(wù)周期，則拒絕其進(jìn)入隊(duì)列，這就意味著周期性任務(wù)只有在其周期內(nèi)可以被調(diào)度時(shí)才可以進(jìn)入隊(duì)列。對(duì)于非周期性任務(wù)，其周期Tnew在計(jì)算時(shí)被置為負(fù)數(shù)，入隊(duì)控制時(shí)不需要原則（2）的判斷。

非實(shí)時(shí)任務(wù)插隊(duì)調(diào)整：若新任務(wù)滿足準(zhǔn)入原則，若隊(duì)列中存在任務(wù)的時(shí)間因子大于新任務(wù)時(shí)間因子，此時(shí)會(huì)發(fā)生插隊(duì)現(xiàn)象，即隊(duì)列中時(shí)間因子大的任務(wù)和非實(shí)時(shí)任務(wù)就會(huì)向隊(duì)尾移動(dòng)。由于實(shí)時(shí)任務(wù)由絕對(duì)截至?xí)r限描述，新實(shí)時(shí)任務(wù)的時(shí)間因子會(huì)隨著提交時(shí)間參數(shù)的增大而增大，因此此前提交的實(shí)時(shí)任務(wù)最終會(huì)有機(jī)會(huì)得到運(yùn)行。但是非實(shí)時(shí)任務(wù)時(shí)間因子初始化為負(fù)數(shù)，新實(shí)時(shí)任務(wù)到達(dá)時(shí)會(huì)一直被插隊(duì)，若插隊(duì)頻繁，則會(huì)造成非實(shí)時(shí)任務(wù)得不到調(diào)度，使其餓死，因此要對(duì)其進(jìn)行插隊(duì)調(diào)整。為每個(gè)非實(shí)時(shí)任務(wù)ti設(shè)定一個(gè)參數(shù)Ci（初始為0），記錄任務(wù)被插隊(duì)次數(shù)，任務(wù)被插隊(duì)一次增加1，當(dāng)Ci到達(dá)閾值C時(shí)，將任務(wù)時(shí)間因子dfi置為0，任務(wù)將不能被插隊(duì)，并最終能被執(zhí)行。

算法1任務(wù)準(zhǔn)入控制

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

3.2 任務(wù)不可搶占原則

當(dāng)有新任務(wù)進(jìn)入任務(wù)隊(duì)列P1后，若新任務(wù)優(yōu)先級(jí)比正在運(yùn)行的任務(wù)優(yōu)先級(jí)高，可能會(huì)發(fā)生任務(wù)搶占，進(jìn)行上下文切換。上下文切換需要保存現(xiàn)場(chǎng)，會(huì)增加系統(tǒng)開銷，因此在設(shè)計(jì)調(diào)度策略時(shí)，要盡量減少上下文切換的次數(shù)。本調(diào)度策略在充分考慮減少系統(tǒng)開銷和上下文切換次數(shù)的情況下，設(shè)計(jì)兩個(gè)任務(wù)不可搶占原則，任務(wù)在滿足兩個(gè)原則其中之一的情況下就可以不進(jìn)行任務(wù)的上下文切換。

（1）當(dāng)新任務(wù)的隊(duì)列優(yōu)先級(jí)和正在運(yùn)行的任務(wù)的隊(duì)列優(yōu)先級(jí)相同即Pnew=Pcur，并且不論新任務(wù)的時(shí)間因子dnew大小，都不會(huì)進(jìn)行上下文的切換，而是直接將任務(wù)插入隊(duì)列的相應(yīng)位置。

（2）使用e表示任務(wù)已經(jīng)運(yùn)行的時(shí)間，當(dāng)新任務(wù)的隊(duì)列優(yōu)先級(jí)高于正在執(zhí)行的任務(wù)隊(duì)列優(yōu)先級(jí)即Pnew=P1，Pnew＞Pcur，如果(Ecur-ecur)+Enew≥dnew-Anew，新任務(wù)可以搶占正在運(yùn)行的任務(wù)，否則不可搶占。

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

任務(wù)優(yōu)先級(jí)逆轉(zhuǎn)考慮：任務(wù)隊(duì)列P1可以搶占其他隊(duì)列正在運(yùn)行的任務(wù)，這種情況下系統(tǒng)的資源訪問(wèn)機(jī)制可能會(huì)造成優(yōu)先級(jí)逆轉(zhuǎn)情況，即高優(yōu)先級(jí)任務(wù)等待低優(yōu)先級(jí)任務(wù)執(zhí)行完畢后才能執(zhí)行。為了避免發(fā)生優(yōu)先級(jí)逆轉(zhuǎn)，本文采取優(yōu)先級(jí)繼承方法，即當(dāng)高優(yōu)先級(jí)任務(wù)訪問(wèn)被低優(yōu)先級(jí)任務(wù)占用的資源時(shí)，將低優(yōu)先級(jí)任務(wù)的隊(duì)列優(yōu)先級(jí)提高至高優(yōu)先級(jí)任務(wù)的隊(duì)列優(yōu)先級(jí)，并將其置為隊(duì)列中為最高優(yōu)先級(jí)任務(wù)即隊(duì)首任務(wù)，使其能夠快速優(yōu)先執(zhí)行完畢，將高優(yōu)先級(jí)任務(wù)阻塞時(shí)間限制在一個(gè)比較小的時(shí)間間隔內(nèi)，避免優(yōu)先級(jí)逆轉(zhuǎn)情況的發(fā)生。

3.3 任務(wù)的調(diào)度

任務(wù)的調(diào)度要分兩種情況討論，第一種情況是當(dāng)前任務(wù)執(zhí)行完畢后的任務(wù)調(diào)度，此時(shí)若上下文切換次數(shù)不為0，則返回執(zhí)行被打斷的任務(wù)并將上下文切換次數(shù)減1，若所有隊(duì)列都為空，系統(tǒng)進(jìn)入睡眠節(jié)能狀態(tài)，否則任務(wù)調(diào)度器按照任務(wù)隊(duì)列優(yōu)先級(jí)調(diào)度任務(wù)；另一種情況是在當(dāng)前任務(wù)運(yùn)行期間提交了更重要的任務(wù)，在可搶占隊(duì)列即P1隊(duì)列中，由準(zhǔn)入控制器觸發(fā)調(diào)度事件，此時(shí)新提交任務(wù)若不滿足兩個(gè)不可搶占原則，則表明新提交任務(wù)需要搶占當(dāng)前任務(wù)緊急執(zhí)行，因此首先進(jìn)行上下文的切換，然后調(diào)度提交的新任務(wù)，否則表明新提交任務(wù)滿足不可搶占原則，并繼續(xù)執(zhí)行當(dāng)前任務(wù)。

4 性能測(cè)試及結(jié)果分析

4.1 性能分析

（1）時(shí)間開銷

基于多優(yōu)先級(jí)隊(duì)列調(diào)度策略時(shí)間開銷主要來(lái)自準(zhǔn)入控制和任務(wù)調(diào)度的開銷，準(zhǔn)入控制中原則（1）時(shí)間開銷為O(1)，原則（2）時(shí)間開銷為O(lp1+lp2+lp3)，lp1，lp2，lp3分別為三個(gè)隊(duì)列的對(duì)應(yīng)長(zhǎng)度。任務(wù)調(diào)度只需要調(diào)度隊(duì)列中最高優(yōu)先級(jí)任務(wù)，所以其時(shí)間開銷為O(1)。因此基于多優(yōu)先級(jí)隊(duì)列調(diào)度策略時(shí)間開銷為O(lp1+lp2+lp3)。當(dāng)任務(wù)都為非實(shí)時(shí)任務(wù)時(shí)候，任務(wù)直接插入隊(duì)列尾部，此時(shí)基于多優(yōu)先級(jí)隊(duì)列調(diào)度策略時(shí)間開銷和標(biāo)準(zhǔn)TinyOS調(diào)度時(shí)間開銷相同，其他情況下多優(yōu)先級(jí)隊(duì)列調(diào)度策略的時(shí)間開銷會(huì)增加。

（2）內(nèi)存占用

基于多優(yōu)先級(jí)隊(duì)列調(diào)度策略的內(nèi)存開銷主要來(lái)源于三部分，任務(wù)隊(duì)列存儲(chǔ)空間、任務(wù)隊(duì)列堆棧空間以及調(diào)度相關(guān)變量空間。其中任務(wù)隊(duì)列存儲(chǔ)空間為任務(wù)數(shù)×4 B，每個(gè)任務(wù)存儲(chǔ)空間比原來(lái)FCFS調(diào)度中每個(gè)任務(wù)占用空間增加3 B，任務(wù)之間最多可以搶占一次，所以增加一個(gè)堆棧空間（大小約40 B），在一般應(yīng)用中系統(tǒng)中任務(wù)數(shù)為10個(gè)左右，此時(shí)基于多優(yōu)先級(jí)隊(duì)列調(diào)度策略比標(biāo)準(zhǔn)TinyOS的FCFS調(diào)度多消耗大約80 B內(nèi)存空間，占總內(nèi)存空間2.05%，這表明沒(méi)有明顯增加系統(tǒng)內(nèi)存開銷，傳統(tǒng)EDF調(diào)度策略中為每個(gè)任務(wù)分配一個(gè)堆?？臻g，則堆棧空間大小增加任務(wù)數(shù)×40 B，很大程度上增加了系統(tǒng)對(duì)內(nèi)存的需求。在對(duì)相關(guān)變量及堆棧空間進(jìn)行統(tǒng)計(jì)后，如表1，在與現(xiàn)有的多線程系統(tǒng)MANTIS OS比較中，基于多優(yōu)先級(jí)隊(duì)列調(diào)度策略內(nèi)存開銷小于MANTIS OS內(nèi)存開銷。

圖3 FCFS吞吐量

表1 內(nèi)存開銷對(duì)比B

4.2 實(shí)驗(yàn)測(cè)試

運(yùn)用TOSSIM[13]進(jìn)行仿真實(shí)驗(yàn)，設(shè)計(jì)兩個(gè)針對(duì)Micaz平臺(tái)的驗(yàn)證應(yīng)用，對(duì)FCFS調(diào)度策略和基于多優(yōu)先級(jí)調(diào)度策略在吞吐量和實(shí)時(shí)任務(wù)的響應(yīng)等方面進(jìn)行對(duì)比。

（1）在此應(yīng)用中，在一個(gè)節(jié)點(diǎn)中設(shè)置三個(gè)任務(wù)，task1、task2、task3，分別分配在P1、P2、P3隊(duì)列中，每個(gè)任務(wù)每次向周圍三個(gè)特定節(jié)點(diǎn)發(fā)送一個(gè)數(shù)據(jù)包，數(shù)據(jù)包中包含原有隊(duì)列信息，發(fā)送頻率均為10 Hz，統(tǒng)計(jì)在60 s內(nèi)的數(shù)據(jù)包總數(shù)并求得每秒發(fā)送數(shù)據(jù)包平均數(shù)據(jù)。

通過(guò)統(tǒng)計(jì)，由圖3、圖4和圖5對(duì)比顯示，F(xiàn)CFS調(diào)度策略沒(méi)有考慮任務(wù)重要性，將重要任務(wù)排列在隊(duì)列尾部，使得重要任務(wù)例如task1并沒(méi)有得到理想吞吐量，EDF調(diào)度策略將重要任務(wù)優(yōu)先級(jí)提高并搶占正在運(yùn)行的低優(yōu)先級(jí)任務(wù)，但是低優(yōu)先級(jí)任務(wù)執(zhí)行機(jī)會(huì)極大降低，基于多優(yōu)先級(jí)隊(duì)列調(diào)度策略中任務(wù)根據(jù)其重要程度分配不同隊(duì)列，高優(yōu)先級(jí)隊(duì)列任務(wù)只有在滿足可搶占條件時(shí)搶占低優(yōu)先級(jí)隊(duì)列中正在運(yùn)行的任務(wù)，降低了低優(yōu)先級(jí)任務(wù)被搶占幾率，增加了低優(yōu)先級(jí)任務(wù)執(zhí)行機(jī)會(huì)，并使得重要任務(wù)吞吐量明顯提高。

（2）在應(yīng)用中設(shè)置三個(gè)節(jié)點(diǎn)如表2，分別為A、B、C節(jié)點(diǎn)，其中A節(jié)點(diǎn)向B節(jié)點(diǎn)發(fā)送數(shù)據(jù)包，發(fā)送頻率為8 Hz，B節(jié)點(diǎn)則負(fù)責(zé)轉(zhuǎn)發(fā)A節(jié)點(diǎn)發(fā)送的數(shù)據(jù)包到C節(jié)點(diǎn)，同時(shí)為B節(jié)點(diǎn)設(shè)置一個(gè)周期性本地任務(wù)，并設(shè)置為一般性任務(wù)，其觸發(fā)頻率8 Hz，執(zhí)行時(shí)間為150 ms，目的是讓節(jié)點(diǎn)處于滿載狀態(tài)，C節(jié)點(diǎn)負(fù)責(zé)接收B節(jié)點(diǎn)轉(zhuǎn)發(fā)的數(shù)據(jù)包并統(tǒng)計(jì)接收數(shù)據(jù)包個(gè)數(shù)。

圖4 EDF調(diào)度策略吞吐量

圖5 基于多優(yōu)先級(jí)隊(duì)列吞吐量

表2 節(jié)點(diǎn)任務(wù)設(shè)置及說(shuō)明

圖6顯示了節(jié)點(diǎn)任務(wù)運(yùn)行一段時(shí)間后在節(jié)點(diǎn)任務(wù)運(yùn)行一段時(shí)間后的不同調(diào)度策略突發(fā)任務(wù)響應(yīng)的對(duì)比，可以看出EDF調(diào)度策略和基于多優(yōu)先級(jí)隊(duì)列調(diào)度策略可以對(duì)突發(fā)任務(wù)做出及時(shí)響應(yīng)，而FCFS調(diào)度策略則按照到達(dá)順序?qū)θ蝿?wù)排列，嚴(yán)重影響了系統(tǒng)對(duì)突發(fā)任務(wù)的響應(yīng)，通過(guò)統(tǒng)計(jì)分析A節(jié)點(diǎn)發(fā)送的數(shù)據(jù)包，B節(jié)點(diǎn)在時(shí)間內(nèi)轉(zhuǎn)發(fā)的數(shù)據(jù)包和C節(jié)點(diǎn)接收到的數(shù)據(jù)包，可以發(fā)現(xiàn)使用FCFS策略時(shí)，B節(jié)點(diǎn)上接收數(shù)據(jù)包任務(wù)到來(lái)時(shí)被安排在隊(duì)列尾部，導(dǎo)致數(shù)據(jù)包的超時(shí)甚至丟失；EDF調(diào)度策略中突發(fā)任務(wù)截至?xí)r限小于其他任務(wù)截至?xí)r限，因此到來(lái)時(shí)搶占其他任務(wù)如本地任務(wù)優(yōu)先執(zhí)行，但是EDF調(diào)度策略復(fù)雜的計(jì)算和較多的上下文切換并不適用于無(wú)線傳感器網(wǎng)絡(luò)；基于多優(yōu)先級(jí)隊(duì)列調(diào)度策略中，突發(fā)任務(wù)被分配在P1隊(duì)列中，在數(shù)據(jù)包到來(lái)時(shí)，接收數(shù)據(jù)包的任務(wù)在滿足可搶占條件時(shí)可以搶占正在執(zhí)行的低優(yōu)先級(jí)隊(duì)列中的任務(wù)優(yōu)先執(zhí)行，使數(shù)據(jù)包在有效時(shí)間內(nèi)被正確處理，很好保證了系統(tǒng)對(duì)突發(fā)任務(wù)的及時(shí)響應(yīng)，有效提高了系統(tǒng)的吞吐量和系統(tǒng)對(duì)重要任務(wù)的響應(yīng)性能。

圖6 不同調(diào)度策略中突發(fā)任務(wù)響應(yīng)對(duì)比

5 結(jié)束語(yǔ)

為了提高TinyOS在實(shí)時(shí)環(huán)境應(yīng)用中的實(shí)時(shí)任務(wù)的響應(yīng)速率，本文在TinyOS原有的調(diào)度策略基礎(chǔ)上，提出一種基于多優(yōu)先級(jí)隊(duì)列調(diào)度策略，它充分考慮了任務(wù)的執(zhí)行時(shí)間以及系統(tǒng)開銷，實(shí)驗(yàn)結(jié)果表明，該調(diào)度策略在保持TinyOS原有調(diào)度策略性能的情況下，有效提高了系統(tǒng)對(duì)重要任務(wù)的響應(yīng)性能，在任務(wù)負(fù)載較重情況下，響應(yīng)性能的提高更加明顯。

[1]孫利民，李建中，陳渝，等.無(wú)線傳感器網(wǎng)絡(luò)[M].北京：清華大學(xué)出版社，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]尹震宇，趙海，徐久強(qiáng)，等.無(wú)線傳感器網(wǎng)絡(luò)操作系統(tǒng)中搶占式任務(wù)調(diào)度策略[J].東北大學(xué)學(xué)報(bào)：自然科學(xué)版，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]宋風(fēng)坤，陳滌.采用快速排隊(duì)算法的WSN任務(wù)調(diào)度策略研究[J].計(jì)算機(jī)工程與應(yīng)用，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調(diào)度算法的可調(diào)度性分析[J].計(jì)算機(jī)工程與應(yīng)用，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

針對(duì)TinyOS先來(lái)先服務(wù)調(diào)度策略中重要任務(wù)不能及時(shí)響應(yīng)的不足，提出一種基于多優(yōu)先級(jí)任務(wù)隊(duì)列的調(diào)度策略。該調(diào)度策略將原來(lái)一個(gè)任務(wù)隊(duì)列增加為三個(gè)優(yōu)先級(jí)隊(duì)列并引入搶占機(jī)制，最高優(yōu)先級(jí)隊(duì)列中的任務(wù)在滿足搶占原則時(shí)才可以搶占其他隊(duì)列正在執(zhí)行的任務(wù)，任務(wù)只能在不同隊(duì)列之間發(fā)生搶占，這樣既減少了上下文切換，又保證了重要任務(wù)的優(yōu)先執(zhí)行。實(shí)驗(yàn)結(jié)果表明，該調(diào)度策略在不影響原有系統(tǒng)性能的情況下，提高了TinyOS對(duì)重要任務(wù)的響應(yīng)性能。

無(wú)線傳感器網(wǎng)絡(luò)；TinyOS；調(diào)度策略

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.

國(guó)家自然科學(xué)基金（No.71102065）。

馬文濤（1988—），男，碩士研究生，主要研究領(lǐng)域?yàn)榍度胧较到y(tǒng)、無(wú)線傳感器網(wǎng)絡(luò)；李雙慶（1969—），男，副教授，博士，主要研究領(lǐng)域?yàn)榍度胧较到y(tǒng)開發(fā)、SOA/SOC、計(jì)算機(jī)網(wǎng)絡(luò)。E-mail：mwt0530@163.com

2012-12-13

2013-02-05

1002-8331（2014）22-0106-05

CNKI網(wǎng)絡(luò)優(yōu)先出版：2013-03-13,http://www.cnki.net/kcms/detail/11.2127.TP.20130313.0955.020.html