Zum Hauptinhalt springen

Leichte Epoch-Schutz in Garnet (Latch-freies Lazy-Synchronisation)

Kontext​

Wir müssen sicherstellen, dass gemeinsam genutzte Variablen nicht gleichzeitig ohne deterministische Reihenfolgen gelesen und mutiert werden. Häufig verwendete Konkurrenzprimitive wie Mutexe und Semaphoren, die von der Sprache bereitgestellt werden, erfordern, dass Threads häufig miteinander synchronisieren. Diese Synchronisation zwischen Threads ist teuer; Epoch Protection reduziert die Häufigkeit der Synchronisation zwischen Threads.

Epoch Protection (10.000-Fuß-Ansicht)​

  • LightEpoch bietet einen Synchronisationsmechanismus, bei dem der Schreibpfad den Thread nicht blockieren muss, sondern als Callback-Aktion Aufgabe enqueued werden kann. Der Schreibpfad wird an die Instanz von LightEpoch übergeben, um sicherzustellen, dass der Schreibvorgang nicht ausgeführt wird, wenn ein anderer Thread die Epoche "erworben" hat oder den Zustand zu einem bestimmten Zeitpunkt liest.

  • Als Benutzer können Sie Epoch Protection verwenden, um den neuesten Zustand gemeinsam genutzter Variablen vertrauensvoll anzuzeigen, ohne sich Gedanken über Änderungen ihres Zustands machen zu müssen. Das gesamte Epoche-System fährt mit der Aktualisierung des Zustands fort, nur wenn der Thread mit dem Anzeigen der Zustand-Version fertig ist.

  • LightEpoch wird verwendet, da es bestimmte Operationen nach anderen Threads ausführen kann, die den vorherigen Zustand gesehen haben und nicht mehr ausgeführt werden (das ist die Grundlage der Epochenkontrolle). Es ist nicht wirklich "gegenseitiger Ausschluss". Es ist eher so, als ob Adressgrenzen festgelegt und innerhalb dieser Grenzen so gearbeitet wird, dass kein Konflikt besteht. Ganz kurz: Threads "schützen" die aktuelle Epoche, indem sie sagen "Ich bin in dieser Epoche aktiv" (wobei "Epoche" ein Zähler ist). Wenn sie fertig sind, entfernen sie diesen Schutz. Wenn eine Operation, die gemeinsam genutzte Variablen ändern würde (wie 'HeadAddress'), ausgeführt werden soll, geschieht dies durch "Hochzählen" der Epoche, was den Zähler erhöht und dann wartet, bis kein anderer Thread mehr mit dem vorherigen geschützten Wert arbeitet. Variablen werden vor dem Hochzählen gesetzt, so dass jeder Thread, der den neuen Zählerwert sieht, auch die aktualisierten Variablen sieht (wiederum z.B. 'HeadAddress'), damit wir wissen, dass wir sicher bis zur aktuellen 'HeadAddress' arbeiten können, die hinter der vorherigen liegt.

Implementierungsdetails​

  • Es gibt ein systemweites LightEpoch-Threads-Array mit N Einträgen, wobei N = max(128, ProcessorCount * 2). Das bedeutet, dass eine gegebene LightEpoch bis zu 128 Threads unterstützen kann. Im Code werden Sie feststellen, dass wir zwar die Tabelle für die Variable tableRaw zuweisen und setzen, aber alle Interaktionen mit der Epoch Table über tableAligned erfolgen. Diese Optimierung dient der Cache-Zeilengröße auf modernen Prozessoren und L1-L3-Caches (64-Byte Cache-Zeilengröße). Wenn ein Thread Teil des Epoch Protection-Systems wird, fügen wir ihn zur Epoch Table hinzu und speichern eine Thread-lokale Epoche für diesen Thread in der Epoch Table. Zu Beginn der Aufnahme in die Epoch Table wird die Thread-lokale Epoche auf die aktuelle globale Epoche gesetzt.

  • Jedes Mal, wenn wir eine Epoche "erwerben", beansprucht ein Thread die Eigentümerschaft über einen Epochenzähler. Alle neu eintreffenden Threads übernehmen die Epochen erst nach diesem.

  • Jeder Thread, der Zugriff auf das LightEpoch-Objekt hat, kann die globale Epoche erhöhen (global für den Geltungsbereich der Instanz der LightEpoch-Klasse, gemeinsam für Threads).

  • Wir können Trigger-Aktionen hinzufügen, die ausgeführt werden, wenn alle Threads eine sichere Epoche überschritten haben (Für jeden Thread T: SafeEpoch <= Thread-lokale Epoche <= Globale Epoche). Da das System alle Thread-lokalen Epochen in einer systemzugänglichen Epochentabelle speichert, können wir eine sichere Epoche scannen und finden. Dies gibt uns die Möglichkeit, eine genau einmal ausgeführte Funktion zu haben, die darauf angewiesen ist, dass alle Threads logisch koordinieren und keine Codes ausgeführt werden, während die Epoche für den Trigger endet.

  • Wenn Sie genau hinschauen, macht epoch.Resume() im Wesentlichen Folgendes: Ein Thread findet einen freien Eintrag in der Epochentabelle, legt seine ID dort ab und " beansprucht " die aktuelle Epoche (der nächste Thread erhöht die Epoche um 1 und beansprucht die nächste Epoche). Innerhalb von epoch.Resume() gibt es eine Schleife; wenn der aktuelle Ziel-Epoche-Eintrag bereits von einem anderen Thread belegt ist, gibt der aktuelle Thread nach. Wenn er aufwacht, versucht er, den nächsten Eintrag zu belegen. Wenn die Epochentabelle voll ist, werden die restlichen Threads weiterhin nachgeben.

Relevante öffentliche Methoden und wie man sie benutzt​

  1. ThisInstanceProtected: Gibt an, ob der aufrufende Thread einen Eintrag in der Epochentabelle besitzt, d.h. derzeit an der Epoch Protection teilnimmt. Wenn nicht, kann er an der Epoch Protection teilnehmen, indem er Resume aufruft.

  2. ProtectAndDrain: Markiert den aktuellen Thread als Besitzer einer aktualisierten Epoche und führt das Entleeren von Aktionen bis zu diesem Zeitpunkt durch. Dies wird intern von Resume verwendet. Es dient als Möglichkeit, die gemeinsam genutzten Variablen durch das Entleeren ausstehender Aktionen zu aktualisieren. Oft innerhalb von Schleifen verwendet, um sicherzustellen, dass wir Aktionen progressiv entleeren.

  3. Suspend: Verwenden Sie dies, um den Besitz einer Epoche aufzugeben. Wenn der Thread, der Suspend aufruft, der letzte aktive Thread im LightEpoch-System ist, werden die ausstehenden Aktionen/Schreibvorgänge aufgerufen.

  4. Resume: Verwenden Sie dies, wenn ein Thread einen aktualisierten Zustand der gemeinsam genutzten Variablen anzeigen muss, bis zum neuesten Zustand, der von allen anderen Threads als sicher angesehen wird. Es dient als temporäre Grenze, um ausstehende Aktionen/Schreibvorgänge anzuwenden, bevor die gemeinsam genutzten Variablen verwendet werden.

  5. BumpCurrentEpoch(Action): Verwenden Sie dies, um einen Schreibvorgang oder eine Aktion für später zu einem Zeitpunkt zu planen, an dem es sicher ist, den Zustand einer gemeinsam genutzten Variablen zu ändern. Ein Aufruf hiervon kann Aktionen entleeren, wenn er während der Iterationen Werte findet, die er entleeren kann.