Systems in many safety-critical application domains are subject to certification requirements. For any given system, however, it may be the case that only a subset of its functionality is safety-critical and hence subject to certification; the rest of the functionality is non-safety-critical and does not need to be certified, or is certified to lower levels of assurance. The certification-cognizant runtime scheduling of such mixed- criticality systems is considered. An algorithm called EDF-VD (for Earliest Deadline First with Virtual Deadlines) is presented: this algorithm can schedule systems for which any number of criticality levels are defined. Efficient implementations of EDF-VD, as well as associated schedulability tests for determining whether a task system can be correctly scheduled using EDF-VD, are presented. For up to 13 criticality levels, analyses of EDF-VD, based on metrics such as processor speedup factor and utilization bounds, are derived, and conditions under which EDF-VD is optimal with respect to these metrics are identified. Finally, two extensions of EDF-VD are discussed that enhance its applicability. The extensions are aimed at scheduling a wider range of task sets, while preserving the favorable worst-case resource usage guarantees of the basic algorithm
Additional Metadata
THEME Null option (theme 11)
Journal Journal of the ACM
Baruah, S, Bonifaci, V, D'Angelo, G, Li, H, Marchetti Spaccamela, A, van der Ster, S.L, & Stougie, L. (2015). Preemptive Uniprocessor Scheduling of Mixed-Criticality Sporadic Task Systems. Journal of the ACM, 62(2), 1–33.