Triple-geprüft Verriegelung?

Question

So in der Zwischenzeit wissen wir, dass doppelt geprüft sichernde wie funktioniert nicht in C ++, zumindest nicht in einer tragbaren Weise.

ich merke, ich habe nur eine fragile Implementierung in einem lazy-Quadtree, dass ich für ein Terrain Raytracer verwenden. Also habe ich versucht, einen Weg zu finden, um noch faul Initialisierung auf sichere Art und Weise verwenden, wie ich mag nicht, zu vervierfachen Speichernutzung und Wieder um große Teile des implementierten Algorithmen.

Diese Traversal durch das Muster auf Seite 12 von C ++ und den Gefahren der inspiriert ist doppelt geprüft Sperren , sondern versucht, es zu tun billiger:

(pseudo code!)

struct Foo {
    bool childCreated[4];
    Mutex mutex[4];
    Foo child[4];

    void traverse (...) {
        ...
        if (!childCreated[c]) { 
            // get updated view
            #pragma flush childCreated[c]
            if (!childCreated[c]) { 
                ScopedLock sl (mutex[c]);
                if (!childCreated[c]) {
                    create (c);
                    #pragma flush childCreated[c]  
                    childCreated[c] = true;
                }
            }
        }
    }
}

Es wird angenommen, dass #pragma flush auch als harter Sequenzpunkt dienen würde, wo Compiler und Prozessoren werden nicht an Nachbestellung Operationen über sie erlaubt werden.

Welche Probleme sehen Sie?

Bearbeiten Version 2, die versuchen, in Rechnung Vlads Antwort zu nehmen (dritte bündig vorstellen):

(pseudo code!)

struct Foo {
    bool childCreated[4];
    Mutex mutex[4];
    Foo child[4];

    void traverse (...) {
        ...
        if (!childCreated[c]) { 
            // get updated view
            #pragma flush childCreated[c]
            if (!childCreated[c]) { 
                ScopedLock sl (mutex[c]);
                #pragma flush childCreated[c]
                if (!childCreated[c]) {
                    create (c);
                    #pragma flush childCreated[c]
                    childCreated[c] = true;
                }
            }
        }
    }
}

Bearbeiten Version 3, finde ich irgendwie diese hübschen äquivalent zu Version 2, weil ich nicht das Kind mit mir, sondern einer primitiven Flagge auf Gültigkeit zu überprüfen, im Grunde auf einer Speicherbarriere verlassen zwischen dem Erstellen ein Kind und Schreiben zu dieser Flagge.

(pseudo code!)

struct Foo {
    bool childCreated[4];
    Mutex mutex[4];
    Foo child[4];

    void traverse (...) {
        ...
        if (!childCreated[c]) { 
            ScopedLock sl (mutex[c]);
            #pragma flush childCreated[c]
            if (!childCreated[c]) {
                create (c);
                #pragma flush childCreated[c]
                childCreated[c] = true;
            }
        }
    }
}

Answer 1

Es scheint, dass Ihr Muster nicht korrekt ist. Betrachten wir den Fall, wenn Thread # 1 führt nach dem ersten #pragma flush bebauen. Dann schaltet die Steuerung auf den Faden # 2, die weiter geht, und schafft eine c, wird die Steuerung zurück, kurz bevor zweiten #pragma flush genommen. Nun ist der erste Thread aufwacht, und schafft das Kind neu.

Edit: sorry, falsch. Es wird nicht in der Lage, das Schloss zu nehmen

Edit 2: nein, noch korrekt, da der Wert in thread # nicht gespült wird 1