L’ordonnanceur d’un système d’exploitation est une partie cruciale pour la performance. Il décide de l’affectation des fils d’exécution aux différents cÅ“urs et processeurs d’une machine afin d’utiliser au mieux la machine à disposition, tout en garantissant une certaine réactivité pour les applications qui en ont besoin (notamment les interfaces graphiques : elles ne peuvent pas rester plusieurs minutes sans pouvoir exécuter la moindre instruction, car elles ne peuvent alors pas répondre aux stimuli de l’utilisateur, qui a alors toutes les raisons de râler).

Il y a de cela une quinzaine d’années, Linus Torvalds déclarait, en somme, que l’ordonnancement était un problème très facile et qu’il était déjà très bien résolu dans le noyau Linux depuis dix ans (c’est-à-dire depuis les toutes premières versions du noyau) : inutile d’en discuter, tout fonctionne pour le mieux, tout va très bien, madame la marquise. Linus Torvalds estime même que l’extrapolation de ces techniques aux cas de machines à plusieurs processeurs est « trivial » : une logique de répartition de la charge entre les différents processeurs ne devrait représenter que quelques centaines de lignes de code, que les développeurs « ne devraient pas trop merder », selon ses termes.

Cependant, avec l’avènement de machines avec de plus en plus de cÅ“urs pour le plus grand nombre, l’ordonnancement s’est alors révélé bien plus compliqué que dans le cas à un seul processeur et cÅ“ur par machine. En effet, les taux d’utilisation du processeur restent très élevés, tout semble se passer pour le mieux… sauf que certains cÅ“urs restent inutilisés par moments. Au niveau technique, cet ordonnancement reste très similaire à celui pratiqué au début des années 1990, à la différence de la répartition de la charge : régulièrement, le noyau répartit à nouveau les tâches à effectuer sur les différents cÅ“urs, chacun suivant alors une politique équitable entre les tâches (selon l’algorithme CFS, completely fair scheduler).

Une équipe de chercheurs a remarqué des déficiences majeures du côté de l’ordonnanceur en tentant d’expliquer certaines dégradations importantes de performance en laissant le noyau Linux gérer lui-même l’affinité des processus par rapport aux cÅ“urs, plutôt qu’en les assignant manuellement aux cÅ“urs disponibles. De fil en aiguille, ils ont éliminé les causes les plus probables, comme une mauvaise localité en mémoire, des contentieux à l’accès à une ressource partagée ou les changements de contexte. Ils en sont venus à suspecter l’ordonnanceur du noyau. Pour récupérer des informations suffisantes, ils ont développé des outils de suivi à très haute résolution pour caractériser la répartition des tâches aux différents cÅ“urs et processeurs d’une machine de test. Le résultat était sans appel : certains processeurs étaient surchargés, d’autres presque complètement désÅ“uvrés, selon des motifs étranges et difficiles à expliquer rationnellement.

Par la suite, l’équipe a cherché dans le code source du noyau les parties à incriminer, elle a trouvé un premier défaut dans le code de l’ordonnanceur CFS : les chercheurs sont alors partis dans l’exploration plus approfondie du code. Ils ont fini par trouver quatre défauts majeurs dans le code : une fois analysés et corrigés (les patchs sont disponibles sur leur site pour le noyau en version 4.1, ils ne sont pas encore intégré dans Linux), le test de performance de bases de données TPC-H a vu une amélioration de douze à vingt-trois pour cent, le plus flagrant étant probablement une amélioration d’un facteur de cent trente-sept dans certaines charges de type HPC !

Ce travail de détection et de correction doit être très fin, car les techniques conventionnelles de test et de débogage sont totalement inefficaces pour comprendre ce genre de défauts : les symptômes sont très évasifs (les épisodes problématiques sont assez fréquents, mais chacun dure au plus quelques centaines de millisecondes), il est impossible de distinguer un véritable problème du bruit de fond dans un outil comme htop.

En réalité, les problèmes se situent principalement au niveau des heuristiques de CFS : pour éviter des calculs très lourds et de la communication (forcément lente) entre les différents processeurs, certaines données sont approchées à l’aide d’heuristiques (principalement, la charge de chaque cÅ“ur et processeur). Cependant, leur impact n’a pas toujours été analysé en profondeur, ce qui laisse une grande marge d’améliorations à ce niveau.

Cet article tire plusieurs conclusions, la première étant que Linus Torvalds est très loin de détenir la vérité quant aux résultats des ordonnanceurs : non, ce n’est pas un problème résolu, il faudra encore pas mal de recherche à ce niveau pour exploiter au mieux le matériel disponible (et éviter de laisser des cÅ“urs totalement inoccupés). Les correctifs proposés par les chercheurs ne résolvent que les problèmes qu’ils ont remarqués : ils ne prétendent pas donner des solutions génériques à tous les problèmes, ils n’ont pas poussé les tests jusqu’à déterminer l’impact sur d’autres types de charges.

L’objectif est atteint : les ordonnanceurs doivent encore évoluer.

Source : The Linux Scheduler: a Decade of Wasted Cores (présentations courte et longue).