没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
2
∞
9
年
12
月
第
27
卷第
6
期
西北工业大学学报
Dec.
2
∞
9
Vo
l. 27
No.6
Journal
of
Northwestern
Polytechnical
University
面向分布实时嵌入式系统的任务优化调度算法
梁克,周兴社,盛瑞卿,张凯龙
(西北工业大学计算机学院,陕西西安
710072)
摘
要:文章针对负载难以准确预知且动态变化的复杂分布实时嵌入式系统,提出了一种基于快速模
型预测控制的任务调度算法,通过动态调整分配在各个处理器上的任务
QoS
,使得每个处理器的
CPU
利用率保持在参考值附近,保证了任务的实时性;利用多参数二次规划的方法求解模型预测控制中的
约束优化问题,可有效减小算法的执行时间。实验结果表明算法有效且负载极小。
关键词:分布实时嵌入式系统,任务调度,模型预测控制,多参数二次规划
中图分类号
:T
P3
01
文献标识码
:A
文章编号:
1000-2758
(2009)
06
-0
900
-0
6
许多任务关键领域的分布实时嵌人式(
Di
strib-
uted
Real-time
Embedded
,
DRE)
系统都运行在负载
以及可用资源数量不能准确预知且变化的动态未知
环境中
(1)
。而传统的调度算法依赖于对负载的准
确建模,或者基于任务的最坏执行时间,显然不适合
这类
DRE
系统。现有的基于静态调节和启发式算
法的自适应策略,不能保证系统的稳定性,环境的不
断变化将使得系统的可靠性和可用性降低。需要研
究新的自适应策略,其建立在坚实的理论基础上,可
提供系统性能分析的依据
(2)
。近几年来,人们借助
自动控制原理提出了一系列反馈控制实时调度算法
(FCS
,
Feedback
Control
real-time
Scheduling)
[3.4)
。
FCS
通过动态控制任务的
QoS
来保证系统在动态环
境下的实时性。本文提出了一种基于快速模型预测
控制的任务调度算法,不仅可以保证
DRE
系统在动
态未知环境中的实时性,同时具有较小的额外开销。
1
问题描述
1.1
端到端的任务模型
假定
DRE
系统中包含
m
个周期任务{刀
lzgi
运
ml
以及
n
个处理器,每个任务式又包含一系列运
行在不同处理器上的子任务
I
Tij
I
1
运
j
运
Si
1
(Si
为
任务
Tt
的子任务个数)
,并且这些子任务具有相同
的执行频率。子任务
Tg
只有在它的前驱子任务丸
-1
执行完毕后才开始执行。
任务只具有端到端的相对截止期眼,且等于其
周期。任务式的执行频率可以在
[R
min
.
i
Rm
皿
.J
内动
态调整。假定已知每个子任务巧的估计执行时间
CV
,而其实际执行时间可能不同于此估计值,且在运行
时会发生变化。
1.2
问题转化
DRE
系统中的调度是为了满足端到端任务的
截止期限,该问题等同于满足每个处理器上所有子
任务的截止期限,而解决这个问题的通常做法是保
证处理器的
CPU
利用率不大于其可调度的利用率
上限
(8)
。同时,我们考虑尽可能充分地利用资源。
因此,
DRE
系统的调度问题就转化为如何在动态未
知环境中保证各个处理器的
CPU
利用率不大于并
且尽可能接近其利用率上限的问植。
2
相关研究
由于分布实时系统中采用端到端的任务模型,
使得各处理器的性能之间具有搞合性,因此在分布
式系统中必须借助
MIMO
控制理论,以实现基于反
馈控制的自适应调度
(5)
。
文献
[6]
采用了线性二次型最优控制方法,设
收稿日期
:2
∞
8-10-16
基金项目:国家自然科学基金
(60736017)
及
863
计划
tl
(2
∞
7AA010304)
资助
作者简介:梁克(1
982
-),西北工业大学博士研究生,主要从事公布式、嵌入式计算研究。
资源评论
weixin_38747025
- 粉丝: 129
- 资源: 1108
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功