Algorithm and complexity for the global scheduling of sporadic tasks on multiprocessors with work-limited parallelism

URL : http://rtns07.irisa.fr/fichiers/actes.pdfInternational audienceWe investigate the global scheduling of sporadic, implicit deadline, real-time task systems on identical multiprocessor platforms. We provide a task model which integrates work-limited job parallelism. For work-limited parallelism, we prove that the time-complexity of deciding if a task set is feasible is linear relatively to the number of (sporadic) tasks for a fixed number of processors. Based on this proof, we propose an optimal scheduling algorithm. Moreover, we provide an \emph{exact} feasibility utilization bound