Vous êtes nouveau sur Developpez.com ? Créez votre compte ou connectez-vous afin de pouvoir participer !

Vous devez avoir un compte Developpez.com et être connecté pour pouvoir participer aux discussions.

Vous n'avez pas encore de compte Developpez.com ? Créez-en un en quelques instants, c'est entièrement gratuit !

Si vous disposez déjà d'un compte et qu'il est bien activé, connectez-vous à l'aide du formulaire ci-dessous.

Identifiez-vous
Identifiant
Mot de passe
Mot de passe oublié ?
Créer un compte

L'inscription est gratuite et ne vous prendra que quelques instants !

Je m'inscris !

À quel point l'ordonnanceur de Linux pose-t-il problème aux jeux ?
Pour certains développeurs de jeux, l'ordonnanceur actuel de Linux n'est pas génial.

Le , par dourouc05

177PARTAGES

19  0 
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.



Le même test sous Windows donne des résultats bien meilleurs, jusque deux ordres de grandeur pour le même code :



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.

Code des mesures.

Une erreur dans cette actualité ? Signalez-le nous !

Avatar de Darktib
Membre confirmé https://www.developpez.com
Le 05/01/2020 à 18:12
Pour information, le blog post de Malte Skarupke est à prendre avec des pincettes, il a fait l'objet d'une réponse de Linus Torvalds lui-même : https://www.realworldtech.com/forum/...rpostid=189723
Suivi d'une réponse de Malte : https://www.realworldtech.com/forum/...rpostid=189747
Puis encore de Linus : https://www.realworldtech.com/forum/...rpostid=189752

En gros : n'utilisez jamais de spin locks ni de yield(), les deux pour la même raison de fond : le noyau n'est pas au courant de pourquoi attendre ou pourquoi redonner la main, et du coup le comportement du système est erratique au mieux, car le noyau doit, d'une certaine manière, deviner ce que le développeur voulait faire...
10  0 
Avatar de transgohan
Expert éminent https://www.developpez.com
Le 06/01/2020 à 13:39
Effectivement il ne semble pas comprendre ce qu'il utilise...
Prendre la fonction qui prend le moins de temps n'est pas une réponse censée, et c'est confirmé dans son cas par Linus Torvald (toujours aussi hargneux dans ses propos d'ailleurs à ce que je lis...).

Faire tourner des jeux sur un RTOS pour palier au maximum à ce genre de souci ?
5  0 
Avatar de LittleWhite
Responsable 2D/3D/Jeux https://www.developpez.com
Le 04/01/2020 à 15:22
Par exemple, je ne rencontre pas du tout les problèmes de xarkam (ni avec le NAS utilisé dans ce test (je ne pourrais pas tester une nouvelle fois)), ni avec un lecteur vidéo (ni audio). De même d'un transfert d'un RPi en SSH à un PC, je suis full speed de mon réseau.
Les coupures peuvent aussi bien arriver sous Windows, notamment avec VLC (comme un ami a pu le remarqué).
D'ailleurs, avec VLC, il y a plein d'options et plus précisément, celles du matériel utilisé pour le décodage de la vidéo, qui sont à inspecter.

En bref, ce que j'aime, c'est que sous Linux, il y a une chance de pouvoir inspecter en détail où cela coince (on a/on peut avoir les symboles de débogage de tous les logiciels fonctionnant). Sous Windows, ce n'est pas le cas et cela peut être handicapant.

Citation Envoyé par Steinvikel Voir le message
@LittleWhite
Tu suggères que c'est une problématique plus à la nature du codage, ou à celui du langage utilisé, plutôt qu'à la nature de l'ordonnanceur lui même que ces deux éléments précédents sont sensés utiliser ?
Non, pas le langage, ni le code utilisé. Je penchais plus à d'autres composants du noyau ou encore, la bibliothèque standard. En effet, le std::mutex n'est pas le même sous Windows que sous Linux. On pourrait donc tester et comparer l'implémentation clang, l'implémentation MinGW à celle de MSVC (celle qui semble être utilisée). Aussi, sous Linux, je tenterai différentes pistes telles que :
  • jouer avec le gouverneur de fréquence CPU (powersave...) et faire un test en fréquence max fixe (et même tester le turboboost)
  • jouer avec nice ;
  • jouer avec le core pinning (bloquer le programme/les programmes sur des coeurs spécifiques).

Mais avant de partir dans tous les sens, il faut que je lise son article (l'original) en entier .
4  0 
Avatar de LittleWhite
Responsable 2D/3D/Jeux https://www.developpez.com
Le 04/01/2020 à 11:20
Bonjour,

Sujet vraiment intéressant. Maintenant, je n'arrive pas à comprendre.
On a parlé de ces résultats sous Windows :

En comparaison de ceux-ci, sous Linux :

Ce que je vois de plus flagrant, c'est le std::mutex. Le reste, c'est une différence de ~3ms (soit 5%) (pire cas) à l'avantage de Windows. 5%, on peut considérer cela comme négligeable.
Du coup, il reste le std::mutex. Je me demande si c'est réellement un problème d'ordonnancement.
3  0 
Avatar de CaptainDangeax
Membre éprouvé https://www.developpez.com
Le 06/01/2020 à 15:02
Citation Envoyé par xarkam Voir le message
Il a certainement raison. Lorsque je lance une vidéo dans vlc sous linux, j'ai des coupures sur les 10 premières secondes et lorsque je me déplace dans la vidéo car tout les cœurs sont sollicités.
J'ai maintenant l'explication à ce phénomène.

Avec le réseau c'est pareil. Sous linux je copie 50% moins vite vers/de mon nas alors que sous windows je vais à 100% de la vitesse de mon lan.
Pour ton VLC, est-ce que au moins tu as activé l'accélération matérielle avec VA-API ou VDPAU sous Linux ? C'est un point à vérifier.

Pour ton NAS, est-ce que tu utilises NFS quand tu es sous Linux ? Si tu utilises Samba, le protocole de Windows, rien d'étonnant à ce que Windows aille plus vite...
3  0 
Avatar de Steinvikel
Membre émérite https://www.developpez.com
Le 11/01/2020 à 6:49
...surtout que permis les plus gros contributeur du kernel Linux, il y a notament Intel, Red Hat, Linaro, Samsung, SUSE, IBM, Renesas, Google, AMD et Texas Instruments, ARM, Oracle ...et Microsoft.
Que des amateurs en somme.
2  0 
Avatar de transgohan
Expert éminent https://www.developpez.com
Le 06/01/2020 à 16:27
Citation Envoyé par yahiko Voir le message
Il s'agit d'une autre preuve éclatante que Windows, [...] est plus performant que Linux
J'espère que c'est sur le ton de l'humour...
Car cela ne prouve en l'état... Rien du tout...
Un OS met à disposition bien plus de fonction qu'un simple spinlock ou autre...

Ce serait comme d'affirmer que telle voiture est inférieure à une autre car tel bouton du panneau de contrôle est moins accessible...
Il n'y a aucun fond de vérité dans cette affirmation.
2  1 
Avatar de Steinvikel
Membre émérite https://www.developpez.com
Le 04/01/2020 à 12:15
@LittleWhite
Tu suggères que c'est une problématique plus à la nature du codage, ou à celui du langage utilisé, plutôt qu'à la nature de l'ordonnanceur lui même que ces deux éléments précédents sont sensés utiliser ?

Citation Envoyé par dourouc05 Voir le message
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.
Eh bien je peut statuer, en témoignant personnellement, que sur un Windows 10 Pro à jour (2019) équipé d'un SSD Toshiba classique, d'un i7 Haswell (4xxx), et de 8 Go de RAM (CL7-7-7)... sur de plus en plus de jeux (FPS ou MMO notamment), il y a des freezes/saccades de 0,5s à 4s avec un son uni-tonal (comme un électrocardiogramme plat, mais à la note où le son s'est arrêté).
Ce problème survient car le "petit" SSD est trop rempli (sur ses 120 Go), et que l'usage actuelle de la machine l'amène à être constamment en dépassement de RAM --> 8 Go physique, 1Go réservé pour l'iGPU, --> 7Go pour le système qui utilise constamment entre 14 et 28 Go de "mémoire validé" comme l'appel Windows dans sa mémoire virtuelle (swap).
Je ne suis pas sûr que se contexte de "limitation de ressource" soit si défavorable au kernel Linux. En fait je pense plutôt que la tendance serait inverse. Mais bon, je m'avance sur un domaine que je ne maîtrise pas.

Je me rappel sur Windows 95 et 98, et plus rarement sur XP, entendre le son "trembler" régulièrement, il est dommage de constater que malgré des processeurs 1000x plus puissant (si ce n'est plus), cette "lenteur" continue d'apparaître. On peut tout de même relativiser en tenant compte du fait que, bien que 1000x plus puissant, ils sont 1000x plus sollicités et de manière plus polyvalente.
0  0 
Avatar de JPLAROCHE
Membre confirmé https://www.developpez.com
Le 04/01/2020 à 15:23
Avec le réseau c'est pareil. Sous linux je copie 50% moins vite vers/de mon nas alors que sous windows je vais à 100% de la vitesse de mon lan.

J'ai un NAS externe , que ce soit sous Linux ou Windows(sur le même ordinateur) c'est IDEM.
j'utilise OpenMediaVault et un HP dédier (un cube en raid) .
0  0 
Avatar de walfrat
Membre éprouvé https://www.developpez.com
Le 06/01/2020 à 15:06
L'article est intéressant, la réponse de Linus Torvald et celle de l'auteur du Billet à Linus suggère plusieurs chose :
  • Le locking et notamment les mesures de performance, sont un sujet difficile.
  • les spinlock et sched_yield sont des fonctions à éviter
  • la réponse de l'auteur est que beaucoup de développeur dans le monde du jeux vidéo qui n'ont pas de connaissance aussi avancés en Linux utilisent les spinlock car sur des benchmarks simples ils apparaissent plus performant.


Dans les sujets liés je me souviens qu'il n'y a pas si longtemps, un développeur avait suggéré une modification du code de l'ordonnanceur afin de corriger un problème qui arrivait souvent avec des lectures vidéos qui faisait que l'ordonnanceur ne donnait pas assez de temps à la vidéo même avec aucun autre logiciel qui tourne. (logiciel au sens navigateur web, word, pas des processus et daemon classiques qui tournent par exemple sur un Ubuntu par défaut).
0  0