Corteva - Une méthodologie correcte par construction pour supporter la variabilité du temps d’exécution dans les systèmes temps réel / A Correct-by-construction methodology for supporting execution time variability in real-time systems.

Porteur du projet : Giuseppe LIPARI - Professor
Equipe Emeraude

PRCE - Projets de recherche collaborative Entreprises- Privé/Public
Partenaires : 1- Université de Lille_CRIStAL, 2 - ONERA DTIS, 3 - RTAW

Défi Sociétal : Société de l’information et de la communication

Recherche industrielle

Résumé  :
Dans le domaine de la programmation des systèmes temps-réel critiques, il est capital de pouvoir garantir que les calculs seront réalisés dans les délais impartis, afin d’éviter une panne catastrophique du système. Les systèmes avioniques et aérospatiaux, les systèmes électroniques dans le domaine automobile, les systèmes de contrôle de trains, etc, sont des exemples de systèmes temps-réel critiques. Pour garantir leur correction, le concepteur doit calculer une borne supérieure au temps d’exécution de chaque bloc de code de l’application, puis garantir que, dans le pire cas, chaque bloc sera ordonnancé par le système d’exploitation de manière à ce qu’il se termine avant son échéance.
De nos jours, il est difficile de construire un système temps-réel à la fois prévisible et performant sur des processeurs modernes, car la vitesse d’exécution d’un programme est très variable. Le pire cas peut être des centaines de fois plus long que le meilleur cas, en raison de paramètres variant d’une exécution à l’autre, tels que, par exemple, l’état de la mémoire cache. C’est pourquoi le concepteur sur-dimensionne généralement la puissance des processeurs, ce qui mène à un coût plus élevé du système. En raison de la volonté constante d’intégrer de nouvelles fonctionnalités, cette situation n’est pas gérable à long terme. Bien que des méthodes aient été proposées pour prendre en compte ces importantes variations, elles ne sont pas immédiatement applicables car elles se concentrent sur l’ordonnancement sans prendre en compte les aspects fonctionnels de l’application Ce projet a pour objectif général de contribuer à la conception et au développement d’une nouvelle génération de systèmes embarqués temps-réel critiques. En particulier, nous tenterons de résoudre le problème de l’importante variabilité du temps d’exécution en utilisant des modèles de programmation fiables et prouvés qui combinent aspects temporels et fonctionnels. L’idée principale de ce projet peut être résumée comme suit. D’abord, nous utiliserons des techniques de calcul de pire temps d’exécution (Worst Case Execution Time - WCET) paramétriques, pour calculer statiquement un WCET sous la forme d’une formule. Cette formule dépend de paramètres, qui correspondent aux valeurs d’entrée du bloc de code executé et à des informations sur l’état de la mémoire cache. Ensuite, nous instancierons cette formule dynamiquement à l’exécution pour estimer un temps d’exécution plus précis. Cette estimation permettra, à l’exécution, de détecter l’occurence d’un temps d’exécution exceptionnellement élevé afin d’adapter le comportement de l’application de manière à garantir le respect des échéances. Le concepteur spécifiera le comportement de l’application à l’aide d’un langage synchrone pour garantir formellement à la fois la sûreté fonctionnelle et la sûreté temporelle. Enfin, nous proposons l’utilisation d’une méthodologie pour aider le concepteur à configurer son système de la meilleure façon possible.

Abstract :
In real-time safety critical systems, it is of paramount importance to guarantee that computation is performed within certain time bounds, otherwise a critical failure may happen. Avionics and aerospace systems, electronic automotive systems, train control systems, etc, are all examples of real-time safety-critical systems. To guarantee correctness, the designer needs first to compute bounds on the execution time of every block of code, and then to guarantee that, in the worst-case, every block is scheduled by the operating system to complete before its deadline.
Today, it is difficult to build efficient and predictable real-time systems on modern processors, because the execution time of a piece of code exhibits a large variability. The worst-case can be hundreds of times larger than the best-case, due to dynamically varying paremeters such as the state of cache memories for instance. Therefore, the designer needs to greatly over-provision the computational capacity of the processors, leading to a higher cost of the system. The continued demand for additional functionalities makes the situation unsustainable in the long term. While some methods have been proposed to deal with such large variations, they are not immediately applicable because they focus on scheduling without considering the functional aspects of the application.
The overall objective of this project is to contribute to the design and development of the next generation of safety critical embedded real-time systems. In particular, we aim at solving the problem of the large variability of execution times by using sound and provably correct programming models that combine functional and timing aspects.
The main idea can be summarised as follows. First, we will use parametric Worst-Case Execution Time analysis techniques for computing off-line a WCET formula. The formula is parametrised with respect to input values of the code block and to state of the processor cache. Then, we plan to use the formula at run-time to dynamically estimate a tighter upper bound to the execution time. The execution time estimation will be used at run time to dynamically select the application behaviour so as to avoid deadline misses. The designer will specify the behaviour of the system by using a synchronous language to formally guarantee at the same time functional and timing correctness. Finally, we propose to use a design methodology to help the designer configure the system in the best way.

Mots clefs / Keywords :
Langages de programmation et de specification,
Modèlesde calcul pour le prallélisme, la répartition, la mobilité, la sécurité des systèmes embarqués, les objets connectés et temps réel