-
题名带时间约束实时任务图模型上可调度性分析算法研究
被引量：2
- 1
-
-
作者
孙景昊
关楠
邓庆绪
-
机构
东北大学信息科学与工程学院
-
出处
《计算机学报》
EI
CSCD
北大核心
2016年第12期2481-2493,共13页
-
基金
国家"九七三"重点基础研究发展规划项目预研项目(2014CB360509)
国家自然科学基金(61300022
+4 种基金
61300194
61472072)
中央高校基本科研业务费(N130423007
N130504008)
河北省自然科学基金(F2013501048)资助~~
-
文摘
带时间约束的实时任务图(TCDRT)模型具有接近于时间自动机的丰富表达性,但是其关联的可调度性分析(SA)问题却是强NP困难的.目前的研究仅关注一类约束个数为常数K的易解模型:K-TCDRT,且局限于SA问题的图转换求解方法.这种间接求法使得问题的计算复杂度随约束宽度呈指数倍增长.该文研究TCDRT模型上可调度性分析问题的直接求解方法,为两个核心子问题给出新的理论结果:第一,针对需求上界函数(DBF)的计算问题,提出了考虑时间约束的路径需求结构,并据此设计了新的动态规划算法,其时间复杂度与约束宽度无关;第二,对于可调度分析上界T的限定问题,从理论上证明了该问题是伪多项式时间可解的,且计算复杂度不再与K指数相关,这使得文中算法性能较已有结果有指数级提升.更进一步地,该文方法还蕴含着一类新的TCDRT易解模型.该类模型突破了约束个数必须为常数的局限,其分析难度也较K-TCDRT有指数倍地下降.
-
关键词
时间约束
实时任务图
可调度性分析
需求上界函数
动态规划
-
Keywords
timing constraints
digraph real-time tasks
schedulability analysis
demand bound function
dynamic programming
-
分类号
TP301
[自动化与计算机技术—计算机系统结构]
-
-
题名混合关键级任务资源需求的概率性分析
被引量：1
- 2
-
-
作者
张通
郑浩
朱长昊
张凤登
-
机构
上海理工大学光电信息与计算机工程学院
-
出处
《软件导刊》
2022年第1期156-163,共8页
-
基金
上海市自然科学基金项目(15ZR1429300)。
-
文摘
混合关键级系统可调度性分析通常基于最坏情况执行时间,导致系统资源的过度预置和低关键级模式下的分析过于苛刻。为解决资源过度预置的问题,简化低关键级模式下的可调度性,针对单核处理器上EDF调度的混合关键级零星任务集,提出随机需求约束函数模型。分析了混合关键级系统的概率性资源需求,得到相应的可调度性条件,并在尽可能增加低关键级任务预算的同时设计出系统可调度性测试算法。实验结果表明,与之前的可调度接受率相比,该方法提高了32%,在降低pDBF模型算法复杂度基础上仍使可调度性得到显著改善。
-
关键词
混合关键级
需求约束函数
概率性分析
可调度性
调度算法
-
Keywords
mixed-criticality
demand bound function
probabilistic analysis
schedulability
scheduling algorithm
-
分类号
TP301
[自动化与计算机技术—计算机系统结构]
-
