Implementieren eines Ringpuffers in Java

1. Überblick

In diesem Tutorial lernen wir, wie man einen Ring Buffer in Java implementiert.

Ring Buffer

Ring Buffer (oder Circular Buffer) ist eine begrenzte zirkuläre Datenstruktur, die zum Puffern von Daten zwischen zwei oder mehr Threads verwendet wird. Wenn wir weiter in einen Ringpuffer schreiben, wird er umlaufen, wenn er das Ende erreicht.

2.1. Funktionsweise

Ein Ringpuffer wird mit Hilfe eines Arrays fester Größe implementiert, das an den Grenzen umbrochen wird.

Abgesehen von dem Array werden drei Dinge überwacht:

• den nächsten verfügbaren Slot im Puffer, um ein Element einzufügen,
• das nächste ungelesene Element im Puffer,
• und das Ende des Arrays – der Punkt, an dem der Puffer zum Anfang des Arrays umschlägt

Die Mechanik, wie ein Ringpuffer diese Anforderungen handhabt, variiert je nach Implementierung. Der Wikipedia-Eintrag zu diesem Thema zeigt zum Beispiel eine Methode, die vier Zeiger verwendet.

Wir werden den Ansatz von Disruptors Implementierung des Ringpuffers unter Verwendung von Sequenzen übernehmen.

Das erste, was wir wissen müssen, ist die Kapazität – die feste maximale Größe des Puffers. Als nächstes verwenden wir zwei monoton steigende Sequenzen:

• Schreibsequenz: beginnt bei -1, erhöht sich um 1, wenn wir ein Element einfügen
• Lesesequenz: beginnt bei 0, erhöht sich um 1, wenn wir ein Element verbrauchen

Wir können eine Sequenz auf einen Index im Array abbilden, indem wir eine Mod-Operation verwenden:

arrayIndex = sequence % capacity

Die Mod-Operation wickelt die Sequenz um die Grenzen, um einen Slot im Puffer abzuleiten:

Lassen Sie uns sehen, wie wir ein Element einfügen:

buffer = element

Wir erhöhen die Sequenz vor dem Einfügen eines Elements.

Um ein Element zu konsumieren, führen wir eine Post-Inkrementierung durch:

element = buffer

In diesem Fall führen wir eine Post-Inkrementierung der Sequenz durch. Das Verbrauchen eines Elements entfernt es nicht aus dem Puffer – es bleibt einfach im Array, bis es überschrieben wird.

2.2. Leere und volle Puffer

Wenn wir um das Array herumgehen, beginnen wir, die Daten im Puffer zu überschreiben. Wenn der Puffer voll ist, können wir entweder die ältesten Daten überschreiben, unabhängig davon, ob der Leser sie verbraucht hat, oder das Überschreiben der nicht gelesenen Daten verhindern.

Wenn der Leser es sich leisten kann, die Zwischenwerte oder die alten Werte zu verpassen (z.B. bei einem Börsenticker), können wir die Daten überschreiben, ohne darauf zu warten, dass sie verbraucht werden. Wenn der Leser jedoch alle Werte verbrauchen muss (wie bei E-Commerce-Transaktionen), sollten wir warten (blockieren/busy-wait), bis der Puffer einen freien Platz hat.

Der Puffer ist voll, wenn die Größe des Puffers gleich seiner Kapazität ist, wobei seine Größe gleich der Anzahl der ungelesenen Elemente ist:

size = (writeSequence - readSequence) + 1isFull = (size == capacity)

Wenn die Schreibsequenz hinter der Lesesequenz zurückbleibt, ist der Puffer leer:

isEmpty = writeSequence < readSequence

Der Puffer gibt einen Nullwert zurück, wenn er leer ist.

2.2. Vorteile und Nachteile

Ein Ringpuffer ist ein effizienter FIFO-Puffer. Er verwendet ein Array fester Größe, das im Voraus zugewiesen werden kann und ein effizientes Speicherzugriffsmuster ermöglicht. Alle Pufferoperationen haben die konstante Zeit O(1), einschließlich des Verbrauchs eines Elements, da keine Verschiebung von Elementen erforderlich ist.

Auf der anderen Seite ist die Bestimmung der richtigen Größe des Ringpuffers entscheidend. Beispielsweise können die Schreibvorgänge lange Zeit blockieren, wenn der Puffer zu klein ist und die Lesevorgänge langsam sind. Wir können dynamische Größenbestimmung verwenden, aber das würde das Verschieben von Daten erfordern und wir würden die meisten der oben beschriebenen Vorteile verpassen.

Implementierung in Java

Nun, da wir verstehen, wie ein Ringpuffer funktioniert, lassen Sie uns fortfahren, ihn in Java zu implementieren.

3.1. Initialisierung

Zunächst definieren wir einen Konstruktor, der den Puffer mit einer vordefinierten Kapazität initialisiert:

public CircularBuffer(int capacity) { this.capacity = (capacity < 1) ? DEFAULT_CAPACITY : capacity; this.data = (E) new Object; this.readSequence = 0; this.writeSequence = -1;}

Dies erzeugt einen leeren Puffer und initialisiert die Sequenzfelder, wie im vorherigen Abschnitt beschrieben.

3.2. Angebot

Als nächstes implementieren wir die Operation Angebot, die ein Element in den Puffer an der nächsten freien Stelle einfügt und bei Erfolg true zurückgibt. Sie gibt false zurück, wenn der Puffer keinen leeren Slot finden kann, d.h. wir können ungelesene Werte nicht überschreiben.

Lassen Sie uns die offer-Methode in Java implementieren:

public boolean offer(E element) { boolean isFull = (writeSequence - readSequence) + 1 == capacity; if (!isFull) { int nextWriteSeq = writeSequence + 1; data = element; writeSequence++; return true; } return false;}

So, wir erhöhen die Schreibsequenz und berechnen den Index im Array für den nächsten verfügbaren Slot. Dann schreiben wir die Daten in den Puffer und speichern die aktualisierte Schreibsequenz.

Lassen Sie es uns ausprobieren:

@Testpublic void givenCircularBuffer_whenAnElementIsEnqueued_thenSizeIsOne() { CircularBuffer buffer = new CircularBuffer<>(defaultCapacity); assertTrue(buffer.offer("Square")); assertEquals(1, buffer.size());}

3.3. Poll

Schließlich werden wir die Poll-Operation implementieren, die das nächste ungelesene Element abruft und entfernt. Die Poll-Operation entfernt das Element nicht, sondern erhöht die Lesereihenfolge.

Lassen Sie uns das implementieren:

public E poll() { boolean isEmpty = writeSequence < readSequence; if (!isEmpty) { E nextValue = data; readSequence++; return nextValue; } return null;}

Hier lesen wir die Daten in der aktuellen Lesereihenfolge, indem wir den Index im Array berechnen. Dann inkrementieren wir die Sequenz und geben den Wert zurück, wenn der Puffer nicht leer ist.

Lassen Sie es uns ausprobieren:

@Testpublic void givenCircularBuffer_whenAnElementIsDequeued_thenElementMatchesEnqueuedElement() { CircularBuffer buffer = new CircularBuffer<>(defaultCapacity); buffer.offer("Triangle"); String shape = buffer.poll(); assertEquals("Triangle", shape);}

Producer-Consumer Problem

Wir haben über die Verwendung eines Ringpuffers für den Austausch von Daten zwischen zwei oder mehr Threads gesprochen, was ein Beispiel für ein Synchronisationsproblem ist, das Producer-Consumer Problem genannt wird. In Java können wir das Producer-Consumer-Problem auf verschiedene Weise lösen, indem wir Semaphoren, begrenzte Warteschlangen, Ringpuffer usw. verwenden.

Lassen Sie uns eine Lösung implementieren, die auf einem Ringpuffer basiert.

4.1. flüchtige Sequenzfelder

Unsere Implementierung des Ringpuffers ist nicht thread-sicher. Machen wir sie für den einfachen Fall eines einzelnen Erzeugers und eines einzelnen Verbrauchers thread-sicher.

Der Erzeuger schreibt Daten in den Puffer und erhöht die writeSequence, während der Verbraucher nur aus dem Puffer liest und die readSequence inkrementiert. Das Backing Array ist also konkurrenzfrei und wir kommen ohne Synchronisation aus.

Aber wir müssen immer noch sicherstellen, dass der Konsument den neuesten Wert des writeSequence-Feldes sehen kann (Sichtbarkeit) und dass die writeSequence nicht aktualisiert wird, bevor die Daten tatsächlich im Puffer verfügbar sind (Ordnung).

Wir können den Ringpuffer in diesem Fall konkurrierend und sperrfrei machen, indem wir die Sequenzfelder flüchtig machen:

private volatile int writeSequence = -1, readSequence = 0;

In der Angebotsmethode garantiert ein Schreiben in das flüchtige Feld writeSequence, dass die Schreibvorgänge in den Puffer vor der Aktualisierung der Sequenz erfolgen. Gleichzeitig stellt die flüchtige Sichtbarkeitsgarantie sicher, dass der Verbraucher immer den neuesten Wert von writeSequence sieht.

4.2. Producer

Lassen Sie uns einen einfachen Producer Runnable implementieren, der in den Ringpuffer schreibt:

public void run() { for (int i = 0; i < items.length;) { if (buffer.offer(items)) { System.out.println("Produced: " + items); i++; } }}

Der Producer-Thread würde in einer Schleife auf einen leeren Slot warten (busy-waiting).

4.3. Consumer

Wir werden einen Consumer Callable implementieren, der aus dem Puffer liest:

public T call() { T items = (T) new Object; for (int i = 0; i < items.length;) { T item = buffer.poll(); if (item != null) { items = item; System.out.println("Consumed: " + item); } } return items;}

Der Consumer-Thread fährt fort, ohne zu drucken, wenn er einen Nullwert aus dem Puffer erhält.

Schreiben wir unseren Treibercode:

executorService.submit(new Thread(new Producer<String>(buffer)));executorService.submit(new Thread(new Consumer<String>(buffer)));

Die Ausführung unseres Producer-Consumer-Programms erzeugt eine Ausgabe wie die folgende:

Produced: CircleProduced: Triangle Consumed: CircleProduced: Rectangle Consumed: Triangle Consumed: RectangleProduced: SquareProduced: Rhombus Consumed: SquareProduced: Trapezoid Consumed: Rhombus Consumed: TrapezoidProduced: PentagonProduced: PentagramProduced: Hexagon Consumed: Pentagon Consumed: PentagramProduced: Hexagram Consumed: Hexagon Consumed: Hexagram

Abschluss

In diesem Tutorial haben wir gelernt, wie man einen Ringpuffer implementiert und wie man ihn zur Lösung des Producer-Consumer-Problems verwenden kann.