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

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é

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).

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.

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.

Google pour les structures de données sans verrouillage et la mémoire transactionnelle logicielle .

Je suis d'accord avec John Skeet sur celui-ci; le filetage sans verrouillage est le terrain de jeu du diable, et il vaut mieux laisser aux gens qui savent qu'ils savent ce qu'ils doivent savoir.

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.

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.