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

摘 要：根据μC/OS2Ⅱ实时嵌入式系统内核的特殊性，在原有优先级调度算法的基础上，提出了两种通过增加优先级数目来增大内核可管理任务数的算法，其中，一种方法是直接扩展指向任务优先级的索引范围，从而实现优先级数的增加；另一种方法是增加索引实现优先级数的增加。这两种方法都可以把优先级数从64个扩展到256个。最后，对两种改进方法进行比较，找出一种较好的方法。

关键词：μC/OS2Ⅱ；就绪表；优先级；任务调度

引 言

实时系统是对时间有特殊要求的系统，系统运行结果的正确性不仅要求系统的逻辑正确，而且依赖于运行结果产生的时间。尤其是硬实时系统，具有明确的实时参数，如果在某个限定的时刻前不能完成任务将导致整个应用的失败。μC/OS2Ⅱ是一个为实时嵌入式应用而设计的抢占式多任务的实时操作系统，全部μC/OS2Ⅱ的函数调用与服务执行时间是可知的。在μC/OS2Ⅱ中，涉及到的重要概念有实时内核、任务间的通信、任务切换与调度、任务优先级分配、任务间的竞争、死锁等。其中，内核负责管理各个任务，为每个任务分配CPU时间，并负责任务之间的通信。μC/OS2Ⅱ内核最多可以管理64个任务，其中系统保留了8个任务，用户最多可以有56个应用任务。因此，当工程的复杂性增大，在μC/OS2Ⅱ操作系统上运行的任务数目不断增加时，如果任务数目超过64个，就必须换用其他的开发平台，这样就可能造成大量的前期开发工作作废。我们考虑到这种情况，根据μC/OS2Ⅱ本身的任务可扩展性，在原有的优先级调度算法基础上，提出了两种可行的大量增加可管理任务的算法。

基于优先级的抢占式调度算法

　　当系统响应时间很重要时，要使用占先式内核。μC/OS2Ⅱ的实时内核就是占先式内核。其特点是能够确定最高优先级的就绪任务什么时候可以执行，可以得到CPU的控制权，从而使任务级响应时间得以最优化。相应地，μC/OS2Ⅱ内核采用的是基于优先级的抢占式调度策略。系统为每个任务分配一个优先级，最高优先级的任务一旦就绪，总能得到CPU的控制权。当一个运行着的任务使一个比它优先级高的任务进入了就绪态，当前任务的CPU使用权就被剥夺了，或者说被挂起了，那个高优先级的任务立刻得到了CPU的控制权。

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

　　为增加μC/OS2Ⅱ内核可管理任务的数目，该算法利用μC/OS2Ⅱ原有的优先级判定表格，重新定义了存放任务优先级的字节，并重新建立任务就绪表，把64个任务扩充到256个任务，最后给出了新的最高就绪任务的查找算法。

对优先级字节的改动和规定
在μC/OS2Ⅱ中，原有的基于64个任务调度的优先级调度算法分别用3个比特位来定位任务优先级在就绪表(readylist) 中的行和列，即0～2位标识该任务在总就绪表中的列信息，3～5位标识该任务在就绪表中的行信息。因此，存放任务优先级的字节中8个比特位只会用到6位，而有两个比特位空闲。该算法直接扩展定位就绪任务优先级在就绪表中位置的行和列信息的比特位，使其能够区分256个不同的任务优先级。扩展后的算法规定任务优先级字节的定义如图1所示。


将任务放入就绪表
套用μC/OS2Ⅱ中定义的就绪表变量OSRdyGrp和OSRdyTbl[ ]，仍旧用变量OSRdyGrp来表示优先级在就绪表中所在的行，在OSRdyGrp中，任务按优先级分组，16个任务为一组。OSRdyGrp的每一位表示16组任务中是否有进入就绪态的任务，如果存在进入就绪态的任务，则相应位置为1。使用OSRdyTbl[]数组(根据上面的扩展规则将该数组的大小由原来的8位扩展为16位) 表示优先级在就绪表中的列信息，即存放每个优先级的任务是否就绪的信息，如果某一位对应的任务处于就绪态，则将该位的值置为1。

例如，OSRdyTbl[0]对应优先级为0～15的任务，OSRdyTbl [1]对应优先级为16～31的任务，依次类推，OSRdyTbl[15]对应优先级为240～255的任务。优先级为78的任务处于就绪状态，不仅要将OSRdyTbl[4]的第14位置1，而且要将OSRdyGrp的第4位置1。也就是说只要OSRdyTbl[n ]中有一位为1，则OS2RdyGrp的第n 位就为1。变量OSRdyGrp和OSRdyTbl[]之间的关系如图2所示(图2中OSRdyGrp下表格中标注的数字0～15仅为清楚起见表示16组任务，并非表示OSRdyGrp中每一位的状态信息，同理，OSRdyTbl[ ]下表格中的数字0～255也仅表示256个任务，并非实际存放的状态信息) 。



把任务放入就绪表的程序是:
OSRdyGrp| =OSMapTbl[prio> > 4]；
OSRdyTbl[prio> > 4]| =OSMapTbl[prio& 0X0F]；
其中，char OSMapTbl[]={0X01，0X02，0X04，0X08，0X10，0X20，0X40，0X80，0X0100，0X0200，0X0400，0X0800，0X1000，0X2000，0X4000，0X8000} ，用于限制OSRdyTbl []数组的元素下标在0到15之间，prio表示任务的优先级。

从就绪表中删除任务
当优先级为prio任务脱离就绪状态时，可清除OSRdyGrp和OSRdyTbl[]中的对应该任务的位：
if ( (OSRdyTbl[prio> > 4]& =～OSMapTbl[prio& 0X0F]) ==0)
　OSRdyGrp& =～OSMapTbl[prio> > 4]；

以上代码将就绪任务表数组OSRdyTbl []中相应元素的相应位清零，而对于OSRdyGrp，只有当被删除任务所在的任务组中，全组任务一个都没有进入就绪态时，才将相应位清零。也就是说，OSRdyTbl [prio> > 4]所有的位都是0时，OSRdyGrp的相应位才清0。

判定最高优先级就绪任务的方法
在μ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]；

判定最高优先级就绪任务的方法
使用以上方法建立就绪表之后，我们仍然可以利用原有的优先级判定表格OSUnMapTbl ( [256]) ，对最高优先级就绪任务进行查找，并且不需要象第一种方法那样增加变量。具体的查找算法如下：
if ( (OSRdyGrp[0]& 0XFF) ! =0) {
　y=OSUnMapTbl[OSRdyGrp[0]]；
　x=OSUnMapTbl[OSRdyTbl0[y]]；
　prio=( y< < 3) + x；}
else if ( (OSRdyGrp[1]& 0XFF) ! =0) {
　　y=OSUnMapTbl[OSRdyGrp[1]]；
　　x=OSUnMapTbl[OSRdyTbl1[y]]；
　　prio=( y< < 3) + x+ 64；}

　　else if ( (OSRdyGrp[2]& 0XFF) ! =0) {
　　　y=OSUnMapTbl[OSRdyGrp[2]]；
　　　x=OSUnMapTbl[OSRdyTbl2[y]]；
　　prio=( y< < 3) + x+ 128；}
　　　else{
　　　　y=OSUnMapTbl[OSRdyGrp[3]]；
　　　　x=OSUnMapTbl[OSRdyTbl3[y]]；
　　　　prio=( y< < 3) + x+ 192；}

两种方法的比较

上面详细介绍了扩展μC/OS2Ⅱ内核可管理任务数目的两种方法。下面从几个方面讨论两种改进的调度算法的优劣。首先，从代码数量上看，第一种方法代码数量要远少于第二种方法，这也就意味着第一种方法的代码平均执行时间必然少于第二种方法的代码执行时间；其次，从把就绪任务放入就绪表的所用时间来看，第一种方法可以直接确定位置，将就绪任务放入就绪表，而第二种方法中，必须顺序查找，然后才能确定就绪任务在就绪表中的位置，第一种方法所用时间明显少于第二种方法；最后，从查找最高优先级就绪任务所需的时间来看，第一种方法通过变量ox和oy直接确定所有就绪任务中的哪一个任务优先级最高，而第二种方法必须从最高优先级开始顺序查找，直到找到第一个处于就绪状态的任务才结束查找，这种方法花费的时间显然要比第一种方法多。是否能够快速判定最高优先级就绪任务是整个调度算法的最关键问题，因此通过以上分析，可以看出第一种方法显然要大大优于第二种方法。

综上所述，我们在利用μC/OS2Ⅱ源码公开的基础上，对原有的内核任务优先级调度算法进行修改，介绍了两种不同的方法把可管理任务从原来的64个增加到256个，使其可应用于多于64个任务的复杂的工程项目开发。并且通过比较得出结论，第一种算法要优于第二种算法，第一种算法在理论上更简洁清楚，并且更加易于实现，已经在实际的开发中得到应用。