| 一种改进的RM可调度性判定算法 |
| 其他题名 | improved rate monotonic schedulability test algorithm
|
| 刘军祥; 王永吉
|
| 2005
|
| 发表期刊 | 软件学报
 |
| ISSN | 1000-9825
|
| 卷号 | 16期号:1页码:89-100 |
| 摘要 | 固定优先级任务可调度性判定是实时系统调度理论研究的核心问题之一.目前已有的各种判定方法可归结为两大类:多项式时间调度判定和确切性判定.多项式时间调度判定通常采用调度充分条件来进行,为此,许多理想条件下基于RM(rate monotonic)调度算法的CPU利用率最小上界被提了出来.确切性判定利用RM调度的充要条件,保证任何任务集均可被判定,并且判定结果是确切的.但是由于时间复杂度较差,确切性判定方法难以实现在线分析.提出了一种改进的RM可调度性判定方法(improved schedulability test algorithm,简称ISTA).首先介绍了任务调度空间这一概念,并提出了二叉树表示,然后进一步提出了相关的剪枝理论.在此基础上,研究了任务之间可调度性的相关性及其对判定任务集可调度性的影响,提出并证明了相关的定理.最后基于提出的定理,给出了一种改进的伪多项式时间可调度性判定算法,并与已有的判定方法进行了比较.仿真结果表明,该算法平均性能作为任务集内任务个数的函数具有显著提高. |
| 收录类别 | ei,cscd,wanfang,cnki
|
| 关键词 | 实时系统
调度
实时调度
Rm算法
硬实时系统
Real-time System
Schedulability
Real-time Scheduling
Rm(Rate Monotonic)Algorithm
Hard Real-time System
|
| 部门归属 | 互联网软件技术实验室
|
| 语种 | 中文
|
| 内容类型 | 期刊论文
|
| URI标识 | http://ir.iscas.ac.cn/handle/311060/3252
|
| 专题 | 互联网软件技术实验室
|
推荐引用方式
GB/T 7714 |
刘军祥,王永吉. 一种改进的RM可调度性判定算法[J]. 软件学报,2005,16(1):89-100.
|
| APA |
刘军祥,&王永吉.(2005).一种改进的RM可调度性判定算法.软件学报,16(1),89-100.
|
| MLA |
刘军祥,et al."一种改进的RM可调度性判定算法".软件学报 16.1(2005):89-100.
|
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。
修改评论