Ordonnanceurs pour SETR

Les termes techniques utilisés ici sont identifiés et définis dans le glossaire proposé aux pages ≈5..8 de STR – Volume 00.

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 :

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.

Rôle d'un ordonnanceur

Un ordonnanceur, tout système d'exploitation confondu, joue plusieurs rôles, dont :

Cette liste est fortement inspirée de http://en.wikipedia.org/wiki/Scheduling_(computing)

La caractéristique par laquelle un ordonnanceur dans un SETR diverge le plus clairement de la norme est qu'il est foncièrement inéquitable, mais a le devoir de tout faire pour que les tâches puissent rencontrer leurs échéances.

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 :

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 :

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.

Sous QNX, par exemple, il y a 256 niveaux de priorité.

Selon man sched(7), Linux accepte des priorités de 1 à 99 inclusivement, où 1 est le plus prioritaire, mais ces priorités s'appliquent si l'ordonnanceur suit une politique TR

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.

Les principaux algorithmes d'ordonnancement de QNX sont l'ordonnancement FIFO, l'ordonnancementRound-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 :

À 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 , consommé par l'exécution du thread qui le remplit périodiquement d'un montant ).

Quand le thread bloque, le remplacement de la part de son budget qui a été consommée, paramètre , est planifié pour se produire après un certain délai d'exécution (ici : ).

Dans le schéma à droite, un thread s'exécute à sa priorité normale pour un temps déterminé par son budget d'exécution initial . Une fois ce budget épuisé, sa priorité baisse au niveau 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 .

Conséquemment, si le système est bien conçu, le thread pourra s'exécuter à chaque période pour un temps d'exécution maximal , donc un thread de priorité ne consommera que 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 par période de temps , sans que cette exécution ne soit contiguë pendant ladite période.

À droite, le budget du thread est de dans une période de remplissage de . Son exécution initiale bloque après , ce qui entrâine la planification d'un remplissage au seuil de .

Le thread peut s'exécuter à nouveau après , ce qui planifie une autre phase de remplissage. Le thread a alors encore dans son budget d'exécution.

Le thread s'exécute ensuite sans bloquer pour , ce qui épuise son budget, et sa priorité chute à ; à partir de ce moment, il se peut qu'il ne puisse plus prendre la main.

Le premier remplissage de , planifié en début de parcours, devrait se produire au seuil de , donc à l'échéance de . Au seuil de , un remplissage de se produit et le thread récupère sa priorité normale .

Le thread consomme les de son budget et sa priorité redescend; enfin, son budget « subit » un remplissage de au seuil de 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.


Valid XHTML 1.0 Transitional

CSS Valide !