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

Patrick Meumeu Yomsi 1 Yves Sorel 1
1 AOSTE - Models and methods of analysis and optimization for systems with real-time and embedding constraints
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Paris-Rocquencourt, Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : 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.
Document type :
Liste complète des métadonnées

Cited literature [25 references]  Display  Hide  Download
Contributor : Yves Sorel <>
Submitted on : Thursday, August 4, 2011 - 4:13:23 PM
Last modification on : Monday, November 5, 2018 - 3:36:03 PM
Document(s) archivé(s) le : Saturday, November 5, 2011 - 2:21:11 AM


Files produced by the author(s)


  • HAL Id : inria-00613347, version 1


Patrick Meumeu Yomsi, Yves Sorel. An Algebraic Approach for Fixed-Priority Scheduling of Hard Real-time Systems with Exact Preemption Cost. [Research Report] RR-7702, INRIA. 2011, pp.43. ⟨inria-00613347⟩



Record views


Files downloads