Sperrfreie, konstante Update-Zeit für gleichzeitige Baumdatenstrukturen?

20

Ich habe in letzter Zeit ein bisschen Literatur gelesen und einige interessante Datenstrukturen gefunden.

Ich habe verschiedene Methoden untersucht, um die Aktualisierungszeiten auf Worst-Case-Aktualisierungszeit [1-7] herabzusetzen.O(1)

Vor kurzem habe ich begonnen, mich mit sperrenfreien Datenstrukturen zu befassen, um einen effizienten gleichzeitigen Zugriff zu ermöglichen.

Wurde eine dieser Worst-Case -Update-Time-Techniken bei der Implementierung von sperrenfreien Datenstrukturen verwendet?O(1)

Ich frage weil; Für mich scheinen sie die offensichtliche praktische Erweiterung dieser "theoretischen Verbesserung" zu sein.


  1. Tarjan, Robert Endre. „Aktualisieren eines ausgeglichenen Suchbaums in O (1) -Rotationen.“ Informationsverarbeitungsbuchstaben 16, Nr. 5 (1983): 253 & ndash; 257.

  2. Driscoll, JR, N. Sarnak, DD Sleator und RE Tarjan. "Datenstrukturen persistent machen". In Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, 109–121. STOC '86. New York, NY, USA: ACM, 1986.

  3. Levcopoulos, C. und Mark H. Overmars. "Ein ausgeglichener Suchbaum mit O (1) Worst Case-Aktualisierungszeit." Acta Inf. 26, nein. 3 (November 1988): 269–277.

  4. Fleischer, Rudolf. Ein einfacher ausgeglichener Suchbaum mit O (1) Worst Case-Aktualisierungszeit

  5. Dietz, Paul F und Rajeev Raman. "Ein Finger-Suchbaum mit konstanter Aktualisierungszeit". Informationsverarbeitungsbuchstaben 52, Nr. 3 (1994): 147-154.

  6. Lagogiannis, George, Christos Makris, Yannis Panagis, Spyros Sioutas und Kostas Tsichlas. "Neue Dynamic Balanced Search Trees mit konstanter Aktualisierungszeit im schlimmsten Fall." J. Autom. Lang. Kamm. 8, nein. 4 (Juli 2003): 607–632.

  7. Brodal, Gerth Stølting, George Lagogiannis, Christos Makris, Athanasios Tsakalidis und Kostas Tsichlas. „Optimale Fingersuchbäume in der Zeigermaschine.“ J. Comput. Syst. Sci. 67, nein. 2 (September 2003): 381–418.

BEIM
quelle
2
Fügen Sie möglicherweise Links zu den Artikeln hinzu, um Personen zu helfen, die Ihr Problem untersuchen möchten.
Raphael
3
Okay, in Links zu den jeweiligen Artikeln hinzugefügt.
AT
1
Ich schlage vor, bei cstheory.SE (mit einem Link zurück hier) neu zu posten, wenn Sie nicht bald eine nützliche Antwort erhalten.
JeffE
1
Danke für den Vorschlag. Ich habe neu gepostet: Lock-free, konstante Update-Zeit gleichzeitige
AT
Ich habe zuvor die Bibliothek Praktische sperrfreie Datenstrukturen verwendet . Sie unterstützen teilweise sperrenfreie Baumdatenstrukturen. Vielleicht haben die, wonach Sie suchen.
Reza

Antworten:

4

O(1) hilft nicht an und für sich. In einer gesperrten Datenstruktur muss es eine einzelne atomare Instanz geben, wenn sich Ihre Datenstruktur zu ändern scheint. Alle Repräsentationsinvarianten müssen sowohl unmittelbar vor als auch unmittelbar nach diesem atomaren Moment in Kraft sein.

Wenn Sie also eine Änderung an der Datenstruktur vornehmen, besteht das wichtige Merkmal darin, dass Sie alle Änderungen an einer privaten Datenstruktur vornehmen und die Änderungen dann in einer einzelnen atomaren Anweisung austauschen können.

Die Freiheit von Sperren ist normalerweise am einfachsten, wenn Ihre Datenstrukturen unveränderlich ( rein funktional ) sind. Sie behalten einfach einen globalen Zeiger auf die aktuelle Version der Datenstruktur. Leser müssen nichts sperren. Änderungen an der Datenstruktur werden bewirkt, indem der globale Zeiger auf eine unveränderbare Datenstruktur auf eine andere ausgetauscht wird.

Zum Beispiel: Wenn Sie einen rein funktionalen Baum mit ausgeglichenem Baum haben, haben Sie:

  1. Zeichnen Sie den aktuellen globalen Zeiger auf die Wurzel des Baums auf.
  2. Erstellen Sie einen neuen Baum, der einen Knoten einfügt oder löscht. (Dies ist zeitlich und räumlich logarithmisch in Bezug auf die Anzahl der aktuell in der Struktur vorhandenen Knoten und umfasst das Erstellen neuer Knoten vom Änderungspunkt bis zur Wurzel und das Zeigen aller neuen Knoten auf die alten Teile der vorherigen Version der Datenstruktur. )
  3. Vergleichen Sie den globalen Zeiger atomar und tauschen Sie ihn gegen den Stamm aus. (Beachten Sie, dass dies möglicherweise fehlschlägt, wenn zwischen der Aufzeichnung des alten Stammzeigers und jetzt eine andere Änderung stattgefunden hat. In diesem Fall kehren Sie zu Schritt 1 zurück und versuchen es erneut. Dies ist die sogenannte "optimistische Parallelitätskontrolle".)

Beachten Sie, dass der wichtigste Teil das ist, was ich oben über die Aufrechterhaltung von Repräsentationsinvarianten gesagt habe. Es ist normalerweise nicht ausreichend, einen Algorithmus zu haben, der eine atomare Änderung in der Mitte des Baums vornimmt. Warum? Beispiel: Möglicherweise haben Sie einen Reader-Thread, der gerade eine Vorbestellung für den Baum durchläuft. Wenn Sie einen Knoten ändern, der ein Vorfahr des Knotens ist, den sie gerade lesen, werden Sie die Voraussetzungen ungültig machen, die sie für erzwungen hielten. Der Leser muss in der Lage sein, mit der Datenstruktur genau so zu arbeiten, wie sie vor Ihrer Änderung war, oder genau so, wie sie nach der Änderung sein wird. Nichts dazwischen.

Edit : Wie @Raphael hervorhob, gibt es Techniken, um veränderbare Datenstrukturen frei von Sperren zu machen. Ein konstruktiver Beweis dafür, dass dies immer möglich ist, ist: Solange Sie einen einzigen globalen Zeiger auf die "Spitze" Ihrer Datenstruktur haben, können Sie, auch wenn diese veränderlich ist, immer die gesamte Datenstruktur kopieren und Ihre Mods in die kopieren Kopieren Sie die Daten, und versuchen Sie dann mithilfe der optimistischen Parallelitätssteuerung, den Zeiger auf Ihre neu erstellte Datenstruktur für das Original zu vergleichen und auszutauschen. Das Schöne an funktionalen baumbasierten Datenstrukturen ist, dass sie die Kosten für das Kopieren bei einer Datenstruktur der Größe .O ( N )O(log(N))O(N)

Wandering Logic
quelle
Ich denke, aktive Wartetechniken, z. B. mit Compare-and-Swap, werden normalerweise als "lock free" bezeichnet, sodass es auch in der veränderlichen Umgebung einige Auswege gibt.
Raphael
Ich kenne den Begriff aktives Warten nicht (und Google hilft nicht). (Wenn Sie über die Arbeit von Kogan und Petrank sprechen, zeigt dies, wie Sie Algorithmen ohne Sperren in wartefreie umwandeln können.) Ich habe eine Bearbeitung hinzugefügt, die beschreibt, wie Sie mit der Veränderlichkeit von Sperren im Allgemeinen umgehen können.
Wandering Logic
Mit "aktiv warten" meine ich so etwas wie while ( !P ) { noOp(); } doWork();wo noOpein sleepoder ähnliches sein kann.
Raphael
Im Teil Bearbeiten haben Sie die Technik erwähnt, mit der sich veränderbare Datenstrukturen sperren lassen. Wie angegeben kopieren wir die gesamte Datenstruktur, nehmen Modifikationen an der Kopie vor und verwenden dann das CAS-Grundelement. Aber wie macht man den CopySchritt atomar? Es scheint ein weiteres schwieriges Problem zu sein atomic snapshot.
Hengxin
@hengxin: Stellen Sie sich das CAS-Grundelement als "Publish" -Operator vor. Bevor die Datenstruktur veröffentlicht wird, hat nur der Thread, der die Änderungen vornimmt, Zugriff darauf. Nachdem die Datenstruktur veröffentlicht wurde, ist sie unveränderlich. Der Kopierschritt muss nicht atomar sein, da das einzige, was ein Thread kopieren könnte, eine veröffentlichte Version ist, die unveränderlich ist. Wenn zwei Threads gleichzeitig versuchen, sich zu verändern, kopieren sie beide dieselbe unveränderliche Datenstruktur, ändern ihre lokalen Kopien und dann ist eine der CAS-Operationen erfolgreich und die andere schlägt fehl. Derjenige, der fehlschlägt, muss erneut kopiert und aktualisiert werden.
Wandering Logic