#Ordonnancement des processus et des threadsCopier le lien

Prérequis

• Chapitre Processus: états, préemption, quantum.
• Chapitre Synchronisation: verrous et interaction avec l'attente.

Objectifs d'apprentissage

• Énoncer les critères d'une politique (réactivité, débit, équité) et leurs tensions.
• Expliquer le principe du CFS de Linux et la place du temps réel.
• Diagnostiquer une inversion de priorité et connaître les remèdes.

Le processeur est une ressource finie: un seul fil d'exécution peut avancer par cœur à un instant donné. L'ordonnancement est l'art de partager ce temps de calcul entre toutes les tâches qui le réclament. En pratique, c'est une machine à compromis: améliorer un critère en dégrade presque toujours un autre.

#0. Le temps partagé, tel que le cours le poseCopier le lien

L'ordonnancement naît d'une décision historique. Avant 1960, l'utilisation d'un ordinateur était individuelle et interactive: la machine était réservée pour une certaine durée, l'utilisateur essayait, réparait, réfléchissait — et l'ordinateur passait l'essentiel de son temps inactif. Le traitement par lots du début des années 1960 a amélioré l'utilisation du temps machine, mais au prix de l'interactivité: plus de connexion directe, des travaux enchaînés en différé.

La réintroduction de l'interactivité, vers la fin des années 1960, s'est faite par deux mécanismes indissociables: l'accès multiple, qui permet à plusieurs utilisateurs d'être connectés en même temps sur la même machine, et le temps partagé, qui découpe le temps du processeur en périodes très courtes réparties entre les utilisateurs. C'est exactement la définition d'un ordonnanceur préemptif, énoncée quarante ans avant que le mot ne soit à la mode.

Trois conséquences structurent tout le chapitre.

Un seul processus s'exécute à la fois. Le cours le dit sans détour dans sa liste d'états: un processus peut être « en exécution — un seul à la fois ». Tous les autres sont soit en attente d'un événement extérieur, soit en attente d'exécution, c'est-à-dire d'une tranche de temps, soit en attente de l'arrivée d'une partie de la mémoire virtuelle. Ordonnancer, c'est choisir lequel passe de l'attente à l'exécution.

L'illusion de la simultanéité. Le cours explique que « tout se passe comme s'ils s'exécutaient simultanément »: je compile un programme, je reçois du courrier, mon voisin exécute un programme sur ma machine. L'illusion tient à la finesse du découpage, pas à une parallélisme réel.

La charge moyenne. Le seul indicateur d'ordonnancement que le cours nomme est celui d'uptime: la charge moyenne, définie comme la longueur de la file d'attente pour exécution, moyennée sur la dernière minute, les 5 et les 15 dernières minutes. C'est l'observation directe de l'état « en attente d'exécution »: une charge durablement supérieure au nombre de cœurs signifie que des processus font la queue plus longtemps qu'ils ne s'exécutent.

1uptime              # charge moyenne sur 1, 5 et 15 minutes2top                 # la même ligne en tête d'écran, plus le détail par processus

#1. Objectifs et métriquesCopier le lien

Une politique d'ordonnancement juge ses choix à l'aune de plusieurs critères: la réactivité (temps de réponse moyen pour une requête interactive), le débit (nombre de tâches terminées par unité de temps), l'équité (ne pas affamer une tâche), la prédictibilité (respect des contraintes temps réel). Selon la charge du système, ces objectifs entrent en tension: réduire le temps de réponse des tâches courtes retarde mécaniquement les longues; maximiser le débit brut défavorise l'interactif. Les métriques usuelles pour départager une politique: temps de réponse, temps d'attente, temps de séjour (turnaround), débit.

#2. Algorithmes classiques et CFSCopier le lien

Les premiers OS utilisaient des stratégies simples comme le round-robin (quantum fixe tournant) ou les files multi-niveaux à retour d'information (multilevel feedback: une tâche qui épuise son quantum descend d'un niveau; une tâche qui se bloque vite sur des entrées-sorties remonte, car elle laisse la place). Linux a adopté le Completely Fair Scheduler (CFS), qui modélise le CPU comme une ressource à partager proportionnellement au poids de chaque tâche (le poids vient de la nice value). CFS maintient un arbre rouge-noir trié par temps virtuel; à chaque décision, il choisit la tâche ayant accumulé le moins de temps virtuel, ce qui revient à égaliser l'usage du CPU sans quantum explicite. Depuis les noyaux récents, EEVDF remplace progressivement CFS sur Linux; le principe de pondération et de temps virtuel demeure.

L'observation directe existe:

1ps -o pid,ni,comm        # nice value de vos processus (ni)2cat /proc/<pid>/sched    # compteurs, temps virtuel, politique (policy)3chrt -p <pid>            # politique d'ordonnancement effective

Les tâches temps réel utilisent des politiques différentes (SCHED_FIFO, SCHED_RR) qui respectent strictement les priorités, au risque de bloquer indéfiniment les tâches moins prioritaires si une tâche temps réel boucle sans se bloquer. D'où la discipline: réserver ces politiques à ce qui en vaut vraiment la peine.

#3. Threads, affinité et inversion de prioritéCopier le lien

Les threads d'un même processus partagent la mémoire et les descripteurs. Pour profiter du parallélisme, le noyau doit décider sur quel cœur exécuter chaque thread. L'affinité CPU (fixer un thread à un cœur) peut améliorer la localisation des caches, mais limite la flexibilité (taskset -c 0 cmd pour l'observer).

Les systèmes multi-cœurs exposent des phénomènes comme l'inversion de priorité: un thread basse priorité détient un verrou dont a besoin un thread haute priorité, et l'arrivée d'une tâche de priorité moyenne (qui préempte la basse sans être bloquée par le verrou) retarde la libération. La conséquence visible: la haute priorité attend un verrou détenu par un thread qu'elle pourrait préempter, paradoxe apparent. L'anecdote fondatrice reste Mars Pathfinder (1997), replantée par une inversion exactement de ce type, corrigée à distance par l'activation de l'héritage de priorité. Les protocoles d'héritage de priorité permettent d'éviter ces situations en élevant temporairement la priorité du détenteur du verrou jusqu'à sa libération.

#AtelierCopier le lien

Banc d'essai à trois fils (pthreads):

1. un fil interactif qui alterne courts calculs et courtes pauses,
2. un fil de calcul intensif (CPU-bound), sans pause,
3. un fil qui détient un mutex convoité par le fil interactif.

Observations à relever: temps de réponse du fil interactif selon que le CPU-bound tourne ou non (comparez avec chrt entre SCHED_OTHER et SCHED_FIFO, et avec nice). Puis provoquez l'inversion: le fil basse priorité tient le verrou longuement, un fil moyenne priorité sature le CPU, et le fil haute priorité attend. Avec perf sched record/perf sched latency (ou la sortie de pidstat -wt 1), visualisez qui attend et qui tourne. Enfin, laissez le noyau appliquer l'héritage (mutex robuste/PI, PTHREAD_PRIO_INHERIT) et observez la reprise de l'exécution haute priorité.

Simulation sans écriture de code: le module Systèmes d'exploitation propose les démonstrateurs MLFQ et file prête qui permettent de rejouer ces politiques pas à pas.

#ExercicesCopier le lien

1. D'où vient historiquement le temps partagé? Quels deux mécanismes l'ont rendu possible, et quel compromis le traitement par lots avait-il imposé?

2. Combien de processus s'exécutent simultanément sur un cœur? Dans quel état sont les autres?

3. Que désigne la charge moyenne affichée par uptime? Que signifie une charge de 4.00 sur une machine à 4 cœurs, et sur une machine à 1 cœur?

4. Que désigne l'état « en attente d'exécution » dans la liste d'états du cours, et en quoi diffère-t-il de « en attente d'un événement extérieur »?

5. Le cours affirme que « tout se passe comme s'ils s'exécutaient simultanément ». Sur quoi repose cette illusion?