Un système d’exploitation est constitué d’une myriade de parties, tel un orchestre jouant une symphonie : chaque instrument doit jouer sa partition exactement (et en synchronie), sans quoi l’orchestre ne produit qu’une infâme cacophonie. Certains composants sont essentiels, même s’ils ne sont pas utilisés en permanence : d’un certain point de vue, l’ordonnanceur d’un système d’exploitation peut se comparer à un triangle. Certes, ce n’est pas l’instrument le plus compliqué à jouer (selon Linus Torvalds), mais, sans lui, la symphonie tombe à plat.
Plus précisément, l’ordonnanceur est la partie du noyau du système d’exploitation qui détermine qui aura droit à s’exécuter sur un cœur à un moment donné. Il est exécuté dans deux occasions particulières :
- lorsqu’un processus fait appel au noyau (un appel système, par exemple pour demander l’exécution d’une opération d’entrée-sortie : celle-ci prend du temps, le processus est mis en pause le temps qu’elle soit terminée) ;
- au moment d’une interruption lancée au niveau matériel (en particulier, des interruptions sont lancées à intervalle régulier, pour s’assurer qu’aucun processus n’utilise l’intégralité d’un cœur sans laisser de miette aux autres).
Cet ordonnanceur joue donc un rôle fondamental dans la performance d’un système où plusieurs processus doivent fonctionner simultanément. Les jeux, en particulier, peuvent bénéficier d’améliorations à ce niveau : l’ordonnanceur peut en général prendre en compte des priorités pour chaque processus. (Par exemple, c’est ce que fait Windows 10 quand il détecte un jeu, avec son mode jeu.) Justement, pour le moment, la communauté Linux discute d’un nouvel algorithme d’ordonnancement, MuQSS. Celui-ci est prévu pour être relativement léger (un ordonnanceur doit s’exécuter très vite !), mais pour gérer un très grand nombre de cœurs.
Malte Skarupke est développeur de jeux : professionnellement, il développe des intelligences artificielles chez Avalanche (à l’origine de jeux come Rage 2) ; il adore aussi améliorer les temps d’exécution des algorithmes (notamment avec des tables de hachage). Lors du portage de Rage 2 sur Stadia, la plateforme de jeu exécutée dans le nuage, les développeurs ont remarqué une série de blocages qu’ils avaient du mal à régler. Malte Skarupke a fait partie de ceux qui ont analysé la situation (il a participé à l’écriture du code incriminé dans ces blocages) et en a fait un compte-rendu assez exhaustif. Sa conclusion ? L’ordonnanceur actuel de Linux n’est pas génial, MuQSS améliore un peu la situation, mais ils ne sont pas au niveau de l’ordonnanceur de Windows : personne n’a encore trouvé d’algorithme d’ordonnancement parfait.
Le problème vient de certains mécanismes de synchronisation entre tâches (un processeur pouvant contenir une grande série de tâches, mais rien n’oblige une tâche à se synchroniser uniquement avec d’autres du même processus). La théorie fournit une série d’outils pour cette synchronisation : des barrières de synchronisation (souvent utilisées sur GPU), des sémaphores, des verrous tournants, des primitives d’exclusion mutuelle et d’autres encore. Pour les besoins du portage vers Stadia, deux étaient plus appropriées que les autres :
- les verrous actifs : une variable indique si une tâche est en train de s’exécuter (par exemple, la variable vaut 1) ou non (0). Ensuite, chaque tâche vérifie régulièrement si cette variable change de valeur : dès qu’elle passe à zéro, une tâche peut commencer à s’exécuter. Pour ce faire, elle utilise une instruction spécifique du processeur : souvent nommée test-and-set , elle s’exécute de manière atomique et vérifie si la variable en question a une valeur donnée ; si oui, elle est écrasée ; sinon, rien ne se fait. Le principe de cette instruction atomique est que la lecture et l’écriture pour cette valeur se font sans qu’aucune interférence ne puisse avoir lieu, ce qui évite bon nombre de problèmes de synchronisation. Le problème principal d’un verrou actif est que chaque tâche doit vérifier, en permanence, si le verrou est disponible (dans une boucle infinie tant qu’il est indisponible) : cela pompe énormément de ressources de calcul et n’a de sens que dans certains contextes particuliers (notamment en temps réel, puisqu’on n’a pas forcément le temps de rendre l’exécution au noyau : un changement de contexte prend beaucoup de temps) ;
- les verrous std::mutex de C++, qui se comportent comme des sémaphores ou d’autres primitives : la principale différence avec les verrous actifs est que, si le verrou n’est pas disponible, la tâche est mise en pause par le noyau. L’exécution reprend donc sur une autre tâche, celle qui vient d’être bloquée reviendra sur le devant de la scène plus tard. S’il n’y a aucune raison d’avoir des contraintes fortes en temps (comme une exécution en temps réel), ce système permet une très bonne utilisation des ressources de la machine.
Le problème de Stadia, c’est que Google vise à proposer, pour ceux qui ont une connexion à Internet suffisamment véloce (bande passante élevée et latence faible — la précision est importante, ici), des jeux à soixante images par seconde, pour une fluidité impeccable. Or, cela ne laisse que seize millisecondes et des poussières pour effectuer tous les calculs pour une image. Si le jeu est bloqué une fraction de milliseconde à chaque image pour des problèmes d’acquisition de verrou, ça passe encore. S’il l’est plus d’une milliseconde, des problèmes commencent à apparaître. C’est pour ça que les développeurs de Rage 2 ont commencé à utiliser des verrous actifs pour Stadia : ils n’ont pas vraiment de temps à perdre pour acquérir un verrou. Sauf que cette implémentation a fait en sorte que toutes les tâches étaient bloquées !
Le problème principal est que les primitives de synchronisation voient leur performance testée en nombre total d’acquisition par secondes. Ce qui importe aux développeurs, ici, c’est le temps nécessaire à l’acquisition d’un verrou, c’est-à-dire la latence. Une implémentation équitable des verrous actifs (ticket_spinlock dans le tableau ci-dessous, qui rend l’exécution au système d’exploitation s’il n’arrive pas à prendre le contrôle du verrou assez — rendre l’exécution prend à peine cent cinquante nanosecondes) prend bien plus longtemps que d’autres implémentations (même plus qu’un std::mutex), mais force la tâche à attendre un temps relativement constant. La milliseconde et demie s’explique par le fait que l’ordonnanceur de base de Linux donne le droit d’utiliser un cœur par tranche d’une milliseconde et demie.
Sauf que ces attentes ne sont pas vraiment le problème pour Rage 2 sur Stadia ! Leur situation est plus difficile à mesurer : dans les cas où le verrou est disponible, il s’agit de compter le temps où ce verrou reste disponible, mais où personne ne s’en saisit. Les mesures changent assez drastiquement : ce temps est assez limité… avec des valeurs très élevées qui apparaissent. Les écarts sont bien plus limités pour std::mutex : c’est pour cela que l’utiliser a pu améliorer les résultats du jeu, contre-intuitivement.
En lançant le même test sur Linux, mais avec d’autres algorithmes d’ordonnancement, les résultats ne varient pas énormément : Linux garde son retard sur Windows sur ce point. Ce phénomène se remarque en pratique : quand tous les cœurs sont utilisés et que l’utilisateur joue un fichier audio, Windows n’aura aucune coupure, contrairement à Linux, dans bien des cas. Bien évidemment, ces résultats n’ont pas de valeur scientifique à proprement parler, vu qu’ils n’ont pas été reproduits sur d’autres machines que celle du développeur, mais donnent déjà de la matière à digérer pour le développement d’une nouvelle génération d’algorithmes d’ordonnancement.
Bien plus de détails (dont les détails des mesures et les résultats complets) : Measuring Mutexes, Spinlocks and how Bad the Linux Scheduler Really is.