English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  Mixed-criticality Scheduling of Sporadic Task Systems

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.

Item is

Files

show Files
hide Files
:
mixedcritical-esa.pdf (Any fulltext), 311KB
 
File Permalink:
-
Name:
mixedcritical-esa.pdf
Description:
-
OA-Status:
Visibility:
Private
MIME-Type / Checksum:
application/pdf
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Baruah, Sanjoy1, Author
Bonifaci, Vincenzo2, Author           
D'Angelo, Gianlorenzo1, Author
Marchetti-Spaccamela, Alberto1, Author
van der Ster, Suzanne1, Author
Stougie, Leen1, Author
Affiliations:
1External Organizations, ou_persistent22              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s): eng - English
 Dates: 20112011
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 618716
DOI: 10.1007/978-3-642-23719-5_47
URI: http://dx.doi.org/10.1007/978-3-642-23719-5_47
Other: Local-ID: C1256428004B93B8-66B483FE686CF648C12579790061CE13-Bonifaci:2011:c
 Degree: -

Event

show
hide
Title: 19th Annual European Symposium on Algorithms
Place of Event: Saarbrücken, Germany
Start-/End Date: 2011-09-05 - 2011-09-07

Legal Case

show

Project information

show

Source 1

show
hide
Title: Algorithms - ESA 2011
  Abbreviation : ESA 2011
  Subtitle : 19th Annual European Symposium
Source Genre: Proceedings
 Creator(s):
Demetrescu, Camil1, Editor
Halldórsson, Magnús M.1, Editor
Affiliations:
1 External Organizations, ou_persistent22            
Publ. Info: Berlin : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 555 - 566 Identifier: -

Source 2

show
hide
Title: Lecture Notes in Computer Science
  Abbreviation : LNCS
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 6942 Sequence Number: - Start / End Page: - Identifier: ISSN: 0302-9743