引言

优先级反转问题在实时系统中普遍存在，不同的实时内核给出了不同的解决方案，μC/OSII采用的是优先级置顶解决方案。采用优先级置顶，其不足之处是很明显的，主要有以下3点：

① 假设申请互斥资源R优先级最高的任务为T1，优先级值为M，为R指定的优先级值为N，N<M。若M ≠ N+1，则当T1占有R运行时，优先级值在N与M之间的任务无法抢占T1，这也造成了优先级反转。

② 预先指定一个固定的优先级值，显得灵活性不够。当系统发生变动、需要改变其值时，可能出现找不到合适值、要占用其他任务优先级值的情况，从而引起连锁反应，使系统改动变大，同时加大了开发的难度。

③ μC/OSII现在稳定运行的版本中，可设定的优先级值为0～63，保留4个最高优先级0～3和4个最低优先级60～63后，留给用户任务的为56个。若有多个临界资源，将会占用多个优先级，这样一来μC/OSII可管理的用户任务数将十分有限，使一些复杂的嵌入式应用在μC/OSII上无法实现。

笔者在仔细分析μC/OSII的任务调度算法和优先级置顶实现原理后，模仿优先级继承，提出了基于调度标识继承的优先级反转解决方案。与优先级置顶相比，时间上没有节省，但不用预先指定一个优先级值，不会占用用户任务可使用的优先级。

1基于调度标识继承的解决方案

1.1调度标识

在μC/OSII任务调度算法中，任务优先级值的低3位确定了任务在总就绪表OSRdyTbl[]的所在位，高3位确定了在OSRdyTbl[]数组中的索引号。任务控制块ptcb的一些属性记录着这些关系（prio为任务优先级值）：

ptcb>OSTCBY=（INT8U）（prio >> 3）;//在OSRdyTbl[]中索引号

ptcb>OSTCBBit=（INT8U）（1 << ptcb>OSTCBY）;//置位掩码

ptcb>OSTCBX=（INT8U）（prio & 0x07）;//在OSRdyTbl[]中对应位

ptcb>OSTCBBitX=（INT8U）（1<<ptcb>OSTCBX）;//对应位置位掩码

将ptcb加入就绪表所作的操作为：

OSRdyGrp |=ptcb>OSTCBBitY;

OSRdyTbl[ptcb>OSTCBY] |=ptcb>OSTCBBitX;

将OSRdyGrp和OSRdyTbl[]中对应位置1后，表示ptcb已经就绪，可以参与调度了。而寻找就绪表中的最高优先级任务，完全是根据OSRdyGrp 和OSRdyTbl[]的值来计算的，与具体的任务已没有什么关系了。先找到一个最高优先级值，再去寻找对应的任务。

在分析了μC/OSII的任务调度后，可以看到ptcb在就绪表中的位置完全取决于OSTCBY和OSTCBX的值。虽然在创建任务时，OSTCBY和OSTCBX是根据任务优先级值来初始化的，但在后期的调度中，并没有使用任务优先级值，而是直接使用OSTCBY和OSTCBX的值。我们将OSTCBY和OSTCBX的组合称作“调度标识”。

1.2调度标识继承的基本思路

假设有低优先级任务ptcb1和高优先级任务ptcb2，ptcb1已占有互斥资源R，ptcb2在运行中也要使用R。调度标识继承就是让ptcb1继承ptcb2的调度标识，而不是直接继承优先级，ptcb1以ptcb2的调度标识参与任务竞争调度。若从任务就绪表中找到的最高优先级值为ptcb2的优先级值，寻找对应的任务时，使它不是找到ptcb2，而是ptcb1。实现这一寻找过程可以用一个全局数组来实现：OSPrio[64]={0,1,2，...，63}。64表示有64个优先级值，初始状态时，OSPrio[n]=n。当发生调度标识继承后，如优先级值为m（m>5）的任务继承了优先级值为（m-5）的任务的调度标识，则令OSPrio[m-5]=m。从任务就绪表中找到的最高优先级值为（m-5）时，调度优先级值为OSPrio[m-5]的任务，即优先级值为m的任务。实现代码为：

OSPrioHighRdy=OSPrio[OSPrioHighRdy];

数组下标OSPrioHighRdy是从任务就绪表中找到的最高优先级值，通过OSPrio[]进行一次转换得到要运行任务的优先级值。以上就是调度标识继承解决方案的基本思路，并没有继承高优先级任务的优先级，只是在任务调度中继承了它的调度标识，所以也称为模仿优先级继承的解决方案。调度标识的继承是在高优先级任务申请互斥资源时实现，而恢复低优先级任务的调度标识则是在低优先级任务释放互斥资源时实现的。

1.3可行性分析

该解决方案是否正确，改动后的系统是否能安全、稳定地运行，需要经过严格证明后才能应用于实际开发中。ptcb1继承了ptcb2的调度标识，在运行中ptcb1与ptcb2会不会发生冲突？ptcb1使用ptcb2的调度标识，在任务调度以外的其他部分能否正常运行？当优先级高于ptcb2的任务ptcb3也申请互斥资源时，能否应付？这些问题是采用该方法后不得不考虑的。

当ptcb1已占有互斥资源而ptcb2申请时，会进入该互斥资源的等待列表。若没有定义等待超时，在ptcb1占有互斥资源的过程中，ptcb2始终处于挂起状态，不会参与任务调度，ptcb1与ptcb2始终处于隔离状态；若定义了等待超时，当因等待超时使ptcb2就绪时，通过修改OSPrio[]数组就可以恢复ptcb2的正常任务调度。虽然ptcb1继承了ptcb2的调度标识，但ptcb1与ptcb2不会发生任何冲突。

在μC/OSII中与调度标识发生联系的除了任务就绪表外，就只有事件等待列表了。当某个事件发生后，要将事件等待列表中最高优先级任务置于就绪态。事件等待列表与任务就绪表的构造原理是一样的，在寻找最高优先级任务时，也是先计算出最高优先级值后再去寻找对应的任务。若从事件等待列表中计算得到的最高优先级值为ptcb2的优先级值，也可通过全局数组OSPrio[]转换得到要运行任务的优先级值，即ptcb1的优先级值，这样就可找到ptcb1。经过少量的改动后，ptcb1使用ptcb2的调度标识，在任务调度以外的其他部分就能够正常运行了。

ptcb1已继承了ptcb2的调度标识，当优先级高于ptcb2的任务ptcb3也申请互斥资源时，将ptcb1的调度标识改为ptcb3的调度标识，数组OSPrio[]作相应的变动，即可实现ptcb3取代ptcb2。所以发生这种情况时，是完全能够应付的。

得益于μC/OSII完全开源的内核，采用调度标识继承的解决方案带来的影响都可以显性地评估出来。在回答了以上3个问题后，可以看出该方法与原有内核结构不存在冲突，是完全可行的。

1.4调度标识继承的实现

μC/OSII用互斥型信号量来实现对互斥资源的独占式处理，互斥型信号量也称作mutex。实现调度标识继承，在μC/OSII原有代码基础上主要修改了与mutex有关的函数和需要计算最高优先级的函数，下面将详细说明需要修改的地方。

在创建mutex的函数OSMutexCreate（）中,不用预先为mutex设定一个优先级值，因为预先占用而标识一个优先级值不可用的代码都可以去掉。变量OSEventCnt的高8位初始为0x00，低8位初始为0xFF。在以后的处理中，若OSEventCnt的高8位为0x00,表示没有发生调度标识继承，否则记录着调度标识被继承的任务的优先级值；若OSEventCnt的低8位为0xFF，表示没有任务占有mutex，否则记录着占有mutex的任务的优先级值。

对mutex的处理，仍以低优先级任务ptcb1和高优先级任务ptcb2为例来说明。当ptcb2申请已被ptcb1占有的mutex时，在OSMutexPend（）函数中，将ptcb1的调度标识修改为ptcb2的调度标识，变量OSEventCnt高8位改为ptcb2的优先级，低8位记录ptcb1的优先级，同时修改数组OSPri[]。实现代码如下：

ptcb1 >OSTCBY=ptcb2 >OSTCBY;

ptcb1 >OSTCBBitY=ptcb2 >OSTCBBitY;

ptcb1 >OSTCBX=ptcb2 >OSTCBX;

ptcb1 >OSTCBBitX=ptcb2 >OSTCBBitX;//ptcb1继承了ptcb2的调度标识

OSPrio[ptcb2 >OSTCBPrio]=ptcb1 >OSTCBPrio;//修改数组OSPrio[]

ptcb1继承了ptcb2的调度标识后，若ptcb2是最高优先级任务，则在OS_Sched（）函数中计算出来的最高优先级值OSPrioHighRdy是ptcb2的优先级。要找到任务ptcb1需加入一句代码：

OSPrioHighRdy=OSPrio[OSPrioHighRdy];

通过全局数组OSPrio将OSPrioHighRdy转化为ptcb1的优先级，这样实际运行的任务将会是ptcb1。

ptcb1使用ptcb2的调度标识，若ptcb1进入某事件的等待列表，那么该事件发生后，会寻找事件等待列表中优先级最高的任务。若ptcb2是最高优先级任务，则在OS_EventTaskRdy（）函数中计算出来的最高优先级值prio是ptcb2的优先级。要找到ptcb1，只需加入一句代码“prio=OSPrio[prio];”将计算出来的最高优先级值转化为ptcb1的优先级。

当ptcb1释放mutex时，根据ptcb1的优先级恢复ptcb1的调度标识，修改OSPrio[]，同时变量OSEventCnt的高8位恢复为0x00，低8位恢复为0xFF。实现代码如下：

ptcb1>OSTCBY=（INT8U）（ptcb1>OSTCBPrio>> 3）;

ptcb1>OSTCBBitY=（INT8U）（1 << ptcb1>OSTCBY）;

ptcb1>OSTCBX=（INT8U）（ptcb1>OSTCBPrio & 0x07）;

ptcb1>OSTCBBitX=（INT8U）（1 << ptcb1>OSTCBX）;//恢复了ptcb1的调度标识

OSPrio[ptcb2>OSTCBPrio]=ptcb2>OSTCBPrio;//恢复OSPrio[]数组

OSEventCnt=（OSEventCnt | 0xFF） & ~（0xFF<<8）; //恢复变量OSEventCnt

有一种特殊情况，ptcb2在申请mutex时定义了等待超时。当出现等待超时后，ptcb2虽没有获得mutex也会进入任务就绪表，参与任务调度。此时只需在使ptcb2就绪的函数中加入一句代码：

OSPrio[ptcb2>OSTCBPrio]=ptcb2>OSTCBPrio;

这样ptcb2就可以正常地参与任务调度了。

以上用伪代码描述了主要的改动部分，但在一些细节改动上并没有详细地介绍，例如if语句中判断条件的改变、某些代码先后顺序的改变。

2测试结果

完成代码的改动后，在S3C2440开发板上进行了多种情况下的测试，均能按预期正常地运行。这里，以一种情况为例来说明：有3个任务T1、T2、T3，任务优先级T1<T2<T3；T1、T3要使用mutex，T2不需要；3个任务开始运行的先后顺序依次为T1、T2、T3。运行结果如图1所示。

图1运行结果

从结果可看出，在T3挂起后T1成功地继承了T3的调度标识，优先于T2运行。T1可尽快地释放mutex，这样就有效地抑制了T2和T3的优先级反转。

3性能分析

在运行时间上主要关注任务调度所花的时间。因为要将计算得到的最高优先级值转化为要运行任务的优先级，所以增加了OSPrioHighRdy=OSPrio[OSPrioHighRdy]这样一行代码，增加了一次查找OSPrio[]数组的运算和一次赋值运算。在现在主流的微处理器上，增加的运行时间是很少的。以运行在200 MHz的ARM9处理器为例，增加的时间在0.01 μs级别，对于大多数实时应用来说，是可以接受的。

在存储空间上，只多了一个数组INT8U OSPrio[64]，增加了64字节的存储空间。虽然嵌入式系统对存储空间要求很严格，但对大多数应用来说，64字节的存储空间不会成为负担。

4总结与展望

优先级反转是实时内核都必须解决的问题，μC/OSII采取的是优先级置顶方案。本文针对优先级置顶的一些不足，提出了调度标识继承的解决方案，解决了优先级置顶预先占用优先级的问题。但同时也增加了运行时间和存储空间，对于那些对时间和空间要求非常苛刻的系统，可能会不适用；而且在改动后，笔者虽然进行了多种情况下的测试，但仍然可能有些特殊情况没考虑到，改动后的代码是否健壮，仍需进一步严格的论证。