Configuration d’ordonnancement de systèmes temps réel embarqués

Encadrants : 

Occurrences : 

2016

Nombre d'étudiants minimum: 

2

Nombre d'étudiants maximum: 

3

Nombre d'instances : 

1

Contexte

Ce projet porte sur l’ordonnancement de systèmes embarqués temps réel critiques sur processeur multi-cœurs. Les systèmes temps réel doivent respecter des échéances temporelles strictes et un tel comportement est d’autant plus important qu’un non-respect peut entrainer des défaillances et éventuellement des pertes humaines.

Description

Afin de garantir un bon comportement, les ordonnancements proposent des tests assurant que le système et les tâches qu’il exécute va se comporter comme prévu compte tenu de ses paramètres temporels (échéances et pires temps d’exécution des tâches). Ces tests impliquent des calculs sur des nombres entiers et font appel à des fonctions affines par morceaux, les intervalles étant imposés par les échéances de temps.

Certaines approches d’ordonnancement utilisent des techniques fondées sur les serveurs d’exécution. Un serveur dispose d’un taux d’utilisation du processeur et il est rechargé en temps d’exécution à certaines échéances. Les temps d’exécution qu’il détient sont donc caractérisés par une fonction affine par morceaux appelée supply bound function (sbf). Il offre ce temps pour permettre l’exécution des tâches qu’ils contrôlent. Celles-ci vont donc s’exécuter lorsque le serveur dispose encore de budget de temps. La fonction de consommation des tâches est également une fonction affine par morceaux appelée demand bound function(dbf).

Pour vérifier qu’un ordonnancement de serveur d’exécution il faut assurer que l’offre est supérieure à la demande à tout instant dans le temps. Il faut donc comparer les fonctions sbf(t) et dbf(t) pour tout instant t.
Il se trouve que déterminer quelles tâches doit s’exécuter dans quel serveur d’exécution pour pouvoir utiliser certaines techniques d’ordonnancement, constitue un problème très difficile pour lequel il faut utiliser des heuristiques. De sorte que la comparaison des fonctions ci-dessus doit être effectuée un très grand nombre de fois.

Travail

On écrira en Python un programme de comparaison de fonctions affines par morceaux. Les élèves devront se former à Python et proposer une implémentation et des structures de données efficaces pour que cette comparaison puisse être utilisée un très grand nombre de fois. Le choix du langage Python est imposé par le reste de l’environnement de calcul qui se trouve être implanté en Python.

À ce propos, les données seront fournies dans le format actuel des données de l’environnement. Il conviendra éventuellement de les convertir afin de faciliter et accélérer les calculs demandés. Il faudra naturellement équiper le code de sondes pour mesurer le temps d’exécution et proposer diverses implantations pour déterminer la ou les solutions les plus appropriées.

Les calculs devront se faire en nombres rationnels.