samedi 11 octobre
Accueil :: Dépêches :: Entretiens :: Journaux :: Forums :: Sondages :: Suivi :: Statistiques :: Contact :: Plan

Liens connexes

Dépêche modérée par

Dépêche éditée par

: La fin du verrou global dans le noyau Linux ?

Posté par patrick_g (page perso, ). Modéré le 18 mai 2008.
0
Connu sous le nom de "Big Kernel Lock" (BKL) ou encore de "Giant Lock", le verrou global du noyau est une technique permettant de rendre un système d'exploitation compatible avec l'emploi de machines multiprocesseurs.
Récemment un problème de régression de performances est venu remettre en lumière le BKL et raviver l'intérêt dans la difficile tâche consistant à le supprimer entièrement du noyau Linux.
Les discussions sur la liste de diffusion ont été vives avant que Linus ne choisisse une orientation. Maintenant c'est un travail de longue haleine qui va commencer afin d'en finir une bonne fois pour toute avec le verrou géant du noyau.

> Lire la suite (80 commentaires, moyenne: 4,7).   [dépêche : 12698 caractères]

Conceptuellement la technique du verrou global du noyau est simple. Quand une machine multiprocesseur (SMP) est utilisée il faut mettre en place un mécanisme empêchant les divers processeurs d'effectuer des actions contradictoires au même moment ou d'accéder aux mêmes ressources simultanément. Imaginons par exemple qu'un programme utilisateur déclenche un appel système et que le processus entre alors en espace noyau pour effectuer l'action demandée. Comment être certain que l'autre processeur n'est pas en train d'exécuter un code qui demande, lui-aussi, à entrer en espace noyau ? La solution la plus simple à ce problème est que le premier processus pose un verrou derrière lui dès qu'il entre dans l'espace mémoire du noyau. Ainsi le code s'exécutant sur l'autre processeur ne pourra pas entrer et faire des choses contradictoires.

L'avantage du verrou global du noyau est donc qu'il est très simple et très facile à mettre en place. Comme beaucoup de tâches vivent de toute façon la majeure partie de leur temps en espace utilisateur cela ne pose pas trop de problèmes d'utiliser le "Giant lock" et, avec une machine multiprocesseurs, on obtient quand même une plus grande rapidité d'exécution.
Le désavantage c'est que cette solution fait perdre, pour certaines tâches, une bonne partie des bénéfices associées à l'utilisation d'une machine SMP. Les programmes faisant un appel fréquent au noyau sont pénalisés par le "Giant lock". Comme le code du second processeur attend patiemment à la porte du noyau que le premier processus déverrouille l'entrée on perd beaucoup en rapidité. Encore pire : Imaginez une coûteuse machine octoprocesseurs avec un seul coeur faisant son travail en espace noyau alors que les sept autres se roulent les pouces en attendant l'ouverture du verrou !

La vraie solution au problème des accès simultanés au noyau n'est donc pas le verrou global. Ce ne peut être qu'une simple solution provisoire en attendant mieux. Mais qu'est-ce qui serait mieux ? On pourrait par exemple, à l'intérieur du noyau, isoler les blocs faisant des choses différentes et permettre de mettre des petits verrous sur chacun des blocs. Par exemple si un processus entre en espace noyau pour accéder au système de fichiers il ne posera qu'un verrou sur le système de fichiers. Ainsi un autre processus s'exécutant sur un autre processeur pourra entre en espace noyau pour accéder, par exemple, à la pile réseau. Il lui suffira de poser son verrou à lui sur la pile réseau et il n'y aura aucun risque d'actions contradictoires. Pour aller plus loin on fragmentera la pile réseau elle-même en sous-parties afin de pouvoir poser des verrous sur ces sous-parties, etc.
On voit que cette idée tend à décomposer conceptuellement le noyau en blocs fonctionnels de plus en plus petits afin de poser des verrous qui ne bloquent que le minimum de fonctions. Ce "fine-grained locking" (verrouillage à grains fins) est donc bien plus efficace que le verrou global du noyau et ce dernier est progressivement éliminé des systèmes d'exploitation modernes.
L'ennui c'est que l'implémentation du verrouillage à grains fins est très difficile et que le risque d'introduction de bugs subtils est très élevé. Cela prend donc du temps de convertir un système d'exploitation et l'élimination du verrou global est un projet de longue haleine.
Le noyau Linux a évolué progressivement au fil des années afin de réduire au maximum les appels au verrou global et, de la même façon, FreeBSD a lancé le projet SMPng pour introduire le verrouillage à grains fins à partir des versions 5.x. La majorité des blocs fonctionnels importants de ces noyaux sont désormais libérés du "Giant Lock" et tout le code critique pour les performances s'exécute avec le système de verrouillage à grains fins.
Certes il reste de nombreux appels au verrou global disséminés dans tout le noyau mais ces appels sont dans des parties anciennes du noyau et personne n'a vraiment envie d'aller mettre son nez dedans car de toute façon cela n'impacte pas les performances. Comme l'a écrit en 2004 Jonathan Corbet : "Changer le vieux code employant le BKL n'est pas un exercice de timides. Dans la plupart des cas l'attitude la plus prudente a été de simplement laisser les choses en l'état".
La situation était d'autant moins urgente qu'Ingo Molnar avait modifié le verrou géant pour qu'un thread en attente puisse obliger celui s'exécutant en mode noyau a interrompre son travail, à sortir du noyau et à libérer le verrou. Cette modification (techniquement Ingo a transformé le verrou géant en un sémaphore) avait pour but de réduire les latences générées par le "Giant lock". En permettant de préempter les divers appels au verrou géant restant dans le noyau tout le monde pensait qu'on en avait enfin fini avec cet empoisonnant casse-tête.

C'est pour cette raison que le message que Yanmin Zhang a posté le 6 mai sur la liste de diffusion Linux a causé une certaine consternation. Selon un test de performances, nommé AIM7, Yanmin Zhang a constaté une dégradation de 40% de la rapidité d'exécution entre le noyau stable 2.6.25 et le noyau candidat 2.6.26-rc1. Il a traqué l'origine du problème et il est tombé sur ce patch rendant très générique l'implémentation des sémaphores dans le noyau. Le problème se complique un peu parce que les sémaphores ne sont plus trop utilisés dans le noyau depuis l'introduction des mutex à partir du 2.6.16.
Nous voilà donc avec un noeud de problèmes qui semble inextricable et avec peu de solutions envisageables :
Ingo Molnar avait choisi la seconde solution mais Linus a opté pour la troisième. Pour lui le retour du problème de latence est l'occasion rêvée pour en finir avec le BKL (Big Kernel Lock): "La nouvelle implémentation des sémaphores (NdT: Celle d'Ingo avec le "lock stealing") n'en vaut tout simplement pas la peine. Très franchement nous avons peut-être _besoin_ d'avoir un BKL peu performant pour en finir avec lui. Les gens ont essayé de rendre le BKL plus efficace et cela a été un échec. Plutôt que d'investir des efforts démesurés en essayant de le rendre meilleur pourquoi ne pas juste dire : Bordel - Si vous avez des problèmes avec le verrou géant vous devez bosser avec les autres pour supprimer ce BKL au lieu de tourner autour du pot !"

Comme souvent avec Linus c'est donc la solution la plus radicale et la plus propre qui est favorisée. Il va donc falloir se retrousser les manches et s'attaquer à tous les appels au verrou géant qui restent dans le noyau. C'est un travail de grande ampleur car, comme le souligne Ingo : "12 ans après que Linux ait été converti en système d'exploitation compatible avec les machine multiprocesseurs, il reste encore plus de 1300 appels au verrou géant dans le code. Plus de 400 sont des sections critiques faisant appel à lock_kernel() et il y a aussi plus de 800 appels ioctl. Ces appels sont dispersés dans des zones de vieux code et peu de gens ont une bonne compréhension de ces zones et osent les modifier. Selon une analyse rapide, à la vitesse actuelle de suppression du BKL nous allons devoir attendre plus de 10 ans pour en finir et pour retrouver une latence acceptable".

Bien entendu dans l'esprit d'Ingo il n'était pas acceptable de s'en tenir à la vitesse actuelle et il a annoncé une branche spéciale du noyau Linux nommée "kill-the-BKL" afin d'accélérer le mouvement. En gros la stratégie suivie va consister a rendre le plus facile possible la suppression des appels au verrou géant sans risquer d'introduire les bugs subtils évoqués plus haut. Le BKL est transformé en mutex géant, l'outil de déboguage lockdep est ainsi compatible et permet de détecter les situations d'interblocages. Jonathan Corbet s'est consacré pour sa part a éradiquer les appels système injustifiés au verrou géant pour les périphériques en mode caractère. En effet beaucoup de ces périphériques n'ont pas vraiment besoin du BKL et ne font appel à lui que parce que le développeur a mal écrit son code. Il suffit donc d'enlever les lignes lock_kernel/unlock_kernel dans fs/char_dev.c et de modifier les 83 pilotes faisant appel à char_dev.c.
A un moment Jonathan Corbet s'est inquiété de savoir ce qui allait arriver aux modules maintenus à l'extérieur de la branche Linux principale : "Il n'y a pas d'avertissement aux mainteneurs de modules externes que des changements doivent être fait. Donc, sans le moindre doute, un bon nombre d'entre eux vont juste continuer comme avant sans rien modifier. Et quand l'un de ces modules aura _vraiment_ besoin du BKL alors un truc horrible va arriver à quelqu'un".
Comme il était prévisible Linus ne se préoccupe pas trop des gens qui maintiennent des modules à l'extérieur de la branche principale et sa réponse a été sans pitié : "Les modules externes ont des bugs parce que les interfaces changent. Film à 11 heures.
C'est vrai, mais cela ne devrait pas nous empêcher de le faire quand même. Spécialement parce que les modules externes qui sont bien maintenus (cad dont les auteurs suivent les grandes discussions comme celle-ci) pourront simplement s'adapter et utiliser le BKL comme avant. Et en plus ce changement restera compatible avec les anciens noyaux. Bien entendu les modules bien maintenus n'utiliseraient pas le BKL de toute façon..."

En définitive toute cette agitation sera sans doute bénéfique pour le noyau Linux. Après l'élimination progressive au fil des années du verrou géant dans tout le code critique pour les performances le travail avait été interrompu et les derniers appels non critiques stagnaient toujours dans le noyau. Pourquoi se casser la tête pour les enlever puisque cela ne changera rien à la rapidité de la machine ?
Le problème de performances soulevé par Yanmin Zhang aura donc été l'occasion de piquer au vif les développeurs et de raviver leur zèle. Comme Linus a refusé l'option tentante de cacher le BKL en complexifiant l'implémentation des sémaphores il ne reste plus qu'à s'attaquer bille en tête aux derniers vestiges du verrou géant. Le travail va se dérouler dans la branche "kill-the-BKL" mais il sera sans doute possible aux utilisateurs du noyau principal d'activer une nouvelle option (CONFIG_DEBUG_BKL) afin de participer eux aussi à la chasse aux bugs.
Avec un peu de chance ce processus ne devrait pas prendre trop de temps. Dans quelques mois le verrou géant ne devrait plus être qu'un mauvais souvenir et tous les processus pourront gambader simultanément en espace noyau.

Cette discussion est archivée, il n'est plus possible de laisser des commentaires.

Note : les commentaires appartiennent à ceux qui les ont postés. Nous n'en sommes pas responsables.

patrick_g, sors de ce corps !

Posté par nonas (Jabber id, page perso, ) le 18/05/2008 à 19:45. (lien). Évalué à 9.

Merci encore une fois pour cette superbe dépêche !

Bravo

Posté par Florimond Collette () le 18/05/2008 à 19:49. (lien). Évalué à 10.

Excellent article, résumant tout ce qui c'est passé avec la juste de dose de détails et d'explications.

Un petit correctif

Posté par reno () le 18/05/2008 à 19:49. (lien). Évalué à 7.

>mais Linus a opté pour la seconde.

Non c'est la troisième dans ta liste.

un point que je trouve perfectible aussi, c'est que dans la liste tu marque 'complexifier l'implémentation des sémaphores' ce qui aurait tendance a faire croire que ce serait nouveau, alors que ce n'est pas le cas.. Je mettrais plutôt 'revenir a l'ancienne implémentation (complexe mais performantes) des sémaphores'.

En tout cas, merci pour le poste!

Et CONFIG_PREEMPT_RT ?

Posté par pleiades () le 18/05/2008 à 20:24. (lien). Évalué à 9.

Le soucis est qu'il y a un impact non négligeable sur le temps réel sous Linux. Supprimer le BKL rajoute une section non pré-emptible dans le noyau. Et cela doit donc avoir un impact sur le patch CONFIG_PREEMPT-RT d'Ingo Molnár justement.
http://kerneltrap.org/mailarchive/linux-kernel/2008/5/14/1821774

pl.

Chapeau !!

Posté par nazcafan () le 18/05/2008 à 20:28. (lien). Évalué à 10.

Je dois avouer que j'ai déjà lu 2 fois des articles à propos du BKL, une fois sur kernelnewbies et une fois sur slashdot. Je n'avais pas compris grand chose...

En revanche, cette dépèche est claire, bien structurée, et explique parfaitement l'origine du problème, le principe des solutions envisagées, les tenants et les aboutissants.... Du patrick_g en grande forme quoi !

Merci beaucoup pour ces dépêches que je lis toujours avec grand plaisir.

Et en attendant ?

Posté par Éric (Jabber id, page perso, ) le 18/05/2008 à 20:28. (lien). Évalué à 4.

> Dans quelques mois

Et en attendant ?

La 26 était en rc1 donc à un statut assez avancé. Elle est retardée de quelques mois ? ou on la sortira avec la perte de perf ?

Sémaphore et mutex

Posté par IsNotGood () le 18/05/2008 à 20:51. (lien). Évalué à 3.

Tu parles de sémaphores et de mutex. Tu dis que c'est la même chose ou le laisse entendre.
Je ne connais pas grand chose au fonctionnement interne du noyau, mais mutex et sémaphore ne sont pas la même chose.
On peut utiliser un sémaphore comme un mutex, mais pas l'inverse. Certe, on peut implémenter les sémaphore uniquement avec les mutex, mais c'est n'est pas trivial.

Es-ce que j'ai rien compris ou as-tu fait un raccourcis pour simplifier ?

Vers ou ?

Posté par eastwind (Jabber id, ) le 18/05/2008 à 21:34. (lien). Évalué à 3.

Tu m'as fait peur , j'ai cru qu'il était questions de DRM , dans le noyau :)

et les autres OS ?

Posté par tomachaka () le 18/05/2008 à 21:41. (lien). Évalué à 7.

On parle un peu de FreeBSD dans la news, ils cherchent apparemment aussi à éliminer ce "verrou global"... mais qu'en est-il des autres ?

Comment se débrouillent-ils ? Les BSD, MacOSX, Windows ?

Par contre, je suppose que les OS temps réel comme QNX n'ont pas ce problème ?

Et les micro noyaux type HURD ?

Posté par topisto () le 19/05/2008 à 09:22. (lien). Évalué à 7.

Je suis peut-être à côté de la plaque mais n'arrive-t-on pas là aux limites intrinsèques des OS monolithiques comme Linux ? La solution n'est-elle pas dans la conception même de l'OS ? Des micro noyaux type HURD ne gèrent-il pas mieux cette problèmatique ?

bkl

Posté par Edgar Smith () le 19/05/2008 à 22:59. (lien). Évalué à 2.

[cite]Pour rebondir sur le sujet, comment s'en sortent les autres systèmes d'exploitation par rapport à ce problème ? Freebsd a été brièvement évoqué, qu'en est-il de windows, solaris, mac os x par exemple ?[/cite]

FreeBsd utilise les mutex pour diviser le BKL en de nombreux verrous fins.
Dragonfly a été crée en raison de cetteimplémentation et utilise pour sa part le Light weight kernel threading. (LWKT)

Merci pour l'article

Posté par Zorro () le 19/05/2008 à 23:36. (lien). Évalué à 9.

J'aime beaucoup la théorie informatique, elle me fascine littéralement. La capacité d'abstraction, et de raisonnement sur des mécanismes proches de l'intelligence, de ceux qui la maîtrise me sidère.
Mais je ne suis pas du tout informaticien de formation. Comme je la parcoure en dilettante, je suis trop souvent trop vite largué, et j'abandonne alors vite la lecture, vaguement frustré de n'avoir pas su suivre des formations scientifiques/informatiques.
Mais tes articles sont toujours superbes, et me redonnent à chaque fois du plaisir et du réconfort. À la fois pointus et clairs, parfaitement vulgarisés, ils me laissent à chaque fois plus cultivé et avec une meilleure compréhension des outils que j'utilise.
Donc bravo et merci.

Revenir en haut de page

Run by Team LinuxFr.org

Cette page a été générée par Templeet en 0.2316s (dont 0.022 de SQL).
Cette page est peut-être conforme xhtml 1.0.
Information sur le site.
Faire un don !