Regarding the Optimality of Speedup Bounds of Mixed-Criticality Schedulability Tests

Abstract

Much existing research on Mixed-Criticality (MC) scheduling (see [7] for a review) has focused on dealing with the Vestal model [15], 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 [1] 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.

Meeting Name

Mixed Criticality on Multicore/Manycore Platforms (Dagstuhl Seminar 17131), Dagstuhl Reports, March 2017

Department(s)

Computer Science

Research Center/Lab(s)

Intelligent Systems Center

Keywords and Phrases

Mixed-Criticality; Speedup Bounds; Optimality; Clairvoyance

Document Type

Article - Conference proceedings

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 2017 Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, All rights reserved.

Publication Date

01 Mar 2017

Link to Full Text

Share

 
COinS