微型抢占式多任务实时内核设计

1、微型抢占式多任务实时内核设计作 者： 北京航空航天大学 郑玉全摘要：介绍引入事件驱动观念的抢占式多任务微型实时内核microstar的设计与实现；提出基于事件的优先级这一新概念。关键词：事件驱动 优先级 任务管理 消息 信号 同步市面上有很多优秀的嵌入式实时操作系统（rtos），但在中低端微控制器（mcu）上运行性能良好的rtos内核并不多。在高档机下，功能强大、运行极好的嵌入式实时操作系统，移植到中低端机上时性能很可能大幅度下降。一个很重要的原因就是它的大部分功能对中低档系统来说是不需要的，反而成为制约性能的累赘。中低档微控制器与高档机相比，一方面，寻址能力有限，处理速度慢，在相同的实时性能

2、要求下，对内核的代码效率的要求更为严格；另一方面，中低档机完成的任务相对简单，减少了对内核的功能需求，比如可以不需要内存管理。从嵌入式系统的共性来说，大多数情况下用户程序和系统内核是紧密结合在一起的，运行时存储器容量消耗、任务的数量、执行时间和结果都是可以预计的，这可进一步缩小对内核的功能需求。 事件驱动的观点认为，任务应该是被动地响应外界发生的各种事件，而不是主动地去“查询”，浪费处理器时间。采用事件驱动编程的方法，不仅提高了运行效率，而且降低了事件处理之间的耦合，使程序流程非常清晰，从而可大大提高开发效率。充分考虑中低端微控制器的硬件特点和嵌入式系统软件的需求，引入“事件驱动”的观念，笔者

3、开发了一个微型的抢占式多任务rtos内核microstar。支持任务的动态创建、删除、睡眠、挂起和恢复，提供消息（message）和信号（signal）两种任务间的通信方案、完善的定时器服务和功能齐全的任务同步函数库。限于篇幅，着重论述几个与众不同的设计思路和实现难点。1 调度策略1.1 基于事件的优先级对内核的实时性能来说，调度策略是关键。好的调度策略，既要体现各任务因所处理的事件对实时性的不同要求而带来的优先级差异，又要保证一定的公平性，避免出现低优先级任务长时间得不到执行的极端情形。常用的调度策略有两种：一种是按时间片轮转(round robin)调度，如rtx51；另一种是严格按优先级

4、的占先式调度，如c/os。按时间片轮转调度能很好地保证公平，但优先级的差异是通过对处理器的占用时间的多少来体现的。如果各个任务都不主动放弃执行，高优先级的任务能够比低优先级任务获得更多的处理器时间；但在嵌入式系统中，某个事件要求实时处理，并不意味着该处理需要较长的时间，而往往是要求尽快响应。因此，采用按时间片轮转调度，实时性不会太好。如果严格按任务的优先级来调度，可极大地提升系统的实时性，但却欠缺公平。如果高优先级任务是个无等待的死循环，低优先级任务就无法获得执行机会。一个好的办法是两者的结合，即可由任务的优先级产生调度，也可以由时间片到产生新的任务调度，如vxworks；但是实现起来较为复杂

5、，不一定适合中低档mcu。为此，基于以下事实，提出“基于事件的优先级(events based priority)”这一新观念。 一个任务往往处理多个事件，各个事件对实时性的要求不尽相同。一般的rtos下，任务的优先级是根据这些事件中对实时性要求最高的一个来确定的。因此，高优先级任务在处理对实时性要求不高的事件时，完全可能会妨碍低优先级任务处理具有一定实时性要求的事件。 有些情况下，对同一事件的处理可分为前台处理和后台处理：前台处理所需时间短，对实时性有较高的要求；后台处理花费时间长，对实时性则无多大要求。如果根据正在处理和等待处理的事件对实时性的不同要求，更细致地按事件处理的前后台阶段，动态

6、地调整任务的优先级，采用优先级调度策略，既可发挥实时性好的优点，又可在一定限度内保证公平。这种情况下，任务的优先级不再是一成不变的，而是动态地取决于所处理的事件和处理阶段，这就是所谓的“基于事件的优先级”。 1.2 在microstar中的实现microstar中任务的优先级是由静态优先级和动态优先级共同决定的。静态优先级等同于其它rtos中的优先级；动态优先级为基于事件的优先级由内核根据任务正在处理和等待处理的事件动态调整。静态优先等级限定为015级，不允许创建静态优先级相同的任务。动态优先等级目前只有0(亦称紧急级)、1(亦称普通级)两级。任务的实际优先等级可由下式来计算：优先等级动态优先

7、等级×16 + 静态优先等级。优先等级值越大，优先级越低。可以看出，动态优先级起决定作用。怎样实现优先级动态可调呢?首先简要介绍macrostar中任务的四个状态：休眠(dormant)任务因调用睡眠函数、挂起函数或者等待内核同步对象而进入休眠态；等待(waiting)任务因等待消息或者信号(勿与“信标”、“信号量”相混淆)而进入等待态； 就绪(ready)任务运行的条件都已俱备，只等被调度，称为就绪态，亦称可调度态；运行(running)任务正在使用处理器的资源，称为运行态。这些状态都是用标志位来实现的。16个静态优先级对应的任务的某一状态刚好可用一个16位的二进制数来标识。休眠态

8、用os_slpstate来表示，从高位算起，第n位为0表示静态优先级为n的任务处于休眠态。等待态是依据“事件驱动”观念而专为消息和信号而设计的，用os_rdyhstate和os_rdystate两个16位的变量来记录。只有当os_rdyhstate和os_rdystate的第n位均为0时，才表示静态优先级为n的任务处于等待态。如果任务处于非等待状态，意味着任务已在处理事件或者有事件要处理(可以认为任务一开始就处理“启动”这个“虚拟事件”)，这时，才有动态优先级的概念。如果os_rdyhstate中的第n位为1，表示静态优先级为n的任务的动态优先级为紧急级；如果os_rdyhstate第n位为0

9、，则表示静态优先级为n的任务的动态优先级为普通级。要求实时处理的事件发生后，内核简单将os_rdyhstate相应位置1，提升任务的动态优先级；当前事件处理完毕后，如果已无实时性要求较高的事件等待处理，简单地将os_rdyhstate相应位清0，降低任务的动态优先级。由此，即可实现优先级的动态可调。只有当任务既不处在休眠态也不处在等待态时，任务才是可以调度的。2 任务管理2.1 任务控制块多任务系统中用任务控制块（tcb）来记录任务的各种属性。在这些属性中，最重要的是任务堆栈栈顶地址。进行上下文切换（context switch）时，被停止执行的任务的所有寄存器状态、下一条代码的地址都要入栈保

10、护，因而这个属性是必需的。如果允许修改任务的优先级，优先级属性也是必需的。所以，将任务控制块简化如下：typedef structuint_16 msg2; /*消息接收区*/int * sp; /*堆栈栈顶指针*/uchar priority; /*静态优先级*/uchar reserved; /*保留 */tcb,*ptcb;tcb os_tcbs user_task_num +1 ;/*用户任务数最多为15个*/msg用来存储发送给任务的消息，两个16位的二进制可按位存放32个消息。sp指向任务堆栈栈顶。priority记录任务的静态优先级。数组os_tcbs用来记录系统所有任务的信息，

11、其下标与任务的id号相对应，即id号为n的任务的控制块为os_tcbsn。2.2 任务的创建os_createtask函数用来创建一个任务：void os_createtask(taskproc task, /任务函数的指针uchar taskid, /任务的id号uchar priority, /优先级int * pstack, /任务堆栈栈底地址void * param /任务函数的入口参数);typedef void (*taskproc)( void * param);创建任务时，内核要做以下几方面的工作： 初始化任务控制块； 初始化任务堆栈，使其如同被其它任务抢断时的情形； 将任务状

12、态置为就绪态。该函数是依赖于处理器的，图1是较为通用的描述。中断程序中，在高优先级任务剥夺低优先级任务之前，内核将断点时的各寄存器状态入栈保护，这部分区域即为寄存器映像区。将任务退出函数os_exit的地址先于任务函数mytask入栈，以使mytask函数退出后返回到os_exit中去，由此来实现任务的自动删除。2.3 任务切换与任务创建一样，任务切换代码与硬件相关。在pc机上，代码和步骤如下：void interrupt os_schedule( )（1）if( os_nlayers )return;os_nlayers+; （2）_dx = (int)os_pcurtcb; /*os_pc

13、urtcb指向当前任务的控制块*/*(int*)(_dx+4) = _sp;*(int*)(_dx+6) = _ss; （3）os_getreadytask( ); （4） _dx = (int)os_pcurtcb;_sp = *(int*)(_dx+4);_dx = *(int*)(_dx+6);_ss = _dx; （5）os_nlayers-;? （6）unlock_int( ); （7）(1)利用c语言interrupt关键字使各寄存器入栈保护。（2）锁定调度器，不允许重调度。（3）将当前任务的栈顶地址（由堆栈段寄存器ss和栈指针寄存器sp组成）保存在os_pcurtcb->s

14、p中（pc机下，tcb中的sp定义为远指针类型）。（4）选出优先级最高的就绪任务(方法类似于c/os)，并将os_pcurtcb指向新任务的控制块。（5）栈寄存器指向新任务的栈顶地址。（6）解锁调度器。（7）各寄存器出栈，恢复到上次被中断时的情形。3 消息与信号为很好地支持事件驱动编程，microstar借鉴了windows的“基于消息，事件驱动”观念，并加以扩展。在microstar中，事件不仅可以触发消息、信号，而且由事件触发的消息或信号是有优先级的，这是因为不同事件对处理的实时性要求是不同的。内核正是根据消息、信号的优先级来动态调整任务的动态优先级的。3.1 消 息 消息是一种很友好的通

15、信方式。考虑中低档单片机的内存容量和需求，将消息简化为一个031的值。采用固定位图存储格式，将这32个值映射到任务控制块的msg域，这大大减小了存储空间。可将msg域看作一个32位的二进制变量，第i位为1，表示有值为i的消息，因此消息的存取只需通过简单的“与”、“或”运算。消息的优先级依值而定，值越大，优先级越低。在系统范围内，消息优先级又分为两级：紧急级（值015）与普通级（值1631）。当有紧急消息发送给任务时，内核会提升任务的动态优先级，从而提高消息处理的实时性。当任务无紧急消息要处理时，内核就降低它的动态优先级。发送消息的核心代码如下：/*const uint_16 os_maskta

16、ble16 = 0x8000,0x4000, .,0x0008,0x0004,0x0002,0x0001 */if( msg&0xf0 ) /*普通级消息*/ptcb->msg1 |= os_masktablemsg&0x0f;/*普通级消息存在msg1中*/os_rdystate |= os_masktableptcb->priority;else /*紧急级消息*/ptcb->msg0 |= os_masktablemsg; ;/*紧急级消息存在msg0中*/os_rdyhstate |= os_masktableptcb->priority;/*提

17、升动态优先级*/与先进先出(fifo)方式的消息队列不同，内核总是取出优先级最高的消息来交给任务处理。消息接收函数os_getmessage设计思路如下：如果消息接收区中无紧急消息，则降低任务的动态优先级；如果消息接收区中有消息，则取出优先级最高的消息；如果没有消息，则将任务转为等待态。考虑有时候不希望任务进入等待态，microstar还提供了非阻塞的os_peekmessage消息接收函数。3.2 信 号在嵌入式系统编程中，常利用标志位来实现前后台程序或不同的任务间的通信。microstar也提供了类似的任务间的通信方式信号（signal）。它避免了用户程序因不断查询标志位而带来的时间浪费，

18、而且支持信号间的“与”、“或”运算。通俗来说，信号就是标志位，用来标识某个事件的发生。同消息一样，信号也有紧急级与普通级之分。与消息不同的是，信号完全由用户程序创建和维护，内核只是帮助用户程序等待信号，以避免低效率的标志位查询。使用起来不如消息直观，但执行效率较高。实现起来非常简单，请参见源码。4 定时器定时器在嵌入式系统有着大量的用途，如led的定时刷新、串口通信中的超时检查。对定时器的需求分为两类，一种是周期性重复定时，比如每隔10ms去刷新led；另一种是仅需定时一次的一次性定时。定时时长以系统时钟节拍（tick,又译作滴达）作为单位。两次系统定时中断之间的时间间隔为一个节拍。定时器结构

19、体如下：typedef structuint_16 elapse; /*定时时长的余值*/uint_16 backtime; /*定时时长的备份值*/ msg timerid; /*定时器id号*/uchar taskid; /*拥有该定时器的任务的id*/timerproc lptimerfunc; /*定时调用的函数指针*/timer,*ptimer; timeros_timersuser_timer_num; /*最多为16个*/周期性定时和一次性定时是通过timerid来区分的。如果timeid为64，为一次性定时；如果timerid不大于32，则为周期性定时。用os_timers数组

20、记录定时器信息，用16位的os_timerstate表示定时器的状态。如果os_timerstate的二进制数的第n位为1，则表示os_timersn空闲可用。 对周期性定时器，每隔定时时长的时间，内核就调用的lptimerfunc指向的函数，并且将timerid以消息的方式发送给任务，对任务的动态优先级的影响与普通消息一样。因此，要想取得实时性较好的定时器，只需将timerid设在015之间。与一次性定时相关的是睡眠函数和限时等待同步对象的函数。任务使用这两个函数而进入休眠态后，在定时时间到时，内核将其恢复为就绪态，并自动释放定时器资源。系统定时处理的核心代码如下：if( !(-ptimer

21、->elapse) ) /*elapse减为零表示时间到*/if( ptimer->lptimerfunc)(*ptimer->lptimerfunc)(ptimer->taskid,ptimer->timerid);switch( ptimer->timerid&0xf0 )case sleep_id: /*一次性定时*/os_slpstate |= taskmask; /*结束休眠态*/os_timerstate |= timermask; /*释放定时器*/break;case 0x00: /*发送紧急级定时器消息*/ptcb->msg0

22、 |= os_masktableptimer->timerid;os_rdyhstate |= os_masktableptcb->priority ;break;case 0x10: : /*发送普通级定时器消息*/ptcb->msg1 |= os_masktableptimer->timerid&0x0f;os_rdystate |= os_masktableptcb->priority ;5 同 步抢占式多任务下，低优先级的任务可以被高优先级任务打断执行。以常规方式访问共享变量或资源时，会出现奇怪的结果。比如，一个任务调用printf(“12345”

23、)试图在输出设备上输出“12345”，但执行中被高优先级任务打断；而高优先级任务也调用printf(“67890”)试图输出“67890”，最终的输出结果可能是“1267890345”之类。这就是多任务环境下的任务同步问题。同步方式有两种，一种为用户同步方式，不需要与内核打交道，具有速度快的优点，但只适合保护执行时间短的代码；另一种是内核同步方式，需要通过内核来实现，速度相对较慢，但可保护执行时间长的代码。5.1 用户同步方式用户方式下的同步是通过关键代码段（critical section）保护来实现。关键代码段是指这样一小段代码，它执行时必须独占对某些共享资源的访问权，不允行被其它试图访问

24、该资源的代码打断。最简单的是得用关/开中断来实现，优点是速度极快，缺点是带来中断延迟，只适合执行时间极短的代码段。另一简单的方案是通过加锁/解锁调度器来实现，即在关键代码段执行期间禁止内核进行任务切换。采用这种方法，不会带来中断延迟，但带来了调度延迟。在microstar中，对os_nlayers加1即可锁定调度器，减1即可解锁。但直接利用解锁调度器来离开关键代码段并不合适。如果在关键代码段执行中，发生了中断，使更高优先级任务就绪。但由于调度器被锁定，中断程序退出时不能进行任务切换以使高优先级任务执行。因此我们希望，最好一旦调度器解锁，马上就切换到高优先级任务。为此，专门用变量os_flag的

25、最低位作为标志位，中断程序中调用任何可以使任务就绪的系统函数都会影响到该标志位，如os_postmessage、os_setevent，os_notity。退出关键代码段时以此来判断是否需要进行任务调度。离开临界代码段时的代码如下：if( (os_flag&0x01) && (!(-s_nlayers ) ) ) -os_schedule( ); 5.2 内核同步对象 如果要保护执行时间较长的代码，就要使用内核同步对象来同步。常用的内核同步对象有事件(event)、信标(semaphore，亦称信号量)和互斥量(mutex)。 事件对象用来通知事件或者操作已经完成，它用

26、一个布尔值来表示该事件处于通知还是未通知状态。信标对象用于对资源进行计数。它记录了当前可用的资源数目。当用1来初始化信标对象的可用资源数目时，信标对象实际上成为了互斥对象。microstar提供事件和信标两种同步对象，支持查询、限时等待或无限时等待操作。内核同步对象的结构如下：typedef structuint_16 waiter; /*等待列表*/uchar num; /*可用资源数目或者事件状态*/uchar type; /*同步对象类型*/object,*pobject,*hobject,*hevent,*hsemaphore;当一个任务因等待同步对象而进入休眠态时，它的静态优先级按位存放在waiter域中。如果静态优先级为n的任务在等待某个同步对象，则waiter二