A fully polynomial-time approximation scheme for feasibility analysis in static-priority systems with bounded relative deadlines

Issue title: Best Papers of RTS' 2005

Article type: Research Article

Authors: Fisher, Nathan | Baruah, Sanjoy

Affiliations: Department of Computer Science, CB #3175, The University of North Carolina, Chapel Hill, NC 27599, USA

Note: [] Corresponding author. Tel.: +1 919 843 7412; Fax: +1 919 962 1416; E-mail: fishern@cs.unc.edu

Abstract: Current feasibility tests for the static-priority scheduling of periodic task systems run in pseudo-polynomial time. We present a fully polynomial-time approximation scheme (FPTAS) for feasibility analysis in static-priority systems where each task's relative deadline is constrained to be at most its period. This test is an approximation with respect to the amount of processor capacity that must be "sacrificed" for the test to become exact. We show that an arbitrary level of accuracy, ϵ, may be chosen for the approximation scheme, and present a run-time bound that is polynomial in terms of ϵ and the number of tasks, n.

Keywords: Real-time scheduling, uniprocessor systems; static-priority systems, feasibility analysis, approximation algorithms

Journal: Journal of Embedded Computing, vol. 2, no. 3-4, pp. 291-299, 2006