Non-preemptive scheduling algorithms and schedulability conditions for real-time systems with precedence and latency constraints

Liliana Cucu 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 : First we justify our concern in latency constraints for real-time systems with precedence constraints. We evoke the model based on graph theory used to state and solve the problem of non-preemptive scheduling systems with precedence and latency constraints. Because latency constraints involve pairs of operations related to the graph which models the precedence constraints, we define three relations between pairs of operations, relations which determine the way of scheduling the operations. We give a necessary and sufficient condition of schedulability for the particular case of systems with precedence and latency constraints, where all pairs, on which latency constraints are imposed, are in one of these relations. Finally, we give a general schedulability condition for real-time systems with precedence and latency contraints and we propose a scheduling algorithm which is proved optimal.
Document type :
Reports
Complete list of metadatas

Cited literature [1 references]  Display  Hide  Download

https://hal.inria.fr/inria-00070600
Contributor : Rapport de Recherche Inria <>
Submitted on : Friday, May 19, 2006 - 8:58:42 PM
Last modification on : Monday, November 5, 2018 - 3:36:03 PM
Long-term archiving on : Sunday, April 4, 2010 - 9:33:21 PM

Identifiers

  • HAL Id : inria-00070600, version 1

Citation

Liliana Cucu, Yves Sorel. Non-preemptive scheduling algorithms and schedulability conditions for real-time systems with precedence and latency constraints. [Research Report] RR-5403, INRIA. 2004, pp.33. ⟨inria-00070600⟩

Share

Metrics

Record views

372

Files downloads

1148