Wie viele ABA-Tag-Bits werden in sperrfreien Datenstrukturen benötigt?

Die Menge der Tag-Bits, die praktisch sicher ist, kann basierend auf der Vorkaufszeit und der Häufigkeit der Zeigeränderungen geschätzt werden.

Zur Erinnerung, das ABA-Problem tritt auf, wenn ein Thread den Wert liest, den er mit Compare-and-Swap ändern möchte, wird Preempted, und wenn er fortfährt, entspricht der tatsächliche Wert des Zeigers dem, was der Thread zuvor gelesen hat . Daher kann die Vergleichs- und Austauschoperation trotz Datenstrukturmodifikationen, die möglicherweise während der Vorbearbeitungszeit von anderen Threads ausgeführt wurden, erfolgreich sein.

Die Idee des Hinzufügens des monoton inkrementierten Tags besteht darin, jede Modifikation des Zeigers einzigartig zu machen. Damit es erfolgreich ist, müssen Inkremente eindeutige Tag-Werte während der Zeit erzeugen, in der ein modifizierender Thread möglicherweise verhindert wird. d. h. für garantierte Korrektheit kann das Tag während der gesamten Vorbearbeitungszeit nicht umlaufen.

Nehmen wir an, dass die Vorbelegung eine einzelne OS-Planungszeitscheibe dauert, die typischerweise zehn bis hundert Millisekunden beträgt. Die Latenz von CAS auf modernen Systemen beträgt zehn bis Hunderte von Nanosekunden. Eine grobe Worst-Case-Schätzung ist, dass es möglicherweise Millionen von Zeigermodifikationen gibt, während ein Thread vorweggenommen ist, und daher sollte es mehr als 20 Bits in dem Tag geben, damit es nicht umgebrochen wird.

In der Praxis kann es möglich sein, basierend auf der bekannten Häufigkeit von CAS-Operationen eine bessere Schätzung für einen bestimmten realen Anwendungsfall zu machen. Man muss auch die Worst-Case-Vorkaufszeit genauer abschätzen; Zum Beispiel könnte ein Thread mit niedriger Priorität, der von einem Job mit höherer Priorität vorweggenommen wurde, eine viel längere Vorlaufzeit haben.

Laut dem Papier

Ссылка Gefahrenhinweise: Sichere Speicherrückgewinnung für blockierungsfreie Objekte (IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 15, NO. 6, JUNI 2004, S. 491) von PhD Maged M. Michael

Tag-Bits sollten so groß sein, dass ein Wraparound in echten lockfreien Szenarien unmöglich ist (Ich kann dies so lesen, als ob Sie N Threads ausführen könnten und jeder auf die Struktur zugreifen könnte. Sie sollten mindestens N + 1 verschiedene Zustände für Tags haben):

  

6.1.1 IBM ABA-Prevention-Tags

     

Die früheste und einfachste Lock-Free-Methode für die Wiederverwendung von Knoten ist   die Methode tag (update counter), die mit der Methode   Dokumentation von CAS auf dem IBM System 370 [11]. Es   erfordert die Zuordnung eines Tags zu jedem Ort, der der ist   Ziel von ABA-anfälligen Vergleichsoperationen. Durch Inkrementieren   das Tag, wenn der Wert des zugehörigen Ortes ist   geschriebene Vergleichsoperationen (z. B. CAS) können bestimmen, ob   der Standort wurde seit dem letzten Zugriff der   gleichen Thread, wodurch das ABA-Problem verhindert wird.     Die Methode erfordert, dass das Tag genügend zu erstellende Bits enthält   Vollumbruch unmöglich während der Ausführung von   einzelner Lock-Free-Versuch. Diese Methode ist sehr effizient und   ermöglicht die sofortige Wiederverwendung von ausgefallenen Knoten.

Abhängig von Ihrer Datenstruktur könnten Sie in der Lage sein, einige zusätzliche Bits von den Zeigern zu stehlen. Wenn zum Beispiel die Objekte 64 Bytes lang sind und immer auf 64-Byte-Grenzen ausgerichtet sind, könnten die unteren 6 Bits jedes Zeigers für die Tags verwendet werden (aber das ist wahrscheinlich das, was Sie bereits für Ihren neuen Plan vorgeschlagen haben).

Eine andere Möglichkeit wäre, anstelle von Zeigern einen Index in Ihre Objekte zu verwenden.

Bei zusammenhängenden Objekten, die natürlich einfach ein Index in ein Array oder einen Vektor sein würden. Im Fall von Listen oder Bäumen mit Objekten, die auf dem Heap zugeordnet sind, könnten Sie einen benutzerdefinierten Zuordner verwenden und einen Index in den zugewiesenen Block (en) verwenden.

Für zB 17M-Objekte würden Sie nur 24 Bits benötigen und 40 Bits für die Tags lassen.

Dies würde einige (kleine und schnelle) zusätzliche Berechnung benötigen, um die Adresse zu erhalten, aber wenn die Ausrichtung eine Potenz von 2 ist, wird nur eine Verschiebung und eine Addition benötigt.