Mixed-Criticality Scheduling of Sporadic Task Systems

Sanjoy Baruah 1 Vincenzo Bonifaci 2 Gianlorenzo d'Angelo 3, 4 Alberto Marchetti-Spaccamela 5 Suzanne Ster 6 Leen Stougie 7
1 Department of Computer Science [Chapel Hill]
2 MPII - Max-Planck-Institut für Informatik
3 UNIVAQ - University of L'Aquila [Italy]
4 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
5 DIS - Dipartimento di Informatica e Sistemistica "Antonio Ruberti"
6 VU - Vrije Universiteit Amsterdam [Amsterdam]
7 Department of mathematics and computing science [Eindhoven]
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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [8 references]  Display  Hide  Download
https://hal.inria.fr/hal-00643987
Contributor : Gianlorenzo d'Angelo <>
Submitted on : Wednesday, November 23, 2011 - 1:55:30 PM
Last modification on : Wednesday, August 21, 2019 - 10:22:07 AM
Long-term archiving on : Friday, February 24, 2012 - 2:25:48 AM

File

MixedTasks.pdf
Files produced by the author(s)

Identifiers

Collections

I3S | INRIA | UNICE | UNIV-COTEDAZUR

Citation

Sanjoy Baruah, Vincenzo Bonifaci, Gianlorenzo d'Angelo, Alberto Marchetti-Spaccamela, Suzanne Ster, et al.. Mixed-Criticality Scheduling of Sporadic Task Systems. 19th Annual European Symposium on Algorithms (ESA 2011), Sep 2011, Saarbruecken, Germany. pp.555-566, ⟨10.1007/978-3-642-23719-5_47⟩. ⟨hal-00643987⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

414

Files downloads

570

Contact


archive-ouverte@inria.fr