嵌入式μ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-Ⅱ内核采用任务的优先级作为任务标识，通过查找就绪表实现对就绪任务的管理。这种巧妙的设计能够保证任务调度的效率和任务调度时对优先级就绪任务的查找时间的确定性。

就绪表中有两个变量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-Ⅱ任务管理效率如此之高的关键因素。

　　3 μC/OS-Ⅱ调度算法的改进

μC/OS-Ⅱ目前的版本多仅能支持64个任务， 除去保留系统使用的优先级，多只支持56个任务。随着应用系统日益复杂，如此有限的任务数必将限制其广泛应用。为了使其可应用于更多更复杂的系统，必须对相关算法进行改进，扩展其可支持的任务数目。在对μC/OS-Ⅱ任务调度算法进行深入分析的基础上，下面将讨论如何将其支持的任务数由64个扩展为256个。

按μC/OS-Ⅱ原有思想不难想到直接将就绪表扩展为16×16，但这样做会出现内存消耗严重的问题。根据就绪表及数组OSUnMapTbl[]的定义，可推导出计算掩码数组OSUnMapTbl[]大小的公式（其中MAX_TASK_NUM为内核可支持任务数）：

OSUnMapTblSize=2sqrt（MAX_TASK_NUM）                      （1）

由式（1）可知：当系统支持任务数为64时，OSUnMapTbl[]数组元素个数为256个；而当任务数增加到256时， OSUnMapTbl[]数组元素的个数却指数级地增长到65 536个。这会导致很严重的问题：OSUnMapTbl[]是一个常驻内存的全局数组， 因此OSUnMapTbl[]数组的大小将直接决定系统对RAM的需求量。在32位的ARM处理器上，每个int型数占4 B（32 bit），则当任务数为64时，OSUnMapTbl[]数组仅消耗8 kB（256×32 bit）内存；而当任务数增加到256时，OSUnMapTbl[]这个常驻内存的全局数组将消耗掉2 MB（65 536×32 bit）内存。显然，一个普通的嵌入式设备是耗不起这么大的内存的，任务调度时系统将会崩溃。因此，必须对原有调度算法进行改进。

　　3.1 改进的就绪表结构

为了解决由于任务数增加引起的OSUnMapTbl[]数组大小指数级增长而导致内存消耗过大问题，考虑对就绪表再多进行索引。

任务数扩展到256个时，将256个任务按优先级分成4块，每块64个任务。为此，增加一个变量OSRdyIdx。改进后的就绪表由OSRdyIdx、OSRdyGrp[p]、OSRdyTbl[p][q]（p∈[0，3]，q∈[0，7]）三个变量组成。其中，OSRdyIdx某一位置1，表示该块中存在就绪任务；OSRdyGrp[p]数组的某一位置1则表示该组中存在就绪任务；而OSRdyTbl[p][q]的某一位置1，表示该优先级所对应的任务就绪。256个任务时改进的就绪表结构示。

当任务数扩展到256个时， 任务的优先级用二进制。在改进的就绪表结构中，仍将μC/OS-Ⅱ的任务按优先级进行分组。优先级的两位ZZ确定任务在就绪表中的哪一块，即变量OSRdyIdx的第几位为1； 中间三位YYY确定任务在就绪表某一块的哪一组，即数组OSRdyGrp[p]的第几位为1；而低3位XXX确定就绪任务在就绪表某一组的哪一位。这样形成了的三级查询，先选块，再选组，再选组内偏移。改进就绪表结构后，对OSMapTbl也要相应扩展。根据OSMapTbl[]数组的意义对其就绪扩展，扩展后的数组。

　　3.2 对相关算法的改进

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

与原有算法类似，任务进入就绪态时，需将就绪表中相应位置1，即利用OSMapTbl[]将OSRdyIdx、OSRdyGrp[]和OSRdyTbl[][]数组中相应位分别置位。改进后使一个任务进入就绪态的算法如下：

OSRdyIdx             |=OSMapTbl[prio》6]；

OSRdyGrp[prio》6]|=OSMapTbl[（prio》3）&0x07]

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

相反，要从就绪表中删除一个任务，只需将就绪表中相应位清零。同理，要在任务所在块所在组的所有任务都不在就绪态的情况下，才能将相应的块标志和组标志置0。改进的使任务退出就绪态的算法如下：

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

[prio & 0x07]）==0）

OSRdyGrp[prio》6]&=～OSMapTbl[（prio》3）&0x07]）

if（OSRdyTbl[prio》6]==0）

OSRdyIdx&=～OSMapTbl[prio》6]；

　3.2.2 从就绪态任务中查找优先级的任务

为了保证查找已就绪任务中优先级任务的时间确定，并提高查询效率，同样不能简单地使用while循环实现。μC/OS-Ⅱ仍需构造一个掩码数组SUnMapTbl[]。改进的就绪表以多进行索引的方法，有效地解决了OSUnMapTbl[]表过大导致消耗大量内存的问题，使掩码数组的大小从65 536有效地减小到256，从而使这个常驻内存的全局数组内存消耗量从2 MB减小到8 KB。

改进后的就绪表中每张子表中仍然只有64个任务，因此，就绪表结构改进后掩码表并不需要改变，仍与64个任务时相同号。对于OSUnMapTbl[]掩码表的构造，由于该表比较大，不宜人工推算，可写一个小程序生成，不难实现。限于篇幅，构造OSUnMapTbl[]表的代码不在此列出。

就绪表构造好后，通过如下算法，便可方便地找出进入就绪态的任务中优先级的任务在就绪表中的位置，以便进行任务切换。改进的算法如下：

z=OSUnMapTbl[OSRdyIdx]；

y=OSUnMapTbl[OSRdyGrp[z]]；

x=OSUnMapTbl[OSRdyTbl[z][y]]；

OSPrioHighRdy=（z《6）+（y《3）+x；

以上查找就绪表算法与直接通过while循环从就绪中查找法相对比，只需4行代码就实现了优先级任务查找的过程，这样时间复杂度从O（n3）降低到了O（1），从而大大提高了任务调度效率，并且保证了系统的实时性和确定性。

　　3.3 改进方案测试及分析

本文提出的方案继承了μC/OS-Ⅱ设计思想，在保证内核性能和实时性的前提下，成功地将μC/OS-Ⅱ可支持的任务数由64个扩展为256个，从而达到升级μC/OS-Ⅱ内核的目的，使其可应用于更多更复杂的系统。

该改进方案有如下优点：

（1）实现简单。只需对就绪表结构稍加改进，并对调度算法相关部分作出相应的修改。

（2）调度时间确定。引进OSMapTbl[]、OSUnMapTbl[]两张表能保证μC/OS-Ⅱ任务调度时间的确定性，并降低时间复杂度和内存消耗。

（3）保证实时性。实时性是RTOS的生命，该改进方案能保证重要任务总是优先占有CPU。

（4）可扩展性。如果还需扩大任务数，可按改进方案的思路进一步改进就绪表，以适应应用系统的需要；并可按该方案根据实际需要来定制任务数目，以更加有效地利用系统资源。

作为一个高实时性操作系统，μC/OS-Ⅱ必须有高效的任务调度算法作为支撑，任务调度算法是μC/OS-Ⅱ中主要的算法之一。本文深入分析了嵌入式实时操作系统μC/OS-Ⅱ的任务调度算法，找出了其任务管理效率如此之高的关键原因，并在此基础上提出了一种增大其支持任务数的改进方案。该方案算法执行时间确定，不随实际任务数目变化，从而保证了系统的实时性；且能保证内存消耗，扩展可支持任务数而不对系统效率产生太大的影响。利用本文提出的方案，用户还可根据实际需要定制任务数，以更加有效地利用系统资源，并使μC/OS-Ⅱ能应用在更多更复杂的场景。