streamalism.org

1. Oversikt

I denne veiledningen lærer vi hvordan du implementerer en ringebuffer i Java.

2. Ringbuffer

Ring Buffer (eller Circular Buffer) er en avgrenset sirkulær datastruktur som brukes til å buffere data mellom to eller flere tråder. Når vi fortsetter å skrive til en ringbuffer, brytes den rundt når den når slutten.

2.1. Hvordan det fungerer

En ringbuffer er implementert ved hjelp av en matrise med fast størrelse som brytes rundt på grensene.

Bortsett fra matrisen holder den rede på tre ting:

• neste tilgjengelige spor i bufferen for å sette inn et element,
• neste uleste element i bufferen,
• og slutten av matrisen - punktet hvor bufferen brytes rundt til starten av matrisen

Mekanikken til hvordan en ringbuffer håndterer disse kravene, varierer med implementeringen. For eksempel viser Wikipedia-oppføringen om emnet en metode som bruker fire-pekere.

Vi låner tilnærmingen fra Disruptors implementering av ringbufferen ved hjelp av sekvenser.

Det første vi trenger å vite er kapasiteten - den faste maksimale størrelsen på bufferen. Neste, vi bruker to monotont økendesekvenser:

• Skriv sekvens: starter ved -1, trinn med 1 når vi setter inn et element
• Les Sekvens: starter ved 0, trinn med 1 når vi bruker et element

Vi kan kartlegge en sekvens til en indeks i matrisen ved hjelp av en modoperasjon:

arrayIndex = sekvens% kapasitet 

De mod-operasjon bryter sekvensen rundt grensene for å utlede et spor i bufferen:

La oss se hvordan vi setter inn et element:

buffer [++ writeSequence% capacity] = element 

Vi øker sekvensen før vi setter inn et element.

For å konsumere et element gjør vi en etterøkning:

element = buffer [readSequence ++% kapasitet] 

I dette tilfellet utfører vi en etterøkning på sekvensen. Å forbruke et element fjerner det ikke fra bufferen - det blir bare i matrisen til det blir overskrevet.

2.2. Tomme og fulle buffere

Når vi vikler rundt matrisen, begynner vi å overskrive dataene i bufferen. Hvis bufferen er full, kan vi velge å overskrive de eldste dataene uavhengig av om leseren har brukt dem, eller forhindre overskriving av dataene som ikke er lest..

Hvis leseren har råd til å savne de mellomliggende eller gamle verdiene (for eksempel en aksjekurs), kan vi overskrive dataene uten å vente på at de skal konsumeres. På den annen side, hvis leseren må forbruke alle verdiene (som med e-handelstransaksjoner), bør vi vente (blokkere / opptatt-vente) til bufferen har et spor tilgjengelig.

Bufferen er full hvis størrelsen på bufferen er lik kapasiteten, hvor størrelsen er lik antall uleste elementer:

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

Hvis skrivesekvensen henger etter lesesekvensen, er bufferen tom:

isEmpty = writeSequence <readSequence 

Bufferen returnerer a null verdi hvis den er tom.

2.2. Fordeler og ulemper

En ringbuffer er en effektiv FIFO-buffer. Den bruker et array i fast størrelse som kan forhåndsallokeres på forhånd og gir et effektivt minnetilgangsmønster. Alle bufferoperasjoner er konstant tid O (1), inkludert forbruk av et element, da det ikke krever en forskyvning av elementene.

På baksiden er det viktig å bestemme riktig størrelse på ringbufferen. For eksempel kan skriveoperasjonene blokkere i lang tid hvis bufferen er for liten og avlesningene er treg. Vi kan bruke dynamisk størrelse, men det vil kreve flytting av data, og vi vil gå glipp av de fleste fordelene som er diskutert ovenfor.

3. Implementering i Java

Nå som vi forstår hvordan en ringebuffer fungerer, la oss fortsette å implementere den i Java.

3.1. Initialisering

La oss først definere en konstruktør som initialiserer bufferen med en forhåndsdefinert kapasitet:

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

Dette vil opprette en tom buffer og initialisere sekvensfeltene som diskutert i forrige avsnitt.

3.3. By på

Deretter implementerer vi by på operasjon som setter inn et element i bufferen i neste tilgjengelige spor og returnerer ekte på suksess. Det kommer tilbake falsk hvis bufferen ikke finner et tomt spor, det vil si vi kan ikke overskrive uleste verdier.

La oss implementere by på metode i Java:

offentlig boolsk tilbud (E-element) {boolsk isFull = (writeSequence - readSequence) + 1 == kapasitet; hvis (! isFull) {int nextWriteSeq = writeSequence + 1; data [nextWriteSeq% kapasitet] = element; writeSequence ++; returner sant; } returner falsk; } 

Så vi øker skrivesekvensen og beregner indeksen i matrisen for neste tilgjengelige spor. Deretter skriver vi dataene til bufferen og lagrer den oppdaterte skrivesekvensen.

La oss prøve det:

@Test offentlig ugyldig gittCircularBuffer_whenAnElementIsEnqueued_thenSizeIsOne () {CircularBuffer buffer = new CircularBuffer (defaultCapacity); assertTrue (buffer.offer ("Square")); assertEquals (1, buffer.size ()); } 

3.4. avstemming

Til slutt implementerer vi avstemming operasjon som henter og fjerner neste uleste element. De avstemming operasjonen fjerner ikke elementet, men øker lesesekvensen.

La oss implementere det:

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

Her leser vi dataene i gjeldende lesesekvens ved å beregne indeksen i matrisen. Deretter øker vi sekvensen og returnerer verdien, hvis bufferen ikke er tom.

La oss teste det ut:

@Test offentlig ugyldig gittCircularBuffer_whenAnElementIsDequeued_thenElementMatchesEnqueuedElement () {CircularBuffer buffer = new CircularBuffer (defaultCapacity); buffer.offer ("Triangle"); Strengform = buffer.poll (); assertEquals ("Triangle", form); } 

4. Produsent-forbrukerproblem

Vi har snakket om bruk av en ringebuffer for utveksling av data mellom to eller flere tråder, som er et eksempel på et synkroniseringsproblem som kalles Producer-Consumer-problemet. I Java kan vi løse produsent-forbrukerproblemet på forskjellige måter ved hjelp av semaforer, avgrensede køer, ringbuffere osv.

La oss implementere en løsning basert på en ringebuffer.

4.1. flyktige Sekvensfelt

Vår implementering av ringbufferen er ikke trådsikker. La oss gjøre det trådsikkert for den enkle saken fra enkeltprodusent og enkeltforbruker.

Produsenten skriver data til bufferen og øker skrivSekvens, mens forbrukeren bare leser fra bufferen og øker readSequence. Så, backing-arrayet er ubestridelig, og vi kan komme oss unna uten synkronisering.

Men vi må fortsatt sørge for at forbrukeren kan se den nyeste verdien av skrivSekvens felt (synlighet) og at skrivSekvens oppdateres ikke før dataene faktisk er tilgjengelige i bufferen (bestilling).

Vi kan gjøre ringbufferen samtidig og låsfri i dette tilfellet ved å lage sekvensfeltene flyktige:

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

I by på metode, en skriv til flyktige felt skrivSekvens garanterer at skrivene til bufferen skjer før du oppdaterer sekvensen. Samtidig er den flyktige synlighet garanterer at forbrukeren alltid vil se den nyeste verdien av skrivSekvens.

4.2. Produsent

La oss implementere en enkel produsent Kjørbar som 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 ++; }}} 

Produsentetråden ville vente på et tomt spor i en løkke (travelt ventende).

4.3. Forbruker

Vi implementerer en forbruker Kan kalles som leser fra bufferen:

offentlig T [] samtale () {T [] elementer = (T []) nytt objekt [forventet antall]; for (int i = 0; i <items.length;) {T item = buffer.poll (); if (item! = null) {items [i ++] = item; System.out.println ("Forbruket:" + vare); }} returnere varer; } 

Forbrukertråden fortsetter uten utskrift hvis den mottar en null verdi fra bufferen.

La oss skrive førerkoden vår:

executorService.submit (ny tråd (ny produsent (buffer))); executorService.submit (ny tråd (ny forbruker (buffer))); 

Å gjennomføre vårt produsent-forbrukerprogram gir produksjon som nedenfor:

Produsert: Circle Produsert: Triangle Forbruket: Circle Producert: Rectangle Forbruket: Triangle Forbruket: Rectangle Produsert: Square Produsert: Rhombus Forbruket: Square Produsert: Trapezoid Forbruket: Rhombus Forbruket: Trapezoid Produsert: Pentagon Produsert: Pentagram Produsert: Hexagon Forbruket: Pentagon Forbruket: Pentagram Produsert: Hexagram Forbruket: Hexagon Forbruket: Hexagram 

5. Konklusjon

I denne opplæringen har vi lært hvordan vi implementerer en ringbuffer og utforsket hvordan den kan brukes til å løse produsent-forbrukerproblemet.

Som vanlig er kildekoden for alle eksemplene tilgjengelig på GitHub.