1 July 2010, C&O Seminar, Vincenzo Bonifaci (MPI Informatics, Saarbrücken, Germany)

We survey some recent results concerning the design and analysis of algorithms that ensure the schedulability of real-time tasks. We consider the problem of analyzing and certifying the feasibility of a system of periodically or sporadically recurring real-time tasks with hard deadlines, that have to be scheduled on a platform composed of one or more identical processors. We provide lower and upper bounds on the complexity of exact feasibility testing, as well as approximate feasibility tests for both the periodic and the sporadic variant.

For more information, see k.r.apt at uva.nl