μC/ OSⅡ优先级扩展的两种方法探讨

郝强 山东大学计算机科学与技术学院；济南职业学院 250103

μC/ OSⅡ优先级扩展的两种方法探讨

郝强 山东大学计算机科学与技术学院；济南职业学院 250103

在μC/ OSⅡ操作系统上运行的任务数目不断增加时，任务数目过多造成效率下降，本文根据μC/ OSⅡ本身的任务可扩展性，在原有的优先级调度算法基础上，提出了两种可行的大量增加可管理任务的算法。

实时操作系统；调度算法；实时性；优先级

1、引言

本文引入嵌入式操作系统μ C/OSII是一个多任务的实时内核,它具有嵌入式软件共有的可裁剪、低资源、低功耗等特点；作为实时操作系统除了要满足应用的功能需区域以外，更重要的是还要满足应用提出的实时性要求。

2、简介

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

3、用快表索引优先级

在μ C/ OSⅡ中，原有的基于64个任务调度的优先级调度算法分别用3 个比特位来定位任务优先级在就绪表(ready list) 中的行和列，即0～2 位标识该任务在总就绪表中的列信息，3～5 位标识该任务在就绪表中的行信息。因此，存放任务优先级的字节中8个比特位只会用到6位，而有两个比特位空闲。该算法直接扩展定位就绪任务优先级在就绪表中位置的行和列信息的比特位，使其能够区分256个不同的任务优先级。扩展后的算法规定任务优先级字节的定义如上图所示。套用μ C/ OS2 Ⅱ中定义的就绪表变量OSRdyGrp 和OSRdyTbl [ ]，仍旧用变量OSRdyGrp 来表示优先级在就绪表中所在的行，在OSRdyGrp 中，任务按优先级分组，1 6个任务为一组。OSRdyGrp 的每一位表示16 组任务中是否有进入就绪态的任务，如果存在进入就绪态的任务，则相应位置为1。使用OSRdyTbl[ ]数组(根据上面的扩展规则将该数组的大小由原来的8 位扩展为16 位)表示优先级在就绪表中的列信息，即存放每个优先级的任务是否就绪的信息，如果某一位对应的任务处于就绪态，则将该位的值置为1。例如，OSRdyTbl[0]对应优先级为0～15的任务，OSRdyTbl [1]对应优先级为1 6～3 1的任务，依次类推，OSRdyTbl[15 ]对应优先级为240～255 的任务。优先级为78 的任务处于就绪状态，不仅要将OSRdyTbl[4]的第14位置1，而且要将OSRdyGrp 的第4位置1。也就是说只要OSRdyTbl[n]中有一位为1，则OS2RdyGrp 的第n 位就为1。变量OSRdyGrp 和OSRdyTbl[ ]之间的关系如下图所示(图中OSRdyGrp 下表格中标注的数字0～15 仅为清楚起见表示16组任务，并非表示OSRdyGrp 中每一位的状态信息，同理，OSRdyTbl[ ]下表格中的数字0～255 也仅表示256 个任务，并非实际存放的状态信息)。

把任务放入就绪表的程序是:

0 X 0 1 0 0，0 X 0 2 0 0，0 X 0 4 0 0，0X0800，0X1000，0X2000，0X4000，0X8000}，用于限制OSRdyTbl [ ]数组的元素下标在0 到15 之间，prio 表示任务的优先级。

4、用线性表索引优先级

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

在这种方法中，用一个字节的最高两位存放索引信息(对应于下图中的OSRdyXY)，则意味着将就绪表分为4 个部分，因此，若要将任务放入就绪表，首先要通过索引信息确定任务优先级在就绪表中的哪个部分,然后再通过行和列信息确定任务优先级的具体位置。其中，变量OSRd y XY， OSRd y Grp [ ]以及OS2RdyTbl0[ ]～OSRdyTbl3[ ]的关系如左图所示，图中的数字0～255 仅为清楚起见表示索引信息或任务优先级，并非实际存放的状态信息。

将就绪任务放入就绪表的具体代码可用如下方法实现:

5、两种方法的比较

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

[1]吴旭光, 何军红. 嵌入式操作系统原理与应用[M]. 化学工业出版社. 2007.

[2]吴明晖. 基于ARM的嵌入式系统开发与应用. 人民邮电出版社.2004.

[3]Labrosse J J. 基于ARM的嵌入式系统开发与应用.北京：北京航空航天大学出版社.2003 .

10.3969/j.issn.1001-8972.2010.18.060