Aller au contenu
ELECTRONICS ENGINEERINGelectronics-engineering.com
Systèmes d'exploitation

Systèmes temps réel : EDF, priorités monotones en fréquence et temps de réponse

Tâches périodiques, condition d'utilisation démontrée, EDF optimal, la borne de Liu et Layland, analyse du temps de réponse avec un exemple, inversion de priorité et héritage, RTOS.

https://www.electronics-engineering.com/fr/systemes-temps-reel-edf-rate-monotonic-temps-de-reponse/

Pas encore de vote : soyez le premier à noter cette page.

Dans un système temps réel, un résultat correct mais tardif est faux : la commande de freinage d’une voiture, un régulateur de moteur, un stimulateur cardiaque doivent répondre dans un délai fixé. Ce qui compte n’est pas la vitesse moyenne, mais la garantie dans le pire cas. Dans cette leçon, nous regardons le modèle de tâches périodiques, l’ordonnancement EDF avec la démonstration de la condition nécessaire, la priorité monotone en fréquence (rate monotonic) avec sa borne et l’analyse exacte du temps de réponse sur un exemple, l’inversion de priorité et les systèmes d’exploitation temps réel.

Le modèle de tâches périodiques

On distingue les systèmes durs (hard), où manquer une échéance est une défaillance (commandes de vol, airbags), et les mous (soft), où seule la qualité se dégrade (lecture vidéo). De nombreuses tâches de commande sont périodiques (leçon de Commande numérique sur l’implémentation) : la tâche \tau_i est lancée toutes les T_i, demande au plus C_i de calcul (le temps d’exécution au pire cas) et doit finir avant le lancement suivant. Son facteur d’utilisation est U_i = C_i/T_i, et l’utilisation totale U = \sum_iU_i.

L’échéance la plus proche d’abord

L’algorithme EDF (earliest deadline first) exécute à chaque instant la tâche prête dont l’échéance est la plus proche, avec préemption.

Théorème. Sur un processeur, un ensemble de tâches périodiques dont l’échéance égale la période est ordonnançable par un algorithme quelconque seulement si U \le 1 ; avec EDF, la condition est aussi suffisante.

Démonstration de la nécessité. Considérons l’intervalle [0, H), où H est le plus petit commun multiple des périodes. La tâche \tau_i est lancée H/T_i fois et demande en tout (H/T_i)C_i de calcul, qui doit être fait dans H. La demande totale est \sum_i(H/T_i)C_i = UH, et le processeur offre au plus H : il faut UH \le H, c’est-à-dire U \le 1. ∎

La suffisance pour EDF (Liu et Layland, 1973) se démontre en montrant que, si une échéance était manquée, dans l’intervalle précédent le processeur aurait toujours été occupé par des tâches d’échéances non plus tardives, et leur demande dépasserait la longueur de l’intervalle, c’est-à-dire U \gt  1. EDF est donc optimal : il utilise le processeur jusqu’à 100 %.

Priorité monotone en fréquence et temps de réponse

De nombreux systèmes utilisent plutôt des priorités fixes, plus simples et plus prévisibles en surcharge : avec la règle rate monotonic (RMS), la tâche de plus courte période a la plus haute priorité. Liu et Layland ont démontré que RMS garantit les échéances si

    \[ U \le n\left(2^{1/n} - 1\right) \]

où n est le nombre de tâches : 0,83 pour deux, 0,78 pour trois, tendant vers \ln 2 \approx 0.69. La condition n’est que suffisante ; pour une réponse exacte, on calcule le temps de réponse au pire cas, qui se produit quand toutes les tâches sont lancées ensemble. Pour la tâche i, avec des tâches j de plus haute priorité :

    \[ R_i = C_i + \sum_{j}\left\lceil\frac{R_i}{T_j}\right\rceil C_j \]

parce que pendant R_i, chaque tâche de plus haute priorité est lancée \lceil R_i/T_j\rceil fois et l’interrompt chaque fois pendant C_j. L’équation se résout par itération à partir de R_i = C_i, jusqu’à ce que la valeur cesse de changer ; la tâche respecte son échéance si R_i \le T_i.

Ordonnancement rate monotonic de trois tâches
La tâche tau 1 (période 4, calcul 1) a la plus haute priorité, tau 2 (période 6, calcul 2) une priorité moyenne, tau 3 (période 12, calcul 3) la plus basse. Les flèches marquent les lancements ; les rectangles les exécutions. Tau 3 est interrompue deux fois et finit à l’instant 10, avant son échéance à 12.

Exemple. Trois tâches (C, T) : (1, 4), (2, 6), (3, 12), avec U = 0.25 + 0.33 + 0.25 = 0.83, au-dessus de la borne de 0,78 : le test suffisant est non concluant. Temps de réponse de \tau_3 : on part de R = 3 ; puis 3 + \lceil 3/4\rceil + 2\lceil 3/6\rceil = 6 ; puis 3 + 2 + 2 = 7 ; puis 3 + \lceil 7/4\rceil + 2\lceil 7/6\rceil = 3 + 2 + 4 = 9 ; puis 3 + 3 + 4 = 10 ; puis 3 + \lceil 10/4\rceil + 2\lceil 10/6\rceil = 3 + 3 + 4 = 10, stable. R_3 = 10 \le 12 : l’ensemble est ordonnançable, comme le montre la figure.

L’inversion de priorité

Une tâche H de haute priorité attend un verrou détenu par une tâche L de basse priorité. Si entre-temps une tâche M de priorité moyenne est lancée, qui n’utilise pas le verrou, M préempte L, et H reste bloquée pendant toute la durée de M : une tâche moins importante retarde indirectement la plus importante, pendant un temps non borné s’il y a beaucoup de tâches moyennes. C’est l’inversion de priorité. En 1997, la sonde Mars Pathfinder se réinitialisait sans cesse pour cette raison, jusqu’à ce qu’on active depuis la Terre l’option d’héritage de priorité : tant que L détient un verrou demandé par H, L hérite temporairement de la priorité de H, M ne peut pas la préempter, et le blocage de H dure au plus autant que la section critique de L. Le protocole du plafond de priorité fait plus, et empêche aussi les interblocages entre verrous.

Les systèmes d’exploitation temps réel

Un système d’exploitation temps réel (RTOS) offre des ordonnanceurs préemptifs à priorités, des latences d’interruption petites et surtout bornées, des outils de synchronisation avec héritage de priorité et une allocation de mémoire prévisible. Sur les microcontrôleurs, on utilise de très petits noyaux comme FreeRTOS ou Zephyr, de quelques kilo-octets ; dans les systèmes plus grands, Linux avec les extensions PREEMPT_RT, qui rendent presque tout le noyau préemptible et ramènent les latences au pire cas à des dizaines de microsecondes. Le temps d’exécution au pire cas C_i doit être mesuré ou calculé avec des outils d’analyse, en tenant compte des caches et des interruptions : c’est souvent la partie la plus difficile de la conception.

S’abonner
Notifier de
guest
1 commentaire
Le plus ancien
Plus récent Les plus votés
1
0
Vous avez apprécié cet article ? Merci de laisser un commentaire.x