引言
μC/OSII的就绪表设置、清除、查找算法，是高效的、跨平台的程序。它使用了两个查找数组OSMapTbl[8]和OSUnMapTbl[256]，以提高查找就绪表的速度，尽快获取就绪任务的最高优先级。
CortexM3是ARM公司较新的一种架构版本，主要应用在单片机领域。基于它生产的32位芯片日益增多；CortexM3只支持Thumb2指令集，在效能和代码密度间能取得更佳的表现。
1在ARM上改动算法的因由利弊
由于就绪表操作是在关中断状态下运行的，其执行影响到系统的中断响应时间，因此就绪表操作算法的效率是衡量实时操作系统优劣的基准之一。
在CortexM3所用的指令集中，一些指令功能不可小觑，如前导零计数clz、字内位反转rbit、位清除bic。其中的clz和bic为μC/OS就绪表的高优先级获取算法指出了另一条道路。
（1） 改动后的优势
① 节省存储空间。不再使用查找数组OSMapTbl[8]和OSUnMapTbl[256]。设立这两个数组的目的，是为了提高查找就绪表的效率。
② 提升查找效率。clz是单周期指令，使用带移位的加法指令，大幅缩短运算时间。
③ 增加了μC/OSII支持的任务数量，从64提升到了1 024（2.84版支持的任务数量已经到了256，不过效率有所下降）。
（2） 存在的不足
① Realview MDK（这里使用的是3.20版及其指令模拟器）尚不支持在C语言程序中使用Thumb2指令内联汇编。使用内嵌汇编函数时，函数的调用（跳转返回）降低了执行效率。
② C语言对clz指令的支持尚有不足，故新算法跨平台性差。但鉴于ARM芯片应用广泛，指令又被ARM9之后的芯片广泛兼容，所以应用空间还算广阔。
2μC/OSII就绪表算法介绍与具体改动
μC/OSII就绪表是一个数组，数组元素一位的值（1或0）对应了一个任务就绪与否，该位在数组中的位置表示任务的优先级。当需要调度已就绪的最高优先级任务运行时，就在就绪表中查找该任务。
2.1μC/OSII就绪表算法简介
一种解决方法是，对数组各项依次判断是否为0：若>0,进入该项查找最小权的置1位位置；若=0，优先级加一个基数，查下一项，直至查到该优先级。
μC/OSII技高一筹，设置了一个对就绪表各项判断是否为0的变量，称之为就绪表组。就绪表组一位为0或1，对应就绪表一项的值是否为0。通过查找就绪表组最小权位的置1位位置，就确定了对应首个>0的就绪表项的下标，从而避免了循环，大幅度提高了效率。
2.2改动方式与源码
clz算法接受了μC/OSII的思路，再通过使用clz指令来进行优化。不同的是，clz是从右往左查，二进制的高权位对应高优先级，而μC/OSII优先级以值小为高。
考虑到有时用不到很多任务，这时用数组作就绪表不免浪费。因此当任务总数小于32时，就用32位无符号整数变量作就绪表。注意，此时就绪表组变量OSRdyGrp被当作就绪表使用。
常量OS_LES_TSK表示是否使用较小任务数，0表示使用最多32个任务，1表示使用最多1 024个任务。
常量RdySt是将32位整数的最高权位置1，以便移位使用。
2.3C语言实现
以下算法利用内嵌clz指令的函数编写，实现了指定优先级任务在就绪表的设置、清除，在就绪表中查找就绪任务的最高优先级。
#defineOS_LES_TSK 0
#defineRdySt #0x80000000
intOSRdyGrp ;//任务就绪表组,任务数<32当作就绪表用
intOSRdyTbl[32] ;//任务就绪表
//将优先级为prio的任务在就绪表置位
voidOSRdySET（unsigned shortprio） {
prio=prio;//设防某些编译器报错
//当任务总数<32时不编译OSRdyTbl[],以提升效率
#ifOS_LES_TSK
OSRdyGrp|=（RdySt>>prio）;
#else
//任务数在1~1 024之间，调度将多花些时间
//prio>>5：任务组OSRdyGrp需置1的位的位置，
//即OSRdyTbl[]下标
OSRdyGrp|=（RdySt>>（prio>>5））;
//prio & 31：按位与，取prio的低5位，设置数组元素
OSRdyTbl[prio>>5]|=（RdySt>>（prio & 31））;
#endif
}
//将优先级为prio的任务在就绪表清零
voidOSRdyCLR（unsigned shortprio） {
prio=prio;
#ifOS_LES_TSK//当任务总数<32
OSRdyGrp&=~（RdySt>>prio）;
#else
//任务数在1~1 024之间，调度将多花些时间
//prio>>5:就绪表组OSRdyGrp需清零的位的位置，
//即就绪表OSRdyTbl[]下标
//prio & 31:按位与，取prio的低5位，设置数组元素
OSRdyTbl[prio>>5] &= ~（RdySt>>（prio & 31））;
//若就绪表OSRdyTbl[]一项为零，则清零其对应的就
//绪表组的一位
if（OSRdyTbl[prio>>5]==0 ）
OSRdyGrp &= ~（RdySt>>（prio>>5））;
#endif
}
//前导零计数：内嵌汇编函数，可能降低执行效率
__asm unsigned shortClzGet（intOSRdyGrp） {
clz.w r0,r0
bx lr//不写也能返回，详见后文
}
//获取任务就绪组/表的最高优先级，前导零计数
//函数调用降低效率，可以将下面的语句写在别的函数中
unsignedshortOSPrioHighRdy（） {
unsignedshorty;
#ifOS_LES_TSK
//任务数<32，可以考虑将y定义为8位无符号整数
//unsignedchar y;
y=ClzGet（OSRdyGrp）;
#else
//任务数在1~1 024之间，调度将多花些时间
y=ClzGet（OSRdyGrp）;
y=ClzGet（OSRdyTbl[y]）+（y<<5）;
#endif
returny;
}
//检查执行结果是否正确，33是适合检查用的数值
intmain（） {
unsigned shortprio=0;
while（prio<1024） {
OSRdySET（prio）; //根据优先级设置任务就绪表位、组位
prio=OSPrioHighRdy（）; //获取就绪表中任务的最高优先级
OSRdyCLR（prio）;//根据优先级清除对应的
//就绪表位、组位
prio+=33;
if（prio>1023）
prio=0;
}
}
程序中的bx r14，有些资料上要求必须写，不过查看反汇编代码，编译程序已经给加上了。看来是编译程序已升级，会不会出错要看使用的编译器，建议还是按规范写上。由于内嵌函数调用返回耗时，查找算法未能充分发挥，需改进编译后的汇编代码以实现更高的效率，或使用汇编代码重写这部分程序。
2.4THUMB2汇编指令实现
用汇编语言写程序时的技巧：在最高优先级任务的设置、清除函数中，C语言运算符“|= ”对等汇编指令“orr”,“&= ~”对等汇编指令“bic”。这两条指令都可以进行预移位操作，大幅提高执行效率。可以查看反汇编源码，看C编译器是否利用了这一便利。
在查找函数中，可以省去C语言程序中的内嵌汇编调用，减少冗余指令。示意伪代码如下：
ldr r0,=OSRdyGrp ;加载就绪表组变量OSRdyGrp地址
ldr r1, [r0];取就绪表组变量OSRdyGrp值
#ifOS_LES_TSK
clz.w r0, r1;取最高优先级
#else
clz..w r0, r1;获取最高优先级所在就绪表项的下标
ldr r2,=OSRdyTbl;加载就绪表首地址
add.wr2, r2,r0,#2;计算最高优先级所在就绪表项地址
ldr r3, [r2];取该项的值
Clz.w r1,r3;取该项内的最高优先级
add.w r0,r1,r0 ,lsl #5;计算得到最高优先级
#endif
bx r14
可以看出，除了数据加载指令外，查找的核心算法仅3条指令（使用<32个任务时，仅1条指令）。不过在实际设计算法的时候，还需要考虑指令流水线停顿，方能达到最佳的效果。
2.5μC/OSII 2.84版相关源码介绍
以下是翻译整理后的μC/OSII优先级查找算法源码（2.84版），较长的注释是添加的算法说明。
/************************************
*查找就绪表中的最高优先级任务运行
*说明: 本函数被其他μC/OSII服务调用，以确保就绪表中的
*最高优先级任务最早被执行，全局变量“OSPrioHighRdy”也随
*之改变
*提示:①这是μC/OSII的内部函数，用户程序不要调用它
*② 该函数被调用时需要关中断
*************************************
//就绪优先级调度新算法，将优先级数由8×8=64扩展到
//16×16=256
staticvoidOS_SchedNew （void） {
#if OS_LOWEST_PRIO <= 63//参考最多提供64个优先级
INT8Uy;
/*数组OSUnMapTbl[256]的作用：
当给定一个位二进制无符号整数，如OSRdyGrp，怎么判断它被置1的最小权位是哪个，即如何从右往左查找第一个1出现的位置？当处理器没有现成的指令时，可以先将数的256种状况
存入数组OSUnMapTbl[256]中，判断最小权位时，查询数组
OSUnMapTbl[OSRdyGrp]即可*/
y = OSUnMapTbl[OSRdyGrp];
OSPrioHighRdy = （INT8U）（（y << 3） + OSUnMapTbl[OSRdyTbl[y]]）;
#else//现在能提供256个优先级
INT8Uy;//就绪表组，用1或0标记
有无就绪任务
INT16U *ptbl;//就绪表某一项指针，计算后确定是哪一项
/*当16位整数OSRdyGrp低8位不为零，获取就绪表组置1的最小权位0~7，
则获取8~15位*/
if （（OSRdyGrp & 0xFF） != 0） {
y = OSUnMapTbl[OSRdyGrp & 0xFF];
} else {
y = OSUnMapTbl[（OSRdyGrp >> 8） & 0xFF] + 8;
}
ptbl = &OSRdyTbl[y];/*就绪表数组某一项指针赋值*/
if （（*ptbl & 0xFF） != 0） {
OSPrioHighRdy = （INT8U）（（y << 4） + OSUnMapTbl[（*ptbl & 0xFF）]）;
} else {
OSPrioHighRdy = （INT8U）（（y << 4） + OSUnMapTbl[（*ptbl >> 8） & 0xFF] + 8）;
}
#endif
}
clz最高优先级查找算法，与μC/OS的新算法有所不同：返回的结果分别是8位、16位整数。这是因为8位已经不能表示>255的值;过程中clz算法更多地使用16或32位整数，以充分利用芯片性能。
3适用范围
等待任务列表使用了与就绪表操作相似的过程，注意要同时更改其数据类型和算法。算法虽然是在CortexM3上执行的，但适用于ARM9及其以后芯片。支持ARM指令集的芯片，可以在C语言中使用内嵌汇编，不必再编写汇编查找函数。
本文所叙述的算法适用于下述两种情况。
① 使用μC/OSII系统：
◆ 要求更多的任务优先级；
◆ 要求产品性能优越或是时间关键的应用，想进一步提高效率；
◆ 学习、研究或希望优化μC/OSII以扩展其应用范围。
② 未使用μC/OSII系统：
◆ 移植改造其他操作系统的就绪表算法；
◆ 编写新操作系统或执行调度程序；
◆ 编程爱好者借鉴、改进编程方法。