Completely Fair Scheduler

Le Completely Fair Scheduler (ordonnanceur complètement équitable en Français), ou CFS est un ordonnanceur de tâches pour le noyau Linux, qui a fait son apparition avec la version 2.6.23 sortie le 9 octobre 2007, remplaçant ainsi le précédent ordonnanceur qui était apparu dans le noyau 2.5.2-pre10 en janvier 2002.

Il gère l'allocation de ressource processeur pour l'exécution des processus, en maximisant l'utilisation globale du CPU tout en optimisant l'interactivité. Il a été écrit par Ingo Molnár.

Fonctionnement

Contrairement au précédent ordonnanceur utilisé par le noyau Linux, CFS n'est pas basé sur des files de processus, mais utilise un arbre rouge-noir implémentant une chronologie des futures exécutions des tâches. En effet, l'arbre trie les processus selon une valeur représentative du manque de ces processus en temps d'allocation du processeur, par rapport au temps qu'aurait alloué un processeur dit multitâche idéal, sur lequel tous les processus s'exécuteraient en même temps et à la même vitesse. Ainsi, à chaque intervention de l'ordonnanceur, il "suffit" à ce dernier de choisir le processus le plus en manque de temps d'exécution pour tendre au mieux vers le comportement du processeur multitâche idéal. De plus, l'ordonnanceur utilise une granularité temporelle à la nanoseconde, rendant redondante la notion de tranches de temps, les unités atomiques utilisées pour le partage du CPU entre processus. Cette connaissance précise signifie également qu'aucune heuristique (basée sur des statistiques, donc pouvant commettre des erreurs) n'est requise pour déterminer l'interactivité d'un processus.

Voir aussi

• Ordonnancement dans les systèmes d'exploitation
• Noyau de système d'exploitation
• Staircase Deadline Scheduler

Notes

Liens externes

• Article sur l'évolution de l'ordonnanceur CFS dans le noyau 2.6.38