The Performance of Inherently Stable Priority List Dispatchers in Hard Real-Time Systems

This paper investigates low overhead solutions to the problem of scheduling instability in non-preemptive static priority list scheduling. Non-preemptive priority list scheduling is vulnerable to several multiprocessor anomalies. For example, in precedence constrained task systems, real-time deadlines can be missed due to a reduction in the duration of one or more tasks. A system displaying this behavior is called unstable. Several inherently stable run-time dispatchers of varying complexity are presented and their performance is investigated. These algorithms are less restrictive than previous stabilization methods and are based on an Extended Scheduling model that includes phantom tasks as a mechanism to model non-transparent overhead and events external to the processor. The dispatchers presented range from the simplest priority sequence enforcing dispatcher, up to a minimally stable algorithm based on the conditions necessary and sufficient for instability to occur. Extensive simulation on a wide range of task systems, including real-world workloads, shows that very simple low-overhead dispatchers have near-optimal average performance. Thus, real-time system developers are supplied with simple run-time dispatching algorithms that make complicated stabilization methods unnecessary.