Méthodes d'analyse statique de pire temps d'exécution de programmes

Les systèmes temps réel

Un système temps réel typique se compose de capteurs, d'un module qui analyse les données reçues par les capteurs et prend une décision, et d'une partie mécanique qui réalise physiquement la décision. Les dernières années ont vu se réaliser l'informatisation croissante du module d'analyse et de prise de décision.

Au niveau d'un tel système informatique, les contraintes d'intégrité se traduisent alors par le fait que tout traitement doit :

• produire des résultats justes ;
• être réalisé dans des délais impartis, sous peine de conséquences graves.

On parle alors de système temps réel dur.

À titre d'exemple et de manière très simplifiée, on peut considérer la commande d'un avion en tant que système constitué d'un manche à balai, d'un capteur de mouvements de ce dernier, de différents capteurs permettant de situer l'avion (en termes de position, d'orientation et de vitesse), d'un système informatique de correction d'erreurs de navigation du pilote, et d'éléments mécaniques réalisant l'action correcte. Dans un tel système informatique, plusieurs tâches sont exécutées, le plus souvent périodiquement (à intervalles réguliers), chaque tâche ayant sa propre période et sa propre priorité. Ainsi, pour chaque capteur, une tâche échantillonne l'intensité relevée. Lorsqu'un mouvement du manche à balai est détecté, une tâche effectue des calculs afin de corriger une erreur éventuelle du pilote (par exemple : un mouvement brusque du manche, une erreur d'appréciation de la situation) et envoie des ordres à des actionneurs. Dans cet exemple, deux contraintes d'intégrité peuvent être mises en évidence :

• Pour chaque tâche considérée de manière isolée, son exécution doit être terminée avant la fin de la période de la tâche ;
• Pour chaque tâche, en tenant compte de l'effet des autres tâches se partageant le même processeur, il faut s'assurer qu'elle puisse toujours s'exécuter selon la période qui lui est attribuée, sans quoi des pertes d'information ou de commande peuvent se produire.

Pour valider la première contrainte, il faut connaître le pire temps d'exécution de la tâche, appelé en anglais WCET (Worst-Case Execution Time). Par la suite, on s'intéressera à l'état actuel des connaissances concernant l'obtention des WCET.

Obtention des pires temps d'exécution

Étant donné un programme P et une architecture sur laquelle il s'exécute, le pire cas d'exécution de P se produit sous l'effet conjugué :

• du programme P lui-même et de son comportement en fonction des données qu'il prend en entrée ;
• d'un certain comportement de l'architecture sur laquelle s'exécute le programme.

Un exemple très simple de programme P permet d'illustrer la première de ces contraintes, la dépendance du temps d'exécution de ce programme aux données qu'il prend en entrée.

1 procedure P (a,b : entier) ;
2 debut
3  pour i depuis 1 jusqu'à a boucle
4   si (b > 4) alors -- Un certain traitement X très long
5   sinon - Un autre traitement Y un peu moins long 
6  fin si ;
7 fin boucle;
8 fin procedure P;

Le programme P prend en entrée des valeurs entières a et b, qui ne seront connues qu'au lancement du programme. P comporte une boucle (mot clé « boucle - fin boucle »), qui permet de répéter plusieurs fois l'exécution de portions de code. Dans ce programme, la portion de code des lignes 4 et 5 est répétée un nombre de fois égal à a. Le temps d'exécution du programme dépendra donc de la valeur d'entrée a. De même, P inclut une construction conditionnelle (lignes 4 et 5) permettant d'exécuter un certain traitement si une condition est vérifiée, et un autre traitement dans le cas contraire. Ici, comme la condition testée dépend d'une valeur d'entrée du programme (b), le temps d'exécution du programme dépendra également de cette valeur.

En ce qui concerne l'influence de l'architecture, les processeurs modernes comportent de nombreux dispositifs permettant d'augmenter la rapidité d'exécution des programmes. L'un de ces dispositifs est par exemple le mécanisme de pipeline. Un autre concerne les mémoires cache. Ces dispositifs améliorent les performances générales d'un système informatique. Les travaux concernant l'analyse de WCET portent entre autres sur la prise en compte de ces éléments architecturaux dans l'analyse, en vue de réaliser des systèmes temps réel durs moins onéreux et plus performants.