收 稿日 期: 2004-09-02
基 金项 目: 国 家自然 科学 基金资 助项 目(60203011)
·
作 者简 介: 王小 英(1975 - ),女,江西波 阳人,东 北大学 博士 研究生; 赵 海(1959 - ),男,辽 宁沈阳 人,东北 大学教 授,博士 生导 师
·
第 26卷第 5期
2 005 年 5 月
东 北 大 学 学 报 ( 自 然 科 学 版 )
Journal of Northeastern University(Natural Science)
Vol.26,No .5
May 2 0 0 5
文章编号: 1005-3026(2005)05-0425-04
自 适 应 SR-RM 调 度 算 法
王小英, 赵 海, 张文波, 尹震宇
(东北大 学 信息 科学与 工程 学院, 辽宁 沈 阳 110004)
摘 要: 在分析 RM 调度算法的基础上,提出了一种自适应 SR-RM 调度算法,通过跟踪 任务
的实际执行情况以及处理 器的繁 忙程 度自 适应 地调 整任 务的 执行 周期,使任 务得 到较 合 理的 调
度,达到理想的服务响应时间,以提高系统的实时性;同时监视和预测 环境的变化 是否造成不 可调
度任务集,通过自动调节任务的执行周期来减少不可调度任务集的 发生,提 高系统的可 靠性
·
通过
仿真实验,证明 SR-RM 能得到较小的任务调度错失率、较高的可调度利用率和实时性能
·
关 键 词: SR-RM 调度;RM 调度;自适应;实时系统
中图分类号: TP 316 .2 文献标识码: A
C .L .Liu 和 J .W .Layland 于 1973 年提出了
著名的 RM(Rate Monotonic)
[1]
调度算法,这个算
法根据任务的执行周期来分配固定的优先级,执
行周期越短则分配的优先级越高
·
它是一个最优
的静态优先级抢占式调度算法
·
后人的 很多研
究
[2 ~8]
丰富和完善了 RM 调度理论, 并通过各种
方式消除和减弱了这些限定条件,如利用优先级
置顶协议
[9]
使得任务可以交互,采用非周期性服
务器
[10]
来调度非周期性任务等等
·
但在使用 RM
时,一般都是通过离线估算各个任务的最坏执行
时间 C
i
,并将任务的最坏执行时间作为一个常数
Ci 考虑, 再根据服务需求编排任务的执 行周期
T
i
,并通过仿真检验各任务能否在其截止期前完
成
·
由于任务实际执行时间的波动范围比较大,
在实时系统设计中,不得不保守地将其最坏执行
时间 C
i
选得比较大,以保证能成功调度所有的任
务
·
为保证成功调度,还应满足处理器的利用率
U =
∑
n
i = 1
C
i
T
i
≤ n(2
1/ n
- 1), 其中, U 是 n 的减函
数,当 n→∞时, U→0.693
·
因此在任务的最坏
执行时间估算时,如果 Ci 取得偏大, 则推算出的
T
i
也相应偏大,影响了系统的实时性能;如果 C
i
选得偏小,在处理器繁忙时,系统的可靠性将大打
折扣
·
当系统在实际运行中出现不可调度任务时,
RM 调度算法还会出现多米诺效应, 影响到后续
的任务调度
·
如果不应用其他机制,RM 调度算 法
将无法发现不可调度任务集并自动恢复正常
·
本文提出一种自适 应 SR-RM 调度算法, 通
过跟踪任务实际执行情况以及处理器繁忙程度自
适应地调整任务的执行周期,使任务得到较合理
的调度,达到理想的服务响应时间,以提高系统的
实时性;同时监视和预测环境的变化是否造成不
可调度任务集, 通过自动调节任务的执行周期来
减少不可调度任务集的发生,提高系统的可靠性
·
1 SR-RM 调度算法模型
1 .1 可调度检测点的选择
定义 n 个周期性任务 P
1
, P
2
, …, P
n
,其中,
任务 P
i
的执行周期为 T
i
(1≤ i≤ n),且 T
1
≤ T
2
≤…≤ Tn , 最坏执行时间为 Ci (1≤ i≤ n),相位
为 I
i
(0≤ I
i
≤ T
i
)
·
文献[1]证明了任务最繁忙的
时刻是所有任务的相位为 I
i
= 0(1≤ i≤ n)时,即
所有任务同时要求立即执行的时刻
·
当 0 为临界时刻时, W
i
( t)为[0, t]内所有 任
务需要执行的总时间:
W
i
( t) =
∑
i
j = 1
C
j
·「t/ T
j
·
(1)
同时,定义:
L
i
( t) = W
i
( t)/ t, (2)
L
i
= min
(0 < t≤ T
i
)
L
i
( t), (3)
L = max(1≤ i≤ n) Li
·
(4)