La optimización del compilador rompe el código de subprocesos múltiples

Question

Después de haber aprendido de la manera difícil que shared variables are currently not guarded by memory barriers, ahora he encontrado otro problema. O bien estoy haciendo algo mal, o la optimización del compilador existente en dmd puede romper el código de subprocesos múltiples reordenando las lecturas de las variables shared.

A modo de ejemplo, cuando compilo un ejecutable con dmd -O (optimización completa), el compilador optimiza alegremente la variable local o en este código (donde cas es la función de comparación y de intercambio de core.atomic)

shared uint cnt; 
void atomicInc () { uint o; do { o = cnt; } while (!cas(&cnt, o, o + 1));} 

a algo como esto (ver desmontaje a continuación):

shared uint cnt; 
void atomicInc () { while (!cas(&cnt, cnt, cnt + 1)) { } } 

En el código "optimizado" cnt se lee dos veces de la memoria, de ese modo corriendo el riesgo de que otro hilo haya modificado cnt en el medio. La optimización básicamente destruye el algoritmo compare-and-swap.

¿Es esto un error, o hay una forma correcta de lograr el resultado deseado? El único problema que he encontrado hasta ahora es implementar el código usando el ensamblador.

código de prueba completa y los detalles adicionales
Para completar, aquí es un código de prueba completo que muestra tanto los problemas de memoria (no hay barreras, y el problema de optimización). Se produce la siguiente salida en tres máquinas Windows diferentes tanto para DMD 2.049 y DMD 2.050 (suponiendo que el algoritmo de Dekker no punto muerto, lo que podría suceder):

dmd -O -run optbug.d 
CAS : failed 
Dekker: failed 

y el bucle interior atomicInc se compila a este con plena optimización:

; cnt is stored at 447C10h 
; while (!cas(&cnt, o, o + 1)) o = cnt; 
; 1) prepare call cas(&cnt, o, o + 1): &cnt and o go to stack, o+1 to eax 
402027: mov ecx,447C10h   ; ecx = &cnt 
40202C: mov eax,[447C10h]  ; eax = o1 = cnt 
402031: inc eax     ; eax = o1 + 1 (third parameter) 
402032: push ecx     ; push &cnt (first parameter) 
    ; next instruction pushes current value of cnt onto stack 
    ; as second parameter o instead of re-using o1 
402033: push [447C10h]  
402039: call 4020BC    ; 2) call cas  
40203E: xor al,1    ; 3) test success 
402040: jne 402027    ; no success try again 
; end of main loop 

Aquí está el código de prueba:

import core.atomic; 
import core.thread; 
import std.stdio; 

enum loops = 0xFFFF; 
shared uint cnt; 

/* ***************************************************************************** 
Implement atomicOp!("+=")(cnt, 1U); with CAS. The code below doesn't work with 
the "-O" compiler flag because cnt is read twice while calling cas and another 
thread can modify cnt in between. 
*/ 
enum threads = 8; 

void atomicInc () { uint o; do { o = cnt; } while (!cas(&cnt, o, o + 1));} 
void threadFunc () { foreach (i; 0..loops) atomicInc; } 

void testCas () { 
    cnt = 0; 
    auto tgCas = new ThreadGroup; 
    foreach (i; 0..threads) tgCas.create(&threadFunc); 
    tgCas.joinAll; 
    writeln("CAS : ", cnt == loops * threads ? "passed" : "failed"); 
} 

/* ***************************************************************************** 
Dekker's algorithm. Fails on ia32 (other than atom) because ia32 can re-order 
read before write. Most likely fails on many other architectures. 
*/ 
shared bool flag1 = false; 
shared bool flag2 = false; 
shared bool turn2 = false; // avoids starvation by executing 1 and 2 in turns 

void dekkerInc () { 
    flag1 = true; 
    while (flag2) if (turn2) { 
     flag1 = false; while (turn2) { /* wait until my turn */ } 
     flag1 = true; 
    } 
    cnt++;     // shouldn't work without a cast 
    turn2 = true; flag1 = false; 
} 

void dekkerDec () { 
    flag2 = true; 
    while (flag1) if (!turn2) { 
     flag2 = false; while (!turn2) { /* wait until my turn */ } 
     flag2 = true; 
    } 
    cnt--;     // shouldn't work without a cast 
    turn2 = false; flag2 = false; 
} 

void threadDekkerInc () { foreach (i; 0..loops) dekkerInc; } 
void threadDekkerDec () { foreach (i; 0..loops) dekkerDec; } 

void testDekker () { 
    cnt = 0; 
    auto tgDekker = new ThreadGroup; 
    tgDekker.create(&threadDekkerInc); 
    tgDekker.create(&threadDekkerDec); 
    tgDekker.joinAll; 
    writeln("Dekker: ", cnt == 0 ? "passed" : "failed"); 
} 

/* ************************************************************************** */ 
void main() { 
    testCas; 
    testDekker; 
} 

Answer 1

Si bien los problemas todavía parecen existir, core.atomic ahora expone atomicLoad, lo que permite una solución directa relativa.Para hacer el trabajo cas ejemplo, basta con cargar cnt atómicamente:

void atomicInc () { 
    uint o; 
    do { 
     o = atomicLoad(cnt); 
    } while (!cas(&cnt, o, o + 1)); 
} 

Del mismo modo, para hacer el trabajo algoritmo de Dekker:

// ... 
while (atomicLoad(flag2)) if (turn2) { 
// ... 
while (atomicLoad(flag1)) if (!turn2) { 
// ... 

Para arquitecturas diferentes a IA32 (haciendo caso omiso de las operaciones de cadena y SSE) que puede también Reordenar

• lee al respecto lee
• o escribe rela tivo a
escribe
• o escribe y lee en la misma ubicación de memoria serían necesarios

barreras de memoria adicionales.

Answer 2

Sí, el código en ensamblador. Si omite el uso de la función cas() y simplemente escribe toda la función atomicInt en el ensamblaje, solo se tratará de unas pocas líneas de código. Hasta que lo haga, probablemente luchará contra las optimizaciones del compilador.

Además de todo eso, puede utilizar la instrucción x86 LOCK INC en lugar de CAS y debería poder reducir la función a solo una o dos líneas de ensamblaje.