Ordonnancement en ligne

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.