MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Baruah, Sanjoy
Bonifaci, Vincenzo
D'Angelo, Gianlorenzo
Marchetti-Spaccamela, Alberto
van der Ster, Suzanne
Stougie, Leen		dblp
dblp
dblp
dblp
dblp
dblp
Not MPG Author(s):
Baruah, Sanjoy
D'Angelo, Gianlorenzo
Marchetti-Spaccamela, Alberto
van der Ster, Suzanne
Stougie, Leen
Editor(s):
Demetrescu, Camil
Halldórsson, Magnús M.		dblp
dblp
Not MPII Editor(s):
Demetrescu, Camil
Halldórsson, Magnús M.
BibTeX cite key*:
Bonifaci:2011:c
Title, Booktitle
Title*:
Mixed-criticality scheduling of sporadic task systems
mixedcritical-esa.pdf (310.64 KB)
Booktitle*:
Algorithms - ESA 2011 : 19th Annual European Symposium
Event, URLs
Conference URL::
http://esa2011.mpi-inf.mpg.de/
Downloading URL:
http://dx.doi.org/10.1007/978-3-642-23719-5_47
Event Address*:
Saarbrücken, Germany
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
5 September 2011
Event End Date:
7 September 2011
Publisher
Name*:
Springer
URL:
http://www.springer.com
Address*:
Berlin
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
6942
Number:
Month:
October
Pages:
555-566
Year*:
2011
VG Wort Pages:
ISBN/ISSN:
0302-9743
Sequence Number:
DOI:
10.1007/978-3-642-23719-5_47
Note, Abstract, ©
(LaTeX) 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.
Keywords:
Preemptive Scheduling, Safety-Critical Systems, Mixed Criticality
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Bonifaci:2011:c,
AUTHOR = {Baruah, Sanjoy and Bonifaci, Vincenzo and D'Angelo, Gianlorenzo and Marchetti-Spaccamela, Alberto and van der Ster, Suzanne and Stougie, Leen},
 EDITOR = {Demetrescu, Camil and Halld{\"o}rsson, Magnús M.},
 TITLE = {Mixed-criticality scheduling of sporadic task systems},
 BOOKTITLE = {Algorithms - ESA 2011 : 19th Annual European Symposium},
 PUBLISHER = {Springer},
 YEAR = {2011},
 VOLUME = {6942},
 PAGES = {555--566},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Saarbr{\"u}cken, Germany},
 MONTH = {October},
 ISBN = {0302-9743},
 DOI = {10.1007/978-3-642-23719-5_47},
}

Entry last modified by Jennifer Müller, 05/02/2012
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]		Created
01/02/2012 18:48:17
Revisions
3.
2.
1.
0.
Editor(s)
Jennifer Müller
Anja Becker
Anja Becker
Vincenzo Bonifaci
Edit Dates
02.05.2012 15:49:38
19.03.2012 08:51:17
26.01.2012 16:41:21
01/02/2012 06:48:17 PM

File Attachment Icon
mixedcritical-esa.pdf