嵌入式μC/OS-Ⅱ任务调度算法的改进

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

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

另外，虽然μC/OS-Ⅱ内核非常优秀，但根据实际需求仍有一些地方有待改进，如任务数目的限制等问题。μC/OS-Ⅱ目前版本最多仅支持64个任务，而且其中有8个要保留供系统使用，所以最多有56个任务可供用户使用。随着应用系统日益复杂，如此有限的任务数必将限制其广泛应用，为了使其可应用于更复杂的系统，必须对相关算法进行改进。

1 μC/OS-Ⅱ任务调度简介

μC/OS-Ⅱ中的任务通常是一个无限循环，其任务状态有五种：休眠态、运行态、就绪态、等待态和挂起态。作为一个抢占式的实时内核，μC/OS-Ⅱ仅支持按任务优先级进行切换，不支持时间片轮转等其他调度方式，它总是运行进入就绪态的优先级最高的任务。μC/OS-Ⅱ中以任务的优先级作为任务标识，相同优先级的任务将无法区分，也就是说，μC/OS-Ⅱ不支持重复优先级。因此，μC/OS-Ⅱ内核中任务调度的主要工作就是查找出进入就绪态的任务中优先级最高的任务，并进行上下文切换。这里所花费的时间主要有：（1）查找最高优先级任务时间；（2）任务上下文切换时间。其中，任务上下文切换时间是与处理器相关的，操作系统无法控制。因此，要想提高任务调度效率，主要考虑如何提高查找最高优先级就绪任务的效率。

实时性是实时系统最重要的性能指标之一。操作系统的实时性主要体现在：当高优先级的任务就绪时，操作系统尽快将此任务调度到CPU执行。μC/OS-Ⅱ巧妙地通过构造一张就绪表，并使用查表法来实现对最高优先级的就绪任务的查找，这样可保证查找时间与应用程序中的任务数无关，确保查找时间的确定性，从而保证内核的实时性并提高任务切换效率。

2 μC/OS-Ⅱ任务调度算法分析

2.1 就绪表结构

μC/OS-Ⅱ内核采用任务的优先级作为任务标识，通过查找就绪表实现对就绪任务的管理。这种巧妙的设计能够保证任务调度的效率和任务调度时对最高优先级就绪任务的查找时间的确定性。

如图1所示的就绪表中有两个变量OSRdyGrp（8 bit，每bit代表一组）和OSRdyTbl[8]（数组中每个bit代表一个优先级），如果某个任务就绪，就将就绪表中相应位置1。为了提高任务切换效率，μC/OS-Ⅱ任务调度算法采取分级查询的方法。考虑到任务数不超过64，可以用6 bit（26=64）来表示，μC/OS-Ⅱ对任务按优先级进行分组，优先级的高三位决定任务在就绪表的第几组，而低三位用于确定在该组的第几位。这样便形成了的二级查询，先选组，再选组内偏移，这样可大大提高查询效率。

2.2 使一个任务进入或退出就绪态

如果要使优先级为22的任务进入就绪态，优先级22用二进制表示为0b00010110，其高3位和低3位分别为010和110。由就绪表的定义可知，优先级为22的任务在就绪表的第2组第6位，要使其进入就绪态，只需将OSRdyGrp的第2位和OSRdyTbl[]的第6位分别置1即可。

为了便于对某一位进行位操作，μC/OS-Ⅱ又建立了一个掩码数组OSMapTbl[]（如表1，定义在OS_CORE.C文件中）。若要将第k位置位，只需同OSMapTbl[k]按位进行与操作即可。通过如下算法可使一个任务进入就绪态（其中prio是任务的优先级）：

INT8U const OSMapTbl[]={0x01，0x02，0x04，0x08，0x10，

0x20，0x40，0x80}；

OSRdyGrp |=OSMapTbl[prio》3]；

OSRdyTbl[prio》3] |=OSMapTbl[prio & 0x07]；

在OSMapTbl[prio>>3]中，prio右移3位即prio/8，便可得到所在的组。用移位实现是为了提高程序效率，后面的prio《3同样如此；而OSMapTbl[prio & 0x07]中，prio & 0x07即只保留prio的低三位，这样便可得到任务在该组中的位置。

从就绪任务列表中删除一个任务则正好相反。对于OSRdyGrp，只有当被删除任务所在任务组中全组任务一个都没有进入就绪态时，也就是说OSRdyTbl[prio》3]所有的位都是零时，才将OSRdyGrp相应位清零。可通过如下程序清单从就绪表中删除一个任务：

if （（OSRdyTbl[prio》3]&=～OSMapTbl[prio & 0x07]）==0）

OSRdyGrp &=～OSMapTbl[prio》3]；

2.3 查找最高优先级就绪任务

就绪表建立后，如何高效地查找出最高优先级就绪任务是任务调度的关键。优先级越高的任务，其优先级值越小，越在就绪表的右上方。因此，为了找出最高优先级的就绪任务，只需对OSRdyGrp从右往左找到第一个为1的位，假设为第m位；再从该组OSRdyGrp[m]中，从右往左找到第一个为1的位，假设为第n位。即就绪表中的第m组第n个任务为最高优先级的就行任务，组合一下，便得到了最高优先级就绪任务的优先级。该操作可通过一个while循环扫描整个就绪表实现，但随着就绪表中就绪任务的数目不同，这样做最多要查找64步，最少才需查找1步，显然其查找时间是不确定的；而任务切换时间的不确定性让系统的实时性难以得到保证，这对实时系统是致命的。为了解决这个问题，μC/OS-Ⅱ又建立了一个比较大的掩码数组OSUnMapTbl[k]（定义在OS_CORE.C文件中），其下标值范围为k∈[0，255]，值域为[0，7]。

这样，通过如下算法可在保证查找时间确定的前提下，较快地查找出进入就绪态的优先级最高的任务：

y=OSUnMapTbl[OSRdyGrp]；

x=OSUnMapTbl[OSRdyTbl[y]]；

OSPrioHighRdy=（y《3）+x；

以上查找算法和通过循环直接从就绪表查找相比，只需3行代码便可实现对最高优先级就绪任务的查找。

2.4 μC/OS-Ⅱ任务调度算法

任务调度算法是μC/OS-Ⅱ中最主要的算法之一。该算法通过建立OSUnMapTbl[]和OSMapTbl[]两张表，使任务切换执行时间恒定，不随任务数目变化，从而保证了系统的确定性和实时性。这里对μC/OS-Ⅱ的设计思想进行臆测，即“以空间换时间”。这点也可以从μC/OS-Ⅱ中存在众多的全局变量看出，如OSRdyTbl[]、OSEventTabl[]、OSTCBTbl[]等。这种设计思想避免了动态初始化。对于一个操作系统，任务调度十分频繁，这一点空间相对其换取的宝贵CPU时间是微不足道的。

μC/OS-Ⅱ正是采用这种策略使其性能得到了大大的提升，这种处理方法也是μC/OS-Ⅱ任务管理效率如此之高的关键因素。