Ordonnanceurs pour SETR

Ce qui suit est un bref survol des bases propres à la question des ordonnanceurs dans les SETR. Vos notes de cours (si vous suivez un cours avec moi, à tout le moins, mais en général je présume) vont plus loin, et la littérature va évidemment beaucoup plus loin.

Quelques thématiques connexes sont couvertes ailleurs, incluant :

• Bases sur l'ordonnancement (vocabulaire, tâches périodiques)
• Tests « d'ordonnançabilité »

Une part importante de ce qui suit est inspiré de ce que propose QNX, qui est (littéralement) un SETR exemplaire. J'utiliserai SETR pour faire référence au système d'exploitation TR, alors que j'utiliserai « système » tout court pour faire référence à un ensemble d'unités d'exécution collaborant dans la réalisation d'une tâche.

Enjeux

Un SETR ne cherche pas à être équitable, au contraire : son rôle est de s'assurer de certaines caractéristiques foncièrement inéquitables. Par exemple :

• Les processus prioritaires dominent l'exécution du système
• Un système bien construit respectera ses contraintes TR (s'il est possible d'y arriver)
• Un processus de faible priorité ne bloquera pas l'exécution d'un processus plus important

Pour y arriver, un SETR met en place certaines stratégies, que nous survolerons ci-dessous.

Noyau à faible priorité

Le noyau d'un SETR est l'un des composants les moins importants d'un SETR. Pour cette raison, il n'interfère pas avec les tâches à haute priorité, qui gardent la main une fois qu'ils l'ont acquise.

Le noyau d'un SETR prendra la main quand :

• Un événement sollicitera son ordonnanceur, ce qui permettra momentanément à quelques processus de même importance de partager les ressources. Par événement, on entend ici :
  • une exception; une interruption matérielle
  • une interruption logicielle, incluant la fin du temps alloué à un thread
  • un interblocage, etc.
• Le processus prioritaire en cours d'exécution fera un appel système, ce qui provoquera une inversion de priorités, et conséquemment élèvera le noyau au niveau de priorité du processus client par la voie d'un héritage de priorités

En fait, le noyau de QNX est préemptible. Sans surprises, le noyau redonnera la main au processus client dès que cela sera possible. Son objectif premier est d'être essentiellement invisible et de ne pas interférer avec les opérations du système.

Services du noyau

Comme tous les noyaux de systèmes d'exploitation, celui d'un SETR offre une interface pour un petit nombre de services. Comme le montre l'image à droite (qui n'est pas à jour, mais illustre convenablement le propos), le micronoyau de QNX prend en charge : L'ordonnancement des threads de ses processus Les mécanismes de synchronisation, pour réagir aux interblocages Les mécanismes de communication entre processus, pour des raisons d'efficacité (ces mécanismes sont critiques au bon fonctionnement d'un système), et Ce qui a trait au temps et aux interruptions, bien entendu Un système d'exploitation comme QNX respecte l'interface POSIX, commune à plusieurs systèmes d'exploitation (surtout les dérivés d'UNIX), mais il est d'usage de recourir à ses services plus spécialisés, du moins lorsqu'on l'utilise pour ce en fonction de quoi il a été conçu : gérer la bonne exécution des STR.

Cette image a été prise d'une version antérieure de QNX neutrino

Gestion des interblocages

Pour réagir lors d'interblocages, en particulier les cas qui découlent d'une inversion de priorités, un SETR doit prendre en charge la gestion des ressources susceptibles de bloquer un thread. Ainsi, le noyau d'un SETR doit connaître les états des divers threads sous sa gouverne avec précision, ce qui lui permet de constater les interblocages et de modifier les priorités des threads au besoin.

Cette image a été prise d'une version antérieure de QNX neutrino

Ordonnanceurs

Essentiellement, un thread dans un SETR s'exécute jusqu'à ce qu'un appel système, une exception ou une interruption survienne. À ce moment, le noyau s'anime et prend une décision d'ordonnancement, peu importe le processus dans lequel s'exécutait le thread qui vient de s'interrompre. Cette décision mènera habituellement à la reprise du thread venant tout juste de s'interrompre, mais un changement de contexte se produira si ce thread est bloqué, préempté ou se suspend volontairement.

L'ordonnanceur tient typiquement une file d'attente pour chaque niveau de priorité, et chacune de ces files d'attente contient les threads prêts à s'exécuter et ayant la priorité en question.

• Un thread bloqué (en attente d'une ressource) est retiré de la file d'attente des threads prêts à s'exécuter, puis y est réinséré lorsqu'il débloque
• Un thread sera préempté si un thread de priorité supérieure devient prêt; le thread préempté demeure en tête de sa propre file d'attente
• Un thread qui se suspend volontairement est replacé à la fin de sa propre file d'attente. Il est possible qu'il reprenne immédiatement la main, par exemple s'il n'a fait qu'un yield et demeure le seul à avoir la priorité la plus haute du lot

Les principaux algorithmes d'ordonnancement de QNX sont l'ordonnancement FIFO, l'ordonnancement Round-Robin, l'ordonnancement adaptatif et l'ordonnancement sporadique. De manière amusante, QNX permet à chaque thread (sans blagues!) ce choisir l'algorithme qui s'appliquera à lui : quand une décision sera prise quant à l'ordonnancement d'un thread dans sa file d'attente, la stratégie d'ordonnancement de ce thread sera celle qui sera tenue en ligne de compte.

Ordonnancement FIFO

Dans une approche FIFO, un thread en cours d'exécution pourra se suspendre volontairement, que ce soit un bloquant ou en faisant un appel système, et pourra se faire préempter par un thread de plus haute priorité

Ordonnancement Round-Robin

Dans une approche de type Round-Robin, un thread en cours d'exécution pourra se suspendre volontairement, que ce soit un bloquant ou en faisant un appel système, et pourra se faire préempter par un thread de plus haute priorité, mais pourra aussi épuiser la tranche de temps qui lui aura été attribuée. En effet, dans cette approche, un thread accepte de s'exécuter pour une tranche de temps fixée lorsqu'il aura pris la main, et d'être suspendu une fois cette tranche de temps épuisée (ce qui ne signifie pas qu'il ne reprendra pas la main immédiatement, bien sûr)

Ordonnancement adaptatif

Une approche adaptative est une adaptation de l'approche de type Round-Robin, dans laquelle un thread qui a consommé la totalité de sa tranche de temps sans bloquer voit sa priorité réduite d'un niveau si au moins un autre thread de même priorité est dans sa file d'attente (on parle alors de décrépitude de priorité, ou Priority Decay).

Le thread retrouvera sa priorité s'il s'exécute puis bloque, ou s'il n'a pas été ordonnancé depuis plus d'un certain seuil de temps (typiquement : une seconde).

Ordonnancement sporadique

Dans une approche d'ordonnancement sporadique, les choses sont plus complexes :

• Le principe de cette stratégie est de fixer un plafond sur le temps d'exécution attribué à un thread dans une période de temps donnée, donc de contrôler le taux d'occupation d'un ordonnancement par un thread
• Ceci permet entre autres de réaliser ce qu'on nomme du Rate Monotonic Analysis (RMA) sur un système contenant à la fois des événements périodiques et apériodiques. Vu grossièrement, une approche est Rate Monotonic si elle favorise l'ordonnancement de tâches ayant une courte période
• Avec un ordonnancement sporadique, du fait qu'un thread ne peut monopoliser à lui seul l'occupation d'un ordonnanceur, ce thread peut réagir à des événements apériodiques sans mettre en péril les tâches critiques du même système

À l'image d'un ordonnancement FIFO, un thread assujetti à un ordonnancement sporadique s'exécute jusqu'à ce qu'il bloque ou jusqu'à ce qu'il soit préempté par un thread de plus haute priorité. À l'image d'un ordonnancement adaptatif, un thread assujetti à un ordonnancement sporadique pourra perdre un niveau de priorité dans certaines circonstances.

Cela dit, l'ordonnancement sporadique donne un contrôle plus fin sur les fluctuations de priorité d'un thread, à partir d'une combinaison de facteurs paramétrables : budget initial de temps alloué, temps maximal d'exécution à pleine priorité, seuil de priorité plus faible auquel réduire le thread au lorsque cela s'avère opportun, quoi faire pour récupérer un budget de temps pleinement dépensé, et limites imposées sur le nombre de telles récupérations

Exemples

Examinons brièvement l'impact d'un ordonnancement sporadique. Comme plus haut, ces images ont été prises d'une version antérieure de QNX neutrino, et le texte de l'article vers lequel mène ce lien demeure enrichissant encore aujourd'hui.

L'image à droite montre un ordonnancement sporadique fixant un budget de temps d'exécution initial, paramètre $C$, consommé par l'exécution du thread qui le remplit périodiquement d'un montant $T$). Quand le thread bloque, le remplacement de la part de son budget qui a été consommée, paramètre $R$, est planifié pour se produire après un certain délai d'exécution (ici : $40 ms$).
Dans le schéma à droite, un thread s'exécute à sa priorité normale $N$ pour un temps déterminé par son budget d'exécution initial $C$. Une fois ce budget épuisé, sa priorité baisse au niveau $L$ jusqu'à un éventuel remplissage du budget. Si le thread ne bloque pas et n'est jamais préempté, sa priorité descendra à un seuil plus bas, pour devenir une sorte de tâche d'arrière-plan, ce qui est susceptible d'avoir pour conséquence de ne plus lui permettre de s'exécuter, du moins si les priorités des autres threads du système dépassent la sienne. Une fois le remplissage de son budget complété, sa priorité redevient $N$. Conséquemment, si le système est bien conçu, le thread pourra s'exécuter à chaque période $T$ pour un temps d'exécution maximal $C$, donc un thread de priorité $N$ ne consommera que $\frac{C}{T}\%$ du temps d'exécution disponible.
Si un thread bloque plusieurs fois, il se peut que le remplissage de son budget d'exécution se produise à divers moments, donc que son budget d'exécution total soit $C$ par période de temps $T$ , sans que cette exécution ne soit contiguë pendant ladite période. À droite, le budget $C$ du thread est de $10 ms$ dans une période de remplissage $T$ de $40 ms$. Son exécution initiale bloque après $3 ms$, ce qui entrâine la planification d'un remplissage au seuil de $40 ms$. Le thread peut s'exécuter à nouveau après $6 ms$, ce qui planifie une autre phase de remplissage. Le thread a alors encore $7 ms$ dans son budget d'exécution. Le thread s'exécute ensuite sans bloquer pour $7 ms$, ce qui épuise son budget, et sa priorité chute à $L$; à partir de ce moment, il se peut qu'il ne puisse plus prendre la main. Le premier remplissage de $7 ms$, planifié en début de parcours, devrait se produire au seuil de $46 ms$, donc à l'échéance de $T$. Au seuil de $40 ms$, un remplissage de $3 ms$ se produit et le thread récupère sa priorité normale $N$. Le thread consomme les $3 ms$ de son budget et sa priorité redescend; enfin, son budget « subit » un remplissage de $7 ms$ au seuil de $46 ms$ pour reprendre sa priorité normale. Visiblement, le thread continuera d'osciller d'un niveau de priorité à l'autre, desservant des événements apériodiques dans excéder les paramètres de contrôle que nous lui aurons apposés.

Ordonnancement par partitions

Enfin, QNX permet de réaliser de l'ordonnancement par partitions, par lequel les tâches sont groupées par ensembles qui sont par la suite répartis sur les coeurs disponibles. Ceci permet de gérer autrement la contention pour les ressources, en particulier pour le processeur

Lectures complémentaires

Quelques liens pour enrichir le propos.

• Un Whitepaper sur l'ordonnancement de SETR dans une perspective QNX, par Jeff Schaffer et Steve Reid en 2015, peut être consulté sur http://qnx.symmetry.com.au/resources/whitepapers/qnx_joy_of_scheduling.pdf
• Rate-Monitonic Analysis : ../../Liens/Temps-Reel--Liens.html#rate_monotonicity
• Ordonnancement adaptatif : http://community.qnx.com/sf/wiki/do/viewPage/projects.core_os/wiki/APS_How_it_Works_FAQ
• Pour voir les sources d'un ordonnanceur, celui du système d'exploitation nommé Fuchsia : https://github.com/fuchsia-mirror/zircon/blob/master/kernel/kernel/sched.c