Mixed-criticality Scheduling of Sporadic Task Systems

Baruah, Sanjoy; Bonifaci, Vincenzo; D'Angelo, Gianlorenzo; Marchetti-Spaccamela, Alberto; van der Ster, Suzanne; Stougie, Leen

doi:10.1007/978-3-642-23719-5_47

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Conference Paper

Mixed-criticality Scheduling of Sporadic Task Systems

MPS-Authors

/persons/resource/persons44160

Bonifaci, Vincenzo
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

Supplementary Material (public)

There is no public supplementary material available

Citation

Baruah, S., Bonifaci, V., D'Angelo, G., Marchetti-Spaccamela, A., van der Ster, S., & Stougie, L. (2011). Mixed-criticality Scheduling of Sporadic Task Systems. In C. Demetrescu, & M. M. Halldórsson (Eds.), Algorithms - ESA 2011 (pp. 555-566). Berlin: Springer. doi:10.1007/978-3-642-23719-5_47.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0010-1259-0

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 $\phi$; here $\phi < 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.