μC/OS2Ⅱ中优先级调度算法的改进及实现

在 μC/OS2Ⅱ中，采用基于优先级的可抢占式调度策略，系统为每一个任务分配一个优先级，调度程序总是选择优先级最高的就绪任务运行。内核运行中将频繁地进行任务调度，并且任务调度属于系统的临界资源，调度时需要独占CPU，不允许外部中断和任务切换。所以调度速度缓慢时，会影响整个系统的响应速度和处理能力。因此，如何快速查找最高优先级就绪任务就成为整个算法的核心问题之一。

该算法在扩展了系统可管理任务数目的同时，考虑了如何在任务数目增大时，还能够快速进行最高优先级就绪任务判定的问题，并给出了一种快速的判定方法。在介绍判定最高优先级就绪任务的方法之前，先描述μC/OS2Ⅱ中原有的优先级判定表格OSUnMapTbl ( [256])，该表格为16×16的数组，每个数组元素的值是固定的。当使用该表格时，数组下标转换为相应的八位二进制，其中高四位对应数组的行，低四位对应数组的列(假设最右边的一位是第0位bit0) ，由此就可查表判断一组任务就绪态任务中优先级最高的那个任务所在的位置(查表后返回的值在0到7之间) ，再经过计算，就可得到最高优先级就绪任务的优先级。

为了减少不必要的工作，在判定最高优先级就绪任务的方法中，利用了上面介绍的优先级判定表格OSUnMapTbl ( [256]) ，把改进后的优先级就绪表看作一个类似二维坐标的平面(如图3所示) ，使256个



任务优先级平均分布在4个象限中(图中的数字0～255表示256个任务优先级，每个位置实际存放的是任务优先级的状态信息) ，同时使用了两个变量ox和oy来共同确定任务的优先级所在象限，并由此进一步查找最高优先级的就绪任务。

变量ox和oy的取值情况如图3所示，下面的查找最高优先级算法首先从判断优先级所在的象限开始进行查找。具体代码如下：
oy=OSRdyGrp 0X00FF ；
if ( oy==0)
　y=OSUnMapTbl[OSRdyGrp> > 8]+ 8；
else
　y=OSUnMapTbl[oy]；
ox=OSRdyTbl[y] 0X00FF ；
if ( ox==0)
　x=OSUnMapTbl[OSRdyTbl[y]> > 8]+ 8；
else
　x=OSUnMapTbl[ox]；
prio=( y 4) + x；

例如，如果OSRdyGrp的值为0X0068，则利用上面的代码，首先可以判断oy! =0，则查优先级判定表格得到OSUnMapTbl[oy]的值为3，假设OSRdyTbl[3]的值为0X00E4，则可判断ox! =0，再查优先级判定表格得到OSUnMapTbl[ox]的值为2，最后计算得到任务的优先级prio为50。

μC/OS2Ⅱ中优先级调度算法的第二种改进方法

在μC/OS2Ⅱ中，原来的优先级调度算法只使用了一个字节中的6位，剩余两位空闲。在第一种改进方法中，我们是直接扩展了定位就绪任务优先级在就绪表中位置的行和列信息的比特位。现在介绍的第二种方法是利用原来存放优先级的字节中剩余的两位作为索引，重建就绪表，使任务优先级扩展到256个。这里需要增加一个变量OSRdyXY，用于存放索引信息，另外还要使用变量OSRdyGrp[]存放任务优先级的行信息，OSRdyTbl0[ ]，OSRdyTbl1[ ]，OSRdyTbl2[ ]和OSRdyTbl3[ ]4个8位数组用于存放每个优先级的任务是否就绪的信息。这种方法的任务优先级字节的定义如图4所示。

将任务放入就绪表

在这种方法中，用一个字节的最高两位存放索引信息(对应于图5中的OSRdyXY)，则意味着将就绪



表分为4个部分，因此，若要将任务放入就绪表，首先要通过索引信息确定任务优先级在就绪表中的哪个部分，然后再通过行和列信息确定任务优先级的具体位置。其中，变量OSRdyXY，OSRdyGrp[]以及OS2RdyTbl0[]～OSRdyTbl3[]的关系如图5所示，图中的数字0～255仅为清楚起见表示索引信息或任务优先级，并非实际存放的状态信息。

将就绪任务放入就绪表的具体代码可用如下方法实现：
OSRdyXY=prio> > 6；
OSRdyGrp[OSRdyXY]| =OSMapTbl[prio> > 3]；
if (OSRdyXY==0X00)
　OSRdyTbl0[prio> > 3]| =OSMapTbl[prio 0X07]；
if (OSRdyXY==0X01)
　OSRdyTbl1[(prio> > 3) 0X07]| =OSMapTbl[prio 0X07]；
if (OSRdyXY==0X02)
　OSRdyTbl2[(prio> > 3) 0X07]| =OSMapTbl[prio 0X07]；
if (OSRdyXY=0X03)
　OSRdyTbl3[(prio> > 3) 0X07]| =OSMapTbl[prio 0X07]；
其中，char OSMapTbl[]={0X01，0X02，0X04，0X08，0X10，0X20，0X40，0X80} ，prio表示任务的优先级。

从就绪表中删除任务

当任务脱离就绪态时，可以用下面的代码对存放该任务优先级的变量中的相应位清零：
OSRdyXY=prio> > 6；
if (OSRdyXY==0X00)
　if ( (OSRdyTbl0[prio> > 3] =～OSMapTbl[prio 0X07]) ==0)
　　OSRdyGrp[OSRdyXY] =～OSMapTbl[prio> > 3]；
if (OSRdyXY==0X01)
　if ( (OSRdyTbl1[(prio> > 3) 0X07] =～OSMapTbl[prio 0X07]) ==0)
　　OSRdyGrp[OSRdyXY] =～OSMapTbl[prio> > 3]；
if (OSRdyXY==0X02)
　if ( (OSRdyTbl2[(prio> > 3) 0X07] =～OSMapTbl[prio 0X07]) ==0)
　　OSRdyGrp[OSRdyXY] =～OSMapTbl[prio> > 3]；
if (OSRdyXY==0X03)
　if ( (OSRdyTbl3[(prio> > 3) 0X07] =～OSMapTbl[prio 0X07]) ==0)
　　OSRdyGrp[OSRdyXY] =～OSMapTbl[prio> > 3]；

判定最高优先级就绪任务的方法