Quelles règles exactes du modèle de mémoire C ++ empêchent le réordonnancement avant d’acquérir des opérations?

J’ai une question concernant l’ordre des opérations dans le code suivant:

std::atomic x; std::atomic y; int r1; int r2; void thread1() { y.exchange(1, std::memory_order_acq_rel); r1 = x.load(std::memory_order_relaxed); } void thread2() { x.exchange(1, std::memory_order_acq_rel); r2 = y.load(std::memory_order_relaxed); } 

Étant donné la description de std::memory_order_acquire sur la page cppreference ( https://en.cppreference.com/w/cpp/atomic/memory_order ), cela

Une opération de chargement avec cet ordre de mémoire effectue l’opération d’acquisition sur l’emplacement de mémoire affecté: aucune lecture ni écriture dans le thread en cours ne peuvent être réorganisées avant ce chargement.

il semble évident qu’il ne pourra jamais en résulter que r1 == 0 && r2 == 0 après avoir exécuté thread1 et thread2 .

Cependant, je ne trouve aucun libellé dans la norme C ++ (en examinant le brouillon C ++ 14 actuellement), qui établit la garantie que deux charges détendues ne peuvent pas être réorganisées avec des échanges acquisition-libération. Qu’est-ce que je rate?

EDIT: Comme cela a été suggéré dans les commentaires, il est en fait possible d’obtenir r1 et r2 égaux à zéro. J’ai mis à jour le programme pour utiliser load-acquisition comme suit:

 std::atomic x; std::atomic y; int r1; int r2; void thread1() { y.exchange(1, std::memory_order_acq_rel); r1 = x.load(std::memory_order_acquire); } void thread2() { x.exchange(1, std::memory_order_acq_rel); r2 = y.load(std::memory_order_acquire); } 

Maintenant, est-il possible d’obtenir à la fois r1 et r2 et égaux à 0 après avoir exécuté simultanément thread1 et thread2 ? Si non, quelles règles C ++ empêchent cela?

La norme ne définit pas le modèle de mémoire C ++ en termes de classement des opérations autour d’opérations atomiques avec un paramètre de classement spécifique. Au lieu de cela, pour le modèle de commande Acquérir / Valider, il définit des relations formelles telles que “synchronise avec” et “se produit avant” qui spécifient comment les données sont synchronisées entre les threads.

N4762, §29.4.2 – [atomics.order]

Une opération atomique A qui effectue une opération de libération sur un object atomique M se synchronise avec une opération atomique B qui effectue une opération d’acquisition sur M et tire sa valeur de tout effet secondaire de la séquence de publication précédée de A.

Au § 6.8.2.1-9, la norme indique également que si un magasin A se synchronise avec une charge B, tout ce qui est séquencé avant A inter-thread “se passe avant” tout ce qui est séquencé après B.

Aucune relation “synchronise-avec” (et donc inter-thread n’a lieu avant) n’est établie dans votre deuxième exemple (le premier est encore plus faible) car les relations d’exécution (qui vérifient les valeurs renvoyées par les charges) sont manquantes.
Mais même si vous vérifiiez la valeur de retour, cela ne serait pas utile car les opérations d’ exchange ne «libèrent» rien (c’est-à-dire qu’aucune opération de mémoire n’est séquencée avant ces opérations). Neiter ne fait-il rien acquérir des opérations de charge atomique puisqu’aucune opération n’est séquencée après les charges.

Par conséquent, conformément à la norme, chacun des quatre résultats possibles pour les charges dans les deux exemples (y compris 0 0) est valide. En fait, les garanties données par la norme ne sont pas plus solides que memory_order_relaxed sur toutes les opérations.

Si vous souhaitez exclure le résultat 0 0 dans votre code, les 4 opérations doivent utiliser std::memory_order_seq_cst . Cela garantit un ordre total unique des opérations impliquées.

Dans la version d’origine, il est possible de voir r1 == 0 && r2 == 0 car il n’est pas nécessaire que les magasins soient propagés à l’autre thread avant de le lire. Ce n’est pas une réorganisation des opérations de l’un ou l’autre thread, mais par exemple une lecture de cache obsolète.

 Thread 1's cache | Thread 2's cache x == 0; | x == 0; y == 0; | y == 0; y.exchange(1, std::memory_order_acq_rel); // Thread 1 x.exchange(1, std::memory_order_acq_rel); // Thread 2 

La libération sur le thread 1 est ignorée par le thread 2 et inversement. Dans la machine abstraite, il n’y a pas de cohérence avec les valeurs de x et y sur les threads

 Thread 1's cache | Thread 2's cache x == 0; // stale | x == 1; y == 1; | y == 0; // stale r1 = x.load(std::memory_order_relaxed); // Thread 1 r2 = y.load(std::memory_order_relaxed); // Thread 2 

Vous avez besoin de plus de threads pour obtenir des “violations de causalité” avec des paires acquisition / libération, car les règles de classement normales, combinées aux règles “devient visible dans les effets secondaires”, obligent au moins une des load à afficher 1 .

Sans perte de généralité, supposons que le thread 1 s’exécute en premier.

 Thread 1's cache | Thread 2's cache x == 0; | x == 0; y == 0; | y == 0; y.exchange(1, std::memory_order_acq_rel); // Thread 1 Thread 1's cache | Thread 2's cache x == 0; | x == 0; y == 1; | y == 1; // sync 

La version sur le thread 1 forme une paire avec l’acquisition sur le thread 2, et la machine abstraite décrit un y cohérent sur les deux threads.

 r1 = x.load(std::memory_order_relaxed); // Thread 1 x.exchange(1, std::memory_order_acq_rel); // Thread 2 r2 = y.load(std::memory_order_relaxed); // Thread 2 

dans la commande Release-Acquire pour créer un sharepoint synchronisation entre 2 threads, nous avons besoin d’un object atomique M qui sera identique dans les deux opérations

Une opération atomique A qui effectue une opération de libération sur un object atomique M synchronise avec une opération atomique B qui effectue une opération d’acquisition sur M et tire sa valeur de tout effet secondaire de la séquence de libération précédée de A

ou plus en détail:

Si un magasin atomique dans le fil A est marqué memory_order_release et qu’une charge atomique dans le fil B de la même variable est taguée memory_order_acquire , toutes les écritures en mémoire (non atomiques et atomiques relâchées) qui se sont déroulées avant le magasin atomique du sharepoint vue du fil A , deviennent des effets secondaires visibles dans le fil B C’est-à-dire qu’une fois la charge atomique terminée, le thread B garantie de voir tout le thread A écrit dans la mémoire.

La synchronisation est établie uniquement entre les threads libérant et acquérant la même variable atomique.

  N = u | if (M.load(acquire) == v) :[B] [A]: M.store(v, release) | assert(N == u) 

ici sharepoint synchronisation sur M -release-magasin et charge-acquisition (qui prennent la valeur de store-release!). en tant que résultat stocker N = u dans le thread A (avant la libération du magasin sur M ) visible dans B ( N == u ) après chargement-acquisition sur le même M

si prenons exemple:

 atomic x, y; int r1, r2; void thread_A() { y.exchange(1, memory_order_acq_rel); r1 = x.load(memory_order_acquire); } void thread_B() { x.exchange(1, memory_order_acq_rel); r2 = y.load(memory_order_acquire); } 

Que pouvons-nous sélectionner pour l’object atomique commun M ? dire x ? x.load(memory_order_acquire); sera le sharepoint synchronisation avec x.exchange(1, memory_order_acq_rel) ( memory_order_acq_rel inclut memory_order_release (plus fort) et exchange include store ) si x.load charge une valeur de x.exchange et main sera synchronisée après acquisition (soit dans le code après l’acquisition) rien n’existe) avec les magasins avant la sortie (mais encore avant l’échange rien en code).

solution correcte (chercher presque exactement question ) peut être la suivante:

 atomic x, y; int r1, r2; void thread_A() { x.exchange(1, memory_order_acq_rel); // [Ax] r1 = y.exchange(1, memory_order_acq_rel); // [Ay] } void thread_B() { y.exchange(1, memory_order_acq_rel); // [By] r2 = x.exchange(1, memory_order_acq_rel); // [Bx] } 

supposons que r1 == 0 .

Toutes les modifications apscopes à une variable atomique particulière se produisent dans un ordre total spécifique à cette variable atomique.

nous avons 2 modification de y : [Ay] et [By] . parce que r1 == 0 cela signifie que [Ay] se produit avant [By] dans l’ordre de modification total de y . à partir de ceci – [By] lire la valeur stockée par [Ay] . alors nous avons ensuite:

  • A est écrit à x[Ax]
  • Après avoir libéré magasin [Ay] à y ( acq_rel include release , échange include store )
  • B charge acquérir de y (valeur [By] stockée par [Ay]
  • une fois la charge atomique acquise (sur y ) terminée, le thread B garantie de voir tout le thread A écrit dans la mémoire avant la libération de magasin (sur y ). il voit donc l’effet secondaire de [Ax] – et r2 == 1

une autre solution possible utilise atomic_thread_fence

 atomic x, y; int r1, r2; void thread_A() { x.store(1, memory_order_relaxed); // [A1] atomic_thread_fence(memory_order_acq_rel); // [A2] r1 = y.exchange(1, memory_order_relaxed); // [A3] } void thread_B() { y.store(1, memory_order_relaxed); // [B1] atomic_thread_fence(memory_order_acq_rel); // [B2] r2 = x.exchange(1, memory_order_relaxed); // [B3] } 

encore une fois parce que toutes les modifications de la variable atomique y se produisent dans un ordre total. [A3] sera avant [B1] ou inversement.

  1. si [B1] avant [A3][A3] lit une valeur enregistrée par [B1] => r1 == 1 .

  2. si [A3] avant [B1] – la valeur [B1] est lue par [A3] et à partir de la synchronisation clôture-clôture :

Une clôture de libération [A2] dans le thread A synchronise avec une clôture d’acquisition [B2] dans le thread B , si:

  • Il existe un object atomique y ,
  • Il existe une écriture atomique [A3] (avec n’importe quel ordre de mémoire) modifiant y dans le thread A
  • [A2] est séquencé avant [A3] dans le thread A
  • Il existe une lecture atomique [B1] (avec n’importe quel ordre de mémoire) dans le thread B

  • [B1] lit la valeur écrite par [A3]

  • [B1] est séquencé avant [B2] dans le thread B

Dans ce cas, tous les magasins ( [A1] ) séquencés avant [A2] dans le thread A se produiront avant toutes les charges ( [B3] ) à partir des mêmes emplacements ( x ) créés dans le thread B après [B2]

donc [A1] (magasin 1 à x) sera avant et aura un effet visible pour [B3] (charger le formulaire x et enregistrer le résultat dans r2 ). donc sera chargé 1 de x et r2==1

 [A1]: x = 1 | if (y.load(relaxed) == 1) :[B1] [A2]: ### release ### | ### acquire ### :[B2] [A3]: y.store(1, relaxed) | assert(x == 1) :[B3] 

Vous avez déjà une réponse à la partie juriste linguistique. Mais je veux répondre à la question connexe de savoir comment comprendre pourquoi cela peut être possible dans asm sur une architecture de processeur possible qui utilise LL / SC pour l’atomique RMW .

C ++ 11 n’a aucun sens à interdire cette réorganisation: cela exigerait une barrière de chargement de magasin dans ce cas où certaines architectures de CPU pourraient en éviter une.

Cela pourrait être possible avec de vrais compilateurs sur PowerPC, étant donné la façon dont ils mappent les ordres de mémoire C ++ 11 aux instructions asm.

Sur PowerPC64, une fonction avec un échange acq_rel et une charge d’acquisition (en utilisant des arguments de pointeur au lieu de variables statiques) est gcc6.3 -O3 -mregnames comme suit avec les gcc6.3 -O3 -mregnames de gcc6.3 -O3 -mregnames . Cela provient d’une version C11 parce que je voulais examiner les résultats clang pour MIPS et SPARC, et la configuration clang de Godbolt fonctionne pour C11 mais échoue pour C ++ 11 lorsque vous utilisez -target sparc64 .

(source + asm sur Godbolt pour MIPS32R6, SPARC64, ARM 32 et PowerPC64. )

 foo: lwsync # with seq_cst exchange this is full sync, not just lwsync # gone if we use exchage with mo_acquire or relaxed # so this barrier is providing release-store ordering li %r9,1 .L2: lwarx %r10,0,%r4 # load-linked from 0(%r4) stwcx. %r9,0,%r4 # store-conditional 0(%r4) bne %cr0,.L2 # retry if SC failed isync # missing if we use exchange(1, mo_release) or relaxed ld %r3,0(%r3) # 64-bit load double-word of *a cmpw %cr7,%r3,%r3 bne- %cr7,$+4 # skip over the isync if something about the load? PowerPC is weird isync # make the *a load a load-acquire blr 

isync n’est pas une barrière de charge de magasin; il suffit que les instructions précédentes soient complétées localement (retrait de la partie en panne du kernel). Il n’attend pas que le tampon de magasin soit vidé afin que les autres threads puissent voir les magasins précédents.

Ainsi, le magasin SC ( stwcx. ) stwcx. partie de l’échange peut être stwcx. dans le tampon de magasin et devenir globalement visible après la charge d’acquisition pure qui le suit. En fait, un autre Q & A a déjà posé cette question et la réponse est que nous pensons que cette réorganisation est possible. Est-ce que `isync` empêche la réorganisation Store-Load sur le CPU PowerPC?

Si la charge pure est seq_cst , PowerPC64 gcc met une sync avant le ld . Effectuer l’ exchange seq_cst n’empêche pas la réorganisation. N’oubliez pas que C ++ 11 ne garantit qu’un seul ordre total pour les opérations SC, de sorte que l’échange et la charge doivent tous deux être SC pour C ++ 11 pour le garantir.

Donc, PowerPC possède un mappage inhabituel de C ++ 11 à asm pour atomics. La plupart des systèmes mettent les barrières les plus lourdes sur les magasins, permettant ainsi aux charges seq-cst d’être moins chères ou n’ayant une barrière que d’un côté. Je ne sais pas si cela était nécessaire pour la commande de mémoire très faible de PowerPC, ou si un autre choix était possible.

https://www.cl.cam.ac.uk/~pes20/cpp/cpp0xmappings.html montre quelques implémentations possibles sur différentes architectures. Il mentionne de multiples alternatives pour ARM.


Sur AArch64, nous obtenons ceci pour la version C ++ d’origine de thread1:

 thread1(): adrp x0, .LANCHOR0 mov w1, 1 add x0, x0, :lo12:.LANCHOR0 .L2: ldaxr w2, [x0] @ load-linked with acquire semantics stlxr w3, w1, [x0] @ store-conditional with sc-release semantics cbnz w3, .L2 @ retry until exchange succeeds add x1, x0, 8 @ the comstackr noticed the variables were next to each other ldar w1, [x1] @ load-acquire str w1, [x0, 12] @ r1 = load result ret 

La réorganisation ne peut pas se produire là-bas, car les magasins de version AArch64 sont à libération séquentielle , et non à libération simple. Cela signifie qu’ils ne peuvent pas réorganiser avec des chargements ultérieurs.

Mais sur une machine hypothétique qui possède également ou à la place des atomes LL / SC à libération brute, il est facile de voir qu’un acq_rel n’arrête pas les chargements ultérieurs vers différentes lignes de cache de devenir globalement visibles après le LL mais avant le SC de l’échange.


Si exchange est implémenté avec une transaction unique comme sur x86, si chargement et stockage sont adjacents dans l’ordre global des opérations en mémoire, aucune opération ultérieure ne peut être réorganisée avec un échange acq_rel et est fondamentalement équivalente à seq_cst .

Mais LL / SC n’a pas besoin d’être une vraie transaction atomique pour donner à RMW l’atomicité de cet emplacement .

En fait, une seule instruction swap asm aurait pu assouplir la sémantique ou acq_rel. SPARC64 a besoin d’instructions de membar autour de son instruction d’ swap . Ainsi, contrairement à xchg de x86, ce n’est pas seq-cst par lui-même. (SPARC possède une mnémonique très lisible et lisible par l’homme, surtout par rapport à PowerPC. En principe, tout est plus lisible que PowerPC.)

Ainsi, il n’a aucun sens de demander à C ++ 11 de le faire: cela nuirait à une implémentation sur un CPU qui n’aurait autrement pas besoin d’une barrière de chargement de magasin.