Implementering af en ringbuffer i Java

1. Oversigt

I denne vejledning lærer vi at implementere en ringbuffer i Java.

Ringbuffer

Ringbuffer (eller cirkulær buffer) er en afgrænset cirkulær datastruktur, der bruges til at puffere data mellem to eller flere tråde. Når vi bliver ved med at skrive til en ringbuffer, bliver den viklet rundt, når den når slutningen.

2.1. Sådan fungerer det

En ringbuffer er implementeret ved hjælp af et array af fast størrelse, der vikler sig rundt ved grænserne.

Afhængigt af arrayet holder den styr på tre ting:

• den næste ledige plads i bufferen til at indsætte et element,
• det næste ulæste element i bufferen,
• og arrayets ende – det punkt, hvor bufferen vikler sig rundt til arrayets start

Mekanikken i, hvordan en ringbuffer håndterer disse krav, varierer med implementeringen. Wikipedia-indlægget om emnet viser f.eks. en metode, der anvender four-pointers.

Vi låner fremgangsmåden fra Disruptors implementering af ringbufferen ved hjælp af sekvenser.

Den første ting, vi skal kende, er kapaciteten – den faste maksimale størrelse af bufferen. Dernæst bruger vi to monotont stigende sekvenser:

• Skriv sekvens: starter ved -1, øges med 1, når vi indsætter et element
• Læs sekvens: starter ved 0, øges med 1, når vi forbruger et element

Vi kan mappe en sekvens til et indeks i arrayet ved at bruge en mod-operation:

arrayIndex = sequence % capacity

Mod-operationen vikler sekvensen rundt om grænserne for at udlede et slot i bufferen:

Lad os se, hvordan vi indsætter et element:

buffer = element

Vi forhåndsinkrementerer sekvensen, før vi indsætter et element.

For at forbruge et element foretager vi en post-inkrementering:

element = buffer

I dette tilfælde udfører vi en post-inkrementering på sekvensen. Når vi forbruger et element, fjernes det ikke fra bufferen – det forbliver bare i arrayet, indtil det bliver overskrevet.

2.2. Tomme og fyldte buffere

Når vi vikler rundt i arrayet, begynder vi at overskrive dataene i bufferen. Hvis bufferen er fuld, kan vi vælge enten at overskrive de ældste data, uanset om læseren har forbrugt dem, eller at forhindre overskrivning af de data, der ikke er blevet læst.

Hvis læseren kan tillade sig at gå glip af de mellemliggende eller gamle værdier (f.eks. en aktiekursticker), kan vi overskrive dataene uden at vente på, at de er blevet forbrugt. Hvis læseren derimod skal forbruge alle værdierne (f.eks. ved e-handelstransaktioner), bør vi vente (block/busy-wait), indtil bufferen har et ledigt slot til rådighed i bufferen.

Bufferen er fuld, hvis bufferens størrelse er lig med dens kapacitet, hvor dens størrelse er lig med antallet af ulæste elementer:

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

Hvis skrive-sekvensen halter efter læse-sekvensen, er bufferen tom:

isEmpty = writeSequence < readSequence

Bufferen returnerer en nul-værdi, hvis den er tom.

2.2. Fordele og ulemper

En ringbuffer er en effektiv FIFO-buffer. Den anvender et array af fast størrelse, der kan allokeres på forhånd og giver mulighed for et effektivt hukommelsesadgangsmønster. Alle bufferoperationer er konstant tid O(1), herunder forbruget af et element, da det ikke kræver en forskydning af elementer.

På bagsiden er det kritisk at bestemme den korrekte størrelse af ringbufferen. F.eks. kan skriveoperationerne blokere i lang tid, hvis bufferen er underdimensioneret, og læsningerne er langsomme. Vi kan bruge dynamisk dimensionering, men det ville kræve, at data flyttes rundt, og vi vil gå glip af de fleste af de fordele, der er diskuteret ovenfor.

Implementering i Java

Nu da vi forstår, hvordan en ringbuffer fungerer, skal vi gå videre med at implementere den i Java.

3.1. Initialisering

Først skal vi definere en konstruktør, der initialiserer bufferen med en foruddefineret kapacitet:

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

Dette vil skabe en tom buffer og initialisere sekvensfelterne som diskuteret i det foregående afsnit.

3.2. Offer

Næste gang implementerer vi offer-operationen, der indsætter et element i bufferen på det næste tilgængelige slot og returnerer true ved succes. Den returnerer false, hvis bufferen ikke kan finde et tomt slot, dvs. vi kan ikke overskrive ulæste værdier.

Lad os implementere offer-metoden i Java:

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

Så vi øger skrivesekvensen og beregner indekset i arrayet for det næste ledige slot. Derefter skriver vi dataene til bufferen og gemmer den opdaterede skrivesekvens.

Lad os prøve det af:

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

3.3. Poll

Slutteligt skal vi implementere poll-operationen, der henter og fjerner det næste ulæste element. Poll-operationen fjerner ikke elementet, men øger den læste sekvens.

Lad os implementere den:

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

Her læser vi dataene på den aktuelle læste sekvens ved at beregne indekset i arrayet. Derefter øger vi sekvensen og returnerer værdien, hvis bufferen ikke er tom.

Lad os afprøve det:

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

Producer-Consumer-problem

Vi har talt om brugen af en ringbuffer til at udveksle data mellem to eller flere tråde, hvilket er et eksempel på et synkroniseringsproblem kaldet Producer-Consumer-problemet. I Java kan vi løse producent-forbruger-problemet på forskellige måder ved hjælp af semaforer, bounded queues, ringbuffere osv.

Lad os implementere en løsning baseret på en ringbuffer.

4.1. Volatile Sequence Fields

Vores implementering af ringbufferen er ikke trådsikker. Lad os gøre den trådsikker i det enkle tilfælde med en enkelt producent og en enkelt forbruger.

Producenten skriver data til bufferen og øger writeSequence, mens forbrugeren kun læser fra bufferen og øger readSequence. Så backing arrayet er contention-fri, og vi kan slippe af sted uden synkronisering.

Men vi skal stadig sikre, at forbrugeren kan se den seneste værdi af writeSequence-feltet (synlighed), og at writeSequence ikke opdateres, før dataene rent faktisk er tilgængelige i bufferen (ordnering).

Vi kan gøre ringbufferen samtidig og låsefri i dette tilfælde ved at gøre sekvensfelterne flygtige:

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

I offer-metoden garanterer en skrivning til det flygtige felt writeSequence, at skrivningerne til bufferen sker før opdatering af sekvensen. Samtidig sikrer den flygtige synlighedsgaranti, at forbrugeren altid vil se den seneste værdi af writeSequence.

4.2. Producer

Lad os implementere en simpel producer Runnable, der skriver til ringbufferen:

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

Producertråden ville vente på et tomt slot i en løkke (busy-waiting).

4.3. Forbruger

Vi vil implementere en forbruger Callable, der læser fra bufferen:

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

Forbrugertråden fortsætter uden at udskrive, hvis den modtager en nulværdi fra bufferen.

Lad os skrive vores driverkode:

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

Afvikling af vores producent-forbruger-program giver output som nedenfor:

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

Slutning

I denne tutorial har vi lært at implementere en ringbuffer og udforsket, hvordan den kan bruges til at løse producent-forbruger-problemet.