Le multi-threading sans verrouillage est destiné aux vrais experts du threading

86

Je lisais une réponse que Jon Skeet a donnée à une question et y mentionnait ceci:

En ce qui me concerne, le multi-threading sans verrouillage est destiné aux vrais experts du threading, dont je ne fais pas partie.

Ce n'est pas la première fois que j'entends cela, mais je trouve très peu de gens qui parlent de la façon dont vous le faites réellement si vous souhaitez apprendre à écrire du code multithread sans verrouillage.

Ma question est donc en plus d'apprendre tout ce que vous pouvez sur le threading, etc. où commencez-vous à essayer d'apprendre à écrire spécifiquement du code multi-threading sans verrou et quelles sont de bonnes ressources.

À votre santé

vdhant
la source
J'utilise les plates-formes gcc, linux et X86 / X68. Sans verrouillage, ce n'est pas aussi difficile qu'ils le font tous! Les fonctions intégrées de gcc atomic ont des barrières de mémoire sur Intel, mais cela n'a pas d'importance dans la vraie vie. Ce qui compte, c'est que la mémoire soit modifiée de manière atomique. Lorsque vous concevez des structures de données "sans verrouillage", cela n'a pas d'importance lorsqu'un autre thread voit un changement. Les listes chaînées simples, les listes à sauter, les tables de hachage, les listes gratuites, etc. sont assez faciles à faire sans verrouillage. Le verrouillage gratuit n'est pas pour tout. C'est juste un autre outil qui convient à certaines situations.
johnnycrash
2
1024cores.net
Mankarse
Voter pour fermer en tant que recommandation de ressources, ou ne pas clarifier ce que vous demandez.
Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功

Réponses:

100

Les implémentations actuelles «sans verrouillage» suivent le même schéma la plupart du temps:

  • * lire un état et en faire une copie **
  • * modifier la copie **
  • faire une opération verrouillée
  • réessayer en cas d'échec

(* facultatif: dépend de la structure de données / de l'algorithme)

Le dernier bit est étrangement similaire à un verrou tournant. En fait, c'est un spinlock de base . :)
Je suis d'accord avec @nobugz sur ce point: le coût des opérations imbriquées utilisées dans le multi-threading sans verrouillage est dominé par les tâches de cache et de cohérence mémoire qu'il doit effectuer .

Ce que vous gagnez cependant avec une structure de données "sans verrouillage", c'est que vos "verrous" sont très fins . Cela diminue la chance que deux threads simultanés accèdent au même «verrou» (emplacement mémoire).

L'astuce la plupart du temps est que vous n'avez pas de verrous dédiés - à la place, vous traitez par exemple tous les éléments d'un tableau ou tous les nœuds d'une liste liée comme un "verrou tournant". Vous lisez, modifiez et essayez de mettre à jour s'il n'y a pas eu de mise à jour depuis votre dernière lecture. Si tel était le cas, vous réessayez.
Cela rend votre "verrouillage" (oh, désolé, non verrouillable :) très fin, sans introduire de mémoire ou de ressources supplémentaires.
Le rendre plus fin diminue la probabilité d'attentes. Le rendre aussi fin que possible sans introduire de besoins en ressources supplémentaires semble bien, n'est-ce pas?

Cependant, la plupart du plaisir peut provenir de la bonne commande de chargement / magasin .
Contrairement à nos intuitions, les processeurs sont libres de réorganiser les lectures / écritures de la mémoire - ils sont d'ailleurs très intelligents: vous aurez du mal à observer cela à partir d'un seul thread. Cependant, vous rencontrerez des problèmes lorsque vous commencerez à faire du multi-threading sur plusieurs cœurs. Vos intuitions vont s'effondrer: ce n'est pas parce qu'une instruction est plus tôt dans votre code que cela se produira plus tôt. Les processeurs peuvent traiter les instructions dans le désordre: et ils aiment particulièrement faire cela aux instructions avec accès mémoire, pour masquer la latence de la mémoire principale et mieux utiliser leur cache.

Maintenant, il est sûr contre l'intuition qu'une séquence de code ne circule pas "de haut en bas", mais fonctionne comme s'il n'y avait aucune séquence du tout - et peut être appelée "terrain de jeu du diable". Je pense qu'il est impossible de donner une réponse exacte quant aux réorganisations de chargement / magasin qui auront lieu. Au lieu de cela, on parle toujours en termes de mays and mights and cannettes et se prépare au pire. "Oh, le CPU pourrait réorganiser cette lecture pour venir avant cette écriture, il est donc préférable de mettre une barrière de mémoire ici, à cet endroit."

Les choses sont compliquées par le fait que même ces mays et mights peuvent différer selon les architectures de CPU. Il se peut , par exemple, que quelque chose qui ne se produise pas dans une architecture puisse se produire sur une autre.


Pour obtenir un multi-threading "sans verrouillage", vous devez comprendre les modèles de mémoire.
Obtenir le modèle de mémoire et les garanties corrects n'est cependant pas anodin, comme le démontre cette histoire, dans laquelle Intel et AMD ont apporté quelques corrections à la documentation pour MFENCEprovoquer des remous parmi les développeurs JVM . Il s'est avéré que la documentation sur laquelle les développeurs se sont appuyés depuis le début n'était pas si précise en premier lieu.

Les verrous dans .NET entraînent une barrière de mémoire implicite, vous pouvez donc les utiliser en toute sécurité (la plupart du temps, c'est-à-dire ... voir par exemple cette grandeur de Joe Duffy - Brad Abrams - Vance Morrison sur l'initialisation paresseuse, les verrous, les volatiles et la mémoire barrières. :) (Assurez-vous de suivre les liens sur cette page.)

En prime, vous découvrirez le modèle de mémoire .NET lors d'une quête parallèle . :)

Il y a aussi un "oldie but goldie" de Vance Morrison: ce que chaque développeur doit savoir sur les applications multithread .

... et bien sûr, comme @Eric l'a mentionné, Joe Duffy est une lecture définitive sur le sujet.

Un bon STM peut se rapprocher le plus possible du verrouillage fin et offrira probablement une performance proche ou comparable à une implémentation faite à la main. L'un d'eux est STM.NET des projets DevLabs de MS.

Si vous n'êtes pas un fanatique uniquement de .NET, Doug Lea a fait un excellent travail dans JSR-166 .
Cliff Click a une vision intéressante des tables de hachage qui ne reposent pas sur le verrouillage par bandes - comme le font les tables de hachage simultanées Java et .NET - et semblent bien évoluer jusqu'à 750 processeurs.

Si vous n'avez pas peur de vous aventurer dans le territoire Linux, l'article suivant fournit plus d'informations sur les éléments internes des architectures de mémoire actuelles et sur la façon dont le partage de la ligne de cache peut détruire les performances: ce que tout programmeur doit savoir sur la mémoire .

@Ben a fait de nombreux commentaires sur MPI: Je suis sincèrement d'accord que MPI peut briller dans certains domaines. Une solution basée sur MPI peut être plus facile à raisonner, plus facile à implémenter et moins sujette aux erreurs qu'une implémentation de verrouillage à moitié cuite qui tente d'être intelligente. (C'est cependant - subjectivement - également vrai pour une solution basée sur STM.) Je parierais aussi qu'il est à des années-lumière plus facile d'écrire correctement une application distribuée décente dans par exemple Erlang, comme le suggèrent de nombreux exemples réussis.

MPI, cependant, a ses propres coûts et ses propres problèmes lorsqu'il est exécuté sur un seul système multicœur . Par exemple, à Erlang, il y a des problèmes à résoudre autour de la synchronisation de la planification des processus et des files d'attente de messages .
En outre, à la base, les systèmes MPI implémentent généralement une sorte d' ordonnancement N: M coopératif pour les «processus légers». Cela signifie par exemple qu'il y a un changement de contexte inévitable entre les processus légers. Il est vrai que ce n'est pas un "changement de contexte classique" mais surtout une opération de l'espace utilisateur et cela peut être fait rapidement - cependant je doute sincèrement qu'il puisse être ramené sous les 20 à 200 cycles qu'une opération verrouillée prend . La commutation de contexte en mode utilisateur est certainement plus lentmême dans la bibliothèque Intel McRT. L'ordonnancement N: M avec des processus légers n'est pas nouveau. Les LWP étaient là depuis longtemps dans Solaris. Ils ont été abandonnés. Il y avait des fibres dans NT. Ils sont pour la plupart une relique maintenant. Il y avait des "activations" dans NetBSD. Ils ont été abandonnés. Linux avait sa propre vision du sujet du thread N: M. Il semble être un peu mort maintenant.
De temps en temps, il y a de nouveaux prétendants: par exemple McRT d'Intel , ou plus récemment la planification en mode utilisateur avec ConCRT de Microsoft.
Au niveau le plus bas, ils font ce que fait un planificateur MPI N: M. Erlang - ou n'importe quel système MPI - pourrait grandement bénéficier des systèmes SMP en exploitant le nouvel UMS .

Je suppose que la question du PO ne porte pas sur les mérites et les arguments subjectifs pour / contre toute solution, mais si je devais y répondre, je suppose que cela dépend de la tâche: pour créer des structures de données de base de bas niveau et de haute performance qui fonctionnent sur un système unique avec nombreux cœurs , des techniques à faible verrouillage / «sans verrouillage» ou un STM donneront les meilleurs résultats en termes de performances et battraient probablement une solution MPI à tout moment en termes de performances, même si les plis ci-dessus sont aplatis par exemple à Erlang.
Pour construire quelque chose de modérément plus complexe qui fonctionne sur un seul système, je choisirais peut-être un verrouillage classique à gros grains ou, si les performances sont très préoccupantes, un STM.
Pour construire un système distribué, un système MPI ferait probablement un choix naturel.
Notez qu'il existe également des implémentations MPI pour .NET (bien qu'elles ne semblent pas aussi actives).

Andras Vass
la source
1
Bien que cette réponse contienne beaucoup de bonnes informations, l'idée principale selon laquelle les algorithmes sans verrouillage et les structures de données ne sont essentiellement qu'un ensemble de verrous rotatifs à grain très fin est fausse. Bien que vous voyiez généralement des boucles de relance dans des structures sans verrouillage, le comportement est très différent: les verrous (y compris les verrous spin) acquièrent exclusivement certaines ressources et d'autres threads ne peuvent pas progresser tant qu'ils sont maintenus. La "nouvelle tentative" dans ce sens attend simplement que la ressource exclusive soit libérée.
BeeOnRope
1
Les algorithmes sans verrouillage, par contre, n'utilisent pas CAS ou d'autres instructions atomiques pour acquérir une ressource exclusive, mais plutôt pour effectuer une opération. S'ils échouent, cela est dû à une course temporellement fine avec un autre thread, et dans ce cas, l'autre thread a progressé (a terminé son opération). Si un thread est indéfiniment suspect, tous les autres threads peuvent toujours progresser. C'est à la fois qualitativement et en termes de performances très différent des serrures exclusives. Le nombre de "tentatives" est généralement très faible pour la plupart des boucles CAS, même en cas de forte contention ...
BeeOnRope
1
... mais cela n'implique bien sûr pas une bonne mise à l'échelle: la contention pour un seul emplacement mémoire sera toujours assez lente sur les machines SMP, juste en raison des latences inter-sockets inter-core, même si le nombre de pannes CAS est faible.
BeeOnRope
1
@AndrasVass - Je suppose que cela dépend aussi du "bon" vs "mauvais" code sans verrouillage. Tout le monde peut certainement écrire une structure et l'appeler sans verrou alors qu'elle utilise simplement un verrou tournant en mode utilisateur et ne répond même pas à la définition. J'encourage également tous les lecteurs intéressés à consulter cet article de Herlihy et Shavit, qui examine de manière formelle les différentes catégories d'algorithmes basés sur et sans verrouillage. Tout ce que Herlihy a sur ce sujet est également recommandé.
BeeOnRope
1
@AndrasVass - Je ne suis pas d'accord. La plupart des structures classiques sans verrouillage (listes, files d'attente, cartes simultanées, etc.) n'avaient pas de rotation, même pour les structures mutables partagées, et les implémentations pratiques existantes de la même chose dans, par exemple, Java suivent le même modèle (je ne suis pas aussi familier avec ce qui est disponible en C ou C ++ compilé en natif et c'est plus difficile là-bas en raison de l'absence de garbage collection). Peut-être que vous et moi avons une définition différente de la rotation: je ne considère pas la "relance CAS" que vous trouvez dans les trucs sans verrouillage "la rotation". La «rotation» de l'OMI implique une attente à chaud.
BeeOnRope
27

Livre de Joe Duffy:

http://www.bluebytesoftware.com/books/winconc/winconc_book_resources.html

Il écrit également un blog sur ces sujets.

L'astuce pour obtenir de bons programmes à faible verrouillage est de comprendre précisément quelles sont les règles du modèle de mémoire sur votre combinaison particulière de matériel, de système d'exploitation et d'environnement d'exécution.

Personnellement, je ne suis pas assez intelligent pour faire une programmation correcte à faible verrouillage au-delà d'InterlockedIncrement, mais si vous l'êtes, tant mieux, allez-y. Assurez-vous simplement de laisser beaucoup de documentation dans le code afin que les personnes qui ne sont pas aussi intelligentes que vous ne cassent pas accidentellement l'un de vos invariants de modèle de mémoire et introduisent un bogue impossible à trouver.

Eric Lippert
la source
38
Donc, si Eric Lippert et Jon Skeet pensent que la programmation sans verrouillage n'est que pour les gens plus intelligents qu'eux-mêmes, alors je m'enfuirai humblement en hurlant l'idée immédiatement. ;-)
dodgy_coder
20

Il n'existe pas de "threading sans verrouillage" de nos jours. C'était un terrain de jeu intéressant pour les universitaires et autres, à la fin du siècle dernier, lorsque le matériel informatique était lent et coûteux. L'algorithme de Dekker a toujours été mon préféré, le matériel moderne l'a mis au pâturage. Ça ne marche plus.

Deux développements ont mis fin à cela: la disparité croissante entre la vitesse de la RAM et celle du CPU. Et la capacité des fabricants de puces à mettre plus d'un cœur de processeur sur une puce.

Le problème de vitesse de la RAM a obligé les concepteurs de puces à mettre un tampon sur la puce du processeur. Le tampon stocke le code et les données, rapidement accessibles par le cœur du processeur. Et peut être lu et écrit depuis / vers la RAM à un rythme beaucoup plus lent. Ce tampon est appelé le cache du processeur, la plupart des processeurs en ont au moins deux. Le cache de 1er niveau est petit et rapide, le 2ème est grand et plus lent. Tant que le processeur peut lire les données et les instructions du cache de premier niveau, il fonctionnera rapidement. Un cache manquant coûte vraiment cher, cela met le processeur en veille pendant jusqu'à 10 cycles si les données ne sont pas dans le 1er cache, jusqu'à 200 cycles si elles ne sont pas dans le 2ème cache et qu'elles doivent être lues à partir de RAM.

Chaque cœur de processeur a son propre cache, ils stockent leur propre «vue» de la RAM. Lorsque le processeur écrit des données, l'écriture est effectuée dans le cache qui est ensuite, lentement, vidé dans la RAM. Inévitable, chaque cœur aura désormais une vision différente du contenu de la RAM. En d'autres termes, un processeur ne sait pas ce qu'un autre processeur a écrit jusqu'à ce que ce cycle d'écriture RAM soit terminé et que le processeur actualise sa propre vue.

C'est dramatiquement incompatible avec le threading. Tu as toujours vraiment souciez l'état d'un autre thread lorsque vous devez lire des données écrites par un autre thread. Pour cela, vous devez programmer explicitement une soi-disant barrière de mémoire. Il s'agit d'une primitive de processeur de bas niveau qui garantit que tous les caches de processeur sont dans un état cohérent et ont une vue à jour de la RAM. Toutes les écritures en attente doivent être vidées dans la RAM, les caches doivent ensuite être actualisés.

Ceci est disponible dans .NET, la méthode Thread.MemoryBarrier () en implémente un. Étant donné que cela représente 90% du travail effectué par l'instruction de verrouillage (et plus de 95% du temps d'exécution), vous n'êtes tout simplement pas en avance en évitant les outils que .NET vous donne et en essayant d'implémenter les vôtres.

Hans Passant
la source
2
@ Davy8: la composition rend les choses encore difficiles. Si j'ai deux tables de hachage sans verrouillage et en tant que consommateur, j'accède aux deux, cela ne garantira pas la cohérence de l'état dans son ensemble. Le plus proche que vous pouvez venir aujourd'hui est les STM où vous pouvez mettre les deux accès par exemple dans un seul atomicbloc. Dans l'ensemble, la consommation de structures sans verrouillage peut être tout aussi délicate dans de nombreux cas.
Andras Vass
4
Je me trompe peut-être, mais je pense que vous avez mal expliqué le fonctionnement de la cohérence du cache. La plupart des processeurs multicœurs modernes ont des caches cohérents, ce qui signifie que le matériel du cache s'assure que tous les processus ont la même vue du contenu de la RAM - en bloquant les appels "read" jusqu'à ce que tous les appels "write" correspondants soient terminés. La documentation Thread.MemoryBarrier () ( msdn.microsoft.com/en-us/library/… ) ne dit absolument rien sur le comportement du cache - c'est simplement une directive qui empêche le processeur de réorganiser les lectures et les écritures.
Brooks Moses
7
"Il n'existe pas de" threading sans verrouillage "ces jours-ci." Dites cela aux programmeurs Erlang et Haskell.
Juliet
4
@HansPassant: "Il n'y a pas de" threading sans verrouillage "de nos jours". F #, Erlang, Haskell, Cilk, OCaml, la bibliothèque parallèle de tâches de Microsoft (TPL) et les blocs de construction filetés (TBB) d'Intel encouragent tous la programmation multithread sans verrouillage. J'utilise rarement des verrous dans le code de production ces jours-ci.
JD
5
@HansPassant: "une soi-disant barrière de mémoire. Il s'agit d'une primitive CPU de bas niveau qui garantit que tous les caches CPU sont dans un état cohérent et ont une vue à jour de la RAM. Toutes les écritures en attente doivent être vidées dans la RAM, le les caches doivent ensuite être actualisés ". Une barrière mémoire dans ce contexte empêche les instructions mémoire (chargements et magasins) d'être réorganisées par le compilateur ou le CPU. Rien à voir avec la cohérence des caches CPU.
JD
0

Quand il s'agit de multi-threading, vous devez savoir exactement ce que vous faites. Je veux dire explorer tous les scénarios / cas possibles qui pourraient se produire lorsque vous travaillez dans un environnement multi-thread. Le multithreading sans verrouillage n'est pas une bibliothèque ou une classe que nous intégrons, c'est une connaissance / expérience que nous gagnons au cours de notre voyage sur les threads.

bragboy
la source
Il existe de nombreuses bibliothèques qui fournissent une sémantique de threading sans verrouillage. STM est d'un intérêt particulier, dont il existe un certain nombre d'implémentations.
Marcelo Cantos
Je vois les deux côtés de celui-ci. Obtenir des performances efficaces d'une bibliothèque sans verrouillage nécessite une connaissance approfondie des modèles de mémoire. Mais un programmeur qui n'a pas cette connaissance peut toujours bénéficier des avantages de l'exactitude.
Ben Voigt
0

Même si le threading sans verrouillage peut être difficile dans .NET, vous pouvez souvent apporter des améliorations significatives lors de l'utilisation d'un verrou en étudiant exactement ce qui doit être verrouillé et en minimisant la section verrouillée ... cela est également connu comme la minimisation de la granularité du verrou .

À titre d'exemple, disons simplement que vous devez rendre un thread de collection sûr. Ne jetez pas aveuglément un verrou autour d'une méthode itérant sur la collection si elle effectue une tâche gourmande en ressources processeur sur chaque élément. Vous n'aurez peut-être besoin que de verrouiller la création d'une copie superficielle de la collection. L'itération sur la copie pourrait alors fonctionner sans verrou. Bien sûr, cela dépend fortement des spécificités de votre code, mais j'ai pu résoudre un problème de convoi de verrouillage avec cette approche.

dodgy_coder
la source