Implementering af en ringbuffer i Java

1. Oversigt

I denne vejledning lærer vi, hvordan du implementerer en ringbuffer i Java.

2. Ringbuffer

Ringbuffer (eller cirkulærbuffer) er en afgrænset cirkulær datastruktur, der bruges til buffering af data mellem to eller flere tråde. Når vi fortsætter med at skrive til en ringbuffer, vikles den rundt, når den når slutningen.

2.1. Hvordan det virker

En ringbuffer implementeres ved hjælp af et array i fast størrelse, der ombrydes ved grænserne.

Bortset fra arrayet holder det styr på tre ting:

  • den næste ledige plads i bufferen for at indsætte et element,
  • det næste ulæste element i bufferen,
  • og slutningen af ​​arrayet - det punkt, hvor bufferen vikles rundt til starten af ​​arrayet

Mekanikken for, hvordan en ringbuffer håndterer disse krav, varierer med implementeringen. For eksempel viser Wikipedia-posten om emnet en metode, der bruger fire-pegepinde.

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

Den første ting, vi skal vide, er kapaciteten - den faste maksimale størrelse af bufferen. Næste, vi bruger to monotontiltagendesekvenser:

  • Skriv sekvens: starter ved -1, trin på 1, når vi indsætter et element
  • Læs sekvens: starter ved 0, trin med 1, når vi spiser et element

Vi kan kortlægge en sekvens til et indeks i arrayet ved hjælp af en mod-operation:

arrayIndex = sekvens% kapacitet 

Det mod-operation vikler sekvensen rundt om grænserne for at udlede en plads i bufferen:

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

buffer [++ writeSequence% capacity] = element 

Vi forudvælger sekvensen før vi indsætter et element.

For at forbruge et element foretager vi en efter-stigning:

element = buffer [readSequence ++% kapacitet] 

I dette tilfælde udfører vi en forøgelse af sekvensen. Forbrugende et element fjerner det ikke fra bufferen - det forbliver bare i arrayet, indtil det overskrives.

2.2. Tomme og fulde buffere

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

Hvis læseren har råd til at gå glip af de mellemliggende eller gamle værdier (for eksempel en aktiekurs ticker), kan vi overskrive dataene uden at vente på, at de forbruges. På den anden side, hvis læseren skal forbruge alle værdierne (som med e-handelstransaktioner), skal vi vente (blokere / optage-vente), indtil bufferen har en plads tilgængelig.

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

størrelse = (writeSequence - readSequence) + 1 isFull = (størrelse == kapacitet) 

Hvis skrivesekvensen hænger bag læsningssekvensen, er bufferen tom:

isEmpty = writeSequence <readSequence 

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

2.2. Fordele og ulemper

En ringbuffer er en effektiv FIFO-buffer. Det bruger et array i fast størrelse, der kan forhåndsallokeres på forhånd og giver et effektivt hukommelsesadgangsmønster. Alle bufferoperationer er konstant tid O (1), inklusive forbrug af et element, da det ikke kræver en forskydning af elementer.

På bagsiden er det afgørende at bestemme den korrekte størrelse af ringbufferen. For eksempel kan skriveoperationerne blokere i lang tid, hvis bufferen er for lille og læsningerne er langsomme. Vi kan bruge dynamisk dimensionering, men det kræver flytning af data, og vi går glip af de fleste af de fordele, der er diskuteret ovenfor.

3. Implementering i Java

Nu hvor vi forstår, hvordan en ringbuffer fungerer, lad os fortsætte med at implementere den i Java.

3.1. Initialisering

Lad os først definere en konstruktør, der initialiserer bufferen med en foruddefineret kapacitet:

offentlig CircularBuffer (int-kapacitet) {this.capacity = capacity; denne.data = (E []) nyt objekt [kapacitet]; this.readSequence = 0; this.writeSequence = -1; } 

Dette opretter en tom buffer og initialiserer sekvensfelterne som beskrevet i det foregående afsnit.

3.3. Tilbud

Dernæst implementerer vi tilbud operation, der indsætter et element i bufferen i det næste tilgængelige slot og vender tilbage rigtigt om succes. Det vender tilbage falsk hvis bufferen ikke kan finde en tom plads, det vil sige vi kan ikke overskrive ulæste værdier.

Lad os implementere tilbud metode i Java:

offentligt boolsk tilbud (E-element) {boolsk isFull = (writeSequence - readSequence) + 1 == kapacitet; hvis (! isFull) {int nextWriteSeq = writeSequence + 1; data [nextWriteSeq% capacity] = element; writeSequence ++; returner sandt; } returner falsk; } 

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

Lad os prøve det:

@Test offentlig ugyldighed givenCircularBuffer_whenAnElementIsEnqueued_thenSizeIsOne () {CircularBuffer buffer = ny CircularBuffer (standardCapacity); assertTrue (buffer.offer ("Square")); assertEquals (1, buffer.size ()); } 

3.4. Afstemning

Endelig implementerer vi afstemning handling, der henter og fjerner det næste ulæste element. Det afstemning operation fjerner ikke elementet, men forøger læsningssekvensen.

Lad os implementere det:

offentlig E-afstemning () {boolean isEmpty = writeSequence <readSequence; hvis (! isEmpty) {E nextValue = data [readSequence% capacity]; readSequence ++; returner nextValue; } returnere null; } 

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

Lad os teste det:

@Test offentlig ugyldighed givenCircularBuffer_whenAnElementIsDequeued_thenElementMatchesEnqueuedElement () {CircularBuffer buffer = ny CircularBuffer (standardCapacity); buffer.offer ("Triangle"); Strengform = buffer.poll (); assertEquals ("Triangle", form); } 

4. Producent-forbrugerproblem

Vi har talt om brugen af ​​en ringbuffer til udveksling af 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-forbrugerproblemet på forskellige måder ved hjælp af semaforer, afgrænsede køer, ringbuffere osv.

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

4.1. flygtige Sekvensfelter

Vores implementering af ringbufferen er ikke trådsikker. Lad os gøre det trådsikkert for den enkle enkeltproducent- og enkeltforbruger sag.

Producenten skriver data til bufferen og forøger skrivSekvens, mens forbrugeren kun læser fra bufferen og forøger readSequence. Så backing-arrayet er uenigt, og vi kan komme væk uden synkronisering.

Men vi er stadig nødt til at sikre, at forbrugeren kan se den nyeste værdi af skrivSekvens felt (synlighed), og at skrivSekvens opdateres ikke, før dataene faktisk er tilgængelige i bufferen (bestilling).

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

privat flygtig int writeSequence = -1, readSequence = 0; 

I tilbud metode, en skrivning til flygtige Mark skrivSekvens garanterer, at skrivene til bufferen sker, inden sekvensen opdateres. På samme tid flygtige synlighedsgaranti sikrer, at forbrugeren altid vil se den nyeste værdi af skrivSekvens.

4.2. Producent

Lad os implementere en simpel producent Kan køres der skriver til ringbufferen:

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

Producenttråden ville vente på en tom plads i en løkke (travlt med at vente).

4.3. Forbruger

Vi implementerer en forbruger Kan kaldes der læser fra bufferen:

offentlig T [] kald () {T [] poster = (T []) nyt objekt [forventet antal]; for (int i = 0; i <items.length;) {T item = buffer.poll (); if (item! = null) {items [i ++] = item; System.out.println ("Forbruget:" + vare); }} returnere varer } 

Forbrugertråden fortsætter uden udskrivning, hvis den modtager en nul værdi fra bufferen.

Lad os skrive vores chaufførkode:

executorService.submit (ny tråd (ny producent (buffer))); executorService.submit (ny tråd (ny forbruger (buffer))); 

At udføre vores producent-forbrugerprogram producerer output som nedenfor:

Produceret: Cirkel Produceret: Trekant Forbrugt: Cirkel Produceret: Rektangel Forbrugt: Trekant Forbrugt: Rektangel Produceret: Firkantet Produceret: Rhombus Forbrugt: Firkantet Produceret: Trapezoid Forbrugt: Rhombus Forbrugt: Trapezoid Produceret: Pentagon Produceret: Pentagram Produceret: Hexagon Forbruget: Pentagon Forbrugt: Pentagram Produceret: Hexagram Forbrugt: Hexagon Forbrugt: Hexagram 

5. Konklusion

I denne vejledning har vi lært at implementere en ringbuffer og undersøgt, hvordan den kan bruges til at løse producent-forbrugerproblemet.

Som normalt er kildekoden til alle eksemplerne tilgængelig på GitHub.


$config[zx-auto] not found$config[zx-overlay] not found