c++ - semanticas - Adquirir/liberar semántica con 4 hilos.

semantica html ejemplos

Question

Actualmente estoy leyendo C ++ Concurrencia en Acción por Anthony Williams. Uno de sus listados muestra este código, y afirma que la afirmación de que z != 0 puede disparar.

#include <atomic>
#include <thread>
#include <assert.h>
std::atomic<bool> x,y;
std::atomic<int> z;
void write_x()
{
x.store(true,std::memory_order_release);
}
void write_y()
{
y.store(true,std::memory_order_release);
}
void read_x_then_y()
{
while(!x.load(std::memory_order_acquire));
if(y.load(std::memory_order_acquire))
++z;
}
void read_y_then_x()
{
while(!y.load(std::memory_order_acquire));
if(x.load(std::memory_order_acquire))
++z;
}
int main()
{
x=false;
y=false;
z=0;
std::thread a(write_x);
std::thread b(write_y);
std::thread c(read_x_then_y);
std::thread d(read_y_then_x);
a.join();
b.join();
c.join();
d.join();
assert(z.load()!=0);
}

Así que los diferentes caminos de ejecución que puedo pensar son los siguientes:

1)

Thread a (x is now true)
Thread c (fails to increment z)
Thread b (y is now true)
Thread d (increments z) assertion cannot fire

2)

Thread b (y is now true)
Thread d (fails to increment z)
Thread a (x is now true)
Thread c (increments z) assertion cannot fire

3)

Thread a (x is true)
Thread b (y is true)
Thread c (z is incremented) assertion cannot fire
Thread d (z is incremented)

¿Podría alguien explicarme cómo esta afirmación puede disparar?

Él muestra este pequeño gráfico:

¿No debería la tienda para y también sincronizarse con la carga en read_x_then_y , y la tienda para sincronizar con la carga en read_y_then_x ? Estoy muy confundido.

EDITAR:

Gracias por sus respuestas, entiendo cómo funcionan los métodos atómicos y cómo usar Adquirir / Liberar. Simplemente no entiendo este ejemplo específico. Estaba tratando de averiguar si la afirmación se dispara, entonces, ¿qué hizo cada hilo? ¿Y por qué la afirmación nunca se dispara si usamos la consistencia secuencial?

La forma en que estoy razonando sobre esto es que si el thread a ( write_x ) almacena en x entonces todo el trabajo que ha realizado hasta ahora se sincroniza con cualquier otro subproceso que lee x con el orden de adquisición. Una vez que read_x_then_y ve esto, se sale del bucle y lee y . Ahora, 2 cosas podrían pasar. En una opción, write_y ha escrito en y , lo que significa que esta versión se sincronizará con la instrucción if (carga), lo que significa que z se incrementa y la aserción no puede activarse. La otra opción es si write_y no se ha ejecutado todavía, lo que significa que la condición if falla y z no se incrementa. En este escenario, solo x es verdadero e y sigue siendo falso. Una vez que se ejecuta write_y, read_y_then_x se sale de su bucle, sin embargo, tanto x como y son verdaderas y z se incrementa y la afirmación no se activa. No se me ocurre ninguna orden de ejecución o memoria donde z nunca se incremente. ¿Puede alguien explicar dónde mi razonamiento es defectuoso?

Además, sé que la lectura del bucle siempre se realizará antes de la lectura de la instrucción if, ya que la adquisición impide este reordenamiento.

Answer 1

Está pensando en términos de consistencia secuencial, el orden de memoria más fuerte (y predeterminado). Si se utiliza este orden de memoria, todos los accesos a las variables atómicas constituyen un orden total y, de hecho, la aserción no se puede activar.

Sin embargo, en este programa, se utiliza un orden de memoria más débil (liberación de almacenes y adquisición de cargas). Esto significa, por definición, que no puede asumir un orden total de operaciones. En particular, no puede asumir que los cambios sean visibles para otros subprocesos en el mismo orden. (Solo se garantiza un orden total en cada variable individual para cualquier orden de memoria atómica, incluido memory_order_relaxed ).

Los almacenes de x e y producen en subprocesos diferentes, sin sincronización entre ellos. Las cargas de x e y producen en subprocesos diferentes, sin sincronización entre ellos. Esto significa que está totalmente permitido que el hilo c vea x && ! y x && ! y y el hilo d ve y && ! x y && ! x . (Estoy abreviando las cargas adquiridas aquí, no tome esta sintaxis para significar cargas secuencialmente consistentes).

En pocas palabras: una vez que use un orden de memoria más débil que secuencialmente coherente, puede dejar de lado la noción de un estado global de todos los atómicos, que es coherente entre todos los subprocesos, adiós. ¿Cuál es exactamente la razón por la que tantas personas recomiendan mantener la coherencia secuencial a menos que necesite el rendimiento (por cierto, recuerde que debe medir si es aún más rápido) y está seguro de lo que está haciendo? Además, obtener una segunda opinión.

Ahora, si te quemarás con esto, es una pregunta diferente. El estándar simplemente permite un escenario en el que falla la afirmación, en función de la máquina abstracta que se utiliza para describir los requisitos estándar. Sin embargo, su compilador y / o CPU no pueden explotar esta asignación por una razón u otra. Por lo tanto, es posible que para un compilador y una CPU dados, nunca veas que la afirmación se activa, en la práctica. Tenga en cuenta que un compilador o CPU siempre puede usar un orden de memoria más estricto que el que solicitó, ya que esto nunca puede introducir violaciones de los requisitos mínimos de la norma. Es posible que solo le cueste algo de rendimiento, pero eso no está cubierto por el estándar de todos modos.

ACTUALIZACIÓN en respuesta al comentario: El estándar no define un límite superior duro sobre el tiempo que tarda un hilo en ver los cambios en un atómico por otro hilo. Hay una recomendación para los implementadores de que los valores deberían hacerse visibles con el tiempo .

Hay garantías de secuenciación , pero las pertinentes a su ejemplo no impiden que la afirmación se dispare. La garantía básica de liberación de adquisición es que si:

• El hilo e realiza un lanzamiento-almacén a una variable atómica x
• El hilo f realiza una carga de adquisición desde la misma variable atómica
• Luego, si el valor leído por f es el que almacenó e, el almacén en e se sincroniza con la carga en f. Esto significa que cualquier almacén (atómico y no atómico) en e que fue, en este hilo , secuenciado antes del almacén dado a x , es visible para cualquier operación en f, es decir, en este hilo , secuenciado después de la carga dada. [Tenga en cuenta que no hay garantías dadas con respecto a los hilos que no sean estos dos!]

Por lo tanto, no hay garantía de que f lea el valor almacenado por e, a diferencia de, por ejemplo, algún valor anterior de x . Si no lee el valor actualizado, entonces la carga tampoco se sincroniza con el almacén, y no hay garantías de secuencia para ninguna de las operaciones dependientes mencionadas anteriormente.

Yo comparo los atómicos con un orden de memoria menor que el que es secuencialmente consistente con la Teoría de la Relatividad, donde no hay una noción global de simultaneidad .

PD: Dicho esto, una carga atómica no puede simplemente leer un valor antiguo arbitrario. Por ejemplo, si un hilo realiza incrementos periódicos (por ejemplo, con un orden de liberación) de una variable atomic<unsigned> , inicializada en 0, y otro hilo se carga periódicamente desde esta variable (por ejemplo, con un orden de adquisición), entonces, excepto para un ajuste final, el Los valores vistos por este último hilo deben ser monótonamente crecientes. Pero esto se desprende de las reglas de secuenciación dadas: una vez que el último hilo lee un 5, todo lo que sucedió antes del incremento de 4 a 5 se encuentra en el pasado relativo de todo lo que sigue a la lectura de 5. De hecho, una disminución distinta del ajuste es ni siquiera está permitido para memory_order_relaxed , pero este orden de memoria no promete la secuencia relativa (si existe) de los accesos a otras variables.

Answer 2

La sincronización de adquisición-liberación tiene (al menos) esta garantía: los efectos secundarios antes de una liberación en una ubicación de memoria son visibles después de una adquisición en esta ubicación de memoria.

No existe tal garantía si la ubicación de la memoria no es la misma. Y lo que es más importante, no hay una garantía total de pedidos (global).

Mirando el ejemplo, el hilo A hace que el hilo C salga de su bucle, y el hilo B hace que el hilo D salga de su bucle.

Sin embargo, la forma en que una publicación puede "publicarse" en una adquisición (o la forma en que una adquisición puede "observar" una liberación) en la misma ubicación de memoria no requiere una ordenación total. Es posible que el hilo C observe la liberación de A y que el hilo C observe la liberación de B, y solo en el futuro, C observe la liberación de B y que D observe la liberación de A.

El ejemplo tiene 4 hilos porque ese es el ejemplo mínimo que puede forzar ese comportamiento no intuitivo. Si alguna de las operaciones atómicas se hiciera en el mismo hilo, habría una orden que no podría violar.

Por ejemplo, si write_x y write_y sucedieron en el mismo subproceso, se requeriría que cualquier subproceso observado un cambio en y tendría que observar un cambio en x .

De manera similar, si read_x_then_y y read_y_then_x sucedieran en el mismo hilo, observaría que ambos han cambiado en x e y al menos en read_y_then_x .

Tener write_x y read_x_then_y en el mismo hilo no tendría sentido para el ejercicio, ya que sería obvio que no se sincronizaría correctamente, como lo sería tener write_x y read_y_then_x , que siempre leería la última x .

EDITAR:

La forma en que estoy razonando sobre esto es que si el thread a ( write_x ) almacena en x entonces todo el trabajo que ha realizado hasta ahora se sincroniza con cualquier otro subproceso que lee x con el orden de adquisición.

(...) No puedo pensar en ningún orden de ejecución o memoria donde z nunca se incrementa. ¿Puede alguien explicar dónde mi razonamiento es defectuoso?

Además, sé que la lectura del bucle siempre se realizará antes de la lectura de la instrucción if, ya que la adquisición impide este reordenamiento.

Eso es orden secuencialmente consistente, lo que impone un orden total. Es decir, impone que write_x y write_y sean visibles para todos los subprocesos uno tras otro; o bien x entonces y o y luego x , pero el mismo orden para todos los hilos.

Con la liberación de adquisición, no hay orden total. Se garantiza que los efectos de un lanzamiento solo serán visibles para una adquisición correspondiente en la misma ubicación de memoria. Con la adquisición de la write_x se garantiza que los efectos de write_x serán visibles para quien write_x que x ha cambiado.

Esta nota de que algo ha cambiado es muy importante. Si no notas un cambio, no estás sincronizando. Como tal, el hilo C no se está sincronizando en y y el hilo D no se está sincronizando en x .

Esencialmente, es mucho más fácil pensar en la adquisición de versiones como un sistema de notificación de cambios que solo funciona si se sincroniza correctamente. Si no se sincroniza, puede o no observar efectos secundarios.

Las arquitecturas de hardware de modelos de memoria fuertes con coherencia de caché incluso en NUMA, o lenguajes / marcos que se sincronizan en términos de orden total, hacen que sea difícil pensar en estos términos, porque es prácticamente imposible observar este efecto.