Note publique d'information : Deux techniques sont utilisées pour vérifier que des tâches temps réel respectent
bien leurs échéances temporelles : les tests d'ordonnançabilité qui renvoient un résultat
binaire (ordonnançable ou non) et les calculs de temps de réponse (Response Time Analysis
- RTA) qui déterminent la longueur du plus long intervalle de temps entre le réveil
et la terminaison d'une tâche. Ces deux approches ont une complexité pseudo-polynomiale
et notons qu'aucun algorithme polynomial n'est connu. Dans ce contexte, elles ne sont
pas particulièrement appropriées pour la conception interactive des systèmes temps
réel ou pour analyser des systèmes distribués à l'aide d'une analyse holistique. Dans
de tels scénarios, un algorithme pseudo-polynomial est lent, puisque les calculs des
temps de réponse des tâches sont exécutés à de nombreuses reprises. De plus, pour
certains systèmes temps réels, tels que dans les systèmes de contrôle-commande, il
est nécessaire de connaître le pire temps de réponse des tâches et non seulement la
décision binaire sur l'ordonnançabilité des tâches. Dans ce contexte, il peut être
acceptable d'utiliser un algorithme plus rapide qui fournit une analyse approchée
au lieu d'utiliser des analyses reposant sur des calculs exacts. Comme cette approximation
va introduire du pessimisme dans le processus de décision, il est souhaitable de le
quantifier d'une manière à définir un compromis entre le temps de calcul et l'exigence
de ressource du processeur. C'est la raison pour laquelle, dans ce travail, nous proposons
des algorithmes pour calculer efficacement des bornes supérieures des pires temps
de réponse et nous présentons des résultats sur leurs qualités dans le pire cas (analyse
de compétitivité avec augmentation de ressource) et en moyenne (simulations).
Note publique d'information : Two techniques are used to verify if real-time tasks meet their deadlines : schedulability
tests that return a binary result (schedulable or not) and the calculation of the
response times (Response Time Analysis - RTA) which determines the length of the longest
interval between the release instant and the completion of a task. Both approaches
have a pseudo-polynomial time complexity and please note that no polynomial time algorithm
is known. In this context, they are not particularly suitable for interactive design
of real-time systems or to analyze distributed systems using an holistic analysis.
In such scenarios, a pseudo-polynomial time algorithm is slow, since the computations
of the task response times are performed many times. Moreover, for some real time
systems, such as the control-command systems, it is necessary to know the task worst-case
response times and not only the binary decision on the tasks schedulability. In this
context, it may be acceptable to use a faster algorithm which provides an approximate
analysis instead of the analysis based on exact calculations. As these approximations
will produce pessimism in the decision process, it is desirable to quantify this pessimism
in such a way as to define a compromise between computation time and resource requirement
of processor. That is the reason why, in this work, we propose efficient algorithms
to compute upper bounds of worst-case response times and we present results on their
qualities in the worst-case (competitive analysis resource augmentation) and in the
average (simulations).