Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:




Library Locked Library locked




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

URL of the conference:

http://esa2011.mpi-inf.mpg.de/

URL for downloading the paper:

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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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 06:48:17 PM
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
mixedcritical-esa.pdf