Ordonnancement hors ligne

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.