Uniprocessor Mixed-Criticality Scheduling with Graceful Degradation by Completion Rate


The scheduling of mixed-criticality (MC) systems with graceful degradation is considered, where LO-criticality tasks are guaranteed some service in HI mode in the form of minimum cumulative completion rates. First, we present an easy to implement admission-control procedure to determine which LO-criticality jobs to complete in HI mode. Then, we propose a demand-bound-function-based MC schedulability test that runs in pseudo-polynomial time for such systems under EDF-VD scheduling, wherein two virtual deadline setting heuristics are considered. Furthermore, we discuss a mechanism for the system to switch back from HI to LO mode and quantify the maximum time duration such recovery process would take. Finally, we show the effectiveness of our proposed method by experimental evaluation in comparison to state-of-the-art MC schedulers.

Meeting Name

2018 IEEE Real-Time Systems Symposium, RTSS 2018 (2018: Dec. 11-14, Nashville, TN)


Computer Science

Research Center/Lab(s)

Intelligent Systems Center

Second Research Center/Lab

Center for High Performance Computing Research


The authors are grateful to the input from Prof. Sanjoy Baruah at Washington University at St Louis. This work is partially supported by NSF grants (CNS-1837472, CNS-1850851, CNS-1545050, and CCF-1725755).

Keywords and Phrases

Criticality (nuclear fission); Interactive computer systems; Polynomial approximation; Response time (computer systems); Scheduling; EDF-GVD; Experimental evaluation; Graceful degradation; Mixed criticalities; Recovery process; Schedulability test; State of the art; Uniprocessors; Real time systems

International Standard Book Number (ISBN)


International Standard Serial Number (ISSN)

1052-8725; 2576-3172

Document Type

Article - Conference proceedings

Document Version


File Type





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

Publication Date

01 Dec 2018