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.
Z. Guo and S. K. Baruah, "The Concurrent Consideration of Uncertainty in WCETs and Processor Speeds in Mixed-Criticality Systems," Proceedings of the 23rd International Conference on Real-Time Networks and Systems (2015, Lille, France), vol. 04-06-November-2015, pp. 247 - 256, Association for Computing Machinery (ACM), Nov 2015.
The definitive version is available at https://doi.org/10.1145/2834848.2834852
23rd International Conference on Real-Time Networks and Systems, RTNS 2015 (2015: Nov. 4-6, Lille, France)
Keywords and Phrases
Algorithms; Criticality (Nuclear Fission); Scheduling; Speed
International Standard Book Number (ISBN)
Article - Conference proceedings
© 2015 Association for Computing Machinery (ACM), All rights reserved.
01 Nov 2015