Précédent Index Suivant

Chapitre 3   Ordonnancement et Analyse d'ordonnancement

Dans ce chapitre, nous introduisons tout d'abord la problématique de l'ordonnancement en temps-réel, dans le contexte du modèle de système décrit précédemment. Nous citons ensuite une série de résultats scientifiques qui ont été obtenus dans ce domaine central de l'ingénierie temps-réel. Nous commençons par dresser un panorama des contraintes et propriétés d'ordonnancement, avant de donner les propriétés des problèmes algorithmiques associés en termes de complexité, et les grandes classes d'approches courantes (section 3.2). Nous développons ensuite plus avant les propriétés d'une classe particulière d'ordonnancement (à priorités simples ; section 3.3) pour des systèmes constitués exclusivement de tâches temps-réel strict, avec ou sans prise en compte des coûts système, avec ou sans contraintes de ressources, avec ou sans contraintes de précédence. Puis nous levons progressivement les restrictions de ce modèle : support de tâches apériodiques (section 3.4), gestion de la surcharge (section 3.5), techniques d'ordonnancement qui ne sont pas à priorités (section 3.6), ordonnanceurs qui s'adaptent à un manque d'informations sur le comportement du système ou de l'environnement (section 3.7). Nous terminons par un aperçu des méthodes d'ordonnancement sur systèmes multiprocesseur ou distribués (section 3.8).

3.1   Problématique de l'ordonnancement en temps-réel

3.1.1   Description

Nous nous concentrons sur une pièce fondamentale d'un système temps-réel : l'ordonnanceur. Pour chaque processeur, l'ordonnanceur est en charge de définir l'ordonnancement, qui est une séquence infinie d´éléments du type : (date, identifiant_travail). Chaque élément correspond à l'élection de la tâche à exécuter, puis à un changement de contexte, qui fait suite à une décision d'ordonnancement par l'ordonnanceur.

La problématique de l'ordonnancement revient à définir comment agencer les exécutions des tâches sur chaque processeur. Un ordonnancement est faisable (feasible schedule en anglais), si toutes les contraintes temporelles et de ressources sont respectées (voir section 3.1.2 ci-dessous). Suivant les caractéristiques du modèle de tâches et du système, un ordonnancement faisable peut exister ou non. Lorsqu'un tel ordonnancement existe, le système temps-réel est dit ordonnançable (schedulable en anglais). Un système est dit ordonnançable par un algorithme donné si l'ordonnancement qui en résulte est faisable.

L'objectif que poursuit l'analyse statique hors-ligne est d'établir l'ordonnançabilité du modèle, et/ou la faisabilité d'un l'ordonnancement donné. Ce sont les propriétés des problèmes étudiés lors de cette phase d'analyse, et quelques solutions, que nous présentons dans la suite de cette étude.

3.1.2   Critères et métriques usuels de spécification de contraintes de validité

Pour le temps-réel strict, le critère de validité fondamental est que toutes les tâches temps-réel strict respectent toutes leurs contraintes temporelles en toute circonstance nominale de fonctionnement. Au delà de cette contrainte fondamentale que nous développons plus loin dans le présent chapitre, différents mécanismes peuvent être comparés par des mesures quantitatives sur leur comportement, en s'inspirant des travaux en temps-réel souple.

En temps-réel souple, les contraintes de validité peuvent faire appel à des données numériques caractérisant le comportement du système. Suivant la complexité du système, il est possible de les obtenir par analyse (le plus souvent statistique) ou par évaluation (le plus souvent par simulation). Parmi les métriques les plus courantes, citons :
le taux de respect :
c'est la proportion de travaux des tâches qui respectent leurs contraintes temporelles. Hit ratio en anglais. Lorsque les tâches doivent subir un test préventif lors de leur activation et avant leur exécution, afin de vérifier que leurs contraintes temporelles pourront être respectées sans remettre en cause le reste du système (test d'acceptation, voir 3.4.2), on parle de taux de garantie (guarantee ratio en anglais).
la valeur dégagée :
on associe à l'exécution de chaque tâche une fonction de valeur, et on mesure la somme (ou une autre fonction) des valeurs obtenues pendant le déroulement du système [BSS95]. Hit value ratio en anglais. Par exemple, on peut représenter une tâche temps-réel ferme par la fonction de valeur suivante : si la tâche se termine avant son échéance, elle dégage la valeur X > 0, et 0 sinon. Un cas particulier est celui où X vaut 1, auquel cas la valeur dégagée (completion count en anglais) est directement liée au taux de respect. D'autres fonctions de valeur font intervenir le temps d'exécution (effective processor utilization en anglais) [BHS01], ou d'autres paramètres [AB99].
le débit :
c'est le nombre de travaux d'une tâche qui respectent leurs contraintes temporelles par fenêtre de temps donnée [WS99b]. Throughput en anglais. En multimédia par exemple, il peut s'agir de la mesure du nombre d'images rendues par seconde (fps pour frames per second).
le seuil d'utilisation :
c'est l'utilisation du processeur au dessus de laquelle des tâches commencent à dépasser leurs contraintes temporelles [VJP97, KAS93]. Utilization breakdown en anglais.
les caractéristiques temporelles
(voir 2.1.1.2) telles que le retard, la gigue de démarrage, la laxité, le temps de réponse par exemple. Le cas particulier de la validation de tâches temps-réel strict consiste à garantir au moins que le retard maximal pour ces tâches est négatif ou nul.
les coûts systèmes
(voir 2.2.2.2) tels que les coûts d'ordonnancement par exemple.
La majorité de ces métriques évoluent au cours du temps. L'évaluation du modèle, ou sa validation font alors intervenir les propriétés de leur distribution, telles que le maximum, le minimum, ou les caractéristiques statistiques (moyenne, écart-type par exemple). Le mode d'évaluation s'intéresse en général au régime permanent (stimuli de l'environnement réguliers), et plus rarement aux régimes transitoires [LSA+00] (délai de rétablissement, sur-utilisation temporaire). Lorsqu'il s'agit de proposer un nouveau mécanisme système pour le temps-réel, on le soumet à ces techniques d'évaluation, en intégrant dans le modèle ou dans l'implantation à évaluer soit des jeux de tests issus de systèmes réels (tels que ceux présentés dans [CFBW93, ABR+93, Tin92a, Aud91, Bur93, TC94, TBW92a, BWH93]), soit des jeu de tests générés aléatoirement.

Pour des spécifications données qui émettent des contraintes sur ces paramètres, la validation peut se faire à deux niveaux du cycle de développement : au niveau du modèle issu de la conception (évaluation a priori), et au niveau de l'implantation (évaluation a posteriori). Nous nous intéressons dans la partie suivante à l'évaluation et à la validation pour ces deux étapes, et présentons quelques méthodes.

3.2   Caractéristiques des problèmes et des méthodes d'ordonnancement

Après avoir introduit quelques éléments de terminologie (section 3.2.1), nous décrivons les caractéristiques de quelques problèmes d'ordonnancement (section 3.2.2), et présentons les grandes classes de solutions courantes à ces problèmes (section 3.2.3).

3.2.1   Classes des problèmes

On indique ici les caractéristiques liées aux systèmes cible de l'ordonnancement ou à l'ordonnancement lui-même, qui forment les paramètres du problème d'ordonnancement qu'on cherche à résoudre.

Monoprocesseur/multiprocesseur
L'ordonnancement est de type monoprocesseur si toutes les tâches ne peuvent s'exécuter que sur un seul et même processeur. Si plusieurs processeurs sont disponibles dans le système, l'ordonnancement est multiprocesseur.

Préemptif/non-préemptif
L'ordonnancement (en-ligne ou hors-ligne) est préemptif lorsque les préemptions (voir 2.1.1.1) sont autorisées. On peut remarquer que dans le cas des ordonnanceurs monoprocesseur, la problématique de la synchronisation sur ressource n'existe pas en non-préemptif puisque il ne peut pas y avoir de concurrence sur l'accès aux ressources en l'absence de préemption.

Avec/Sans insertion de temps creux : oisif/non oisif
L'ordonnanceur peut avoir la propriété suivante : à partir du moment ou au moins une tâche est prête à être exécutée, alors l'ordonnanceur en élit forcément une parmi elles. Dans ce cas, l'ordonnanceur est non oisif, c'est à dire qu'il fonctionne sans insertion de temps creux (non-idling ou work-conservative en anglais).

Dans certains cas, un système peut n'être ordonnançable qu'en n'élisant aucune tâche pendant un certain temps, alors qu'il en existe au moins une prête à être exécutée. Dans ce cas, l'ordonnanceur est oisif, c'est à dire qu'il fonctionne par insertion de temps creux (with inserted idle times en anglais). Par exemple, le système de tâches de la figure 3.1 (les notations sont introduites figure 2.4, section 2.1.1.2) n'est pas ordonnançable en non-préemptif non oisif (figure 3.1(a)), alors qu'il est ordonnançable en non-préemptif oisif (figure 3.1(b)). On peut remarquer que la définition d'un ordonnancement oisif repose sur la connaissance des activations à venir.

[Non-oisif]
[Oisif]
[b].32
  T1 T2
Date d'activation 0 1
WCET 3 1
Échéance absolue 5 3

 
 

Figure 3.1 : Intérêt de l'ordonnancement oisif en non-préemptif

En-ligne/hors-ligne
Un ordonnancement hors-ligne (off-line en anglais) signifie que la séquence d'ordonnancement est prédéterminée à l'avance : dates de début d'exécution des tâches, de préemption/reprise éventuelles. En pratique, l'ordonnancement prend la forme d'un plan hors-ligne (ou statique), exécuté de façon répétitive (on parle aussi d'ordonnancement cyclique, qui définit le cycle majeur) : à chaque top d'horloge (on parle de cycle mineur) une tâche particulière du cycle majeur courant est exécutée jusqu'à terminaison ou jusqu'au top d'horloge suivant.

Un ordonnancement en-ligne correspond au déroulement d'un algorithme qui tient compte des tâches effectivement présentes dans la file d'ordonnancement (run-queue en anglais) lors de chaque décision d'ordonnancement. Les ordonnanceurs en-ligne peuvent reposer sur la construction de plans d'ordonnancements en cours de fonctionnement, auquel cas ils sont dits à plan dynamique [KSSR96]. Mais plus couramment, ces ordonnanceurs sont fondés sur la notion de priorité (voir 3.2.3.2).

Il est par ailleurs possible de transformer un ordonnancement à plan statique en ordonnancement en-ligne (par exemple à priorité statique préemptif [DFP01] ou non-préemptif [Bat98], ou à priorité dynamique [CA97]).

Centralisé/distribué
Lorsqu'un système est distribué, l'ordonnancement (en-ligne) est distribué si les décisions d'ordonnancement sont prises par un algorithme localement en chaque noeud.

Il est centralisé lorsque l'algorithme d'ordonnancement pour tout le système, distribué ou non, est déroulé sur un noeud privilégié.

Statique/dynamique
Les ordonnanceurs statiques fondent leurs décisions d'ordonnancement sur des paramètres assignés aux tâches du système avant leur activation. À l'inverse, les ordonnanceurs dynamiques fondent leurs décisions sur des paramètres qui varient en cours de fonctionnement du système.

Optimal/non optimal
Par définition, un algorithme d'ordonnancement optimal [GRS96] pour une classe de problème d'ordonnancement donné est tel que : si un système est ordonnançable (voir 3.1) par au moins un algorithme de la même classe, alors le système est ordonnançable par l'algorithme d'ordonnancement optimal. En conséquence, si un système n'est pas ordonnançable par un ordonnanceur optimal d'une classe donnée, alors il ne l'est par aucun ordonnanceur de la même classe.

3.2.2   Complexité des problèmes

Le problème qui consiste à définir un ordonnancement peut être ramené à un problème d'optimisation. Par exemple, beaucoup de travaux s'intéressent à minimiser le retard maximal parmi toutes les tâches (``Lmax'' dans la suite). Car une fois ce retard maximal minimisé, la correction temporelle du système est équivalente à vérifier que ce retard maximal est négatif ou nul.

Nous nous intéressons ici à la complexité [Coo71, Coo83, GJ79] de quelques problèmes pertinents pour l'ordonnancement [SSNB94][2].

Pour exprimer ces problèmes, une notation abrégée a été introduite [Rie98, SSNB94, But97, GLLK79, Mer92], que nous n'utilisons pas ici.

3.2.2.1   Ordonnancement monoprocesseur

Les tableaux 3.1 et 3.1 indiquent la complexité de quelques problèmes d'ordonnancement respectivement non-preéemptifs et préemptifs sur monoprocesseur.

monoprocesseur non-préemptif
tâches temps précédences ressources problème complexité  
concrètes creux        
non non non   minimiser Lmax polynomiale voir 3.2.3.2
non oui non   ordonnançabilité NP-complet [GJ79, HV95]
oui non non indifférent minimiser Lmax NP-complet [GJ79, JSM91]
oui non series-parallel1   minimiser Lmax2 polynomiale [SSNB94, Law78, GL95]
oui non oui   minimiser Lmax NP-difficile [SSNB94, Law78]
synchrones non oui   minimiser Lmax polynomiale [SSNB94, Law73]
 
monoprocesseur préemptif
tâches temps précédences ressources problème complexité  
concrètes creux        
non non non verrous seuls ordonnançabilité NP-difficile [Mok83]
non non non oui ordonnancement impossible [Mok83], voir 3.3.6
        optimal    
non + temps non non oui minimiser Lmax polynomiale [Mok83]
d'exécution            
tous égaux            
indifférent non non non minimiser Lmax polynomiale voir 3.2.3.2
indifférent non oui non minimiser Lmax polynomiale voir 3.2.3.2
indifférent non oui oui ordonnancement NP-difficile [SSNB94]

Table 3.1 : Complexité de problèmes d'ordonnancement monoprocesseur

On peut remarquer que le problème à résoudre est d'autant plus complexe que les préemptions sont interdites ou que les temps creux sont autorisés (insérer des temps creux dans l'ordonnancement revient à être capable de prévoir les activations à venir).

En pratique, pour résoudre les problèmes difficiles qui font intervenir des ressources et éventuellement des contraintes de précédences, il existe des ordonnancements statiques [JD90], des approches sub-optimales (telles que le kernelized monitor [Mok83]) ou des heuristiques (comme [Man98, MMM00b, RS94] par exemple), ou des protocoles pour accéder aux ressources en utilisant des algorithmes d'ordonnancement classiques (comme nous le verrons en 3.3.6).

3.2.2.2   Ordonnancement multiprocesseur

Nous nous intéressons ici aux systèmes multiprocesseur simples dans lesquels l'ordonnancement est centralisé et pour lesquels on suppose les temps de communication entre les noeuds nuls. Le tableau 3.2 présente quelques résultats de complexité : le problème considéré est celui qui consiste à déterminer un ordonnancement hors-ligne non-préemptif faisable. La plupart des résultats présentés dans ce tableau sont issus de [SSNB94].

multiprocesseur non-préemptif hors-ligne [SSNB94]
Nombre de ressources précédences temps d'exécution complexité
Processeurs        
2 non quelconques tous égaux polynomial
2 non non quelconques NP-complet
2 non quelconques 2 valeurs possibles NP-complet
2 oui non tous égaux polynomial [RS94]
2 1 forêt tous égaux NP-complet
3 1 non tous égaux NP-complet
N non forêt tous égaux polynomial
N non quelconque tous égaux NP-complet

Table 3.2 : Complexité d'ordonnancement non-préemptif hors-ligne pour multiprocesseur

Contrairement au cas monoprocesseur, en ordonnancement multiprocesseur hors-ligne, pour tout ordonnancement préemptif du système qui dégage une valeur donnée, on peut toujours trouver des ordonnancements non-préemptifs qui dégagent une valeur encore plus faible [McN59]. C'est le cas par exemple si la mesure de la valeur de l'ordonnancement est la somme des temps d'exécution des tâches correctement ordonnancées. En multiprocesseur, autoriser les préemptions ne facilite donc rien, et rajoute des surcoûts à l'exécution (liés aux changements de contexte). Ainsi, le résultat de complexité sur la configuration la plus simple en préemptif hors-ligne [Law83] reflète bien cette propriété :
préemptif, N processeurs, tâches quelconques, sans ressource, sans précédence : la définition d'un ordonnancement hors-ligne qui minimise le nombre de tâches en retard est un problème NP-difficile.
En ce qui concerne l'ordonnancement en-ligne pour multiprocesseur, il est prouvé [Mok83] qu'aucun algorithme d'ordonnancement en-ligne ne peut être optimal sans avoir la connaissance complète à l'avance de toutes les échéances, de tous les temps d'exécution, et de toutes les dates de démarrage des tâches. En pratique, on utilise des heuristiques (comme [Man98, MMM00b, RS94] par exemple) pour résoudre ces problèmes, comme nous le verrons en 3.8.3.3.

3.2.3   Solutions aux problèmes d'ordonnancement

Dans la suite, nous nous intéressons d'abord au problème le plus simple : l'ordonnancement monoprocesseur sans ressource et sans précédence. Nous présentons ici les solutions simples les plus courantes, et verrons comment ces solutions peuvent être aménagées pour supporter des systèmes avec ressources et contraintes de précédence.

3.2.3.1   Ordonnancement hors-ligne

L'ordonnancement hors-ligne repose sur la définition d'un plan statique. Cette politique d'ordonnancement possède l'avantage de se contenter d'un support d'exécution très réduit (l'accès à une base de temps suffit). Par là même, elle introduit un surcoût d'exécution lié à l'ordonnancement très faible [KFG+92] (il suffit que l'une horloge système incrémente la position courante dans le plan d'ordonnancement), car les traitements pour l'établissement du plan (comme [SA00, CCS02, Foh94] avec des algorithmes ad hoc, optimaux [JD90], ou par optimisation multi-critères [EJ00] par exemple) sont effectués hors-ligne, et peuvent se permettre d'être très complexes. En particulier, ce type d'ordonnancement se prête bien aux cas de systèmes complexes tels que les systèmes temps-réel distribués [SRG89] (le problème principal restant alors la synchronisation des horloges locales pour un déroulement cohérent du plan). Également, l'environnement n'influence pas le déroulement du plan, ce qui rend le système robuste car immunisé contre une partie des dépassements d'hypothèse dus à la mauvaise modélisation de l'environnement. Enfin, la garantie que le système respectera toutes ses contraintes temporelles est une propriété facile à appréhender : il ``suffit'' que le plan soit vérifié hors-ligne, et que les évaluations des temps d'exécution soient correctes. Ceci fait de cette solution celle qui paraît la plus rigoureuse et la plus stricte ; nous verrons cependant que dans les cas de systèmes centralisés simples il existe des solutions en-ligne qui offrent tout autant de garanties.

En contrepartie, il est nécessaire de se ramener à des plans périodiques, ou à des plans qui supposent connues toutes les dates d'arrivées (éventuellement non périodiques) de toutes les tâches. Cela conduit à sur-contraindre le système, en particulier quand on doit traiter des tâches périodiques de période non multiple du cycle mineur, ou des événements de fréquence d'occurrence maximale élevée mais de faible fréquence moyenne. Au mieux, ces contraintes excessives entraînent un surdimensionnement du système, et au pire l'impossibilité de déterminer un ordonnancement faisable. De plus, les plans générés sont très sensibles aux petites modifications du code ou des fonctionnalités qui peuvent être faites (ajout d'une tâche supplémentaire par exemple) : ces modifications affectent le plan dans son ensemble (non localité), ce qui pose problème d'intégration lorsque plusieurs acteurs (entreprises, ingénieurs) coopèrent sur le même projet (contraire aux contraintes de confidentialité par exemple). Un autre problème qui se pose est que le plan doit être capable de définir l'ordonnancement sur une durée égale à l'hyperpériode des tâches, qui peut être très grande, ce qui implique une grande consommation mémoire pour stocker le plan, inadaptée aux petits systèmes embarqués.

Il existe cependant des ordonnancements par plan statique qui peuvent être complétés par un algorithme d'ordonnancement en-ligne (comme [Foh94, IF99], par une méthode similaire à la réquisition de temps creux, que nous verrons en 3.4.1.2), afin de prendre en compte l'activation de tâches sporadiques ou apériodiques par exemple.

Nous ne détaillons pas davantage ce type d'ordonnancement dans ce travail. Dans la suite, nous intéressons aux algorithmes d'ordonnancement en-ligne.

3.2.3.2   Ordonnanceurs en-ligne

La majorité des ordonnanceurs temps-réel en-ligne reposent sur la notion de priorité : lors de chaque décision d'ordonnancement, la tâche de plus haute priorité est élue. Les priorités peuvent être attribuées hors-ligne, auquel cas l'algorithme d'ordonnancement est dit à priorité statique ou fixe ; ou en-ligne, auquel cas il est dit à priorité dynamique. 3

Ce type d'ordonnanceur est plus complexe que les ordonnanceurs à plan statique : les décisions d'ordonnancement consistent à élire la tâche prête de plus haute priorité. Dans le cas des ordonnanceurs à priorité dynamique, il s'agit en plus de déterminer les priorités relatives des différentes tâches prêtes, ce qui peut se révéler coûteux en terme de ressource processeur.

D'autre part, ce type d'ordonnanceur est plus exigeant en terme de services que doit fournit le support d'exécution : celui-ci doit entre autre pouvoir gérer des files de tâches à ordonnancer, et doit pouvoir déterminer quand une décision d'ordonnancement est nécessaire. Il en résulte par là même des appels à l'ordonnanceur plus fréquents qu'en ordonnancement hors-ligne, ce qui accroît encore le surcoût d'exécution engendré. En pratique, les supports d'exécution les plus courants et les standards disponibles les plus utilsés, fournissent les fonctionnalités nécessaires à l'ordonnancement à priorité fixe.

Comme nous le verrons par la suite, ces ordonnanceurs ont l'avantage de s'adapter aux évolutions de l'environnement (support des tâches sporadiques, admission de tâches apériodiques), ou du système (caractérisation temporelle incomplète de certaines parties du système par exemple). De plus, les algorithmes simples que nous décrivons ci-après peuvent être étendus pour supporter des modèles de tâches plus riches, des contraintes de précédence, ou des synchronisations de ressources, ce qui leur permet de rivaliser avec les ordonnancements hors-ligne de ce point de vue.

3.3   Ordonnanceurs à priorités simples

Dans cette partie, nous définissons les algorithmes d'ordonnancement à priorité fixe que nous considérons dans la suite (section 3.3.1), avant de donner quelques résultats d'optimalité les concernant (section 3.3.2). Nous indiquons ensuite les conditions d'ordonnaçabilité qui leur sont associées, pour un modèle de système très restrictif (section 3.3.3). Puis nous levons certaines restrictions du modèle (sections 3.3.4), avant de donner quelques extensions pour supporter des contraintes d'ordonnancement supplémentaires (section 3.3.5), et pour prendre en compte les accès concurrents à des ressources protégées (section 3.3.6). Nous concluons (section 3.3.7) par une petite discussion sur les choix d'ingénierie qui émanent des familles d'ordonnancement évoquées.

3.3.1   Politiques d'ordonnancement à priorités courantes

Nous nous plaçons ici dans le cadre simple de l'ordonnancement monoprocesseur non oisif à priorité, lorsque toutes les tâches sont indépendantes (pas de précédence, pas de ressource).

Les ordonnancements à priorités les plus courants sont les suivants :
EDF (pour Earliest Deadline First) : ordonnancement à priorité dynamique. Une tâche est d'autant plus prioritaire que sa date d'échéance absolue est proche de la date courante. Le cas particulier où les tâches sont synchrones est parfois appelé EDD (pour Earliest Due Date), ou algorithme de Jackson.
LLF (pour Least Laxity First) : ordonnancement à priorité dynamique. Les tâches sont d'autant plus prioritaires que leur laxité est faible à la date courante.
RM (pour Rate Monotonic) : ordonnancement à priorité statique pour tâches périodiques/sporadiques avec échéance relative égale à la période/délai d'inter-arrivée. Une tâche est d'autant plus prioritaire que sa période est petite.
DM (pour Deadline Monotonic) : ordonnancement à priorité statique pour tâches sporadiques. Une tâche est d'autant plus prioritaire que son échéance relative est petite. DM équivaut à RM quand l'échéance relative est égale à la période.
En dépit de leur simplicité, ces ordonnanceurs possèdent des propriétés relativement fortes. C'est ainsi qu'ils servent de base à quantités de variantes, comme nous le voyons par la suite.

3.3.2   Résultats d'optimalité

Les ordonnancements simples précédents ont les propriétés intéressantes suivantes :
  1. EDF et LLF sont optimaux parmi les ordonnancements préemptifs non oisifs [LL73]. EDF est également optimal relativement à la minimisation du retard maximal des tâches [But97].
  2. EDF est optimal parmi les ordonnancements non-préemptifs non oisifs [GMR95, GRS96].
  3. RM est optimal parmi les ordonnancements préemptifs non oisifs à priorité statique, pour tâches périodiques non-concrètes/synchrones ou sporadiques, lorsque l'échéance relative est égale à la période (ou au délai d'inter-arrivée dans le cas sporadique) [LL73].
  4. DM est optimal parmi les ordonnancements préemptifs non oisifs à priorité statique, pour tâches périodiques non-concrètes/synchrones ou sporadiques à échéance relative inférieure à la période [ABRW91, But97, LW82].
  5. Dans les cas où les tâches périodiques concrètes ne sont jamais synchrones, ni RM, ni DM ne sont optimaux parmi les ordonnancements préemptifs non oisifs à priorité statique. Dans [Aud91], on donne l'affectation optimale des priorités pour l'ordonnancement préemptif non oisif à priorité statique pour le cas général (i.e. qui reste valable quand les échéances relatives et les périodes ne sont pas reliées).
  6. DM est optimal parmi les ordonnancements non-préempifs non oisifs à priorité statique, pour tâches périodiques non-conrètes/synchrones ou sporadiques à échéance relative inférieure à la période [Bat98].
Pour l'ordonnancement à priorité dynamique, les démonstrations utilisent le fait que si on dispose d'un ordonnancement faisable, alors intervertir 2 tâches pour respecter l'ordre d'ordonnancement EDF ou LLF conserve la faisabilité de l'ordonnancement. Le même type de démonstration est utilisé avec les priorités des tâches pour démontrer l'optimalité de RM/DM.

3.3.3   Quelques conditions de faisabilité

Dans la suite, les notations suivantes seront utilisées : dans le système G de N tâches, chaque tâche ti, iÎ[1,N] possède un temps d'occupation4 sur le processeur Ci et une échéance relative Di. Si ti est périodique, Ti représente la période. Si ti est sporadique, Ti représente le délai d'inter-arrivée.

Le taux d'utilisation de ce système de tâches s'écrit alors : U = åi=1N Ci/Ti, et on rappelle qu'une condition nécessaire pour que le système soit faisable est U £ 1 (voir 2.1.1.2).

3.3.3.1   EDF préemptif

Pour un ensemble de tâches périodiques tel que " i, Di = Ti, la condition nécessaire et suffisante de faisabilité [LL73] est :
U =
N
å
i=1
Ci
Ti
£ 1

Cette condition reste nécessaire et suffisante dans le cas où " i, Di ³ Ti [BMR90].

Pour un ensemble de tâches périodiques tel que " i, Di £ Ti, la condition précédente n'est bien sûr plus suffisante puisque Di peut être arbitrairement petit, comme le prouve l'exemple de la figure 3.2.
[b].35
  t1 t2
Ti 20 30
Ci 10 11
Di 10 20
Þ U=86.67 < 1

Figure 3.2 : Système de 2 tâches périodiques synchrones non ordonnançable par EDF

Dans ce cas, une condition suffisante de faisabilité analogue existe, qui revient à considérer le système comme étant constitué de tâches sporadiques de délai inter-arrivée Di, et qui s'écrit åi=1N Ci/Di £ 1. Mais cette condition pessimiste n'est pas nécessaire comme le prouve l'exemple de la figure 3.3.
[b].35
  t1 t2
Ti 20 30
Ci 10 10
Di 10 20
Þ
N
å
i=1
Ci
Di
= 1.5 > 1
(U=83.33 < 1)

Figure 3.3 : Système de 2 tâches périodiques synchrones ordonnançable par EDF

Dans [BMR90] et [Spu96], deux conditions nécessaires et suffisantes pour la faisabilité d'un ensemble de tâches périodiques avec Di et Ti arbitraires sont données. Dans [BMR90], il s'agit du déroulement de l'ordonnancement par l'intermédiaire de la demande en capacité processeur (processor demand en anglais) h(t), définie par :
tÎ R+, h(t) =
N
å
i=1
Ci . max[0, ë
t - Di
Ti
û + 1] =
 
å
Di £ t
Ci . (ë
t - Di
Ti
û + 1)
La condition de faisabilité nécessaire et suffisante pour le système de tâches est alors :
U £ 1
 
Ù
" tÎ R+, h(t) £ t
Vérifier cette condition pour toutes les valeurs de t est infaisable en pratique. Dans [BMR90] puis [GRS96], on indique comment restreindre correctement le domaine de variation de t (une fraction discrète de l'hyperpériode), mais la complexité reste élevée (bien que la taille du domaine de variation de t soit pseudo-polynomiale dans la majorité des cas).
Dans [Spu96], il s'agit du calcul du temps de réponse pire cas rti pour chacune des tâches, reposant sur le calcul de l'interférence qu'une tâche peut subir suite à l'activation de tâches plus urgentes (on parle de busy period). Une fois ce temps déterminé, il suffit de vérifier que " i, rti £ Di. La complexité de ce calcul reste élevée.

En pratique, dans le cas général (Ti et Di arbitraires) on utilise souvent la condition suffisante (i.e. pessimiste) plus simple suivante :
N
å
i=1
Ci
min(Di,Ti)
£ 1

3.3.3.2   EDF non préemptif

Considérons d'abord le cas non oisif. La condition nécessaire et suffisante de faisabilité pour un ensemble de tâches concrètes apériodiques correspond à dérouler l'ordonnancement. Dans le cas de tâches apériodiques non-concrètes, une condition nécessaire et suffisante en O(N2) est donnée dans [GMR95].

Dans le cas de tâches sporadiques ou périodiques non-concrètes, une condition nécessaire et suffisante pseudo-polynomiale est donnée dans [JSM91] et repose sur la demande en ressource processeur.

Dans le cas de tâches périodiques concrètes, la même condition devient suffisante seulement, et le problème qui consiste à déterminer l'ordonnançabilité du système est NP-complet [GMR95, JSM91] (des conditions de faisabilité dans le cas synchrone et non synchrone sont données dans [GMR95]).

Puisque l'ordonnancement non oisif peut être vu comme un cas particulier d'ordonnancement oisif, toutes ces conditions de faisabilité restent valables dans le cas oisif, mais ne sont plus que suffisantes seulement. Dans le cas oisif (NP-complet en général), [GMR95] montre qu'à partir d'un ordonnancement oisif faisable, on peut dériver un ordonnancement par EDF oisif ; il en est déduit un algorithme de type branch and bound pour la détermination d'un ordonnancement EDF oisif (complexité exponentielle).

3.3.3.3   Ordonnancement préemptif à priorité statique

Dans ce paragraphe et le suivant, les tâches ti sont classées par ordre de priorité pi décroissantes : i<j Þ pi³pj (pi = 0 étant la plus faible priorité possible) ; dans le cas d'une affectation des priorités suivant RM ou DM, pi = 1/min(Di,Ti). Dans toute la suite, on ne considère que les ordonnancement à priorité fixe non oisifs.

Une première condition de faisabilité nécessaire simple est U £ 1 (puisque EDF est optimal parmi tous les ordonnancements non oisifs).

Dans [LL73], la condition suffisante suivante sur la faisabilité d'un ensemble de tâches périodiques synchrones est montrée, qui suppose l'affectation des priorités suivant RM ou DM :
h
N
å
i=1
Ci
min(Di,Ti)
£ N.(21/N - 1)
Cette condition suffisante est adaptée dans [SLL93] pour le cas où " i, Di ³ Ti par modification de l'algorithme RM à 2 séries de priorités, et s'écrit U £ 1 dans le cas particulier de tâches harmoniques (la condition devient alors nécessaire et suffisante).

Dans [LL73], il est également montré la propriété fondamentale selon laquelle la pire configuration de tâches périodiques non-concrètes (i.e. les pires temps de réponse) est obtenue pour le premier travail des tâches lorsque toutes les tâches sont activées au même instant (instant critique, correspondant à un ensemble de tâches synchrones). Il en découle que la condition 3.3 reste une condition de faisabilité suffisante pour des ensembles de tâches périodiques non-concrètes ou sporadiques.

Une première condition pseudo-polynomiale nécessaire et suffisante pour l'ordonnançabilité de tâches périodiques non-concrètes ou sporadiques est donnée dans [LSD89]. Cette condition, appelée TDA (pour Time Demand Analysis), fait intervenir une formulation de la demande en ressource processeur pour chaque tâche, est valable pour le cas simple " i, Di £ Ti avec affectation des priorités quelconque, et s'écrit :
" i Î [1 ··· N],
 
min
0 < t £ Di
(
i
å
j=1
Cj
t
.é
t
Tj
ù) £ 1
De par la variation ``par palier'' de la demande en ressource processeur (au gré des activations), on peut remarquer qu'il suffit d'évaluer l'équation 3.4 en un nombre fini de valeurs pour le paramètre t (en l'occurrence l'ensemble Si = { kTj | j £ i, k=1 ··· ë Ti/Tj û }).

Une condition nécessaire et suffisante équivalente, mais plus utilisée, pour la faisabilité de tâches périodiques non concrètes ou sporadiques est donnée dans [JP86, Tin92a, Bur94]. Elle repose sur le calcul du temps de réponse pire cas rti des tâches, s'intitule RTA (pour Response Time Analysis), et s'écrit " i, rti £ Di. Le calcul de rti ne suppose pas d'affectation des priorités particulières, et peut se calculer sans hypothèse sur la relation entre les Ti et les Di.

Dans le cas où " i, Di £ Ti [JP86], rti se calcule en prenant en compte les interférences venant des tâches de priorité supérieure : c'est un calcul itératif qui vise à élargir un intervalle de temps jusqu'à ce que celui-ci contienne à la fois le temps d'exécution de ti, et les interférences par les tâches de priorité supérieure (i.e. pour une fenêtre de taille w, cette interférence s'écrit åj<iCj.éw/Tjù). Lorsque U£1 et " i, Di £ Ti, rti est ainsi le point fixe de la suite5 :
rti(0) = Ci
" k ³ 1, rti(k) =
Ci +
 
å
j<i
Cj.é
rti(k-1)
Tj
ù
    (3.1)

Dans le cas général [Tin92a, Bur94] (tâches périodiques non concrètes où sporadiques, Di et Ti non reliés), il faut en plus prendre en compte les interférences de ti avec elle-même quand Di > Ti (i.e. dans ce cas, plusieurs travaux de ti peuvent être prêts à s'exécuter en même temps).

Lorsque les tâches périodiques sont concrètes, ces conditions d'ordonnançabilité deviennent suffisantes seulement. En effet, lorsque les dates d'activation des premiers travaux des tâches font que les tâches ne sont jamais activées simultanément, le temps de réponse pire cas qui se manifeste effectivement peut être strictement plus petit que celui calculé dans les formules ci-dessus, qui considèrent le pire temps de réponse toutes configurations confondues. Dans [Aud91], en plus de définir l'affectation optimale des priorités, on présente à la fois un test qui permet de savoir si l'ensemble des tâches concrètes peut ou non être synchrone à un moment donné (auquel cas les conditions précédentes sont nécessaires et suffisantes), et le test de faisabilité de l'ensemble de tâches qui tient compte des dates de démarrage des premiers travaux.

3.3.3.4   Ordonnancement non préemptif à priorité statique

Dans le cas général (Di et Ti non reliés) de tâches périodiques non concrètes ou sporadiques, [GRS96] donne une condition nécessaire et suffisante d'ordonnançabilité d'un ensemble de tâches, analogue à RTA. Il y est également montré que l'affectation des priorités suivant RM ou DM n'est plus optimale dans le cas non-préemptif (sauf si " i, Di £ Ti et " i ¹ j, Di < Dj Þ Ci £ Cj), mais que l'affectation optimale pour le cas préemptif donnée dans [Aud91] reste optimale dans le cas non préemptif non oisif.

3.3.3.5   Autres ordonnancements à priorité statique

Les travaux [WS02, WS99a, GP96] proposent un modèle de tâches à priorité statique intermédiaire entre le préemptif et le non préemptif qui permet d'allier l'intérêt des deux méthodes. Il s'agit d'associser à chaque tâche deux priorités : la priorité de la tâche tant qu'elle n'a pas commencé son exécution (le seuil de préemption ou preemption threshold en anglais), et la priorité pi quand elle a commencé son exécution. Les cas préemptif et non préemptif sont des cas particuliers avec un seuil de préemption respectivement de pi et 0. Ces travaux proposent à la fois un test de faisabilité, et un algorithme d'affectation optimal polynomial des seuils de préemption.

3.3.4   Limitations

Les conditions de faisabilité qui ont été formulées ci-dessus supposent un modèle de système monoprocesseur idéal assez restrictif. En particulier : Dans les paragraphes qui suivent, nous présentons les différentes extensions qui ont été apportés aux ordonnancements à priorité que nous venons de décrire, et qui visent à supprimer tout ou partie de ces limitations.

3.3.5   Extensions

3.3.5.1   Extensions du modèle de tâches

Gigue d'activation
En pratique, entre la date où une tâche périodique doit être théoriquement activée, et la date réelle à laquelle la tâche est mise dans la file des tâches prêtes à être exécutées, il peut y avoir un délai variable dû par exemple à la résolution de l'horloge système (en particulier pour un mode de fonctionnement de type tick scheduling, dans lequel les tâches ne peuvent démarrer que lors des ticks d'horloge), aux surcoûts induits par les décisions d'ordonnancement, ou au temps de génération d'un message nécessaire avant le commencement de la tâche. Les conditions de faisabilité données ci-dessus ne sont alors plus suffisantes.

Des extensions à ces conditions existent pour prendre en compte une telle gigue. Le principe est de ramener la gigue à un temps de blocage (voir 3.3.6). Ainsi, pour l'ordonnancement préemptif à priorité fixe, RTA est étendu pour supporter la gigue [ABR+93, Tin92a, Bur94]. Le même type d'extension existe pour les ordonnancements à priorité dynamique [Spu96].

Contraintes de précédence
En ce qui concerne l'ordonnancement préemptif à priorité dynamique, [Law73] propose un algorithme qui minimise le retard maximal tout en prenant les contraintes de précédences en compte (Latest Deadline First). Le principe est de laisser en attente une tâche prête à être exécuter tant que sa/ses précédences n'a/n'ont pas été validée(s). Pour l'ordonnancement suivant EDF, la prise en compte des contraintes de précédence peut se faire par modification des échéances relatives [HMT90, SS93, Jef92]. L'ordonnancement résultant est alors optimal vis à vis des ordonnancements préemptifs non oisifs qui prennent en compte les précédences [HMT90].

Une anomalie est remarquable quand l'ordonnancement est à priorité fixe : suivant l'affectation des priorités, la terminaison en avance d'une tâche peut rendre non ordonnançable un système qui était ordonnançable lorsque les temps d'exécution étaient tous considérés toujours égaux au temps pire-cas. La figure 3.5 propose une illustration.
[Temps d'exécution égal au WCET]
[t1 termine en avance]
[b].32
  t1 t2 t3 t4
Ci 5 2 1 5
Di = Ti 18 6 18 18
pi 1 2 0 3

 
 

Figure 3.5 : Contrainte de précédence t3 t4 et dates de terminaison

On peut également remarquer que l'ajout de contraintes de précédence peut rendre ordonnançable un système qui ne l'était pas. La figure 3.6 propose une illustration.
[Sans précédence : infaisable en priorité statique (ici affectation DM)]
[Prise en compte de la précédence t1 t3 (ici affectation p1=0, p2=1, p3=2)]
[b].32
  t1 t2 t3
Ci 1 2 1
Di 4 3 4
Ti 6 3 6

 
 

Figure 3.6 : Contraintes de précédence et ordonnançabilité

Des travaux [Tin94, Tin92b, Tin93, ATB93] se sont attachés à étendre les conditions de faisabilité RTA de manière à intégrer des contraintes de précédence (sous la forme d'un délai minimal incompressible entre l'activation d'une tâche et celles de ses successeurs : notion de transaction) avec prise en compte des terminaisons en avance sous la forme d'une gigue d'activation en aval des précédences. D'autres études s'intéressent à des chaînes de tâches (i.e. 0 ou 1 tâche précède 0 ou 1 tâche) et vérifient le respect des contraintes temporelles parmi tous les entrelacements des chaînes possibles (ou sur un sur-ensemble plus simple) [SNF98] et en tenant compte des variations des temps d'exécution [RRGC02, SGL97].

Modèles de tâches plus riches
Certains travaux s'intéressent à des modèles de tâches plus complexes avec les ordonnanceurs à priorité statique et dynamiques simples. Comme par exemple :

3.3.5.2   Prise en compte des coûts système et matériels

Prendre en compte les interruptions matérielles peut se faire en les modélisant sous la forme de tâches de haute priorité. Prendre en compte les changements de contexte (préemptions) peut se faire en rajoutant le coût du changement de contexte (dont l'estimation non pessimiste est un domaine de recherche actif) soit au temps pire-cas de chaque tâche, soit au temps pire-cas des tâches qui peuvent être préemptées (ce qui est possible avec les algorithmes à priorité fixe, mais pas avec ceux à priorité dynamique).

En ce qui concerne l'ordonnancement à priorité dynamique (préemptif et non-préemptif), les travaux de [JS93, Jef92] et [SP97, Spu96] intègrent le surcoût des interruptions matérielles indépendantes des tâches du système, dans la condition 3.2 fondée sur la demande en ressource processeur.

En ce qui concerne l'ordonnancement à priorité fixe, les travaux de [JS93] et [SNF98] indiquent comment intégrer le surcoût des interruptions matérielles dans TDA et RTA respectivement. Le document [KAS93] détaille comment intégrer différents surcoûts fixes pire-cas (tels que le coût des préemptions, de l'ordonnanceur) dans TDA en tick scheduling (aisément transposable à RTA). Les travaux [Tin93, BWH93] précisent comment intégrer les surcoûts liés à l'interruption d'horloge pour du tick scheduling, en tenant compte de la durée d'exécution variable de l'ordonnanceur, qui est fonction du nombre de tâches à activer à chaque interruption.

3.3.5.3   Extensions du modèle de système : fonctionnement par phases

Pour certains systèmes, les tâches n'ont pas toutes besoin d'être prises en compte à tout moment. C'est le cas lorsque le système fonctionne par phase : un avion par exemple aura besoin de certaines fonctionnalités pendant le décollage, d'autres pendant la croisière, et d'autres encore à l'atterrissage. Des travaux se sont penchés sur l'intégration de tels modèles de système pour l'ordonnancement en plan statique [Foh94, KNH+97] (recours à un plan intermédiaire de transition immédiat ou différé) et à priorité statique [TBW92b] (extension de RTA) par exemple.

Le fonctionnement par phase pose le problème de la cohérence d'état global du système lors des transitions, dont la résolution est une approche propre à chaque application.

3.3.6   Prise en compte des ressources

L'intégration des contraintes de ressources avec les ordonnancements classiques que nous venons de présenter soulève un certain nombre de problèmes, qui sont résolus à l'aide de protocoles d'accès aux ressources.

3.3.6.1   Problématique

Comme dans les systèmes informatiques non temps-réel, le principe est d'isoler l'accès à une ou plusieurs ressources sous la forme de sections critiques, c'est à dire de portions de code à l'intérieur des tâches.

En temps-réel, ceci s'accompagne de problèmes dus au temps de blocage inévitable qu'une tâche doit subir dès qu'elle demande une ressource possédée par une tâche de priorité inférieure.

Anomalie d'ordonnancement
Sans précaution particulière sur l'ordonnancement en dehors du fait que les contraintes de ressource sont prises en compte, la terminaison plus tôt d'une tâche peut rendre infaisable un ordonnancement qui l'était lorsque les temps pire-cas étaient considérés. Il s'agit d'une anomalie similaire à celle présentée en 3.3.4 et illustrée dans la figure 3.7 (une seule ressource en accès exclusif, les traits épais marquent la requête/la libération de la ressource, les zones hachurées marquent la possession de la ressource).
[Ordonnancement faisable]
[Violation d'échéance si la section critique de t3 est plus courte]


Figure 3.7 : Anomalie d'ordonnancement en présence d'une ressource

Inversion de priorité
Le jeu des conflits liés aux ressources peut entraîner qu'une tâche t1 soit mise en attente d'une ressource possédée par une tâche de priorité inférieure t3. Mais cette tâche de faible priorité peut être préemptée par une tâche t2 de priorité intermédiaire entre celles de t1 et de t3, et qui n'est pas en conflit ni avec t1, ni avec t3 pour la ressource. Il en découle que t1 a en fait été préemptée par une tâche t2 de priorité inférieure et qui n'est pourtant pas en conflit avec elle. Si ce phénomène d'inversion de priorité n'a pas été pris en compte au moment de la conception, des dépassements d'échéance sont possibles, comme cela a été le cas pour le célèbre dysfonctionnement de la mission Mars Pathfinder [5].

Comme nous le voyons par la suite, des protocoles de prise de ressource existent pour empêcher les inversions de priorité.

Interblocage
Ce problème n'est pas particulier aux systèmes temps-réel et apparaît lorsque plusieurs ressources sont présentes dans le système. Pour le cas simple à deux tâches t1 et t2 avec deux ressources en accès exclusif R1 et R2, il apparaît lorsque t1 possède R1 et t2 possède R2 et que t1 et t2 ont à leur tour besoin de R2 et R1 respectivement. Ce type de configuration (une boucle) entraîne le blocage permanent de t1 et t2 ainsi que la non disponibilté permanente de R1 et R2. Ce problème est généralisable sur des boucles de blocage à davantage de tâches et de ressources.

Une solution simple pour empêcher ce problème d'apparaître est d'imposer un ordre d'acquisition des ressources arbitraire lors de la phase de conception. Nous verrons que certains protocoles d'accès aux ressources permettent d'éviter ce problème par d'autres voies.

3.3.6.2   Démarche

Le problème qui se pose en temps-réel en présence d'accès concurrents à des ressources, est l'intégration, dans les algorithmes d'ordonnancement à priorité classiques, d'une borne supérieure sur le temps de blocage d'une tâche par les tâches de priorités inférieures. Les protocoles d'accès aux ressources ont pour rôle de réaliser cette intégration, en rendant les temps de blocage effectivement bornés, et si possible avec une borne réduite.

Une fois la borne Bi sur le temps de blocage que peut subir un travail de ti déterminée, l'intégration dans les conditions de faisabilité permet de valider le comportement temporel correct du système, y compris en présence de terminaisons de tâches en avance, et s'écrit : Ces tests sont tous suffisants seulement (les tâches peuvent ne subir aucun blocage en réalité), et sont plus ou moins pessimistes.

3.3.6.3   Protocoles d'accès aux ressources

Une première source de blocage qui pose des problèmes sur la détermination des bornes de blocage, correspond à l'inversion de priorité. Si on n'utilisait pas de protocole d'accès aux ressources, alors les temps de blocage seraient considérablement longs (de l'ordre de Bi = åi<k£ N Ck en priorité statique par exemple).

La méthode la plus simple pour résoudre ce problème est d'interdire toute préemption tant qu'une tâche possède une ressource. Les temps de blocage sont ainsi parfaitement déterminés (le maximum des durées de toutes les sections critiques de toutes les tâches de priorité inférieure), mais trop pessimistes (toutes les tâches sont prises en compte, y compris les tâches qui ne rentrent pas en conflit de ressource avec la tâche ti considérée).

En ordonnancement à priorité statique, un autre protocole simple est le protocole à héritage de priorité (PIP pour Priority Inheritance Protocol) [SRL90], qui vise par construction à interdire l'inversion de priorité : quand une tâche de priorité L bloque un travail d'une tâche H de priorité supérieure, elle hérite de la priorité H jusqu'à ce qu'elle relâche les ressources pour lesquelles H est bloquée. Ce protocole exhibe des temps de blocage plus petits, mais ne gère pas les interblocages, et peut entraîner des surcoûts à cause des blocages répétés (blocages en chaîne) et des préemptions associées à chaque fois qu'une tâche H est bloquée par une tâche L.

Les mêmes travaux [SRL90] présentent un protocole qui résout ces deux limitations : le protocole à seuil de priorité ou PCP pour Priority Ceiling Protocol. Le principe est d'associer à chaque ressource un seuil de priorité égal à la plus grande priorité parmi toutes les tâches qui peuvent la demander. Lorsqu'une tâche demande une ressource, elle n'est autorisée à la prendre que si sa priorité est supérieure aux seuil de priorité de toutes les ressources acquises par d'autres tâches. Si la tâche demandeuse bloque, elle transmet sa priorité (héritage) à la tâche qui possède la ressource demandée. PCP a l'avantage d'empêcher tout interblocage et de limiter le nombre de blocages (1 blocage maximum par travail). Mais ceci se fait au prix d'un effort d'implantation et de conception plus grand : l'algorithme est relativement délicat à implanter, et la définition des seuils de priorité des ressources implique qu'on est capable de préciser hors ligne quelle tâche a besoin de quelle(s) ressource(s).

Afin d'éviter toute préemption due à des blocages, les travaux [Bak91] proposent le protocole à priorité de pile (SRP, pour Stack Resource Policy). Avec ce protocole, la tâche n'est pas autorisée à démarrer tant que toutes les ressources qui lui sont nécessaires ne sont pas disponibles, ce qui a pour effet d'éviter tout blocage une fois que la tâche a démarré (sans toutefois supprimer l'éventuel blocage avant le démarrage). Le protocole repose sur la notion de niveau de préemption fixé hors-ligne et indépendant du type d'ordonnancement à priorité (statique ou dynamique). Le protocole maintient pour l'ensemble du système le seuil de priorité P courant, et une tâche n'est autorisée à démarrer que si sa priorité est supérieure à la priorité de la tâche courante, et si son niveau de préemption est supérieur au seuil de priorité P du système. À chaque fois que la tâche acquiert une ressource, le seuil de priorité du système P est affecté à la valeur du plus haut niveau de préemption parmi toutes les tâches susceptibles d'acquerir la ressource. Avec SRP, le temps de blocage et les contraintes de conception sont identiques à ceux de PCP, mais le nombre de préemptions pour cause de blocage est nul : il est alors inutile de se soucier de l'accès concurrent aux ressources. De plus, il est possible de considérer des ressources non binaires (telles que des sémaphores, ou des piles).

Ces travaux peuvent également être intégrés dans un système avec ordonnancement à priorité dynamique [Spu96, SS93, Bak91]. Les travaux de Jeffay [Jef92, Jef89] proposent une autre technique, dite par phases, pour l'ordonnancement en priorité dynamique. Chaque phase correspond soit à une portion sans acquisition de ressource, soit à une section critique différente. Le principe est de modifier dynamiquement les échéances des tâches à chaque changement de phase, de manière à reproduire un comportement similaire à SRP : on parle de EDF/DDM (pour Dynamic Deadline Modification). L'auteur fournit une condition suffisante d'ordonnançabilité du système résultant.

3.3.6.4   Modes d'accès aux ressources optimistes

Plutôt que d'avoir recours à l'acquisition d'une ressource afin de modifier une structure de données (telle qu'une file par exemple), il peut être intéressant (quand c'est possible) d'utiliser des primitives qui effectuent une série d'opérations de façon optimiste (i.e. en ne supposant aucun conflit), et qui est répétée si il y a eu des conflits jusqu'à validation des opérations. L'avantage de cette méthode est que pour une série d'opérations relativement courte, les surcoûts système sont réduits. Le problème est qu'en temps-réel il est important de savoir borner le nombre de fois où les opérations de mise à jour sont répétées.

On distingue couramment 2 approches pour ce type de mécanisme optimiste [ARJ95] :
Algorithmes sans attente
(wait-free en anglais). Les tâches qui ont validé leurs modifications aident celles qui sont en train d'essayer de valider les leurs, mais qui n'y ont pas encore réussi. Ce mécanisme peut être vu comme une forme d'inversion de priorité, et induit des coûts d'exécution qui peuvent être importants (copie de données en zone de transit).
Algorithmes sans blocage
(lock-free en anglais). Une tâche donnée recommence d'elle-même la série d'opérations de modifications tant qu'elles n'ont pas été validées.
Les travaux [ARJ95] étendent les conditions de faisabilité pour RM et EDF pour les algorithmes sans blocage : le principe est de déterminer une borne supérieure sur le nombre de fois où les opérations de modification seront répétées.

3.3.7   Choix d'ingénierie

Par rapport à l'ordonnancement statique (voir 3.2.3.1), l'ordonnancement à priorité reste une solution simple à implanter, plus souple lorsque des modifications sont introduites, et est moins gourmande en mémoire. En contrepartie, plus il y a de contraintes (ressources, précédences par exemple), moins le processeur peut être effectivement utilisé, et dans certains cas, aucun ordonnancement en-ligne ne peut exister.

Au sein de la famille des ordonnancements en-ligne à priorité, le concepteur doit choisir entre priorité statique et dynamique. Le choix est d'autant plus difficile que les différentes extensions aux modèles simples issus de [LL73] existent en général pour les deux sous-familles.

Les ordonnancements à priorité statique s'intègrent très bien dans un système d'exploitation sans qu'il y ait besoin de lui faire gérer des contraintes de temps : il suffit que le système dispose d'un ordonnanceur à priorité, ce qui est pour le moins courant. En contrepartie, le seuil d'utilisation qu'il est possible d'atteindre (i.e. la rentabilité du processeur) est moins élevé qu'en priorité dynamique. De ce point de vue, il existe des versions mixtes (ordonnancements à priorité statique et dynamique combinés) qui effacent la frontière entre ordonnancement à priorité statique et dynamique [Zub98], et qui permettent de faire un compromis entre rentabilité du processeur et complexité d'ordonnancement en-ligne.

D'autre part, en priorité dynamique, lorsqu'une échéance est dépassée, elle affecte toutes les autres tâches, quel que soit leur niveau de criticité, ce qui peut amener des dépassements d'échéances en cascade non contrôlés (voir section 3.5). De ce point de vue, les ordonnancements à priorité statique ont l'avantage de mieux isoler ces fautes (les tâches de priorité supérieure à la tâche fautive ne sont pas touchées), mais moins encore que les ordonnancements hors-ligne par plan (une tâche programmée à telle date sera toujours exécutée, où l'ensemble du système sera arrêté, que la tâche précédente ait terminé dans les temps ou non).

3.4   Ordonnancement avec sous-partie dynamique

Un système temps-réel peut être en charge du contrôle d'un procédé par exemple, et en même temps avoir à fournir une palette de services sans contrainte temporelle (affichage d'une interface graphique, exécution des services d'un système d'exploitation généraliste par exemple [Bar97, GAGB01]), ou avec contrainte temporelle mais facultatifs (affichage de statistiques sur le procédé par exemple).

On se place toujours dans le cadre des ordonnancements à priorités, et on considère que le système est désormais constitué d'une sous-partie temps-réel strict garantie hors ligne, comprenant uniquement des tâches sporadiques et/ou périodiques ; et d'une sous-partie constituée de tâches apériodiques (sous-partie dynamique dans la suite). L'objectif est de continuer de garantir la faisabilité des tâches temps-réel strict, tout en obtenant un temps de réponse le plus petit possible pour les tâches apériodiques.

En section 3.4.1, nous étudions le cas où les tâches apériodiques sont sans contrainte temps-réel, puis le cas où de telles contraintes existent (section 3.4.2). Nous terminons en donnant des améliorations aux mécanismes pour profiter de la terminaison plus tôt des tâches temps-réel strict (section 3.4.3).

3.4.1   Tâches apériodiques sans contrainte de temps-réel

3.4.1.1   Approches par tâches serveurs

La méthode la plus simple pour prendre en compte les tâches apériodiques sans contrainte de temps, est de les ordonnancer lorsqu'aucune tâche périodique/sporadique temps-réel strict n'est prête. Avec cette méthode (ordonnancement en temps libre ou background scheduling en anglais), les conditions de faisabilité et l'algorithme ordonnancement ne sont pas modifiés, mais le temps de réponse des tâches apériodiques qui découle est long.

Afin d'améliorer le temps de réponse des tâches apériodiques dans le contexte d'un ordonnancement à priorités, l'idée est de les faire prendre en charge par une tâche du système qui possède une réelle priorité (statique ou dynamique), sans toutefois remettre en cause l'ordonnancement des tâches périodiques et sporadiques temps-réel strict : on parle de tâches serveur. Même si nous nous intéressons ici aux ordonnancements à priorités, une technique similaire existe pour les ordonnancements à plans [Foh94, IF99].

Priorité statique
En ordonnancement à priorité statique, les premières approches [But97] considèrent une tâche serveur périodique de capacité fixée re-remplie à chaque début de période du serveur, et qui décroît en fonction du temps (méthode à serveur périodique ou polling server en anglais), ou en fonction de l'utilisation par les tâches apériodiques [SLS95] (DS, pour deferrable server). Dans le premier cas, l'introduction du serveur ne modifie pas les conditions de faisabilité (le serveur est une tâche périodique classique, ordonnancé même si il n'a aucune tâche apériodique à exécuter). En contrepartie, les tâches apériodiques ne sont pas prises en compte quand elles arrivent lorsque le serveur a été complètement ordonnancé dans la période courante. Dans le deuxième cas, les tâches apériodiques y gagnent en réactivité puisqu'elles sont prises en compte à tout moment dans la période courante : on parle de serveur avec préservation de la bande passante (bandwidth preserving en anglais). Mais l'introduction du serveur perturbe l'ordonnancement des autres tâches temps-réel (le serveur n'est pas ordonnancé pendant la période courante jusqu'à ce qu'il ait une tâche apériodique à exécuter), ce qui modifie les conditions de faisabilité (l'utilisation maximale garantie, analogue à la condition 3.3, est plus faible).

Une variante de DS, plus simple et dont les conditions de faisabilité sont analogues au cas du polling server, est la méthode serveur sporadique [Spr90] où le serveur est une tâche sporadique dans laquelle la seule contrainte est que les re-remplissages de la capacité du serveur sont séparés par un délai d'inter-arrivée du serveur. En contrepartie, le temps de réponse des tâches apériodiques est plus compliqué à déterminer. D'autres variantes plus complexes existent, comme la méthode à échange de priorité [But97] (priority exchange en anglais), qui visent à accumuler de la capacité d'exécution tant que le serveur n'a pas de tâche apériodique à exécuter. La condition de faisabilité est moins défavorable que DS (l'utilisation maximale garantie est plus élevée), mais les tâches apériodiques ont un temps de réponse plus élevée que DS.

Priorité dynamique
En ordonnancement à priorité dynamique, une première technique est de déclarer une tâche serveur, de capacité et de période (ou délai d'inter-arrivée, définissant l'échéance relative) données. EDF peut être utilisé pour ordonnancer les serveurs. On peut utiliser les méthodes à échange de priorité ou de serveur sporadique indiquées ci-dessus, pour définir le comportement du serveur [But97]. Dans les deux cas, la condition d'ordonnancement revient à considérer le serveur comme une tâche temps-réel quelconque, la réactivité des apériodiques étant d'autant plus faible que la période du serveur est grande.

Il existe d'autres méthodes qui évitent d'avoir à attendre le début de la période suivante avant de pouvoir exécuter la tâche apériodique, de façon à réduire leur temps de réponse. Le principe est de réserver une portion de la capacité du processeur à une tâche serveur (sa capacité), et de modifier en-ligne l'échéance relative du serveur suivant la présence ou l'absence de tâches apériodiques à exécuter, tout en garantissant que les tâches temps-réel ne sont pas perturbées. C'est le fonctionnement des serveurs à bande passante donnée : TBS [SB94, CLB99, LB00a, SBS95] pour Total Bandwidth Server en anglais (pour des requêtes apériodique dont on connaît le temps pire-cas), ou CBS [AB98a, ALB99, JG01, LB01] pour Constant Bandwidth Server en anglais (pour des requêtes apériodiques quelconques) par exemple. La condition de faisabilité revient toujours à considérer le serveur comme une tâche temps-réel quelconque du système.

3.4.1.2   Approches par réquisition de temps creux

Priorité statique
Il existe une méthode très consommatrice en mémoire, qui minimise le temps de réponse de la première tâche apériodique en tête de la file des apériodiques sur le serveur [TLS95] : l'ordonnancement par réquisition de la laxité [LT94] (slack stealing en anglais). Il s'agit de maintenir en mémoire un calendrier (la fonction de laxité), établi hors-ligne, et qui couvre une hyperpériode du système. À chaque instant, le calendrier indique la capacité d'exécution que le serveur des tâches apériodiques est autorisé à prendre au détriment des tâches temps-réel strict, tout en garantissant que les échéances de ces dernières restent respectées. Les travaux [DTB93, Dav93] présentent une version complète mais complexe de cette technique, qui calcule la fonction de laxité en-ligne (pas de calendrier), ainsi que des versions approchées mais moins complexes.

Enfin, il existe une méthode aux performances (réactivité des tâches apériodiques) comparables, dite à double priorité (ou dual priority) [Dav94, GNM99], mais moins coûteuse en mémoire et en temps de calcul tant hors-ligne que en-ligne. Elle consiste à retarder au maximum les tâches temps-réel strict d'un retard calculé hors-ligne par analyse de temps de réponse (le retard de promotion ou promotion time en anglais) si il y a des tâches apériodiques présente. Pour cela, pendant la durée de ce retard de promotion, les tâches temps-réel strict ont une priorité plus faible que les tâches apériodiques qui peuvent être présentes, ce qui assure une bonne réactivité des tâches apériodiques. Afin de continuer de garantir les tâches temps-réel strict, une fois que le retard de promotion d'une tâches temps-réel strict est écoulé, celle-ci retrouve sa priorité nominale, supérieure à la priorité de toutes les tâches apériodiques éventuellement présentes.

Priorité dynamique
Il existe également une technique similaire à l'ordonnancement par réquisition de la laxité pour EDF [TLSH94].

3.4.2   Activations en-ligne de tâches avec contraintes de temps-réel

Lorsque les tâches qui se présentent dynamiquement au cours de la vie du système ont des contraintes temporelles (traitement exceptionnel avec échéance stricte par exemple), il est impossible de garantir l'ordonnançabilité de l'intégralité du système hors-ligne (cela reviendrait à pouvoir prévoir l'avenir). En pratique, le problème se découpe en deux sous-problèmes reliés [MM97] : 1/ l'acceptation de la tâche, 2/ l'ordonnancement proprement dit. La phase d'acceptation a pour rôle de vérifier que si la tâche peut être ordonnancée, alors i) ses propres contraintes temporelles sont respectées en présence des autres tâches déjà présentes, et ii) il est possible d'ordonnancer la tâche sans remettre en cause les contraintes temporelles des autres tâches temps-réel (voir ci-dessous). Cette phase est dépendante de l'ordonnancement. Si ce test d'acceptation échoue, la tâche est refusée.

Tâches périodiques et sporadiques
Si la tâche à accepter est périodique ou sporadique, l'acceptation consiste en la vérification des conditions d'ordonnançabilité données en 3.3.3, ou d'une variante (comme [BS93] pour EDF, ou [McE94, RJMO98] pour l'ordonnancement à priorité statique par exemple).

Tâches apériodiques
Si la tâche à accepter est apériodique, la technique est de soumettre individuellement chaque travail au test d'acceptation, et d'ordonnancer chaque travail suivant une technique telle que celles décrites en 3.4.1. Le test d'acceptation repose sur le calcul du temps de réponse de la tâche apériodique en fonction de toutes les autres tâches déjà présentes dans le système (dépend de l'algorithme d'ordonnancement), et consiste en la vérification que ce temps de réponse est compatible avec les contraintes temporelles. Une partie de ces travaux [CLB99, LB00a, DTB93] s'intéressent en plus à la prise en compte du partage de ressources entre les tâches temps-réel strict, et celles dynamiquement activées.

3.4.3   Récupération de ressources pour favoriser l'ordonnancement de tâches activées dynamiquement

Lorsque l'ordonnancement de tâches temps-réel activées dynamiquement dépend d'un test d'acceptation, il est important de pouvoir compter sur le maximum de ressources disponibles, en particulier en ce qui concerne les ressources processeur. Ceci suppose d'être capable d'évaluer précisément les ressources disponibles et celles nécessaires : si l'on se limite à ne prendre en compte que les pires comportements des tâches en cours (temps d'exécution pire cas, fréquence d'activation maximale pour les tâches sporadiques), alors des tâches temps-réel dynamiquement activées risquent d'être refusées à tort. La récupération de ressources est un mécanisme complémentaire à l'acceptation dynamique en-ligne vu précédemment, qui permet de profiter des ressources réservées pour d'autres tâches, mais qui sont finalement non utilisées (par exemple : abandon de la tâche de sauvegarde quand la tâche primaire d'un couple primaire/sauvegarde termine correctement), afin de limiter le pessimisme introduit par la réservation de ressource processeur qui avait été faite sur la base d'un comportement pire-cas.

Il existe des méthodes qui réactualisent les ressources disponibles à la fin de chaque tâche, pour récupérer celles réservées mais non utilisées [SBS95, LB00a, Dav93]. Il existe d'autres méthodes plus précises, qui mesurent l'accélération par rapport au temps d'exécution pire cas, au cours de l'exécution de la tâche [HS90, MZ93, DTB93, GAGB01] : il s'agit de découper la tâche en sections (milestones en anglais), dont on connaît le temps pire cas, et encadrées par l'émission de signaux de repérage envoyés au système d'exploitation par exemple.

Ces techniques sont en général accompagnées d'un mécanisme de repêchage des tâches refusées (ou second chance en anglais) : lorsque la récupération des ressources libère suffisamment de ressources, il peut être possible d'ordonnancer une tache dynamiquement activées qui avait été précédemment refusée et mise dans la file de repêchage (reject queue en anglais).

3.4.4   Problèmes reliés

La contention sur la ressource processeur parmi les tâches temps-réel qui arrivent dynamiquement, pose le problème de l'arbitrage entre les tâches à accepter, refuser, ou abandonner lorsque le système entre en situation de surcharge (ressource processeur insuffisante). Nous verrons en 3.5 quels sont les problèmes soulevés, et comment ils peuvent être traités.

3.5   Gestion de la surcharge

Lorsque les ressources nécessaires pour exécuter les tâches du système sont plus importantes que les ressources disponibles (en particulier les ressources processeur), le système entre en phase de surcharge. Le phénomène de surcharge peut être lié à un fonctionnement anormal du système, résultat d'un comportement non prévu de l'environnement (activation de tâches sporadiques sans respect du délai minimal d'inter-arrivée par exemple), ou du système (temps d'exécution réels supérieurs aux temps pire-cas spécifiés, surcoûts du système d'exploitation ou du matériel sous-estimés ou mésestimés). Le phénomène peut aussi être le résultat d'une décision de réalisation, comme la prise en compte de tâches temps-réel apériodiques par exemple, ou la volonté de considérer des temps d'exécution moyens plutôt que des temps pire-cas dans l'ordonnancement (afin de limiter le surdimensionnement du système, quand par exemple le comportement au pire-cas n'est pas raisonnable, comme pour un mécanisme d'allocation mémoire par exemple).

Si aucune précaution n'est prise, la conséquence d'une surcharge est que certaines tâches ne respectent pas leur échéance, et le système peut s'écrouler : les tâches qui manquent leur échéance retardent les autres qui à leur tour manquent leur échéance. C'est l'effet domino [SSDB94] particulièrement sensible avec un ordonnancement de type EDF, puisque celui-ci fonde ses décisions d'ordonnancement sur la proximité de l'échéance de la tâche, donnant ainsi plus grande priorité à la tâche qui est en train de manquer son échéance.

En amont de la surcharge, il est possible d'éliminer une partie des risques. Par exemple, il est possible de filtrer les événements générés par l'environnement, pour ne pas qu'ils dépassent une certaine fréquence d'apparition [Sta94]. Mais cette approche n'est pas forcément compatible avec le système considéré.

En présence de surcharge, la solution pour contrôler le comportement du système est de borner ou de diminuer les besoins en ressources. Cela suppose : En aval, une fois la surcharge détectée ou anticipée, il y a plusieurs méthodes pour diminuer le besoin en ressource processeur : soit certaines tâches sont volontairement abandonnées, i.e. terminées d'autorité (décisions microscopiques) ; soit la structure globale du système est modifiée, i.e. le système est reconfiguré (décisions macroscopiques). Nous nous intéressons maintenant à ces deux voies d'étude (sections 3.5.1 et 3.5.2 respectivement) dans le cas d'ordonnanceurs pour le temps-réel strict. En section 3.5.3, nous indiquons des modèles de systèmes qui tolèrent des dépassements d'hypothèses dans certaines limites.

3.5.1   Ordonnancement sans reconfiguration

En général, on découpe le système en deux sous-parties : la sous-partie critique définie et garantie hors-ligne, et la sous-partie non critique. La sous-partie critique n'est jamais remise en cause, seule la sous-partie non critique présente les problèmes de surcharge. Nous nous concentrons ici sur cette sous-partie non critique.

On distingue habituellement plusieurs classes d'ordonnanceurs de cette catégorie : les ordonnanceurs au mieux (best effort en anglais) sans test d'acceptation dans lesquels les tâches sont ordonnancées jusqu'à leur terminaison ou jusqu'à dépassement d'échéance ; les ordonnanceurs avec test d'acceptation et sans remise en cause des tâches acceptées (dits aussi à garantie) ; les ordonnanceurs avec exécution conditionnelle (test à l'activation ou avant démarrage) et politique de rejet, i.e. abandon (dits aussi robustes).

3.5.1.1   Notion de valeur

Que ce soit pour évaluer la qualité d'un ordonnanceur en présence de surcharge, pour donner des garanties numériques sur le comportement du système (tous ordonnanceurs), ou pour arbitrer entre les tâches à accepter (ordonnanceurs à garantie) ou abandonner (ordonnanceurs robustes), il est nécessaire d'introduire les notions d'importance des tâches représentées numériquement par des fonctions de valeur, et de valeur globale dégagée par le système, qui définit la qualité du service effectivement fourni par le système.

Les fonctions de valeur associées aux tâches peuvent être par exemple constantes, ou fonction du temps d'exécution, ou fonction de la date courante relativement à la date de démarrage, ou fonction de la décision qui doit être prise (acceptation, refus ou abandon ; comme dans [MB97, Del96]). La valeur globale dégagée par le système peut à son tour être la somme des valeurs dégagées par chacune des tâches, ou une fonction plus complexe [BPB+00].

Nous ne considérons pas ici le problème décisionnel lié la définition des fonctions de valeur, qui peut lui-même être un problème complexe [BPB+00].

3.5.1.2   Limites théoriques

Les travaux de Sanjoy Baruah montrent que pour des fonctions de valeur simples, il existe une limite sur la valeur globale maximale garantie qu'on peut atteindre avec un algorithme en-ligne, par rapport à ce qu'il est possible d'obtenir avec un algorithme d'ordonnancement optimal qui disposerait de toutes les informations sur les activations de tâches à venir, dit ordonnanceur clairvoyant (comme par exemple [AB98b]). Le quotient entre les deux valeurs est le facteur de compétitivité.

Dans le cas simple où la fonction de valeur pour une tâche est : 1 quand la tâche termine dans les temps, et 0 si elle dépasse son échéance où si elle est refusée ou abandonnée, les travaux [BHS01] montrent que dans le cas général, par rapport à un algorithme clairvoyant, les algorithmes d'ordonnancement en-ligne peuvent dégager une valeur (appelée dans ce cas le taux de réussite ou completion count ou hit ratio) arbitrairement plus petite (i.e. le facteur de compétitivité vaut 0).

Des travaux analogues [BKM+91], mais qui s'intéressent à la fonction de valeur qui vaut le temps d'exécution effectif en cas de terminaison correcte, ou 0 sinon (dépassement d'échéance, refus ou abandon), montrent que, par rapport à un algorithme clairvoyant, la valeur dégagée (appelée dans ce cas l'utilisation!effective du processeur ou EPU) maximale garantie par un algorithme en-ligne ne peut pas être plus du quart de la valeur dégagée par un algorithme clairvoyant : le facteur de compétitivité est 1/4, ce facteur étant d'autant plus élevé que la surcharge est faible (0.4 quand la charge tend vers 1+, et bien sûr 1 quand la charge est inférieure à 1). Ces travaux traitent également du cas plus général où la valeur dégagée par l'exécution correcte d'une tâche est fonction du temps d'exécution pondéré par un facteur d'importance de la tâche.

Les travaux [BH97] étendent cette étude en s'intéressant à l'évolution du facteur de compétitivité en fonction de du quotient echeance/WCET (qui figure la laxité) minimal parmi toutes les tâches du système : comme on s'y attend, le facteur de compétitivité est d'autant plus élevé (tend vers 1) que ce ratio est élevé.

3.5.1.3   Ordonnanceurs au mieux

Avec ces ordonnanceurs, une tâche est ordonnancée jusqu'à son terme, ou jusqu'à dépassement de son échéance, de manière à borner le besoin en ressources processeur. Cette stratégie peut être associée à un ordonnancement à priorités classique, ou à priorités liées à une fonction de valeur.

Dans le paragraphe précédent, il était question de garanties strictes sur la valeur qu'il est possible d'obtenir. Avec ce type d'ordonnancement, beaucoup de travaux s'intéressent aussi à la valeur moyenne dégagée par le système (par simulation ou analyse probabiliste) avec un ordonnancement donné (par exemple RM, DM et EDF dans [Gar99], RM pour l'approche Statistical Rate Monotonic Scheduling [AB98d, AB98c], ou des ordonnanceurs à priorité dynamique [AB99, BSS95]), étant données plusieurs lois statistiques sur les durées d'exécution et les dates d'activation des tâches, et plusieurs fonctions de valeur.

Ce type de travail est une transposition des conditions de faisabilité classiques au domaine des probabilités : il permet par exemple d'affirmer qu'un système de tâches donné dégagera une valeur moyenne donnée. Ceci permet d'avoir une idée globale sur la qualité du service moyen fourni, mais sans disposer de garantie stricte sur la qualité minimale du service fourni. Ce qui rend ces résultats adaptés en priorité au monde du temps-réel souple.

3.5.1.4   Ordonnanceurs à garantie et ordonnanceurs robustes

En général, les ordonnanceurs à garantie reposent directement sur le test d'acceptation (tels que ceux évoqués en 3.4) : si celui-ci résussit, la tâche est définitivement intégrée dans le système. C'est le fonctionnement de GED (pour Guaranteed Earliest Deadline) [BS93], une variante de EDF avec test d'acceptation. On pourrait cependant imaginer des ordonnanceurs qui refusent une tâche alors que le test d'acceptation réussit, par anticipation de l'activation prochaine d'une tâche (sporadique par exemple) plus importante.

Les ordonnanceurs robustes sont souvent des ordonnanceurs à priorité classiques, avec test d'acceptation, et dans lesquels la politique de rejet n'est activée qu'en cas de refus d'une tâche : quand le test d'acceptation échoue, l'ordonnanceur tente d'abandonner une ou plusieurs tâches de moindre importance. C'est le fonctionnement de RED (pour Robust Earliest Deadline) [BS93], une variante robuste de GED.

D'autres ordonnanceurs robustes ne reposent pas sur un test d'acceptation, mais sur un test de démarrage, comme Dover [KS93] qui est issu de EDF. Dover repose sur une propriété fondamentale de EDF qui lui permet d'identifier la saturation transitoire du processeur (i.e. un risque de surcharge) au démarrage d'une tâche, auquel cas le démarrage est conditionné par un test qui optimise la valeur dégagée à hauteur de la limite théorique donnée dans [BKM+91] et évoquée précédemment.

3.5.2   Ordonnancement avec reconfiguration

Les ordonnanceurs de ce type sont capables de passer d'une configuration du système à une autre. Une configuration peut être un ensemble de tâches défini hors-ligne, ou défini en-ligne : le système est constitué d'une série de services ; un service étant une fonction particulière du système ou un groupement de tâches établi par un algorithme spécialisé [IMR96]. Chaque service peut être rendu avec une plus ou moins grande qualité, ou différentes contraintes en ressources, en précédences, en temps, par des ensembles de tâches différents ayant chacun leur coût d'exécution.

Ce type d'ordonnanceur repose sur deux mécanismes : Ainsi, dans l'approche FERTS par exemple [BSS94, GSSR97], l'application est composée d'entités (i.e. FERTs, ou services), et chaque entité peut correspondre à plusieurs séries (compositions) de modules (i.e. tâches) : les stratégies (i.e. configuration) de chaque entité. Le système ne prend pas les décisions de changement de configuration à l'échelle de la tâche, mais à l'échelle de l'entité. Lorsqu'une entité est activée, en fonction de l'état courant du système, la stratégie la plus adaptée pour l'entité est choisie.

Les travaux [Del96] présentent une approche similaire : la politique d'abandon de tâches en cas de refus d'une tâche est définie par le concepteur sous la forme d'un composant logiciel dédié : le régisseur. Mais en plus, pour les tâches périodiques, plusieurs configurations globales du système (ensemble de tâches), ou phases, sont définies hors-ligne. Le concepteur fournit un automate pour passer d'une configuration à l'autre, et c'est le régisseur qui décide de changer l'état de l'automate (i.e. des tâches à ordonnancer) en fonction de la charge courante. Malheureusement, la notion de phase pose deux problèmes : Des travaux avec le système distribué ordonnancé par plans statiques Maruti [SdSA95] résolvent le problème de la cohérence en établissant à l'avance une série de points où les changements de reconfiguration peuvent se faire. D'autres travaux avec le système distribué ordonnancé par plans statiques MARS [KNH+97] résolvent également ce problème, en reposant pour cela à la fois sur l'existence d'une phase de transition entre 2 modes adjacents (le mode précédent, et le mode destination), et sur le fait que l'ordonnancement est commandé par le temps, afin d'assurer la synchronisation des changements de mode. Cependant, il reste toujours le danger de l'instabilité au changement de phase, que le concepteur doit continuer de traiter.

3.5.3   Extensions au modèle de tâche

Il existe des modèles qui intègrent directement le fait que des tâches puissent être totalement ou en partie abandonnées, et ceci avec garantie en-ligne, ou hors-ligne dès la phase de validation par analyse de faisabilité.

Ainsi, il existe des modèles pour lesquels la spécification doit préciser quels travaux d'une tâche peuvent être supprimés : Il existe des modèles où seule une partie de la tâche est garantie hors-ligne, l'exécution du reste dépendant de la charge du système :

3.6   Extensions du modèle de système

Nous avons présenté les méthodes d'ordonnancement classiques en temps-réel. Il existe cependant d'autres approches qui reposent sur d'autres modèles du système concernant l'ordonnancement. Les deux sections qui suivent abordent deux modèles de systèmes différents : systèmes fondés sur un ordonnancement fluide (section 3.6.1), et systèmes fondés sur une hiérarchie d'ordonnanceurs (section 3.6.2).

3.6.1   Ordonnancement fluide

En matière d'ordonnancement dynamique, dans les paragraphes précédents, le système d'exploitation fait appel aux décisions d'ordonnancement uniquement lorsque la structure du système est modifiée : une tâche est activée, dépasse une contrainte temporelle, demande/relâche une ressource système, ou se termine. Certains problèmes d'ordonnancement sont rendus complexes en partie à cause des périodes incompressibles entre deux décisions d'ordonnancement (par exemple le calcul du temps de réponse), puisqu'il s'agit alors de faire des calculs, des vérifications ou des optimisations non linéaires.

Le modèle d'ordonnancement fluide, par Pfair [SAWJ+96, JG01] (proportional fair), ou PSA [ALB99] (proportional share allocation), s'inspire des techniques de partage de bande passante en réseau ou en multimédia (comme dans le système Nemesis [oCCL00] par exemple, qui procède par réservation), et a pour but de se rapprocher le plus possible d'un système linéaire, dans lequel le rythme de progression des tâches serait régulier. Ce modèle revient à considérer qu'à tout moment les tâches ont une portion donnée et connue du processeur qui leur est réservée (i.e. un processeur virtuel de moindre capacité donnée connue) : la fraction de la bande passante de traitement du processeur. Et une fois que le rythme de progression est connu, il est possible d'assurer que les contraintes temporelles sont respectées.

Le modèle fluide parfait imposerait qu'à tout instant le processeur exécute une partie de chaque tâche, proportionnelle à la bande passante du processeur qui lui est allouée. Ce principe théorique n'est pas applicable : en pratique, l'ordonnanceur est appelé régulièrement, toutes les q unités de temps (le quantum d'ordonnancement). Cependant, en contrepartie à la discrétisation introduite par les quanta de q unités de temps, le rythme de progression défini par l'ordonnanceur n'est pas exactement constant, mais borné de façon sûre et connue par l'ecart temporel@écart temporel (time lag en anglais), qui correspond à l'écart maximal entre les progressions obtenues par exécution réelle et suivant le modèle théorique fluide parfait.

Dans les méthodes les plus simples répondant à ces contraintes, le concepteur associe un poids absolu wi à chaque tâche, et l'ordonnanceur garantit que la tâche aura une fraction wi/åjwj de la bande passante du processeur qui lui est allouée. Il existe par exemple une adaptation de EDF, dite EEVDF (pour Elligible Earliest Virtual Deadline First), qui borne l'écart temporel à q unités de temps, en travaillant dans une échelle de temps virtuelle : dans cette échelle de temps, 1 unité de temps correspond à l'exécution de toutes les tâches de sorte que celles-ci progressent individuellement de wi unités de traitement processeur. Cet algorithme est accompagné d'une condition de faisabilité analogue à U £ 1, et peut être adapté pour tenir compte des terminaisons plus tôt des tâches, ou pour l'ordonnancement de tâches activées dynamiquement (via test d'acceptation en-ligne simple). Il existe également d'autres algorithmes tels que WFQ (Weighted Fair Queueing) ou SFQ (Start Fair Queueing) plus complexes ou avec un écart temporel plus élevé.

Avec ces algorithmes, le rythme de progression de chaque tâche varie en fonction de åiwi, donc en fonction de la structure du système (tâches activées non terminées). Il existe des variantes qui fonctionnent par allocation, dès la phase d'acceptation (ou hors-ligne), d'une fraction fixée de la bande passante de traitement du processeur, indépendamment du nombre et du poids des autres tâches : il s'agit de recalculer les poids absolus des tâches à chaque changement de structure du système (activation ou fin de tâche) de manière à ce que pour chaque tâche, wi/åjwj corresponde à la bande passante allouée.

L'inconvénient du modèle d'ordonnancement fluide est que les surcoûts système sont plus élevés : liés d'une part aux préemptions tous les q quanta de temps (par interruption), et d'autre part aux décisions d'ordonnancement qui doivent être prises quoi qu'il arrive. Cependant, en pratique, ces surcoûts demeurent raisonnables parce que i) les systèmes d'exploitation gèrent une horloge système, donc on peut profiter de l'interruption d'horloge pour prendre les décisions d'ordonnancement, auquel cas le quanta de temps q correspond à la résolution de l'horloge système (ou à un multiple) ; ii) les algorithmes d'ordonnancement pour ce modèle sont peu coûteux (comparables à la complexité des ordonnancements à tourniquet, ou round-robin en anglais, des systèmes généralistes).

L'avantage de ce modèle est qu'il permet de résoudre des problèmes d'ordonnancement temps-réel complexes en multiprocesseur, comme nous le verrons en 3.8.2.

3.6.2   Ordonnanceurs multiples et hiérarchiques

Dans les paragraphes précédents, nous considérions une application unique, et le système d'exploitation était chargé d'arbitrer entre les besoins en ressources de toutes les tâches de façon globale.

Quelques travaux s'intéressent cependant aux systèmes à ordonnanceurs multiples (ou également à priorités en couches), c'est à dire au cas où plusieurs ordonnanceurs doivent cohabiter dans le système. En particulier, les travaux [Mig99] et [Nav99] présentent une technique analytique fondée sur le calcul d'une borne sur le temps de réponse des tâches, pour établir l'ordonnançabilité lorsque le système est constitué de plusieurs files d'exécution, pour lesquelles la politique d'ordonnancement peut être soit de type FIFO, soit de type tourniquet (c'est le cas de système respectant la norme Posix 1003.1b).

Les travaux sur l'ordonnancement hiérarchique s'attachent à rendre le modèle de système plus modulaire, d'apparence mieux conçu, de sorte que le système est composé d'applications disposant chacune d'une fraction des ressources du système, dont la ressource processeur. L'idée est d'isoler les besoins et les occupations de ressources entre applications, y compris au niveau de la gestion des contraintes de temps et des occupations processeur [Sta93a], de la même manière que l'est la mémoire par exemple.

Pour cela, l'approche est de partager le travail d'ordonnancement entre plusieurs niveaux hiérarchiques. Dans le modèle le plus simple [WL99a, RH01, CJ98], l'ordonnancement des tâches est délégué à une composante spécialisée de l'application parente ; et le système s'occupe de l'ordonnancement des ordonnanceurs des applications. Ce modèle d'ordonnancement hiérarchique peut être étendu à plus de deux niveaux.

Dans un tel modèle, l'application devient un composant du système chargée elle-même de l'ordonnancement de ses tâches, avec les avantages d'abstraction et de modularité que cela apporte (aspect boîte noire), mais aussi avec toute la difficulté de prouver la composition de tels composants vis à vis des contraintes temporelles [RS01].

Pour supporter ce paradigme, plusieurs notions sont proposées, qui peuvent être composées dans le système : Quelques travaux [BM01, BM02] présentent un prototype d'implantation incluant ces deux notions, pour des mécanismes à deux niveaux hiérarchiques, fondés sur un langage dédié à la définition des ordonnanceurs.

Étant donné la complexité de prouver le comportement temporel correct de tels systèmes, ils trouvent en général bien leur place dans les systèmes temps-réel souple, et peuvent dans ce cas s'accommoder d'une connaissance minimale, incomplète, ou approximative sur les comportements temporels des applications et de leur tâches.

3.7   Relâchement d'hypothèses sur l'environnement et le système

Jusqu'à présent, le système était conçu à des fins de prévention des fautes temporelles : il était admis que toute tâche en cours d'exécution dans le système avait un comportement temporel et des besoins en ressources connus dès la phase de conception, ou au moment de l'acceptation.

Nous allégeons maintenant ces hypothèses, en considérant des systèmes pour lesquels toutes les informations sur le comportement temporel de l'application et de l'environnement ne sont pas disponibles avant l'acceptation des tâches. Cela peut être dû à une très grande complexité de modélisation (plusieurs centaines de tâches interdépendantes par exemple) qui empêche de caractériser leur comportement. Ou à une volonté délibérée de ne pas prendre en compte les comportements pire-cas systématiquement, de manière à rentabiliser au maximum les ressources système.

Face à ces lacunes, il s'agit soit de ramener le comportement réel dans les limites d'un comportement pire-cas identifié (principe de filtrage présenté en 3.5), soit de prévoir l'information manquante.

Nous présentons ici brièvement deux approches dont le rôle est de s'adapter à l'absence, avant exécution, d'informations utiles aux décisions d'ordonnancement. Ces mécanismes trouvent largement leur place en temps-réel souple.

3.7.1   Approche par prévision

Le principe de cette approche est que le système observe son propre comportement selon un certain nombre de métriques, et utilise ses observations pour prétendre prévoir l'évolution du comportement à venir, et ainsi fonder une partie des décisions (d'ordonnancement ici) sur ces prévisions. Les informations manquantes sont donc générées à partir du comportement passé.

En pratique, le fonctionnement consiste en un composant qui définit le comportement à venir d'un paramètre à partir des valeurs brutes mesurées, de leur dérivée et de leur intégrale : on parle de contrôleur PID (pour proportional integral derivative en anglais). Ce composant injecte ses résultats en entrée du mécanisme de décision, et l'ensemble forme ainsi une boucle de rétroaction (feedback control en anglais). Le choix se porte vers le contrôleur PID parce qu'il s'agit d'un composant dont le comportement (en particulier les conditions de stabilité) a été largement étudié en traitement du signal.

Ainsi, il existe une extension de EDF (FC-EDF et FC-EDF2 pour Feedback-Control EDF) [SLS98, LSA+00] qui utilise une rétroaction PID afin de prévoir la charge à venir. Cette prévision conditionne le choix de la version de chaque tâche à accepter, pour des tâches qui existent en plusieurs versions.

Il existe également des extensions de TPS (présenté en 3.5.3) [GS96, SG97a, NG97a, NGM01] qui permettent d'affiner l'ordonnancement des tâches principales, par prévision des temps d'exécution en fonction des temps d'exécution observés dans le passé (stockés dans une base de données).

3.7.2   Systèmes réflexifs

Le principe de cette approche est symétrique à la précédente : le système dispose de toutes les informations qui lui permettent de reconstruire de façon précise l'information manquante. Une autre caractéristique des systèmes réflexifs est qu'ils sont capables de modifier leur propre structure si ils jugent que l'état courant l'exige. Cette deuxième caractéristique peut consister en une reconfiguration du système (voir en 3.5.2), ou en la sélection de mécanismes d'exécution à la volée (comme une stratégie de tolérance aux fautes par exemple). L'ensemble de ces deux caractéristiques peut être offert par le langage dans certains cas, ou sinon elle doit faire partie du modèle de système.

Grâce à la première propriété, il est par exemple possible de connaître l'ensemble des entités (objets, ressources) qui interviendront pendant l'exécution d'un travail, avant l'activation de celui-ci, et en fonction de l'état courant du système (par exemple si l'activation des travaux d'une tâche est modélisée par un automate). Ensuite, grâce à ces connaissances, il est possible de dérouler les tests d'acceptation et l'ordonnancement [Sta93b].

Ainsi, le système Spring [SRN+98], dont l'ordonnancement est de type plan dynamique, utilise cette approche afin de générer ses plans : la chaîne de compilation hors-ligne extrait le maximum d'informations sur le comportement de chacune des entités. Ces informations permettent également de vérifier automatiquement en-ligne un certain nombre de contraintes de synchronisation. Le même type de fonctionnement est considéré dans [RSYJ97] où il s'agit d'utiliser les informations sur les différentes entités du système, ainsi que leurs différents besoins en ressources, pour pouvoir initier des changements de configuration suivant l'évolution des utilisations de ressources, elles-mêmes conditionnées par le comportement de l'environnement.

3.8   Ordonnancement pour systèmes multiprocesseurs ou distribués

Nous considérons ici des systèmes constitués de plusieurs processeurs qui coopèrent pour exécuter l'application, et présentons très brièvement les problèmes liés à l'ordonnancement dans ce contexte, ainsi que quelques voies pour les résoudre.

Dans ce qui suit, nous disons qu'un système est multiprocesseur quand l'ordonnancement qui s'exécute est unique (i.e. les files d'attentes de tâches sont partagées entre tous les processeurs), et qu'il est distribué quand l'ordonnancement est distribué (i.e. chaque processeur est en charge de l'ordonnancement d'une partie donnée des tâches). Les décisions qui mènent à un choix de conception plutôt qu'à l'autre dépendent du degré de couplage entre les processeurs : un système à mémoire physiquement partagée sera plus naturellement régi par un ordonnanceur central unique (modèle multiprocesseur ci-dessus), qu'un système architecturé sans mémoire partagée autour d'un réseau local.

Après avoir présentés quelques difficultés liées à l'ordonnancement de ce type de systèmes (section 3.8.1), nous indiquons très brièvement quelques travaux dans le domaine de l'ordonnancement multiprocesseur (section 3.8.2), puis distribué (section 3.8.3).

3.8.1   Problématique

Nous l'avons vu en 3.2.2.2, dans le schéma le plus simple (pas de ressource, pas de précédence), aucun ordonnanceur multiprocesseur en-ligne n'est optimal [Mok83] (en particulier aucune extension multiprocesseur de RM ou de EDF). Par contre, suivant les modèles de tâches choisis, il existe des algorithmes d'ordonnancement qui permettent d'ordonnancer les tâches (mais de façon non optimale), et qui sont accompagnés de conditions de faisabilité.

L'ordonnancement en multiprocesseur ou en distribué procède par conséquent au cas par cas, et se heurte à un certain nombre de difficultés dans l'établissement des conditions de faisabilité car, par rapport au cas centralisé, il existe un certain nombre d'``anomalies'' [Law83, GFB01], comme par exemple :

3.8.2   Ordonnancement pour systèmes multiprocesseurs

Ce modèle de système correspond au plus simple envisageable : par rapport à l'ordonnancement centralisé, il s'agit d'ajouter une étape d'affectation des tâches aux processeurs, et à gérer leur migration vers les autres processeurs (en général à faible surcoût).

Un cas particulier à ce modèle correspond à un domaine de recherche particulièrement actif actuellement : il concerne les multiprocesseurs uniformes. Dans ce modèle, si un traitement met c unités de temps à s'exécuter sur un processeur, ce même traitement demandera s.c unités de temps pour s'exécuter sur un autre processeur du système, avec le facteur s (la vitesse ou rapidité) constant et connu. Les multiprocesseurs identiques sont un cas particulier de multiprocesseur uniforme : tous les processeurs ont la même capacité de traitement, i.e. s=1 pour tout couple de processeurs du système.

Dans ce cas, il existe une condition nécessaire et suffisante pour l'ordonnançabilité d'un ensemble de tâches périodiques indépendantes [FGB01, GBF02] (algorithme d'ordonnancement inconnu). Ce résultat est utilisé pour dériver une condition suffisante pour l'ordonnancement de tâches périodiques par une variante de EDF sur multiprocesseur. Dans cette variante, si le système comporte m processeurs, à tout instant les travaux prêts à être exécutés et de plus haute priorité sont affectés aux processeurs les plus rapides, jusqu'à concurrence de m travaux, et en assurant qu'un travail plus prioritaire qu'un autre est affecté à un processeur plus rapide. Cette définition de EDF introduit par conséquent beaucoup de migrations (au rythme des activations et terminaisons des tâches), mais aucune alternative ne semble diminuer ce nombre de migrations dans le cas général [GFB01].

D'autres travaux [ABJ01] se sont intéressés à l'aménagement analogue de RM pour le cas particulier du multiprocesseur identique, et proposent une condition suffisante pour l'ordonnançabilité.

Les algorithmes d'ordonnancement fluide ont également été étendus au cas multiprocesseur identique pour des tâches périodiques indépendantes [AS99, BGP95, RM00].

Lorsque des contraintes plus complexes sont à prendre en compte (autres ressources, précédences), peu de résultats existent concernant ces algorithmes simples. En pratique, l'ordonnancement de tels systèmes repose sur les mêmes méthodes que celles utilisées pour les systèmes distribués.

3.8.3   Ordonnancement pour systèmes distribués

Dans ces systèmes, il n'y a pas un unique mécanisme d'ordonnancement qui centralise les informations et les décisions d'ordonnancement, mais plusieurs (1 par processeur, ou 1 par multiprocesseur). Par rapport à l'ordonnancement multiprocesseur, quatre difficultés supplémentaires apparaissent : Pour pallier aux complexités théoriques, et aux difficultés de réalisation majeures, en pratique trois voies sont couramment empruntées : l'ordonnancement statique (pour la ressource processeur et/ou réseau), l'ordonnancement avec affectation statique des processeurs, et différentes heuristiques.

3.8.3.1   Ordonnancements statiques

Étant donné la complexité du problème d'ordonnancement, il est intéressant de la reléguer hors-ligne (par exemple, dans [EJ00], ou dans les systèmes Mars [KFG+92, SRG89, Foh94] et Maruti [SdSA95]), ce qui permet de définir et de valider à la fois les allocations des processeurs et du réseau dès la phase de conception.

3.8.3.2   Ordonnancements avec affectation statique des processeurs

Dans ce modèle, les tâches sont regroupées par processeur dès la phase de conception, et un algorithme d'ordonnancement dérivé du cas centralisé est employé sur chaque processeur.

Ainsi, il existe des approches qui reposent sur la définition d'un plan au niveau de l'ordonnancement pour le réseau (on parle de multiplexage temporel, ou TDMA pour Time Division Multiple Access). Il s'agit ensuite d'associer à chaque émission ou réception de message, une tâche sporadique dans chacun des systèmes communiquant en point à point, et à intégrer ces tâches dans le modèle de système, en intercalant entre elles les temps de propagation du messages sous la forme de contraintes de précédence, de temps de blocage, et de gigue de démarrage. Lorsqu'il s'agit d'affecter les différentes tâches aux processeurs pour ce modèle de système, les travaux [TBW92a] proposent une solution fondée sur une méthode d'optimisation globale suboptimale (le recuit simulé). Les travaux [Nav99] présentent une approche comparable lorsque les messages sont échangés sur un réseau à priorité (bus CAN), et s'intéressent également au taux de mon respect des échéances dû à la perte ou à l'altération de messages.

Il existe d'autres modèles de systèmes beaucoup plus simples, où les échanges de messages entre processeurs sont modélisés par des traitants d'interruption (de plus haute priorité que toutes les tâches) qu'il s'agit de prendre en compte dès la phase de conception [TH99]. Cette phase de validation est beaucoup plus complexe, puisqu'il s'agit d'étudier de manière exhaustive tous les entrelacements possibles de toutes les tâches avec les interruptions possibles, suivant les profils d'émission de messages.

3.8.3.3   Heuristiques

Dans les systèmes distribués plus complexes, qui doivent considérer par exemple à la fois des contraintes de précédence et de ressources en environnement hétérogène et de façon dynamique, il existe des approches suboptimales par heuristiques.

L'algorithme le plus répandu étant l'algorithme myope (myopic algorithm en anglais) [Man98], utilisé dans le système Spring [SRN+98]. Le système Spring est composé de multiprocesseurs à 4 processeurs à mémoire partagée, dont 1 spécialisé dédié à l'ordonnancement, et les multiprocesseurs sont reliés entre eux par un réseau dédié. L'algorithme myope est chargé d'établir des plans dynamiques pour chaque multiprocesseur, en tenant compte des précédences (éventuellement vis à vis des autres multiprocesseurs du système) et des contraintes temporelles. Il repose sur un algorithme d'allocation sur les processeurs locaux itératif, relié à un test d'acceptation, et dont le nombre d'itérations est borné à la conception.

Cet algorithme a été étendu pour supporter des modèles de tâches particuliers, tels que les FERTS évoqués en 3.5.2, ou l'intégration de tâches temps-réel souple [MMM00b] (par serveur).

3.8.3.4   Considérations de tolérance aux fautes

Une définition anecdotique des systèmes distribués (attribuée à Leslie Lamport) est : ``A distributed system is one that stops you from getting any work done when a machine you've never even heard of crashes''. En effet, dans un système distribué, la probabilité qu'au moins un élément soit défaillant est mécaniquement liée (exponentiellement) au nombre d'éléments dans le système.

En conséquence, pour les systèmes distribués temps-réel critiques, il est nécessaire de prendre en compte les fautes qui peuvent apparaître. La technique est d'utiliser la redondance (des traitements ou des messages de communication) temporelle ou spatiale de façon à détecter ou masquer les fautes qui peuvent apparaître.

Mais gérer la redondance de façon correcte impose que les fonctions répliquées soient cohérentes entre elles, ce qui amène à résoudre le problème du consensus, ce qui rajoute des contraintes supplémentaires à la conception du système. Notamment parce qu'une des briques de base est de déterminer, et de façon cohérente, quels noeuds sont corrects ou non, avant de pouvoir établir l'accord sur les décisions entre les noeuds corrects (on parle de mécanisme de gestion de groupe). Or ceci, dans le modèle de défaillance le plus simple dit à silence sur défaillance, rajoute la présence d'un délai de détection de défaillance, souvent élevé, à prendre en compte dans la conception du système.

Un autre problème qui se pose en présence de mécanisme de tolérance aux fautes des noeuds est celui du redémarrage des noeuds après défaillance, et de leur réinsertion dans le système. Cette faculté, quand elle est supportée, pose à la fois le problème de la cohérence de la décision de réinsertion vis à vis du mécanisme de gestion de groupe, et également celui de la reprise d'un état correct par le noeud qui se réinsère. Suivant l'implantation du système et le mécanisme de reprise, celui-ci peut entraîner des occupations en ressources conséquentes le temps du transfert ou de l'établissement de l'état de reprise qu'il est nécessaire de prendre en compte en particulier dans l'ordonnancement des messages réseau [Vij98].

Le système MARS [KFG+92] par exemple propose toute une architecture avec redondance du réseau et des traitements, et leur intégration avec les contraintes de temps-réel. La tolérance aux fautes est facilitée de par la conception autour d'un plan d'ordonnancement connu de tous les noeuds, permettant par exemple de détecter la défaillance d'un noeud (absence ou retard d'un message).

De même, Spring [GSSR97, MM97], Hades [CPC+00] ou Dharma [MMM00a] proposent plusieurs solutions pour la gestion de plusieurs types de redondances logicielles en contexte de temps-réel. Par exemple, Hades repose sur la décomposition des traitements du système en unités élémentaires caractérisées hors-ligne par des besoins en ressources, et liées entre elles par des contraintes de précédences éventuellement conditionnelles accompagnées de l'envoi de messages. Ce type d'architecture autorise la prise en compte des traitements répliqués pour établir le consensus même en présence de défaillances, dans les analyses d'ordonnancement.

1
Ce type de graphe rassemble les arbres convergents et divergents, mais n'est pas du tout adapté aux cas courants où des échanges de messages peuvent se faire en travers de l'arbre [SSNB94].
2
Ou toute fonction de chaînes de travaux vers R qui possède la propriété : f(a) £ f(b) Þ f(a..ab...b) £ f(a..ba..b).
3
J. Migge [Mig99] remarque que l'ordonnancement à priorité statique correspond à la définition d'une priorité à l'échelle de la tâche (i.e. tous travaux confondus), et que l'ordonnancent à priorité dynamique revient la plupart du temps à définir la priorité à l'échelle de chaque travail (c'est le cas pour l'ordonnancement EDF par exemple).
4
Pour le moment, nous considérons qu'il s'agit du temps d'exécution effectif, toujours constant. En 3.3.4, nous nuancerons cette définition.
5
Cette suite admet un point fixe dès que åj £ i Cj/Tj £ 1, or ceci est vrai puisque åj £ i Cj/Tj £ U £ 1.
Précédent Index Suivant