资源描述：
《一种可在实时系统中实现最高优先级任务选取的算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、一种可在实时系统中实现最高优先级任务选取的算法 (内蒙古财经学院计算机信息管理系，内蒙古呼和浩特010070)
摘要：文章主要从就绪任务的管理、最高优先级数获取及选择最高优先级任务三个方面对该算法进行了阐述。
关键词：实时操作系统；任务分组；就绪表；逆映射表
中图分类号：TP316.2文献标识码：A文章编号：1007—6921(XX)13—0051—02
实时操作系统［1］(RealTimeOperatingSystem,简称RTOS)和分时操作系统不同，分时操作系统注重系统的公平性，而实时操作系统主要体现实时性。一般
2、情况下，为了保证高的实时性，实时内核的任务调度［2］采用抢占式的优先级算法。文章所论述的内容就是一种可在实时内核中实现的抢占式高优先级任务选取算法。
1就绪任务的管理
1.1任务分组
该算法先对任务进行分组，分组依据是把任务的优先级看作由两部分比特构成的整数：高位若干比特表示组号，称组优先级；剩余低位部分表示同组但优先级不同的不同任务，称为子优先级。分组具体如下：
假设系统中的任务集合为T={ti｜0i)为第i个任务的优先级，定义优先级的n个高位比特表示分组号，m个低位为子优先级数，则函数Hn(P(ti))表示任务ti的分组号,
3、函数Lm(P(ti))为任务ti的子优先级数。那么就可以依据任务的优先级分组号求出任务集合的一个划分［3］φ={STi
4、0n+1,任意tk,tj∈STi,当Hn(P(tk))=Hn(P(tj))，0i∈φ，则集合STi的分组号作为GN变量中表示该分组状态比特的位置。例如上述的STi中有就绪的任务，且STi的分组号为x,则GN中第x个比特取值为1，否则为0；按照上述的做法可把任务集分组，并且使用GN变量保存时也考虑了不同组的优先级。如可以假定分组号越小，该分组的优先级越高。
1.2建立就绪表
就绪表是一张静态的二维表,可按下面规则建立
5、。
设就绪表为RT(ReadyTable),则RT={vi｜0≤ii表示第i个一维向量，向量分量是比特。具有相同组优先级的任务状态由RT中的一个向量表示，则任务组和向量的映射关系为：分组号=向量的编号。处于同组中具有不同子优先级的任务与向量中的比特的映射关系为：任务子优先级=表示该任务的向量分量的位置。
按照上述的方法不但可以建立就绪表，同时又建立了任务优先级，GN及就绪表之间的映射关系，如图1所示。
740)this.width=740"border=undefined>
1.3任务进入及退出就绪表
740)this.wi
6、dth=740"border=undefined>
2最高优先级数的获取
获取最高优先级数的一般方法是先检查GN找到最高组优先级，再检查RT表中的指定向量来确定本组中最高子优先级，然后通过两者来得到当前最高的优先级。这种方法效率不高，文章通过建立逆映射表的方法来直接获取最高优先级数。
2.1逆映射表
逆映射表是一张常量表，在操作系统的设计阶段就已经定义。为了方便，可称该表为UMT(UnmappingTable)。UMT的容量为Max(GN表示的最大数+1,RT的分量可表示最大数+1)，并且在创建该表前，系统设计人员必须对系统采用
7、的优先级方法有明确的定义，如文中规定优先级数越大，任务优先级越小。
假定UMT的容量由GN决定，且GN的位长为L。则GN可表示的数的集合S={s
8、0≤sL}。对S集合求划分，条件为：任意s∈S，且s≠0,对s的二进制表示从低位向高位检查，如果发现了第一个非0的比特就把s加入到子集SSi中，i为第一个非0比特在GN中的位置。则可得划分Κ={SSi
9、0≤i≤L-1},那么UMT表的初始化值可这样决定，来自K中的任意子集SSi,0≤i≤L-1，从该子集中任取一元素s，则UMT［s］=i。只要按上述方法把K的子集都使用一次，则UMT被建立起来了。最后
10、，使UMT［0］=0。
例如：GN和RT的分量都为8位长。则可知UMT的容量=Max(GN表示的最大数+1,RT的分量可表示最大数+1)=256。那么通过上述算法可得逆映射表，如图2。
740)this.width=740"border=undefined>
2.2得到最高优先级
组优先级=UMT［GN］；
子优先级=UMT［RT［UMT［GN］］］；
任务优先级=组优先级+子优先级。
3最高优先级任务选取的实现
首先，系统为任务建立一个双向链表TL，该链表中的节点为任务的控制块(TasksC
11、ontrolBlock,简称TCB)。之所以建立双向链表是因为在双向链表上完成插、删及查找某个任务是高效的。然后在该双向链
