一种可在实时系统中实现最高优先级任务选取的算法

(内蒙古财经学院 计算机信息管理系，内蒙古 呼和浩特 010070)
摘 要：文章主要从就绪任务的管理、最高优先级数获取 及选择最高优先级任务三个方面对该算法进行了阐述。
关键词：实时操作系统；任务分组；就绪表；逆映射表
中图分类号：TP316.2  文献标识码：A  文章编号：1007—6921(2009)13—0051—02

实时操作系统［1］(Real Time Operating System,简称RTOS)和分时操作系统不同， 分时操作系统注重系统的公平性，而实时操作系统主要体现实时性。一般情况下，为了保证 高的实时性，实时内核的任务调度［2］采用抢占式的优先级算法。文章所论述的内 容就是一种可在实时内核中实现的抢占式高优先级任务选取算法。
1 就绪任务的管理
1.1 任务分组

该算法先对任务进行分组，分组依据是把任务的优先级看作由两部分比特构成的整数：高位 若干比特表示组号，称组优先级；剩余低位部分表示同组但优先级不同的不同任务，称为子 优先级。分组具体如下：

假设系统中的任务集合为T={t_i｜0<i<系统允许的最大任务数+1}，函数P(t_i)为第i个任 务的优先级，定义优先级的n个高位比特表示分组号，m个低位为子优先级数，则函数Hn(P(t_i))表示任务t_i的分组号,函数Lm(P(t_i))为任务t_i的子优先级数。那么就可以依据 任务 的优先级分组号求出任务集合的一个划分［3］φ={ST_i|0<i<2ⁿ+1,任意t_k,t_j∈ST_i ,当Hn(P(t_k))=Hn(P(t_j))，0<k<系统允许的最大任务数+1，0<j<系统允许的最大任务数 +1}。当任意集合ST_i∈φ，则集合STi的分组号作为GN变量中表示该分组状态比特的位置 。例如上述的ST_i中有就绪的任务，且ST_i的分组号为x,则GN中第x个比特取值为1，否则 为0；按照上述的做法可把任务集分组，并且使用GN变量保存时也考虑了不同组的优先级。 如可以假定分组号越小，该分组的优先级越高。
1.2 建立就绪表

就绪表是一张静态的二维表,可按下面规则建立。

设就绪表为RT(Ready Table),则RT={v_i｜0≤i<最大的分组数}，v_i表示第i个一维向量 ，向量分量是比特。具有相同组优先级的任务状态由RT中的一个向量表示，则任务组和向量 的映射关系为：分组号=向量的编号。处于同组中具有不同子优先级的任务与向量中的比特 的映射关系为：任务子优先级=表示该任务的向量分量的位置。

按照上述的方法不但可以建立就绪表，同时又建立了任务优先级，GN及就绪表之间的映射关 系，如图1所示。


1.3 任务进入及退出就绪表


2 最高优先级数的获取

获取最高优先级数的一般方法是先检查GN找到最高组优先级，再检查RT表中的指定向量来确 定本组中最高子优先级，然后通过两者来得到当前最高的优先级。这种方法效率不高，文章 通过建立逆映射表的方法来直接获取最高优先级数。
2.1 逆映射表 

逆映射表是一张常量表，在操作系统的设计阶段就已经定义。为了方便，可称该表为UMT(Un mapping Table)。UMT的容量为Max(GN表示的最大数+1,RT的分量可表示最大数+1)，并且在 创建该表前，系统设计人员必须对系统采用的优先级方法有明确的定义，如文中规定优 先级数越大，任务优先级越小。

假定UMT的容量由GN决定，且GN的位长为L。则GN可表示的数的集合S={s|0≤s<2^L}。对S集 合求划分，条件为：任意s∈S，且s≠0,对s的二进制表示从低位向高位检查，如果发现了第 一个非0的比特就把s加入到子集SS_i中，i为第一个非0比特在GN中的位置。则可得划分Κ= {SS_i|0≤i≤L-1},那么UMT表的初始化值可这样决定，来自K中的任意子集SSi ,0≤i ≤L-1，从该子集中任取一元素s，则UMT［s］=i。只要按上述方法把K的子集都使用一次， 则UMT被建立起来了。最后，使UMT［0］=0。

例如：GN和RT的分量都为8位长。则可知UMT的容量=Max(GN表示的最大数+1,RT的分量可表示最大数 +1)=256。那么通过上述算法可得逆映射表，如图2。


2.2 得到最高优先级

组优先级= UMT［GN］；

子优先级= UMT［RT［UMT［GN］］］；

任务优先级=组优先级+子优先级。
3 最高优先级任务选取的实现

首先，系统为任务建立一个双向链表TL，该链表中的节点为任务的控制块(Tasks Control  Block,简称TCB)。之所以建立双向链表是因为在双向链表上完成插、删及查找某个任务是 高效的。然后在该双向链表上建立一级索引［4］，索引结构表为TS ，TS中每个元素 由两个字 段构成：任务优先级，指向TCB的指针。这样可利用最高优先级数直接定位到要找的任务。 上述的数据结构如图3所示。


4  算法的优点最高优先级任务选取

算法的优点是任务进入、退出就绪表及从就绪表中找到最高优先级任务所消耗的时间是常 量，它与系统中任务数无关。这一点对于实时操作系统来说非常重要，因为上述每一个工作 都必须在关中断的情况下完成，所以三个工作耗时必须短，否则会使系统的中断响应被延迟 ，系统的实时性不能得到保证。

现在市面上存在的实时系统中采用的算法，比如实时Linux等，虽然可保证实时性，但算法 的运行时间并不是常量，它们是随着系统中运行任务数目的增加而增长。这样会导致系统的 实时性随着任务数的增加而降低。
5 结束语

尽管RTOS的研究在国外已经将近20年，发展也比较成熟，但在国内确尚属起步阶段，所以， 在这方面有很多工作值得去做。 
［参考文献］
［1］ David E. Simon. An Embedded Software Primer ［M］. China Machine Pre ss, 2005.88~90.[ZK)]
［2］ 王田苗.嵌入式系统设计与实例开发［M］.北京：清华大学出版社, 2003.32~ 34.[ZK)]
［3］ S.利普舒尔茨,M.利普森.离散数学［M］.北京：科学出版社, 2002.[ZK)]
［4］ 许卓群,杨冬青等.数据结构与算法［M］.北京：高等教育出版社, 2004.334~ 335.