Simulation intervals for uniprocessor real-time schedulers with preemption delay

In the framework of embedded and time-critical systems we consider the scheduling of preemptive real-time periodic tasks upon uniprocessor. We consider the notion of simulation interval, a finite time interval such that the schedule starts to repeat in a cycle. The interest is to design a time interval which includes all possible (reachable) schedule states. Our study focuses on a model where preemption costs are explicitly considered, i.e. the time required by the real-time operating system (RTOS) or the hardware to load the context of execution of preempted jobs. We present and prove correct a simulation interval for asynchronous arbitrary deadline tasks with preemption delays and that holds for any deterministic and memoryless scheduler upon uniprocessor. This first contribution is valid for all schedulers one can imagine (but deterministic and memoryless), including non-preemptive schedulers, not work-conserving, not necessarily popular “real-time” ones. We then consider a particular case, regarding the preemption delays, for EDF scheduling for which we extend the work of Leung & Merrill showing that [0, O^{max} + 2 cdot H) is a simulation interval (significantly shorter than the general result). We also show that [0, S_n+H) from our previous work remains a simulation interval for fixed task priority (FTP) schedulers. Before concluding we open a discussion on the scope of the results, paths for reducing pessimism as well as other potential results opened by this work.