带时间约束实时任务图模型上可调度性分析算法研究

发布时间：2017-08-13 15:32

  本文关键词：带时间约束实时任务图模型上可调度性分析算法研究

  更多相关文章： 时间约束 实时任务图 可调度性分析 需求上界函数 动态规划

【摘要】：带时间约束的实时任务图(TCDRT)模型具有接近于时间自动机的丰富表达性,但是其关联的可调度性分析(SA)问题却是强NP困难的.目前的研究仅关注一类约束个数为常数K的易解模型:K-TCDRT,且局限于SA问题的图转换求解方法.这种间接求法使得问题的计算复杂度随约束宽度呈指数倍增长.该文研究TCDRT模型上可调度性分析问题的直接求解方法,为两个核心子问题给出新的理论结果:第一,针对需求上界函数(DBF)的计算问题,提出了考虑时间约束的路径需求结构,并据此设计了新的动态规划算法,其时间复杂度与约束宽度无关;第二,对于可调度分析上界T的限定问题,从理论上证明了该问题是伪多项式时间可解的,且计算复杂度不再与K指数相关,这使得文中算法性能较已有结果有指数级提升.更进一步地,该文方法还蕴含着一类新的TCDRT易解模型.该类模型突破了约束个数必须为常数的局限,其分析难度也较K-TCDRT有指数倍地下降.
【作者单位】： 东北大学信息科学与工程学院;
【关键词】： 时间约束 实时任务图 可调度性分析 需求上界函数 动态规划
【基金】：国家“九七三”重点基础研究发展规划项目预研项目(2014CB360509) 国家自然科学基金(61300022,61300194,61472072) 中央高校基本科研业务费(N130423007,N130504008) 河北省自然科学基金(F2013501048)资助~~
【分类号】：TP301.6
【正文快照】： 然科学基金(61300022,61300194,61472072)、中央高校基本科研业务费(N130423007,N130504008)、河北省自然科学基金(F2013501048)1引言在实时系统验证领域,形式化模型更关注系统的时间行为和不确定性等非功能特征,是系统可调度性分析的理论基础.为便于理论分析,形式化模型通常

【相似文献】

中国期刊全文数据库 前10条

1 徐建华;李允;;基于单调速率的可调度性判定改进算法[J];计算机工程;2011年22期

2 牛云;戴冠中;梁亚琳;;基于时间需求迭代和排队模型的开放式实时系统可调度性分析算法研究[J];计算机科学;2009年01期

3 于晓;王家礼;;偏序的周期任务间可调度性判定算法[J];电子测量与仪器学报;2009年04期

4 张永悦;孙瑜;李允;徐建华;;复杂实时系统可调度性判定工具的研究与实现[J];计算机工程;2013年01期

5 郭锐锋;刘娴;丁万夫;李杰;王鸿亮;;回卷恢复模型下容错实时系统的可调度性分析[J];小型微型计算机系统;2013年06期

6 毛羽刚,张拥军,金士尧,胡华平;一种改进的分布强实时系统可调度性分析算法[J];软件学报;2001年02期

7 王高才;李伟;;基于随机模型的软实实时时系统的任务期望可调调度度性[J];控制理论与应用;2012年01期

8 谢拴勤;潘姿君;;实时多任务系统可调度性工程评估方法研究[J];计算机测量与控制;2007年12期

9 李俊,阳富民,卢炎生;一种可行的容错实时系统可调度性分析[J];软件学报;2005年08期

10 陈劲林,杨士元,胡东成;基于确定周期性任务的进程管理及可调度性分析[J];计算机研究与发展;2000年03期

中国重要会议论文全文数据库 前3条

1 周美娇;应启戛;张凤登;萧伟;冯治宝;;带有空闲帧的FIP总线可调度性分析[A];第六届全国信息获取与处理学术会议论文集（3）[C];2008年

2 王宇;侯朝桢;;数字化操控系统中CAN总线的信息可调度性分析[A];《制造业自动化与网络化制造》学术交流会论文集[C];2004年

3 王宇;侯朝桢;;数字化操控系统中CAN总线的信息可调度性分析[A];先进制造技术论坛暨第三届制造业自动化与信息化技术交流会论文集[C];2004年

中国博士学位论文全文数据库 前6条

1 王磊;容错实时系统可调度性分析研究[D];浙江大学;2005年

2 李俊;容错硬实时系统的可调度性分析[D];华中科技大学;2007年

3 窦强;分布式强实时系统中可调度性分析算法的研究[D];国防科学技术大学;2001年

4 姚兴华;资源供需进程演算的证明系统研究[D];华东师范大学;2014年

5 于晓;基于嵌入式Linux的仪器操作系统的研究[D];西安电子科技大学;2009年

6 钱之琳;基于服务的信息物理融合系统可信建模与分析[D];华东理工大学;2014年

中国硕士学位论文全文数据库 前3条

1 王好;基于eM-Plant原油处理过程的可调度性分析[D];广东工业大学;2013年

2 余飞;基于Uppaal的多处理器实时系统的可调度性分析[D];上海交通大学;2011年

3 张永悦;基于仿真的实时系统可调度性分析工具的研究与实现[D];云南师范大学;2014年

，

本文编号：668030