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
1 ULB - Université Libre de Bruxelles [Bruxelles]
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.
Type de document :
Communication dans un congrès
Isabelle Puaut, Nicolas Navet. 15th International Conference on Real-Time and Network systems - RTNS'07, Mar 2007, Nancy, France. pp.123-128, 2007, Proceedings of the 15th International Conference on Real-Time and Network systems - RTNS'07
Liste complète des métadonnées
https://hal.inria.fr/inria-00192213
Contributeur : Liliana Cucu <>
Soumis le : mardi 27 novembre 2007 - 10:51:53
Dernière modification le : jeudi 11 janvier 2018 - 06:20:05

Identifiants

  • HAL Id : inria-00192213, version 1

Collections

INRIA | LORIA | UNIV-LORRAINE

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. Isabelle Puaut, Nicolas Navet. 15th International Conference on Real-Time and Network systems - RTNS'07, Mar 2007, Nancy, France. pp.123-128, 2007, Proceedings of the 15th International Conference on Real-Time and Network systems - RTNS'07. 〈inria-00192213〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

174

Contact


archive-ouverte@inria.fr