μC/OS－ll中任务调度算法的改进

时间：2007-01-21 22:35:00

关键字：调度算法 OS BSP 程序员

手机看文章

扫描二维码
随时随地手机看文章

[导读]μC/OS－ll中任务调度算法的改进

摘要：介绍μC／OS—II嵌入式实时操作系统的特点，分析单一的基于优先级调度算法存在的不足。根据嵌入式应用不同的实时性要求，将应用划分为实时任务、分时任务和后台任务三种类型。针对分时任务，新增加时间片调度算法，给出调度算法的实现方法，同时增加任务创建和销毁的接口；降低基于μC／OS—1I操作系统的嵌入式产品开发难度和设计成本，有利于该操作系统的应用推广。

关键词：μC／OS—II 嵌入式系统任务调度算法时间片调度

引言

目前，操作系统内核的软件中，μC，0S-II称得上是小型实时操作系统。它由Jean J．Labrosse于1992年推出第l版，立刻在嵌入式系统领域引起强烈反响。μC／OS II是一个基于抢占式的实时多任务内核，可固化、可剪裁、具有高稳定性和可靠性。它最鲜明特点就是源码公开，便于移植和维护，而且对于学校研究完全免费，只有在应用于盈利项目时才需要支付少量的版权费，特别适合一般使用者的学习、研究和开发。自问世以来，其稳定性和可靠性得到了广泛的认可，现已经通过美国FAA认证。在嵌入式领域，μc／OS凭借优越特性得到了越来越广泛的应用，众多的研究开发者将其作为操作系统的样板，移植到各种硬件平台，其外围的应用也越来越多。

1 μC／0S在嵌入式产品应用中存在的问题

随着移动通信、信息家电以及工业控制等领域的快速发展，嵌入式软件产业迎来了极佳的发展时机。强劲的市场需求带来了研发的快速增长，越来越多的软件公司投入到嵌入式产品的研发中。但另一方面，大部分软件公司却缺乏嵌入式操作系统这个嵌入式产品的核心技术，无法提供给各种应用多任务等现代操作系统所必备的功能，极大地限制了产品的性能和发展。μC／OS具有源码公开，商业授权费极低等特点，成为嵌入式产品开发的一种选择。

μC／OS—II在设计时强调实时性。它采用单一的基于优先级的抢先式调度算法，有效地保证了实时性的要求。在各种嵌入式操作系统中，其任务切换带来的时延窗口很小。非常适合强实时性的任务要求，但是对于大部分周期性和实时性要求不高的任务来说，μC／O一II还存在一些不足：

①缺乏时间片调度，低优先级的任务很难得到执行。μC／OS—II不支持时间片调度，优先级高的任务如果不主动放弃CPU，低优先级任务永远都不可能运行。这对于那些分别编写，但叉可能同时运行的任务来说，只能通过任务之间的同步等动作来完成交替运行。这不但增加了编程难度，而且破坏了模块的独立性。

②任务创建和销毁的接口复杂。μC／OS—ll的上层软件开发需要关心底层具体实现，接口比较复杂。对于经验不多的程序员来说，第一，创建任务时需要用户自行指定优先级。这必然牵涉到如何管理分配优先级的问题。第二，μC／OS—II中任务的栈空间完全由用户管理，系统只是简单地要求用户创建任务时传人栈地址，而不参与栈空间的申请和释放。为了简化μC／OS的示例程序，更是简单地以静态数组作为任务栈。栈空间的放任自流在带来一定灵活性的同时也会带来问题的隐患。第三，因为μC／OS—II规定任务必须为无限循环或自销毁形式，所以其任务在结束时，需要手工调用OSTaskDel，使该任务进入睡眠态，不能简单地返回。与现在流行的大多数操作系统用法差异较大。

结合国内的产业现状，从程序员素质和应用程序的实时性分类，在数量上都呈现金字塔状；而且往往是高级程序员负责开发实时应用，普通程序员开发非实时应用。如果希望能在包括数目庞大的非实时应用的产品中利用μC／OS—II，则必须对它作出扩充，在保留实时任务支持的前提下，增添时间片调度，并对任务的接口作出简化处理。

2 μC／OS调度算法的改进

μC／OS中的每个任务具有一个任务控制块0S_TCB，任务控制块记录任务执行的环境，包括任务的优先级、任务的堆栈指针、任务的相关事件控制块指针等。内核将系统中处于就绪态的任务在就绪表中进行标注，通过就绪表中的两个变量OSRdyGrp和OSRdyTbl[]可快速查找系统中就绪的任务。在μC／OS—II中每个任务有唯一的优先级，因此任务的优先级也是任务的唯一标识。内核可用控制块优先级表OSTCBPrioTbl[]通过任务的优先级查到任务控制块的地址。μC／OS—II主要就是利用任务控制快OS_TCB、就绪表和控制块优先级表0STCBPrioTbl[]来进行任务调度。任务调度程序OSSched()首先由就绪表中找到当前系统中处于就绪态的优先级最高的任务，然后根据其优先级由控制块优先级表0STCBPrioTbl[]取得相应任务控制块的地址，由OS_TASK—SW()程序进行运行环境的切换。若在任务运行时发生中断，则转向执行中断程序，执行完毕后不是简单地返回中断调用处，而是由OSIntExit()程序进行任务调度，执行当前系统中优先级最高的就绪态任务。

本文拟在不破坏μC／OS实时性的前提下，增加时间片调度，以适于非实时性场合，并参考Windows和Linux多种通用操作系统任务调用接口函数，对μC／0S任务接口作出改进，提供通用简单的编程接口,降低应用软件开发难度，增加系统稳定性和可靠性。

2.1 时间片调度算法的设计与实现

μC／OS中共有64个任务，其中作者保留了8个任务以备将来使用，因此用户可以有多达56个应用任务。将这些任务划分为3个层次，如图l所示。

实时任务保留原本设计的绝对优先级调度，对系统驱动或通信等实时性要求高的场合提供支持，任务的创建接口保持不变，由高级程序员编写相应程序；在分时任务空间采用时间片调度，各种任务轮流执行，适用于事务性处理或实时性要求不高的场合，普通程序员在此区间内编写任务，并对此空间任务的创建和销毁提供了新的编程接口，使之适合普通程序员的编程习惯；后台任务是指idle任务、统计任务等在系统空闲时运行的任务，其在实时任务和分时任务都没有就绪时才有机会运行，此区间也采用绝对优先级调度。

分时任务在μC／OS原先的五种状态中添加了等待态，定义为OS_STAT_WAITSLICE，表示正在等待时间片的重新产生。增添新状态后的状态迁移如图2所示。

其中睡眠态(dormant)异于多数操作系统的定义，是指任务驻留在程序空间之中，还没有交给μC／OS—II管理。所有任务开始于睡眠态，通过调用任务创立函数把任务交给μC／0S—II。当任务一旦建立，就进入就绪态准备运行。在任务销毁时，可以通过调用OSTaskDel()返回到睡眠态。其余阻塞态、就绪态、运行态和中断态较常见，这里不再详述，可以参考文献[1]第3章。

图2中，如果处于运行态的任务时间片消耗完毕，则该任务进入等待状态如果全部分时任务都进入等待状态，则系统会为其全部重新分配时间片，并使它们都返回就绪态。除此之外，其余状态关系与μC／0S—Il相同。

为了实现分时任务时间片调度算法，首先在OS_TCB结构中添加OSTCBTimeSlices，以存储任务剩余的时间片数；同时定义OS-NORMAL_PRIO_START和OS_NOR-MAL_PRIO_START，表示分时任务区间的大小；还必须修改μC／0S的时钟服务程序，即函数OSTimeTick()，来处理与时钟相关的任务状态。修改后处理流程如图3所示。

图3中，模块②之前的流程与在μC／()S—II中几乎完全相同，主要负责对所有任务时延值的处理。模块②判断处于就绪态的分时任务是否时间片用完，如是，则将其设置为等待态。模块③查出就绪的最高优先级任务。如果低于分时任务区间，说明没有分时任务或所有的分时任务都处于等待态，此时为所有的分时任务重新分配新的时间片，并将其变更为就绪态。模块④中，如果当前任务是分时任务，则说明该任务已经消耗了一个时间片，将该任务时间片减1。

从改进后的处理流程可以看出，实时任务优先级高，调度不受影响，不会进入新加入的部分；分时任务在运行态时，其时间片会不停减少，直到剩余时间片为零，则进入等待态。当系统的所有分时任务都进入了等待态，则对在等待态的分时任务重新计算剩余时间片，并把它们都设为就绪态，则新的一轮分时任务交替运行又开始了。所有的后台任务的调度也不受影响。

OSTimeTick处理十分频繁，必须尽可能地减少运算开销，改进方案对其增加分时任务的处理。在有实时任务运行时，延时基本没有增加；只有在所有分时任务都进入等待态后，才会有较大的计算量，经试验效果良好。

2.2 任务接口的改进

为了简化应用编程接口，屏蔽低层任务管理细节，为用户提供新的任务接口OSNTaskCreate和OSNTaskDel。0SNTaskCreate用于创建分时任务，该函数在分时区间自动分配优先级，代替用户申请栈空间，并在初始化栈内容时压人OSNTaskDel地址。在用户任务退出后，就会自动调用()SNTaskDel，以释放栈空间，并调用()STaskDel。如此更符合用户在Windows等系统的情况，任务结束后只是简单返回，减小了错误出现的机会。改进后的OSNTaskCreate伪码如下：