Ordonnancement du processeur

Un ordonnanceur du processeur choisit le processus ou le fil d’exécution prêt qui s’exécutera ensuite sur un processeur. La règle qu’il suit est sa politique. Le répartiteur met le choix en œuvre en passant à l’exécution de la tâche sélectionnée. Une autre politique peut utiliser le même mécanisme de commutation.

Suivre les changements d’état

Une tâche en cours d’exécution dispose d’un processeur. Une tâche prête pourrait s’exécuter, mais attend son tour. Une tâche bloquée attend un événement, comme la fin d’une lecture disque. Seules les tâches prêtes peuvent être sélectionnées.

Supposons qu’un éditeur lance une lecture disque alors qu’un compilateur est prêt. L’éditeur passe de l’état en cours d’exécution à l’état bloqué, ce qui permet au compilateur de s’exécuter. À la fin de la lecture, une interruption remet l’éditeur à l’état prêt. Il ne s’exécute pas nécessairement tout de suite : la politique doit choisir entre lui et les autres tâches prêtes.

Les décisions d’ordonnancement interviennent lorsqu’une tâche se bloque, se termine, devient prête ou est interrompue et remise à l’état prêt. Céder volontairement le processeur le libère aussi. La préemption consiste à retirer le processeur à une tâche qui aurait pu continuer à s’exécuter ; son état sauvegardé est conservé et elle peut reprendre plus tard.

Une interruption d’horloge permet au noyau d’imposer une tranche de temps, même si un programme boucle sans céder le processeur. La fin d’une entrée-sortie peut aussi déclencher une préemption en rendant prête une tâche plus favorisée. Linux, Windows et macOS utilisent l’ordonnancement préemptif.

Le travail se déroule par rafales

Les programmes alternent entre des rafales de calcul, pendant lesquelles ils effectuent des calculs, et des périodes d’attente d’entrées-sorties. Un programme limité par le processeur, comme un encodeur, présente de longues rafales de calcul. Un programme limité par les entrées-sorties, comme un éditeur, effectue souvent de courts calculs avant d’attendre. Donner rapidement accès au processeur à un éditeur après une frappe peut améliorer sa réactivité sans lui donner beaucoup de temps processeur au total.

Le répartiteur sauvegarde l’état de l’ancienne tâche, restaure les registres de la tâche choisie et reprend son flux d’instructions en mode utilisateur. La latence de répartition est le temps nécessaire pour passer l’exécution à une autre tâche. La commutation perturbe aussi les caches et le tampon de traduction, ou TLB, qui conserve des traductions d’adresses. La tâche suivante peut devoir les remplir à nouveau : la sauvegarde des registres ne représente donc qu’une partie du coût.

Trois échelles de temps pour l’ordonnancement

L’ordonnanceur à long terme admet les tâches soumises et contrôle leur nombre dans le système. L’ordonnanceur à moyen terme peut suspendre des processus entiers en les retirant de la mémoire par échange, puis les y replacer. L’ordonnanceur à court terme sélectionne la prochaine tâche prête et intervient fréquemment. Les systèmes généralistes s’appuient principalement sur ce dernier rôle ; les systèmes par lots et les grappes de calcul peuvent aussi contrôler explicitement l’admission.

Commence une comparaison de politiques avec des tâches simples qui n’utilisent que le processeur et dont les durées sont connues. Fais ensuite varier une caractéristique : des durées inégales révèlent les attentes causées par FIFO, des arrivées tardives révèlent les limites de l’absence de préemption, les entrées-sorties créent des possibilités de recouvrement du travail et les durées inconnues nécessitent une prédiction ou une rétroaction.

Un ordonnancement indique quand les tâches s’exécutent. Un indicateur précise quelle partie de cet ordonnancement compte. Note l’arrivée, la première exécution et la fin de chaque tâche avant de calculer des moyennes.

Distinguer les trois temps

Le temps de séjour mesure tout l’intervalle entre l’arrivée et la fin. Le temps de réponse mesure le délai jusqu’à la première exécution. Le temps d’attente additionne tous les intervalles passés à l’état prêt sans exécution.

Pour une tâche qui n’utilise que le processeur, le temps de séjour est égal au temps d’attente plus le temps d’exécution sur le processeur. Avec des entrées-sorties, le temps passé à l’état bloqué fait aussi partie du temps de séjour : soustraire seulement le temps processeur surestimerait donc l’attente. Ici, le temps de réponse est défini à partir de la première exécution ; un service destiné aux utilisateurs peut mesurer séparément le délai jusqu’à son premier résultat.

Étudier une frise FIFO

A arrive à 0 ms et demande 8 ms de temps processeur. B arrive à 1 ms et demande 4 ms. C arrive à 2 ms et demande 2 ms. Sans coût de commutation, FIFO donne :

• A : 0–8 ms.
• B : 8–12 ms.
• C : 12–14 ms.

Le temps de séjour moyen est de $\frac{8+11+12}{3}=\frac{31}{3}\approx \mathrm{10,33}$ ms. Les temps de réponse et d’attente moyens sont tous deux de $\frac{0+7+10}{3}=\frac{17}{3}\approx \mathrm{5,67}$ ms. Ils coïncident parce que chaque tâche s’exécute une fois sans interruption. Avec la préemption, une tâche peut attendre à nouveau après son premier tour ; le temps d’attente peut donc dépasser le temps de réponse.

Mesurer toute la charge de travail

Le débit compte les tâches terminées par unité de temps écoulé. L’ordonnancement termine trois tâches en 14 ms, soit environ 214,29 tâches/s. Le taux d’utilisation du processeur est le temps pendant lequel le processeur est occupé divisé par le temps écoulé ; il est ici de 100 %, car le processeur n’est jamais inactif. Précise l’intervalle de mesure : ajouter une période d’inactivité après la fin modifierait les deux valeurs.

Un taux d’utilisation élevé peut tout de même s’accompagner de longues attentes. Il ne signifie pas non plus que tout le temps d’occupation correspond à du travail utile pour les applications : les mesures réelles peuvent compter les commutations et d’autres travaux du noyau comme du temps d’occupation. Précise si un calcul de surcoût mesure le temps d’occupation ou le travail utile.

Choisir ce qu’il faut optimiser

Pour le travail par lots, le temps de séjour moyen compte souvent. Pour le travail interactif, une réponse rapide compte. Les services partagés ont besoin d’un accès équitable ainsi que d’un bon débit. La famine signifie qu’une tâche admissible attend indéfiniment ; une bonne moyenne ne suffit donc pas à établir que le traitement est équitable.

Examine les délais individuels et la queue de la distribution. Un temps de réponse au 99e percentile décrit le délai au-dessous duquel ou auquel se situent environ 99 % des observations ; quelques attentes très longues peuvent disparaître dans une moyenne faible. Soustrais toujours l’instant d’arrivée propre à chaque tâche et compte ses périodes d’exécution comme du service, jamais comme de l’attente.

FIFO, aussi appelé premier arrivé, premier servi ou FCFS, exécute les tâches prêtes par ordre d’arrivée. Il est non préemptif : une arrivée ultérieure ne peut pas interrompre une rafale de calcul en cours. Dans les exemples sans entrées-sorties, chaque tâche sélectionnée s’exécute jusqu’à son terme.

Observer l’effet de convoi

A, B et C arrivent ensemble. A demande 60 ms ; B et C demandent chacune 6 ms. Avec A en premier, FIFO exécute A 0–60, B 60–66 et C 66–72. Les temps de séjour sont de 60, 66 et 72 ms, soit une moyenne de 66 ms. Les petites tâches passent la majeure partie de leur vie à attendre derrière A. C’est l’effet de convoi.

La politique du plus court travail d’abord (SJF) sélectionne la prochaine rafale de calcul la plus courte parmi les tâches prêtes et ne la préempte pas. Avec les mêmes arrivées, elle exécute B 0–6, C 6–12, puis A 12–72. Le temps de séjour moyen devient $\frac{6+12+72}{3}=30$ ms. Le travail total du processeur reste de 72 ms ; l’amélioration vient du fait que les tâches courtes se terminent plus tôt.

Pourquoi cela aide-t-il ? Si une longue rafale s’exécute juste avant une courte, les deux tâches attendent tous les travaux précédents. Inverser seulement ces deux rafales réduit l’attente de la tâche courte de la durée de la longue rafale, tout en augmentant celle de la tâche longue de la seule durée de la courte rafale. Répéter ces inversions place les rafales par ordre croissant. Si toutes les tâches arrivent ensemble et que leurs durées sont connues, SJF minimise les temps de séjour et d’attente moyens ; dans ce cas non préemptif sans entrées-sorties, le temps de réponse jusqu’à la première exécution est aussi égal au temps d’attente.

Limiter le choix aux tâches prêtes

A arrive maintenant à 0 ms, tandis que B et C arrivent à 10 ms. À 0 ms, A est le seul choix possible. SJF non préemptif exécute A 0–60, B 60–66, C 66–72. Les temps de séjour sont de 60, 56 et 62 ms, soit une moyenne d’environ 59,33 ms. SJF ne peut pas agir sur une tâche future ni interrompre une rafale déjà commencée.

FIFO évite la famine lorsque les tâches précédentes finissent par libérer le processeur. SJF peut provoquer la famine d’une tâche longue en attente si des tâches courtes continuent d’arriver.

Prédire une rafale

La prochaine rafale de calcul est généralement inconnue. Un lissage exponentiel combine la dernière rafale mesurée avec la prédiction précédente :

Ici, $t_n$ est la rafale mesurée, ${\tau }_n$ la prédiction précédente et $\alpha$ un poids compris entre 0 et 1. En partant de 10 ms et en utilisant $\alpha =\mathrm{0,5}$, une mesure de 6 ms donne une prédiction de 8 ms. Une mesure suivante de 4 ms donne 6 ms ; une autre de 6 ms laisse la prédiction à 6 ms. Avec un poids nul, les mesures n’ont aucun effet ; avec un poids de un, seule la mesure la plus récente compte. La grandeur prédite est la durée de la rafale de calcul, et non la taille du fichier programme ou le nombre de lignes.

La politique du plus court temps restant d’abord (STCF), aussi appelée SRTF, est la version préemptive de SJF. À une arrivée ou à une fin de tâche, compare le temps processeur dont chaque tâche prête a encore besoin. Une nouvelle tâche interrompt la tâche en cours lorsqu’elle demande moins de temps que celui qui reste à cette dernière.

Comparer les temps restants

A demande 60 ms et arrive à 0 ms. B et C demandent chacune 6 ms et arrivent à 10 ms. A s’exécute pendant 10 ms ; il lui reste 50 ms. À 10 ms, B l’emporte car 6 ms est inférieur à 50 ms ; C a la même durée, donc l’ordre d’arrivée puis le nom départagent l’égalité.

La frise est A 0–10, B 10–16, C 16–22, A 22–72. Les temps de séjour sont de 72 ms pour A, 6 ms pour B et 12 ms pour C, soit une moyenne de 30 ms. Les temps de réponse sont de 0, 0 et 6 ms, soit une moyenne de 2 ms. Pour ces arrivées, SJF non préemptif donne un temps de séjour moyen d’environ 59,33 ms et un temps de réponse moyen d’environ 35,33 ms.

Soustrais toujours le temps de service déjà reçu. Comparer une nouvelle rafale de 12 ms aux 60 ms initiales de A serait une erreur s’il ne restait que 5 ms à A. STCF terminerait d’abord A. Lorsque les durées sans entrées-sorties sont connues et que le coût de commutation est nul, STCF minimise le temps de séjour moyen, quels que soient les instants d’arrivée. Les tâches longues peuvent tout de même subir une famine si des tâches plus courtes continuent d’arriver.

Lorsque toutes les tâches sans entrées-sorties arrivent ensemble, SJF et STCF donnent le même ordre. La tâche la plus courte en cours d’exécution ne fait que raccourcir ; aucune tâche en attente ne devient donc une raison de la préempter.

Utiliser le temps de blocage d’une autre tâche

Une tâche bloquée ne peut pas utiliser le processeur. Son attente d’entrée-sortie offre l’occasion d’exécuter d’autres tâches prêtes, même avec une politique non préemptive. La préemption redevient utile lorsque la fin d’une entrée-sortie rend prête une courte rafale alors qu’une autre tâche s’exécute.

Considère A avec cinq rafales de calcul de 10 ms et une lecture disque de 10 ms après chacune de ses quatre premières rafales. B demande une rafale de calcul de 50 ms. Les deux arrivent à 0 ms. Si le processeur reste inactif pendant les lectures de A et retarde B jusqu’à la fin de A, A se termine à 90 ms et B à 140 ms.

Traite chaque rafale de A à son retour comme une tâche courte prête :

• A s’exécute de 0 à 10 ; sa lecture occupe la période 10–20 pendant que B s’exécute.
• A revient pour la période 20–30 ; il reste 40 ms à B, donc les 10 ms de A l’emportent.
• B s’exécute de 30 à 40 pendant la lecture suivante. L’alternance se répète.
• La dernière rafale de A s’exécute de 80 à 90 ; B termine les 10 ms restantes de son travail pendant la période 90–100.

A se termine toujours à 90 ms, mais B se termine à 100 ms. Le processeur effectue 100 ms de travail en 100 ms de temps écoulé. L’activité du disque et celle du processeur se recouvrent ; le processeur n’exécute pas A pendant que A est bloquée. Une interruption de périphérique remet A à l’état prêt à la fin de chaque lecture, après quoi STCF compare sa nouvelle rafale au travail restant de B.

L’ordonnancement à tour de rôle (RR) maintient une file FIFO de tâches prêtes et donne à la tâche en tête au plus un quantum, ou tranche de temps. Une tâche qui se termine ou se bloque libère le processeur avant la fin de sa tranche. Une tâche encore prête lorsque sa tranche expire passe en fin de file.

Suivre les tours avant de calculer les temps

A, B et C arrivent à 0 ms et demandent chacune 9 ms. Avec un quantum de 3 ms, RR exécute :

• Premier tour : A 0–3, B 3–6, C 6–9.
• Deuxième tour : A 9–12, B 12–15, C 15–18.
• Dernier tour : A 18–21, B 21–24, C 24–27.

Les premières exécutions ont lieu à 0, 3 et 6 ms ; le temps de réponse moyen est donc de 3 ms. Les fins ont lieu à 21, 24 et 27 ms ; le temps de séjour moyen est donc de 24 ms. FIFO donne un temps de réponse moyen de 9 ms et un temps de séjour moyen de 18 ms. Ici, RR démarre rapidement toutes les tâches, mais repousse la fin de la première à 21 ms.

RR répartit l’accès au processeur pendant que les tâches sont en concurrence ; il n’égalise pas leurs instants de fin. Une tâche courte peut se terminer à son premier tour. Avec un ensemble fixe de $n$ tâches prêtes et un quantum $q$, l’attente entre deux tours est au plus de $(n-1)q$ sans coût de commutation. Des arrivées continues, d’autres classes de priorité et des restrictions sur les processeurs utilisables modifient le cadre dans lequel cette borne s’applique.

Traiter les arrivées à la fin d’une tranche

Utilise l’ordre d’arrivée, puis l’ordre alphabétique en cas d’égalité. Une tâche qui arrive exactement à l’expiration d’une tranche rejoint la file avant la tâche préemptée. Avec A qui arrive à 0 ms et demande 8 ms, B à 1 ms et demande 4 ms, et C à 2 ms et demande 2 ms, un quantum de 2 ms donne A 0–2, B 2–4, C 4–6, A 6–8, B 8–10, A 10–14.

Le dernier intervalle de A contient deux tours consécutifs sans concurrent. Les temps de réponse sont de 0, 1 et 2 ms ; les temps de séjour sont de 14, 9 et 4 ms. Leurs moyennes sont de 1 ms et 9 ms. Dans RR de base, lorsqu’une tâche bloquée revient, elle rejoint la file pour un nouveau tour ; elle ne réserve pas son temps processeur inutilisé pendant qu’elle est bloquée.

Choisir un quantum qui justifie son coût

Un très grand quantum fait fonctionner RR comme FIFO pour les rafales plus courtes que ce quantum. Un quantum minuscule provoque de nombreuses répartitions et perturbe les caches à répétition. Dans une mise en œuvre simple fondée sur une horloge, le quantum correspond à un nombre entier de périodes d’horloge.

Pour un coût de commutation $s$ après chaque tranche utile de durée $q$, la fraction approximative de surcoût est de $\frac{s}{q+s}$. Une commutation de 0,1 ms coûte environ 9,1 % avec une tranche de 1 ms, mais environ 0,99 % avec une tranche de 10 ms. Des tranches plus longues amortissent le coût des commutations en le répartissant sur plus de travail utile.

Une règle pratique courante consiste à choisir une tranche dans laquelle la plupart des rafales, par exemple environ 80 %, se terminent. Le bon choix dépend des durées de rafales mesurées et des délais de réponse que la charge de travail peut tolérer. Compte séparément les commutations entre tâches et les événements d’horloge qui laissent simplement continuer la seule tâche prête.

Un ordonnanceur par priorité exécute la tâche prête la plus prioritaire. Les tâches de même priorité peuvent suivre l’ordre FIFO ou s’exécuter à tour de rôle. Dans une version préemptive, une tâche plus prioritaire qui devient prête prend immédiatement le processeur ; dans une version non préemptive, elle attend que la tâche en cours le libère.

Lire le sens de l’échelle

Les numéros de priorité n’ont pas de sens universel. Dans les exemples de manuel présentés ici, utilise les plus petits nombres pour les priorités les plus élevées. Les valeurs nice de Linux suivent le même sens, mais les niveaux de priorité de Windows et les priorités temps réel de Linux utilisent les plus grands nombres pour les priorités les plus élevées.

A, B et C arrivent à 0 ms avec des rafales de 4, 3 et 5 ms et les priorités 2, 1 et 3. L’ordonnancement non préemptif par priorité exécute B 0–3, A 3–7 et C 7–12. Leurs temps d’attente sont de 0, 3 et 7 ms, soit une moyenne d’environ 3,33 ms ; leurs temps de séjour sont de 3, 7 et 12 ms, soit une moyenne d’environ 7,33 ms.

Une priorité interne découle d’un comportement mesuré, comme l’utilisation du processeur ou les attentes d’entrées-sorties. SJF détermine le rang à partir de la durée prédite de la rafale. Une priorité externe vient d’une personne, par exemple un administrateur qui juge une sauvegarde moins urgente. Aucun de ces choix ne garantit que les tâches peu prioritaires reçoivent du temps si des tâches plus prioritaires arrivent continuellement.

Augmenter la priorité pendant l’attente

Le vieillissement augmente progressivement la priorité d’une tâche en attente. Si son rang augmente d’un niveau toutes les 100 ms, une tâche qui commence à la priorité 20 atteint la priorité maximale 0 après 2 s d’attente à l’état prêt. Un rang plus élevé la met en concurrence avec les tâches favorisées ; les règles de départage déterminent les tours entre tâches de même rang.

La famine est une absence de progression causée par la sélection répétée d’autres tâches. Le vieillissement y remédie en modifiant le rang au fil du temps. Il répond à un objectif différent de la prédiction de la durée des rafales : une tâche longue qui attend depuis longtemps peut mériter un tour même si sa rafale reste longue.

Suivre la dépendance dans une inversion de priorité

Une tâche très prioritaire H peut être bloquée en attendant un verrou détenu par une tâche peu prioritaire L. Une tâche de priorité intermédiaire M peut préempter L. H ne peut alors pas avancer, même si M est moins prioritaire que H : L doit d’abord s’exécuter pour libérer le verrou. C’est une inversion de priorité.

Avec l’héritage de priorité, L hérite temporairement de la priorité de H tant qu’elle détient le verrou dont H a besoin. M ne peut plus empêcher L d’utiliser le processeur. L s’exécute, libère le verrou et perd la priorité héritée ; H devient prête et peut s’exécuter.

Augmenter la priorité de H ne libère pas le verrou qu’elle attend : H reste bloquée. Il faut permettre au fil d’exécution capable de satisfaire la dépendance de s’exécuter. En 1997, Mars Pathfinder a rencontré un problème d’inversion de priorité, résolu en activant l’héritage de priorité.

Un ordonnanceur à files multiniveaux avec rétroaction (MLFQ) combine priorités et ordonnancement à tour de rôle. Son objectif est de se rapprocher du service offert aux tâches courtes et de garder les tâches interactives réactives sans connaître à l’avance la durée d’exécution future de chaque tâche. L’utilisation récente du processeur fournit la rétroaction.

Appliquer les règles des files

Chaque tâche prête appartient à une file de priorité. La version de base avec comptabilisation suit quatre règles :

1. Choisir la file de priorité la plus élevée qui contient des tâches prêtes.
2. Dans cette file, faire passer les tâches de même priorité à tour de rôle.
3. Placer une nouvelle tâche dans la file supérieure.
4. Rétrograder une tâche lorsqu’elle épuise son allocation de temps processeur à son niveau actuel, en comptant l’utilisation sur tous ses tours et malgré les interruptions pour entrées-sorties.

Un quantum limite un tour. Une allocation limite le service total à un niveau de priorité. Un niveau peut autoriser plusieurs quanta avant une rétrogradation. Au niveau le plus bas, une rétrogradation laisse la tâche dans la file inférieure.

Cela donne à une nouvelle tâche une chance de se terminer rapidement. Une tâche qui consomme régulièrement du temps processeur révèle un besoin plus long et descend. Une courte rafale suivie d’un blocage consomme peu d’allocation ; les tâches interactives tendent donc à rester plus longtemps dans les niveaux élevés.

Suivre une tâche longue et une nouvelle venue

Utilise les files Q2, Q1 et Q0, avec Q2 au sommet, des quanta de 10 ms et des allocations de 10 ms à chaque niveau, sans relèvement pendant ce suivi. A demande 200 ms et arrive à 0 ms. Elle s’exécute dans Q2 de 0 à 10, dans Q1 de 10 à 20, puis dans Q0.

À 100 ms, A a reçu 100 ms de temps processeur. B arrive et demande 20 ms. B entre dans Q2 et préempte A, puis s’exécute de 100 à 110 dans Q2. Elle a consommé l’allocation de ce niveau et descend dans Q1. Q1 est plus prioritaire que Q0 où se trouve A ; B s’exécute donc de 110 à 120 et se termine. A reprend à 120 et achève ses 100 ms restantes à 220 ms. Le temps de séjour de B est de 20 ms bien qu’elle soit arrivée après une tâche beaucoup plus longue.

Suis le travail restant de A pendant l’exécution de B : il reste de 100 ms. Le temps avance pendant le service de B, mais A ne reçoit alors aucun service processeur.

Distinguer l’attente de la consommation de processeur

Un éditeur qui s’exécute pendant 1 ms puis attend une saisie utilise une allocation de 10 ms en dix rafales de ce type. Le temps passé à l’état bloqué n’est pas décompté de l’allocation de processeur. Avec une comptabilisation stricte, ces courtes rafales s’additionnent tout de même : l’éditeur finit donc par descendre, sauf si un relèvement de priorité le remonte d’abord.

Une ancienne règle de MLFQ ne rétrogradait que les tâches qui utilisaient un quantum entier sans interruption. Une tâche qui cédait le processeur juste avant son expiration conservait sa priorité. Cette règle rendait les tâches interactives réactives, mais permettait aussi une manipulation délibérée. Comptabiliser l’utilisation cumulée du processeur ferme cette faille.

Les files inférieures s’exécutent lorsque toutes les files supérieures ne contiennent aucune tâche prête. Une tâche plus prioritaire qui est bloquée n’empêche pas les tâches moins prioritaires d’utiliser le processeur. Si la demande des tâches très prioritaires reste soutenue, les tâches inférieures ont besoin d’un mécanisme supplémentaire contre la famine, fourni par les relèvements périodiques.

La rétroaction produit une séparation utile, mais le comportement passé d’une tâche peut cesser de représenter ses besoins actuels. Un long calcul peut ensuite devenir interactif. Pendant ce temps, une tâche de la file inférieure peut attendre indéfiniment si les files supérieures restent occupées.

Réexaminer périodiquement chaque tâche

Un relèvement de priorité ramène toutes les tâches dans la file supérieure après une période $S$. Il permet aux tâches en attente de partager cette file et à l’ordonnanceur de réapprendre les changements de comportement. Une tâche limitée par le processeur qui a été remontée consomme ensuite son allocation et redescend.

Considère les premières règles de MLFQ : deux tâches interactives cèdent toujours le processeur avant la fin d’une tranche complète de 10 ms et maintiennent ensemble Q2 occupée. Une tâche limitée par le processeur attend dans Q0. Sans relèvement, elle ne reçoit aucun service. Dans un ordonnancement répétitif où un relèvement toutes les 100 ms lui donne un tour de 10 ms au niveau supérieur avant sa rétrogradation, puis où les tâches supérieures occupent le reste du temps, elle reçoit 10 % du processeur. Ce pourcentage provient de ce suivi ; un relèvement n’attribue pas une part fixe générale.

Une longue période de relèvement laisse de longues attentes entre les occasions de s’exécuter. Une période très courte réinitialise sans cesse les tâches limitées par le processeur et réduit l’avantage des tâches interactives. Certaines conceptions ont utilisé des périodes proches d’une seconde, mais le choix dépend du comportement de la charge de travail et des objectifs de réponse.

Comptabiliser malgré les cessions du processeur

La manipulation de l’ordonnanceur est un problème distinct. Avec l’ancienne règle fondée sur une tranche entière, un programme peut s’exécuter pendant 9 ms, demander une entrée-sortie de 1 ms et recommencer. Il n’utilise jamais une tranche entière de 10 ms d’un seul coup et conserve donc la priorité maximale tout en consommant presque tout le temps processeur disponible.

Avec une allocation cumulative de 10 ms, la première rafale consomme 9 ms et il reste 1 ms. Après l’entrée-sortie, une milliseconde supplémentaire épuise l’allocation et la tâche est rétrogradée pendant sa deuxième rafale. Une demande d’entrée-sortie change l’état ; elle n’efface pas le service déjà reçu. La règle de comptabilisation empêche cette tactique même sans relèvement.

Régler les niveaux

Choisis le nombre de files, le quantum de chaque file, l’allocation de chaque niveau et la période de relèvement. Les files supérieures utilisent généralement des quanta courts, par exemple 10 ms, pour alterner rapidement entre les tâches interactives. Les files inférieures peuvent utiliser des quanta beaucoup plus longs, parfois de plusieurs centaines de millisecondes, pour réduire les commutations pendant les calculs soutenus.

L’allocation peut augmenter indépendamment du quantum. Un niveau avec un quantum de 5 ms et une allocation de 15 ms peut autoriser trois tours complets avant la rétrogradation. Augmenter l’allocation retarde le classement d’une tâche parmi les tâches longues ; augmenter le quantum allonge un tour individuel.

La conception du partage du temps de Solaris illustre la rétroaction fondée sur une table : sa table classique configurable comporte 60 niveaux de priorité, avec des quanta allant d’environ 20 ms en haute priorité à quelques centaines de millisecondes en basse priorité. Les conceptions classiques de BSD calculaient plutôt la priorité à partir de l’utilisation récente du processeur, dont l’influence diminue avec le temps. Dans les deux cas, l’influence des anciennes utilisations du processeur diminue, de sorte que le passé lointain d’un fil d’exécution ne détermine pas définitivement son traitement.

L’ordonnancement à part proportionnelle vise à répartir le service processeur selon les parts attribuées. Dans l’ordonnancement par loterie, chaque tâche pouvant s’exécuter possède des tickets. Un ticket gagnant tiré au hasard choisit la tâche pour la prochaine tranche de durée égale. La probabilité qu’une tâche gagne est son nombre de tickets divisé par le nombre total de tickets des tâches pouvant s’exécuter.

Trouver le ticket gagnant

A détient 100 tickets, B 50 et C 250. Numérote les 400 tickets de 0 à 399. A possède les tickets 0–99, B les tickets 100–149 et C les tickets 150–399. Un tirage de 300 sélectionne C.

Une mise en œuvre fondée sur une liste tire un nombre et cumule les nombres de tickets. Les totaux cumulés sont de 100 après A, 150 après B et 400 après C. Arrête-toi au premier total strictement supérieur au nombre tiré. Utiliser « supérieur ou égal » attribuerait incorrectement les tickets situés aux frontières : le numéro 100 appartient à B. Placer d’abord les détenteurs du plus grand nombre de tickets réduit la longueur moyenne de cette recherche dans la liste.

Distinguer l’espérance d’une garantie

Si A détient 75 tickets et B 25, la part espérée de A est de 75 %. Sur 100 tirages indépendants de tranches égales, les deux tâches pouvant s’exécuter, A peut espérer 75 gains. L’écart-type est de :

$\sqrt{100\times \mathrm{0,75}\times \mathrm{0,25}}\approx \mathrm{4,33}$ tranches.

Un résultat d’environ 71–79 gains se situe à peu près à un écart-type de la moyenne ; ce n’est pas un intervalle garanti. Sur de courtes durées, le résultat peut s’écarter fortement du rapport visé de 3:1. À mesure que la fenêtre d’observation s’allonge, la dispersion aléatoire relative diminue. La loterie offre une équité probabiliste, sans répartition exacte sur une fenêtre finie ni attente bornée avant le tour suivant.

Pour deux tâches ayant le même nombre de tickets et les mêmes besoins en processeur, l’indicateur d’inéquité U divise l’instant de fin le plus précoce par le plus tardif. Le rapport atteint 1 lorsqu’elles se terminent ensemble et il est plus petit lorsque l’une se termine beaucoup plus tôt. Ce rapport de fin est particulièrement variable pour les tâches courtes ordonnancées par loterie.

Répartir les tickets entre utilisateurs et selon les dépendances

La monnaie de tickets permet à un utilisateur de répartir localement un droit global attribué. L’utilisateur X possède 200 tickets globaux et attribue 300 tickets locaux à X1 et 100 à X2. Sur 400 tickets locaux, X1 en possède les trois quarts, ce qui lui donne 150 tickets globaux ; X2 en reçoit 50. L’utilisateur Y possède 100 tickets globaux pour Y1. Le total est de 300 : X1 reçoit donc une part espérée de 50 %, X2 d’environ 16,67 % et Y1 d’environ 33,33 % du processeur disputé.

Le transfert de tickets prête temporairement les tickets d’un client à un serveur qui travaille pour lui, puis les lui rend lorsque la requête est terminée. Il suit ainsi la dépendance entre les travaux. L’inflation des tickets permet à des tâches qui coopèrent d’augmenter leur propre nombre de tickets pour demander davantage de service. Elle nécessite de la confiance ou des limites : une inflation sans restriction permet à une tâche avide de diluer les parts de toutes les autres.

La loterie a besoin du total des tickets, mais ne conserve pas la progression de chaque tâche dans le service reçu. Une nouvelle tâche ajoute simplement ses tickets à l’ensemble des tâches pouvant s’exécuter. L’attribution des tickets reste un choix de politique ; le tirage aléatoire applique ce choix en espérance. Les tickets d’une tâche bloquée ne concourent pas pour une tranche qu’elle ne peut pas utiliser.

L’ordonnancement par pas transforme les parts de tickets en une séquence déterministe. Chaque tâche pouvant s’exécuter possède un pas, calculé en divisant une grande constante par son nombre de tickets, et une valeur de passage qui enregistre sa progression pondérée. Choisis la valeur de passage la plus faible, exécute cette tâche pendant une tranche de même durée, puis ajoute son pas à sa valeur de passage.

Calculer les pas

A possède 50 tickets, B 25 et C 100. Avec la constante 1 000, leurs pas sont de 20, 40 et 10. Plus une tâche possède de tickets, plus son pas est petit. La valeur de passage d’une tâche favorisée augmente lentement : elle devient donc plus souvent la plus faible.

Initialise toutes les valeurs de passage à zéro et départage les égalités par ordre alphabétique. Garde les valeurs dans l’ordre fixe A, B, C :

Seule la valeur de passage de la tâche sélectionnée change. En sept tranches, A reçoit deux tours, B un et C quatre : exactement le rapport 50:25:100. Lorsque toutes les valeurs de passage valent 40, chaque tâche a progressé de la même quantité de service pondéré. Entre ces moments d’alignement, les parts sur une courte période ne sont pas nécessairement exactes.

Distinguer le service réel de la progression virtuelle

La valeur de passage sert au classement : elle ne représente ni le temps écoulé ni un nombre de tickets. Le grand pas de B la fait attendre pendant que les valeurs de passage de A et de C rattrapent la sienne. B reçoit tout de même la part prévue d’un septième sur ce cycle répétitif. Ajouter le nombre de tickets à la valeur de passage inverserait le principe : la tâche ayant le plus de tickets ferait le plus grand saut et serait sélectionnée moins souvent.

La constante contrôle l’échelle des pas, pas les rapports de tickets visés. Les mises en œuvre en nombres entiers ont besoin d’une précision suffisante pour éviter que les arrondis ne déforment ces rapports. Les comparaisons et les mises à jour doivent utiliser une échelle cohérente.

Placer judicieusement une nouvelle tâche

Supposons que les tâches déjà présentes aient des valeurs de passage proches de 4 000. Une nouvelle tâche commençant à zéro gagnerait à répétition pendant son rattrapage, même avec peu de tickets. Initialise sa valeur de passage par rapport à la progression actuelle du système, par exemple au minimum actuel, afin qu’elle ne reçoive pas de service pour le temps précédant son arrivée.

Le temps d’exécution virtuel de Linux utilise une idée proche : il comptabilise une progression pondérée pour le service processeur réel. Dans les deux cas, un droit plus élevé fait augmenter cette progression plus lentement, ce qui permet à la tâche de rester en concurrence pour obtenir du service par la suite.

Les ordonnanceurs équitables de Linux suivent le service processeur pondéré. L’ordonnanceur complètement équitable (CFS), introduit dans Linux 2.6.23 en 2007, choisissait la tâche pouvant s’exécuter dont le temps d’exécution virtuel était le plus faible. Linux a commencé à remplacer cette règle de sélection par EEVDF dans la version 6.6 en 2023.

Répartir le service selon les poids

Une valeur nice va de −20, la plus favorisée, à +19, la moins favorisée. Nice 0 a le poids 1 024. Chaque échelon vers une valeur nice plus élevée réduit le poids d’un facteur d’environ 1,25. Exemples de poids : 3 121 pour nice −5, 820 pour nice 1, 335 pour nice 5, 110 pour nice 10 et 15 pour nice 19.

Nice 0 face à nice 1 donne $\frac{1024}{1024+820}\approx \mathrm{0,555}$, soit environ 55,5 % contre 44,5 %. Les parts dépendent approximativement de la différence entre les valeurs nice : $3121\mathrm{/}1024$ et $335\mathrm{/}110$ valent tous deux environ 3,05. Nice +19 en concurrence avec nice 0 reçoit tout de même environ 1,4 % dans ce modèle simple à deux tâches.

Le CFS classique répartit une latence d’ordonnancement cible selon les poids :

Pour les poids 1 024, 1 024 et 335, le total est de 2 383. Une période cible de 48 ms donne environ 20,63 ms à chacune des tâches de poids supérieur et 6,75 ms à celle de poids inférieur. Ces paramètres servent d’exemple et ne sont pas des valeurs par défaut universelles du noyau. Avec quatre tâches égales, 48 ms donnent 12 ms à chacune. Avec dix tâches, 4,8 ms chacune seraient inférieures à une granularité minimale de 6 ms prise comme exemple : la période doit donc augmenter.

Comptabiliser la progression virtuelle

CFS augmente le temps d’exécution virtuel d’une tâche en cours d’exécution de :

Une tâche de poids 1 024 gagne une milliseconde virtuelle par milliseconde réelle. Une tâche de poids 335 en gagne environ 3,06. Comptabiliser plus rapidement la progression des tâches de poids inférieur les fait attendre plus tôt, tandis que les tâches de poids supérieur reçoivent davantage de service réel.

Le CFS classique classe les tâches en file pouvant s’exécuter dans un arbre rouge-noir selon leur temps d’exécution virtuel. L’insertion et la suppression prennent un temps logarithmique ; un pointeur conservé vers le nœud le plus à gauche permet de trouver le minimum en temps constant. Les tâches bloquées quittent cet arbre. Le placement au réveil empêche qu’un ancien sommeil ne donne un droit illimité à du service de rattrapage.

Choisir parmi les tâches admissibles avec EEVDF

EEVDF conserve les poids et la comptabilisation du service virtuel. Une tâche a un retard de service positif lorsqu’elle doit encore recevoir du service et négatif lorsqu’elle en a reçu plus que son droit. Les tâches dont le retard de service est positif ou nul sont admissibles. EEVDF sélectionne la tâche admissible dont l’échéance virtuelle est la plus proche.

L’échéance combine le début virtuel d’une demande et la durée de service demandée, convertie en temps virtuel. C’est une valeur qui ordonne le service, pas une promesse d’instant de fin réel. Une tranche demandée plus courte peut donner à une tâche admissible une échéance plus proche et améliorer la latence sans augmenter sa part à long terme fondée sur son poids. Linux prend actuellement en charge les demandes de tranche par sched_setattr().

Plusieurs processeurs ne sont utiles que si du travail peut s’exécuter en parallèle. Un seul fil d’exécution s’exécute sur un processeur logique à la fois ; plusieurs fils ou programmes indépendants peuvent utiliser plusieurs processeurs simultanément. Un ordonnanceur doit choisir à la fois quelle tâche s’exécute et où elle s’exécute.

Partager la responsabilité de l’ordonnancement

Dans le multitraitement symétrique (SMP), les processeurs exécutent le code du noyau et prennent leurs propres décisions d’ordonnancement. Dans le multitraitement asymétrique, un processeur principal coordonne l’ordonnancement tandis que les autres exécutent le travail attribué. Le contrôle centralisé est plus simple, mais le processeur principal peut devenir un goulot d’étranglement. Les systèmes généralistes utilisent le SMP.

Les décisions simultanées exigent une coordination. Si deux processeurs retirent des tâches d’une file de tâches prêtes partagée, ses mises à jour doivent être synchronisées pour qu’aucune entrée ne soit perdue et qu’aucune tâche en file ne soit sélectionnée deux fois. Un plus grand nombre de processeurs peut accroître la contention sur cette structure partagée.

Préserver le contenu utile des caches

Les cœurs possèdent de petits caches rapides, généralement des caches L1 et L2 privés et un cache L3 plus grand partagé par plusieurs cœurs. La localité temporelle consiste à réutiliser des données consultées récemment. La localité spatiale consiste à accéder à des données proches, comme des éléments consécutifs d’un tableau.

Un fil d’exécution qui effectue un tri sur le cœur 0 remplit ses caches et son TLB. S’il y reprend après une brève préemption, de nombreuses entrées nécessaires peuvent encore être présentes. Sur le cœur 3, il peut devoir récupérer à nouveau les mêmes données dans un cache partagé ou en mémoire. L’affinité de cache est la tendance de l’ordonnanceur à maintenir un fil près du processeur qu’il a récemment utilisé. Le bénéfice exact dépend de ce qui reste en cache et de la topologie de partage des caches.

Distinguer cohérence et synchronisation

La cohérence des caches empêche les cœurs d’utiliser indéfiniment des copies en cache contradictoires d’un même emplacement mémoire. La surveillance du bus est une possibilité de mise en œuvre : les caches observent le trafic et invalident ou mettent à jour leurs copies lorsqu’un autre cœur écrit. Les systèmes plus grands peuvent utiliser d’autres mécanismes de cohérence.

La cohérence ne transforme pas plusieurs instructions en une seule opération atomique. Si deux processeurs lisent tous deux la longueur d’une file, modifient des entrées et réécrivent la longueur, la cohérence des lectures et écritures individuelles autorise tout de même des entrelacements nuisibles. L’ordonnanceur a besoin de verrous ou d’une autre méthode de synchronisation pour toute la mise à jour. La ligne de cache partagée d’un verrou peut elle-même passer d’un cœur à l’autre lorsqu’ils se la disputent.

Lire l’organisation du matériel

Intel appelle son implémentation du SMT Hyper-Threading. Deux fils d’exécution occupés sur des processeurs logiques d’un même cœur se disputent les ressources de ce cœur ; deux processeurs logiques ne sont pas équivalents à deux cœurs physiques indépendants. Une migration NUMA peut aussi éloigner un calcul de la mémoire qu’il utilise, même lorsque le remplissage des caches est bref.

Déplacer un fil vers un processeur inactif peut supprimer une longue attente en file. Le laisser en place peut préserver la localité. Compare ces coûts pour la charge de travail réelle : l’affinité est une préférence de performance, tandis qu’un masque d’affinité explicite restreint les processeurs autorisés.

Un ordonnanceur multiprocesseur doit disposer d’un endroit où conserver les tâches prêtes. Une file unique partagée permet de trouver facilement du travail. Des files distinctes par processeur réduisent la contention sur les ressources partagées et préservent le placement, mais peuvent laisser un processeur surchargé pendant qu’un autre est inactif.

Comparer les organisations des files

Dans l’ordonnancement multiprocesseur à file unique, tous les processeurs puisent dans une file partagée. Si les tâches peuvent s’exécuter sur tous les processeurs, le travail en attente occupe naturellement un processeur inactif. Un verrou partagé protège la file ; augmenter le nombre de processeurs peut donc faire de ce verrou un goulot d’étranglement.

Avec cinq tâches A–E à tour de rôle sur quatre processeurs, une séquence attribue A, B, C, D au premier tour ; E, A, B, C au deuxième ; et D, E, A, B au troisième. A s’exécute sur le processeur 0, puis 1, puis 2. La machine reste occupée, mais A change sans cesse de caches privés. Des règles d’affinité peuvent conserver la plupart des placements tout en déplaçant certaines tâches pour équilibrer le travail.

Repérer les parts inégales

Dans l’ordonnancement multiprocesseur à files multiples, chaque processeur ordonnance sa propre file. Supposons que le processeur 0 ait A et C et que le processeur 1 ait B et D, toutes limitées par le processeur et se partageant localement le temps à tour de rôle. Au départ, chaque tâche reçoit la moitié d’un processeur. Lorsque C se termine, A reçoit tout le processeur 0 tandis que B et D reçoivent toujours chacune la moitié du processeur 1.

La machine reste entièrement utilisée, mais les tâches ne reçoivent plus des parts égales. Si A se termine aussi, le processeur 0 devient inactif alors que B et D sont prêtes. Déplacer l’une d’elles vers le processeur 0 donne à chacune un processeur entier et utilise la capacité auparavant inactive.

Avec trois tâches égales limitées par le processeur et deux processeurs, un service égal à long terme correspond aux deux tiers d’un processeur par tâche. Un placement fixe laisse une tâche seule et deux autres se partager un processeur. Alterner périodiquement la tâche qui est seule peut approcher la répartition égale. Aucun fil d’exécution ne s’exécute sur les deux processeurs à la fois.

Décider quand migrer

La migration déplace une tâche vers la file d’un autre processeur. Le vol de travail est une stratégie où le processeur demandeur prend l’initiative : un processeur ayant peu de travail examine la file d’un processeur plus chargé et lui prend du travail. Des vérifications fréquentes créent du trafic de synchronisation ; des vérifications rares laissent le déséquilibre persister. Le vol doit aussi respecter les processeurs autorisés et la localité mémoire.

Compare le temps d’attente que l’on prévoit d’économiser au coût de migration. Une longue file sur un processeur et un processeur compatible inactif constituent une bonne raison de déplacer une tâche. Une petite différence temporaire entre les files peut disparaître avant que le coût des caches à remplir ne soit compensé.

Les conceptions O(1) et CFS de Linux utilisaient des files de tâches prêtes par processeur ; Linux équilibre la charge entre des domaines d’ordonnancement matériels en tenant compte des cœurs et des sockets partagés. L’ordonnanceur alternatif BF Scheduler utilisait une file unique. Les utilisateurs peuvent restreindre le placement avec taskset ou sched_setaffinity() sous Linux et SetThreadAffinityMask() sous Windows. Un masque d’affinité restrictif peut expliquer pourquoi une tâche prête n’utilise pas un processeur qui paraît inactif.

Linux ordonnance des fils d’exécution, appelés tâches dans le noyau. La politique d’ordonnancement, la valeur nice, les réglages de groupe et l’affinité processeur d’une tâche répondent à des questions différentes sur le moment et le lieu de son exécution.

Lire d’abord la politique

Les politiques normales ont la priorité statique 0. FIFO et RR temps réel utilisent les priorités 1–99, dont 99 est la plus élevée. Une tâche FIFO continue jusqu’à ce qu’elle se bloque, cède le processeur ou soit préemptée par une tâche plus prioritaire. RR ajoute des tours entre tâches de même priorité ; sched_rr_get_interval() indique son quantum. Ces noms désignent des politiques Linux : l’ordonnancement normal équitable n’est pas l’algorithme RR à tranches égales des manuels.

Modifier les parts et le placement

Nice va de −20 à +19, avec 0 par défaut. Les valeurs plus élevées réduisent le poids dans la classe équitable, d’un facteur d’environ 1,25 par échelon. Lors d’un lancement typique avec nice 0, nice -n 10 make démarre une compilation avec nice 10 ; -n est un ajustement de la valeur nice héritée. renice -n 5 -p 4321 fixe la valeur nice du processus cible à 5. Un utilisateur peut rendre son propre travail moins favorisé ; augmenter sa priorité exige un privilège adapté ou une limite de ressource qui l’autorise.

taskset -c 0,1 ./app autorise un programme à s’exécuter sur les processeurs 0 et 1. Cette commande ne crée pas de second fil d’exécution et ne garantit l’exclusivité d’aucun des deux processeurs. ps -o pid,cls,ni,rtprio,comm affiche les champs liés à la politique, tandis que top aide à observer la priorité, nice et la consommation de processeur.

chrt -f 50 ./app sélectionne la priorité temps réel FIFO 50. Utilise les réglages temps réel uniquement dans un environnement contrôlé : un fil d’exécution très prioritaire et occupé peut retarder l’interpréteur de commandes et des tâches système essentielles. Les limites de bande passante temps réel par défaut réservent du temps au travail normal, mais ne rendent pas toute charge de ce type réactive. La priorité modifie l’accès au service processeur, pas la vitesse d’une instruction.

Distinguer le poids de groupe du quota

Dans cgroup v2, cpu.weight va de 1 à 10 000, avec 100 par défaut, et répartit la capacité processeur disputée de la classe équitable entre les groupes actifs de même niveau. Des poids de 200 et 100 donnent environ deux tiers et un tiers d’un processeur lorsque les deux groupes sont occupés. Si le second devient inactif, le premier peut utiliser toute la capacité disponible.

cpu.max fixe un plafond de bande passante. La valeur « 50000 100000 » autorise 50 ms de temps processeur cumulé par période de 100 ms, soit en moyenne l’équivalent de la moitié d’un processeur. Plusieurs fils d’exécution peuvent consommer ce budget en parallèle et l’épuiser plus tôt en temps écoulé. Un groupe plafonné peut voir son débit limité même lorsqu’il reste de la capacité processeur libre.

Situer les noms dans l’histoire

L’ordonnanceur O(1) de Linux 2.6.0 utilisait des tableaux de priorités et une rétroaction sur l’interactivité. CFS est arrivé dans la version 2.6.23 en 2007. Linux 6.6 a commencé en 2023 la transition vers la sélection EEVDF dans la classe équitable. Depuis Linux 6.12 en 2024, sched_ext prend en charge des politiques d’ordonnancement BPF chargées dynamiquement sur les noyaux configurés à cet effet. Si un tel ordonnanceur échoue ou empêche des tâches prêtes de progresser, le noyau rétablit l’ordonnancement intégré.

Windows ordonnance les fils d’exécution prêts selon une priorité allant de 0 à 31, les plus grands nombres étant les plus prioritaires. Les fils prêts de même priorité passent à tour de rôle. Un fil plus prioritaire qui devient prêt préempte un fil moins prioritaire sans attendre la fin de son quantum. La priorité 0 appartient au fil de mise à zéro des pages, qui efface les pages libres.

Trouver la priorité de base à partir de deux paramètres

La priorité de base d’un fil d’exécution dépend de la classe de priorité de son processus et de son propre niveau relatif. Les classes de processus sont Idle, Below normal, Normal, Above normal, High et Realtime. Les niveaux de fil comprennent Idle, Lowest, Below normal, Normal, Above normal, Highest et Time critical.

Time critical donne 15 hors de la classe Realtime et 31 dans celle-ci. Le niveau de fil Idle donne 1 hors de Realtime et 16 dans cette classe. Ces niveaux extrêmes sont des entrées particulières de la table : ajouter un décalage fixe à chaque classe donnerait donc des résultats erronés.

Suivre un relèvement temporaire

Les priorités 1–15 constituent la plage variable ; les priorités 16–31 constituent la plage temps réel. Un fil d’exécution commence avec une priorité dynamique égale à sa priorité de base. Pour les fils de la plage variable, des événements comme une entrée ou la fin d’une attente peuvent relever temporairement la priorité dynamique. Les fils dont la priorité de base est temps réel ne reçoivent pas ces relèvements.

Supposons qu’un fil de priorité de base 8 soit remonté à 14. S’il continue à calculer, sa priorité dynamique baisse d’un niveau après chaque quantum complet : 13 après le premier, 12 après le deuxième et 8 après le sixième. Le relèvement ne modifie pas définitivement la priorité de base et ne descend pas sous celle-ci.

C’est une rétroaction : le travail récemment débloqué reçoit rapidement du service, tandis qu’une utilisation soutenue du processeur perd l’avantage temporaire. Windows utilise aussi des relèvements temporaires pour les fils prêts qui attendent depuis longtemps afin de lutter contre la famine. Un tel relèvement peut aider le détenteur peu prioritaire d’un verrou à progresser, mais c’est un mécanisme différent de l’héritage de priorité propre à un verrou.

Reconnaître des conceptions apparentées

La classe de partage du temps de Solaris est une conception MLFQ pilotée par une table. ULE de FreeBSD utilise des files de tâches prêtes par processeur et compare les comportements de sommeil et d’exécution pour identifier les fils interactifs. Ces systèmes partagent l’idée d’adapter le service au comportement observé sans utiliser des règles de files identiques.

macOS propose des classes de qualité de service (QoS), notamment interactif pour l’utilisateur, lancé par l’utilisateur, par défaut, utilitaire et arrière-plan. Elles décrivent l’urgence du travail. Sur les puces Apple, la QoS aide le système à répartir le travail entre cœurs performants et économes. Les programmes communiquent l’importance du travail ; le système d’exploitation choisit son placement selon la politique et le matériel disponible.

Les ordonnanceurs existants combinent rétroaction, priorités, équité et affinité. La classe Realtime de Windows donne une priorité de passage supérieure, mais ne garantit ni un calcul plus rapide ni une correction complète en temps réel.

Choisis l’objectif de la charge de travail avant de choisir un ordonnanceur. Une file de tâches par lots peut privilégier la fin rapide de nombreuses petites tâches. Un éditeur a besoin d’un service rapide après une saisie. Un serveur partagé a besoin d’une répartition justifiable entre utilisateurs ou groupes.

Adapter le mécanisme à l’objectif

Comparer les politiques sur des données identiques

A arrive à 0 ms et demande 8 ms, B arrive à 1 ms et demande 4 ms, et C arrive à 2 ms et demande 2 ms. Ignore le coût des commutations. FIFO exécute A, B, C. SJF commence aussi par A, mais exécute ensuite C avant B. STCF exécute A 0–1, B 1–2, C 2–4, B 4–7, A 7–14. RR utilise un quantum de 2 ms et place les tâches arrivant à la fin d’une tranche dans la file avant la tâche dont la tranche a expiré.

STCF l’emporte sur les deux indicateurs pour cette charge de travail, car chaque nouvelle tâche plus courte s’exécute immédiatement à son arrivée. RR offre un démarrage rapide sans connaître les durées des rafales. Lorsque des tâches de même durée arrivent simultanément, FIFO peut avoir un temps de séjour moyen inférieur à celui de RR. Un classement sur une charge de travail renseigne sur cette charge.

Choisir une méthode d’évaluation

La modélisation déterministe calcule à la main un déroulement fixe. Elle donne des résultats exacts pour ses données et facilite l’examen des décisions, mais omet souvent les coûts de répartition et de cache. Les modèles de files d’attente décrivent les arrivées et les services à l’aide de distributions et prédisent le comportement moyen.

Pour un système stable en régime permanent, la loi de Little relie le nombre moyen de tâches $n$, le taux d’arrivée $\lambda$ et le temps moyen de séjour $W$ :

Avec 14 tâches/s et un temps moyen de 0,5 s dans le système, le nombre moyen est de 7 tâches. Garde un périmètre cohérent : le nombre de tâches dans la file des tâches prêtes nécessite le temps d’attente dans cette file, tandis que le nombre de tâches dans tout le système nécessite le temps passé dans l’ensemble du système. Convertis les unités avant de multiplier.

La simulation exécute un modèle de l’ordonnanceur, souvent sur une trace de charge de travail enregistrée. Elle peut tester des arrivées et des blocages complexes, mais ses conclusions dépendent du modèle et des traces choisies. La mise en œuvre mesure l’ordonnanceur dans un véritable système d’exploitation et inclut le surcoût réel ; elle demande davantage d’efforts et nécessite toujours des charges représentatives et des mesures reproductibles.

Examine le débit, le taux d’utilisation, les délais individuels et en queue de distribution, l’équité et la consommation d’énergie en plus des moyennes. Sur un multiprocesseur, une machine occupée peut tout de même répartir inégalement le service ou perdre du temps à remplir de nouveau les caches. Compare les politiques sur la même fenêtre d’observation et la même charge de travail, puis fais varier les caractéristiques de la charge qui comptent pour les utilisateurs concernés.