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.

L'ordonnanceur tient typiquement une file d'attente pour chaque niveau de priorité (sous QNX, il y en a 256 niveaux), 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.

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.

Lectures complémentaires

Quelques liens pour enrichir le propos.


Valid XHTML 1.0 Transitional

CSS Valide !