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

Les systèmes informatiques peuvent être classés en trois catégories : les systèmes transformationnels, les systèmes réactifs et les systèmes interactifs. Les systèmes transformationnels transforment des données d’entrée en données de sortie à leur propre rythme, sans interaction avec leur environnement. Les systèmes interactifs représentent typiquement la classe des programmes avec une interface graphique. Ils répondent aux demandes d’un utilisateur, et il est bienvenu qu’ils y répondent rapidement. Les systèmes réactifs sont en charge de contrôler des procédés. Un procédé est un système physique à contrôler, possédant son propre environnement. Par conséquent, le système réactif doit réagir suffisamment rapidement par rapport à la dynamique du procédé contrôlé et de son environnement. Contrairement aux autres catégories, les systèmes réactifs ne présentent pas de comportements récurrents : le procédé évoluant avec sa propre dynamique dans un environnement souvent complexe, il est rare que des scénarios d’exécution système réactif/évolution du procédé dans son environnement soient reproductibles.

Les systèmes informatiques contrôlant des procédés physiques critiques, notamment dans le domaine du transport, de l’exploration autonome, etc., sont typiquement embarqués sur le procédé lui-même. On parle alors de système embarqué critique. De tels systèmes sont souvent soumis à des contraintes de temps inhérentes à la dynamique du procédé contrôlé. On dit alors qu’ils sont temps réel. Un système temps réel est un système réactif, en charge de s'assurer du maintien d’un procédé (drone, système automobile ou avionique, etc.) dans un état désiré, tout en assurant une réactivité du système qui soit cohérente avec les contraintes de temps inhérentes au procédé et à son environnement. Malgré l’accroissement de la puissance des calculateurs, d’abord en fréquence, puis en nombre de cœurs de calcul depuis le début des années 2000, les calculateurs embarqués sont dimensionnés au plus juste des besoins en puissance de calcul de façon, notamment, à minimiser l’énergie consommée, et donc l’autonomie du procédé.

Deux hypothèses sont communément à la base d’un partitionnement au niveau des modèles, des méthodes et des problématiques traités : l’hypothèse synchrone et l’hypothèse asynchrone. L’hypothèse synchrone considère que les traitements sont déclenchés directement par l’arrivée d’événements. Les traitements sont considérés comme ayant une durée nulle, ou en tout cas inférieure à l’écart minimal séparant deux événements déclencheurs successifs. L’hypothèse asynchrone se repose sur le paradigme de programmation multitâche : des événements peuvent, comme dans le cas synchrone, déclencher des traitements. Cependant, les traitements sont considérés de durée non nulle. Par conséquent, un traitement peut être préempté par un autre, c’est-à-dire interrompu, et mis en attente, pour affecter les ressources de calcul à un autre traitement plus prioritaire par exemple.

Dans le cadre de cet article, nous considérons l’hypothèse asynchrone. Nous considérons que cette hypothèse est réaliste, notamment dans le cas des systèmes embarqués. Dans ce cas, les ressources de calcul se doivent d’être dimensionnées au plus juste de façon à maximiser l’autonomie énergétique du système. L’un des points centraux sous-jacents à l’hypothèse asynchrone est la gestion des ressources de calcul, et notamment du processeur. En fonction des traitements à exécuter à un instant donné, que nous appellerons des tâches, c’est le rôle de l’ordonnanceur de décider quelle tâche est exécutée sur le processeur, en fonction d’une stratégie d’ordonnancement.

L’ordonnanceur est l’entité centrale du noyau, cœur de l’exécutif ou système d’exploitation en charge de la gestion des ressources matérielles. Parmi les tâches prêtes à être exécutées, il choisit la tâche à exécuter suivant une certaine stratégie. Il y a deux grandes familles d’ordonnanceur : les ordonnanceurs en-ligne connaissent l’état courant des tâches actives, et se basent souvent sur des priorités pour choisir la tâche à élire. Les ordonnanceurs hors-ligne, souvent appelés séquenceurs, se basent sur la connaissance totale du système actuel, et de son futur, qui a permis, hors-ligne, de bâtir à l’avance une séquence d’ordonnancement qui est suivie à l’exécution. Dans cet article, nous parlerons principalement d’ordonnancement en-ligne qui est le type d’ordonnancement le plus répandu.

Le système de contrôle est donc multitâche, et les tâches sont ordonnancées par l’ordonnanceur. Il s'informe de l'état courant du procédé contrôlé à l'aide de capteurs, et agit sur celui-ci à l'aide d'actionneurs. Les contraintes de temps peuvent être de deux natures : les contraintes de bout-en-bout concernent une chaîne de traitement partant d'un ensemble de capteurs et se terminant à un ensemble d'actionneurs ; des contraintes locales dues à des limitations matérielles. Ainsi, lorsqu’un capteur fournit des informations au système en utilisant un bus de communication, sans l’aide d’un dispositif de mémorisation (de type buffer), le système doit lire des données entrantes avant qu’elles ne soient écrasées par les suivantes. Il arrive aussi qu’une commande envoyée à un actionneur doive absolument être rafraîchie à un certain rythme. De façon générale, dans la théorie utilisée pour la validation temporelle, toutes les contraintes temporelles, qu’elles soient locales ou de bout-en-bout, sont traduites sous forme de contraintes locales sur les tâches.

Le respect des contraintes temporelles est plus ou moins important : la violation de certaines contraintes peut mettre le système ou bien son environnement en péril : on parle alors de contraintes strictes. Au contraire, certaines contraintes concernent uniquement la qualité du service rendu par le système, dans ce cas on parle de contraintes relatives. Par exemple, l’attitude d’un aéronef peut être instable si le contrôle d’attitude (tangage, roulis) ne peut être exécuté une fois toutes les 50 millisecondes. Les contraintes de temps appliquées aux tâches du contrôle d’attitude sont strictes. On parle de contraintes fermes lorsque, sur une fenêtre temporelle donnée, un certain nombre de contraintes doivent être respectées afin de garantir l’intégrité du système. Respecter toutes les contraintes de temps augmente dans ce cas la qualité de service de l’application. On trouve peu de contraintes relatives dans le domaine du transport, mais on peut en trouver dans les applications non critiques telles les applications multimédia, ou le jeu vidéo. Dans cet article, seules les contraintes strictes sont considérées.

La problématique qui nous intéresse ici est comment assurer qu’étant donné un système de tâches partageant des ressources de calcul, toutes les contraintes temporelles seront toujours respectées : c’est la validation temporelle, qui repose sur une étude d’ordonnançabilité. Résoudre ce problème permet aussi de répondre à la question du dimensionnement : quelles ressources de calcul sont-elles nécessaires à une application temps réel donnée ?

Il est important de garder à l’esprit que « temps réel » ne signifie pas « rapidité », mais « temporellement déterministe ». Ainsi, on privilégie toujours le déterminisme à la vitesse d’exécution moyenne. La validation temporelle repose en effet sur le fonctionnement pire cas du système : il est primordial, sur un système critique, que le système ne se comporte jamais de manière erronée, et il est généralement intolérable que le système ne se comporte très bien qu’en moyenne, en étant parfois erroné. La validation des systèmes critiques se base donc sur les pires comportements du système : elle se doit donc d’être conservative, on parle aussi de pire cas.

Cet article est structuré de la façon suivante : afin de présenter le contexte global dans lequel la problématique de l’ordonnancement est soulevée, le chapitre 1 introduit les architectures matérielles et logicielles des applications. Nous verrons en particulier le fonctionnement de base des systèmes d’exploitation temps réel. Après avoir introduit les principes fondamentaux de l’ordonnancement temps réel, nous présentons les modèles temporels des tâches, qui seront utilisés lors de la validation temporelle. Ce chapitre introduit enfin les principaux types d’algorithmes d’ordonnancement, et les propriétés et mesures permettant de les caractériser.

Le chapitre 2 se focalise sur les tests d’ordonnançabilité, c’est-à-dire sur les moyens utilisés pour montrer qu’un système ordonnancé par un ordonnanceur respectera toujours toutes ses contraintes de temps. Nous commençons par les modèles les plus simples (tâches indépendantes), pour lesquels nous montrons les types de tests, classés par familles d’algorithmes d’ordonnancement considérées. Nous élargissons ensuite ces tests au cas de tâches communicantes ou se synchronisant.

Les derniers chapitres introduisent des outils liés à l’analyse d’ordonnançabilité et des points d’entrée vers des travaux plus spécifiques. Tout au long de cet article, certains points d’entrée de références bibliographiques seront cités. Le lecteur est invité à consulter [Doc. S 8 055v2] pour trouver les références complètes des travaux cités.