Efficient Schedulability Analysis of Semi-Clairvoyant Sporadic Task Systems With Graceful Degradation

Vestal proposed an abstract model for mixed-criticality workloads in which each job is characterized by multiple different estimates of its actual, but unknown, worst-case execution time (WCET). While this model helped establish the study of mixed-criticality systems, it has received criticism for incorporating some unrealistic assumptions. In response, recent works have introduced an alternative "semi-clairvoyant" model in which each job reveals upon arrival which of its WCET parameters it will respect. Such models are practically realizable and demonstrate a significant improvement over conventionally considered models in terms of speedup factor and schedulability. More recently, several different interpretations of graceful degradation have been considered in the context of semi-clairvoyant scheduling. Under one of these, Earliest Deadline First (EDF) scheduling has been shown to be optimal and associated exact schedulability tests have been derived. This work proposes Mixed-Criticality Quick Processor-demand Analysis (MC-QPA), an efficient and exact schedulability test for EDF-based semi-clairvoyant scheduling of sporadic task systems, and formally establishes its correctness. The effectiveness of MC-QPA over prior approaches in terms of the test running times is demonstrated via simulation experiments.