C#/CLR: MemoryBarrier und Torn liest

Question

Nur herumspielen mit Nebenläufigkeit in meiner Freizeit, und wollte versuchen, zerrissene Lesevorgänge ohne Sperren auf der Leserseite zu verhindern, so dass gleichzeitige Leser nicht miteinander stören.

Die Idee besteht darin, Schreibvorgänge über eine Sperre zu serialisieren, aber nur eine Speicherbarriere auf der Leseseite zu verwenden. Hier ist eine wiederverwendbare Abstraktion, die den Ansatz einzukapseln ich kam mit:

public struct Sync<T> 
    where T : struct 
{ 
    object write; 
    T value; 
    int version; // incremented with each write 

    public static Sync<T> Create() 
    { 
     return new Sync<T> { write = new object() }; 
    } 

    public T Read() 
    { 
     // if version after read == version before read, no concurrent write 
     T x; 
     int old; 
     do 
     { 
      // loop until version number is even = no write in progress 
      do 
      { 
       old = version; 
       if (0 == (old & 0x01)) break; 
       Thread.MemoryBarrier(); 
      } while (true); 
      x = value; 
      // barrier ensures read of 'version' avoids cached value 
      Thread.MemoryBarrier(); 
     } while (version != old); 
     return x; 
    } 

    public void Write(T value) 
    { 
     // locks are full barriers 
     lock (write) 
     { 
      ++version;    // ++version odd: write in progress 
      this.value = value; 
      // ensure writes complete before last increment 
      Thread.MemoryBarrier(); 
      ++version;    // ++version even: write complete 
     } 
    } 
} 

Sie nicht über Überlauf auf der Version Variable Sorge, vermeide ich, dass eine andere Art und Weise. Also ist mein Verständnis und Anwendung von Thread.MemoryBarrier in obigem korrekt? Sind irgendwelche Barrieren unnötig?

Answer 1

Ich nahm einen langen Blick auf Ihren Code und es scheint mir richtig. Eine Sache, die mir sofort in den Sinn kam, war, dass Sie ein etabliertes Muster für die Low-Lock-Operation verwendet haben. Ich kann sehen, dass Sie version als eine Art virtuelle Sperre verwenden. Gerade Zahlen werden freigegeben und ungerade Zahlen werden erfasst. Und da Sie einen monoton steigenden Wert für die virtuelle Sperre verwenden, vermeiden Sie auch die ABA problem. Das Wichtigste ist jedoch, dass Sie während des Leseversuchs weiterschleifen, bis der Wert der virtuellen Sperre gleich ist, bevor der Lesevorgang beginnt, verglichen mit , nachdem abgeschlossen ist. Andernfalls halten Sie dies für einen fehlgeschlagenen Lesevorgang und versuchen es noch einmal. Also, ja, die Kernlogik ist gut gemacht.

Also, was ist mit der Platzierung der Speicherbarriere Generatoren? Nun, das alles sieht auch ziemlich gut aus. Alle Thread.MemoryBarrier Anrufe sind erforderlich. Wenn ich nit-pick hätte, würde ich sagen, dass Sie ein zusätzliches in der Write Methode benötigen, damit es so aussieht.

public void Write(T value) 
{ 
    // locks are full barriers 
    lock (write) 
    { 
     ++version;    // ++version odd: write in progress 
     Thread.MemoryBarrier(); 
     this.value = value; 
     Thread.MemoryBarrier(); 
     ++version;    // ++version even: write complete 
    } 
} 

Der zusätzliche Anruf hier stellt sicher, dass ++version und this.value = value nicht getauscht bekommen. Nun erlaubt die ECMA-Spezifikation technisch diese Art von Befehlsneuordnung. Die Implementierung der CLI und der x86-Hardware von Microsoft weist jedoch bereits eine flüchtige Semantik für Schreibvorgänge auf, sodass sie in den meisten Fällen nicht wirklich benötigt wird. Aber wer weiß, vielleicht wäre es in der Mono-Laufzeit notwendig, die ARM-CPU zu targetieren.

Auf der Read Seite der Dinge kann ich keine Fehler finden. In der Tat, die Platzierung der Anrufe, die Sie haben, ist genau, wo ich sie gestellt hätte. Manche Leute fragen sich vielleicht, warum Sie vor dem ersten Lesen von version keinen brauchen. Der Grund dafür ist, dass die äußere Schleife den Fall abfängt, wenn der erste Lesevorgang aufgrund der Thread.MemoryBarrier weiter unten zwischengespeichert wurde.

Das bringt mich zu einer Diskussion über die Leistung. Ist das wirklich schneller als ein hartes Schloss in der Read Methode? Nun, ich habe Ihren Code ziemlich ausführlich getestet, um Ihnen bei der Beantwortung dieser Frage zu helfen. Die Antwort ist ein definitives Ja! Das ist ein bisschen schneller als ein hartes Schloss. Ich testete mit einem Guid als Werttyp, weil es 128 Bits und so größer als die native Wortgröße meines Computers (64 Bits) ist. Ich habe auch verschiedene Variationen über die Anzahl der Autoren und Leser verwendet. Ihre Low-Lock-Technik hat die Hard-Lock-Technik konsequent und deutlich übertroffen. Ich habe sogar ein paar Variationen mit Interlocked.CompareExchange versucht, um das bewusste Lesen zu machen, und sie waren auch alle langsamer. Tatsächlich war es in manchen Situationen sogar langsamer als das Festschloss. Ich muss ehrlich sein. Das hat mich nicht überrascht.

Ich habe auch einige ziemlich signifikante Gültigkeitsprüfung durchgeführt. Ich habe Tests erstellt, die für eine lange Zeit laufen würden und nicht einmal, dass ich eine zerrissene Lektüre gesehen habe. Und dann als Kontrolltest würde ich die Read Methode in einer solchen Weise zwicken, dass ich wusste, dass es falsch sein würde, und ich führte den Test wieder durch. Dieses Mal begannen, wie erwartet, zufällige Lesevorgänge zu erscheinen. Ich habe den Code wieder auf das geändert, was Sie haben, und die zerrissenen Lesetexte verschwanden; wieder wie erwartet. Dies schien zu bestätigen, was ich bereits erwartet hatte. Das heißt, Ihr Code sieht korrekt aus. Ich habe keine große Auswahl an Laufzeit- und Hardware-Umgebungen zum Testen (und ich habe auch keine Zeit), also bin ich nicht bereit, ein 100% iges Gütesiegel zu geben, aber ich glaube, ich kann Ihrer Implementierung zwei Daumen hoch geben zur Zeit.

Schließlich, mit allem, was ich sagte, würde ich immer noch vermeiden, dies in Produktion zu setzen. Ja, vielleicht stimmt es, aber der nächste Typ, der den Code pflegen muss, wird es wahrscheinlich nicht verstehen. Jemand kann den Code ändern und brechen, weil er die Konsequenzen ihrer Änderungen nicht versteht. Sie müssen zugeben, dass dieser Code ziemlich spröde ist. Schon die geringste Veränderung könnte es brechen.

Answer 2

Es scheint, als ob Sie in lock-free/wartefreie Implementierung interessant sind. Lassen Sie uns von dieser Diskussion ausgehen, zum Beispiel: Lock-free multi-threading is for real threading experts