HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 Connect in order to contact the contributor
Submitted on : Tuesday, November 27, 2007 - 10:51:53 AM
Last modification on : Friday, February 4, 2022 - 3:24:52 AM

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

60