Compiler-Optimierung bricht Multithread-Code

Question

Nachdem ich den harten Weg, dass shared variables are currently not guarded by memory barriers gelernt habe, habe ich jetzt ein anderes Problem aufgetreten. Entweder mache ich etwas falsch, oder die vorhandene Compiler-Optimierung in dmd kann Multi-Threaded-Code durch Neuordnen von Lesevorgängen von shared Variablen brechen.

Als Beispiel, wenn ich eine ausführbare Datei mit dmd -O (vollständiger Optimierung) zu kompilieren, optimiert der Compiler glücklich die lokale Variable o in diesem Code entfernt

(wo cas die Funktion von core.atomic Vergleichs- und Swap)

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

um so etwas wie diese (siehe dis-Montage unten):

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

im "optimiert" Code cnt wird zweimal aus dem Speicher gelesen, um dadurch läuft das Risiko, dass ein anderer Thread cnt dazwischen geändert hat. Die Optimierung zerstört grundsätzlich den Vergleichs- und Austauschalgorithmus.

Ist dies ein Fehler, oder gibt es einen richtigen Weg, um das gewünschte Ergebnis zu erzielen? Die einzige Problemumgehung, die ich bisher gefunden habe, ist die Implementierung des Codes mit Assembler.

Vollständiger Test-Code und weitere Details
Für Vollständigkeit, hier ist ein vollständiger Test-Code, der beiden Probleme zeigt (keine Memory-Barrieren und das Optimierungsproblem). Es erzeugt die folgende Ausgabe auf drei verschiedenen Windows-Rechnern sowohl für DMD 2.049 und dmd 2.050 (unter der Annahme, dass Dekker-Algorithmus nicht, ist eine Sackgasse, die passieren könnte):

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

Und die Schleife in atomicInc wird dazu mit voller zusammengestellt Optimierung:

; 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 

Hier ist der Testcode:

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

Während die Probleme immer noch zu existieren scheinen, stellt jetzt atomicLoad zur Verfügung, was eine relativ einfache Problemumgehung ermöglicht.Um die cas Beispiel Arbeit zu machen, reicht es cnt atomar zu laden:

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

In ähnlicher Weise zu Dekker-Algorithmus Arbeit zu machen:

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

Für andere Architekturen als ia32 (String-Operationen und SSE ignorieren) das kann Nachbestellung auch

• liest relativ zu liest
• oder schreibt rela tive zu schreibt
• oder schreibt und liest auf den gleichen Speicherplatz

zusätzliche Speicherbarrieren erforderlich wäre.

Answer 2

Ja, Code in Assembler. Wenn Sie die Funktion cas() überspringen und nur Ihre gesamte atomicInt-Funktion in die Assembly schreiben, sind es nur ein paar Codezeilen. Bis Sie dies tun, werden Sie wahrscheinlich gegen die Optimierungen des Compilers kämpfen.

Darüber hinaus können Sie die x86 LOCK INC Anweisung anstelle von CAS verwenden und Sie sollten in der Lage sein, die Funktion auf nur ein oder zwei Zeilen der Baugruppe zu reduzieren.