Scheduling Mixed-Criticality Systems to Guarantee Some Service under All Non-Erroneous Behaviors


Many reactive systems must be designed and analyzed prior to deployment in the presence of considerable epistemic uncertainty: the precise nature of the external environment the system will encounter, as well as the run-time behavior of the platform upon which it is implemented, cannot be predicted with complete certainty prior to deployment. The widely-studied Vestal model for mixed-criticality workloads addresses uncertainties in estimating the worst-case execution time (WCET) of real-time code. Different estimations, at different levels of assurance, are made about these WCET values, it is required that all functionalities execute correctly if the less conservative assumptions hold, while only the more critical functionalities are required to execute correctly in the (presumably less likely) event that the less conservative assumptions fail to hold but the more conservative assumptions do. A generalization of the Vestal model is considered here, in which a degraded (but non-zero) level of service is required for the less critical functionalities even in the event of only the more conservative assumptions holding. An algorithm is derived for scheduling dual-criticality implicit-deadline sporadic task systems specified in this more general model upon preemptive uniprocessor platforms, and proved to be speedup-optimal.

Meeting Name

28th Euromicro Conference on Real-Time Systems, ECRTS 2016 (2016: Jul. 5-8, Toulouse, France)


Computer Science

Research Center/Lab(s)

Intelligent Systems Center

Keywords and Phrases

Criticality (Nuclear Fission); Estimation; Interactive Computer Systems; Scheduling; Uncertainty Analysis

International Standard Book Number (ISBN)


International Standard Serial Number (ISSN)


Document Type

Article - Conference proceedings

Document Version


File Type





© 2016 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.

Publication Date

01 Jan 2016