下载文档原格式
TinyOS任务调度的研究与改进李明，丁恩杰中国矿业大学信电学院，江苏徐州（221008）E-mail：lmsiee@摘要：本文介绍了TinyOS任务调度机制，指出TinyOS调度策略的特点及不足。
采用一种改进式NPEDF算法对TinyOS的调度器进行实时性改造，并详细描述了具体改进方案。
实验测试的结果证明了这种改进策略的有效性。
关键词：TinyOS，任务调度，实时性，NPEDF中图分类号：TP316.891.引言传感器技术、嵌入式计算技术、微电子技术、无线通信技术以及半导体与微机电系统制造技术的飞速发展和相互融合使得具有感知、计算和通信能力的低功耗多功能无线传感器网络得以实现。
近年来，无线传感器网络（WSN-Wireless Sensor Networks）被广泛应用于国防军事、国家安全、环境科学、交通管理、医疗卫生、反恐、灾害监测等领域[1]。
无线传感器网络操作系统（WSNOS）是无线传感器网络的支撑技术之一。
它是WSN 应用程序的基本软件环境，核心是任务调度。
目前面向无线传感器网络的操作系统主要有TinyOS、MANTIS OS[2]、SOS、SenOS[3]、PEEROS[4]等，其中最为流行的是加州大学伯克利分校开发的TinyOS[5]。
它采用基于组件的架构方式，在传感器网络天生就严格限制内存的条件下，可以用最小代码快速来创新和实现各种应用。
目前，它已经被成功的应用到多种硬件平台上，具有很高的应用价值和研究意义。
本文主要研究了TinyOS现有的任务调度策略，在分析出应用TinyOS可能存在的问题的基础上，结合嵌入式实时操作系统的相关理论，提出了一种改进式NPEDF算法，并用这种算法对TinyOS调度器进行实时性改造。
最后，通过实验对改进前后的TinyOS进行测试，以此来验证本文采用的调度算法对无线传感器网络通信性能的影响。
2.TinyOS 2.0任务调度策略TinyOS 2.0采用任务和事件驱动相结合的两级并发模型，任务调度策略采用简单的先进先出（FIFO）算法。
liteos任务调度原则一、引言LiteOS是华为公司开发的一款轻量级操作系统，它具有高效、稳定、安全等特点，并且可以适应各种不同的硬件平台。
在LiteOS中，任务调度是非常重要的一个组成部分，它负责管理和调度系统中的所有任务，确保系统能够高效地运行。
因此，在LiteOS中，需要遵循一些任务调度原则，以确保系统能够正常运行。
二、 LiteOS任务调度原则1. 任务优先级在LiteOS中，每个任务都有一个优先级，优先级越高的任务会被更早地执行。
因此，在设计LiteOS时，需要根据不同任务的重要性来确定它们的优先级。
通常情况下，系统内核和驱动程序的优先级应该比较高，而用户应用程序的优先级则相对较低。
2. 时间片轮转时间片轮转是一种常见的任务调度算法，在LiteOS中也采用了这种算法。
时间片轮转可以确保每个任务都有机会得到执行，并且可以防止某个任务长时间占用CPU资源导致其他任务无法执行。
在LiteOS中，默认时间片为10ms。
3. 互斥锁和信号量在多线程环境下，数据竞争是一个非常常见的问题，为了避免数据竞争，LiteOS中采用了互斥锁和信号量机制。
互斥锁可以确保同一时间只有一个任务能够访问共享资源，而信号量则可以控制任务之间的同步与通信。
4. 任务挂起和恢复在LiteOS中，可以通过挂起和恢复任务来实现任务的动态管理。
当某个任务暂时不需要执行时，可以将其挂起；当需要重新执行时，则可以将其恢复。
这种机制可以有效地节省系统资源，并且可以提高系统的响应速度。
5. 中断处理在LiteOS中，中断处理是非常重要的一个环节。
当硬件设备产生中断时，系统需要快速地响应并且进行相应的处理。
因此，在设计LiteOS 时，需要考虑到中断处理程序的优先级，并且需要确保它们能够及时响应。
6. 堆栈管理在LiteOS中，每个任务都有自己的堆栈空间。
为了确保堆栈空间不会溢出或者出现其他问题，需要对堆栈进行管理。
具体来说，需要记录每个任务使用的堆栈空间大小，并且在堆栈空间即将溢出时及时进行调整。
Tinyos调度器和任务介绍1、介绍TinyOS有二个基本的计算抽象：异步事件和任务。
Tinyos早些版本提供单一的类型任务，没有参数且只能FIFO调度。
将任务调度表现成TINYOS组件更容易制定，将任务表现成TINYOS接口可扩展任务类型。
TINYOS2.0采用这二种方法，这份文本记录了其是如何以简单的机制来提高系统可靠性。
2、TinyOS1.x任务调度TinyOS中的任务是可延迟的调用过程DPC，可以使某程序延迟计算或操作。
TOS任务一次运行完毕，任务间不可抢占。
这二个约束条件意味着任务代码是同步的。
也就是说，任务是原子性的。
在tinyos1.x中，nesC语言通过二种机制支持任务，任务声明和任务发布表达post task void computeTask(){//Code here}result_t rval=post computeTask();TinyOS1.x提供单一的任务类型，无参数函数及单一FIFO的调度策略。
Post语句可返回FAIL，表明TinyOS发布任务失败。
可发布任务多次。
例如，如果某一任务连续发布了二次，第一次成功但第二次失败，此任务将会被运行一次。
因为这样，虽然一次发布失败，但任务仍可能运行。
Tinyos1.x调度器由sched.c文件中的C函数集实现的。
若要修改调度器则需替代或修改此文件。
另外，因为任务仅通过nesC中的task关键字声明和post关键字支持，假设是无参数函数，不能修改语句或任务功能。
Tinyos1.x的任务队列是由固定大小的函数指针类型的循环缓冲实现。
发布任务就是将此任务的函数指针放入下个空缓冲区中。
如果没有空的缓冲区，发布任务将返回失败。
这类模型有几个问题：1）某些组件针对发布任务失败没有合适的响应2）某给出的任务能发布多次，这将占用多个缓冲区3）所有组件的所有任务共享单一资源：某个有问题的组件可能导致其他组件发布任务失败。
从根本上来，为了使组件A在发布任务失败后重新发布任务，另外一个组件B必须调用A的函数（命令或事件）？？。
TOSH_sched_init();for(;;){TOSH_run_task();}这两个函数的实现在tinyos-1.x\tos\system目录下的sched.c源文件中。
这个文件就实现了tinyos 1.x的调度策略，很简单吧？闲话少说，下面分析它的数据结构。
typedef struct {void (*tp) ();} TOSH_sched_entry_T;这个结构体就是tinyos任务队列里的东东，里面是个函数指针。
enum {#ifdef TOSH_MAX_TASKS_LOG2#if TOSH_MAX_TASKS_LOG2 > 8#error "Maximum of 256 tasks, TOSH_MAX_TASKS_LOG2 must be <= 8"#endifTOSH_MAX_TASKS = 1 << TOSH_MAX_TASKS_LOG2,#elseTOSH_MAX_TASKS = 8,#endifTOSH_TASK_BITMASK = (TOSH_MAX_TASKS - 1)};上面定义了tinyos任务队列里的最大任务数TOSH_MAX_TASKS，和一个掩码。
//定义tinyos任务队列，这个队列是个循环队列！volatile TOSH_sched_entry_T TOSH_queue[TOSH_MAX_TASKS];//“头指针”tinyos任务队列里的第一个不为空的任务的下标uint8_t TOSH_sched_full;//“尾指针”如果tinyos任务队列没有满，则是最后一个不为空的任务//的下一个元素的下标；如果任务队列满则是最后一个任务的下标。
volatile uint8_t TOSH_sched_free;好了，数据结构分析完了，咱们看看tinyos是怎样实现这个队列的吧，实现一个队列,无非就是初始化，增加队列元素，删除队列元素，判断队列是否为空……，数据结构里最基本的东东，想必大家比我清楚了！（如果这个不清楚，赶紧回去看看数据结构 ^_^ ）。
TinyOS中基于优先级的软实时任务调度
孙社文
【期刊名称】《微计算机信息》
【年(卷),期】2010(026)008
【摘要】TinyOS是一个开源的构件化操作系统,它采用构件化描述语言NesC进行开发,主要针对资源非常有限的无线传感器网络节点而设计.本文分析了具有代表性的无线传感器网络操作系统TinvOS的调度机制并指出其不足.在此基础上提出了改进方案并实现了基于优先级的调度策略.针对其在实时应用领域的调度缺陷,设计了一种软实时任务调度构件.从实际系统GAINS节点中应用的结果可知,该改进方法能很好地改善无线传感器网络通信性能.
【总页数】3页(P9-10,32)
【作者】孙社文
【作者单位】100036,北京,中国矿业大学机电与信息工程学院
【正文语种】中文
【中图分类】TP393
【相关文献】
1.实时嵌入式异构环境下多优先级混合任务调度动态策略 [J], 马晨;肖智斌;张晶;范洪博;车国霖
2.一种动态优先级实时任务调度算法 [J], 夏家莉;陈辉;杨兵
3.基于动态优先级策略的最优软非周期任务调度算法 [J], 涂刚;阳富民;卢炎生
4.TinyOS任务调度机制与实时调度构件设计 [J], 刘奎安;郭文生;桑楠
5.一种基于动态优先级的实时混合任务调度算法 [J], 徐文清;杨红雨
因版权原因，仅展示原文概要，查看原文内容请购买。
TinyOS学习笔记1---入门当我们uses某接口时，那么该接口下的所有command和event都可以调用。
在一些情况下，组件也可以provides和usesCommand。
同样的provides的组件要实现command的函数内容。
配置文件现在，我们已经知道某些组件提供的接口，但，仅仅通过这还不足以访问这个组件。
如果a,b同时都提供了一个接口c,那么，当组件d访问c接口时访问的到底是a还是b呢？所以配置文件就产生了，它的目的就是声明你要访问的组件名称，并且将它所提供的接口与你想要使用的接口相连接。
配置文件的构成配置文件configuration首先声明了其应用程序下的组件，关键字：components.声明了组件之后，通过->可以将两个组件的接口连接起来。
Main.StdControl -> BlinkM.StdControl;这段代码就是把组件main和blinkm的stdcontrol连接起来，这样，就建立了两个组件之间的联系。
当调用main.stdcontrol的时候就相当于调用了blinkm.stdcontrol。
关键字-> 永远是将一个使用（uses）的接口（左边）于一个提供(provides)的接口（右边）相连接。
也就是说只有左边的组件能够调用右边的组件的接口。
反之则不可以。
并且该关键是一个多对多的关系，即一个组件可以连接到很多接口，反之一样配置文件还可以通过=关键字来进行接口之间的连接，=号表示两个接口之间的关系是等同的，类似于c语言中的指针。
=号两边可以是uses=pro 也可以是u=u ,p=p.注：配置文件中也可以使用或提供接口。
（后面有例子）配置文件和顶级配置文件一个程序中可以有多个配置文件，但一定要有一个顶级配置文件。
在tinyos中组件也是分层次的。
最底层的组件贴近硬件部分，是经过一层一层封装才有了上层的组件，封装的过程中就使用了配置文件。
而一个应用程序需要一个顶级配置文件，在所有其他的配置文件的更高一层，编译时会首先参照该文件进行编译。
101 事件处理任务填满。
此时网络组件的新任务就不能成功入队，从而无法处理SendMsg.sendDone （）发送包完成事件，程序将不能确定包是否发送出去，结果造成网络通信不正常。
2．TinyOS 2.x 调度机制TinyOS 2.x 的内核模型发生了一些改变，在1.x 版本的基础上更进了一步。
在任务上的前后的语义也有所不同，这样的改变是基于运行时的经验并为解决 1.x 模型中的限制。
在TinyOS 2.x 上，任务队列不会再出现多个同样的任务同时执行的情形，每个任务都遵循“一个萝卜一个坑”的模式。
只有在一个“坑”里面已经有任务，并且没有开始执行的时候，这个任务投递才会返回错误信息，这是2.x 在任务调度方面与1.x 的一个最明显的区别。
2.x 分配了一个表示任务ID 的字节，即系统中最多可有255个任务。
任务的ID 越大，表示越受到关注，但与实际的重要程度并无关联。
TinyOS 2.x 任务调度模型如图2-25所示。
一个任务若需要执行多次，可在任务结束的代码处添加将再次投递入队的代码即可。
这样的定义解决了由于任务队列已满而无法通知组件事件结束的问题，从而实现一个任务只占任务队列的一个位置，不会像1.x 那样每投递成功一次就多占一个位置，这是2.x 版本的一大改进之处。
具体实现方法如下：图2-25 TinyOS 2.x 任务调度模型post processTask （）;...task void processTask （） {// do workif （moreToProcess ） {post processTask （）;}}2.6.6 TinyOS 2.x 消息通信机制1．TinyOS 2.x 主动消息通信机制TinyOS 2.x 中每一个主动消息有一个16bit 的目的地址和一个8bit 的消息类型。
在TinyOS1.x 中，消息结构是TOS _Msg 。
在TinyOS2.x 中，消息结构是message _t ，并且这个结构对于来自任何一个节点的通信接口都足够大，足以存储一个数据分组。
TOSH_sched_init();for(;;){TOSH_run_task();}
这两个函数的实现在tinyos-1.x\tos\system目录下的sched.c源文件中。
这个文件就实现了tinyos 1.x的调度策略，很简单吧？闲话少说，下面分析它的数据结构。
typedef struct {
void (*tp) ();
} TOSH_sched_entry_T;
这个结构体就是tinyos任务队列里的东东，里面是个函数指针。
enum {
#ifdef TOSH_MAX_TASKS_LOG2
#if TOSH_MAX_TASKS_LOG2 > 8
#error "Maximum of 256 tasks, TOSH_MAX_TASKS_LOG2 must be <= 8"
#endif
TOSH_MAX_TASKS = 1 << TOSH_MAX_TASKS_LOG2,
#else
TOSH_MAX_TASKS = 8,
#endif
TOSH_TASK_BITMASK = (TOSH_MAX_TASKS - 1)
};
上面定义了tinyos任务队列里的最大任务数TOSH_MAX_TASKS，和一个掩码。
//定义tinyos任务队列，这个队列是个循环队列！
volatile TOSH_sched_entry_T TOSH_queue[TOSH_MAX_TASKS];
//“头指针”tinyos任务队列里的第一个不为空的任务的下标
uint8_t TOSH_sched_full;
//“尾指针”如果tinyos任务队列没有满，则是最后一个不为空的任务
//的下一个元素的下标；如果任务队列满则是最后一个任务的下标。
volatile uint8_t TOSH_sched_free;
好了，数据结构分析完了，咱们看看tinyos是怎样实现这个队列的吧，实现一个队列,无非就是初始化，增加队列元素，删除队列元素，判断队列是否为空……，数据结构里最基本的东东，想必大家比我清楚了！（如果这个不清楚，赶紧回去看看数据结构 ^_^ ）。
一初始化
s
初始化函数很简单，大家肯定都会写了。
void TOSH_sched_init(void)
{
int i;
TOSH_sched_free = 0;
TOSH_sched_full = 0;
for (i = 0; i < TOSH_MAX_TASKS; i++)
TOSH_queue[i].tp = NULL;
}
上面这个就是了，首先是初始化两个“指针”，将它们指向第一个元素。
接着是一个for 循环将队列里的元素逐个“清零”。
二增加队列元素
bool TOS_post(void (*tp) ()) __attribute__((spontaneous)) {
__nesc_atomic_t fInterruptFlags;
uint8_t tmp;
// dbg(DBG_SCHED, ("TOSH_post: %d 0x%x\n", TOSH_sched_free, (int)tp));
fInterruptFlags = __nesc_atomic_start();
tmp = TOSH_sched_free;
if (TOSH_queue[tmp].tp == NULL) {
TOSH_sched_free = (tmp + 1) & TOSH_TASK_BITMASK;
TOSH_queue[tmp].tp = tp;
__nesc_atomic_end(fInterruptFlags);
return TRUE;
}
else {
__nesc_atomic_end(fInterruptFlags);
return FALSE;
}
}
该函数的参数是个函数指针，大家不要怕它，如果不明白就当它是个整数好了（有点误人子弟的嫌疑，不明白的话大家还是回去复习一下c语言 ^_*）！
从上面可以看出，该函数核心代码不过三句，
第一句：if (TOSH_queue[tmp].tp == NULL)，判断队列里是否满了；如果满了则返回FALSE，如果没满则队列的“尾指针”向后移，一时不明白的网友可以在纸上画画，很快就明白了；移完“尾指针”后，语句TOSH_queue[tmp].tp = tp;将传入的参数加入到队列尾（这个队列尾是移完“尾指针”前的队尾）。
就这样，增加队列元素的动作就完了，很简单吧？比我们学过的数据结构还简单吧？三、取出队列元素并删除该元素
bool TOSH_run_next_task ()
{
__nesc_atomic_t fInterruptFlags;
uint8_t old_full;
void (*func)(void);
fInterruptFlags = __nesc_atomic_start();
old_full = TOSH_sched_full;
func = TOSH_queue[old_full].tp;
if (func == NULL)
{
__nesc_atomic_end(fInterruptFlags);
return 0;
}
TOSH_queue[old_full].tp = NULL;
TOSH_sched_full = (old_full + 1) & TOSH_TASK_BITMASK;
__nesc_atomic_end(fInterruptFlags);
func();
return 1;
}
这个函数稍为比增加元素那个函数复杂一点点，不过也很简单！
首先是取出队列元素里的值：
void (*func)(void);
old_full = TOSH_sched_full;
func = TOSH_queue[old_full].tp;
就是这三个语句了！声明一个变量，到最后赋值。
接着语句if (func == NULL)，判断取出的元素的值是否为空，如果不为空则首先将取出值的原来那个位置清零（TOSH_queue[old_full].tp = NULL;），然后将头指针向后移动（TOSH_sched_full = (old_full + 1) & TOSH_TASK_BITMASK;），最后执行这个函数：
fun（）；
完了，这个队列简单到极点了吧？但有什么办法了，tinyos 1.x里，这个就是它的任务调度机制：FIFO，并且当队列满时不能够增加新的任务。
Tinyos 2.x似乎有所改变。
for(;;) { TOSH_run_task(); }这个语句就让tinyos（程序）一直跑到世界末日了！
void TOSH_run_task() {
while (TOSH_run_next_task())
;
TOSH_sleep();
TOSH_wait();
}
这个函数就不废话了！
从上面还可以看出，整个过程中并没有哪个语句调用bool TOS_post(void (*tp) ())函数，
那么谁来增加任务队列中的任务呢？这里举个例子，大家可以转到tinyos-1.x\apps\BlinkTask\目录下，这个例子跟之前的Blink功能一样，不过是使用任务的，在BlinkTaskM.nc文件中Timer 的fired事件中有一句：post processing（）就将任务添加到任务队列中。
换句话说，是应用程序或其它程序将任务添加到任务队列中。
