一种基于μC/OS-Ⅱ的多任务优先级调度新算法

梁建明，金京林

(华南师范大学计算机学院， 广东广州 510631)

嵌入式实时操作系统，一方面需要具有低资源和低功耗的嵌入式系统特点，另一方面还需要满足实时性，以保证任务在可确定的相对短的时间内得到响应[1]. 在实时系统的任务调度中，调度策略最多的是采用优先级抢占式调度法[2]. μC/OS-Ⅱ是一种“硬实时”的嵌入式操作系统[3]，是由Jean J Labrosse编写的一个源代码公开的抢占式实时内核[4]，在嵌入式领域有着广泛的应用[5]. 它采用查表法的算法实现了最高优先级任务的快速查找，其查找的时间复杂度和任务数无关，但其空间复杂度会随着任务数的增加而呈几何级数的增长. 正因为这个关键因素，目前μC/OS-Ⅱ最大只能支持64个任务，而随着嵌入式应用的发展，会成为一个瓶颈.

本文在保持现有其它算法和数据结构不变的基础上，提出了一种查找最高优先级的新算法. 首先，为便于理解和比较新旧算法的区别，对现有的查找最高优先级的算法和主要数据结构进行了分析；然后，详细阐述了新算法的推导和实现过程；最后，对新旧算法在性能上作一些分析和比较.

1 现有的查找最高优先级的算法分析

μC/OS-Ⅱ目前能支持的最大任务数为64个，任务标识号同时也是任务优先级号，且唯一，与高优先级任务相比有较小的优先级号. 现有的算法是将这64个任务分为8组，每组包括8个任务. 图1为相关的数据结构示意图.

图1 现有算法的数据结构Figure 1 The data structure of existing algorithm

图1表明：任务优先级号Prio[6]是1个8比特的无符号整数，其中用YYY(第4位到第6位)这3位来确定该任务属于哪一组，即对应OSRdyGrp[6]中的第几位，用XXX(第1位到第3位)这3位来确定该任务属于该组中的第几个任务，即对应OSRdyTbl[][6]中的第几位，高2位(第7位和第8位)目前是备用状态；任务就绪组OSRdyGrp是一个8比特的无符号整数，每个比特位代表一组任务，该位为1表示该组任务中至少有一个任务处于就绪态，为0表示该组中8个任务都处于非就绪态；任务就绪表OSRdyTbl[]是一个含8个元素的数组，数组下标与OSRdyGrp中的比特位一一对应，每个元素是一个8比特的无符号整数，每个比特位代表一个任务，该位为1表示该任务处于就绪态，为0表示该任务处于非就绪态，只要这8比特位不全为0，则该组任务在OSRdyGrp中对应的位就为1. 当某个任务进入或退出就绪态时，根据该任务优先级号Prio中的YYY和XXX的值分别对OSRdyGrp和OSRdyTbl[]的相应位进行置1或清0，这部分的算法比较精简，文中对此不作进一步分析和优化. 当需要调度最高优先级的任务进入运行态时，μC/OS-Ⅱ目前是采用查表法的算法来实现，即根据当前任务就绪组OSRdyGrp和任务就绪表OSRdyTbl[]的值，在优先级判定表OSUnMapTbl[][6]中找到最高优先级的YYY和XXX值，再组合成当前最高优先级号Prio. 该部分现有的关键算法如下：

//数据结构声明

INT8U Prio; //任务优先级

INT8U OSRdyGrp; //任务就绪组

INT8U OSRdyTbl[8]; //任务就绪表

INT8U OSUnMapTbl[256]; //优先级判定表

//查找最高优先级号

YYY=OSUnMapTbl[OSRdyGrp];

XXX=OSUnMapTbl[OSRdyTbl[YYY]];

Prio=(YYY<<3)+XXX;

可以看出，实现这个算法，需要一直在内存中保存优先级判定表OSUnMapTbl[]，而且这个优先级判定表的元素个数会随任务数的增加而呈几何级数的增加，占用的内存资源也随之迅速增加. 假设μC/OS-Ⅱ支持的任务数是n2个，则OSUnMapTbl[]中就有2n个元素. 现在如果让μC/OS-Ⅱ支持的任务数增加到256个，即n=16，按每个整数占2个字节计算，保存OSUnMapTbl[]就需要128 KB的内存空间，这显然不符合嵌入式系统的低资源的特点.

2 新算法的推导和实现

将μC/OS-Ⅱ支持的任务数增加到256个为例来讨论. 首先将这256个任务分为16组，每组包括16个任务. 只需将目前任务优先级号Prio中的2个备用位用上，用其中的高4位YYYY来确定该任务属于哪一组，用低4位XXXX来确定该任务属于该组中的第几个任务，这样很容易就可以将支持的任务数增加到256个. 图2为相关的数据结构示意图.

图2 新算法的数据结构Figure 2 The data structure of new algorithm

若采用现有的查表法的算法思想，其内存空间的耗用对嵌入式系统来说是无法接受的. 跳出查表法的算法思想，其实查找最高优先级号的关键在于：在OSRdyGrp中，由右向左按位扫描，找出第一个“1”并将其位序号赋给YYYY；同理，在OSRdyTbl[]中，由右向左按位扫描，找出第一个“1”并将其位序号赋给XXXX；找出的2个数组合起来就是当前最高优先级号. 这样，算法关键要解决的问题就是：对任意一个二进制表示的无符号整数k，由右向左按位扫描，找出第一个“1”所在数位的位序号n(序号从0开始). 针对这个问题模型，经数学推导可得：

结论1n=log2((k⨁(k-1))+1)-1,其中k为任意一个二进制表示的无符号整数，n为k中由右向左按位扫描的第一个“1”所在数位的位序号(序号从0开始).

证明不失一般性，设k为m位无符号二进制整数，表示为：

其中，ki(i=m-1,m-2,…,n+2,n+1)的取值为0或1,则k-1可表示为：

其中，ki(i=m-1,m-2,…,n+2,n+1)的取值为0或1.将k和k-1作异或运算有：

结果转换为十进制表示为：k⨁(k-1)=2n+1-1，进而可得：.

n=log2((k⨁(k-1))+1)-1.

证毕.

根据结论1中的这个等式，就很容易实现查找最高优先级号的新算法，关键程序如下：

//数据结构声明

INT8U Prio; //任务优先级

INT16U OSRdyGrp; //任务就绪组

INT16U OSRdyTbl[16]; //任务就绪表

//查找最高优先级号

YYYY= log10((OSRdyGrp^(OSRdyGrp-1))+1)/log10(2)-1;

XXXX=log10((OSRdyTbl[YYYY]^(OSRdyTbl[YYYY]-1))+1)/log10(2)-1;

Prio=(YYYY<<4)+XXXX.

以上算法表明，它没有使用到优先级判定表OSUnMapTbl[]，而是用简单的数学运算来代替，从而完全克服了现有查表法的局限性，保证了响应时间的确定性和实时性，其空间复杂度和时间复杂度都为O(1)，与支持的任务数完全无关，而且如果要增加支持的任务数的话，关键算法不需要作修改，只是在数据结构定义部分改变一下相关变量的位数，这点可以通过宏定义的方式来做，这样会更方便快捷.

3 性能分析

上面详细分析了μC/OS-Ⅱ中查找最高优先级任务的现有算法和新算法，现从以下几个方面对这2种算法作性能上的分析和比较.

(1) 直观地从代码量和程序结构上看，新算法和现有算法基本是一样的，没有任何条件分支语句，这点可以保证在任何情况下，系统的响应时间都是确定的，不会因极端情况的出现导致响应时间时快时慢.

(2) 从算法的时间复杂度上看，新算法保留了现有算法的优点，都是O(1).

(3) 从算法的空间复杂度上看，对于系统支持最大任务数为n2个的情况，现有算法的空间复杂度是O(2n)，而新算法是O(1). 换句话说，现有算法的空间复杂度会随支持的任务数的增加而呈几何级数的增长，这点对嵌入式系统而言是无法接受的. 而新算法与支持的任务数完全无关，可以轻松地将支持的任务数从现有的64个增加到256个，根据实际需要还可以更多，而且不会对时间和空间复杂度有任何影响. 从图3可以更形象地看出现有算法和新算法在空间复杂度变化趋势上的不同，其中横坐标为μC/OS-Ⅱ中支持的最大任务数的开方，纵坐标是所需优先级判定表OSUnMapTbl[]数组的元素个数，实心星号表示的连线为现有算法的变化趋势，空心圆点表示的连线为新算法的变化趋势.

图3 空间复杂度变化趋势比较Figure 3 Trends comparison of space complexity

4 结束语

实验结果表明，新算法保持了与现有的μC/OS-Ⅱ系统兼容，保留了现有算法的优点，而且在算法的空间复杂度和系统可扩展性上还更具优势，并且该算法同样还可以用于优化μC/OS-Ⅱ的事件控制块中的等待任务调度算法，有助于μC/OS-Ⅱ在更多更复杂的嵌入式应用场合中推广.

参考文献：

[1] KRISHNA C M, SHIN K G. 实时系统[M].戴琼海，译.北京:清华大学出版社,2004.

[2] 金宏,王宏安,王强,等.一种任务优先级的综合设计方法[J].软件学报,2003,14(3):376-382.

JIN Hong, WANG Hongan, WANG Qiang, et al. An integrated design method of task priority[J].Journal of Software, 2003,14(3):376-382.

[3] 郭勐,黄江洪,王贞松.实时操作系统μC/OS-Ⅱ的多任务改进方法[J].计算机工程与应用,2005(12):5-7.

GUO Meng, HUANG Jianghong, WANG Zhensong. A novel method for multitask support on real-time operating system μC/OS-Ⅱ[J].Computer Engineering and Applications,2005(12):5-7.

[4] 熊玉梅,陈一民.μC/OS-Ⅱ任务调度算法的改进[J].计算机应用与软件,2008,25(6):84-86.

XIONG Yumei, CHEN Yiming. An improved scheduling algorithm of μC/OS-Ⅱ[J].Computer Applications and Software,2008,25(6):84-86.

[5] 季虹,付少锋,车向泉,等.实时嵌入式操作系统μC/OS-Ⅱ内核的分析与改进[J].计算机工程,2007,33(16):246-250.

JI Hong, FU Shaofeng, CHE Xiangquan, et al. Analysis and improvement of real-time embedded operating system μC/OS-Ⅱ kernel[J].Computer Engineering,2007,33(16):246-250.

[6] LABROSSE J J. 嵌入式实时操作系统μC/OS-Ⅱ [M]. 2版.邵贝贝，译.北京:北京航空航天大学出版社,2003.