基于优先级可抢占式调度策略的设计

翟 月

（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.