Skip to Main content Skip to Navigation
Reports

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 :
Reports
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download

https://hal.inria.fr/inria-00071470
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 5:39:53 PM
Last modification on : Wednesday, September 16, 2020 - 5:07:09 PM
Long-term archiving on: : Sunday, April 4, 2010 - 10:17:10 PM

Identifiers

  • HAL Id : inria-00071470, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

336

Files downloads

304