Schedulability analysis of non-preemptive recurring real-time tasks
Sanjoy Baruah, Samarjit Chakraborty · 2006
The recurring real-time task model was recently pro-posed as a model for real-time processes that contain code with conditional branches. In this paper, we present a necessary and sufficient condition for uniprocessor non-preemptive schedulability analysis for this task model. We also derive a polynomial-time approximation algorithm for testing this condition. Preemptive schedulers usually have a larger schedulability region compared to their non-preemptive counterparts. Further, for most realistic task models, schedulability analysis for the non-preemptive ver-sion is computationally more complex compared to the cor-responding preemptive version. Our results in this paper show that (surprisingly) the recurring real-time task model does not fall in line with these intuitive expectations, i.e. there exists polynomial-time approximation algorithms for both preemptive and non-preemptive versions of schedu-lability analysis. This has important implications on the applicability of this model, since fully preemptive schedul-ing algorithms often have significantly larger runtime over-heads. 1