Mixed-criticality scheduling: Improved resource-augmentation results
Sanjoy Baruah, Haohan Li, Leen Stougie · 2010
Many safety-critical embedded systems are sub-ject to certification requirements; some systems may be required to meet multiple sets of certification re-quirements, from different certification authorities. Certification requirements in such “mixed-criticality” systems give rise to some interesting scheduling prob-lems, that cannot be satisfactorily addressed using techniques from conventional scheduling theory. It had previously been shown that determining whether a sys-tem specified in this model can be scheduled to meet all its certification requirements is highly intractable. Prior work [4] had also introduced a simple, priority-based scheduling algorithm called OCBP for mixed criticality systems, and had quantified, via the metric of processor speedup factor, the effectiveness of OCBP in scheduling dual-criticality systems – systems sub-ject to two sets of certification requirements. In this paper, we extend this result to systems with arbitrarily many distinct criticality levels, by de-riving a quantitative processor speedup factor (that depends on n) for OCBP when scheduling systems with n criticality levels for arbitrary n. 1