下载文档原格式
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"
#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（）就将任务添加到任务队列中。
换句话说，是应用程序或其它程序将任务添加到任务队列中。
