Wie kann ich eine Sperre freie Struktur schreiben?

StackOverflow https://stackoverflow.com/questions/92455

Frage

In meiner Multithread-Anwendung, und ich sehe schwere Lock-Conten darin, über mehrere Kerne gute Skalierbarkeit zu verhindern. Ich habe beschlossen, Lock freie Programmierung zu verwenden, um dies zu lösen.

Wie kann ich schreibe eine Sperre freie Struktur?

War es hilfreich?

Lösung

Kurze Antwort ist:

Sie können es nicht.

Lange Antwort lautet:

Wenn Sie diese Frage stellen, Sie wissen nicht, wahrscheinlich genug, um eine Sperre freie Struktur zu schaffen. Erstellen Lock freie Strukturen ist extrem hart, und nur Experten auf diesem Gebiet kann es tun. Statt Ihre eigenen 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 bewiesen ist, was sind die Einschränkungen - sogar gebrochen einige sperren sind frei Struktur anderen Menschen veröffentlicht

.

Wenn Sie nicht über eine Sperre freie Struktur entsprechend der Struktur finden Sie derzeit verwenden, sondern den Algorithmus anzupassen, so dass Sie einige vorhandene verwenden können.

Wenn Sie immer noch darauf bestehen, Ihr eigenes Schloss freie Struktur zu schaffen, sollten Sie:

  • beginnt mit etwas ganz einfachen
  • verstehen Speichermodell Ihrer Zielplattform (einschließlich Lese- / Schreib-Neuordnungs Einschränkungen, welche Operationen sind Atom)
  • Studium viel über Probleme, die andere Menschen begegnet, wenn Lock freie Strukturen Umsetzung
  • nicht nur erraten, ob es funktionieren wird, beweisen, dass es
  • stark testet das Ergebnis

Mehr lesen:

Lock frei und kostenlos Algorithmen bei Wikipedia warten

Herb Sutter: Lock-Free-Code: ein falsches Gefühl der Sicherheit

Andere Tipps

Verwenden Sie eine Bibliothek wie Intel Threading Building Blocks , es enthält nicht wenige Schloss -freien Strukturen und Algorithmen . Ich würde wirklich nicht empfehlen versuchen, schleusenfreien Code selbst zu schreiben, es ist extrem fehleranfällig und schwer richtig zu machen.

Schreib thread-safe Lock freier Code ist hart; aber dieser Artikel von Herb Sutter erhalten Sie begonnen haben.

Wie sblundy wies darauf hin, wenn alle Objekte unveränderlich sind, schreibgeschützt, Sie müssen aber keine Sorge über Sperren, dies bedeutet, dass Sie eine Menge kopieren können Objekte. Kopieren in der Regel beinhaltet malloc und malloc verwendet Sperren Speicherzuordnungen über Threads zu synchronisieren, so unveränderliche Objekte können Sie kaufen weniger, als Sie denken (malloc selbst skaliert ziemlich schlecht und malloc ist langsam , wenn Sie eine Menge von malloc tun in einer Performance kritischen Abschnitt, nicht erwarten, eine gute Leistung).

Wenn Sie nur einfache Variablen aktualisieren müssen (zB 32 oder 64 Bit int oder Zeiger), führen Sie einfach eine Addition oder Subtraktion Operationen auf ihnen oder tauschen nur die Werte von zwei Variablen, die meisten Plattformen bieten „atomare Operationen“ für das (weiter GCC bietet diese als gut). Atomic ist nicht die gleiche wie Thread-sicher . Allerdings Atom stellt sicher, dass, wenn ein Thread schreibt eine 64-Bit-Wert auf einen Speicherplatz zum Beispiel und ein anderer Thread liest von ihm, das Lesen eines entweder erhält den Wert vor dem Schreibvorgang oder nach dem Schreibvorgang, aber nie ein gebrochen Wert in-zwischen dem Schreibvorgang (zB eine, wo die ersten 32 Bit sind bereits die neue, die letzte 32-Bit immer noch der alte Wert sind! passieren Dies kann, wenn man auf eine solche Atom Zugang nicht verwenden Variable).

Wenn Sie jedoch eine C-Struktur mit drei Werten haben, dass selbst aktualisieren mögen, wenn Sie alle drei mit atomaren Operationen aktualisieren, das sind drei unabhängige Operationen, so dass ein Leser könnte die Struktur mit einem Wert sieht bereits Update und mehr zwei nicht aktualisiert. Hier müssen Sie eine Sperre, wenn Sie versichern müssen, den Leser entweder sieht alle Werte in der Struktur entweder die alten oder die neuen Werte zu sein.

Eine Möglichkeit, Sperren zu machen skalieren viel besser ist R / W-Sperren verwenden. In vielen Fällen sind Updates Daten sind eher selten (Schreiboperationen), aber die Daten zugreifen ist sehr häufig (Lesen der Daten), denken Sie an Sammlungen (Hash-Tabellen, Bäume). In diesem Fall R / W-Sperren finden Sie eine riesige Leistungssteigerung kaufen, wie viele Threads eine Lesesperre gleichzeitig halten können (sie werden nicht gegenseitig blockieren) und nur dann, wenn ein Thread will eine Schreibsperre, alle anderen Threads werden für die Zeit blockiert die Aktualisierung durchgeführt wird.

Der beste Weg, Thread-Probleme zu vermeiden, ist es keine Daten über Threads zu teilen. Wenn jeder Thread die meiste Zeit mit den Daten kein anderer Thread Zugriff hat befasst, werden Sie nicht für diese Daten überhaupt (auch keine atomare Operationen) Sperren müssen. So versucht, so wenig Daten wie möglich zwischen Threads zu teilen. Dann brauchen Sie nur einen schnellen Weg, um Daten zwischen Threads zu bewegen, wenn Sie wirklich (ITC, Inter Thema Kommunikation) haben. Je nach Betriebssystem, Plattform und Programmiersprache (leider gesagt Sie uns weder davon), verschiedene leistungsfähige Methoden für ITC existieren könnte.

Und schließlich ein weiterer Trick mit gemeinsam genutzten Daten zu arbeiten, aber ohne Verriegelung ist sicher Threads greifen nicht auf die gleichen Teile der gemeinsam genutzten Daten zu machen. Z.B. wenn zwei Threads ein Array teilen, aber man wird immer nur Zugriff auf eine noch das andere nur ungerade Indizes, müssen Sie keine Verriegelung. Oder wenn beide den gleichen Speicherblock teilen und verwendet man nur die obere Hälfte, die andere nur die unteren, dann ist keine Verriegelung. Obwohl es nicht gesagt, dass dies für eine gute Leistung führen; insbesondere nicht auf Multi-Core-CPUs. Schreiboperationen von einem Thread auf diesen freigegebenen Daten (ein Kern ausgeführt wird) kann der Cache für einen anderen Thread gespült werden (auf einem anderen Kern läuft), und diese Cache-Spülungen sind oft der Flaschenhals für die Multi-Thread-Anwendungen, die auf modernen Mehrkern-CPUs ausgeführt wird.

Als mein Professor (Nir Shavit von "The Art of Multi-Prozessor-Programmierung") sagte der Klasse: Bitte nicht. Der Hauptgrund ist die Testbarkeit - Sie nicht Synchronisations-Code testen. Sie können Simulationen ausführen, können Sie auch Test betonen. Aber es ist grobe Annäherung am besten. Was Sie wirklich brauchen, ist mathematisch Korrektheitsbeweis. Und nur sehr wenige der Lage Verständnis sie, geschweige denn sie zu schreiben. So, wie andere schon gesagt hatte: bestehende Bibliotheken. Joe Duffy Blog einige Techniken befragt (Abschnitt 28). Der erste Versuch sollte, ist Baum-Splitting -., Um kleinere Aufgaben brechen und kombinieren

Unveränderlichkeit ist ein Ansatz, Sperren zu vermeiden. Siehe Eric Lippert Diskussion und Umsetzung von Dingen wie unveränderliche Stacks und Warteschlangen .

in re. Suma Antwort, zeigt Maurice Herlithy in der Kunst der Multi-Prozessor-Programmierung, die eigentlich alles kann ohne Sperren geschrieben werden (siehe Kapitel 6). iirc handelt es sich dabei im wesentlichen spalt Aufgaben in die Verarbeitungsknotenelemente (wie eine Funktion Verschluss) und Einreihen jedes. Themen werden den Zustand von folgenden alle Knoten aus dem aktuell gecached man berechnen. Natürlich könnte dies im schlimmsten Fall dazu führen, dass sequentielle Leistung, aber es hat wichtige lockless Eigenschaften und verhindert Szenarien, in denen Themen geplant out für lange peroids Zeit bekommen konnten, wenn sie Schlösser halten. Herlithy erreicht auch theoretische Wartefreie Leistung, was bedeutet, dass ein Thread wird nicht ewig warten, am Ende zu dem Atom enqueue zu gewinnen (dies ist viel komplizierter Code).

Ein Multi-Threaded-queue / Stapel überraschend hart ist (siehe in ABA Problem ). Andere Dinge können sehr einfach sein. Sich daran gewöhnt, while (true) blockiert {atomicCAS, bis ich es vertauscht}; sie sind unglaublich mächtig. Eine Intuition für das, was mit CAS ist korrekt Entwicklung helfen kann, wenn Sie gute Tests und vielleicht auch mehr leistungsstarke Werkzeuge verwenden sollte (vielleicht SKETCH , kommende MIT Kendo oder Spin ?) Korrektheit zu überprüfen, ob Sie es auf eine einfache Struktur reduzieren.

Bitte senden Sie mehr über Ihr Problem. Es ist schwierig, eine gute Antwort, ohne Details zu geben.

Bearbeiten immutibility ist schön, aber es ist Anwendbarkeit begrenzt ist, wenn ich es richtig bin zu verstehen. Es ist nicht wirklich zu überwinden Schreibennach-lesen Gefahren; betrachten zwei Threads ausführen "mem = NewNode (MEM)"; sie mem beide lesen konnte, dann schreiben Sie beide es; nicht die richtige für eine Funktion klassischen Zuwachs. Außerdem ist es wahrscheinlich langsam aufgrund Heapzuordnung (die über Threads werden muss synchronisiert).

Inmutability würde diese Wirkung haben. Änderungen an das Objekt in einem neuen Objekt führen. Lisp arbeitet auf diese Weise unter der Decke.

Artikel 13 von Effective Java diese Technik erklärt.

Cliff Klicken Sie hat Kuppel einige wichtige Forschung auf Schloss freie Datenstrukturen, die durch endliche Automaten zu nutzen und auch viele Implementierungen für Java geschrieben. Sie können seine Papiere, Folien und Implementierungen auf seinem Blog: http://blogs.azulsystems.com/cliff/

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 hier:

http://www.cl.cam. ac.uk/research/srg/netos/lock-free/

Die meisten schleusenfreien Algorithmen oder Strukturen mit einiger atomaren Operation beginnen, das heißt eine Änderung zu einem gewissen Speicherplatz, die einmal von einem Thread begonnen wird abgeschlossen sein, bevor ein anderer Thread die gleiche Operation durchführen kann. Haben Sie eine solche Operation in Ihrer Umgebung?

Siehe hier für das kanonische Papier zu diesem Thema.

Versuchen Sie auch diese Wikipedia-Artikel Artikel für weitere Ideen und Links.

Das Grundprinzip für schleusenfreien Synchronisation ist dies:

  • , wenn Sie die Struktur lesen, folgen Sie dem Lesevorgang mit einem Test, um zu sehen, ob die Struktur mutiert war, da Sie die Lese gestartet, und wiederholen Sie, bis Sie beim Lesen erfolgreich sein, ohne etwas anderes zusammen zu kommen und mutiert, während Sie dabei;

  • , wenn Sie die Struktur mutieren, können Sie Ihren Algorithmus und Daten so anordnen, dass es ein einziger Atom Schritt ist, das, wenn genommen, die gesamte Änderung bewirkt, dass zu den anderen Fäden sichtbar werden, und ordnen die Dinge so, dass kein die Änderung ist sichtbar, es sei denn, dass der Schritt genommen wird. Sie verwenden, was lockfree Atom Mechanismus für diesen Schritt auf der Plattform vorhanden ist (z Vergleichs- und Satz, Load-Linked + store-bedingte, etc.). In diesem Schritt müssen Sie dann überprüfen, um zu sehen, ob ein anderer Thread das Objekt mutiert ist, da die Mutationsoperation begann, begehen, wenn sie nicht neu anfangen muss, wenn es hat.

Es gibt viele Beispiele für schleusenfreien Strukturen auf dem Netz; ohne mehr zu wissen, was Sie implementieren und auf welcher Plattform ist es schwer, um genauer zu sein.

Wenn Sie Ihre eigenen Schloss freie Datenstrukturen für einen Multi-Core-CPU schreiben, vergessen Sie nicht über Speicher Barrieren! Bedenken Sie auch einen Blick in Software Transaktionsspeicher Techniken.

Nun, hängt es von der Art der Struktur, aber Sie haben, um die Struktur zu machen, so dass sie vorsichtig und leise erkennen und behandeln mögliche Konflikte.

Ich bezweifle, dass Sie kann man machen, die 100% Lock-frei ist, aber wieder, es hängt davon ab, welche Art von Struktur benötigen Sie zu bauen.

Sie müssen möglicherweise auch die Struktur Scherbe, so dass mehrere Threads bei einzelnen Artikeln arbeiten, und dann später auf Synchronize / rekombinieren.

Wie bereits erwähnt, es hängt wirklich davon ab, welche Art von Struktur über Sie reden. Zum Beispiel können Sie eine begrenzte Lock-Frei-Warteschlange schreiben, aber nicht eine, den Direktzugriff ermöglicht.

Reduzieren oder gemeinsamen wandelbaren Zustand beseitigen.

In Java verwenden, um die java.util.concurrent Pakete in JDK 5+ stattdessen Ihre eigenen zu schreiben. Wie oben erwähnt wurde, ist dies wirklich ein Feld für Experten, und wenn Sie ein Ersatz oder zwei Jahre haben, Ihr eigenes Roll ist keine Option.

Können Sie erklären, was Sie durch die Struktur bedeuten?

Im Moment gehe ich davon aus Sie die gesamte Architektur bedeuten. Sie können es erreichen, indem nicht-Speicher zwischen Prozessen zu teilen, und durch ein Schauspieler-Modell für Ihre Prozesse verwendet wird.

Werfen Sie einen Blick auf meine Link ConcurrentLinkedHashMap rel="nofollow für ein Beispiel, wie eine Sperre schreiben -freie Datenstruktur. Es wird nicht auf irgendwelchen wissenschaftlichen Arbeiten beruhen und nicht Jahre der Forschung erfordern als andere bedeuten. Es dauert einfach vorsichtig Engineering.

tut Meine Implementierung einen ConcurrentHashMap verwenden, die ein Lock-per-Bucket-Algorithmus, aber es beruht nicht auf dieser Implementierung Detail. Es könnte leicht mit Cliff Klicken Sie auf die Lock-freie Implementierung ersetzt werden. Ich habe eine Idee von Cliff entlehnt, sondern verwenden viel mehr explizit, ist es, alle CAS-Operationen mit einer Zustandsmaschine zu modellieren. Dies vereinfacht das Modell, wie Sie sehen, dass ich psuedo Schleusen über die ‚ing Staaten haben. Ein weiterer Trick ist Faulheit und Entschlossenheit zu ermöglichen, je nach Bedarf. Sie werden das sehen oft mit Backtracking oder andere Threads „helfen“ zu bereinigen lassen. In meinem Fall habe ich beschlossen, toter Knoten auf der Liste zu ermöglichen geräumt werden, wenn sie den Kopf zu erreichen, anstatt dich mit der Komplexität sich von der Mitte der Liste zu entfernen. Ich kann das ändern, aber ich habe nicht ganz mein Backtracking-Algorithmus vertrauen und wollten eine große Veränderung wie die Annahme eines 3-Knoten Sperr Ansatz beiseite zu legen.

Das Buch "The Art of Multi-Prozessor-Programmierung" ist ein großer Primer. Insgesamt aber würde ich Lock-Free-Design im Anwendungscode zu vermeiden empfehlen. Oft ist es einfach übertrieben, wo andere, weniger fehleranfällig sind Techniken besser geeignet.

Wenn Sie Sperr-Konflikt sehen, würde ich zuerst versuchen, mehr granulare Sperren auf Ihre Datenstrukturen zu verwenden, anstatt vollständig Lock-Free-Algorithmen.

Beispiel Ich derzeit auf multithreaded Anwendung, die ein benutzerdefiniertes Nachrichtensystem (Liste von Warteschlangen für jede Gewinde enthalten die Warteschlangennachricht für Thread zu verarbeiten) Daten zwischen Threads zu übergeben. Es gibt eine globale Sperre auf dieser Struktur. In meinem Fall muss ich nicht Geschwindigkeit so viel, so dass es nicht wirklich wichtig. Aber wenn diese Sperre würde ein Problem werden, könnte es in jeder Warteschlange durch einzelne Schleusen ersetzt werden, zum Beispiel. Dann Hinzufügen / Entfernen von Elemente zu / von der bestimmten Warteschlange würde keine Auswirkungen auf andere Warteschlangen. Es wäre immer noch eine globale Sperre sein für das Hinzufügen neue Warteschlange und so, aber es wäre nicht so viel behauptet werden.

Selbst ein einzelne Multi produziert / Verbraucher Warteschlange kann mit körniger Verriegelung auf jedes Element geschrieben werden, anstatt eine globale Sperre zu haben. Dies kann auch Anstoß beseitigen.

Wenn Sie mehr Implementierungen und Papiere in Bezug auf das Thema zu lesen, werden Sie feststellen, gibt es folgendes gemeinsames Thema:

1) Status Geteilt Objekte sind Lisp / clojure Stil inmutable : das heißt, alle Schreiboperationen implementiert werden in einem neuen Objekt den bestehenden Zustand zu kopieren, machen Änderungen auf das neue Objekt und dann versuchen, zu aktualisieren der gemeinsam genutzten Zustand (von einem ausgerichteten Zeiger erhalten, die mit dem CAS primitiven aktualisiert werden kann). Mit anderen Worten, ändern Sie NIEMALS ein vorhandenes Objekt, das um mehr als den aktuellen Thread gelesen werden könnten. 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 klar festlegen, was erlaubt Übergänge zwischen den aktuellen und nächsten Zustand gelten : Dann Validieren, dass der Algorithmus gültig ist um Größenordnungen einfacher geworden

3) Griff verworfen Referenzen in Gefahrenzeigerlisten pro Thread . Nachdem die Referenzobjekte sicher sind, wiederverwenden, wenn möglich

Sehen Sie eine anderen verwandten Beitrag von mir, wo einiger Code implementiert mit Semaphore und Mutex ist (teilweise) in einem Lock-freien Stil neu implementiert: Ausschlußart und Semaphore

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top