An Algebraic Approach for Fixed-Priority Scheduling of Hard Real-time Systems with Exact Preemption Cost
Patrick Meumeu Yomsi, Yves Sorel · 2011
In this paper we study hard real-time systems composed of independent periodic preemptive tasks in the monoprocessor case. For such systems it is mandatory to satisfy all the constraints for all tasks. Although preemptive scheduling algorithms are able to successfully schedule some systems that cannot be scheduled by any non preemptive scheduling algorithm, the cost of preemption may not be negligible. Therefore, we propose to consider explicitly its exact cost in the schedulability conditions in order to avoid wasting resources and provide safety in terms of guaranteeing the right behavior of the system at run-time. Five main contributions are presented in this paper. First, we introduce a new model to describe and analyse hard real-time systems, which unifies in one framework different models such as Liu \& Layland's and Mok's models. Second, we show the impact of considering the exact cost of preemption for each task on the schedulability analysis. Third, by using our model based on an algebraic approach we provide new schedulability conditions which take into account the exact cost due to the occurrence of each preemption. Fourth, in this case we propose an optimal algorithm in the sense of feasibility for choosing the fixed-priority of each task. Finally, we address the problem of reducing the number of preemptions.