Thread-sichere LIFO-Datenstrukturimplementierungen

1. Einleitung

In diesem Tutorial werden verschiedene Optionen für threadsichere LIFO-Datenstrukturimplementierungen erläutert .

In der LIFO-Datenstruktur werden Elemente nach dem Last-In-First-Out-Prinzip eingefügt und abgerufen. Dies bedeutet, dass das zuletzt eingefügte Element zuerst abgerufen wird.

In der Informatik ist Stapel der Begriff, der verwendet wird, um sich auf eine solche Datenstruktur zu beziehen.

Ein Stack ist praktisch, um einige interessante Probleme wie die Auswertung von Ausdrücken, das Implementieren von Rückgängig-Operationen usw. zu lösen. Da er in Umgebungen mit gleichzeitiger Ausführung verwendet werden kann, müssen wir ihn möglicherweise threadsicher machen.

2. Stapel verstehen

Grundsätzlich muss ein Stack die folgenden Methoden implementieren:

  1. push () - füge oben ein Element hinzu
  2. pop () - holt das oberste Element und entfernt es
  3. peek () - holt das Element, ohne es aus dem darunter liegenden Container zu entfernen

Nehmen wir an, wir möchten eine Befehlsverarbeitungs-Engine.

In diesem System ist das Rückgängigmachen ausgeführter Befehle ein wichtiges Merkmal.

Im Allgemeinen werden alle Befehle auf den Stapel verschoben, und die Rückgängig-Operation kann einfach implementiert werden:

  • pop () -Methode, um den zuletzt ausgeführten Befehl abzurufen
  • Rufen Sie die Methode undo () für das Befehlsobjekt popped auf

3. Grundlegendes zur Gewindesicherheit in Stapeln

Wenn eine Datenstruktur bei gleichzeitigem Zugriff nicht threadsicher ist, kann dies zu Race-Bedingungen führen .

Kurz gesagt, Race-Bedingungen treten auf, wenn die korrekte Ausführung von Code vom Timing und der Reihenfolge der Threads abhängt. Dies geschieht hauptsächlich, wenn mehr als ein Thread die Datenstruktur gemeinsam nutzt und diese Struktur nicht für diesen Zweck ausgelegt ist.

Lassen Sie uns eine der folgenden Methoden aus einer Java Collection-Klasse, ArrayDeque , untersuchen :

public E pollFirst() { int h = head; E result = (E) elements[h]; // ... other book-keeping operations removed, for simplicity head = (h + 1) & (elements.length - 1); return result; }

Um die mögliche Racebedingung im obigen Code zu erklären, nehmen wir zwei Threads an, die diesen Code ausführen, wie in der folgenden Sequenz angegeben:

  • Der erste Thread führt die dritte Zeile aus: Setzt das Ergebnisobjekt mit dem Element am Index 'head'.
  • Der zweite Thread führt die dritte Zeile aus: Setzt das Ergebnisobjekt mit dem Element am Index 'head'.
  • Der erste Thread führt die fünfte Zeile aus: Setzt den Index 'head' auf das nächste Element im Hintergrundarray zurück
  • Der zweite Thread führt die fünfte Zeile aus: Setzt den Index 'head' auf das nächste Element im Hintergrundarray zurück

Hoppla! Jetzt würden beide Ausführungen dasselbe Ergebnisobjekt zurückgeben .

Um solche Race-Bedingungen zu vermeiden, sollte in diesem Fall ein Thread die erste Zeile erst ausführen, wenn der andere Thread das Zurücksetzen des 'head'-Index in der fünften Zeile abgeschlossen hat. Mit anderen Worten, der Zugriff auf das Element am Index 'head' und das Zurücksetzen des Index 'head' sollten für einen Thread atomar erfolgen.

In diesem Fall hängt die korrekte Ausführung von Code natürlich vom Timing der Threads ab und ist daher nicht threadsicher.

4. Gewindesichere Stapel mit Schlössern

In diesem Abschnitt werden zwei mögliche Optionen für konkrete Implementierungen eines thread-sicheren Stapels erläutert.

Insbesondere werden wir den Java- Stack und eine thread-sicher dekorierte ArrayDeque behandeln.

Beide verwenden Sperren für den sich gegenseitig ausschließenden Zugriff .

4.1. Verwenden des Java- Stacks

Java Collections verfügt über eine Legacy-Implementierung für thread-safe Stack , die auf Vector basiert, einer synchronisierten Variante von ArrayList.

Das offizielle Dokument selbst schlägt jedoch vor, die Verwendung von ArrayDeque in Betracht zu ziehen . Daher werden wir nicht zu sehr ins Detail gehen.

Obwohl der Java- Stack threadsicher und unkompliziert zu verwenden ist, weist diese Klasse große Nachteile auf:

  • Das Einstellen der Anfangskapazität wird nicht unterstützt
  • Es verwendet Sperren für alle Operationen. Dies kann die Leistung bei Single-Threaded-Ausführungen beeinträchtigen.

4.2. Verwenden von ArrayDeque

Die Verwendung der Deque- Schnittstelle ist der bequemste Ansatz für LIFO-Datenstrukturen, da alle erforderlichen Stapeloperationen bereitgestellt werden. ArrayDeque ist eine solche konkrete Implementierung .

Da für die Vorgänge keine Sperren verwendet werden, funktionieren Single-Threaded-Ausführungen einwandfrei. Bei Multithread-Ausführungen ist dies jedoch problematisch.

Wir können jedoch einen Synchronisationsdekorator für ArrayDeque implementieren. Obwohl dies ähnlich wie die Stack- Klasse von Java Collection Framework funktioniert , ist das wichtige Problem der Stack- Klasse, das Fehlen einer anfänglichen Kapazitätseinstellung, gelöst.

Werfen wir einen Blick auf diese Klasse:

public class DequeBasedSynchronizedStack { // Internal Deque which gets decorated for synchronization. private ArrayDeque dequeStore; public DequeBasedSynchronizedStack(int initialCapacity) { this.dequeStore = new ArrayDeque(initialCapacity); } public DequeBasedSynchronizedStack() { dequeStore = new ArrayDeque(); } public synchronized T pop() { return this.dequeStore.pop(); } public synchronized void push(T element) { this.dequeStore.push(element); } public synchronized T peek() { return this.dequeStore.peek(); } public synchronized int size() { return this.dequeStore.size(); } }

Beachten Sie, dass unsere Lösung Deque selbst der Einfachheit halber nicht implementiert , da sie viel mehr Methoden enthält.

Außerdem enthält Guava SynchronizedDeque , eine produktionsbereite Implementierung einer dekorierten ArrayDequeue.

5. Lock-free Thread-sichere Stapel

ConcurrentLinkedDeque is a lock-free implementation of Deque interface. This implementation is completely thread-safe as it uses an efficient lock-free algorithm.

Lock-free implementations are immune to the following issues, unlike lock based ones.

  • Priority inversion – This occurs when the low-priority thread holds the lock needed by a high priority thread. This might cause the high-priority thread to block
  • Deadlocks – This occurs when different threads lock the same set of resources in a different order.

On top of that, Lock-free implementations have some features which make them perfect to use in both single and multi-threaded environments.

  • Für nicht gemeinsam genutzte Datenstrukturen und für Single-Threaded-Zugriff wäre die Leistung mit ArrayDeque vergleichbar
  • Bei gemeinsam genutzten Datenstrukturen hängt die Leistung von der Anzahl der Threads ab, die gleichzeitig darauf zugreifen .

In Bezug auf die Benutzerfreundlichkeit unterscheidet es sich nicht von ArrayDeque, da beide die Deque- Schnittstelle implementieren .

6. Fazit

In diesem Artikel haben wir die Stack- Datenstruktur und ihre Vorteile beim Entwerfen von Systemen wie Command Processing Engine und Expression Evaluators erläutert.

Außerdem haben wir verschiedene Stack-Implementierungen im Java-Sammlungsframework analysiert und deren Leistung und Thread-Sicherheitsnuancen diskutiert.

Codebeispiele finden Sie wie gewohnt auf GitHub.