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

摘要: μC/OSII是源码公开的嵌入式实时操作系统，其任务调度算法的实现颇为精彩。本文对该算法做了简要分析，指出对于一些有硬件算法指令的处理器，仅做移植并直接使用其软件算法是不明智的，相关硬件指令为μC/OSII的优化开辟了广阔的空间。

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

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

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

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

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/OSII在多处使用了上述调度算法。典型地，在事件控制块ECB中有：

INT8UOSEventTbl[OS_EVENT_TBL_SIZE];

INT8UOSEventGrp;

这里，OS_EVENT_TBL_SIZE 的默认值为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,用来以空间换时间，加快优先级查找速度：

INT8UOSTCBX;/*=priority & 0x07;*/

INT8UOSTCBY;/*=priority >> 3;*/

INT8UOSTCBBitX;/*=OSMapTbl[priority & 0x07];*/

INT8UOSTCBBitY;/*=OSMapTbl[priority >> 3];*/

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

2 优先级算法指令

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

cntlzd (Count Leading Zeros Double Word)

cntlzw (Count Leading Zeros Word)

上述指令也可简称为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指令，可迅速找出优先级最高的那个任务。RISC类型的处理器，执行1条指令一般只需要1个CPU时钟周期。执行该指令，仅一个CPU时钟周期就可完成对64个不同优先级任务的判选。在这类处理器上直接移植和套用μC/OSII软件算法，显然不合理。

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

来源：维库开发网