modelo de memoria C++ 0x y cargas/almacenes especulativos

Question

Estaba leyendo sobre el modelo de memoria que forma parte del próximo estándar C++ 0x. Sin embargo, estoy un poco confundido sobre algunas de las restricciones de lo que el compilador puede hacer, específicamente sobre cargas y tiendas especulativas.

Para empezar, algunas de las cosas relevantes:

Hans Boehm's pages about threads and the memory model in C++0x

Boehm, "Threads Cannot be Implemented as a Library"

Boehm and Adve, "Foundations of the C++ Concurrency Memory Model"

Sutter, "Prism: A Principle-Based Sequential Memory Model for Microsoft Native Code Platforms", N2197

Boehm, "Concurrency memory model compiler consequences", N2338

Ahora, la idea básica es esencialmente "Consistencia Secuencial para Programas Libres de Raza de Datos", que parece ser un compromiso decente entre la facilidad de programación y la optimización del compilador y las oportunidades de hardware. Se define que una carrera de datos se produce si no se ordenan dos accesos a la misma ubicación de memoria por diferentes subprocesos, al menos uno de ellos almacena en la ubicación de memoria, y al menos uno de ellos no es una acción de sincronización. Implica que todo acceso de lectura/escritura a datos compartidos debe realizarse a través de algún mecanismo de sincronización, como mutexes u operaciones en variables atómicas (bueno, es posible operar en las variables atómicas con pedido de memoria relajado solo para expertos, pero predeterminado proporciona consistencia secuencial).

En vista de esto, estoy confundido acerca de las restricciones sobre cargas/tiendas espurias o especulativas en variables comunes compartidas. Por ejemplo, en N2338 tenemos el ejemplo

switch (y) { 
    case 0: x = 17; w = 1; break; 
    case 1: x = 17; w = 3; break; 
    case 2: w = 9; break; 
    case 3: x = 17; w = 1; break; 
    case 4: x = 17; w = 3; break; 
    case 5: x = 17; w = 9; break; 
    default: x = 17; w = 42; break; 
} 

que no se permite que el compilador de transformarse en

tmp = x; x = 17; 
switch (y) { 
    case 0: w = 1; break; 
    case 1: w = 3; break; 
    case 2: x = tmp; w = 9; break; 
    case 3: w = 1; break; 
    case 4: w = 3; break; 
    case 5: w = 9; break; 
    default: w = 42; break; 
} 

ya que si y == 2 hay una escritura falsa ax que podría ser un problema si otro hilo estaba actualizando simultáneamente x. Pero, ¿por qué es esto un problema? Esta es una carrera de datos, que está prohibida de todos modos; en este caso, el compilador lo empeora escribiendo a x dos veces, pero incluso una sola escritura sería suficiente para una carrera de datos, ¿no? Es decir. un programa apropiado de C++ 0x necesitaría sincronizar el acceso a x, en cuyo caso ya no existiría la carrera de datos, y la tienda falsa tampoco sería un problema?

Estoy igualmente confundido sobre el Ejemplo 3.1.3 en N2197 y algunos de los otros ejemplos también, pero tal vez una explicación para el problema anterior también lo explique.

EDIT: La respuesta:

La razón por la cual las tiendas especulativos son un problema es que en el ejemplo instrucción switch anterior, el programador podría haber elegido para adquirir condicionalmente la cerradura proteger x sólo si y = 2! . Por lo tanto, la tienda especulativa podría introducir una raza de datos que no estaba allí en el código original, y la transformación está, por lo tanto, prohibida. El mismo argumento se aplica al ejemplo 3.1.3 en N2197 también.

Answer 1

No estoy familiarizado con todas las cosas a las que hace referencia, pero observe que en el caso y == 2, en el primer bit de código, x no está escrito en absoluto (o leído, para el caso) . En el segundo bit de código, está escrito dos veces. Esto es más una diferencia que simplemente escribir una vez vs. escribir dos veces (al menos, es en modelos de subprocesos existentes como pthreads).Además, almacenar un valor que de otro modo no se almacenaría en absoluto es más una diferencia que simplemente almacenar una vez y almacenar dos veces. Por estos dos motivos, no desea que los compiladores simplemente reemplacen un no-operativo con tmp = x; x = 17; x = tmp;.

Supongamos que el subproceso A quiere suponer que ningún otro subproceso modifica x. Es razonable querer que se le permita esperar que si y es 2, y escribe un valor en x, luego lo vuelve a leer, recuperará el valor que ha escrito. Pero si el hilo B está ejecutando al mismo tiempo su segundo bit de código, el hilo A podría escribir en x y luego leerlo, y recuperar el valor original, porque el hilo B guardó "antes" de la escritura y restauró "después". O podría volver a 17, porque el hilo B almacenó 17 "después de" la escritura, y volvió a almacenar el tmp "después de" lee el hilo A. El subproceso A puede hacer la sincronización que quiera, y no ayuda, porque el subproceso B no está sincronizado. La razón por la que no está sincronizado (en el caso y == 2) es que no está utilizando x. Entonces, el concepto de si un determinado bit de código "usa x" es importante para el modelo de subprocesamiento, lo que significa que no se puede permitir que los compiladores cambien el código para usar x cuando "no debería".

En resumen, si se permite la transformación que usted propone, introduciendo una escritura espuria, entonces nunca será posible analizar un poco de código y concluir que no modifica x (ni ninguna otra ubicación de memoria). Hay una serie de modismos convenientes que, por lo tanto, serían imposibles, como compartir datos inmutables entre hilos sin sincronización.

Entonces, aunque no estoy familiarizado con la definición de C++ 0x de "raza de datos", supongo que incluye algunas condiciones donde los programadores pueden suponer que un objeto no está escrito, y que esta transformación violar esas condiciones Yo especulo que si y == 2, entonces su código original, junto con el código concurrente: x = 42; x = 1; z = x en otro hilo, no se define como una carrera de datos. O al menos si se trata de una carrera de datos, no es aquella que permite que z termine con un valor de 17 o 42.

Considere que en este programa, el valor 2 en y podría usarse para indicar "allí hay otros hilos en ejecución: no modifique x, porque no estamos sincronizados aquí, por lo que se introduciría una carrera de datos ". Quizás la razón por la que no hay sincronización es que en todos los demás casos de y, no hay otros hilos ejecutándose con acceso a x. Parece razonable que C++ 0x querría apoyar código como este:

if (single_threaded) { 
    x = 17; 
} else { 
    sendMessageThatSafelySetsXTo(17); 
} 

Es evidente, entonces, que no quieren que se transforma en:

tmp = x; 
x = 17; 
if (!single_threaded) { 
    x = tmp; 
    sendMessageThatSafelySetsXTo(17); 
} 

que es básicamente la misma transformación como en su ejemplo, pero con solo 2 casos, en lugar de que haya suficiente para que parezca una buena optimización de tamaño de código.

Answer 2

Si y==2, y otro hilo modifica o lee x, ¿cómo hay una condición de carrera en la muestra original? Este hilo nunca toca x, por lo que otros hilos pueden hacerlo libremente.

Pero con la versión reordenada, nuestro hilo modifica x, aunque solo sea temporalmente, por lo que si otro hilo también lo manipula, ahora tenemos una condición de carrera donde no había ninguno antes.