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