Le multithreading sans verrouillage est réservé aux vrais experts en threading.

Question

J'étais en train de lire un réponse que Jon Skeet a donné à une question et dans celle-ci il a mentionné ceci :

En ce qui me concerne, le multithreading sans verrou est réservé aux vrais experts en threading, dont je ne fais pas partie.

Ce n'est pas la première fois que j'entends cela, mais je trouve que très peu de personnes parlent de la façon dont on peut réellement le faire si vous êtes intéressé à apprendre comment écrire du code multithreading sans verrou.

Ma question est donc la suivante : outre le fait d'apprendre tout ce que vous pouvez sur le threading, etc., par où commencer pour apprendre à écrire spécifiquement du code multi-threading sans verrou et quelles sont les bonnes ressources ?

Cheers

Answer 1

Les implémentations actuelles "sans verrou" suivent le même schéma la plupart du temps :

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

_{<em>(*facultatif : dépend de la structure de données/algorithme)</em>}

La dernière partie est étrangement similaire à un spinlock. En fait, il s'agit d'un spinlock . :)
Je suis d'accord avec @nobugz sur ce point : le coût des opérations interverrouillées utilisées dans le multithreading sans verrou est de dominée par les tâches de cache et de cohérence de la mémoire qu'elle doit effectuer .

En revanche, une structure de données "sans verrous" permet d'obtenir des "verrous" très fins . Cela réduit le risque que deux threads concurrents accèdent au même "verrou" (emplacement de mémoire).

La plupart du temps, l'astuce consiste à ne pas avoir de verrous dédiés, mais à traiter, par exemple, tous les éléments d'un tableau ou tous les nœuds d'une liste chaînée comme un "spin-lock". Vous lisez, modifiez et essayez de mettre à jour s'il n'y a pas eu de mise à jour depuis votre dernière lecture. Si c'est le cas, vous réessayez.
Cela permet d'obtenir un "verrouillage" (oh, pardon, un non-verrouillage :) très fin, sans nécessiter de mémoire ou de ressources supplémentaires.
Une granularité plus fine diminue la probabilité d'attente. La rendre aussi fine que possible sans introduire de besoins en ressources supplémentaires semble être une bonne chose, n'est-ce pas ?

Cependant, la plupart des plaisirs peuvent provenir de assurer un ordonnancement correct du chargement et du stockage .
Contrairement à ce que l'on pourrait penser, 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 à l'observer à partir d'un seul thread. Vous rencontrerez toutefois des problèmes lorsque vous commencerez à faire du multithreading sur plusieurs cœurs. Vos intuitions s'effondreront : ce n'est pas parce qu'une instruction se trouve plus tôt dans votre code qu'elle se produira effectivement plus tôt. Les processeurs peuvent traiter les instructions dans le désordre : ils aiment particulièrement le faire pour les instructions comportant des accès à la mémoire, afin de masquer la latence de la mémoire principale et de mieux utiliser leur cache.

Il est évident qu'une séquence de code ne s'écoule pas "de haut en bas", mais comme s'il n'y avait pas de séquence du tout, ce qui va à l'encontre de l'intuition et peut être qualifié de "terrain de jeu du diable". Je pense qu'il est impossible de donner une réponse exacte quant aux réorganisations de la charge et de la mémoire qui auront lieu. Au lieu de cela, on parle toujours en termes de mays y lumières y boîtes de conserve et se préparer au pire. "Oh, l'unité centrale pourrait Il est donc préférable de placer une barrière de mémoire ici, à cet endroit".

Les choses sont compliquées par le fait que même ces mays y lumières peut différer d'une architecture CPU à l'autre. Il s'agit d'une pourrait Il se peut, par exemple, qu'une chose qui est garantie de ne pas se produire en une seule architecture pourrait se produire sur un autre.

---

Pour obtenir un multithreading "sans verrou" correct, il faut comprendre les modèles de mémoire.
Obtenir un modèle de mémoire et des garanties correctes n'est cependant pas trivial, comme le montre l'exemple suivant Cette histoire, par laquelle Intel et AMD ont apporté quelques corrections à la documentation de la MFENCE qui a provoqué une certaine agitation parmi les développeurs de JVM . Il s'est avéré que la documentation sur laquelle les développeurs s'appuyaient depuis le début n'était pas si précise que cela.

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

En outre, vous se familiariser avec le modèle de mémoire .NET au cours d'une quête secondaire . :)

Il y a également un "oldie but goldie" de Vance Morrison : Ce que tout développeur doit savoir sur les applications multithreads .

...et bien sûr, en tant que @Eric mentionnés, Joe Duffy est une référence en la matière.

Un bon STM peut se rapprocher le plus possible d'un verrouillage fin et fournira probablement des performances proches ou égales à celles d'une implémentation réalisée à la main. L'un d'entre eux est STM.NET de la Projets DevLabs de l'EM.

Si vous n'êtes pas un fanatique de .NET, Doug Lea a réalisé un excellent travail dans le cadre de la JSR-166 .
Cliff Click propose une approche intéressante des tables de hachage qui ne repose pas sur le lock-striping - comme le font les tables de hachage concurrentes de Java et .NET - et qui semble bien s'adapter à 750 CPU.

Si vous n'avez pas peur de vous aventurer sur le territoire de Linux, l'article suivant vous permettra de mieux comprendre le fonctionnement interne des architectures de mémoire actuelles et la manière dont le partage des lignes de cache peut nuire aux 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 pour dire 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é bâclée qui essaie d'être intelligente (c'est cependant - subjectivement - également vrai pour une solution basée sur STM.) Je parierais également qu'il est des années-lumière plus facile d'écrire correctement un distribué 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 ordinateur de bureau. système unique à plusieurs cœurs . Par exemple, en Erlang, il y a des problèmes à résoudre autour de l'élément synchronisation de l'ordonnancement des processus et des files d'attente de messages .
En outre, les systèmes MPI mettent généralement en œuvre une sorte de système coopératif d'échange de données. Programmation N:M 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 qu'il ne s'agit pas d'un "changement de contexte classique" mais plutôt d'une opération dans l'espace utilisateur et qu'elle peut être rendue rapide. 20-200 cycles d'une opération verrouillée . Le changement de contexte en mode utilisateur est certainement plus lent même dans la bibliothèque Intel McRT. L'ordonnancement N:M avec des processus légers n'est pas nouveau. Les processus légers existent depuis longtemps dans Solaris. Ils ont été abandonnés. Il y avait des fibres dans NT. Elles ne sont plus qu'une relique. Il y avait des "activations" dans NetBSD. Elles ont été abandonnées. Linux avait son propre point de vue sur le sujet du threading N:M. Il semble qu'il s'agisse en quelque sorte d'un système de gestion de l'espace de travail. Il semble qu'il n'y ait plus rien à faire à ce sujet.
De temps en temps, il y a de nouveaux concurrents : par exemple McRT d'Intel ou plus récemment Programmation en mode utilisateur avec ConCRT de Microsoft.
Au niveau le plus bas, ils font ce qu'un planificateur MPI N:M fait. Erlang - ou tout autre système MPI -, pourrait bénéficier grandement des systèmes SMP en exploitant le nouveau système d'ordonnancement MPI. UMS .

Je suppose que la question de l'OP ne porte pas sur les mérites et les arguments subjectifs pour/contre toute solution, mais si je devais répondre à cette question, je suppose que cela dépend de la tâche : pour construire des structures de données de base de bas niveau et de haute performance qui tournent sur un ordinateur de bureau ou un ordinateur portable, il est préférable d'utiliser des structures de données de base de haut niveau. système unique avec plusieurs cœurs Les techniques à faible verrouillage/"sans verrouillage" ou un STM donneront les meilleurs résultats en termes de performances et l'emporteront probablement à tout moment sur une solution MPI, même si les problèmes susmentionnés sont résolus, par exemple dans le cas d'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 importantes, un STM.
Pour construire un système distribué, un système MPI serait probablement un choix naturel.
Il convient de noter qu'il existe Implémentations MPI para .NET également (bien qu'ils semblent moins actifs).

Answer 2

Le livre de Joe Duffy :

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

Il rédige également un blog sur ces sujets.

L'astuce pour réussir les programmes à faible taux de verrouillage consiste à comprendre à un niveau profond précisément quelles sont les règles du modèle de mémoire dans 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 de la serrure basse au-delà de l'InterlockedIncrement, mais si vous l'êtes, c'est parfait, allez-y. Assurez-vous simplement de laisser beaucoup de documentation dans le code afin que les gens qui ne sont pas aussi intelligents que vous ne brisent pas accidentellement l'un des invariants de votre modèle de mémoire et n'introduisent pas un bogue impossible à trouver.

Answer 3

Le "filetage sans serrure" n'existe plus aujourd'hui. 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 cher. Algorithme de Dekker a toujours été mon préféré, mais le matériel moderne l'a mis au rancart. Il ne fonctionne plus.

Deux évolutions ont mis fin à cette situation : la disparité croissante entre la vitesse de la mémoire vive et celle de l'unité centrale. Et la capacité des fabricants de puces à intégrer plus d'un cœur de CPU sur une puce.

Le problème de la vitesse de la RAM a obligé les concepteurs de puces à placer une mémoire tampon sur la puce de l'unité centrale. La mémoire tampon stocke le code et les données, rapidement accessibles par le cœur de l'unité centrale. Il est possible de lire et d'écrire dans la RAM à un rythme beaucoup plus lent. Cette mémoire tampon est appelée cache de l'unité centrale. La plupart des unités centrales en possèdent au moins deux. La mémoire cache de premier niveau est petite et rapide, la mémoire cache de second niveau est grande et plus lente. Tant que l'unité centrale peut lire les données et les instructions du cache de premier niveau, elle fonctionne rapidement. Une erreur de cache est très coûteuse, elle met l'unité centrale en veille pendant 10 cycles si les données ne se trouvent pas dans le premier cache, 200 cycles si elles ne se trouvent pas dans le deuxième cache et qu'elles doivent être lues à partir de la mémoire vive.

Chaque cœur de processeur possède son propre cache, il stocke sa propre "vue" de la mémoire vive. Lorsque l'unité centrale écrit des données, l'écriture est effectuée dans la mémoire cache qui est ensuite, lentement, évacuée vers la mémoire vive. Inévitablement, chaque noyau aura alors une vue différente du contenu de la mémoire vive. En d'autres termes, une unité centrale ne sait pas ce qu'une autre unité centrale a écrit jusqu'à ce que le cycle d'écriture dans la RAM soit terminé y l'unité centrale actualise sa propre vue.

C'est tout à fait incompatible avec le threading. Vous devez toujours vraiment se soucier de l'état d'un autre thread lorsque vous devez lire des données qui ont été écrites par un autre thread. Pour ce faire, vous devez programmer explicitement ce que l'on appelle une barrière mémoire. Il s'agit d'une primitive de bas niveau de l'unité centrale qui garantit que tous les caches de l'unité centrale sont dans un état cohérent et ont une vue actualisée de la mémoire vive. Toutes les écritures en attente doivent être transférées dans la RAM, puis les caches doivent être rafraîchis.

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

Answer 4

Google pour structures de données sans verrou y mémoire transactionnelle logicielle .

Je suis d'accord avec John Skeet sur ce point : le filetage sans serrure est le terrain de jeu du diable, et il vaut mieux le laisser aux personnes qui savent qu'elles savent ce qu'elles doivent savoir.

Answer 5

Lorsqu'il s'agit de multithreading, il faut savoir exactement ce que l'on fait. Je veux dire explorer tous les scénarios/cas possibles qui peuvent se produire lorsque vous travaillez dans un environnement multithread. Le multithreading sans verrou n'est pas une bibliothèque ou une classe que l'on incorpore, c'est une connaissance/expérience que l'on acquiert au cours de notre voyage sur les threads.