HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

FP/EDF, a non-preemptive scheduling combiningfixed priorities and deadlines:uniprocessor and distributed cases

Steven Martin Pascale Minet 1 Laurent George
1 HIPERCOM - High performance communication
Inria Paris-Rocquencourt, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR
Abstract : In this paper, we focus on a non-preemptive scheduling of sporadic flows, combining fixed priorities and deadlines. This scheduling is called FP/EDF. With any flow are associated a fixed priority denoting the importance of the flow and a delivery deadline. A packet m can be transmitted only if there is no waiting packet with a fixed priority higher than m and no waiting packet with the same fixed priority as m but with a smaller deadline. We are interested in the worst case response time of flows, both in uniprocessor and distributed cases. In the uniprocessor case, we prove that any sporadic flow set feasible with the classical Fixed Priority scheduling is feasible with FP/EDF. The converse is false, as shown by an example. Moreover, we show that when all flows sharing the same fixed priority have the same processing time, any sporadic flow set feasible with FP/FIFO is feasible with FP/EDF, but the converse is false. We then establish new results with FP/EDF in a distributed context, when all flows follow the same sequence of nodes. The absolute deadline of a packet that is considered by any scheduler is computed on the first node visited and then left unchanged by any other node. We show in such conditions how to compute an upper bound on the end-to-end response time of any flow. For this, we use a worst case analysis based on the trajectory approach. Results obtained for some configurations are exact. In all configurations, these results are compared with those provided by the classical holistic approach. We show that our results are largely better.
Document type :
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Tuesday, May 23, 2006 - 5:39:53 PM
Last modification on : Friday, February 4, 2022 - 3:13:20 AM
Long-term archiving on: : Sunday, April 4, 2010 - 10:17:10 PM


  • HAL Id : inria-00071470, version 1



Steven Martin, Pascale Minet, Laurent George. FP/EDF, a non-preemptive scheduling combiningfixed priorities and deadlines:uniprocessor and distributed cases. [Research Report] RR-5112, INRIA. 2004. ⟨inria-00071470⟩



Record views


Files downloads