Sont atomiques variables sans verrouillage?

Lorsque nous parlons atomique variables, tels que C++11 est atomic<>, est-ce verrou libre? Ou est-lock-l'indice d'égouttage quelque chose de différent? Si je gérer une file d'attente atomique avec des variables, qu'il sera plus lent qu'un lock-free file d'attente?

InformationsquelleAutor pythonic | 2012-04-11
  1. 36

    La norme ne précise pas si atomique objets sont sans verrouillage. Sur une plate-forme qui ne fournit pas sans verrouillage des opérations atomiques pour un type T, atomic<T> objets peuvent être mises en œuvre à l'aide d'un mutex, qui ne serait pas sans verrouillage. Dans ce cas, tous les récipients à l'aide de ces objets dans leur mise en œuvre ne serait pas sans verrouillage soit.

    La norme fournit un moyen de vérifier si un atomic<T> variable est sans verrouillage: vous pouvez utiliser var.is_lock_free() ou atomic_is_lock_free(&var). Ces fonctions sont garantis retourne toujours la même valeur pour le même type de T sur l'exécution du programme. Pour les types de base tels que int, Il y a aussi des macros (par exemple,ATOMIC_INT_LOCK_FREE), qui précisent les si sans verrouillage atomique accès à ce type n'est disponible.

    • De l'intérêt, il y a des plates-formes qui ne fournissent pas de aucun lockless natif atomics, ou avez-vous juste dire que atomic<T> peut ne pas être en mode natif atomique pour toutes les tailles de T? Je ne vois pas comment une plate-forme sans véritable natif atomics serait de mettre en œuvre les mutex, en premier lieu ...
    • il se pourrait que vous n'avez que 1 octet atomique sur une plate-forme intégrée. Donc, quelque chose comme std::atomic<char> serait sans verrouillage. Toutefois, si les nombres entiers de 32 bits sont simulés par faire 4 octets opérations qui n'est pas atomique. Donc les plus susceptibles std::atomic<int> ne sera pas sans verrouillage. Cependant, vous pouvez faire un mutex (par exemple, un verrou de rotation) avec l'octet atomique.
    • Je voulais dire que sans verrouillage des opérations ne seraient pas pris en charge pour tous les objets de tailles - j'ai édité pour préciser. Je suppose que, en théorie, une plate-forme pourrait fournir natif de verrouillage/déverrouillage des opérations sans avoir lockless opérations atomiques, mais je ne suis pas au courant de telles plates-formes.
    • Certaines plates-formes ont atomique change instructions. Vous pouvez l'utiliser pour un mutex, et std::atomic_flag (qui est doivent être sans verrouillage), mais pas pour un général atomique (car il ne peut pas faire une plaine de charge).
    InformationsquelleAutor interjay
  2. 12

    Sans verrouillage s'applique généralement à des structures de données partagées entre plusieurs threads, où la synchronisation est pas exclusion mutuelle; l'intention est que tous les threads doivent continuer à faire une sorte de progrès au lieu de dormir sur un mutex.

    atomic<T> variables de ne pas utiliser des verrous (au moins où T est nativement atomique sur votre plate-forme), mais ils ne sont pas sans verrouillage dans le sens ci-dessus. Vous pourriez utilisation dans la mise en œuvre d'un lock-conteneur gratuit, mais ils ne sont pas suffisants.

    Par exemple, atomic<queue<T>> ne serait pas tout à coup faire un normal std::queue dans une serrure sans la structure de données. Vous pouvez, toutefois, de mettre en œuvre un véritable sans verrouillage atomic_queue<T> dont les membres ont été atomic.

    Noter que même si atomic<int> est nativement atomique et non émulé avec un verrou sur votre plate-forme, qui n'a pas sans verrouillage en aucune façon intéressante. Plaine int est déjà sans verrouillage dans ce sens: le atomic<> wrapper vous obtient le contrôle explicite de la mémoire de la commande, et l'accès à du matériel à des primitives de synchronisation.

    • Donc, spinlock est sans verrouillage lorsque je la mettre en œuvre à l'aide d'opérations atomiques? Je suppose que vous n'avez jamais céder à l'ordonnanceur, mais je ne suis pas sûr que ce soit sans verrouillage signifie que dans des conditions normales d'utilisation.
    • J'ai enlevé mon downvote btw. Votre modifier pour être plus clair ce que tu voulais dire et je pense que nous discutions sur d'autres niveaux.
    • Cheers - peut-être que je suis l'amalgame entre la sans verrouillage avec non bloquant, il se sent certainement ambiguë lorsque l'on parle de primitives elles-mêmes, plutôt que de l'algorithme de les utiliser.
    • Le terme "attendre" est utilisé pour différencier sans verrouillage des algorithmes de toujours progresser sur tous les threads (ie. ne bloquez pas). Spinlocks sont certainement sans verrouillage, mais ne pas attendre-gratuit - en fait, la même valeur atomique case (CAS) est utilisé couramment dans les algorithmes sans verrouillage.
    • Je suis en désaccord avec votre dernier paragraphe: Depuis la plaine int n'est pas thread-safe, il est inutile de dire que c'est sans verrouillage. Mais atomic<int> est thread-safe, et c'est certainement significatif s'il est sans verrouillage ou pas.
    • Plaine int est thread-safe sur x86 avec un seul écrivain par exemple, si le lecteur(s) ne disposent que de faibles exigences sur la façon up-to-date de leur point de vue est. Donc, pour certains, la logique de l'application, de la plaine int peut parfaitement être thread-safe.
    • Je pense que le dernier commentaire nécessite un peu de qualification. les lectures et les écritures sont garantis atomique et les lectures sont toujours bien commandés, mais écrit peut se produire hors de l'ordre(quoique de manière atomique). Si l'int valeur n'implique pas logiquement que certains autres que l'action est terminée, alors oui, vous êtes en sécurité. Sinon, vous devez atomique<> pour fournir une clôture sur l'écrit pour s'assurer de la causalité.
    • Re: writes may occur out of order - non, x86 commande garantit explicitement que les magasins sont classés dans le même thread, et de maintenir TSO-comme la mémoire de la commande de règles sur plusieurs threads. Il n'a aucun rapport avec bien ordonnée et atomique des charges et les magasins nécessitent encore de verrouillage depuis l'atomicité de l'opération ne garantit pas l'inter-op de l'atomicité de toute nature (c'est à dire - inc [x] peut atomique de charge et atomique magasin, mais la mémoire peut changer entre ces deux)
    • Je pense que j'ai besoin de qualifier un peu ce que je voulais dire. Sur x86, mot de la taille des charges et les magasins sont toujours atomique. Les opérations de lecture sur les x86 sont atomiques "acquisition/diffusion" des opérations. Les opérations d'écriture sur x86 sont atomiques, mais ne sont pas "libération" des opérations, sauf si elles sont "verrouillés", dans ce cas, ils sont "acquisition/diffusion". C'est suffisant pour garantir la causalité. Si vous regardez mon commentaire, je n'ai pas fait de demandes sur inter-op de l'atomicité. J'ai seulement affirmé que l'on peut garantir la causalité dans une serrure, gratuitement. C'est assez pour écrire des algorithmes parallèles correctement sans verrous ou des courses.

    InformationsquelleAutor Useless
  3. 2

    Marketting et le facteur "cool" de côté, il ne fait pas une twopenny tirage au sort d'une différence si la magie C++ syntaxique (brun) de sucre finit par la mise en œuvre d'un bus direct de verrouillage ou un mutex (qui peut compter sur le bus de serrures mais, comme un commentateur l'a fait remarquer, profite de l'OS lui-même pour le faire d'une façon plus efficace), ou rien du tout si vous avez la malchance de s'exécuter sur un seul procesor architecture.

    Mutex sont sémantiquement lock gratuit déjà. Ils mettent en œuvre tout ce dont vous pourriez rêver en termes de planification-la gentillesse, à savoir l'inversion de priorité de la manipulation et de la réentrée.
    Vous ne peut pas impasse sur un mutex (bon, en fait, vous pourriez si vous avez essayé très dur, mais aussi loin que la sécurisation d'une variable est concerné, vous n'aurez pas), et à l'aide d'un mutex sera pas ont plus notables effets secondaires sur les autres processus ou le système d'exploitation que d'un arrêt de bus verrouillé variable.

    La seule différence est qu'un programmeur peut (par leur conception ou par erreur) détenir un mutex pour un temps déraisonnable, bien que tout aussi incompétents programmeur peut sondage sur une "Attente" sans variable et d'obtenir la même idiot résultats, avec une catastrophique bus ralentissement qui va mettre beaucoup plus de stress sur le système dans son ensemble que d'une mauvaise utilisation de mutex (OK, mon précédent allusion à un BSOD était juste un juvénile provokation, si j'ai toujours suspect certains pilotes peuvent ne pas réagir très gentiment à l'lourd de contention de bus). De toute façon, ce problème est vite résolu quand le mutex appels sont enroulées autour d'un linéaire de l'accès à une assez petite quantité de mémoire.

    "Lock libre" est de vendre des rêves de wanabee durs programmeurs. Je trouve assez amusant que d'un mécanisme qui indeeds s'appuie sur verrouillage le multiprocesseur bus pourrait être appelé comme ça.

    Ce qu'est un "Lock gratuit" variable d'accès n'est harceler le matériel par la stérilisation du bus système de cache, interdisant l'accès au bus de planification, et plus généralement à la désactivation de tous les mécanismes qui permettent à votre moyenne multiprocesseur de bus pour faire un travail décent.

    Chaque fois que vous accédez à un "Verrou libre" magie variable, vous êtes une battante poignée de sable dans le bus du contrôleur de roues dentées.

    Comme tout simultanées mécanisme d'accès, bus à verrouillage de variables (désolé, je voulais dire "Verrouiller les variables libres") sont coûteux et peuvent avoir des effets secondaires négatifs qui sont extrêmement difficile de prédire ou même de diagnostiquer.

    Aussi longtemps que vous êtes à l'aide de ces nouveaux brillant jouets comme vous le feriez pour les mutex, c'est à dire très peu et seulement pour quelques bonnes raisons (et non, le jeu de la super cool de M. d'attente gratuit n'est pas l'un d'eux), c'est la fin.

    Mais si vous commencez à l'aspersion de bus de serrures de tous sur la place, ou (Dieu interdit!) interrogation bus à verrouillage de variables comme facile et bon marché de remplacement pour une bonne synchronisation des objets (ce que le super cool de M. d'attente gratuit pourrait appeler "le brassage de votre propre maison spinlocks en 3 étapes faciles"), vous ne gérer à son tour tout ce matériel de pointe votre code s'exécute dans un circa 1995 Pentium I émulateur.

    • Un mutex ne repose pas sur le bus de serrures, à dieu ne plaise que ce serait le cas (c'est beaucoup trop long pour être utilisable). Les verrous sont maintenus à l'intérieur de la base à travers des fouineurs sur la plupart des Processeurs modernes.
    • Je ne comprends pas le BSOD commentaire. Pouvez-vous donner un exemple de code de façon à provoquer un BSOD la façon dont vous l'avez mentionné?
    • Vous avez raison, j'ai corrigé pour qu'il "pourrait s'appuyer".
    • c'est un cas très rare (comme essayer de se verrouiller sur une ligne de split de la valeur peut-être, un fractionnement de la page définitivement), il ne devrait guère se produire dans tout raisonnable code. Je suis d'accord que le terme lock free est un peu abusé, mais c'est venu comme un peu trop d'un coup de gueule - vous devriez mettre/lien quelques exemples avec le profilage des résultats pour que ce soit plus constructif
    • Si vous avez réussi à avoir chaque processeur simultanément collé sur la maison d'un spinlock, je parie que la plupart des systèmes d'exploitation ne tiennent pas en place pour longtemps.
    • Ah bien, un peu de délire est parfois nécessaire pour compenser le battage médiatique,à mon humble avis. J'ai ajouté un exemple de référence de la discussion pour tenter de modérer le caractère informatif/construction trop. Le point principal que j'essayais de faire est, la complexité et les dangers potentiels du faible niveau des mécanismes doivent rester clairs sous l'apparente facilité de l'utilisation de nouvelles sucre syntaxique comme le C++11 interfaces proposent.
    • Ne supposez pas qu'un front-side bus de verrouillage est nécessaire de mettre en œuvre des opérations atomiques au niveau CPU - ARMv7 (au moins) est un exemple de la façon dont il peut être atteint sans.
    • avec qui je suis totalement d'accord 🙂
    • les moniteurs ne autoriser les verrous, ce qui peut être réalisé sur n'importe quelle architecture par quelque chose de simple (mais beaucoup moins pratique et efficace) que le masquage des interruptions. Cependant, les objets de haut niveau offrent aucun moyen de spécifier une telle subtelties comme "je vais être utilisé uniquement sur un seul processeur", afin de bus serrures seront très probablement être utilisée sur de nombreuses architectures, même si certains plus fine des alternatives sont disponibles.
    • Donc atomique variables sont mauvais parce qu'ils nécessitent un bus de verrouillage (c'est mal, mais ok, nous allons courir avec lui), mais les mutex - qui ne nécessitent rmw, et donc "besoin" de bus les verrous (bien nouveau, il existe d'autres implémentations possibles mais puisque nous sommes déjà à déjà l'hypothèse d'une ancienne obsolète CPU ici, c'est probablement exacte) - sont de beaucoup supérieure? Vous n'avez pas vraiment pense qu'au travers de droit?
    • Juste pour que cela soit clair pour les personnes qui pourraient ne pas être à jour sur l'ordinateur de l'architecture: L'ensemble "bus" verrouillage chose n'a pas été le comportement par défaut pour les Processeurs Intel depuis le Pentium pro qui a été publié 1995. Oui, il peut arriver dans certaines situations particulières, mais c'est tellement rare qu'il peut à peu près ignoré de la plupart des analyses de performance. Moderne Intel dessins n'ont même pas le "bus" nous parlons de plus. Il y a encore des échanges entre les mutex et de verrouillage de code libre, mais le bus serrures sont complètement hors de propos, pour discuter de cette question.
    • Concernant les bus de verrouillage: stackoverflow.com/a/43375643/412080
    • On dirait que vous êtes confus atomicité et de "lock-free" mécanismes. Vous avez besoin plus que cache la cohérence d'utiliser une variable partagée pour la synchronisation. Vous avez besoin de les barrières de la mémoire à préserver l'ordre aussi. Cela va forcer un vidage du cache le plus souvent, et de laisser le Cpu récupérer les données partagées de l'autobus. OK, ce n'est pas un bus de verrouillage, juste une invalidation de cache qui seront diviser votre vitesse d'exécution par beaucoup de choses, si vous gardez spinlocking sur certains synchronisation drapeau.

    InformationsquelleAutor kuroi neko