The Concurrent Consideration of Uncertainty in WCETs and Processor Speeds in Mixed-Criticality Systems


Most prior work on mixed-criticality (MC) scheduling has focused on a model in which multiple WCET parameters are specified for each job, the interpretation being that the larger values represent "safer" estimates of the job's true WCET. More recently, a different MC model has been studied in which it is assumed that the precise speed of the processor upon which the system is implemented varies in an a priori unknown manner during runtime, and estimates must be made about how low the actual speed may fall.

The research reported in this paper seeks to integrate the varying-speed MC model and the multi-WCET one into a unified framework. A general model is proposed in which each job may have multiple WCETs specified, and the precise speed of the processor upon which the system is implemented may vary during run-time. We reinterpreted the key idea behind the table-driven MC scheduling scheme proposed in one of our recent work, and provide a more efficient algorithm named LE-EDF. This algorithm strictly generalizes algorithms that were previously separately proposed for MC scheduling of systems with multiple WCETs as well as for MC scheduling on variable-speed processors. It is shown that LE-EDF outperforms (via simulation) and/or dominates existing algorithms (under theoretical proof). LE-EDF is also compared with optimal clairvoyant algorithm using the metric of speedup factor.

Meeting Name

23rd International Conference on Real-Time Networks and Systems, RTNS 2015 (2015: Nov. 4-6, Lille, France)


Computer Science

Keywords and Phrases

Algorithms; Criticality (Nuclear Fission); Scheduling; Speed

International Standard Book Number (ISBN)


Document Type

Article - Conference proceedings

Document Version


File Type





© 2015 Association for Computing Machinery (ACM), All rights reserved.

Publication Date

01 Nov 2015