Tests d’ordonnançabilité
Ordonnancement temps réel - Ordonnancement monoprocesseur

2.1 Principes

Lorsque la politique d’ordonnancement est donnée, par exemple, elle peut être contrainte par le noyau temps réel utilisé, la question posée est : le système est-il ordonnançable avec la politique choisie ? Le test utilisé s’appelle alors un test d’ordonnançabilité. Il est utilisé pour démontrer que, dans le pire cas possible correspondant au système, toutes les contraintes temporelles sont satisfaites. Il faut donc d’une part s’assurer que le test s’applique au modèle d’application choisie, que le pire cas soit caractérisable, et que le test soit viable, c’est-à-dire que le pire cas pris en compte corresponde effectivement à un pire cas au niveau ordonnancement. Un facteur important est la complexité temporelle du test : en effet, pour passer à l’échelle d’applications de taille conséquente (plusieurs centaines de tâches), il est préférable que la complexité du test soit polynomiale, ou au pire pseudo-polynomiale.

Un test d’ordonnançabilité consiste donc :

1. étant donné un modèle de l’application,

2. étant donnée une politique d’ordonnancement exécutée sur un type d’architecture,

3. établir un pire cas, ou à défaut un majorant des pires cas,

4. proposer un test sur le pire cas, viable et prédictible dans ce contexte, qui, s’il est vrai, implique que tout comportement de l’application conforme à son modèle respecte ses contraintes.

Propriétés du test :

• lorsque l’implication du point 4 est une équivalence, alors le test est réputé exact sur le pire cas, sinon, c’est une condition suffisante d’ordonnançabilité,

• si le pire cas est atteignable pour l’application, alors le test est exact sur le modèle de l’application, sinon c’est une condition suffisante sur le modèle de l’application,

• la complexité algorithmique du test est celle de l’item 4.

Par exemple, supposons un modèle d’application constitué de tâches indépendantes, sporadiques, à échéances contraintes, une politique d’ordonnancement à priorités fixes, Deadline Monotonic, sur un système monocœur. Le pire cas pour une tâche se produit lorsqu’elle est réveillée simultanément avec toutes les tâches...