Ordonnancement des processus et des threads
Progression
#Ordonnancement des processus et des threads
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.
#1. Objectifs et métriques
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, et le noyau doit arbitrer.
#2. Algorithmes classiques et CFS
Les premiers OS utilisaient des stratégies simples comme le round-robin (quantum fixe tournant) ou les files multilevel feedback (les tâches interactives remontent dans la pile de priorité). Linux a adopté le Completely Fair Scheduler (CFS), qui modélise le CPU comme une ressource à partager proportionnellement au poids de chaque tâche. CFS maintient un arbre rouge-noir trié par temps virtuel ; à chaque tick, il choisit la tâche ayant accumulé le moins de temps virtuel, ce qui revient à égaliser l'usage du CPU. 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 les tâches moins importantes.
#3. Threads, affinité et inversion de priorité
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é. Les systèmes multicœ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 bloque la libération. Les protocoles d'héritage de priorité permettent d'éviter ces situations en élevant temporairement la priorité du détenteur du verrou.
#Atelier
Élaborez un banc d'essai avec trois threads : un interactif qui réalise de petites tâches, un calculant intensivement et un troisième qui détient un mutex convoité. Observez, à l'aide de chrt et de perf sched, comment le système réagit lorsque vous changez la politique (SCHED_OTHER, SCHED_FIFO) et le quantum. Analysez ensuite la trace pour voir comment l'inversion de priorité se manifeste et comment l'héritage corrige la situation.