¿Cómo lograr una barrera StoreLoad en C ++ 11?

Quiero escribir código portátil (Intel, ARM, PowerPC ...) que resuelve una variante de un problema clásico:

Initially: X=Y=0

Thread A:
  X=1
  if(!Y){ do something }
Thread B:
  Y=1
  if(!X){ do something }

en el que el objetivo es evitar una situación en la que ambos hilos están haciendosomething . (Está bien si ninguna de las dos cosas funciona; este no es un mecanismo de ejecutar exactamente una vez). Corríjame si ve algunos defectos en mi razonamiento a continuación.

Soy consciente de que puedo lograr el objetivo con memory_order_seq_cstatomic storesys de loadla siguiente manera:

std::atomic<int> x{0},y{0};
void thread_a(){
  x.store(1);
  if(!y.load()) foo();
}
void thread_b(){
  y.store(1);
  if(!x.load()) bar();
}

que logra el objetivo, porque debe haber un orden total único en los
{x.store(1), y.store(1), y.load(), x.load()}eventos, que debe estar de acuerdo con el orden del programa "bordes"

• x.store(1) "en TO es antes" y.load()
• y.store(1) "en TO es antes" x.load()

y si foo()fue llamado, entonces tenemos ventaja adicional:

• y.load() "lee el valor antes" y.store(1)

y si bar()fue llamado, entonces tenemos ventaja adicional:

• x.load() "lee el valor antes" x.store(1)

y todos estos bordes combinados juntos formarían un ciclo:

x.store(1)"en TO es antes" y.load()"lee el valor antes" y.store(1)"en TO es antes" x.load()"lee el valor antes"x.store(true)

lo que viola el hecho de que las órdenes no tienen ciclos.

Intencionalmente uso términos no estándar "en TO is before" y "lee el valor antes" en lugar de términos estándar como happens-before, porque quiero solicitar comentarios sobre la exactitud de mi suposición de que estos bordes realmente implican happens-beforerelación, se pueden combinar en un solo gráfico, y el ciclo en dicho gráfico combinado está prohibido. No estoy seguro de eso. Lo que sé es que este código produce barreras correctas en Intel gcc & clang y en ARM gcc

Ahora, mi verdadero problema es un poco más complicado, porque no tengo control sobre "X": está oculto detrás de algunas macros, plantillas, etc. y podría ser más débil que seq_cst

Ni siquiera sé si "X" es una variable única, o algún otro concepto (por ejemplo, un semáforo o mutex ligero). Todo lo que sé es que tengo dos macros set()y check()eso check()devuelve true"después" de que haya llamado otro hilo set(). (Se está también sabe que sety checkson hilos de proceso seguro y no puede crear UB-carrera de datos).

Entonces, conceptualmente set()es algo así como "X = 1" y check()es como "X", pero no tengo acceso directo a los atómicos involucrados, si los hay.

void thread_a(){
  set();
  if(!y.load()) foo();
}
void thread_b(){
  y.store(1);
  if(!check()) bar();
}

Estoy preocupado, eso set()podría implementarse internamente como x.store(1,std::memory_order_release)y / ocheck() podría ser x.load(std::memory_order_acquire). O hipotéticamente std::mutexque un hilo se está desbloqueando y otro está try_locking; en el estándar ISO std::mutexsolo se garantiza que tiene pedidos de adquisición y liberación, no seq_cst.

Si este es el caso, entonces check()si el cuerpo puede ser "reordenado" antes y.store(true)( Ver la respuesta de Alex donde demuestran que esto sucede en PowerPC ).
Esto sería realmente malo, ya que ahora esta secuencia de eventos es posible:

• thread_b()primero carga el valor anterior de x( 0)
• thread_a() ejecuta todo incluido foo()
• thread_b() ejecuta todo incluido bar()

Entonces, ambos foo()y bar()me llamaron, lo que tuve que evitar. ¿Cuáles son mis opciones para evitar eso?

Opcion A

Intente forzar la barrera Tienda-Carga. Esto, en la práctica, se puede lograr std::atomic_thread_fence(std::memory_order_seq_cst);, como explica Alex en una respuesta diferente, todos los compiladores probados emitieron una valla completa:

• x86_64: MFENCE
• PowerPC: hwsync
• Itanuim: mf
• ARMv7 / ARMv8: dmb ish
• MIPS64: sincronización

El problema con este enfoque es que no pude encontrar ninguna garantía en las reglas de C ++, que std::atomic_thread_fence(std::memory_order_seq_cst)debe traducirse en una barrera de memoria completa. En realidad, el concepto de atomic_thread_fences en C ++ parece estar en un nivel diferente de abstracción que el concepto de ensamblaje de barreras de memoria y se ocupa más de cosas como "qué operación atómica se sincroniza con qué". ¿Hay alguna prueba teórica de que la siguiente implementación logre el objetivo?

void thread_a(){
  set();
  std::atomic_thread_fence(std::memory_order_seq_cst)
  if(!y.load()) foo();
}
void thread_b(){
  y.store(true);
  std::atomic_thread_fence(std::memory_order_seq_cst)
  if(!check()) bar();
}

Opcion B

Use el control que tenemos sobre Y para lograr la sincronización, usando operaciones de lectura-modificación-escritura memory_order_acq_rel en Y:

void thread_a(){
  set();
  if(!y.fetch_add(0,std::memory_order_acq_rel)) foo();
}
void thread_b(){
  y.exchange(1,std::memory_order_acq_rel);
  if(!check()) bar();
}

La idea aquí es que los accesos a un solo atómico ( y) deben formarse en un solo orden en el que todos los observadores estén de acuerdo, por lo que fetch_addes anterior exchangeo viceversa.

Si fetch_addes antes, exchangeentonces la parte "liberar" se fetch_addsincroniza con la parte "adquirir" exchangey, por lo tanto, todos los efectos secundarios set()deben ser visibles para la ejecución del código check(), por bar()lo que no se llamará.

De lo contrario, exchangees antes fetch_add, luego fetch_addverá 1y no llamará foo(). Entonces, es imposible llamar a ambos foo()y bar(). ¿Es correcto este razonamiento?

Opcion C

Use atómica ficticia para introducir "bordes" que eviten el desastre. Considere el siguiente enfoque:

void thread_a(){
  std::atomic<int> dummy1{};
  set();
  dummy1.store(13);
  if(!y.load()) foo();
}
void thread_b(){
  std::atomic<int> dummy2{};
  y.store(1);
  dummy2.load();
  if(!check()) bar();
}

Si crees que el problema aquí es que los atomics son locales, entonces imagínate moverlos a un alcance global, en el siguiente razonamiento no parece importarme, y escribí el código intencionalmente para exponer lo gracioso que es ese muñeco1 y dummy2 están completamente separados.

¿Por qué demonios esto podría funcionar? Bueno, debe haber un orden total único {dummy1.store(13), y.load(), y.store(1), dummy2.load()}que debe ser coherente con los "bordes" del orden del programa:

• dummy1.store(13) "en TO es antes" y.load()
• y.store(1) "en TO es antes" dummy2.load()

(Con suerte, una seq_cst store + load forma el equivalente en C ++ de una barrera de memoria completa que incluye StoreLoad, como lo hacen en asm en ISA reales, incluso AArch64, donde no se requieren instrucciones de barrera separadas).

Ahora, tenemos dos casos a considerar: cualquiera y.store(1)es antesy.load() o después en el orden total.

Si y.store(1)es antes, y.load()entonces foo()no se llamará y estamos a salvo.

Si y.load()es antes y.store(1), luego combinándolo con los dos bordes que ya tenemos en orden de programa, deducimos que:

• dummy1.store(13) "en TO es antes" dummy2.load()

Ahora, dummy1.store(13)es una operación de liberación, que libera los efectos de set(), y dummy2.load()es una operación de adquisición, por lo que check()debería ver los efectos set()y, por bar()lo tanto , no se llamará y estamos a salvo.

¿Es correcto pensar aquí que check()verá los resultados de set()? ¿Puedo combinar los "bordes" de varios tipos ("orden del programa", también conocido como Secuenciado antes, "orden total", "antes del lanzamiento", "después de adquirir") de esa manera? Tengo serias dudas sobre esto: las reglas de C ++ parecen hablar de relaciones "sincronizadas con" entre la tienda y la carga en la misma ubicación; aquí no existe tal situación.

Tenga en cuenta que solo nos preocupa el caso en el que dumm1.storese sabe (a través de otro razonamiento) que está antes dummy2.loaden el orden total seq_cst. Entonces, si hubieran estado accediendo a la misma variable, la carga habría visto el valor almacenado y sincronizado con él.

(El razonamiento de barrera de memoria / reordenamiento para implementaciones donde las cargas y almacenes atómicos se compilan en al menos barreras de memoria de 1 vía (y las operaciones seq_cst no pueden reordenarse: por ejemplo, una tienda seq_cst no puede pasar una carga seq_cst) es que cualquier carga / las tiendas después dummy2.loaddefinitivamente se vuelven visibles para otros hilos después y.store . Y de manera similar para el otro hilo, ... antes y.load).

Puedes jugar con mi implementación de las Opciones A, B, C en https://godbolt.org/z/u3dTa8

Las opciones A y B son soluciones válidas.

• Opción A: en realidad no importa a qué se traduzca una cerca seq-cst, el estándar C ++ define claramente qué garantías ofrece. Los he presentado en esta publicación: ¿ Cuándo es útil una cerca memory_order_seq_cst?
• Opción B: sí, su razonamiento es correcto. Todas las modificaciones en algún objeto tienen un orden total único (el orden de modificación), por lo que puede usarlo para sincronizar los hilos y garantizar la visibilidad de todos los efectos secundarios.

Sin embargo, la opción C no es válida! Una relación de sincronización con solo puede establecerse mediante operaciones de adquisición / liberación en el mismo objeto . En el caso de tener dos objetos completamente diferentes y indepent dummy1y dummy2. Pero estos no se pueden utilizar para establecer una relación antes de que suceda. De hecho, dado que las variables atómicas son puramente locales (es decir, solo son tocadas por un hilo), el compilador es libre de eliminarlas según la regla as-if .

Actualizar

Opción A:
supongo set()y check()opero con algún valor atómico. Entonces tenemos la siguiente situación (-> denota secuenciado antes ):

• set()-> fence1(seq_cst)->y.load()
• y.store(true)-> fence2(seq_cst)->check()

Entonces podemos aplicar la siguiente regla:

Para las operaciones atómicas A y B en un objeto atómico M , donde A modifica M y B toma su valor, si hay memory_order_seq_cstcercas X e Y de modo que A se secuencia antes de X , Y se secuencia antes de B y X precede a Y en S , entonces B observa los efectos de A o una modificación posterior de M en su orden de modificación.

Es decir, check()ve ese valor almacenado seto y.load()ve el valor escrito be y.store()(las operaciones ypueden incluso usarse memory_order_relaxed).

Opción C:
El C ++ 17 estándar estados [32.4.3, P1347]:

Habrá un solo pedido total S en todas las memory_order_seq_cstoperaciones, de conformidad con el pedido "antes de" y los pedidos de modificación para todas las ubicaciones afectadas [...]

La palabra importante aquí es "consistente". Esto implica que si una operación Una sucede-antes de una operación B , entonces A debe preceder B en S . Sin embargo, la implicación lógica es una calle de dirección, por lo que no podemos inferir la inversa: sólo porque algunas de operación C precede a una operación D en S no implica que C pasa antes D .

En particular, dos operaciones seq-cst en dos objetos separados no se pueden usar para establecer una relación antes de que ocurra, aunque las operaciones estén totalmente ordenadas en S. Si desea ordenar operaciones en objetos separados, debe consultar seq-cst - Cercas (ver Opción A).

En el primer ejemplo, y.load()leer 0 no implica que eso y.load()ocurra antes y.store(1).

Sin embargo, implica que es anterior en el orden total único gracias a la regla de que una carga seq_cst devuelve el valor de la última tienda seq_cst en la orden total o el valor de alguna tienda no seq_cst que no sucede antes (que en este caso no existe). Entonces, si y.store(1)fue anterior al y.load()orden total, y.load()habría devuelto 1.

La prueba sigue siendo correcta porque el pedido total único no tiene un ciclo.

¿Qué tal esta solución?

std::atomic<int> x2{0},y{0};

void thread_a(){
  set();
  x2.store(1);
  if(!y.load()) foo();
}

void thread_b(){
  y.store(1);
  if(!x2.load()) bar();
}

@mpoeter explicó por qué las opciones A y B son seguras.

En la práctica en implementaciones reales, creo que la opción A solo necesita std::atomic_thread_fence(std::memory_order_seq_cst)en el hilo A, no en B.

Las tiendas seq-cst en la práctica incluyen una barrera de memoria completa, o en AArch64 al menos no se puede reordenar con cargas posteriores de adquisición o seq_cst ( stlrla liberación secuencial debe drenarse del búfer de la tienda antes de ldarpoder leer de la memoria caché).

Las asignaciones de C ++ -> asm tienen la opción de poner el costo de drenar el búfer de la tienda en tiendas atómicas o cargas atómicas. La opción correcta para implementaciones reales es hacer que las cargas atómicas sean baratas, por lo que las tiendas seq_cst incluyen una barrera completa (incluido StoreLoad). Mientras que las cargas seq_cst son las mismas que las cargas adquiridas en la mayoría.

(Pero no POWER; incluso las cargas necesitan sincronización pesada = barrera completa para detener el reenvío de la tienda desde otros subprocesos SMT en el mismo núcleo, lo que podría conducir a un reordenamiento IRIW, porque seq_cst requiere que todos los subprocesos puedan estar de acuerdo en el orden de todas las operaciones seq_cst. ¿Se verán dos escrituras atómicas en diferentes ubicaciones en diferentes hilos siempre en el mismo orden por otros hilos? )

(Por supuesto, para una garantía formal de seguridad, necesitamos una cerca en ambos para promover adquirir / liberar set () -> check () en un seq_cst sincroniza con. También funcionaría para un set relajado, creo, pero un el control relajado podría reordenarse con la barra del POV de otros hilos).

Creo que el verdadero problema con la Opción C es que depende de algún observador hipotético que pueda sincronizarse con ylas operaciones ficticias. Y, por lo tanto, esperamos que el compilador conserve ese orden al hacer asm para un ISA basado en barreras.

Esto será cierto en la práctica en ISA reales; ambos hilos incluyen una barrera completa o equivalente y los compiladores (todavía) no optimizan los átomos. Pero, por supuesto, "compilar a un ISA basado en barreras" no forma parte del estándar ISO C ++. La memoria caché compartida coherente es el observador hipotético que existe para el razonamiento asm pero no para el razonamiento ISO C ++.

Para que la Opción C funcione, necesitamos un pedido como dummy1.store(13);/ y.load()/ set();(como se ve en el Hilo B) para violar alguna regla ISO C ++ .

El hilo que ejecuta estas declaraciones tiene que comportarse como si se set() ejecutara primero (debido a Sequenced Before). Eso está bien, el pedido de memoria en tiempo de ejecución y / o el reordenamiento de las operaciones en tiempo de compilación aún podrían hacerlo.

Las dos operaciones seq_cst d1=13y yson consistentes con la secuencia anterior (orden del programa). set()no participa en el orden global requerido para existir para las operaciones seq_cst porque no es seq_cst.

El subproceso B no se sincroniza con dummy1.store, por lo que no ocurre ningún requisito previo en setrelación con d1=13aplica , a pesar de que esa asignación es una operación de liberación.

No veo ninguna otra violación posible de las reglas; No puedo encontrar nada aquí que sea necesario para ser coherente con setSequenced-Before d1=13.

El razonamiento "dummy1.store releases set ()" es el defecto. Ese orden solo se aplica a un observador real que se sincroniza con él o en asm. Como @mpoeter respondió, la existencia del orden total seq_cst no crea ni implica relaciones antes de pasar, y eso es lo único que garantiza formalmente el pedido fuera de seq_cst.

Cualquier tipo de CPU "normal" con caché compartida coherente donde este reordenamiento realmente podría ocurrir en tiempo de ejecución no parece plausible. (Pero si un compilador pudiera eliminar dummy1y dummy2luego claramente tendríamos un problema, y ​​creo que eso está permitido por el estándar).

Pero dado que el modelo de memoria C ++ no está definido en términos de un búfer de almacenamiento, caché coherente compartida o pruebas de tornasol de reordenamiento permitido, las reglas de C ++ no requieren formalmente las cosas requeridas por la cordura. Esto es quizás intencional para permitir la optimización incluso de las variables seq_cst que resultan ser hilos privados. (Los compiladores actuales no hacen eso, por supuesto, ni ninguna otra optimización de objetos atómicos).

Una implementación en la que un hilo realmente podía ver el set()último mientras que otro podía ver los set()primeros sonidos inverosímiles. Ni siquiera el PODER podría hacer eso; tanto seq_cst load como store incluyen barreras completas para POWER. (Había sugerido en los comentarios que el reordenamiento de IRIW podría ser relevante aquí; las reglas acq / rel de C ++ son lo suficientemente débiles como para acomodar eso, pero la falta total de garantías fuera de las situaciones de sincronización con otras situaciones anteriores es mucho más débil que cualquier HW. )

C ++ no garantiza nada para non-seq_cst a menos que realmente haya un observador, y solo para ese observador. Sin uno estamos en territorio de gatos de Schroedinger. O, si dos árboles caen en el bosque, ¿se cayó uno antes que el otro? (Si es un gran bosque, la relatividad general dice que depende del observador y que no existe un concepto universal de simultaneidad).

@mpoeter sugirió que un compilador podría incluso eliminar la carga ficticia y almacenar operaciones, incluso en objetos seq_cst.

Creo que puede ser correcto cuando pueden probar que nada puede sincronizarse con una operación. por ejemplo, un compilador que puede ver que dummy2no escapa a la función probablemente puede eliminar esa carga seq_cst.

Esto tiene al menos una consecuencia en el mundo real: si compila para AArch64, eso permitiría que una tienda seq_cst anterior se reordene en la práctica con operaciones relajadas posteriores, lo que no hubiera sido posible con una tienda seq_cst + carga que drena el búfer de la tienda antes de cualquier cargas posteriores podrían ejecutarse.

Por supuesto, los compiladores actuales no optimizan los atómicos, a pesar de que ISO C ++ no lo prohíbe; Ese es un problema no resuelto para el comité de normas.

Creo que esto está permitido porque el modelo de memoria C ++ no tiene un observador implícito o un requisito de que todos los hilos estén de acuerdo en ordenar. Proporciona algunas garantías basadas en cachés coherentes, pero no requiere visibilidad para que todos los hilos sean simultáneos.

en el estándar ISO std :: mutex solo se garantiza que tiene orden de adquisición y liberación, no seq_cst.

Pero no se garantiza que nada tenga "orden seq_cst", ya seq_cstque no es propiedad de ninguna operación.

seq_cstes una garantía sobre todas las operaciones de una implementación dada std::atomico una clase atómica alternativa. Como tal, su pregunta no es sólida.