嵌入式实时系统任务内调度的策略和实现

邱培呸呸呸

摘  要  介绍了任务内调度的策略和实现，其利用嵌入式实时系统的任务调度机制和消息队列构造以进程为单位的二级调度策略，支持用状态、信号描述的SDL进程的C程序语言编程结构。它的精简和高效，对提高处理能力和系统整体性能有重大意义。
    关键字  任务调度；  VxWorks；  进程；  消息队列   

1  引言
    嵌入式实时系统提供的任务调度应用在一些大型的系统，如移动通信系统中需要同时处理成百上千的呼叫建立、呼叫拆除以及其他各种服务，仅仅进行任务间调度，将产生频繁的任务间切换，造成任务栈的开销太大，效率明显降低，不符合通信实时性的要求。任务内调度利用嵌入式实时系统的任务调度机制和消息队列构造的二级调度可以有效的提高系统通信的效率。
2  任务调度的局限性
    嵌入式实时操作系统提供了非常灵活的任务调度机制，以VxWorks为例，Wind内核采用基于优先级的抢占式调度法作为它的缺省策略，同时它也提供了轮转调度法，同优先级的若干任务间又可以基于时间片进行调度[1]。每个任务都被分配一定的以数字方式表示的优先级，通常从0到255。操作系统总是每次调度优先级最高的就绪任务执行，低优先级的就绪任务只有在高优先级的任务都处于阻塞态时才有机会被调度运行。任务是可被抢占的，一个可被抢先的低优先级任务在运行时将被一个刚刚从阻塞态醒来的高优先级任务所抢占。如果任务工作在时间片方式，某一个就绪任务也可以抢先另外一个优先级相同但时间片已经用尽的运行任务[2]。
    任务调度将调度问题全部交给操作系统内核，应该说是最省事最安全的一种方法，但是由于系统资源的限制，支持的任务数有限，这种方式在某些软件复杂度不高的产品中是可行的。而在一些大型的系统如移动通信系统中，由于同时可能要处理大量的包括已经建链的、正在建链的和正在拆链的呼叫，这些要同时处理的呼叫数量可能是几百个，也可能达到几千个，此时任务间需要频繁切换，造成任务栈的开销太大，因此效率并不是很高，在这种情况下仅采用任务调度是远远不能满足要求的。因而在任务调度（一级调度）的基础之上继续构建以进程为单位的二级调度就十分必要了。当然随着嵌入式实时操作系统性能的改善、CPU速度的提高，这个问题可能会逐渐弱化。
3  二级调度的机制
3.1  任务与进程之间的关系
    调度任务之间的切换由任务优先级决定，低优先级任务不能抢占高优先级任务，只有高优先级任务进入阻塞状态，低优先级任务才有机会运行，整个过程由操作系统来完成调度。二级调度即进程调度以调度任务为运行载体，就是要利用嵌入式实时操作系统的任务调度机制和消息队列构造自己的以进程为单位的二级调度策略，调度任务根据进程消息的类型和所处的运行状态对进程进行调度。进程调度支持用状态、信号来描述的SDL进程的C程序语言编程结构，具有不同优先级的调度任务分别调度若干个完成不同功能、有不同时延要求的进程运行，并实现进程的二级调度。进程的优先级别取决与任务的优先级，不同任务下的进程具有不同的优先级。同一任务下的进程具有相同的优先级，在使用优先级作为调度策略的系统中，往往对许多具有相同优先级的进程采用先来先服务调度算法（FCFS） [3]。因此在每个调度任务下，进程采用FCFS算法，只有在运行进程交出控制权，其它进程才能进行处理。进程与调度任务之间的关系如图1所示。
    任务由VxWorks根据任务的优先级和任务当前所处的状态（就绪、阻塞、运行）进行调度，调度任务从任务控制块和进程控制块中获得调度进程运行时所需的有关数据。进程也有三种运行状态：就绪态、阻塞态、运行态。因此每个调度任务就有三个队列：就绪进程队列、阻塞进程队列、运行进程队列，这三个队列分别用来指示该调度任务下处于不同运行状态的进程[2]。它的状态在消息激励下可以相互转换，如图2所示。


图1 进程与任务之间的关系



图2 进程状态转换
3.2  进程的构成
    每个进程是由若干函数代码、一个堆栈区、一个静态数据区、一个消息队列和一个进程上下文核心数据结构，即进程控制块（PCB）组成。之所以每个进程都有一个消息队列的原因，是因为如果一个任务下的所有进程共用一个消息队列（可用VxWorks的消息队列实现），则只能在消息队列上从前到后取消息，如果连续有几个消息同属于一个进程，则可能使其它进程的处理滞后，不符合同一任务下不同进程间的公平调度原则。进程的PCB、堆栈和静态数据区随进程的动态创建而创建、随进程的动态删除而释放。进程的代码实际上是用状态、信号所描述的SDL进程的C程序语言实现。
    进程作为有限状态机的集合体，其运行过程实质上是由一个状态机到另外一个状态机的迁移过程，迁移的原因是外部信号（消息）的激励。任何时刻，进程总是在某个状态机上等待某个特定的信号，收到信号并做相应的处理后又迁移到另一状态机。在新状态机上，又重复开始了信号的等待。进程主处理函数的执行过程用SDL图描述如图3所示。


图3 进程调用执行过程的SDL描述
4  二级调度的实现
    每个调度任务创建一个VxWorks定长消息队列，任务被创建后就无限循环运行，不断从自己要处理的消息队列中取消息，如果任务下所有进程的消息队列都为空，任务在其所操作的VxWorks消息队列上等待消息，此时，VxWorks令该任务阻塞，直到在其所等待的消息队列上有一个消息到来时，VxWorks才唤醒该任务，这种策略使其它被低优先级调度任务所调度的进程获得运行机会[2]。
    当一个调度任务被VxWorks调度运行后，该任务将从其所操作的VxWorks消息队列上获得消息，并把取到的消息指派给相应的进程，同时把阻塞且获得消息的进程放到任务的进程就绪队列尾部，然后开始循环调度进程的执行[3]。调度任务每次调度进程就绪队列中的第一个进程，当将被调度的进程是由于同步消息已经应答或延时已经到时而被唤醒时，调度任务将控制转移到保存在进程堆栈中的指令地址；否则，如果进程消息队列头上的是一条新消息，调度任务依据进程消息队列头上的消息和PCB中的数据为进程的主处理函数传递相应入口参数，并从主处理函数的第一条语句开始执行。

    进程依据入口参数获得当前消息，完成对应用层的通用外部接口调用和VxWorks的接口函数调用后，调用“退出进程”外部接口函数通知调度进程已经完成了一次消息处理，并将控制返回给调用任务。控制权返回给调度任务后，调度任务将刚刚处理过的进程从进程就绪队列头摘下，并将刚处理过的消息从该进程的消息队列头摘下，如果此时的进程消息队列为空，当前任务将进程置到任务的进程阻塞队列尾部，否则将进程置到进程就绪队列尾部，任务每调度进程执行一次，所有进程就绪队列中进程的相对位置就要发生一次变化，即循环向前移动了一下，这种调度机制保证了同一任务下的所有就绪进程获得平等的运行机会。
5  调度流程



图4 调度进程示意图

     在图4中，在派发消息链表中的消息时：
    （1）如果接收消息的进程处在阻塞状态，且此时不是在等待同步应答，消息将成为进程PCB消息队列的当前消息，该进程PCB将从阻塞队列进入就绪队列尾；若此时在等待同步应答，则仅将该消息添加到进程PCB消息队列尾。
    （2）如果接收消息的进程已经在就绪状态，则将该消息添加到进程PCB消息队列尾。
    （3）如果待分发的消息是同步定时器超时消息或同步应答消息，那么此消息不进入进程PCB的消息队列，直接把该PCB从阻塞队列中挂到就绪队列头。        
6  结论
    采用二级调度机制可以避免任务间过于频繁的切换，提高速度的同时更有利于系统容量的扩展。在VxWorks操作系统环境下测试的结果显示：进程调度模块效率大约是任务切换的4倍。同时，由于进程调度方式中很大部分（如内存管理、保护、异常处理等）由自己编写和管理，因此在系统初始调试阶段对于错误定位等可以更加方便、快捷。
参考文献
1．VxWorks Programmer’s Guide，[EB/OL]Wind River Systems Inc.，1999
2．Andrew S.Tanenbaum . Modern Operating Systems[M]  北京：机械工业出版社 1999
3．孔祥营,柏桂枝.嵌入式实时操作系统VxWorks及其开发环境Tornado[M].北京:中国电力出版社 2002