浅谈μC／OS任务调度算法的硬件实现

邵贝贝

（清华大学 工程物理系，北京100084）

μC／OS是由美国嵌入式系统专家Jean J.Labrosse先生为嵌入式实时操作系统（RTOS）写的实时内核，最早连载在美国的《嵌入式系统编程》杂志1992年5月和6月刊上，源码发布在该杂志的BBS上。该实时内核最初是为Motorola的8位单片机MC68HC11写的，为便于普及，在后来关于μC／OS和μC／OS－ⅠⅠ的3本著作中［1－3］，该内核提供的是PC上的源码。μC／OS－ⅠⅠ比μC／OS增加了很多功能，在任务调度算法上并无不同，故本文提及任务调度算法时不再区分μC／OS和μC／OS－ⅠⅠ。

一项对我国嵌入式应用工程师的统计表明［4］，各类嵌入式应用工程师正在研究和使用的操作系统中，Linux占38%，μC／OS－ⅠⅠ 占 34%，WinCE 占 16%，VxWorks 占5%。这里，Linux加μC／OS－ⅠⅠ就超过了70%，这两个操作系统对中国嵌入式应用领域的影响可见一斑。它们的共同特点是源码公开。Linux不是实时的，也不是为嵌入式系统专门设计的，而μC／OS－ⅠⅠ是专门为嵌入式应用设计的实时操作系统。将μC／OS－ⅠⅠ嵌入到产品中用于牟利是要对使用权付费的，国内一些信誉好的企业购买μC／OS－ⅠⅠ使用权的例子很多，而一些不大重视信誉和知识产权的企业也不在少数。

μC／OS－ⅠⅠ用于教学与研究是免费的。近些年来，我国各类大学的嵌入式系统教学中纷纷采用μC／OS－ⅠⅠ作为教材。而μC／OS－ⅠⅠ也被移植到几乎所有的CPU上。各类杂志上发表的相关论文也数目可观，虽然大部分论文只谈到移植。

μC／OS－ⅠⅠ是为8位CPU写的RTOS小内核，任务调度算法巧妙，移植到任何处理器上都很好用。而对于一些有RTOS优先级算法硬件指令的16／32／64位的处理器，照搬 μC／OS－ⅠⅠ的8位算法、强行移植 μC／OS－ⅠⅠ未必恰当。

1 μC／OS的调度算法

μC／OS采用优先级至上的任务调度原则：“让进入就绪态任务中优先级最高的那个任务，一进入就绪态立刻就能立即运行”。这种基于优先级的任务调度原则，在嵌入式实时系统中最常用。μC／OS实现了一种巧妙的查表算法，利用这种算法能快速实现上述任务调度原则。这种查表算法的大致思路是，用8字节数组中的64位作为就绪任务表，每一位表示一个任务的状态，该位为1表示任务就绪，0为非就绪态。64位中第一个字节的b0位代表64个任务中优先级最高的任务，最后一个字节的b7位代表优先级最低的空闲任务。通过2次查用一张常数数组表，迅速找出任务就绪表中就绪态任务中优先级最高的那个。常数表中，按照0～7表示的8种不同权重，以一定规律排列128个0、64个1、32个2、16个3，8个4、4个5、2个6和1个7，再补上1个0后，共256字节。查表法避免了逐位检测各优先级位引起的执行时间的不确定性，程序简单，执行速度快，且时间是固定的，与就绪任务多少无关，与任务优先级无关。这是μC／OS任务调度的核心算法。在处理信号量、邮箱、消息队列等事件时，为了查找等待事件发生的任务列表中优先级最高的那个任务，也采用同样的算法，查的是同一张常数数组表。

μC／OS最初是为 Motorola的增强型8位处理器MC68HC11写的，算法精彩，将其移植到其他8位、16位处理器，这种8位机算法无懈可击。除任务就绪表外，μC／OS－ⅠⅠ在多处使用了上述调度算法。典型地，在事件控制块ECB中有：

这里，OS＿EVENT＿TBL＿SⅠZE 的默认值为8，即以8个8位数的数组表示最多64个不同优先级的任务；OSEventGrp是OSEventTbl的索引字节，这就是μC／OS算法中著名的8＋1个字节数据结构。当OSEventTbl中的某一个字节不为0时（表示该字节代表的8个任务中至少有1个在等待事件发生），OSEventGrp中的相应位置1。首先以OSEventGrp的值做偏移量，查那张256字节的常数表，获得1个0到7的数Y，作为优先级高3位，再根据Y的值，找出OSEventTbl中8个字节中最先出现的那个不为零的字节；然后再次查那张表，得到1个0到7的数X，找出字节中最靠近b0的那一位，作为优先级低3位的值，通过将Y左移3位再加上X的值，得到等待事件发生任务中优先级最高的那个任务的优先级。

在每个任务的任务控制块TCB中有下列定义，可以看出，任务优先级被拆分成两个8进制数X和Y，用来以空间换时间，加快优先级查找速度：

以上是μC／OS任务调度算法的简要介绍，Jean J.Laborosse先生最先用这种算法实现了RTOS中基于优先级的调度策略，是μC／OS任务调度算法的精华与核心技术。

2 优先级算法指令

对于32位和64位处理器，特别是一些精简指令流类型的处理器，其内部有可直接用于RTOS优先级算法的硬件指令。以PowerPC处理器［5］为例，予以说明。这里顺便解释一下，PowerPC是ⅠBM、Motorola和Apple三家公司于90年代初期联合设计的32位处理器，90年代后期出现增强型32位处理器，大量用于嵌入式系统，特别是汽车、通信等行业。本世纪初期，还出现了64位的处理器。在64位PowerPC处理器指令中，有2条可供RTOS算法使用的指令：

上述指令也可简称为CLZ指令。设某通用源寄存器RS中有一个64位数，b0是高位，b63是低位，执行cntlzd指令后，在目标寄存器RD中返回源寄存器RS中64位数的前导零的数目。返回0表示b0不为0，即该64位数没有前导0；返回n表示bn不为0，bn位的前面n位（b0～bn－1）共有n个零；返回64表示RS寄存器中所有位都为0。

如果用一个64位数表示64个任务的优先级，从b0开始到b63，b0为最高优先级，b63表示最低优先级，使用cntlzd指令，可迅速找出优先级最高的那个任务。RⅠSC类型的处理器，执行1条指令一般只需要1个CPU时钟周期。执行该指令，仅一个CPU时钟周期就可完成对64个不同优先级任务的判选。在这类处理器上直接移植和套用μC／OS－ⅠⅠ软件算法，显然不合理。

对于32位的PowerPC，也有汇编指令cntlzw。数出一个32位数前置零的数目。指令执行后，RD中返回指定源寄存器RS中32位数的前置零的数目，返回0表示b0不为0，即没有前导0，返回32表示寄存器RS中所有的位都为0。这一条指令可从32个任务中迅速找出优先级最高的那个任务。若使用2个32位数表示64个不同任务的优先级，则下面是使用该指令实现μC／OS－ⅠⅠ算法的示意性代码。

这样，很少几条指令，就完成了μC／OS中需要查表来完成的算法，不仅速度快，还省去了程序中256字节的那张常数表。上述实现方法并非唯一的，还可进一步优化。对于增强型32位PowerPC［6］，还有一条指令可对2个地址连续的32位数做并行操作，同时数出前导零的数目。此时若低32位不为0，则最高优先级者被立即找出；若为0，则取高32位中的优先级再加32即可。

其他32位机，如MⅠPS的处理器，也有同类指令。一些处理器还有与上述指令对称的“数出前置1的数目”指令。总之，在有类似CLZ指令的处理器上，直接移植和使用μC／OS－ⅠⅠ的任务调度算法并不合理。移植后需要摒弃μC／OS－ⅠⅠ中的软件算法，代之以硬件指令算法指令，实现RTOS任务调度算法的优化。

早期的ARM系列处理器并不支持CLZ指令，但从ARM Cortex开始，或者说ARM v5及以后的ARM类CPU，如Cortex－A8、Cortex－M3等，开始支持 CLZ指令。因此对于Cortex单片机，也没有必要套用μC／OS算法，这类处理器可运行μC／OS－ⅠⅠⅠ［7］。μC／OS－ⅠⅠⅠ是在μC／OS－ⅠⅠ的基础上发展起来的商业产品，目前还只能在ST的ARM Cortex 32位微控制器上实现。Cortex有RTOS硬件算法指令，不再需要使用μC／OS的查表算法。μC／OS－ⅠⅠⅠ还增加了同优先级任务的时间片轮转调度法等很多新功能，已经是一个全新的RTOS商业产品了，不再是μC／OS－ⅠⅠ的升级版。由于目前μC／OS－ⅠⅠⅠ产品单一且源码不再开放，以及价格方面等原因，我们还无法预见其未来。因此，深入研究和讨论μC／OS－ⅠⅠ的移植和优化是很有意义的。

除了上面提到的几种处理器，还有一些16位处理器也支持CLZ这样的RTOS运算指令。在这类处理器上强行移植和直接使用μC／OS－ⅠⅠ也会有弄巧成拙的感觉。

以16位的MC9S12XE系列和XF系列单片机为例，片内有2个CPU，一个是传统的CⅠSC类型的CPU S12，另外一个是名为XGate的RⅠSC类型CPU，XGate中有一条类似指令BFFO（Bit Field Find First One）指令格式为：

意为找出第一个1，和数出前导零的数目其实是一回事。目标寄存器RD中得到源寄存器RS中16位数的第一个1的位置，如果RS中为全零，则C标志置位。在XGate处理器上，特别是使用v2内核的处理器，可以利用BFFO指令优化μC／OS－ⅠⅠ任务调度算法。且对于μC／OS－ⅠⅠ的改进并不限于用BFFO指令替代查表算法，还可以尝试将RTOS和其管理的任务分别加载到2个CPU上。内核和任务调度在RⅠSC类型的XGate上运行，被管理的任务放到CⅠSC类型的S12处理器上运行；XGate v1CPU虽然有BFFO指令，由于中断无法嵌套，无法完整地运行XGate，但至少可以将XGate－ⅠⅠ中的时钟节拍函数放到XGate上运行［8］。具有硬件优先级算法指令的处理器，以及多内核单片机，为μC／OS－ⅠⅠ的改进和性能优化开拓了丰富的想象空间。在决定移植和使用μC／OS－ⅠⅠ之前，应该仔细研究一下拟用处理器的指令集，切莫盲目移植了事。

3 移植和优化中还应思考的问题

因为越来越多的RⅠSC类型处理器有了能用于RTOS任务调度算法的硬件指令，μC／OS－ⅠⅠ调度算法可以用硬件指令迅速完成，而不必依赖原来的软件查表算法，大大简化了程序，提高了运算速度。但由于RⅠSC类型的处理器，没有直接对存储器操作的指令，所有操作都只能通过CPU内部寄存器完成，不能如同8位处理器那样直接对存储器做位操作，这类RⅠSC类型处理器中有很多内部寄存器，可以设一些寄存器变量类型的指针来操作。如何用好寄存器变量，是要仔细研究的。

RⅠSC类型的CPU一般没有让存储器的某一位置位或把存储器的某一位清零的指令。往往需要先读存储器到CPU寄存器，再使用“与”、“或”等指令让寄存器某一位复位或置位，再写回到存储器。这一连串的操作可能需要保护，防止其间被中断。可以想象，若移植μC／OS－ⅠⅠ，在填写任务就绪表的时候，操作并不简单，要考虑全面，避免任何疏漏和隐患。另外还有编译器方面的问题。我们看到，上述讨论中涉及了不少汇编指令，如同cntlz，在C语言中是无法直接表达的，编译器对这样的汇编指令能支持到什么程度，是用户要细心研究的。现在，越来越聪明的编译器能将我们写的C程序按照执行速度或代码长度等用户定义的条件进行优化，能优化到什么程度？什么条件下能把类似cntlz这样的指令优化进去？这些都是要研究的。

对于中高端的处理器，一般都有系统态模式和用户态模式（有的CPU称之为保护模式），过去看到的很多移植文章都对此不予理会，让CPU完全工作在系统态。如果让RTOS内核工作在系统态，任务工作在用户态，有助于提高系统安全性。这类讨论也是过去那些关于μC／OS－ⅠⅠ移植的文章中极少见到的。

4 小 结

μC／OS－ⅠⅠ是在中国嵌入式系统应用中很有影响力的RTOS内核，已经被移植到几乎所有能想到的处理器上。其技术亮点体现在优先级调度算法上。由于当初是为8位处理器写的，对于8位处理器和多数16位处理器，运行μC／OS－ⅠⅠ是很不错的选择。处理器硬件技术的不断发展，为RTOS任务调度算法的实现方法开拓了广阔的想像空间。一些原来需要软件实现的算法可以硬件化。典型地，对于32／64位和部分高端16位处理器，有可用于RTOS优先级算法的硬件指令，例如文中提到的Power－PC、MⅠPS、ARM Cortex和 XGate等，直接移植μC／OS－ⅠⅠ代码，套用其调度算法实际上很不合理。使用CLZ或BFFO等硬件指令替代μC／OS－ⅠⅠ中的软件算法，可大大简化μC／OS－ⅠⅠ代码并优化RTOS性能。本文提到的方法也决非唯一。技术在发展，对于μC／OS－ⅠⅠ，千万不要移植了事，尽管已经讨论了十来年，仍然需要静下心来学习并做些深入细致的研究，希望今后能够看到更多深入探讨μC／OS－ⅠⅠ优化的文章。

［1］Labrosse Jean J.μC／OS The real Time Kernel［M］.R＆D Publication，1992.

［2］Labrosse Jean J.μC／OS－ⅠⅠ The real Time Kernel［M］.R＆D Publication，1999.

［3］Labrosse Jean J.μC／OS－ⅠⅠ The real Time Kernel［M］.2nd E－dition.R＆D Publication，2002.

［4］《电子产品世界》编辑部.2008年度嵌入式应用调查报告［J］.电子产品世界，2009，16（1）.

［5］Freescale.e200z6PowerPC Core Reference Manual，2004.

［6］ⅠBM.Book E：Enhanced PowerPC Architecture，2002.

［7］Labrosse Jean J.μC／OS－ⅠⅠⅠ The real Time Kernel［M］.Micrium Press，2009.

［8］邵贝贝，等.嵌入式系统中的双核技术［M］.北京航空航天大学出版社，2008.