streamalism.org

1. Pregled

U ovom uputstvu naučit ćemo kako implementirati Ring Buffer u Javi.

2. Ring pufer

Ring Buffer (ili Circular Buffer) ograničena je kružna struktura podataka koja se koristi za međuspremnik podataka između dvije ili više niti. Dok nastavljamo pisati u međuspremnik prstena, on se omotava čim stigne do kraja.

2.1. Kako radi

Ring Buffer implementiran je pomoću polja fiksne veličine koji se obavija na granicama.

Osim niza, bilježi i tri stvari:

• sljedeći raspoloživi utor u međuspremniku za umetanje elementa,
• sljedeći nepročitani element u međuspremniku,
• i kraj niza - točka u kojoj se međuspremnik omata do početka niza

Mehanika kako prstenasti odbojnik rješava ove zahtjeve razlikuje se ovisno o primjeni. Na primjer, unos u Wikipediji na tu temu prikazuje metodu pomoću četverostrukih pokazivača.

Pristup ćemo posuditi od implementacije Disruptor-a me uspremnika prstena pomoću sekvenci.

Prvo što moramo znati je kapacitet - fiksna maksimalna veličina međuspremnika. Sljedeći, koristit ćemo dvije monotono rastućesekvence:

• Napišite sekvencu: počevši od -1, uvećavajući za 1 dok umetamo element
• Slijed čitanja: počevši od 0, uvećavajući za 1 dok trošimo element

Možemo preslikati sekvencu na indeks u polju pomoću mod operacije:

arrayIndex = slijed% kapaciteta 

The mod operacija obavija sekvencu oko granica kako bi se dobio utor u međuspremniku:

Pogledajmo kako bismo umetnuli element:

međuspremnik [++ writeSequence% kapacitet] = element 

Prethodno povećavamo slijed prije umetanja elementa.

Da bismo potrošili element, radimo post-priraštaj:

element = međuspremnik [readSequence ++% kapaciteta] 

U ovom slučaju izvodimo post-priraštaj na slijedu. Konzumiranjem elementa ne uklanja se iz međuspremnika - on ostaje u polju dok se ne prepiše.

2.2. Prazni i puni odbojnici

Kako se omotavamo oko niza, počet ćemo prepisivati ​​podatke u međuspremnik. Ako je međuspremnik pun, možemo odabrati prepisivanje najstarijih podataka bez obzira je li ih čitač potrošio ili spriječiti prepisivanje podataka koji nisu pročitani.

Ako si čitatelj može priuštiti propuštanje srednjih ili starih vrijednosti (na primjer, oznaka cijene dionice), podatke možemo prebrisati bez čekanja da se potroše. S druge strane, ako čitač mora potrošiti sve vrijednosti (kao kod transakcija e-trgovine), trebali bismo pričekati (blokirati / zauzeti-čekati) dok međuspremnik ima na raspolaganju utor.

Međuspremnik je pun ako je veličina međuspremnika jednaka njegovom kapacitetu, pri čemu je njegova veličina jednaka broju nepročitanih elemenata:

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

Ako slijed zapisivanja zaostaje za slijedom čitanja, međuspremnik je prazan:

isEmpty = writeSequence <readSequence 

Me uspremnik vraća a null vrijednost ako je prazna.

2.2. Prednosti i nedostatci

Prstenasti međuspremnik učinkovit je FIFO međuspremnik. Koristi niz fiksne veličine koji se može unaprijed dodijeliti unaprijed i omogućuje učinkovit obrazac pristupa memoriji. Sve radnje međuspremnika su konstantno vrijeme O (1), uključujući konzumiranje elementa, jer ne zahtijeva pomicanje elemenata.

S druge strane, kritično je utvrđivanje točne veličine međuspremnika prstena. Na primjer, operacije pisanja mogu se dugo blokirati ako je međuspremnik premali, a čitanje sporo. Možemo koristiti dinamičko dimenzioniranje, ali to bi zahtijevalo pomicanje podataka i propustit ćemo većinu gore spomenutih prednosti.

3. Implementacija u Javi

Sad kad smo razumjeli kako radi međuspremnik prstena, krenimo s njegovom implementacijom u Javi.

3.1. Inicijalizacija

Prvo, definirajmo konstruktor koji inicijalizira međuspremnik s unaprijed definiranim kapacitetom:

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

To će stvoriti prazan međuspremnik i inicijalizirati polja sekvence kao što je objašnjeno u prethodnom odjeljku.

3.3. Ponuda

Dalje ćemo implementirati ponuda operacija koja ubacuje element u međuspremnik na sljedećem dostupnom utoru i vraća se pravi na uspjeh. Vraća se lažno ako međuspremnik ne može pronaći prazan utor, tj. ne možemo prepisati nepročitane vrijednosti.

Provedimo ponuda metoda u Javi:

javna logička ponuda (E element) {boolean isFull = (writeSequence - readSequence) + 1 == kapacitet; if (! isFull) {int nextWriteSeq = writeSequence + 1; podaci [nextWriteSeq% kapaciteta] = element; writeSequence ++; povratak istinit; } return false; } 

Dakle, povećavamo slijed pisanja i izračunavamo indeks u polju za sljedeći raspoloživi utor. Zatim zapisujemo podatke u međuspremnik i pohranjujemo ažurirani slijed pisanja.

Isprobajmo:

@Test javna praznina givenCircularBuffer_whenAnElementIsEnqueued_thenSizeIsOne () {CircularBuffer buffer = novi CircularBuffer (defaultCapacity); assertTrue (buffer.offer ("Square")); assertEquals (1, buffer.size ()); } 

3.4. Anketa

Napokon ćemo implementirati anketa operacija koja dohvaća i uklanja sljedeći nepročitani element. The anketa operacija ne uklanja element, ali povećava slijed čitanja.

Provedimo to:

javna E anketa () {boolean isEmpty = writeSequence <readSequence; if (! isEmpty) {E nextValue = podaci [readSequence% kapacitet]; readSequence ++; return nextValue; } return null; } 

Ovdje čitamo podatke u trenutnom slijedu čitanja izračunavanjem indeksa u polju. Zatim, povećavamo sekvencu i vraćamo vrijednost, ako međuspremnik nije prazan.

Isprobajmo:

@Test javna praznina givenCircularBuffer_whenAnElementIsDequeued_thenElementMatchesEnqueuedElement () {CircularBuffer buffer = novi CircularBuffer (defaultCapacity); buffer.offer ("Trokut"); Oblik niza = buffer.poll (); assertEquals ("Trokut", oblik); } 

4. Problem proizvođača i potrošača

Razgovarali smo o upotrebi prstenastog međuspremnika za razmjenu podataka između dvije ili više niti, što je primjer problema sa sinkronizacijom nazvanog problem Proizvođač-Potrošač. U Javi problem proizvođača i potrošača možemo riješiti na razne načine pomoću semafora, ograničenih redova, prstenastih međuspremnika itd.

Implementiramo rješenje temeljeno na prstenastom međuspremniku.

4.1. hlapljiv Polja slijeda

Naša primjena međuspremnika prstena nije sigurna u nitima. Učinimo to sigurnim za konac za jednostavni slučaj jednog proizvođača i jednog potrošača.

Proizvođač zapisuje podatke u međuspremnik i povećava writeSequence, dok potrošač samo čita iz međuspremnika i povećava readSequence. Dakle, sigurnosni niz je bez prepirki i možemo se izvući bez ikakve sinkronizacije.

Ali još uvijek moramo osigurati da potrošač vidi najnoviju vrijednost writeSequence polje (vidljivost) i da je writeSequence se ne ažurira prije nego što su podaci stvarno dostupni u međuspremniku (naručivanje).

U ovom slučaju možemo učiniti međuspremnik zvona istodobnim i bez zaključavanja tako što ćemo napraviti polja sekvence hlapljiv:

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

U ponuda metoda, pisanje u hlapljiv polje writeSequence jamči da se upisi u međuspremnik događaju prije ažuriranja niza. Istodobno, hlapljiv jamstvo vidljivosti osigurava da će potrošač uvijek vidjeti najnoviju vrijednost writeSequence.

4.2. Proizvođač

Primijenimo jednostavnog proizvođača Izvodljivo koji piše u međuspremnik prstena:

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

Nit proizvođača čekao bi prazan utor u petlji (zauzet-čekanje).

4.3. Potrošač

Primijenit ćemo potrošača Pozivno koji čita iz međuspremnika:

javni T [] poziv () {T [] stavke = (T []) novi objekt [očekivani broj]; for (int i = 0; i <items.length;) {T item = buffer.poll (); if (stavka! = null) {stavke [i ++] = stavka; System.out.println ("Potrošeno:" + stavka); }} vratiti stavke; } 

Potrošačka nit nastavlja se bez ispisa ako primi a null vrijednost iz međuspremnika.

Napišimo naš upravljački kod:

executorService.submit (nova nit (novi proizvođač (međuspremnik))); executorService.submit (nova nit (novi potrošač (međuspremnik))); 

Izvršenje našeg programa za proizvođače i potrošače daje rezultate kao u nastavku:

Proizvedeno: Krug proizvedeno: Trokut potrošeno: Krug proizvedeno: Pravokutnik potrošeno: Trokut potrošeno: Pravokutnik proizvedeno: Kvadratno proizvedeno: Rhombus potrošeno: Kvadratno proizvedeno: Trapezoid potrošeno: Rhombus potrošeno: Trapezoid Proizvedeno: Pentagon Proizvedeno: Pentagram Proizvedeno: Šesterokut potrošeno: Pentagon Potrošeno: Proizveden pentagram: konzumiran heksagram: potrošen heksagon: heksagram 

5. Zaključak

U ovom uputstvu naučili smo kako primijeniti Ring Buffer i istražili kako se on može koristiti za rješavanje problema proizvođača i potrošača.

Kao i obično, izvorni kod za sve primjere dostupan je na GitHubu.