An Algebraic Approach for Fixed-Priority Scheduling of Hard Real-time Systems with Exact Preemption Cost

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.Dans ce papier nous étudions les systèmes temps réel durs composés de tâches préemptives indépendantes dans le cas mono-processeur. Pour de tels systèmes il est obligatoire de respecter toutes les contraintes auxquelles sont soumises toutes les tâches. Bien que des algorithmes d'ordonnancement préemptifs soient capables d'ordonnancer certains systèmes qui ne peuvent être ordonnancés avec aucun algorithme d'ordonnancement non préemptif, la préemption peut avoir un coût non négligeable. Nous proposons donc de considérer explicitement le coût exact de la préemption dans les analyses d'ordonnançabilité afin d'une part d'éviter du gaspillage de ressources et d'autre part de garantir un comportement correct lors de l'exécution en temps réel conforme aux analyses d'ordonnançabilité. Nous présentons dans ce papier cinq contributions. Premièrement nous introduisons un nouveau model pour décrire et analyser les systèmes temps réel durs qui unifie plusieurs modèles comme celui de Liu et Layland ou celui de Mok. Deuxièmement nous montrons l'impact de la prise en compte du coût exact de la préemption pour chaque tâche lors de l'analyse d'ordonnançabilité. Troisièmement en utilisant notre modèle fondé sur une approche algébrique nous proposons de nouvelles conditions d'ordonnançabilité qui prennent en compte le coût exact dû à l'occurence de chaque préemption. Quatrièmement, dans le cas ou l'on considère ce coût exact de la préemption, nous proposons un algorithme d'ordonnancement optimal, au sens de la faisabilité, pour choisir la priorité fixe de chaque tâche. Finalement nous étudions le problème consistant à réduire le nombre de préemptions