Problemas de ordenación de memoria

Question

Estoy experimentando con el soporte de C++ 0x y hay un problema, que supongo que no debería estar allí. O no entiendo el tema o gcc tiene un error.

Tengo el siguiente código, inicialmente x y y son iguales. El hilo 1 siempre incrementa x primero y luego incrementa y. Ambos son valores enteros atómicos, por lo que no hay ningún problema con el incremento en absoluto. El hilo 2 está comprobando si el x es menor que y y muestra un mensaje de error si es así.

Este código falla a veces, pero ¿por qué? El problema aquí es probablemente el reordenamiento de la memoria, pero todas las operaciones atómicas son consecutivamente consistentes por defecto y no me relajé explícitamente de esas operaciones. Estoy compilando este código en x86, que, por lo que sé, no debería tener problemas con el pedido. ¿Puedes explicar cuál es el problema?

#include <iostream> 
#include <atomic> 
#include <thread> 

std::atomic_int x; 
std::atomic_int y; 

void f1() 
{ 
    while (true) 
    { 
     ++x; 
     ++y; 
    } 
} 

void f2() 
{ 
    while (true) 
    { 
     if (x < y) 
     { 
      std::cout << "error" << std::endl; 
     } 
    } 
} 

int main() 
{ 
    x = 0; 
    y = 0; 

    std::thread t1(f1); 
    std::thread t2(f2); 

    t1.join(); 
    t2.join(); 
} 

El resultado se puede ver here.

Answer 1

El problema podría estar en su prueba:

if (x < y) 

el hilo podría evaluar x y no moverse a evaluar y hasta mucho más tarde.

Answer 2

Hay un problema con la comparación:

x < y 

El orden de evaluación de subexpresiones (en este caso, de x y y) no se especifica, por lo y pueden ser evaluados antes de x o x se puede evaluar antes de y.

Si x se lee en primer lugar, tiene un problema:

x = 0; y = 0; 
t2 reads x (value = 0); 
t1 increments x; x = 1; 
t1 increments y; y = 1; 
t2 reads y (value = 1); 
t2 compares x < y as 0 < 1; test succeeds! 

Si se asegura explícitamente que y se lee en primer lugar, se puede evitar el problema:

int yval = y; 
int xval = x; 
if (xval < yval) { /* ... */ } 

Answer 3

En primer lugar, estoy de acuerdo con "Michael Burr" y "James McNellis". Su prueba no es justa, y existe una posibilidad legítima de fallar. Sin embargo, incluso si reescribe la prueba de la manera en que "James McNellis" sugiere que la prueba puede fallar.

La primera razón para esto es que no usa semántica volatile, por lo tanto, el compilador puede hacer optimizaciones para su código (que se supone que está bien en un caso de subproceso único).

Pero incluso con volatile no se garantiza que su código funcione.

Creo que no entiende completamente el concepto de reordenación de memoria. En realidad, el reorden de lectura/escritura de memoria puede ocurrir en dos niveles:

1. El compilador puede cambiar el orden de las instrucciones de lectura/escritura generadas.
2. La CPU puede ejecutar instrucciones de lectura/escritura de memoria en orden arbitrario.

El uso de volatile impide que (1). Sin embargo, no ha hecho nada para evitar (2) la reordenación del acceso a la memoria mediante el hardware .

para evitar que esto se debería poner especial valla memoria instrucciones en el código (que se designan para la CPU, a diferencia de volatile que es para compilador sólo).

En x86/x64 hay muchas instrucciones diferentes para la valla de memoria. Además, cada instrucción con semántica lock de forma predeterminada emite una valla de memoria completa.

Más información aquí:

http://en.wikipedia.org/wiki/Memory_barrier

Answer 4

De vez en cuando, x envolverá a 0 justo antes y se envuelve alrededor de cero. En este punto, y será legítimamente mayor que x.