FP/EDF, a non-preemptive scheduling combiningfixed priorities and deadlines:uniprocessor and distributed cases - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2004

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

Steven Martin
  • Fonction : Auteur
Pascale Minet
Laurent George

Résumé

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.
Fichier principal
Vignette du fichier
RR-5112.pdf (483.55 Ko) Télécharger le fichier
Loading...

Dates et versions

inria-00071470 , version 1 (23-05-2006)

Identifiants

  • HAL Id : inria-00071470 , version 1

Citer

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⟩
186 Consultations
182 Téléchargements

Partager

Gmail Facebook X LinkedIn More