Regarding the Optimality of Speedup Bounds of Mixed-Criticality Schedulability Tests
Much existing research on Mixed-Criticality (MC) scheduling (see  for a review) has focused on dealing with the Vestal model , where different WCET estimations of a single piece of code are provided. This is typically a consequence of different tools for determining worst case execution time (WCET) bounds being more or less conservative than each other. It is known  that mixed criticality (MC) scheduling under such model is highly intractable, such that polynomial-time optimal solution is impossible unless P = NP. As a result, speedup bound is widely used in MC scheduling for measuring how close to optimal is a given schedulability analysis.
• A schedulability test has speedup factor of s(s ≥ 1), if any task set that is schedulable by any algorithm on a given platform with processing speed of 1, it will be deemed schedulable by this test upon a platform that is s times as fast.
Of course when deriving MC schedulers and associated schedulability tests, one of the goals is to identify/prove a relative small speedup bound (that is closer to 1). A minimum possible speedup is often presented as the “optimal speedup bound” of a given MC scheduling problem. However, we would like to point out that:
• Optimality of scheduler should not be derived against optimal speedup bounds.
Z. Guo, "Regarding the Optimality of Speedup Bounds of Mixed-Criticality Schedulability Tests," Dagstuhl Reports, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Mar 2017.
Mixed Criticality on Multicore/Manycore Platforms (Dagstuhl Seminar 17131), Dagstuhl Reports, March 2017
Keywords and Phrases
Mixed-Criticality; Speedup Bounds; Optimality; Clairvoyance
Article - Conference proceedings
© 2017 Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, All rights reserved.