Analyse inter-tâche dans le calcul de pire temps d'exécution

Résumé

Les systèmes temps-réel critiques sont constitués de tâches soumises à des contraintes temporelles, qui doivent être respectées sous peine de conséquences catastrophiques. Pour s'assurer du respect de ces contraintes, il est nécessaire de connaitre le pire temps d'exécution (WCET[1] - Worst Case Execution Time) de chaque tâche.

Le comportement de la mémoire cache est un facteur important dans le temps d'exécution d'une tâche, et doit donc être pris en compte dans le calcul de WCET.

Ce projet vise à faire participer l'étudiant au développement d'un analyseur qui a pour but de prédire le comportement du cache d'une tâche. L'étudiant travaillera dans un projet OpenSource existant appelé OTAWA[2,3], et sera guidé par une approche documentée dans des publications scientifiques existantes[4,5].

Mots-clés

temps-réel, analyse statique, pire temps d'exécution (WCET)

Équipe

EMERAUDE

Encadrants

Clément Ballabriga

Présentation détaillée

Contacter les auteurs du sujet

Si vous êtes intéressés, contactez les auteurs par mail.

Pré-requis

OTAWA étant écrit en C++, l'étudiant devra être à l'aise avec la programmation orientée objet. Une maitrise du C++ n'est pas strictement nécessaire (mais c'est un plus), car l'étudiant qui est déjà à l'aise avec un langage objet (tel que Java, par exemple) pourra facilement être encadré dans son adaptation à l'usage du C++ L'environnement de développement est sous Linux. Il est aussi utile que l'étudiant "révise" le fonctionnement du cache (tel qu'il a été vu au L2S3-Archi par exemple).

Contexte

Les systèmes embarqués temps-réel critiques sont composés de tâches qui doivent respecter des contraintes temporelles strictes. Ces types de systèmes sont par exemple utilisés dans l'avionique, et plus généralement dans les domaines où le non respect des contraintes temporelles peut avoir des conséquences catastrophiques.

La validation de ces systèmes passe par l'analyse d'ordonnaçabilité, qui permet de prouver que chaque tâche respectera ses contraintes temporelles. Cette analyse d'ordonançabilité n'est possible qu'à condition de connaitre le pire temps d'exécution (ou WCET - Worst-Case Execution Time) de chaque tâche.

Plusieurs approches existent pour estimer le WCET d'une tâche. Un aperçu des méthodes disponibles est décrit dans [1]. Dans le cadre des systèmes temps-réel critiques, on estime en général le WCET par analyse statique, car cette approche permet de garantir que le WCET d'une tâche n'est pas sous-estimé (sous-estimer le WCET d'une tâche pourrait ammener à déclarer un système "sûr" alors qu'il ne l'est pas dans les faits).

L'analyse statique est une catégorie de méthodes permettant d'obtenir des informations sur le comportement d'un programme sans l'exécuter.

Le cache est une petite mémoire qui accélère l'exécution de programmes en stockant des copies de certains blocs de la mémoire principale. Lorsqu'on a besoin d'une donnée, on vérifie d'abord la donnée est dans le cache, auquel cas la donnée est retournée directement depuis le cache (ce cas de figure est appelé succès de cache), dans le cas contraire l'élement doit être rapatrié depuis la mémoire centrale, ce qui prends plus de temps (ce cas est appelé defaut de cache).

Dans le calcul du WCET par analyse statique, il est important d'obtenir des informations non seulement sur le comportement fonctionnel du programme, mais aussi sur son comportement temporel. Il est donc nécessaire d'analyser le cache, afin de prédire son comportement, c'est-à-dire savoir estimer la quantité de défauts de cache.

Problématique

La plupart des analyses existantes travaillent sur une tâche isolée, toutefois un système temps-réel est composé de multiple tâches. Lorsque plusieurs tâches cohabitent, elles partagent le même cache, ce qui provoque des interférences (le chargement d'une donnée demandée par la tâche T1 peut provoquer la suppression du cache d'une donnée de T2, par exemple). Pour avoir une analyse de WCET adaptée à des systèmes réalistes, il est donc nécessaire de prendre en compte un ensemble de tâches et de gérer les conflits de ces tâches vis à vis du cache.

Dans OTAWA[2,3], l'outil OpenSource de calcul de WCET, il existe déjà une analyse de cache, mais cette analyse travaille sur une tâche isolée. Il existe des approches documentées dans des publications scientifiques[4,5] pour prendre en compte les effets de cache inter-tâches, mais ceci n'est pas implémenté dans OTAWA.

Travail à effectuer

Le travail à effectuer consiste à se baser sur l'approche documentée dans [4,5] pour participer au développement d'un outil permettant d'obtenir des informations utiles à l'analyse de cache inter-tâches. Ce développement s'effectuera dans le cadre d'OTAWA[2,3], framework d'analyse automatique de programmes pour le calcul de WCET. OTAWA contient déjà un certain nombre d'analyses qui vont aider l'étudiant dans ce projet

Bibliographie

[1] Puaut, A. C. I., & Sainrat, C. R. P. Calcul de majorants de pire temps d’exécution: état de l’art. ISO 690

[2] Ballabriga, C., Cassé, H., Rochange, C., & Sainrat, P. (2010). OTAWA: An Open Toolbox for Adaptive WCET Analysis. SEUS, 6399, 35-46.

[3] Cassé, H., & Sainrat, P. (2006, January). OTAWA, a framework for experimenting WCET computations. In 3rd European Congress on Embedded Real-Time Software (Vol. 1).

[4] Altmeyer, S., Davis, R. I., & Maiza, C. (2012). Improved cache related pre-emption delay aware response time analysis for fixed priority pre-emptive systems. Real-Time Systems, 48(5), 499-526. ISO 690

[5] Lunniss, Will, et al. "Integrating cache related pre-emption delay analysis into EDF scheduling." 2013 IEEE 19th Real-Time and Embedded Technology and Applications Symposium (RTAS). IEEE, 2013.