Preemptive Scheduling of Multi-criticality Systems with Varying Degrees of Execution Time Assurance

TLDR

In practice, tighter deadline guarantees often require increasingly conservative execution time bounds. The paper develops techniques that use varying confidence levels in execution time bounds to achieve more precise schedulability analysis and more efficient preemptive fixed‑priority scheduling. The authors model tasks with multiple criticality levels and a set of alternative worst‑case execution times, then evaluate the resulting scheduling methods on workloads abstracted from production avionics systems.

Abstract

This paper is based on a conjecture that the more confidence one needs in a task execution time bound (the less tolerant one is of missed deadlines), the larger and more conservative that bound tends to become in practice. We assume different tasks perform functions having different criticalities and requiring different levels of assurance. We assume a task may have a set of alternative worst-case execution times, each assured to a different level of confidence. This paper presents ways to use this information to obtain more precise schedulability analysis and more efficient preemptive fixed priority scheduling. These methods are evaluated using workloads abstracted from production avionics systems.