Optimalité de EDF et RM
Optimalité de EDF et RM Cette page traite de l'optimalité de EDF (Earliest Deadline First) et RM (Rate Monotonic) dans le contexte des systèmes de tâches périodiques. Vous y trouverez des définitions, des preuves concernant l'ordonnancement, ainsi que des exemples pour mieux comprendre ces concepts fondamentaux en temps réel.
D'après le document Optimalité de EDF et RM
Cet article a été rédigé automatiquement à partir du document source, puis vérifié avant publication.
Document source
Programmation, Th orie des t ches p riodiques · PDF · 3 pages
Afficher l'aperçu du document
Optimalité de EDF et RM
Cette page traite de l'optimalité de EDF (Earliest Deadline First) et RM (Rate Monotonic) dans le contexte des systèmes de tâches périodiques. Vous y trouverez des définitions, des preuves concernant l'ordonnancement, ainsi que des exemples pour mieux comprendre ces concepts fondamentaux en temps réel.
Définition de l'ordonnancement RM
Un système de tâches est dit ordonnançable par RM si l'utilisation totale du système U est inférieure ou égale à 1 (U ≤ 1). Cela signifie que les tâches doivent être indépendantes, préemptables et leurs délais doivent être supérieurs ou égaux à leurs périodes (Di ≥ Pi). Cette condition est cruciale pour garantir que toutes les tâches peuvent être exécutées dans les délais impartis.
Caractéristiques des tâches périodiques
Un système composé de tâches périodiques est dit simplement périodique si la période de chaque tâche est un multiple entier de la période des autres tâches de périodes inférieures. En d'autres termes, pour toutes les tâches Ti et Tk, avec pi < pk, il existe un entier positif nk,i tel que pk = nk,i ⋅ pi. Cela garantit que les tâches peuvent être synchronisées de manière efficace.
Preuve de l'ordonnancement RM
Pour démontrer que les systèmes de tâches simplement périodiques peuvent être ordonnancés par RM, considérons le cas où toutes les tâches sont en phase et où Di = Pi. Ce scénario représente un cas défavorable pour le système. Si la preuve est valide dans ce cas, elle le sera également pour des tâches déphasées.
Soit S un système simplement périodique ordonnancé selon RM. Supposons que S ne soit pas ordonnançable. Soit Ti la tâche qui va rater sa première deadline à l'instant t. Comme Di = Pi, t sera un multiple entier de Pi : t = n.Pi. De plus, puisque S est simplement périodique, alors pour chaque tâche j dans hp(i), il existe un entier positif ni,j tel que Pi = ni,j ⋅ Pj. Ainsi, t = n. ni,j ⋅ Pj pour chaque j dans hp(i).
Analyse de la demande en temps
Dire que Ti va manquer sa deadline à l'instant t signifie que, depuis l'instant 0 (où toutes les tâches sont libérées pour la première fois), jusqu'à l'instant t, la demande en temps pour exécuter toutes les tâches libérées pendant cet intervalle est supérieure à t. En d'autres termes, le temps requis pour exécuter l'ensemble des tâches arrivées entre 0 et t est supérieur à cet intervalle de temps (égal à t).
Nous avons donc :
∑j∈(hp(i)) ej > t
Or, l'utilisation totale du système est définie comme :
U = ∑i (ei / Pi)
Nous pouvons conclure que si U > 1, alors le système S ne peut pas être ordonnancé par RM.
Points clés à retenir
- Un système de tâches périodiques est ordonnançable par RM si U ≤ 1.
- Les tâches doivent être indépendantes et préemptables.
- La période de chaque tâche doit être un multiple entier des périodes des autres tâches.
- La preuve de l'ordonnancement repose sur l'analyse de la demande en temps et de l'utilisation totale.
Questions fréquentes
Qu'est-ce que l'ordonnancement RM ?
L'ordonnancement RM (Rate Monotonic) est une méthode d'ordonnancement pour les systèmes de tâches périodiques où les tâches sont exécutées en fonction de leur période. Les tâches avec des périodes plus courtes ont une priorité plus élevée.
Comment prouver l'ordonnancement d'un système de tâches ?
Pour prouver qu'un système de tâches est ordonnançable par RM, il faut démontrer que l'utilisation totale du système U est inférieure ou égale à 1. Cela implique d'analyser la demande en temps des tâches et de vérifier les conditions d'indépendance et de préemption.
Quelles sont les caractéristiques des tâches périodiques ?
Les tâches périodiques doivent avoir des délais supérieurs ou égaux à leurs périodes. De plus, un système est dit simplement périodique si la période de chaque tâche est un multiple entier des périodes des autres tâches de priorité supérieure.
Pourquoi l'utilisation totale du système est-elle importante ?
L'utilisation totale du système est cruciale car elle détermine si toutes les tâches peuvent être exécutées dans les délais impartis. Si U > 1, cela signifie que la demande en temps dépasse la capacité du système, entraînant des échecs de deadline.
Commentaires
Aucun commentaire pour le moment. Posez la première question.