μC/OS优先级调度机制在PowerPC上的优化

    μC/OS是Jean J.Labrosse开发的实时多任务内核，最初是为Motorola 8位处理器68HC11写的。在后来的相关著作中，作者将代码移植到了PC上，以便于更多的读者学习。μC/OSII继承了μC/OS的算法，有执行效率高、占用空间小、实时性强和可扩展性好等特点，被移植到几乎所有类型的CPU上，成为在嵌入式领域非常有影响力的RTOS。然而，由于该实时内核是为8位CPU设计的，对于那些具有优先级算法硬件指令的CPU，仅做移植是很不够的。

    1  基于优先级的任务调度

    一个基于优先级的实时多任务内核的任务调度机制需要实现下面三个核心的处理功能：

    将任务置于就绪态；

    将任务取消就绪态；

    找出最高优先级的就绪态任务。

    在32位机上运行64个任务，可使用两个32位的整型变量数组OSRdyTbl [2]，建立一个64位的任务就绪态向量;每一位表示对应优先级的任务是否处于就绪态，例如OSRdyTbl [0]的第4位为1表示优先级为4的任务处于就绪态。构造如下的三个函数，用来完成设置任务就绪、取消任务就绪和寻找当前最高优先级的就绪任务。

    void SetTaskRdyBit(INT8U Prio){/*设置任务就绪态*/

    if(Prio>32) OSRdyTbl [1] |= (1 << (63Prio) );

    else OSRdyTbl [0] |= (1 << (31Prio) );

    }

    void ClrTaskRdyBit(INT8U Prio){ /*取消任务就绪态*/

    if(Prio>32) OSRdyTbl[1] &= ~(1 << (63Prio) );

    else OSRdyTbl[0] &= ~(1 << (31Prio) );

    }

    INT8U FindHigheSTRdyTask(void){ /*寻找最高优先级的就绪态任务*/

    INT32U temp;//中间变量

    INT8Uprio=0;

    if(OSRdyTbl[0] != 0){

    temp = OSRdyTbl[0];//就绪态任务中优先级最高者在OSRdyTbl[0]中

    }

    else{

    temp = OSRdyTbl[1]; //就绪态任务中优先级最高者在OSRdyTbl[1]中

    prio +=32;

    }

    while(temp <0x80000000){//逐位查找就绪态任务中优先级最高者

    temp <<=1;

    prio ++;

    }

    return(prio);

    }

    上述代码可在任何处理器上实现所需的功能，没有考虑任何的优化和改进。通过这样的原理性函数，可以更好地理解多任务内核的任务调度。

    寻找最高优先级就绪态任务的函数调用频率高，其执行时间直接影响内核的任务切换延迟时间，影响系统实时性。上述寻找最高优先级的就绪态任务的代码，随当前就绪任务的优先级不同，其循环次数也不同，导致其运行时间不确定。

    2  μC/OS的任务调度实现方法

    μC/OS和μC/OSII是为8位CPU写的，采用8位机算法，支持64个任务。使用8个字节的OSRdyTbl全局数组，表示所有任务的就绪态信息：1为任务就绪，0为非就绪。数组第一个字节的b0位代表64个任务中优先级最高的任务，最后一个字节的b7位代表优先级最低的空闲任务，永远为1。当OSRdyTbl 数组的数据不为0时（表示对应的8个任务中至少有1个进入就绪态），另一个单字节全局变量OSRdyGrp 中的相应位要置1。当任务状态发生变化时，需更新OSRdyGrp和OSRdyTbl中对应的位。

    寻找最高优先级的就绪任务时，μC/OS使用了预先固化的256字节的对照表OSUnMapTbl，给出特定字节值的最低位1所在位的信息。查表算法避免了逐位检测各优先级位引起的执行时间的不确定性，程序简单，执行速度快，与就绪任务多少和优先级无关。

    对于取值0～63的任务优先级，μC/OS将其划分成高3位的Y和低3位的X，并保存在其任务控制块TCB的OSTCBX和OSTCBY中，其对应的OSUnMapTbl的值保存在OSTCBBitY和OSTCBBitX变量中，以提高运算速度。为了避免函数调用所带来的额外开销，μC/OS直接用语句实现如下的三部分功能。

    ① 设置任务进入就绪态

    OSRdyGrp |= ptcb>OSTCBBitY;

    OSRdyTbl[ptcb﹥OSTCBY] |= ptcb>OSTCBBitX;

    ② 设置任务退出就绪态。

    y = OSTCBCur>OSTCBY;

    OSRdyTbl[y] &= ~OSTCBCur>OSTCBBitX;

    if (OSRdyTbl[y] == 0) {

    OSRdyGrp &= ~OSTCBCur>OSTCBBitY;

    }

    ③ 寻找最高优先级的就绪态任务。以OSRdyGrp的值做偏移量，查OSUnMapTbl表，得到1个0到7的数Y，作为优先级高3位，再根据Y的值，找出OSRdyTbl中对应的字节，并且再次查OSUnMapTbl表，得到1个0到7的数X，作为优先级低3位的值，通过将Y左移3位再加上X的值，得到就绪任务中优先级最高的那个。

    y = OSUnMapTbl[OSRdyGrp];

    SPrioHighRdy = (INT8U)((y << 3) + OSUnMapTbl[OSRdyTbl[y]]);

    μC/OS的任务调度算法采用了以空间换时间的策略，将特定字节值的最低位1所在位的信息预先计算并保存到表中，运行时通过查表快速得到；每个任务的TCB中除了保存优先级信息本身外，还使用额外的4个字节保存优先级的高低3位和对应的OSUnMapTbl值，以避免运行时实时计算这几个值所带来的延迟。这些措施增加了系统ROM和RAM的开销。

    3  利用PowerPC“数出前导零数目”指令实现任务调度

    PowerPC是Motorola 、IBM和Apple三家公司于20世纪90年代初期联合设计的32位CPU。Freescale（其前身是Motorola半导体部）发展了针对汽车电子的MPC5xx系列单片机及后续基于e200内核的MPC5xxx系列单片机；更高端的e500、e600内核是用于通信领域的MPC6xxx、7xxx和8xxx系列。

    下面对μC/OS任务优先级调度算法的改进和优化是在MPC5554单片机上实现的。

    PowerPC处理器具有一条“数出前导零数目” 的指令cntlzw(count leading zero word)，可以以硬件指令方式实现优先级的多任务调度算法。这条指令也可用于图像处理和算法加密的场合。该指令数出一个32位寄存器中前置零的数目，例如，返回0表示b0不为零，即没有前导零；返回3表示b3不为零，b3位的前面从b0到b2共有3个零；返回32表示RS寄存器中所有的位都为零。（在PowerPC架构中，最高位MSB表示为b0，低位MSB根据位宽表示为b7、b15或b31。）

    利用这条指令，用汇编语言改写寻找最高优先级的就绪任务的函数，则不需要进行循环移位判断，可以直接从64个任务中找出优先级最高的那个任务。代码如下：

    asm INT8U FindHighestRdyTask(void){

    lisr5,OSRdyTbl@ha//让r5寄存器指向OSRdyTbl[]

    orir5,r5,OSRdyTbl@l

    lwzr3,0(r5)//将OSRdyTbl[0]的值载入r3寄存器

    cntlzwr3,r3//计算OSRdyTbl[0]中前导零数目

    cmpi0,0,r3,32//判断前32个任务是否就绪

    bne __FindEnd//如果前导零数目为32，说明前32个任务均未就绪，需要从后32个任务中寻找

    lwzr4,4(r5)//将OSRdyTbl[1]的值载入r4寄存器

    cntlzwr4,r4//计算OSRdyTbl[1]的前导零数目

    addir3,r4,32//后32个任务需要加上偏移量

    __FindEnd:

    blr //返回值保存在r3寄存器中

    }

    在这段代码中，首先判断前32个任务是否有处于就绪态的，如果没有的话，再对后32个任务进行判断。由于优先级最低的空闲任务总是处于就绪态，所以后32个任务总能返回一个有效值。该代码在前32个任务有就绪态时运行7条指令，在前32个任务均没有就绪时需要执行10条指令；而μC/OS原有的代码编译出来的汇编程序，则需要运行15条指令。

    使用这个方法的另一个好处是不再需要使用256字节的OSUnMapTbl表，任务控制块TCB也不需要使用OSTCBX、OSTCBY和OSTCBBitY、OSTCBBitX变量，每个ECB中也不再需要OSRdyGrp，这也减少了对ROM和RAM的占用。

    4  改进扩展任务数的优先级调度性能

    当对μC/OSII支持的任务数进行扩展时，按照μC/OSII原有的做法，需要按照高低字节分别查找OSUnMapTbl对照表。任务数为256时，寻找最高优先级就绪任务的函数将需要运行约35条指令。数出前导零数目的指令在这种情况下的作用将更加显著，对于32位PowerPC处理器，精心设计的代码可以做到仅需10条指令就将任务数扩展到1024个。

    此时OSRdyGrp扩展为32位，OSrdyTbl扩展成32个32位的数组。从OSRdyGrp得到的前导零数目，就是任务优先级高5位的值，乘以4可以得到该字的相对偏移地址；在OSRdyTbl中，定义高位对应高优先级任务，低位对应低优先级任务，则其前导零数目就是任务优先级低5位的值，和高5位的值移位相加就得到完整的任务优先级。通过将OSRdyGrp和OSRdyTbl定义成结构体，利用结构体首地址的相对寻址来分别读取其数值，可以减少一次取地址的操作。

    寻找最高优先级就绪态的最终代码如下：

    typedef struct {//定义结构体

    INT32U Tbl[32];

    INT32U Grp;

    } OSTaskRdyBlock;

    OSTaskRdyBlock  OSRdy;//定义全局变量OSRdy

    asm INT16U FindHighestRdyTask(void){

    lisr5,OSRdy@ha//将OSRdy结构体指针载入r5寄存器

    orir5,r5,OSRdy@l

    lwzr3,128(r5)//OSRdy.Grp在结构体中具有固定偏移量

    cntlzwr3,r3//数出OSRdyGrp的前导零数目

    slwir6,r3,2//得到OSRdyTbl的地址偏移量

    lwzxr4,r6,r5//通过结构体指针，读取OSRdy.Tbl的对应字

    cntlzwr4,r4//计算OSRdyTbl对应字的前导零数目

    slwir3,r3,5//任务优先级高5位移位

    addr3,r4,r3//和优先级低5位相加，得到完整优先级

    blr//返回

    }

    在64位的PowerPC 更有cntlzd(Count Leading Zero Double word)指令，一次就可以找出64个任务中优先级最高的那个，就更没有必要使用μC/OSII中的算法了。

    5  总结

    RTOS实时内核μC/OS和μC/OSII中，任务调度算法巧妙，性能优异，在嵌入式应用领域很有影响力，被移植到各种CPU上。然而由于是为8位CPU设计的，对于那些具有优先级硬件算法指令的16/32/64位CPU，μC/OSII的软件算法就完全失去了优势。应该利用这类CPU的特有指令，优化任务调度算法，使RTOS的实时性达到最佳。对于这类处理器，仅移植μC/OSII软件算法是很不够的，应该利用相关硬件算法指令。