uCOS-II优先级任务调度在PowerPC上的移植和优化
1 基于优先级的任务调度
一个基于优先级的实时多任务内核的任务调度机制需要实现下面三个核心的处理功能：
◆ 将任务置于就绪态；
◆ 将任务取消就绪态；
◆ 找出最高优先级的就绪态任务。
在32位机上运行64个任务，可使用两个32位的整型变量数组OSRdyTbl [2]，建立一个64位的任务就绪态向量;每一位表示对应优先级的任务是否处于就绪态，例如OSRdyTbl [0]的第4位为1表示优先级为4的任务处于就绪态。构造如下的三个函数，用来完成设置任务就绪、取消任务就绪和寻找当前最高优先级的就绪任务。
上述代码可在任何处理器上实现所需的功能，没有考虑任何的优化和改进。通过这样的原理性函数，可以更好地理解多任务内核的任务调度。
寻找最高优先级就绪态任务的函数调用频率高，其执行时间直接影响内核的任务切换延迟时间，影响系统实时性。上述寻找最高优先级的就绪态任务的代码，随当前就绪任务的优先级不同，其循环次数也不同，导致其运行时间不确定。
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];
OSPrioHighRdy = (INT8U)((y 3) + OSUnMapTbl[OSRdyTbl[y]]);
μC/OS的任务调度算法采用了以空间换时间的策略，将特定字节值的最低位1所在位的信息预先计算并保存到表中，运行时通过查表快速得到；每个任务的TCB中除了保存优先级信息本身外，还使用额外的4个字节保存优先级的高低3位和对应的OSUnMapTbl值，以避免运行时实时计算这几个值所带来的延迟。这些措施增加了系统ROM和RAM的开销。
评论