• Intitulé: Intégration d'éléments Sémantiques dans l'Analyse d'Ordonnançabilité des Applications temps-Réel
  • Directeur de thèse: Annie Choquet-Geniet
  • Co-directeur de thèse: Guy Vidal-Naquet
  • Jury de thèse: Emmanuel Grolleau (président), Franck Pommereau (rapporteur), Frank Singhoff (rapporteur), Christophe Aussaguès (examinateur), Annie Choquet-Geniet (examinateur), Guy Vidal-Naquet (examinateur)
  • Mots clefs: Tests Conditionnels, Réseaux de Petri, Arbre d'ordonnancement, Sémantique, Validation
  • Mention: Très honorable
  • Soutenance: 20 février 2012
  • Financement: Bourse de la région Poitou-Charentes --- (36 mois)

Nous étudions la modélisation et la validation hors-ligne des applications temps-réel en environnement monoprocesseur. Ces applications sont composées d’un ensemble de tâches. Dans notre étude, nous prenons en compte explicitement l'échange des messages, le partage des ressources et les instructions
conditionnelles.

Notre objectif est de mettre en évidence, puis de prendre en compte, les relations sémantiques, induites par les tests conditionnels, pouvant exister entre les tâches. Ces relations sont d'une part, les relations à l'intérieur d'une tâche, qui concernent les corrélations entre les comportements choisis dans des conditionnelles successives, portant sur une même valeur, et d'autre part, les relations entre plusieurs tâches, qui proviennent du fait que si elles examinent le même paramètre afin de déterminer leur comportement, ceux-ci  seront interdépendants.

Classiquement, les applications qui comportent des tests conditionnels sont modélisées de façon linéaire, en encapsulant les blocs conditionnels, et les séquences d'ordonnancement sont utilisées pour leur validation. Cette approche ne permet pas d'obtenir et de valider l'ensemble des comportements effectifs de l'application. C'est la raison pour laquelle nous proposons dans ce travail, une approche de modélisation arborescente, qui permet de considérer de façon explicite les blocs conditionnels.

Par ailleurs, nous construisons et analysons les arbres d'ordonnancement. Ces arbres permettent de valider les applications sur les plans comportementaux et sémantiques (en représentant tous les comportements effectifs), structurels (en vérifiant que toutes les primitives temps-réel sont prises en compte dans le bon ordre) et temporels (respect des délais critiques, des périodes et dates d'activation des tâches). Nous comparons ensuite ces deux approches de validation, et prouvons que les approches de validation linéaires, par encapsulation, sont parfois trop pessimistes, c'est à dire qu'elles peuvent conduire à déclarer certaines applications comme non ordonnançables, alors qu'en réalité elles sont ordonnançables lorsqu'on utilise les arbres d'ordonnancement et les approches arborescentes.

L'approche arborescente, plus détaillée, est donc parfois nécessaire. Nous construisons un générateur qui prend en entrée l'ensemble des codes des instances des tâches de l'application, et fournit en sortie l'ensemble de tous les arbres d'ordonnancement valides sur les plans comportementaux et sémantiques. Ensuite nous en éliminons les instances non valides structurellement ou temporellement.

La complexité du générateur étant exponentielle en fonction du nombre de tâches de l'application, cette approche est difficile à mettre en oeuvre. Nous proposons donc enfin, et validons, par construction d'invariants, une approche de modélisation basée sur les réseaux de Petri colorés avec ensemble terminal et fonctionnant sous la règle du tir maximal, qui permet de gérer les contraintes sémantiques, structurelles et temporelles qui nous intéressent.

Ce réseau est constitué de trois parties: une partie pour la gestion des aspects temporels (date de premier réveil, activation, période ...), une pour la gestion des comportements des tâches et enfin une dernière pour la prise en compte des aspects sémantiques (comportements incohérents ...). Le réseau construit sera utilisé pour générer les arbres valides, par construction du graphe de marquages, et la complexité pourra être réduite grâce à des heuristiques.

Nous avons appliqué ces travaux dans le domaine de l'automobile (système embarqué à l'intérieur d'un véhicule) et dans le domaine de la navigation (le radar dans un bateau). Néanmoins, c'est un travail qui peut s'appliquer dans tous les domaines où on manipule des systèmes temps-réel.