静态优先级实时任务的多项式时间近似分析

Approximate Polynomial Time Analysis of Static Priority Real-time Tasks

经典的硬实时任务响应时间分析及其各种基于初始值的递归改进无法适用交互的实时设计环境.高效的近似分析方法是一种有效的选择,提出能高效计算任务最差响应时间上限的方法并给出与精确调度的误差量化分析,定义响应时间分析的线性近似请求约束函数并由此提出一个具有ε参数多项式时间复杂度的死线约束分析方法.针对死线约束分析方法本文将采用经典的近似比率技术和资源增值技术来分析该方法所提供的性能保证的程度.随机任务集的相关实验证明了所提出近似方法的有效性.

It is not applicable to interactive real-time design environment for response time analysis of classical hard real-time task and all kinds of recursive improvement based on initial value. So the approximate analysis is effective choice for efficiently scheduling re- al-time tasks. This paper puts forward the method of efficiently calculating task worst response time limit and gives quantitative analy- sis of the error with accurate scheduling, and also defines a new linear approximate request bound function and further puts forward analytical method of deadline which has a polynomial time complexity of e parameter. In this method, the analysis makes full use of classical approximation ratio analysis and resource augmentation technique to analyze the degree of the afforded performance. The ef- ficiency of the proposed approximate method is verified by pertinent experiment of random generated tasks set.