Skip to Main content Skip to Navigation
Conference papers

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

Sébastien Collette 1 Liliana Cucu 2 Joël Goossens
2 TRIO - Real time and interoperability
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We 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.
Document type :
Conference papers
Complete list of metadata

https://hal.inria.fr/inria-00192213
Contributor : Liliana Cucu-Grosjean <>
Submitted on : Tuesday, November 27, 2007 - 10:51:53 AM
Last modification on : Friday, February 26, 2021 - 3:28:07 PM

Identifiers

  • HAL Id : inria-00192213, version 1

Collections

Citation

Sébastien Collette, Liliana Cucu, Joël Goossens. Algorithm and complexity for the global scheduling of sporadic tasks on multiprocessors with work-limited parallelism. 15th International Conference on Real-Time and Network systems - RTNS'07, Mar 2007, Nancy, France. pp.123-128. ⟨inria-00192213⟩

Share

Metrics

Record views

195