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 (FPTAS) for computing response time upper bounds under resource augmentation. The resource augmentation is defined as the processor speedup factor bounded by (1 + 1/k), where k =(def) [1/epsilon] - 1 for any constant epsilon is an element of(0, 1), the FPTAS accuracy parameter. This algorithm is best possible in the sense that resource augmentation is indeed necessary for an efficient response time calculation.