Lock-free Multithreading ist für echte Threading-Experten

86

Ich las eine Antwort durch , die Jon Skeet auf eine Frage gab, und darin erwähnte er Folgendes:

Für mich ist sperrenfreies Multithreading etwas für echte Threading-Experten, von denen ich keiner bin.

Es ist nicht das erste Mal, dass ich das höre, aber ich finde nur sehr wenige Leute, die darüber sprechen, wie Sie es tatsächlich tun, wenn Sie lernen möchten, wie man sperrfreien Multithreading-Code schreibt.

Meine Frage ist also, dass Sie nicht nur alles über Threading usw. lernen, sondern auch lernen, wie man spezifisch sperrfreien Multithreading-Code schreibt und welche guten Ressourcen es gibt.

Prost

vdhant
quelle
Ich verwende gcc-, linux- und X86 / X68-Plattformen. Lock-free ist bei weitem nicht so schwer, wie sie alle klingen lassen! Die gcc-Atom-Builtins haben Speicherbarrieren für Intel, aber das spielt im wirklichen Leben keine Rolle. Was zählt ist, dass der Speicher atomar modifiziert wird. Wenn Sie "sperrenfreie" Datenstrukturen entwerfen, wird es nur unübersehbar, dass es keine Rolle spielt, wenn ein anderer Thread eine Änderung sieht. Einzelne verknüpfte Listen, Überspringlisten, Hash-Tabellen, kostenlose Listen usw. lassen sich ganz einfach sperren. Lock Free ist nicht für alles. Es ist nur ein weiteres Werkzeug, das für bestimmte Situationen geeignet ist.
Johnnycrash
2
1024cores.net
Mankarse
Abstimmung zum Schließen als Ressourcenempfehlung oder nicht klar, was Sie fragen.
Ciro Santilli 法轮功 冠状 病 六四 事件 16

Antworten:

100

Aktuelle "sperrenfreie" Implementierungen folgen die meiste Zeit demselben Muster:

  • * Lies einen Zustand und mache eine Kopie davon **
  • * Kopie ändern **
  • Führen Sie eine verriegelte Operation durch
  • Wiederholen Sie den Vorgang, wenn dies fehlschlägt

(* optional: abhängig von der Datenstruktur / dem Algorithmus)

Das letzte Bit ähnelt unheimlich einem Spinlock. In der Tat ist es ein grundlegender Spinlock . :)
Ich stimme @nobugz darin zu: Die Kosten für die ineinandergreifenden Operationen, die beim sperrenfreien Multithreading verwendet werden , werden von den Cache- und Speicherkohärenzaufgaben dominiert, die sie ausführen müssen .

Was Sie jedoch mit einer Datenstruktur gewinnen, die "sperrenfrei" ist, ist, dass Ihre "Sperren" sehr feinkörnig sind . Dies verringert die Wahrscheinlichkeit, dass zwei gleichzeitige Threads auf dieselbe "Sperre" (Speicherort) zugreifen.

Der Trick besteht meistens darin, dass Sie keine dedizierten Sperren haben. Stattdessen behandeln Sie z. B. alle Elemente in einem Array oder alle Knoten in einer verknüpften Liste als "Spin-Lock". Sie lesen, ändern und versuchen zu aktualisieren, wenn seit dem letzten Lesen keine Aktualisierung stattgefunden hat. Wenn ja, versuchen Sie es erneut.
Dies macht Ihr "Sperren" (oh, sorry, nicht sperren :) sehr feinkörnig, ohne zusätzlichen Speicher- oder Ressourcenbedarf einzuführen.
Wenn Sie es feinkörniger machen, verringert sich die Wahrscheinlichkeit von Wartezeiten. Es klingt großartig, es so feinkörnig wie möglich zu gestalten, ohne zusätzliche Ressourcenanforderungen einzuführen, nicht wahr?

Der größte Spaß kann jedoch durch die Sicherstellung der korrekten Bestellung von Laden / Laden entstehen .
Entgegen der eigenen Intuition können CPUs Speicher-Lese- / Schreibvorgänge neu anordnen - sie sind übrigens sehr intelligent: Es wird Ihnen schwer fallen, dies von einem einzigen Thread aus zu beobachten. Sie werden jedoch auf Probleme stoßen, wenn Sie mit dem Multithreading auf mehreren Kernen beginnen. Ihre Intuitionen werden zusammenbrechen: Nur weil eine Anweisung früher in Ihrem Code ist, bedeutet dies nicht, dass sie tatsächlich früher ausgeführt wird. CPUs können Anweisungen in unregelmäßiger Reihenfolge verarbeiten. Dies gilt insbesondere für Anweisungen mit Speicherzugriffen, um die Hauptspeicherlatenz zu verbergen und ihren Cache besser zu nutzen.

Nun ist es gegen die Intuition sicher, dass eine Codesequenz nicht "von oben nach unten" fließt, sondern so läuft, als ob es überhaupt keine Sequenz gäbe - und möglicherweise als "Spielplatz des Teufels" bezeichnet werden kann. Ich glaube, es ist unmöglich, eine genaue Antwort darauf zu geben, welche Nachbestellungen beim Laden / Speichern stattfinden werden. Stattdessen spricht man immer in Bezug auf May und mights und Dosen und auf das Schlimmste vorzubereiten. "Oh, die CPU könnte diesen Lesevorgang so anordnen, dass er vor diesem Schreibvorgang erfolgt. Daher ist es am besten, hier an dieser Stelle eine Speicherbarriere anzubringen."

Angelegenheiten werden durch die Tatsache kompliziert , dass selbst dieses May und mights über CPU - Architekturen unterscheiden können. Es kann beispielsweise der Fall sein, dass etwas, das in einer Architektur garantiert nicht passiert, auf einer anderen Architektur passiert .


Um "sperrfreies" Multithreading richtig zu machen, müssen Sie Speichermodelle verstehen.
Das Speichermodell und die Garantien korrekt zu machen, ist jedoch nicht trivial, wie diese Geschichte zeigt, in der Intel und AMD einige Korrekturen an der Dokumentation vorgenommen haben, die MFENCEbei JVM-Entwicklern für Aufsehen gesorgt hat . Wie sich herausstellte, war die Dokumentation, auf die sich die Entwickler von Anfang an stützten, überhaupt nicht so präzise.

Sperren in .NET führen zu einer impliziten Speicherbarriere, sodass Sie sie sicher verwenden können (meistens ... siehe zum Beispiel die Größe von Joe Duffy - Brad Abrams - Vance Morrison zu verzögerter Initialisierung, Sperren, flüchtigen Bestandteilen und Speicher Barrieren. :) (Folgen Sie unbedingt den Links auf dieser Seite.)

Als zusätzlichen Bonus werden Sie auf einer Nebenquest in das .NET-Speichermodell eingeführt . :) :)

Es gibt auch einen "Oldie but Goldie" von Vance Morrison: Was jeder Entwickler über Multithread-Apps wissen muss .

... und natürlich ist Joe Duffy , wie @Eric erwähnte, eine definitive Lektüre zu diesem Thema.

Ein gutes STM kann einer feinkörnigen Verriegelung so nahe wie möglich kommen und bietet wahrscheinlich eine Leistung, die einer handgefertigten Implementierung nahe kommt oder dieser ebenbürtig ist. Eines davon ist STM.NET aus den DevLabs-Projekten von MS.

Wenn Sie kein reiner .NET-Fanatiker sind, hat Doug Lea in JSR-166 großartige Arbeit geleistet .
Cliff Click hat eine interessante Sicht auf Hash-Tabellen, die nicht auf Lock-Striping basiert - wie es die gleichzeitigen Hash-Tabellen von Java und .NET tun - und scheint gut auf 750 CPUs zu skalieren.

Wenn Sie keine Angst haben, sich in das Gebiet von Linux zu wagen, bietet der folgende Artikel weitere Einblicke in die Interna aktueller Speicherarchitekturen und wie die gemeinsame Nutzung von Cache-Zeilen die Leistung beeinträchtigen kann: Was jeder Programmierer über Speicher wissen sollte .

@ Ben machte viele Kommentare zu MPI: Ich stimme aufrichtig zu, dass MPI in einigen Bereichen glänzen kann. Eine MPI-basierte Lösung kann einfacher zu überlegen, einfacher zu implementieren und weniger fehleranfällig sein als eine halbherzige Sperrimplementierung, die versucht, intelligent zu sein. (Subjektiv gilt dies jedoch auch für eine STM-basierte Lösung.) Ich würde auch wetten, dass es Lichtjahre einfacher ist, eine anständige verteilte Anwendung in z. B. Erlang korrekt zu schreiben , wie viele erfolgreiche Beispiele nahe legen.

MPI hat jedoch seine eigenen Kosten und seine eigenen Probleme, wenn es auf einem einzelnen Multi-Core-System ausgeführt wird . In Erlang müssen beispielsweise Probleme bei der Synchronisierung von Prozessplanung und Nachrichtenwarteschlangen gelöst werden .
Außerdem implementieren MPI-Systeme im Kern normalerweise eine Art kooperative N: M-Planung für "Lightweight-Prozesse". Dies bedeutet zum Beispiel, dass es einen unvermeidlichen Kontextwechsel zwischen einfachen Prozessen gibt. Es ist wahr, dass es sich nicht um einen "klassischen Kontextwechsel" handelt, sondern hauptsächlich um eine User-Space-Operation, die schnell durchgeführt werden kann. Ich bezweifle jedoch aufrichtig, dass sie unter die 20-200 Zyklen einer ineinandergreifenden Operation gebracht werden kann . Die Kontextumschaltung im Benutzermodus ist sicherlich langsamersogar in der Intel McRT-Bibliothek. N: M-Planung mit leichten Prozessen ist nicht neu. LWPs waren lange Zeit in Solaris vorhanden. Sie wurden verlassen. Es gab Fasern in NT. Sie sind jetzt meistens ein Relikt. Es gab "Aktivierungen" in NetBSD. Sie wurden verlassen. Linux hatte seine eigene Sicht auf das Thema N: M-Threading. Es scheint inzwischen etwas tot zu sein.
Von Zeit zu Zeit gibt es neue Konkurrenten: zum Beispiel McRT von Intel oder zuletzt User-Mode Scheduling zusammen mit ConCRT von Microsoft.
Auf der untersten Ebene machen sie das, was ein N: M MPI-Scheduler macht. Erlang - oder ein beliebiges MPI-System - kann auf SMP-Systemen durch die Nutzung des neuen UMS erheblich profitieren .

Ich denke, die Frage des OP bezieht sich nicht auf die Vorzüge und subjektiven Argumente für / gegen eine Lösung, aber wenn ich das beantworten müsste, hängt es wohl von der Aufgabe ab: für den Aufbau von Basisdatenstrukturen mit niedrigem Niveau und hoher Leistung, die auf a laufen Ein einzelnes System mit vielen Kernen , entweder Low-Lock- / "Lock-Free" -Techniken oder ein STM, liefert die besten Ergebnisse in Bezug auf die Leistung und würde wahrscheinlich eine MPI-Lösung jederzeit in Bezug auf die Leistung schlagen, selbst wenn die oben genannten Falten ausgebügelt werden zB in Erlang.
Um etwas mäßig komplexeres zu erstellen, das auf einem einzelnen System ausgeführt wird, würde ich vielleicht die klassische grobkörnige Verriegelung oder, wenn die Leistung von großer Bedeutung ist, ein STM wählen.
Für den Aufbau eines verteilten Systems würde ein MPI-System wahrscheinlich eine natürliche Wahl treffen.
Beachten Sie, dass es auch MPI-Implementierungen für .NET gibt (obwohl sie nicht so aktiv zu sein scheinen).

Andras Vass
quelle
1
Obwohl diese Antwort viele gute Informationen enthält, ist die Überschrift, dass sperrfreie Algorithmen und Datenstrukturen im Wesentlichen nur eine Sammlung sehr feinkörniger Spinlocks sind, falsch. Während in sperrfreien Strukturen normalerweise Wiederholungsschleifen angezeigt werden, ist das Verhalten sehr unterschiedlich: Sperren (einschließlich Spinlocks) erfassen ausschließlich bestimmte Ressourcen, und andere Threads können keine Fortschritte erzielen, solange sie gehalten werden. Der "Wiederholungsversuch" in diesem Sinne wartet einfach darauf, dass die exklusive Ressource freigegeben wird.
BeeOnRope
1
Lock-free-Algorithmen verwenden dagegen weder CAS noch andere atomare Anweisungen, um eine exklusive Ressource zu erhalten, sondern um eine Operation abzuschließen. Wenn sie fehlschlagen, liegt dies an einem zeitlich feinkörnigen Rennen mit einem anderen Thread, und in diesem Fall hat der andere Thread Fortschritte gemacht (seine Operation abgeschlossen). Wenn ein Thread auf unbestimmte Zeit verdächtig ist, können alle anderen Threads weiterhin Fortschritte erzielen. Dies unterscheidet sich sowohl qualitativ als auch leistungsmäßig stark von exklusiven Schlössern. Die Anzahl der "Wiederholungsversuche" ist für die meisten CAS-Loops selbst bei starken Konflikten normalerweise sehr gering ...
BeeOnRope
1
... aber das bedeutet natürlich keine gute Skalierung: Der Wettbewerb um einen einzelnen Speicherort wird auf SMP-Computern immer ziemlich langsam sein, nur aufgrund von Inter-Socket-Latenzen zwischen den Kernen, selbst wenn die Anzahl der CAS-Fehler gleich ist niedrig.
BeeOnRope
1
@AndrasVass - Ich denke, es hängt auch vom "guten" vs "schlechten" sperrenfreien Code ab. Natürlich kann jeder eine Struktur schreiben und sie sperrenfrei nennen, während sie wirklich nur einen Spinlock im Benutzermodus verwendet und nicht einmal die Definition erfüllt. Ich möchte auch interessierte Leser ermutigen, dieses Papier von Herlihy und Shavit zu lesen, in dem die verschiedenen Kategorien von sperrbasierten und sperrenfreien Algorithmen auf formale Weise behandelt werden. Alles von Herlihy zu diesem Thema wird ebenfalls empfohlen.
BeeOnRope
1
@AndrasVass - Ich bin anderer Meinung. Die meisten der klassischen sperrenfreien Strukturen (Listen, Warteschlangen, gleichzeitige Karten usw.) drehten sich selbst für gemeinsam genutzte veränderbare Strukturen nicht, und praktisch vorhandene Implementierungen derselben, beispielsweise in Java, folgen demselben Muster (ich bin nicht so vertraut mit dem, was in nativ kompiliertem C oder C ++ verfügbar ist, und es ist dort schwieriger, da keine Garbage Collection vorhanden ist). Vielleicht haben Sie und ich eine andere Definition von Spinnen: Ich betrachte den "CAS-Wiederholungsversuch", den Sie in sperrfreien Sachen finden, nicht als "Spinnen". IMO "Spinning" impliziert heißes Warten.
BeeOnRope
27

Joe Duffys Buch:

http://www.bluebytesoftware.com/books/winconc/winconc_book_resources.html

Er schreibt auch einen Blog zu diesen Themen.

Der Trick, um Low-Lock-Programme richtig zu machen, besteht darin, auf einer tiefen Ebene genau zu verstehen , welche Regeln das Speichermodell für Ihre spezielle Kombination aus Hardware, Betriebssystem und Laufzeitumgebung enthält.

Ich persönlich bin nicht annähernd klug genug, um über InterlockedIncrement hinaus eine korrekte Low-Lock-Programmierung durchzuführen, aber wenn Sie großartig sind, machen Sie es. Stellen Sie einfach sicher, dass Sie viel Dokumentation im Code belassen, damit Personen, die nicht so schlau sind wie Sie, nicht versehentlich eine Ihrer Speichermodellinvarianten brechen und einen nicht zu findenden Fehler einführen.

Eric Lippert
quelle
38
Wenn also sowohl Eric Lippert als auch Jon Skeet der Meinung sind, dass sperrenfreies Programmieren nur für Leute gedacht ist, die klüger sind als sie selbst, dann werde ich demütig davonlaufen und sofort vor der Idee schreien. ;-)
dodgy_coder
20

Heutzutage gibt es kein "sperrenfreies Einfädeln". Es war ein interessanter Spielplatz für Akademiker und dergleichen, Ende des letzten Jahrhunderts, als Computerhardware langsam und teuer war. Dekkers Algorithmus war immer mein Favorit, moderne Hardware hat ihn auf die Weide gestellt. Es funktioniert nicht mehr.

Zwei Entwicklungen haben dies beendet: die wachsende Ungleichheit zwischen der Geschwindigkeit von RAM und CPU. Und die Fähigkeit der Chiphersteller, mehr als einen CPU-Kern auf einen Chip zu setzen.

Aufgrund des RAM-Geschwindigkeitsproblems mussten die Chipdesigner einen Puffer auf den CPU-Chip setzen. Der Puffer speichert Code und Daten, auf die der CPU-Kern schnell zugreifen kann. Und kann viel langsamer vom / in den RAM gelesen und geschrieben werden. Dieser Puffer wird als CPU-Cache bezeichnet, die meisten CPUs haben mindestens zwei davon. Der Cache der ersten Ebene ist klein und schnell, der zweite ist groß und langsamer. Solange die CPU Daten und Anweisungen aus dem Cache der ersten Ebene lesen kann, läuft sie schnell. Ein Cache-Fehler ist sehr teuer. Er versetzt die CPU in einen Ruhezustand von bis zu 10 Zyklen, wenn sich die Daten nicht im 1. Cache befinden, und in 200 Zyklen, wenn sie sich nicht im 2. Cache befinden und aus dem sie gelesen werden müssen RAM.

Jeder CPU-Kern hat seinen eigenen Cache, sie speichern ihre eigene "Ansicht" des RAM. Wenn die CPU Daten schreibt, wird der Schreibvorgang in den Cache ausgeführt, der dann langsam in den RAM geleert wird. Es ist unvermeidlich, dass jeder Kern jetzt eine andere Ansicht des RAM-Inhalts hat. Mit anderen Worten, eine CPU weiß nicht, was eine andere CPU geschrieben hat, bis dieser RAM-Schreibzyklus abgeschlossen ist und die CPU ihre eigene Ansicht aktualisiert.

Das ist dramatisch inkompatibel mit Threading. Es ist Ihnen immer sehr wichtig, wie der Status eines anderen Threads ist, wenn Sie Daten lesen müssen, die von einem anderen Thread geschrieben wurden. Um dies sicherzustellen, müssen Sie explizit eine sogenannte Speicherbarriere programmieren. Es handelt sich um ein CPU-Grundelement auf niedriger Ebene, das sicherstellt, dass sich alle CPU-Caches in einem konsistenten Zustand befinden und über eine aktuelle Ansicht des Arbeitsspeichers verfügen. Alle ausstehenden Schreibvorgänge müssen in den Arbeitsspeicher geleert werden. Die Caches müssen dann aktualisiert werden.

Dies ist in .NET verfügbar. Die Thread.MemoryBarrier () -Methode implementiert eine. Angesichts der Tatsache, dass dies 90% der Arbeit ist, die die Lock-Anweisung ausführt (und 95 +% der Ausführungszeit), sind Sie einfach nicht voraus, indem Sie die von .NET bereitgestellten Tools meiden und versuchen, Ihre eigenen zu implementieren.

Hans Passant
quelle
2
@ Davy8: Komposition macht es immer noch schwer. Wenn ich zwei sperrfreie Hash-Tabellen habe und als Verbraucher auf beide zugreife, garantiert dies nicht die Konsistenz des gesamten Zustands. Das nächste, was Sie heute erreichen können, sind STMs, bei denen Sie die beiden Zugriffe z. B. in einem einzigen atomicBlock platzieren können. Alles in allem kann es in vielen Fällen genauso schwierig sein, schlossfreie Strukturen zu konsumieren.
Andras Vass
4
Ich kann mich irren, aber ich denke, Sie haben falsch erklärt, wie die Cache-Kohärenz funktioniert. Die meisten modernen Multicore-Prozessoren verfügen über kohärente Caches. Dies bedeutet, dass die Cache-Hardware sicherstellt, dass alle Prozesse dieselbe Ansicht des RAM-Inhalts haben, indem "Lese" -Aufrufe blockiert werden, bis alle entsprechenden "Schreib" -Aufrufe abgeschlossen sind. Die Dokumentation zu Thread.MemoryBarrier () ( msdn.microsoft.com/en-us/library/… ) sagt überhaupt nichts über das Cache-Verhalten aus - es ist lediglich eine Anweisung, die den Prozessor daran hindert, Lese- und Schreibvorgänge neu zu ordnen .
Brooks Moses
7
"Es gibt heutzutage kein" sperrenfreies Einfädeln "mehr." Sagen Sie das den Programmierern von Erlang und Haskell.
Julia
4
@HansPassant: "Heutzutage gibt es kein" sperrenfreies Threading "." F #, Erlang, Haskell, Cilk, OCaml, die Task Parallel Library (TPL) von Microsoft und die Threaded Building Blocks (TBB) von Intel fördern die sperrfreie Multithread-Programmierung. Ich verwende heutzutage selten Sperren im Produktionscode.
JD
5
@HansPassant: "Eine sogenannte Speicherbarriere. Es handelt sich um ein CPU-Grundelement auf niedriger Ebene, das sicherstellt, dass sich alle CPU-Caches in einem konsistenten Zustand befinden und eine aktuelle Ansicht des Arbeitsspeichers haben. Alle ausstehenden Schreibvorgänge müssen in den Arbeitsspeicher geleert werden Caches müssen dann aktualisiert werden ". Eine Speicherbarriere verhindert in diesem Zusammenhang, dass Speicherbefehle (Laden und Speichern) vom Compiler oder der CPU neu angeordnet werden. Nichts mit der Konsistenz von CPU-Caches zu tun.
JD
6

Google für sperrenfreie Datenstrukturen und Software-Transaktionsspeicher .

Ich werde John Skeet in diesem Punkt zustimmen. Lock-Free-Threading ist der Spielplatz des Teufels und am besten Menschen überlassen, die wissen, dass sie wissen, was sie wissen müssen.

Marcelo Cantos
quelle
0

Wenn es um Multithreading geht, muss man genau wissen, was man tut. Ich meine, untersuchen Sie alle möglichen Szenarien / Fälle, die auftreten können, wenn Sie in einer Multithread-Umgebung arbeiten. Lock-free Multithreading ist keine Bibliothek oder Klasse, die wir integrieren, sondern ein Wissen / eine Erfahrung, die wir auf unserer Reise mit Threads sammeln.

Prahler
quelle
Es gibt zahlreiche Bibliotheken, die eine sperrfreie Threading-Semantik bieten. Von besonderem Interesse ist STM, von dem es eine ganze Reihe von Implementierungen gibt.
Marcelo Cantos
Ich sehe beide Seiten von diesem. Um eine effektive Leistung aus einer sperrfreien Bibliothek herauszuholen, sind fundierte Kenntnisse der Speichermodelle erforderlich. Ein Programmierer, der dieses Wissen nicht besitzt, kann dennoch von den Korrektheitsvorteilen profitieren.
Ben Voigt
0

Auch wenn sperrfreies Threading in .NET schwierig sein kann, können Sie bei der Verwendung einer Sperre häufig erhebliche Verbesserungen erzielen, indem Sie genau untersuchen, was gesperrt werden muss, und den gesperrten Abschnitt minimieren. Dies wird auch als Minimierung der Granularität der Sperre bezeichnet .

Angenommen, Sie müssen einen Sammlungsthread sicher machen. Werfen Sie nicht einfach blind eine Sperre um eine Methode, die über die Sammlung iteriert, wenn sie für jedes Element eine CPU-intensive Aufgabe ausführt. Möglicherweise müssen Sie nur eine Sperre setzen, um eine flache Kopie der Sammlung zu erstellen. Das Durchlaufen der Kopie könnte dann ohne Sperre funktionieren. Natürlich hängt dies stark von den Besonderheiten Ihres Codes ab, aber ich konnte mit diesem Ansatz ein Problem mit dem Sperrkonvoi beheben .

dodgy_coder
quelle