Scheduling real-time mixed-criticality jobs

S. Baruah, V. Bonofaci, G. Del'Angelo, H. Li, A. Marchetti-Spaccamela, N. Megow, L. Stougie

Research output: Contribution to JournalArticleAcademicpeer-review

188 Downloads (Pure)


Many safety-critical embedded systems are subject to certification requirements; some systems may be required to meet multiple sets of certification requirements, from different certification authorities. Certification requirements in such "mixed-criticality" systems give rise to interesting scheduling problems, that cannot be satisfactorily addressed using techniques from conventional scheduling theory. In this paper, we study a formal model for representing such mixed-criticality workloads. We demonstrate first the intractability of determining whether a system specified in this model can be scheduled to meet all its certification requirements, even for systems subject to two sets of certification requirements. Then we quantify, via the metric of processor speedup factor, the effectiveness of two techniques, reservation-based scheduling and priority-based scheduling, that are widely used in scheduling such mixed-criticality systems, showing that the latter of the two is superior to the former. We also show that the speedup factors are tight for these two techniques. © 2010 Springer-Verlag.
Original languageEnglish
Pages (from-to)90-101
JournalLecture Notes in Computer Science
Publication statusPublished - 2010
EventMFCS, Brno, Czech Republic - Berlin
Duration: 23 Aug 201027 Aug 2010

Bibliographical note

Proceedings title: Proceedings of the 35th Conference on Mathematical Foundations of Computer Science
Publisher: Springer Verlag
Place of publication: Berlin


Dive into the research topics of 'Scheduling real-time mixed-criticality jobs'. Together they form a unique fingerprint.

Cite this