In meiner Multithreadanwendung sehe ich starke Sperrkonflikte darin und verhindere eine gute Skalierbarkeit über mehrere Kerne hinweg. Ich habe mich entschieden, Lock-Free-Programmierung zu verwenden, um dies zu lösen.Wie kann ich eine lockfreie Struktur schreiben?
Wie kann ich eine lockfreie Struktur schreiben?
Kurze Antwort ist:
Sie können nicht.
Lange Antwort ist:
Wenn Sie diese Frage stellen, nicht wahr wahrscheinlich genug kennen, um eine Sperre freie Struktur zu schaffen. Lock-free-Strukturen zu erstellen ist extrem schwierig und nur Experten auf diesem Gebiet können es tun. Anstatt eigene zu schreiben, suchen Sie nach einer vorhandenen Implementierung. Wenn Sie es finden, zu überprüfen, wie weit es verwendet wird, wie gut es dokumentiert, wenn es gut bewährt, wo die Grenzen sind - auch sind frei Struktur anderen Menschen veröffentlicht gebrochen einige sperren.
Wenn Sie nicht über eine Sperre freie Struktur entsprechend der Struktur finden Sie derzeit verwenden, passen eher den Algorithmus so, dass Sie einige vorhandene verwenden können.
Wenn Sie darauf bestehen nach wie vor auf Ihre eigenes Schloss freie Struktur zu schaffen, sollten Sie: Speichermodell Ihrer Zielplattform (einschließlich Lese-/Schreib-Neuordnungs Einschränkungen
More reading:
Inmutabilität würde diesen Effekt haben. Änderungen am Objekt ergeben ein neues Objekt. Lisp arbeitet so unter der Decke.
Artikel 13 von Effective Java erklärt diese Technik.
Nun, es hängt von der Art der Struktur ab, aber Sie müssen die Struktur so gestalten, dass sie mögliche Konflikte sorgfältig und leise erkennt und behandelt.
Ich bezweifle, dass Sie eine machen können, die 100% frei ist, aber wieder, es hängt davon ab, welche Art von Struktur Sie bauen müssen.
Sie müssen möglicherweise auch die Struktur shard, so dass mehrere Threads für einzelne Elemente arbeiten und später synchronisieren/rekombinieren.
Schreiben thread-sicheren lock freien Code ist schwer; aber this article from Herb Sutter wird Sie starten.
Wie erwähnt, hängt es wirklich davon ab, von welcher Art von Struktur Sie sprechen. Zum Beispiel können Sie eine begrenzte blockierungsfreie Warteschlange schreiben, aber keine, die einen wahlfreien Zugriff erlaubt.
Unveränderlichkeit ist ein Ansatz, um das Sperren zu vermeiden. Siehe Eric Lippert's discussion und Implementierung von Dingen wie unveränderlichen Stapeln und Warteschlangen.
Verwenden Sie eine Bibliothek wie Intel's Threading Building Blocks, enthält es einige lock-free Strukturen und Algorithmen. Ich würde wirklich nicht empfehlen, den Lock-Free-Code selbst zu schreiben, es ist extrem fehleranfällig und schwer zu bekommen.
Reduzieren oder eliminieren Sie den freigegebenen veränderbaren Zustand.
Das Grundprinzip für die Lock-Free-Synchronisation ist dies:
, wenn Sie die Struktur lesen, folgen Sie der Lese mit einem Test, um zu sehen, ob die Struktur mutiert war, da Sie die Lese gestartet und wiederhole es, bis es dir gelingt, zu lesen, ohne dass etwas anderes mitkommt und mutiert, während du es tust;
Wenn Sie die Struktur mutieren, ordnen Sie Ihren Algorithmus und Ihre Daten so an, dass ein einzelner atomarer Schritt entsteht, der die gesamte Änderung für die anderen Threads sichtbar macht und die Dinge so arrangiert, dass keine davon entsteht Die Änderung ist sichtbar, sofern dieser Schritt nicht ausgeführt wird. Sie verwenden für diesen Schritt den blockfreien atomaren Mechanismus auf Ihrer Plattform (z. B. Vergleichen und Festlegen, Laden-Verknüpft + Speichern-Bedingt usw.). In diesem Schritt müssen Sie dann überprüfen, ob ein anderer Thread das Objekt mutiert hat, seit die Mutationsoperation begonnen hat. Wenn Sie dies nicht getan haben, übernehmen Sie einen Neustart, wenn dies der Fall ist.
Es gibt viele Beispiele für blockierungsfreie Strukturen im Internet; ohne mehr darüber zu wissen, was Sie implementieren und auf welcher Plattform es schwieriger ist, spezifischer zu sein.
Die meisten blockierungsfreien Algorithmen oder Strukturen beginnen mit einigen atomaren Operationen, d.h.Eine Änderung an einem Speicherort, der einmal von einem Thread begonnen wurde, wird abgeschlossen, bevor ein anderer Thread dieselbe Operation ausführen kann. Haben Sie eine solche Operation in Ihrer Umgebung?
Siehe here für das kanonische Papier zu diesem Thema.
auch versuchen, diese wikipedia article Artikel für weitere Ideen und Links.
Diese "atomare Operation" klingt verdächtig nach einer Sperre. Was ist der Unterschied? – cHao
Cliff Klicken Sie hat Kuppel einige wichtige Forschung auf Schloss freie Datenstrukturen, die durch endliche Automaten nutzen und erzielte auch eine Menge von Implementierungen für Java. Sie können seine Papiere, Folien und Implementierungen in seinem Blog: http://blogs.azulsystems.com/cliff/
Ein neuer Link von Cliff's Blog: http://www.cliffc.org/blog/ –
Wie sblundy wies darauf hin, wenn alle Objekte sind unveränderlich, schreibgeschützt, Sie müssen nicht jedoch über Sperren, sich Sorgen zu machen, das heißt, Sie muss möglicherweise Objekte viel kopieren. Das Kopieren beinhaltet normalerweise malloc und malloc verwendet Sperren, um Speicherzuteilungen über Threads zu synchronisieren, so dass unveränderliche Objekte Sie weniger kaufen als Sie denken (malloc selbst skaliert eher schlecht und malloc ist langsam; wenn Sie eine Menge malloc in einem leistungskritischen Abschnitt , erwarte keine gute Leistung).
Wenn Sie nur einfache Variablen aktualisieren müssen (zB 32 oder 64 Bit int oder Zeiger), führen Sie einfach Additions- oder Subtraktionsoperationen durch oder tauschen Sie einfach die Werte von zwei Variablen aus. Die meisten Plattformen bieten dafür "atomare Operationen" (weitere GCC bietet diese auch an). Atomic ist nicht dasselbe wie thread-safe.Unteilbar stellt jedoch sicher, dass, wenn ein Thread beispielsweise einen 64-Bit-Wert an einen Speicherort schreibt und ein anderer Thread daraus liest, der Lesevorgang entweder den Wert vor der Schreiboperation oder nach der Schreiboperation erhält, aber niemals eine unterbrochen wird Wert zwischen der Schreiboperation (zB eine, bei der die ersten 32 Bit bereits neu sind, die letzten 32 Bit immer noch der alte Wert! Dies kann vorkommen, wenn Sie keinen atomaren Zugriff auf eine solche Variable verwenden).
Wenn Sie jedoch eine C-Struktur mit drei Werten haben, die aktualisiert werden sollen, selbst wenn Sie alle drei mit atomaren Operationen aktualisieren, handelt es sich um drei unabhängige Operationen. Daher könnte ein Leser die Struktur mit einem Wert bereits aktualisieren und zwei werden nicht aktualisiert. Hier benötigen Sie eine Sperre, wenn Sie sicherstellen müssen, dass der Leser entweder alle Werte in der Struktur als alte oder als neue Werte erkennt.
Eine Möglichkeit, Schlösser viel besser skalieren zu können, sind R/W-Sperren. In vielen Fällen sind Aktualisierungen von Daten eher selten (Schreiboperationen), aber der Zugriff auf die Daten ist sehr häufig (Lesen der Daten), denken Sie an Sammlungen (Hashtabellen, Bäume). In diesem Fall werden Ihnen R/W-Sperren einen enormen Leistungsgewinn bringen, da viele Threads gleichzeitig eine Lesesperre halten können (sie blockieren sich gegenseitig nicht) und nur wenn ein Thread eine Schreibsperre wünscht, alle anderen Threads sind für die Zeit gesperrt, in der das Update durchgeführt wird.
Der beste Weg zur Vermeidung von Thread-Problemen ist, keine Daten über Threads hinweg zu teilen. Wenn jeder Thread die meiste Zeit mit Daten beschäftigt, auf die kein anderer Thread zugreifen kann, brauchen Sie diese Daten überhaupt nicht zu sperren (auch keine atomaren Operationen). Versuchen Sie also, so wenig Daten wie möglich zwischen Threads freizugeben. Dann brauchen Sie nur einen schnellen Weg, um Daten zwischen Threads zu verschieben, wenn Sie wirklich müssen (ITC, Inter Thread Communication). Abhängig von Ihrem Betriebssystem, Ihrer Plattform und Programmiersprache (leider haben Sie uns keine von beiden gesagt), könnten verschiedene leistungsfähige Methoden für ITC existieren.
Und schließlich, ein weiterer Trick mit geteilten Daten zu arbeiten, aber ohne Sperren ist sicherzustellen, dass Threads nicht auf die gleichen Teile der freigegebenen Daten zugreifen. Z.B. Wenn sich zwei Threads ein Array teilen, aber eines immer nur auf even zugreifen wird, das andere nur ungerade Indizes, dann brauchen Sie kein Locking. Oder wenn sich beide den gleichen Speicherblock teilen und einer nur die obere Hälfte benutzt, der andere nur den unteren, braucht man keine Sperre. Es wird zwar nicht gesagt, dass dies zu einer guten Leistung führen wird; vor allem nicht bei Multi-Core-CPUs. Das Schreiben von Operationen eines Threads in diese gemeinsam genutzten Daten (das Ausführen eines Kerns) kann dazu führen, dass der Cache für einen anderen Thread (auf einem anderen Kern) geleert wird. Diese Cache-Flushes sind häufig der Engpass für Multithread-Anwendungen, die auf modernen Mehrkern-CPUs ausgeführt werden.
"Hier brauchen Sie ein Schloss, wenn Sie versichern müssen" ... Nein - Sie mutieren eine neue Kopie der Struktur, anstatt zu tun es an Ort und Stelle, und wechseln Sie, welche als Ihre atomare Operation aktiv ist. – moonshadow
Aber das heißt, Sie müssen wieder malloc, vorausgesetzt, dass dies nicht Stack-Daten sind (was es höchstwahrscheinlich nicht sein wird) und wie ich schon sagte, Malloc kann ein riesiger Flaschenhals sein. In einer unserer Software verursachte die Wiederverwendung des gleichen Speicherblocks jedes Mal im Vergleich zur Verwendung von malloc jedes Mal einen Geschwindigkeitsgewinn von 80%. – Mecki
Sie könnten stattdessen einen threadoptimierten malloc verwenden, der eine Thread-arena verwendet. –
Verwenden Sie in Java die Pakete java.util.concurrent in JDK 5+, anstatt eigene zu schreiben. Wie oben erwähnt, ist dies wirklich ein Bereich für Experten, und wenn Sie nicht ein oder zwei freie Jahre haben, ist das Rollen Ihrer eigenen keine Option.
Wenn Sie Ihre eigenen lock-free Datenstrukturen für eine Multi-Core-CPU schreiben, vergessen Sie nicht über Speicherbarrieren! Betrachten Sie auch Software Transaction Memory Techniken.
Verwenden Sie eine vorhandene Implementierung, da dieser Bereich der Arbeit ist der Bereich des Domain-Experten und PhDs (wenn man es richtig gemacht wollen!)
Zum Beispiel gibt es eine Bibliothek von Code ist hier:
Können Sie klären, was Sie mit Struktur meinen?
Momentan nehme ich an, Sie meinen die Gesamtarchitektur. Sie können dies erreichen, indem Sie keinen Speicher zwischen Prozessen freigeben und ein Aktormodell für Ihre Prozesse verwenden.
Werfen Sie einen Blick auf meine link ConcurrentLinkedHashMap für ein Beispiel zum Schreiben einer Lock-Free-Datenstruktur. Es basiert nicht auf wissenschaftlichen Arbeiten und erfordert keine jahrelange Forschung, wie andere vermuten lassen. Es braucht nur sorgfältiges Engineering.
Meine Implementierung verwendet eine ConcurrentHashMap, einen Lock-per-Bucket-Algorithmus, der jedoch nicht auf diese Implementierungsdetails angewiesen ist. Es könnte leicht durch clock-free-Implementierung von Cliff Click ersetzt werden. Ich habe eine Idee von Cliff ausgeliehen, aber viel expliziter verwendet, um alle CAS-Operationen mit einer Zustandsmaschine zu modellieren. Dies vereinfacht das Modell erheblich, da Sie sehen, dass ich über die Zustände psuedo sperrt. Ein weiterer Trick ist es, Faulheit und Entschlossenheit wie nötig zu ermöglichen. Sie werden dies oft mit Backtracking sehen oder anderen Threads "helfen" zu säubern. In meinem Fall habe ich beschlossen, tote Knoten auf der Liste zu entfernen, wenn sie den Kopf erreichen, anstatt mit der Komplexität umzugehen, sie aus der Mitte der Liste zu entfernen. Ich kann das ändern, aber ich habe meinem Backtracking-Algorithmus nicht ganz vertraut und wollte eine große Veränderung wie die Einführung eines 3-Node-Locking-Ansatzes aufschieben.
Das Buch "Die Kunst der Multiprozessor-Programmierung" ist eine großartige Grundierung. Insgesamt würde ich jedoch empfehlen, im Anwendungscode keine Lock-Free-Designs zu verwenden. Oft ist es einfach Overkill, wo andere, weniger fehleranfällige Techniken besser geeignet sind.
Auf der "concurrentlylinkedhashmap" gibt es jetzt einen interessanten Kommentar geschrieben: Hinweis: Eine seltene Rasse Zustand wurde von Greg Luck (Ehcache) aufgedeckt. Dieser Algorithmus ist veraltet. Ich denke, das zeigt, was zu erwarten ist, wenn Sie selbst sperren Daten frei entwickeln. – Suma
Dieser Kommentar ist seit Ewigkeiten da. Der Kommentar, dass das Projekt für persönliche pädagogische Zwecke zum Verständnis von gleichzeitigen Algorithmen gedacht war, ist seit einiger Zeit der Anfang. Sie versuchen, die Lock-Freiheit für Ihr eigenes persönliches Wachstum zu nutzen, und Sie versuchen, es für die Produktion zu vermeiden. Das ist ziemlich genau das, was ich in meinem ursprünglichen Beitrag gesagt habe. –
in re. Sumas Antwort, Maurice Herlithy, zeigt in The Art of Multiprocessor Programming, dass tatsächlich alles ohne Sperren geschrieben werden kann (siehe Kapitel 6). iirc, Dies beinhaltet im Wesentlichen das Aufteilen von Aufgaben in verarbeitende Knotenelemente (wie ein Funktionsabschluss) und das Einreihen jedes einzelnen. Threads berechnen den Status, indem sie alle Knoten vom zuletzt gecachten Knoten verfolgen. Offensichtlich könnte dies im schlimmsten Fall zu einer sequentiellen Leistung führen, aber es hat wichtige Eigenschaften ohne Sperren, wodurch Szenarien verhindert werden, in denen Threads für lange Zeitperioden geplant werden können, wenn sie Sperren halten. Herlithy erreicht auch eine theoretische, wartungsfreie Leistung, was bedeutet, dass ein Thread nicht ewig damit wartet, die atomare Enqueue zu gewinnen (das ist viel komplizierter Code).
Eine multi-threaded Warteschlange/Stack ist überraschend hart (überprüfen Sie die ABA problem). Andere Dinge können sehr einfach sein. Gewöhnen Sie sich an while (true) {atomicCAS, bis ich es getauscht habe} Blöcke; Sie sind unglaublich stark. Eine Intuition für das, was mit CAS richtig ist, kann bei der Entwicklung helfen, obwohl Sie gute Tests und möglicherweise leistungsfähigere Werkzeuge (vielleicht SKETCH, bevorstehende MIT Kendo oder spin?) Verwenden sollten, um die Korrektheit zu überprüfen, wenn Sie es auf eine einfache Struktur reduzieren können.
Bitte posten Sie mehr über Ihr Problem. Es ist schwierig, ohne Details eine gute Antwort zu geben.
bearbeiten Unzuverlässigkeit ist schön, aber es ist die Anwendbarkeit ist begrenzt, wenn ich es richtig verstehe. Es überwindet nicht wirklich die Gefahren nach dem Lesen; betrachte zwei Threads, die "mem = NewNode (mem)" ausführen; sie könnten beide Mem lesen, dann schreiben beide es; nicht das Richtige für eine klassische Inkrementfunktion. Es ist wahrscheinlich auch langsam wegen der Heap-Zuweisung (die über Threads synchronisiert werden muss).
Wenn Sie eine Sperrkonkurrenz sehen, würde ich zuerst versuchen, granularere Sperren für Ihre Datenstrukturen zu verwenden, anstatt vollständig blockierungsfreie Algorithmen.
Zum Beispiel arbeite ich derzeit an Multithread-Anwendung, die ein benutzerdefiniertes Messaging-System (Liste der Warteschlangen für jeden Thread, die Warteschlange enthält Nachrichten für Thread zu verarbeiten), um Informationen zwischen Threads übergeben. Es gibt eine globale Sperre für diese Struktur. In meinem Fall brauche ich nicht so viel Geschwindigkeit, also spielt es keine Rolle. Wenn diese Sperre jedoch zu einem Problem werden würde, könnte sie beispielsweise durch einzelne Sperren in jeder Warteschlange ersetzt werden.Das Hinzufügen/Entfernen von Elementen zur/von der spezifischen Warteschlange würde andere Warteschlangen nicht beeinträchtigen. Es würde immer noch eine globale Sperre für das Hinzufügen einer neuen Warteschlange und dergleichen geben, aber es würde nicht so viel streiten.
Sogar eine einzelne Warteschlange für mehrere Producer/Consumer kann mit granularem Locking für jedes Element geschrieben werden, anstatt eine globale Sperre zu haben. Dies kann auch Konflikte beseitigen.
Wie mein Professor (Nir Shavit aus "Die Kunst der Multiprozessor-Programmierung") der Klasse sagte: Bitte nicht. Der Hauptgrund ist die Testbarkeit - Sie können den Synchronisationscode nicht testen. Sie können Simulationen ausführen, Sie können sogar Stress-Test. Aber es ist bestenfalls grobe Annäherung. Was Sie wirklich brauchen, ist der mathematische Korrektheitsbeweis. Und nur wenige können sie verstehen, geschweige denn sie schreiben. Also, wie andere gesagt hatten: Verwenden Sie vorhandene Bibliotheken. Joe Duffy's blog untersucht einige Techniken (Abschnitt 28). Die erste, die Sie ausprobieren sollten, ist das Teilen von Bäumen - brechen Sie zu kleineren Aufgaben und kombinieren Sie.
Wenn Sie mehr Implementierungen und Papiere in Bezug auf das Thema zu lesen, werden Sie feststellen, gibt es folgendes gemeinsames Thema:
1) Gemeinsame Statusobjekte sind Lisp/clojure Stil inmutable: das heißt, alle Operationen schreiben werden implementiert, indem der existierende Zustand in ein neues Objekt kopiert wird, Änderungen an dem neuen Objekt vorgenommen werden und dann versucht wird, den gemeinsamen Zustand zu aktualisieren (erhalten von einem ausgerichteten Zeiger, der mit dem CAS-Grundelement aktualisiert werden kann). Mit anderen Worten, Sie ändern NIEMALS ein vorhandenes Objekt, das möglicherweise von mehr als dem aktuellen Thread gelesen wird. Inmutability kann optimiert werden, indem Copy-on-Write-Semantik für große, komplexe Objekte, aber das ist ein anderen Baum von Nüssen
2) Sie deutlich, was angeben erlaubten Übergänge zwischen dem aktuellen und nächsten Zustand gilt: Dann, dass der Algorithmus der Validierung ist gültig um Größenordnungen einfacher
3) Behandeln Sie verworfene Referenzen in Gefahrenhinweislisten pro Thread. Nachdem die Referenzobjekte sicher sind, wiederverwenden, wenn möglich
anderen damit verbundenen Beitrag von mir sehen, wo einiger Code implementiert mit Semaphore und Mutex ist (teilweise) in einem Lock-freien Stil neu implementiert: Mutual exclusion and semaphores
Ich denke, Sie bedeuten Gewindesichere verriegelungsfreie Struktur. –
Welche Sprache benutzen Sie? –