Een ringbuffer in Java implementeren

1. Overview

In deze tutorial leren we hoe we een Ring Buffer in Java kunnen implementeren.

Ring Buffer

Ring Buffer (of Circular Buffer) is een begrensde circulaire datastructuur die wordt gebruikt voor het bufferen van gegevens tussen twee of meer threads. Als we blijven schrijven naar een ring buffer, wraps around als het het einde bereikt.

2.1. Hoe het werkt

Een ringbuffer wordt geïmplementeerd met behulp van een array van vaste grootte die zich aan de grenzen omwikkelt.

Naast de array houdt hij drie dingen bij:

• het volgende beschikbare slot in de buffer om een element in te voegen,
• het volgende ongelezen element in de buffer,
• en het einde van de array – het punt waarop de buffer zich omwikkelt naar het begin van de array

De mechanica van hoe een ringbuffer met deze vereisten omgaat, varieert met de implementatie. Het Wikipedia-artikel over dit onderwerp toont bijvoorbeeld een methode die gebruikmaakt van vierpunters.

We lenen de aanpak van Disruptor’s implementatie van de ringbuffer met behulp van sequenties.

Het eerste wat we moeten weten is de capaciteit – de vaste maximale grootte van de buffer. Vervolgens gebruiken we twee monotoon oplopende sequenties:

• Schrijfsequentie: beginnend bij -1, oplopend met 1 als we een element invoegen
• leessequentie: beginnend bij 0, oplopend met 1 als we een element consumeren

We kunnen een sequentie toewijzen aan een index in de array door een mod-bewerking te gebruiken:

arrayIndex = sequence % capacity

De mod operatie wikkelt de sequentie rond de grenzen om een slot in de buffer af te leiden:

Laten we eens kijken hoe we een element zouden invoegen:

buffer = element

We preïncrementeren de sequentie alvorens een element in te voegen.

Om een element te consumeren, doen we een post-increment:

element = buffer

In dit geval voeren we een post-increment op de sequentie uit. Het consumeren van een element verwijdert het niet uit de buffer – het blijft gewoon in de array tot het wordt overschreven.

2.2.

2.2. Lege en volle buffers

Als we de array ronddraaien, beginnen we met het overschrijven van de gegevens in de buffer. Als de buffer vol is, kunnen we kiezen om ofwel de oudste gegevens te overschrijven, ongeacht of de lezer ze heeft verbruikt, of te voorkomen dat de gegevens die niet zijn gelezen, worden overschreven.

Als de lezer het zich kan veroorloven om de tussenliggende of oude waarden te missen (bijvoorbeeld een aandelenkoersticker), kunnen we de gegevens overschrijven zonder te wachten tot ze zijn verbruikt. Aan de andere kant, als de lezer moet consumeren alle waarden (zoals met e-commerce transacties), moeten we wachten (block/busy-wacht) totdat de buffer heeft een slot beschikbaar.

De buffer is vol als de grootte van de buffer gelijk is aan zijn capaciteit, waarbij de grootte gelijk is aan het aantal ongelezen elementen:

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

Als de schrijfvolgorde achterloopt op de leesvolgorde, is de buffer leeg:

isEmpty = writeSequence < readSequence

De buffer retourneert een null-waarde als hij leeg is.

2.2. Voordelen en nadelen

Een ringbuffer is een efficiënte FIFO-buffer. Hij maakt gebruik van een array van vaste grootte die vooraf kan worden toegewezen en een efficiënt toegangspatroon tot het geheugen mogelijk maakt. Alle bufferbewerkingen zijn constant in tijd O(1), inclusief het consumeren van een element, omdat het niet nodig is om elementen te verschuiven.

Aan de andere kant is het bepalen van de juiste grootte van de ringbuffer van cruciaal belang. De schrijfoperaties kunnen bijvoorbeeld lang blokkeren als de buffer te klein is en de leesoperaties langzaam zijn. We kunnen dynamische sizing gebruiken, maar dan moeten we data verplaatsen en missen we de meeste voordelen die hierboven zijn besproken.

Implementatie in Java

Nu we begrijpen hoe een ring buffer werkt, gaan we verder met het implementeren ervan in Java.

3.1. Initialisatie

Laten we eerst een constructor definiëren die de buffer initialiseert met een voorgedefinieerde capaciteit:

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

Dit zal een lege buffer creëren en de sequentievelden initialiseren zoals besproken in de vorige sectie.

3.2. Offer

Naar aanleiding hiervan zullen we de offer operatie implementeren die een element in de buffer plaatst op het eerstvolgende beschikbare slot en true teruggeeft bij succes. Het retourneert false als de buffer geen leeg slot kan vinden, dat wil zeggen, we kunnen geen ongelezen waarden overschrijven.

Laten we de aanbiedingsmethode in Java implementeren:

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

Dus, we verhogen de schrijfvolgorde en berekenen de index in de array voor het volgende beschikbare slot. Dan schrijven we de gegevens naar de buffer en slaan de bijgewerkte schrijfvolgorde op.

Laten we het eens uitproberen:

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

3.3. Poll

Ten slotte zullen we de poll operatie implementeren die het volgende ongelezen element ophaalt en verwijdert. De poll operatie verwijdert het element niet, maar verhoogt de leesvolgorde.

Laten we het implementeren:

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

Hier lezen we de gegevens op de huidige leesvolgorde door de index in de array te berekenen. Vervolgens verhogen we de reeks en retourneren de waarde, als de buffer niet leeg is.

Laten we het uittesten:

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

Producer-Consumer Probleem

We hebben het gehad over het gebruik van een ringbuffer voor het uitwisselen van gegevens tussen twee of meer threads, wat een voorbeeld is van een synchronisatieprobleem dat het Producer-Consumer probleem wordt genoemd. In Java kunnen we het producer-consumer probleem op verschillende manieren oplossen met behulp van semaforen, begrensde wachtrijen, ringbuffers, enzovoort.

Laten we een oplossing implementeren die is gebaseerd op een ringbuffer.

4.1. volatile Sequence Fields

Onze implementatie van de ringbuffer is niet thread-safe. Laten we hem thread-safe maken voor het eenvoudige geval van een enkele producent en een enkele consument.

De producent schrijft gegevens naar de buffer en verhoogt de writeSequence, terwijl de consument alleen uit de buffer leest en de readSequence verhoogt. Dus, de backing array is contention-vrij en we kunnen wegkomen zonder enige synchronisatie.

Maar we moeten nog steeds ervoor zorgen dat de consument de laatste waarde van het writeSequence-veld kan zien (zichtbaarheid) en dat de writeSequence niet wordt bijgewerkt voordat de gegevens daadwerkelijk beschikbaar zijn in de buffer (ordening).

We kunnen de ringbuffer in dit geval concurrent- en lockvrij maken door de sequence-velden vluchtig te maken:

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

In de aanbiedingsmethode garandeert een schrijven naar het vluchtige veld writeSequence dat het schrijven naar de buffer gebeurt voordat de sequence wordt bijgewerkt. Tegelijkertijd garandeert de vluchtige zichtbaarheidsgarantie dat de consument altijd de laatste waarde van writeSequence zal zien.

4.2. Producer

Laten we een eenvoudige producer Runnable implementeren die naar de ringbuffer schrijft:

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

De producer thread zou wachten op een leeg slot in een lus (busy-waiting).

4.3. Consumer

We zullen een consumer Callable implementeren die uit de buffer leest:

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;}

De consumer thread gaat door zonder af te drukken als hij een null-waarde uit de buffer ontvangt.

Laten we onze driver code schrijven:

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

Uitvoeren van ons producer-consumer programma levert output op zoals hieronder:

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

Conclusie

In deze tutorial hebben we geleerd hoe we een Ring Buffer kunnen implementeren en onderzocht hoe deze kan worden gebruikt om het producer-consumer probleem op te lossen.