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

Approximate Polynomial Time Analysis of Static Priority Real-time Tasks

作　　者：彭浩[1] 蔡美玲[1,2] 陈继锋[1] 

机构地区：[1]湖南涉外经济学院计算机科学与技术学院,长沙410205 [2]中南大学信息科学与工程学院,长沙410083

出　　处：《小型微型计算机系统》2012年第12期2642-2646,共5页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(60803024)资助;湖南省自然科学基金项目(10JJ6092)资助

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

关 键 词：硬实时 线性近似分析 请求约束函数 资源增值技术 

分 类 号：TP316[自动化与计算机技术—计算机软件与理论]