Prudence : document en construction, et structure en émergence...
Pour un résumé des symboles typiques pour les éléments clés des différents tests « d'ordonnançabilité » que vous trouverez dans la littérature, vous pouvez vous référer à ceci (version PDF) ou à cette version HTML.
Les exécutifs, bien qu'ils soient de précieux outils, manquent un peu de flexibilité. En effet :
Pour ces raisons, il arrive souvent qu'on aborde le problème de l'ordonnancement des tâches TR sur un angle plus général, soit celui des ordonnanceurs (Schedulers, en anglais), donc de modules spécialisés dans l'établissement et la gestion de l'exécution des tâches.
Étant donné un ensemble de tâches, si nous évitons la question de la communication entre elles de même que la question de la synchronisation des accès aux ressources, les états possibles d'une pour une tâche donnée (du moins pour ce qui est d'intérêt ici; on se souviendra que dans un SETR typique, il y en a un peu plus que cela, pour tenir compte des responsabilités du système d'exploitation à l'égard de la gestion des ressources) sont :
Les systèmes d'exploitation ont tous au moins un ordonnanceur, souvent de nature équitable. Les ordonnanceurs TR tendent quant à eux à ne pas être équitables, favorisant le respect des contraintes des tâches, en particulier celles des tâches prioritaires, plutôt qu'un bon temps d'exécution moyen ou qu'une répartition en apparence équitable du temps d'exécution.
On trouve au moins trois grandes familles de stratégies d'ordonnancement, applicables à des tâches qui soient préemptives ou non. Ces stratégies visent à déterminer un ordonnancement permettant à toutes les tâches d'un ensemble donné de respecter leurs contraintes, ce qui revient typiquement à déterminer les priorités de chacune des tâches de manière telle qu'un ordonnanceur général et inéquitable opérant avec ces tâches mène à un STR correct, donc dont les tâches s'exécutent correctement et à temps.
Deux grandes règles générales guident le travail des ordonnanceurs TR :
Sur la base de la première règle, on comprendra qu'il peut survenir des situations où le respect de toutes les contraintes TR d'un ensemble de tâches ne sont pas rencontrées, dans le cas où les tâches TR considérées sont toutes des tâches TR souples. Un débordement dit « transitoire » survient alors.
La seconde règle garantit que les contraintes de toutes les tâches TR au sens strict d'un système donné seront respectées. Toutefois, cette règle est très contraignante et il est possible que son application mène à des systèmes qui sous-utilisent les ressources disponibles, ou tout simplement au rejet de systèmes qui pourraient être viables. C'est alors qu'un effort d'optimisation des WCET et des temps d'arrivée devient nécessaire.
Trouver un schème optimal de priorités pour un ensemble de tâches n'est pas banal. Un théorème (Audsley, 1993) indique (je paraphrase) que :
« [...] si une tâche se fait apposer la plus faible priorité et est faisable dans le respect de ses contraintes, alors s'il existe un ordonnancement de priorités pour l'ensemble des tâches à ordonnancer, il existe un ordonnancement valide où a la plus faible priorité »
L'idée est que dans un tel cas, souffre des pires interférences possibles, et ceci indépendamment de l'ordonnancement des priorités des autres tâches. On peut trouver un schème optimal (ou presque) de priorités en appliquant successivement cette approche et en enlevant chaque fois de l'ensemble à ordonnancer la tâche ayant tout juste été placée.
S'il y a possibilité de blocage entre les tâches, on peut se rapprocher de l'optimalité si le coût du blocage est faible.
Notez que dans un STR, la priorité d'une tâche dépend des contraintes TR qu'elle doit respecter, pas de la relative importance de son travail dans le système.
La famille la plus connue regroupe des stratégies reposant sur des tâches à priorité déterminées a priori, ou Fixed Priority Scheduling (FPS). Les algorithmes à priorité fixe sont sans doute les plus connus du lot, les plus utilisés aussi.
Un irritant bien connu des ordonnancements de type FPS est celui de l'inversion de priorités, résultant d'une interaction entre deux tâches où celle à plus faible priorité possède une ressource dont a besoin celle à plus haute priorité, et bloque l'action de cette dernière par le fait-même. Le caractère quelque peu inflexible d'une approche FPS est une cause directe de tels problèmes.
L'algorithme RMS, pour Rate Monotonic Scheduling, est un cas bien connu d'algorithme FPS. Cet algorithme est très répandu du fait qu'il permet de trouver les priorités requises pour un ordonnancement optimale des tâches à ordonnancer si .
En gros, pour appliquer RMS, on choisit a priori des priorités sur la base de la période des tâches : plus courte est la période de la tâche, plus haute est sa priorité.
//
struct Tache {
int periode;
int wcet;
// ...
};
bool respecte_conditions_rms(const Tache &tache) {
return tache.wcet < tache.periode;
}
//
// fonction qui place les tâches en ordre décroissant de priorité (précondition : taches est ordonnançable)
//
vector<Tache> ordonnancer_rms(vector<Tache> taches) {
assert(all_of(begin(taches), end(taches), respecte_conditions_rms));
stable_sort(begin(taches), end(taches), [](const Tache &a, const Tache &b) {
return a.periode < b.periode;
});
return taches;
}L'algorithme DMPO, pour Deadline Monotonic Priority Ordering, est un autre algorithme de la famille FPS. Avec cet algorithme, chaque tâche doit avoir une échéance inférieure ou égale à sa période, et chaque tâche doit aussi avoir un WCET inférieur ou égal à son échéance (donc ).
Les tâches y sont indépendantes les unes des autres; elles ne peuvent pas se bloquer mutuellement et ne peuvent pas se suspendre pas elles-mêmes.
Sous DMPO, . Dans la mesure où ses conditions sont respectées, DMPO mène à un ordonnancement optimal : la preuve implique de prendre un ordonnancement existant puis de transformer graduellement les priorités que génère cet ordonnancement pour qu'il devienne DMPO, conservant chaque fois l'ordonnançabilité de l'ensemble.
Les contraintes propres à RMS et les contraintes propres à DMPO sont semblables : chaque tâche y a une priorité unique, distincte des autres, fixée a priori et basée sur sa période (plus la période est basse, plus la priorité est haute).
//
struct Tache {
int periode;
int echeance;
int wcet;
// ...
};
bool respecte_conditions_dmpo(const Tache &tache) {
return tache.wcet < tache.echeance && tache.echeance < tache.periode;
}
//
// fonction qui place les tâches en ordre décroissant de priorité (précondition : taches est ordonnançable)
//
vector<Tache> ordonnancer_rms(vector<Tache> taches) {
assert(all_of(begin(taches), end(taches), respecte_conditions_dmpo));
stable_sort(begin(taches), end(taches), [](const Tache &a, const Tache &b) {
return a.periode < b.periode;
});
return taches;
}Une autre famille bien connue regroupe les stratégies prenant en charge des tâches dont les priorités varient au fil du temps, ou Dynamic Priority Scheduling (DPS).
L'algorithme EDF, pour Earliest Deadline First, suppose . Avec cet algorithme, la tâche la plus proche de son échéance est la prochaine à être ordonnancée – conséquemment, l'échéance de chaque tâche doit y être connue a priori.
Pour être en mesure d'appliquer l'algorithme EDF, évidemment, toute tâche doit avoir une échéance, ce qui peut restreindre ses champs d'application.
L'algorithme EDF n'est pas sans défauts, cependant. De manière générale, d'ailleurs, les algorithmes de la famille FPS sont plus souvent rencontrés dans les STR du fait qu'ils sont plus simples à implémenter que ne le sont les algorithmes de la famille DPS tels que EDF. Il s'avère aussi qu'en pratique, EDF est plus sensible aux surcharges systémiques que ne le sont les algorithmes FPS. Quand le système est débordé, EDF tend à entraîner, par effet domino, une cascade de manquements aux contraintes TR des diverses tâches qu'il ordonnance.
Une stratégie d'ordonnancement sur la base des échéances, dont EDF est le cas type, souffre d'un problème cousin de celui de l'inversion de priorités, c'est-à-dire l'inversion d'échéances. Les solutions à ce problème s'apparentent aussi, en plus complexes, à celles connues pour l'inversion de priorités.
Détail important : avec un algorithme FPS, l'instant critique représente le pire cas d'utilisation du système, mais avec EDF ce n'est pas le cas.
//
struct Tache {
int echeance;
// ...
};
//
// fonction qui place les tâches en ordre décroissant de priorité (précondition : taches est ordonnançable)
//
vector<Tache> ordonnancer_rms(vector<Tache> taches) {
stable_sort(begin(taches), end(taches), [](const Tache &a, const Tache &b) {
return a.echeance < b.echeance;
});
return taches;
}Enfin, il existe une famille regroupant des stratégies reposant sur l'importance relative des tâches à exécuter, ou Value-Based Scheduling (VBS), dans lesquelles l'ordonnanceur cherche à appliquer une forme d'intelligence dans la stratégie d'ordonnancement en quantifiant cette relative importance, typiquement parce qu'il est susceptible d'être débordé.
//
struct Tache {
// ...
};
double evaluer_valeur(const Tache&);
//
// fonction qui place les tâches en ordre décroissant de priorité (précondition : taches est ordonnançable)
//
vector<Tache> ordonnancer_rms(vector<Tache> taches) {
stable_sort(begin(taches), end(taches), [](const Tache &a, const Tache &b) {
return evaluer_valeur(a) < evaluer_valeur(b);
});
return taches;
}Voilà!
