Contexte

Les architectures matérielles multiprocesseur et notamment multicœur sont maintenant de plus en plus déployées au sein des systèmes temps réel embarqués. Avec elles, se pose le problème de l’ordonnancement temps réel multiprocesseur : définir des règles d’allocation spatiale et temporelle des ressources d’exécution aux différentes tâches applicatives de sorte à respecter leurs contraintes temporelles d’exécution. Depuis une bonne dizaine d’années, cette problématique suscite un fort intérêt de la part de la communauté scientifique de l’ordonnancement temps réel et de nombreuses techniques ont été proposées. Parmi celles-ci et les plus récentes, se distinguent des stratégies optimales en ce sens qu’elles permettent théoriquement une utilisation totale des ressources matérielles. Toutefois cette optimalité est généralement obtenue au prix d’algorithmes peu performants, donnant lieu à de nombreux ré-ordonnancements, préemptions et migrations de tâche. Avant d’envisager la mise en œuvre effective de telles politiques au sein d’un système d’exploitation temps réel, il est indispensable d’en évaluer et comparer les performances. C’est dans ce contexte que l’équipe « Systèmes Temps Réel » de l’IRCCyN a développé une plate-forme logicielle de simulation de politique d’ordonnancement temps réel multiprocesseur appelée STORM - « Simulation TOol for Real-time Multiprocessor scheduling » [http://storm.rts-software.org/]. A partir de la spécification d’une architecture logicielle composée de tâches temps réel, d’une architecture matérielle composée de processeurs et d’une politique d’ordonnancement, elle réalise la simulation de l’exécution des tâches sur les processeurs dans le respect des règles de l’ordonnancement. Les données d’entrée actuelles de STORM sont spécifiées au travers d’un fichier XML. Le résultat de la simulation est un ensemble de traces d’exécution présentées sous forme de diagrammes de Gantt ou bien enregistrées dans des fichiers de sortie pour une analyse par des outils externes. STORM est un outil ouvert en ce sens qu’il permet par simple écriture de nouveaux composants (sous la forme de classes Java) d’étendre ses bibliothèques, en particulier celle déjà bien riche de ses politiques d’ordonnancement.

Sujet

Une politique d’ordonnancement temps réel multiprocesseur optimale appelée RUN a été très récemment publiée [1]. Elle s’appuie sur une approche originale de réduction du problème multiprocesseur en une série de problèmes monoprocesseur (plus simples) et ses auteurs lui confèrent des performances intéressantes. Notre intention est donc d’en faire une évaluation comparée à l’aide de STORM.

Le travail de Master consistera, dans un premier temps, à mener une étude approfondie du principe innovant de cette nouvelle politique d’ordonnancement. Une fois la technique appropriée, il s’agira de développer un composant ordonnanceur pour STORM la mettant en œuvre. Enfin, une étude expérimentale de nature statistique menée sur des jeux d’essai dejà utilisés dans nos travaux dans ce domaine sera conduite et devrait permettre de positionner les performances de ce nouvel algorithme vis-à-vis des autres.

Compétences attendues

Programmation Java et Matlab

Références

[1] P. Régnier, G. Lima, E. Massa, G. Levin, S. Brandt, “RUN : Optimal multiprocessor real-time scheduling via reduction to uniprocessor”, RTSS 2011 – Real-Time Systems Symposium, December 2011, pp. 104-115