An fptas for Response Time Analysis of Fixed Priority Real-Time Tasks with Resource Augmentation

摘要

Response time analysis is required both for on-line admission of applications in dynamic systems and as an integral part of design tools for complex distributed real-time systems. We consider sporadic tasks with fixed-priorities and arbitrary deadlines to be executed upon a uniprocessor platform. Pseudo-polynomial time algorithms are known for computing exact worst-case response times for this task model. Nevertheless, the problem is known NP-hard and there cannot exist a constant approximation algorithm for response time computation, unless P=NP. We propose a fully polynomial time approximation scheme () for computing response time upper bounds under resource augmentation. The resource augmentation is defined as the processor speedup factor bounded by , where for any constant , the accuracy parameter. This algorithm is best possible in the sense that resource augmentation is indeed necessary for an efficient response time calculation.