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

作者：孙景昊; 关楠; 邓庆绪

来源：计算机学报, 2016, (12): 2481-2493.

• 时间约束
• 实时任务图
• 可调度性分析
• 需求上界函数
• 动态规划 timing constraints
• digraph real-time tasks
• schedulability analysis
• demand bound function
• dynamic programming

带时间约束的实时任务图(TCDRT)模型具有接近于时间自动机的丰富表达性,但是其关联的可调度性分析(SA)问题却是强NP困难的.目前的研究仅关注一类约束个数为常数K的易解模型:K-TCDRT,且局限于SA问题的图转换求解方法.这种间接求法使得问题的计算复杂度随约束宽度呈指数倍增长.该文研究TCDRT模型上可调度性分析问题的直接求解方法,为两个核心子问题给出新的理论结果:第一,针对需求上界函数(DBF)的计算问题,提出了考虑时间约束的路径需求结构,并据此设计了新的动态规划算法,其时间复杂度与约束宽度无关;第二,对于可调度分析上界T的限定问题,从理论上证明了该问题是伪多项式时间可解的,且计算复杂度...

• 出版日期2016
• 单位东北大学