Semi-Clairvoyance in Mixed-Criticality Scheduling

TY - GEN

T1 - Semi-Clairvoyance in Mixed-Criticality Scheduling

AU - Agrawa, Kunal

AU - Baruah, Sanjoy

AU - Burns, Alan

N1 - This is an author-produced version of the published paper. Uploaded in accordance with the publisher’s self-archiving policy. Further copying may not be permitted; contact the publisher for details.

PY - 2020/4/2

Y1 - 2020/4/2

N2 - In the Vestal model of mixed-criticality systems, jobs are characterized by multiple different estimates of their actual, but unknown, worst-case execution time (WCET) parameters. Prior work on mixed-criticality scheduling theory assumes that the execution duration of a job is only revealed by actually executing the job through to completion. We consider a different *semi-clairvoyant* model here, in which it is assumed that upon arrival a job reveals which of its WCET parameters it will respect. We identify circumstances under which this is a reasonable model, and design and evaluate scheduling algorithms appropriate for this model. We show that such semi-clairvoyance yields a significant quantifiable benefit over non-clairvoyance, in terms of both the complexity of schedulability analysis and the speedup needed to ensure schedulability.

AB - In the Vestal model of mixed-criticality systems, jobs are characterized by multiple different estimates of their actual, but unknown, worst-case execution time (WCET) parameters. Prior work on mixed-criticality scheduling theory assumes that the execution duration of a job is only revealed by actually executing the job through to completion. We consider a different *semi-clairvoyant* model here, in which it is assumed that upon arrival a job reveals which of its WCET parameters it will respect. We identify circumstances under which this is a reasonable model, and design and evaluate scheduling algorithms appropriate for this model. We show that such semi-clairvoyance yields a significant quantifiable benefit over non-clairvoyance, in terms of both the complexity of schedulability analysis and the speedup needed to ensure schedulability.

U2 - 10.1109/RTSS46320.2019.00047

DO - 10.1109/RTSS46320.2019.00047

M3 - Conference contribution

T3 - IEEE Real-Time Systems Symposium (RTSS)

SP - 458

EP - 468

BT - 2019 IEEE Real-Time Systems Symposium (RTSS)

PB - IEEE

T2 - 40th IEEE Real-Time Systems Symposium (RTSS 2019)

Y2 - 1 December 2019

ER -