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

一种可在实时系统中实现最高优先级任务 选取的算法 (内蒙古财经学院 计算机信息管理系，内蒙古 呼和浩 特 010070) 摘 要：文章主要从就绪任务的管理、最高优先级数获 取 及选择最高优先级任务三个方面对该算法进行了阐述。 关键词：实时操作系统；任务分组；就绪表；逆映射 表 中图分类号：TP316.2 文献标识码：A 文章编号： 10076921(XX)13005102 实时操作系统1(Real Time Operating System,简 称 RTOS)和分时操作系统不同， 分时操作系统注重系统的 公平性，而实时操作系统主要体现实时性。一般情况下， 为了保证 高的实时性，实时内核的任务调度2采用抢 占式的优先级算法。文章所论述的内 容就是一种可在实时 内核中实现的抢占式高优先级任务选取算法。 1 就绪任务的管理 1.1 任务分组 该算法先对任务进行分组，分组依据是把任务的优先 级看作由两部分比特构成的整数：高位 若干比特表示组号， 称组优先级；剩余低位部分表示同组但优先级不同的不同 任务，称为子 优先级。分组具体如下： 假设系统中的任务集合为 T=ti0i)为第 i 个任 务的 优先级，定义优先级的 n 个高位比特表示分组号，m 个低位 为子优先级数，则函数 Hn(P(ti)表示任务 ti 的分组号,函 数 Lm(P(ti)为任务 ti 的子优先级数。那么就可以依据 任 务 的优先级分组号求出任务集合的一个划分 3 =STi|0n+1, 任意 tk,tjSTi ,当 Hn(P(tk)=Hn(P(tj)， 0i，则集合 STi 的分组号作为 GN 变量中表示该分组状 态比特的位置 。例如上述的 STi 中有就绪的任务，且 STi 的分组号为 x,则 GN 中第 x 个比特取值为 1，否则 为 0；按 照上述的做法可把任务集分组，并且使用 GN 变量保存时也 考虑了不同组的优先级。 如可以假定分组号越小，该分组 的优先级越高。 1.2 建立就绪表 就绪表是一张静态的二维表,可按下面规则建立。 设就绪表为 RT(Ready Table),则 RT=vi0ii 表示 第 i 个一维向量 ，向量分量是比特。具有相同组优先级的 任务状态由 RT 中的一个向量表示，则任务组和向量 的映 射关系为：分组号=向量的编号。处于同组中具有不同子优 先级的任务与向量中的比特 的映射关系为：任务子优先级 =表示该任务的向量分量的位置。 按照上述的方法不但可以建立就绪表，同时又建立了 任务优先级，GN 及就绪表之间的映射关 系，如图 1 所示。 740)this.width=740“ border=undefined 1.3 任务进入及退出就绪表 740)this.width=740“ border=undefined 2 最高优先级数的获取 获取最高优先级数的一般方法是先检查 GN 找到最高组 优先级，再检查 RT 表中的指定向量来确 定本组中最高子 优先级，然后通过两者来得到当前最高的优先级。这种方 法效率不高，文章 通过建立逆映射表的方法来直接获取最 高优先级数。 2.1 逆映射表 逆映射表是一张常量表，在操作系统的设计阶段就已 经定义。为了方便，可称该表为 UMT(Un mapping Table)。 UMT 的容量为 Max(GN 表示的最大数+1,RT 的分量可表示最 大数+1)，并且在 创建该表前，系统设计人员必须对系统 采用的优先级方法有明确的定义，如文中规定优 先级数越 大，任务优先级越小。 假定 UMT 的容量由 GN 决定，且 GN 的位长为 L。则 GN 可表示的数的集合 S=s|0sL。对 S 集 合求划分，条件 为：任意 sS，且 s0,对 s 的二进制表示从低位向高位 检查，如果发现了第 一个非 0 的比特就把 s 加入到子集 SSi 中，i 为第一个非 0 比特在 GN 中的位置。则可得划分 = SSi|0iL-1,那么 UMT 表的初始化值可这样决定， 来自 K 中的任意子集 SSi ,0i L-1，从该子集中任取一 元素 s，则 UMTs=i。只要按上述方法把 K 的子集都使 用一次， 则 UMT 被建立起来了。最后，使 UMT0=0。 例如：GN 和 RT 的分量都为 8 位长。则可知 UMT 的容量 =Max(GN 表示的最大数+1,RT 的分量可表示最大数 +1) =256。那么通过上述算法可得逆映射表，如图 2。 740)this.width=740“ border=undefined 2.2 得到最高优先级 组优先级= UMTGN； 子优先级= UMTRTUMTGN； 任务优先级=组优先级+子优先级。 3 最高优先级任务选取的实现 首先，系统为任务建立一个双向链表 TL，该链表中的 节点为任务的控制块(Tasks Control Block,简称 TCB)。之 所以建立双向链表是因为在双向链表上完成插、删及查找 某个任务是 高效的。然后在该双向链表上建立一级索引 4，索引结构表为 TS ，TS 中每个元素 由两个字 段构 成：任务优先级，指向 TCB 的指针。这样可利用最高优先 级数直接定位到要找的任务。 上述的数据结构如图 3 所示。 740)this.width=740“ border=undefined 4 算法的优点 最高优先级任务选取 算法的优点是任务进入、退出就绪表及从就绪表中找 到最高优先级任务所消耗的时间是常 量，它与系统中任务 数无关。这一点对于实时操作系统来说非常重要，因为上 述每一个工作 都必须在关中断的情况下完成，所以三个工 作耗时必须短，否则会使系统的中断响应被延迟 ，系统的 实时性不能得到保证。 现在市面上存在的实时系统中采用的算法，比如实时 Linux 等，虽然可保证实时性，但算法 的运行时间并不是 常量，它们是随着系统中运行任务数目的增加而增长。这 样会导致系统的 实时性随着任务数的增加而降低。 5 结束语 尽管 RTOS 的研究在国外已经将近 20 年，发展也比较 成熟，但在国内确尚属起步阶段，所以， 在这方面有很多 工作值得去做。 参考文献 1 David E. Simon. An Embedded Software Primer M. China Machine Pre ss, XX.8