Nicht blockierender Algorithmus

Nicht zu verwechseln mit Nicht blockierende i/o.

Im Informatik, ein Algorithmus wird genannt nicht blockierend Wenn Fehler oder Suspension von jedem Faden kann nicht ein Versagen oder eine Suspendierung eines anderen Fadens verursachen;[1] Für einige Operationen bieten diese Algorithmen eine nützliche Alternative zu traditioneller Blockierung von Implementierungen. Ein nicht blockierender Algorithmus ist lockfrei Wenn es garantiert systemweit ist Fortschritt, und Wartenfrei Wenn es auch einen garantierten Fortschritt pro Thread gibt. "Nicht blockierende" wurde als Synonym für "lock-frei" in der Literatur bis zur Einführung von Obstruktionsfreiheit im Jahr 2003 verwendet.[2]

Das Wort "nicht blockierend" wurde traditionell verwendet, um zu beschreiben Telekommunikationsnetzwerke Dies könnte eine Verbindung über eine Reihe von Relais "„ ohne vorhandene Anrufe neu arrangieren “weiterleiten (siehe CLOS -Netzwerk). Auch wenn der Telefonaustausch "nicht defekt ist, kann sie immer die Verbindung herstellen" (siehe Nicht blockierter minimaler Spannungsschalter).

Motivation

Hauptartikel: Nachteile von Schlösser

Der traditionelle Ansatz für die Programmierung mit mehreren Threads ist die Verwendung Schlösser Synchronisieren Sie den Zugriff auf gemeinsame Nutzung Ressourcen. Synchronisationsprimitive wie z. Mutexes, Semaphoren, und Kritische Abschnitte sind alle Mechanismen, mit denen ein Programmierer sicherstellen kann, dass bestimmte Codeabschnitte nicht gleichzeitig ausgeführt werden, wenn dies die gemeinsam genutzten Speicherstrukturen beschädigt würde. Wenn ein Thread versucht, ein Schloss zu erwerben, das bereits von einem anderen Faden gehalten wird, blockiert der Faden, bis das Schloss frei ist.

Das Blockieren eines Fadens kann aus vielen Gründen unerwünscht sein. Ein offensichtlicher Grund ist, dass der Faden zwar blockiert ist, aber nichts erreichen kann: Wenn der blockierte Faden eine Hochpriorität durchgeführt hat oder Echtzeit Aufgabe, es wäre sehr unerwünscht, ihren Fortschritt zu stoppen.

Andere Probleme sind weniger offensichtlich. Zum Beispiel können bestimmte Wechselwirkungen zwischen Schlösser zu Fehlerbedingungen wie z. Sackgasse, Lebensunterhalt, und Prioritätsinversion. Die Verwendung von Schlösser beinhaltet auch einen Kompromiss zwischen grobkörnigem Verriegelungen, was die Möglichkeiten für erheblich verringern kann Parallelitätund feinkörniges Verriegelung, das sorgfältiger Design erfordert, erhöht das Verriegelungsaufwand und ist anfälliger für Fehler.

Im Gegensatz zum Blockieren von Algorithmen leiden nicht blockierende Algorithmen nicht an diesen Nachteilen und sind außerdem sicher für den Einsatz in Interrupt Handler: obwohl die vorbewegt Thread kann nicht wieder aufgenommen werden, der Fortschritt ist ohne ihn immer noch möglich. Im Gegensatz dazu kann globale Datenstrukturen, die durch gegenseitige Ausschluss geschützt sind, in einem Interrupt -Handler nicht sicher zugegriffen werden, da der vorbefragte Thread möglicherweise derjenige ist, der die Sperre hält - aber dies kann leicht behoben werden, indem die Interrupt -Anfrage während des kritischen Abschnitts maskiert wird.[3]

Eine lock-freie Datenstruktur kann verwendet werden, um die Leistung zu verbessern. Eine lock-freie Datenstruktur erhöht die Zeit, die die für die parallele Ausführung aufgewendete Zeit verbracht hat, und nicht die serielle Ausführung, wodurch die Leistung auf a verbessert wird Multi-Core-Prozessor, weil der Zugriff auf die gemeinsame Datenstruktur nicht serialisiert werden muss, um kohärent zu bleiben.[4]

Implementierung

Mit wenigen Ausnahmen verwenden nicht blockierende Algorithmen Atomic Read-Modify-Write Primitive, die die Hardware liefern muss, die bemerkenswerteste davon ist vergleichen und tauschen (CAS). Kritische Abschnitte werden fast immer unter Verwendung von Standardschnittstellen über diese Primitiven implementiert (im allgemeinen Fall blockieren kritische Abschnitte, selbst wenn sie mit diesen Primitiven implementiert werden). In den neunziger Jahren mussten alle nicht blockierenden Algorithmen "nativ" mit den zugrunde liegenden Primitiven geschrieben werden, um eine akzeptable Leistung zu erzielen. Das aufstrebende Feld von jedoch Software -Transaktionsspeicher Verspricht Standardabstraktionen zum Schreiben eines effizienten nicht blockierenden Code.[5][6]

Es wurde auch viel Forschung bei der Bereitstellung von Basic durchgeführt Datenstrukturen wie zum Beispiel Stapel, Warteschlangen, Sets, und Hash -Tische. Diese ermöglichen es den Programmen, Daten zwischen Threads asynchron auszutauschen.

Darüber hinaus sind einige nicht blockierende Datenstrukturen schwach genug, um ohne spezielle atomare Primitiven implementiert zu werden. Diese Ausnahmen umfassen:

  • Ein Einzelschreiber mit einem Leiter Ringpuffer FIFO, mit einer Größe, die den Überlauf eines der verfügbaren unsignierten ganzzahligen Typen gleichmäßig spaltet, kann bedingungslos sein sicher implementiert mit nur a Speicherbarriere
  • Read-Copy-Update mit einem einzelnen Schriftsteller und einer beliebigen Anzahl von Lesern. (Die Leser sind wartenfrei; der Verfasser ist normalerweise lockerfrei, bis er die Erinnerung zurückerhalten muss).
  • Read-Copy-Update mit mehreren Autoren und einer beliebigen Anzahl von Lesern. (Die Leser sind wartenfrei; mehrere Autoren serialisieren im Allgemeinen mit einem Schloss und sind nicht obstruktivfrei).

Mehrere Bibliotheken verwenden intern lock-freie Techniken,[7][8][9] Es ist jedoch schwierig, einen lockfreien Code zu schreiben, der korrekt ist.[10][11][12][13]

Nicht blockierende Algorithmen umfassen im Allgemeinen eine Reihe von Lese-, Read-Modify-Write und Schreiben von Anweisungen in einer sorgfältig gestalteten Reihenfolge. Optimierung von Compilern kann die Operationen aggressiv neu arrangieren. Auch wenn sie es nicht tun, ordnen viele moderne CPUs solche Operationen oft neu (sie haben eine "schwache Konsistenzmodell"), es sei denn a Speicherbarriere wird verwendet, um der CPU nicht neu zu ordnen.C ++ 11 Programmierer können verwenden std :: atomic in , und C11 Programmierer können verwenden , beide Liefertypen und Funktionen, die dem Compiler sagen, dass er solche Anweisungen nicht neu arrangieren und die entsprechenden Speicherbarrieren einfügen soll.[14]

Warten Sie

Das Wartenschutz ist die stärkste nicht blockierende Garantie für den Fortschritt und kombiniert den garantierten systemweiten Durchsatz mit Hunger-Freiheit. Ein Algorithmus ist wartenfrei, wenn jede Operation die Anzahl der Schritte, die der Algorithmus vor Abschluss der Operation erfolgt, eine Grenze enthält.[15] Diese Eigenschaft ist für Echtzeitsysteme von entscheidender Bedeutung und ist immer schön zu haben, solange die Leistungskosten nicht zu hoch sind.

Es wurde in den 1980er Jahren gezeigt[16] Dass alle Algorithmen implementiert werden können, wartungsfrei und viele Transformationen aus dem Seriencode genannt werden Universelle Konstruktionen, wurden demonstriert. Die daraus resultierende Leistung passt jedoch im Allgemeinen nicht einmal naive Blockierungsdesigns. Inzwischen haben mehrere Papiere die Leistung von universellen Konstruktionen verbessert, aber ihre Leistung liegt weit unter den Blockierungsdesigns.

Mehrere Papiere haben die Schwierigkeit untersucht, wartenfreie Algorithmen zu erstellen. Zum Beispiel wurde es gezeigt[17] dass das weit verbreitete Atomic bedingt Primitive, CAS und Ll/sc, können nicht hungerfreie Implementierungen vieler gemeinsamer Datenstrukturen bereitstellen, ohne dass Speicherkosten in der Anzahl der Threads linear wachsen.

In der Praxis präsentieren diese unteren Grenzen jedoch keine reale Barriere, da die Ausgabe einer Cache -Linie oder eines ausschließlichen Reservierungskörners (bis zu 2 KB auf dem Arm) pro Thread im gemeinsamen Speicher nicht als zu kostspielig für praktische Systeme (in der Regel die Menge an als zu kostspielig angesehen wird Logisch gefordert ist ein Wort, aber physikalisch CAS -Operationen in derselben Cache -Linie kollidieren, und LL/SC -Operationen in derselben exklusiven Reservierungsgranula kollidieren, sodass die Menge an speicherner physisch erforderlich ist).

Wartefreie Algorithmen waren bis 2011 selten, sowohl in der Forschung als auch in der Praxis. Im Jahr 2011 Kogan und 2011 Petrank[18] präsentierte ein wartungsfreies Warteschlangengebäude am CAS Primitiv, allgemein auf gemeinsamer Hardware verfügbar. Ihre Konstruktion erweiterte die schlossfreie Warteschlange von Michael und Scott.[19] Dies ist eine effiziente Warteschlange, die in der Praxis häufig verwendet wird. Ein Follow-up-Papier von Kogan und Petrank[20] bildete eine Methode zum schnellen Wartungsfree-Algorithmen und verwendete diese Methode, um die Wartefreie Warteschlange praktisch so schnell wie das lock-freie Gegenstück zu machen. Ein nachfolgendes Papier von Timnat und Petrank[21] bildete einen automatischen Mechanismus für die Erzeugung von Wartefreiheitsdatenstrukturen von lock-freien. Daher stehen für viele Datenstrukturen jetzt auf wartfreie Implementierungen verfügbar.

Lock-Freedom

Durch Lock-Freedom können einzelne Fäden verhungern, aber den systemweiten Durchsatz garantiert. Ein Algorithmus ist lockfrei, wenn, wenn die Programm-Threads für eine ausreichend lange Zeit ausgeführt werden, mindestens einer der Threads Fortschritte macht (für eine vernünftige Definition des Fortschritts). Alle wartungsfreien Algorithmen sind lockfrei.

Wenn ein Faden suspendiert wird, garantiert sich ein lockfreier Algorithmus, wenn ein Gewinde-Algorithmus garantiert, dass die verbleibenden Fäden weiterhin Fortschritte machen können. Wenn also zwei Threads für dasselbe Mutex -Sperre oder Spinlock kämpfen können, ist der Algorithmus also nicht lockfrei. (Wenn wir einen Thread aussetzen, der das Schloss enthält, blockiert der zweite Thread.)

Ein Algorithmus ist lock-frei, wenn es unendlich oft von einigen Prozessoren betrieben wird, um eine begrenzte Anzahl von Schritten zu erzielen. Zum Beispiel wenn, wenn N Prozessoren versuchen, eine Operation auszuführen, einige der N Es wird es den Prozessen gelingen, den Betrieb in einer begrenzten Anzahl von Schritten zu beenden, und andere könnten scheitern und wieder ausfallen. Der Unterschied zwischen waartfrei und lockfrei ist, dass die Wartezeit ohne jeden Prozess unabhängig von den anderen Prozessoren garantiert erfolgreich ist.

Im Allgemeinen kann ein lock-freier Algorithmus in vier Phasen ausgeführt werden: Abschluss des eigenen Betriebs, Unterstützung eines Behinderungsbetriebs, Abbruch eines obstrudierenden Betriebs und Warten. Der Abschluss des eigenen Betriebs wird durch die Möglichkeit einer gleichzeitigen Unterstützung und Abtreibung kompliziert, aber ausnahmslos der schnellste Weg zur Fertigstellung.

Die Entscheidung darüber, wann sie helfen, abbrechen oder warten müssen, wenn eine Behinderung erfüllt ist, liegt in der Verantwortung von a Streitleiter. Dies kann sehr einfach sein (Unterstützung mit höherer Priorität, operieren Sie niedrigere Priorität) oder kann optimierter sein, um einen besseren Durchsatz zu erzielen oder die Latenz der priorisierten Operationen zu senken.

Richtige gleichzeitige Unterstützung ist in der Regel der komplexeste Teil eines lockfreien Algorithmus und oft sehr kostspielig: Der Assistenzfaden verlangsamt sich nicht nur, sondern dank der Mechanik des gemeinsamen Speichers wird auch der zu unterstützende Thread verlangsamt, auch der Thread wird verlangsamt, auch dank der Mechanik des gemeinsamen Speichers wird auch der Thread verlangsamt, ebenfalls langsamer , wenn es noch läuft.

Obstruktionsfreiheit

Obstruktionsfreiheit ist die schwächste, nicht blockierende Fortschrittsgarantie. Ein Algorithmus ist obstruktivfrei, wenn zu einem bestimmten Zeitpunkt ein einzelner Faden (d. H. Alle obstrudierenden Gewinde ausgesetzt) ​​für eine begrenzte Anzahl von Schritten seinen Betrieb abschließen.[15] Alle lockfreien Algorithmen sind obstruktivfrei.

Die Obstruktionsfreiheit verlangt nur, dass ein teilweise abgeschlossener Betrieb abgebrochen und die Änderungen zurückgerollt werden können. Das Ablegen gleichzeitiger Unterstützung kann häufig zu viel einfacheren Algorithmen führen, die leichter zu validieren sind. Verhinderung des Systems kontinuierlich Live-Sperrung ist die Aufgabe eines Streitmanagers.

Einige obstruktiv-freie Algorithmen verwenden in der Datenstruktur ein Paar "Konsistenzmarker". Verarbeitet das Lesen der Datenstruktur zuerst einen Konsistenzmarker, las die relevanten Daten in einen internen Puffer, dann den anderen Marker und vergleichen die Markierungen. Die Daten sind konsistent, wenn die beiden Marker identisch sind. Markierungen können nicht identisch sein, wenn das Lesedauer durch einen anderen Prozess unterbrochen wird, der die Datenstruktur aktualisiert. In einem solchen Fall leitet der Prozess die Daten im internen Puffer ab und versucht erneut.

Siehe auch

Verweise

  1. ^ Göetz, Brian; Peierls, Tim; Bloch, Joshua; Bowbeer, Joseph; Holmes, David; Lea, Doug (2006). Java Parallelität in der Praxis. Upper Saddle River, NJ: Addison-Wesley. p.41. ISBN 9780321349606.
  2. ^ Herlihy, M.; Luchangco, V.; Moir, M. (2003). Obstruktiv-freie Synchronisation: Zwei-End-Warteschlangen als Beispiel als Beispiel (PDF). 23. Internationale Konferenz über verteilte Computersysteme. p. 522.
  3. ^ Butler W. Lampson; David D. Redell (Februar 1980). "Erfahrung mit Prozessen und Monitoren in Mesa". Kommunikation der ACM. 23 (2): 105–117. Citeseerx 10.1.1.142.5765. doi:10.1145/358818.358824. S2CID 1594544.
  4. ^ Guillaume Marçais und Carl Kingsford."Ein schneller, lockfreier Ansatz für eine effiziente parallele Zählung von Vorkommen von K-MERS". Bioinformatik (2011) 27 (6): 764-770.doi:10.1093/bioinformatics/btr011 "Qualle Mer Counter".
  5. ^ Harris, Tim; Fraser, Keir (26. November 2003). "Sprachunterstützung für leichte Transaktionen" (PDF). ACM Sigplan nennt. 38 (11): 388. Citeseerx 10.1.1.58.8466. doi:10.1145/949343.949340.
  6. ^ Harris, Tim; Marlow, S.; Peyton-Jones, S.; Herlihy, M. (15. bis 17. Juni 2005). "Komponierbare Speichertransaktionen". Verfahren des ACM Sigplan -Symposiums 2005 über Prinzipien und Praxis der parallelen Programmierung, PPOPP '05: Chicago, Illinois. New York, NY: ACM Press. S. 48–60. doi:10.1145/1065944.1065952. ISBN 978-1-59593-080-4.
  7. ^ libcds - C ++ Bibliothek von schlossfreien Behältern und sicherem Speicher-Rückgewinnungsschema
  8. ^ LIBLFDS - Eine Bibliothek mit lock-freien Datenstrukturen, geschrieben in C.
  9. ^ Parallelitätskit - Eine C-Bibliothek für nicht blockierende Systemdesign und -implementierung
  10. ^ Kräuter Sutter. "Sperrfreier Code: Ein falsches Sicherheitsgefühl". Archiviert von das Original Am 2015-09-01.
  11. ^ Kräuter Sutter. "Schreiben lock-freier Code: Eine korrigierte Warteschlange". Archiviert von das Original am 2008-12-05.
  12. ^ Kräuter Sutter. "Schreiben einer verallgemeinerten gleichzeitigen Warteschlange".
  13. ^ Kräuter Sutter. "Das Problem mit Schlössern".
  14. ^ Bruce Dawson."Arm und lockfreie Programmierung".
  15. ^ a b Anthony Williams."Sicherheit: Off: Wie man sich nicht mit C ++ Atomics in den Fuß schießt". 2015. p. 20.
  16. ^ Herlihy, Maurice P. (1988). Unmöglichkeits- und Universalitätsergebnisse für die wartungsfreie Synchronisation. Proc. 7. jährliches ACM Symp. über Prinzipien des verteilten Computers. S. 276–290. doi:10.1145/62546.62593. ISBN 0-89791-277-2.
  17. ^ Fich, Glaube; Hendler, Danny; Shavit, Nir (2004). Über die inhärente Schwäche der bedingten Synchronisationprimitive. Proc. 23. jährliches ACM Symp.on Principles of Distributed Computing (PODC). S. 80–87. doi:10.1145/1011767.1011780. ISBN 1-58113-802-4.
  18. ^ Kogan, Alex; Petrank, Erez (2011). Wartenfreie Warteschlangen mit mehreren Enqueuers und Dequeuers (PDF). Proc. 16. ACM Sigplan Symp. über Prinzipien und Praxis der parallelen Programmierung (ppopp). S. 223–234. doi:10.1145/1941553.1941585. ISBN 978-1-4503-0119-0.
  19. ^ Michael, Magne; Scott, Michael (1996). Einfache, schnelle und praktische nicht blockierende und blockierende gleichzeitige Warteschlangenalgorithmen. Proc. 15. jährliches ACM Symp. über Prinzipien des verteilten Computers (PODC). S. 267–275. doi:10.1145/248052.248106. ISBN 0-89791-800-2.
  20. ^ Kogan, Alex; Petrank, Erez (2012). Eine Methode zum Erstellen schneller Wartefreiheitsdatenstrukturen. Proc. 17. ACM Sigplan Symp. über Prinzipien und Praxis der parallelen Programmierung (ppopp). S. 141–150. doi:10.1145/2145816.2145835. ISBN 978-1-4503-1160-1.
  21. ^ Timnat, Shahar; Petrank, Erez (2014). Eine praktische, wartungsfreie Simulation für lockfreie Datenstrukturen. Proc. 17. ACM Sigplan Symp. über Prinzipien und Praxis der parallelen Programmierung (ppopp). S. 357–368. doi:10.1145/2692916.2555261. ISBN 978-1-4503-2656-8.

Externe Links