Mixed-Criticality Scheduling of Sporadic Task Systems

Abstract : We consider the scheduling of mixed-criticality task systems, that is, systems where each task to be scheduled has multiple levels of worst-case execution time estimates. We design a scheduling algorithm, EDF-VD, whose effectiveness we analyze using the processor speedup metric: we show that any 2-level task system that is schedulable on a unit-speed processor is correctly scheduled by EDF-VD using speed φ; here φ < 1.619 is the golden ratio. We also show how to generalize the algorithm to K > 2 criticality levels.We finally consider 2-level instances on m identical machines. We prove speedup bounds for scheduling an independent collection of jobs and for the partitioned scheduling of a 2-level task system.
Type de document :
Communication dans un congrès
Camil Demetrescu and Magnús M. Halldórsson. 19th Annual European Symposium on Algorithms (ESA 2011), Sep 2011, Saarbruecken, Germany. Springer, 6942, pp.555-566, 2011, Lecture Notes in Computer Science; Algorithms - ESA 2011. <10.1007/978-3-642-23719-5_47>
Liste complète des métadonnées


https://hal.inria.fr/hal-00643987
Contributeur : Gianlorenzo D'Angelo <>
Soumis le : mercredi 23 novembre 2011 - 13:55:30
Dernière modification le : mardi 22 mai 2012 - 14:32:33
Document(s) archivé(s) le : vendredi 24 février 2012 - 02:25:48

Fichier

MixedTasks.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Sanjoy Baruah, Vincenzo Bonifaci, Gianlorenzo D'Angelo, Alberto Marchetti-Spaccamela, Suzanne Ster, et al.. Mixed-Criticality Scheduling of Sporadic Task Systems. Camil Demetrescu and Magnús M. Halldórsson. 19th Annual European Symposium on Algorithms (ESA 2011), Sep 2011, Saarbruecken, Germany. Springer, 6942, pp.555-566, 2011, Lecture Notes in Computer Science; Algorithms - ESA 2011. <10.1007/978-3-642-23719-5_47>. <hal-00643987>

Partager

Métriques

Consultations de
la notice

245

Téléchargements du document

274