Axes de recherche de l'équipe Systèmes Embarqués Temps Réel (SETR)

Nous considérons le problème de l'ordonnancement pour des systèmes de tâches non indépendantes à échéances strictes. Nous nous intéressons aux techniques d'ordonnancement hors ligne : une séquence est calculée avant l'exécution de l'application et est ensuite implémentée dans une table au niveau du séquenceur. Ces techniques s'appuient généralement sur des approches orientées modèles. Celles-ci présentent deux atouts majeurs.

• Limitent au maximum la surcharge processeur liée à l'ordonnancement, puisque aucun algorithme d'ordonnancement n'est exécuté.
• Basées sur une exploration exhaustive de l'espace des solutions (l'ensemble de toutes les séquences possibles) et donc, s'il existe une séquence valide, elles sont assurées de la trouver. Cela confère donc à ces méthodes une puissance d'ordonnancement supérieure à celle des méthodes en-ligne (i.e. qui consiste à implémenter un algorithme qui s'exécute en même temps que l'application).

Nous envisageons des approches orientées modèle à base :

• de réseaux de Petri ;
• de géométrie discrète ;
• de modèles à base de techniques markoviennes.

Les problèmes que nous traitons sont :

• la prise en compte explicite des instructions conditionnelles dans l'ordonnancement : arbres d'ordonnancement, ordonnançabilité forte ;
• la prise en compte d'aspects sémantiques dans l'ordonnancement ;
• l'étude de l'évolutivité des applications en environnement multiprocesseur : adjonction de tâches périodiques ou apériodiques ;
• la caractérisation géométrique des comportements équitables ;
• les mesures d'équité en vue soit de l'extraction de séquences le plus équitables possible, soit d'une répartition équitable des temps creux ;
• l'étude des propriétés de cyclicité en environnement multiprocesseur ;
• l'analyse qualité des procédés d'ordonnancement.

Les systèmes d’exploitation temps réel définissent des tâches récurrentes. Les tâches temps réel sont généralement réveillées périodiquement. Typiquement, une tâche périodique reçoit en entrée les données de capteurs et command un processus en envoyant des données aux actionneurs. Chaque exécution d’une tâche est appelée une instance qui devra terminer son exécution avant son échéance. La majorité des noyaux temps réel implémente un ordonnancement dirigé par les priorités. L’ordonnancement est construit à l’exécution en choisissant pour exécution la tâche la plus prioritaire parmi les tâches prêtes. A chaque instant la tâche de plus forte priorité est exécutée. Dans la littérature sur l’ordonnancement en-ligne, l’ordonnancement temps réel se caractérise par le fait que les durées des tâches ne sont pas connues avec exactitude avant la fin de la tâche. De plus la durée d’exécution d’une tâche varie d’une instante à une autre. Ainsi, seulement la pire durée d’exécution d’une tâche est supposée connue (Wcet). Un ordonnanceur temps réel en-ligne est dit optimal s’il construit un ordonnancement faisable s’il en existe un pour le système de tâches considéré.

Deux problèmes sont principalement étudiés en ordonnancement temps réel en-ligne.

• Le problème de faisabilité, qui vise à déterminer un algorithme d’ordonnancement en-ligne qui conduira à respecter les échéances des tâches.
• Le problème d’ordonnançabilité, qui pour un algorithme d’ordonnancement donné, détermine si les échéances des tâches seront respectées durant l’exécution des tâches.

Ces problèmes de faisabilité/ordonnançabilité sont fortement dépendants des modèles de tâches, des protocoles de gestion des ressources partagées, des mécanismes de synchronisation/communication des tâches et des plateformes matérielles considérés. Ces problèmes de faisabilité/ordonnançabilité sont des problèmes de décision fortement combinatoires. Pour bon nombre de ces problèmes, seules des conditions suffisantes sont connues pour établir qu’un ordonnancement respectera ou non les échéances des tâches.

Dans l’équipe sont étudiés les thèmes suivants :

• l’analyse des transactions temps réel et des tâches dépendante ;
• l’approximation des temps de réponse des tâches ;
• l’analyse des tâches autorisées à se suspendre elles-mêmes ;
• l’analyse et la configuration des systèmes distribués.