A Fully Polynomial-Time Approximation Scheme for Feasibility Analysis in Static-Priority Systems with Arbitrary Relative Deadlines
Nathan Fisher, S. Baruah · 2006
Current feasibility tests for the static-priority scheduling on uniprocessors 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 with arbitrary relative deadlines. This test is an approximation with respect to the amount of a processor's capacity that must be "sacrificed" for the test to become exact. We show that an arbitrary level of accuracy, /spl epsi/, may be chosen for the approximation scheme, and present a runtime bound that is polynomial in terms of /spl epsi/ and the number of tasks, n.