Temps de réponse d'un STR

Le temps de réponse d'une tâche TR représente le temps entre son lancement et sa complétion. Exprimé autrement, le temps de réponse d'un STR est un cumul des temps de réponse de ses tâches. Le temps de réponse d'un STR est le fruit d'un ensemble complexe d'interactions entre de multiples tâches.

Posons un regard aérien sur la question d'une analyse de ce temps de réponse :

• On évalue le WCET (le facteur $C$ ) de chaque tâche, souvent de manière analytique
• On tient ensuite compte des interférences entre les tâches. La tâche la plus prioritaire n'en subit pas, du moins dans un système à priorités uniques, mais les autres si
• Pour une tâche $i$ , le temps maximal pour une exécution sera déterminée par $R_i=C_i+I_i$ où $I_i$ est le pire cas possible d'interférence subie par la tâche
• Pour une tâche $j$ de priorité supérieure à celle de la tâche $i$ , le nombre de lancements dans un intervalle $[0..R_i)$ sera $\lceil\frac{R_i}{T_j}\rceil$ et l'interférence maximale sera ${\lceil\frac{R_i}{T_j}\rceil}C_j$
• De manière générale, puisque toutes les tâches plus prioritaires que la tâche $i$, donc les tâches dans l'ensemble $hp(i)$, interfèrent avec la tâche $i$, le calcul de $I_i$ est $I_i=\sum_{j \in hp(i)} {\lceil\frac{R_i}{T_j}\rceil}C_j$
• L'équation générale pour évaluer $R_i$ est, en substituant ce qui précède pour $I_i$ dans le calcul : $R_i=C_i+\sum_{j \in hp(i)} {\lceil\frac{R_i}{T_j}\rceil}C_j$ . Ce n'est pas simple à résoudre dû à la présence de $R_i$ des deux côtés de l'équation et dû à la fonction « plafond ». L'équation a plusieurs réponses correctes, et ce l'on cherche est le minimum de ces réponses

On peut heureusement résoudre l'équation par récurrence, en y allant de la tâche la plus prioritaire (celle qui ne subit aucune interférence) à la moins prioritaire.

On considère parfois ce qu'on nomme le Release Jitter $J_i$ d'une tâche sporadique $i$ quand cette tâche est susceptible d'être lancée par une autre tâche, peut-être à distance, et quand il existe une latence entre la demande de lancement et le lancement effectif. Le paramètre $J_i$ représente le pire cas de latence au lancement de la tâche $i$ . En tenant compte de ce paramètre, on obtient $I_i=\sum_{j \in hp(i)} {\lceil\frac{R_i+J_j}{T_j}\rceil}C_j$ .

Tâches apériodiques ou sporadiques

L'analyse du temps de réponse d'un STR ne se limite pas aux ordonnancements dont les tâches sont strictement périodiques. Pour l'adapter de manière à inclure aussi les tâches apériodiques ou sporadiques :

• On reprend le modèle de calcul ci-dessus
• On considère la période $T$ de chaque tâche comme étant l'intervalle minimal entre deux occurrences de l'événement mesuré ou représenté par la tâche. Notez que cette approche est pessimiste, et qu'il arrive que le temps moyen soit préféré au temps minimal (qui est en quelque sorte le pire cas possible) si les systèmes mesurés s'y prêtent
• Pour les tâches sporadiques, on connaît habituellement l'échéance $D$ au moment de leur lancement. Pour les calcul du temps de réponse, il est possible que $D=T$ , du moins dans une approche naïve, et c'est souvent sur cette base que les calculs sont faits, mais $D<T$ et $D>T$ sont tous deux possibles en pratique
• Notez que s'il faut déterminer les priorités des tâches, et s'il s'avère que $D=T$ , alors l'algorithme RMS mène à un ordonnancement optimal
• Dans le cas de tâches apériodiques ou sporadiques, si $D<T$, il a été démontré par (Leung et Whitehead, 1982) que l'algorithme DMPO est optimal

Interactions entre tâches et blocage

Dans un monde « idéal », par exemple dans un système monoprogrammé où toutes les tâches sont périodiques sur la base de paramètres statiques, il est possible de présumer une forme d'indépendance entre les tâches et, par le fait même, de simplifier les calculs. En pratique, supposer l'indépendance des tâches et l'absence d'interactions entre elles n'est pas raisonnable : on trouve des verrous, du passage de messages, des situations d'inversion de priorités, etc.

Il est possible de calculer le blocage maximal d'une tâche $i$ dans un système où existent $K$ ressources (verrous ou autres) en vertu desquelles il est possible d'attendre, en évaluant $B_i=\sum_{k=1}^K usage(k,i)C(k)$ où :

• $usage(k,i)$ est une fonction booléenne valant $0$ ou $1$ , c'est-à-dire que $usage(k,i)=1$ si et seulement si la ressource $k$ est utilisée par au moins une tâche de priorité supérieure à celle de la tâche $i$, et où
• $C(k)$ est la plus longue attente possible pour la ressource $k$ , ce qu'on nomme aussi souvent la section critique $k$ .

Considérant le blocage, le poids d'une tâche donnée dans le calcul du temps de réponse d'un STR devient $R=C+B+I$ ou, de manière plus exhaustive, $R_i=C_i+B_i+\sum_{j \in hp(i)} {\lceil\frac{R_i}{T_j}\rceil}C_j$ .

Impact de la tolérance aux pannes

Il arrive qu'on souhaite tenir compte du coût de la tolérance aux pannes dans le calcul du temps de réponse d'un STR. Pour une tâche $i$ , ce coût est habituellement indiqué par le paramètre $C_i^f$ , équivalent à $max_{k \in hpe(i)}C_k^f$ , et inclut entre autres ce qui a trait aux exceptions. Sans surprises, on s'intéresse habituellement au pire cas.

En omettant le coût associé au Release Jitter (donc en le considérant constant, ou même nul), le calcul du temps de réponse incluant ce paramètre devient : $R_i=C_i+B_i+I_i+max_{k \in hpe(i)}C_k^f$ avec $hpe(i)$ représentant l'ensemble des tâches de priorité supérieure ou égale à celle de la tâche $i$ . Il arrive aussi qu'on ajoute un facteur $F$ au poids de $C_k^f$ si plusieurs pannes sont susceptibles d'être traitées en séquence.

S'il existe un intervalle minimal $T_f$ entre deux pannes, l'équation devient : $R_i=C_i+B_i+I_i+max_{k \in hpe(i)}(\lceil\frac{R_i}{T_f}\rceil C_k^f)$ .

Voilà!