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. © 2011 Springer-Verlag Berlin Heidelberg.

Baruah, S.K., Bonifaci, V., D'Angelo, G., Marchetti-Spaccamela, A., Van Der Ster, S., Stougie, L. (2011). Mixed-Criticality scheduling of sporadic task systems. In Proc. 19th Annual European Symposium on Algorithms (pp.555-566). Berlin : Springer [10.1007/978-3-642-23719-5_47].

Mixed-Criticality scheduling of sporadic task systems

Bonifaci V.;
2011-01-01

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. © 2011 Springer-Verlag Berlin Heidelberg.
2011
978-3-642-23718-8
Baruah, S.K., Bonifaci, V., D'Angelo, G., Marchetti-Spaccamela, A., Van Der Ster, S., Stougie, L. (2011). Mixed-Criticality scheduling of sporadic task systems. In Proc. 19th Annual European Symposium on Algorithms (pp.555-566). Berlin : Springer [10.1007/978-3-642-23719-5_47].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11590/381245
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 121
  • ???jsp.display-item.citation.isi??? 74
social impact