Comment puis-je écrire une structure sans verrou?

Question

Dans mon application multithread, je vois beaucoup de conflits de verrous empêchant une bonne évolutivité sur plusieurs cœurs. J'ai décidé d'utiliser une programmation sans verrou pour résoudre ce problème.

Comment puis-je écrire une structure sans verrou?

Answer 1

La réponse courte est:

Vous ne pouvez pas.

La réponse longue est:

Si vous posez cette question, vous n'en savez probablement pas assez pour pouvoir créer une structure sans verrouillage. Créer des structures sans verrouillage est extrêmement difficile et seuls les experts en la matière peuvent le faire. Au lieu d’écrire la vôtre, recherchez une implémentation existante. Lorsque vous le trouverez, vérifiez dans quelle mesure il est utilisé, s'il est bien documenté, s'il a fait ses preuves, quelles en sont les limites - même des structures sans verrouillage publiées par d'autres personnes sont dépassées.

Si vous ne trouvez pas de structure sans verrou correspondant à la structure que vous utilisez actuellement, adaptez plutôt l'algorithme afin que vous puissiez utiliser un algorithme existant.

Si vous souhaitez toujours créer votre propre structure sans verrou, assurez-vous de:

• commencez par quelque chose de très simple
• comprendre le modèle de mémoire de votre plate-forme cible (y compris les contraintes de réordonnancement en lecture / écriture, les opérations atomiques)
• étudiez beaucoup les problèmes rencontrés par d'autres personnes lors de la mise en place de structures sans verrouillage
• ne devinez pas si cela fonctionnera, prouvez-le
• testez fortement le résultat

Plus de lecture:

Verrouiller des algorithmes libres et attendre gratuitement sur Wikipedia

Herb Sutter: code sans verrou: un faux sentiment de sécurité

Answer 2

Utilisez une bibliothèque telle que Blocs constitutifs du threading d'Intel , elle contient un certain nombre de structures et d'algorithmes sans verrouillage. . Je ne recommanderais vraiment pas d'essayer d'écrire du code sans verrouillage, car il est extrêmement sujet aux erreurs et difficile à comprendre.

Answer 3

Il est difficile d’écrire du code sans verrou de type thread-safe. mais cet article de Herb Sutter vous aidera à démarrer.

Answer 4

Comme sblundy a souligné, si tous les objets sont immuables, en lecture seule, vous n'avez pas besoin de vous inquiéter du verrouillage, mais vous devrez peut-être beaucoup les copier. La copie implique généralement malloc et malloc utilise le verrouillage pour synchroniser les allocations de mémoire sur les threads. Ainsi, les objets immuables peuvent vous acheter moins que vous ne le pensiez (malloc lui-même évolue plutôt mal et malloc est lent ; si vous faites beaucoup de malloc dans une section critique en termes de performances, ne vous attendez pas à de bonnes performances).

Lorsque vous n'avez besoin que de mettre à jour des variables simples (par exemple, int ou pointeurs 32 ou 64 bits), effectuez simplement des opérations d'addition ou de soustraction sur celles-ci ou échangez simplement les valeurs de deux variables, la plupart des plateformes proposent des "opérations atomiques". pour cela (GCC les propose également). Atomic n'est pas la même chose que thread-safe . Cependant, atomic s'assure que si un thread écrit une valeur de 64 bits dans un emplacement mémoire, par exemple, et qu'un autre thread le lit, celui-ci obtient la valeur avant ou après l'opération d'écriture, mais jamais valeur cassée entre les opérations d'écriture (par exemple, où les 32 premiers bits sont déjà les nouveaux, les 32 derniers bits sont toujours les anciennes valeurs! Ceci peut se produire si vous n'utilisez pas l'accès atomique variable).

Cependant, si vous avez une structure C avec 3 valeurs, que vous souhaitez mettre à jour, même si vous mettez à jour les trois avec des opérations atomiques, il s’agit de trois opérations indépendantes. Un lecteur peut donc voir la structure avec une valeur déjà mise à jour et deux non mis à jour. Ici, vous aurez besoin d'un verrou si vous devez vous assurer que le lecteur voit soit toutes les valeurs de la structure soit l'ancienne soit la nouvelle.

L’utilisation des verrous à gauche et à droite est un moyen d’améliorer l’échelle des verrous. Dans de nombreux cas, les mises à jour des données sont plutôt rares (opérations d'écriture), mais l'accès aux données est très fréquent (lecture des données), pensez aux collections (tables de hachage, arbres). Dans ce cas, les verrous R / W vous procureront un gain de performances énorme, car plusieurs threads peuvent détenir un verrou en lecture en même temps (ils ne se bloquent pas) et que si un thread souhaite un verrou en écriture, tous les autres threads sont bloqués au moment où la mise à jour est effectuée.

Le meilleur moyen d'éviter les problèmes de threads est de ne partager aucune donnée entre threads. Si chaque thread traite la plupart du temps avec des données auxquelles aucun autre thread n'a accès, vous n'aurez pas besoin de verrouiller ces données (pas d'opérations atomiques). Essayez donc de partager le moins de données possible entre les threads. Vous n'avez alors besoin que d'un moyen rapide pour déplacer les données entre les threads si vous en avez vraiment besoin (ITC, Inter Thread Communication). En fonction de votre système d'exploitation, de votre plate-forme et de votre langage de programmation (malheureusement, vous ne nous avez dit aucune de ces méthodes), diverses méthodes puissantes d'utilisation du CIT peuvent exister.

Enfin, une autre astuce pour travailler avec des données partagées mais sans aucun verrouillage consiste à s’assurer que les threads n’ont pas accès aux mêmes parties des données partagées. Par exemple. Si deux threads partagent un tableau, mais que l'un d'eux n'accédera jamais que de manière pair, l'autre que les index impairs, vous n'avez pas besoin de verrouiller. Ou si les deux partagent le même bloc de mémoire et que l'un n'utilise que la moitié supérieure de celui-ci, l'autre seulement, le moins, vous n'avez pas besoin de verrouiller. Bien que cela ne soit pas dit, cela conduira à de bonnes performances; surtout pas sur les processeurs multicœurs. Les opérations d'écriture d'un thread sur ces données partagées (exécution d'un coeur) peuvent forcer le cache à être vidé pour un autre thread (exécuté sur un autre core) et ces vidages de cache sont souvent le goulot d'étranglement pour les applications multithreads exécutées sur des processeurs multicœurs modernes.

Answer 5

Comme mon professeur (Nir Shavit de "L'art de la programmation multiprocesseur") a déclaré à la classe: "S'il vous plaît, ne le faites pas". La principale raison est la testabilité - vous ne pouvez pas tester le code de synchronisation. Vous pouvez exécuter des simulations, vous pouvez même effectuer des tests de résistance. Mais c'est au mieux une approximation approximative. Ce dont vous avez vraiment besoin, c'est d'une preuve de correction mathématique. Et très peu capables de les comprendre, encore moins de les écrire. Ainsi, comme d'autres l'ont dit: utilisez les bibliothèques existantes. Le le blog de Joe Duffy analyse certaines techniques (section 28). Le premier que vous devriez essayer est le fractionnement d’arbres: divisez en tâches plus petites et combinez-les.

Answer 6

L’immuabilité est une solution pour éviter le verrouillage. Consultez la discussion d'Eric Lippert et la mise en œuvre d'éléments tels que des piles et des files d'attente immuables. .

Answer 7

en re. La réponse de Suma, Maurice Herlithy, montre dans The Art of Multiprocessor Programming que quasiment n'importe quoi peut être écrit sans verrous (voir le chapitre 6). iirc, il s’agit essentiellement de scinder les tâches en éléments de nœud de traitement (comme une fermeture de fonction) et de les mettre en file d'attente. Les threads calculeront l'état en suivant tous les noeuds du dernier en cache. Évidemment, cela pourrait, dans le pire des cas, entraîner des performances séquentielles, mais il possède d’importantes propriétés sans verrouillage, empêchant ainsi les scénarios dans lesquels les threads pourraient être planifiés pendant de longues périodes où ils détiennent des verrous. Herlithy réalise également des performances théoriques sans attente, ce qui signifie qu’un fil ne finira pas par attendre pour gagner la mise en file d’attente atomique (c’est beaucoup de code compliqué).

Une file d'attente / pile multi-threads est étonnamment difficile (consultez la ABA problème ). D'autres choses peuvent être très simples. S'habituer à while (true) {atomicCAS jusqu'à ce que je l'echange} bloque; ils sont incroyablement puissants. Une intuition pour savoir ce qui est correct avec CAS peut aider le développement, mais vous devez utiliser de bons tests et peut-être des outils plus puissants (peut-être SKETCH , prochain MIT Kendo , ou spin ?) pour vérifier son exactitude si vous pouvez le réduire à une structure simple.

Envoyez-nous davantage d'informations sur votre problème. Il est difficile de donner une bonne réponse sans détails.

L’immuabilité

modifier est une bonne chose, mais son applicabilité est limitée, si je comprends bien. Il ne surmonte pas vraiment les risques d'écriture après lecture; Considérez deux threads exécutant "mem = NewNode (mem)"; ils pouvaient tous les deux lire mem, puis tous les deux l'écrire; pas le correct pour une fonction d'incrémentation classique. En outre, il est probablement lent en raison de l'allocation de tas (qui doit être synchronisée entre les threads).

Answer 8

L'inutilité aurait cet effet. Les modifications apportées à l'objet entraînent la création d'un nouvel objet. Lisp fonctionne de cette manière sous les couvertures.

L’article 13 de Java efficace explique cette technique.

Answer 9

Cliff Click a mené quelques recherches majeures sur les structures de données sans verrouillage en utilisant des machines à états finis et a également publié de nombreuses implémentations pour Java. Vous pouvez trouver ses papiers, diapositives et implémentations sur son blog: http://blogs.azulsystems.com/cliff/

Answer 10

Utilisez une implémentation existante, car ce domaine de travail est le domaine des experts de domaine et des docteurs (si vous le voulez bien!)

Par exemple, il existe une bibliothèque de code ici:

http://www.cl.cam. ac.uk/research/srg/netos/lock-free/

Answer 11

La plupart des algorithmes ou des structures sans verrouillage commencent par une opération atomique, c’est-à-dire par la modification d’un emplacement mémoire qui, une fois commencé par un thread, sera terminée avant que tout autre thread puisse effectuer la même opération. Avez-vous une telle opération dans votre environnement?

Voir ici pour le document canonique sur ce sujet.

Découvrez également cet article de wikipedia pour plus d'idées et de liens.

Answer 12

Le principe de base de la synchronisation sans verrouillage est le suivant:

• chaque fois que vous lisez la structure, vous suivez la lecture avec un test pour voir si la structure a été mutée depuis le début de la lecture et réessayez jusqu'à ce que vous réussissiez à lire sans que rien ne vienne et mute pendant que vous êtes. ce faisant,

• chaque fois que vous modifiez la structure, vous organisez votre algorithme et vos données de manière à ce qu'il n'y ait qu'une seule étape atomique qui, si elle est prise, rende la modification complète visible pour les autres threads, et vous organisez les choses de la modification est visible sauf si cette étape est prise. Vous utilisez le mécanisme atomique sans verrouillage existant sur votre plate-forme pour cette étape (par exemple, comparer-et-définir, lié à la charge + conditionnel au magasin, etc.). Dans cette étape, vous devez alors vérifier si un autre thread a muté l'objet depuis le début de l'opération de mutation, validez si tel n'est pas le cas et recommencez si elle l'a été.

Il existe de nombreux exemples de structures sans verrou sur le Web; sans en savoir plus sur ce que vous mettez en œuvre et sur quelle plate-forme, il est difficile d'être plus précis.

Answer 13

Si vous écrivez vos propres structures de données sans verrouillage pour un processeur multi-core, n'oubliez pas les barrières de mémoire! Pensez également aux techniques de la mémoire de transaction logicielle .

Answer 14

Eh bien, cela dépend du type de structure, mais vous devez créer cette structure de manière à ce qu'elle détecte et gère avec soin et en silence les éventuels conflits.

Je doute que vous puissiez en créer un 100% sans verrouillage, mais encore une fois, cela dépend du type de structure que vous devez construire.

Vous devrez peut-être également fragmenter la structure pour que plusieurs threads fonctionnent sur des éléments individuels, puis ensuite synchroniser / recombiner.

Answer 15

Comme mentionné, cela dépend vraiment du type de structure dont vous parlez. Par exemple, vous pouvez écrire une file d'attente limitée sans verrou, mais pas une file permettant un accès aléatoire.

Answer 16

Réduit ou élimine l'état mutable partagé.

Answer 17

En Java, utilisez les packages java.util.concurrent de JDK 5+ au lieu d’écrire les vôtres. Comme indiqué ci-dessus, il s’agit vraiment d’un domaine réservé aux experts et, à moins d’avoir une ou deux années libres, rouler votre propre n'est pas une option.

Answer 18

Pouvez-vous clarifier ce que vous entendez par structure?

À l'heure actuelle, je suppose que vous parlez de l'architecture globale. Vous pouvez le faire en ne partageant pas la mémoire entre les processus et en utilisant un modèle d'acteur pour vos processus.

Answer 19

Consultez mon lien ConcurrentLinkedHashMap pour obtenir un exemple de procédure à suivre pour verrouiller -free structure de données. Il ne s'appuie sur aucun document académique et n'exige pas des années de recherche comme le suggèrent d'autres. Cela nécessite simplement une ingénierie minutieuse.

Mon implémentation utilise un ConcurrentHashMap, un algorithme de verrouillage par compartiment, mais elle ne repose pas sur les détails de cette implémentation. Il pourrait facilement être remplacé par une implémentation sans verrouillage de Cliff Click. J'ai emprunté une idée à Cliff, mais utilisée beaucoup plus explicitement, c'est de modéliser toutes les opérations CAS avec une machine à états. Cela simplifie grandement le modèle, car vous verrez que j'ai des verrous psuedo via les états ing. Une autre astuce consiste à permettre la paresse et la résolution au besoin. Vous verrez cela souvent en faisant un retour en arrière ou en laissant d'autres discussions "aide". nettoyer. Dans mon cas, j'ai décidé de laisser les nœuds morts de la liste être expulsés lorsqu'ils atteignent la tête, plutôt que de gérer la complexité de leur retrait du milieu de la liste. Je peux changer cela, mais je ne faisais pas entièrement confiance à mon algorithme de retour en arrière et je voulais reporter un changement majeur, comme adopter une approche de verrouillage à 3 nœuds.

Le livre "L'Art de la programmation multiprocesseur" est une excellente introduction. Dans l’ensemble, cependant, je recommanderais d’éviter les conceptions sans verrouillage dans le code de l’application. Souvent, il est tout simplement excessif, là où d’autres techniques, moins sujettes aux erreurs, conviennent mieux.

Answer 20

Si vous voyez des conflits de verrous, je commencerai par essayer d'utiliser des verrous plus granulaires sur vos structures de données plutôt que des algorithmes totalement sans verrous.

Par exemple, je travaille actuellement sur une application multithread dotée d’un système de messagerie personnalisé (liste de files d’attente pour chaque thread, la file contient des messages à traiter) pour transmettre des informations entre les threads. Il y a un verrou global sur cette structure. Dans mon cas, je n'ai pas besoin de beaucoup de vitesse, alors cela n'a pas vraiment d'importance. Mais si ce verrou devenait un problème, il pourrait être remplacé par des verrous individuels à chaque file d'attente, par exemple. Ensuite, l'ajout / la suppression d'éléments dans / de la file d'attente spécifique n'aurait aucune incidence sur les autres files d'attente. Il y aurait toujours un verrou global pour l’ajout de nouvelles files d’attente, mais cela n’aurait pas été autant contesté.

Même une seule file d'attente multiproduits / consommateurs peut être écrite avec un verrouillage granulaire sur chaque élément, au lieu d'avoir un verrou global. Cela peut également éliminer les conflits.

Answer 21

Si vous lisez plusieurs mises en œuvre et articles sur le sujet, vous remarquerez le thème commun suivant:

1) Les objets d'état partagés sont de style lisp / clojure inmutable : toutes les opérations d'écriture sont implémentées, en copiant l'état existant dans un nouvel objet, apportez des modifications au nouvel objet, puis essayez de le mettre à jour. l'état partagé (obtenu à partir d'un pointeur aligné pouvant être mis à jour avec la primitive CAS). En d'autres termes, vous ne modifiez JAMAIS un objet existant qui pourrait être lu par plus que le thread actuel. L’immuabilité peut être optimisée à l’aide de la sémantique de copie sur écriture pour les objets volumineux et complexes, mais c’est un autre arbre de noix

2) vous spécifiez clairement les transitions autorisées entre l'état actuel et l'état suivant. : Valider la validité de l'algorithme devient alors un ordre de grandeur plus simple

3) Gérez les références ignorées dans les listes de pointeurs de danger par thread . Une fois les objets de référence sécurisés, réutilisez-les si possible

Voir un autre poste lié où un code implémenté avec des sémaphores et des mutex est (partiellement) réimplémenté dans un style sans verrouillage: Exclusion mutuelle et sémaphores