Completely Fair Queuing
# Completely Fair Queuing

Le Completely Fair Queuing (« file d'attente complètement équitable » en anglais), ou CFQ, est un ordonnanceur de tâches d'E/S pour le noyau Linux et écrit par Jens Axboe.

CFQ fonctionne en plaçant les requêtes synchrones soumises par les processus dans des files d'attente dédiées (une file par processus), et en allouant des tranches de temps processeur à chaque file pour accéder au disque dur. La taille de la tranche de temps processeur et le nombre de requêtes qu'une file peut soumettre en une seule fois dépend de la priorité d'entrée/sortie assignée au processus correspondant. Les requêtes asynchrones de tous les processus sont regroupées dans un nombre plus restreint de files, une par priorité. Bien que CFQ ne fasse pas à proprement parler de l'ordonnancement anticipé, il fournit le même service, à savoir d'obtenir un bon taux d'échange global avec la mémoire de masse pour l'ensemble du système, en permettant à une file processus de se mettre en attente à la fin d'une opération d'E/S synchrone, après avoir anticipé sur les prochaines opérations d'entrées/sorties de ce processus. CFQ peut-être considéré comme un moyen naturel d'allouer aux processus des tranches de temps processeur dédiées aux E/S .

## Histoire

* En février 2003, Andrea Arcangeli propose son idée d'ordonnanceur d'E/S équitable non-déterministe à Jens Axboe qui l'implémente alors. Jens Axboe apporte de nombreuses améliorations à sa première implémentation, renomme pour l'occasion son ordonnanceur CFQ et propose un patch pour l'ajouter au noyau 2.5.60 de la branche de développement.
* Le 10 mai 2004, CFQ est intégré dans la branche principale du noyau 2.6.6 comme ordonnanceur optionnel, qu'il est possible de sélectionner au démarrage avec le paramètre 'elevator' du noyau.
* Le 19 octobre 2004, Red Hat Enterprise Linux 4, incluant alors un noyau 2.6.9, utilise CFQ par défaut.
* Le 24 décembre 2004, la seconde version de CFQ estampillée CFQv2 est incluse dans le noyau 2.6.10. Les améliorations incluent une meilleure réactivité de l'ordonnanceur ainsi que l'élimination de certains problèmes d'alimentation de celui-ci. L'ordonnanceur peut maintenant être changé pendant l'exécution du système, en modifiant la variable du noyau /sys/block/périphérique_de_type_bloc/queue/scheduler dans le système de fichiers sysfs.
* Le 20 septembre 2006, CFQ devient l'ordonnanceur d'E/S par défaut du noyau 2.6.18.

## Autres ordonnancements d'E/S

* Anticipatory scheduling
* Deadline scheduler
* Noop scheduler

## Sources

* (en) Short detail about CFQ
* (en) RedHat CFQ information
* (en) Coming in 2.6.10
