μ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。

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