streamalism.org

1. Prehľad

V tomto tutoriále sa dozvieme, ako implementovať Ring Buffer v Jave.

2. Ring Buffer

Ring Buffer (alebo Circular Buffer) je ohraničená kruhová dátová štruktúra, ktorá sa používa na ukladanie dát medzi dvoma alebo viacerými vláknami.. Keď stále píšeme do medzipamäte krúžkov, okolo konca sa to zalomí.

2.1. Ako to funguje

Ring Buffer je implementovaný pomocou poľa s pevnou veľkosťou, ktoré sa obklopuje okolo hraníc.

Okrem poľa sleduje tri veci:

• ďalší voľný slot vo vyrovnávacej pamäti na vloženie prvku,
• nasledujúci neprečítaný prvok vo vyrovnávacej pamäti,
• a koniec poľa - bod, v ktorom sa vyrovnáva vyrovnávacia pamäť na začiatok poľa

Mechanika toho, ako kruhový buffer zvláda tieto požiadavky, sa líši podľa implementácie. Napríklad položka Wikipedia na predmete ukazuje metódu využívajúcu štyri ukazovatele.

Prístup si požičiame od Disruptorovej implementácie ring bufferu pomocou sekvencií.

Prvá vec, ktorú musíme vedieť, je kapacita - pevná maximálna veľkosť vyrovnávacej pamäte. Ďalšie, použijeme dva monotónne rastúcesekvencie:

• Sekvencia zápisu: začínajúca na -1, pri vkladaní prvku sa zvyšuje o 1
• Postupnosť čítania: od 0 sa pri konzumácii prvku zvyšuje o 1

Sekvenciu môžeme namapovať na index v poli pomocou operácie mod:

arrayIndex = postupnosť% kapacity 

The operácia mod zalomí sekvenciu okolo hraníc, aby sa odvodila štrbina vo vyrovnávacej pamäti:

Pozrime sa, ako vložíme prvok:

buffer [++ writeSequence% kapacity] = prvok 

Pred vložením prvku predbežne zvyšujeme postupnosť.

Aby sme spotrebovali prvok, urobíme prírastok:

prvok = vyrovnávacia pamäť [readSequence ++% kapacity] 

V takom prípade vykonáme po prírastku postupnosti. Spotreba prvku ho neodstráni z medzipamäte - iba zostane v poli, kým sa neprepíše.

2.2. Prázdne a plné vyrovnávacie pamäte

Keď sa omotáme okolo poľa, začneme prepisovať údaje vo vyrovnávacej pamäti. Ak je vyrovnávacia pamäť plná, môžeme zvoliť prepísanie najstarších údajov bez ohľadu na to, či ich čítačka spotrebovala, alebo zabrániť prepísaniu údajov, ktoré neboli načítané..

Ak si čitateľ môže dovoliť vynechať stredné alebo staré hodnoty (napríklad ticker ceny akcií), môžeme údaje prepísať bez toho, aby sme čakali na ich spotrebovanie. Na druhej strane, ak čítačka musí spotrebovať všetky hodnoty (ako pri transakciách elektronického obchodu), mali by sme počkať (blok / busy-wait), kým vyrovnávacia pamäť nebude mať k dispozícii slot.

Vyrovnávacia pamäť je plná, ak sa veľkosť vyrovnávacej pamäte rovná jeho kapacite, kde sa jeho veľkosť rovná počtu neprečítaných prvkov:

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

Ak sekvencia zápisu zaostáva za sekvenciou čítania, vyrovnávacia pamäť je prázdna:

isEmpty = writeSequence <readSequence 

Vyrovnávacia pamäť vracia a nulový hodnota, ak je prázdna.

2.2. Výhody a nevýhody

Kruhový buffer je efektívny FIFO buffer. Používa pole pevnej veľkosti, ktoré je možné vopred prideliť vopred, a umožňuje efektívny vzor prístupu do pamäte. Všetky operácie vyrovnávacej pamäte sú v konštantnom čase O (1), vrátane konzumácie prvku, pretože to nevyžaduje presun prvkov.

Na druhej strane je určenie správnej veľkosti prstencového bufferu kritické. Napríklad operácie zápisu môžu dlho blokovať, ak je veľkosť medzipamäte nízka a načítania sú pomalé. Môžeme použiť dynamické dimenzovanie, vyžadovalo by to však presun údajov a my by sme prišli o väčšinu výhod, ktoré sú popísané vyššie.

3. Implementácia v Jave

Teraz, keď už rozumieme tomu, ako funguje medzipamäť krúžkov, pristúpime k jej implementácii v Jave.

3.1. Inicializácia

Najskôr definujme konštruktor, ktorý inicializuje vyrovnávaciu pamäť s preddefinovanou kapacitou:

public CircularBuffer (int kapacita) {this.capacity = kapacita; this.data = (E []) nový objekt [kapacita]; this.readSequence = 0; this.writeSequence = -1; } 

Takto sa vytvorí prázdna vyrovnávacia pamäť a inicializujú sa sekvenčné polia, ako je uvedené v predchádzajúcej časti.

3.3. Ponuka

Ďalej implementujeme ponuka operácia, ktorá vloží prvok do medzipamäte na najbližšej dostupnej pozícii a vráti sa pravda o úspechu. Vracia sa to nepravdivé ak vyrovnávacia pamäť nemôže nájsť prázdny slot, to znamená, nemôžeme prepísať neprečítané hodnoty.

Poďme implementovať ponuka metóda v Jave:

public boolean offer (E element) {boolean isFull = (writeSequence - readSequence) + 1 == kapacita; if (! isFull) {int nextWriteSeq = writeSequence + 1; data [nextWriteSeq% kapacity] = prvok; writeSequence ++; návrat pravdivý; } return false; } 

Takže zvyšujeme sekvenciu zápisu a vypočítavame index v poli pre ďalší dostupný slot. Potom zapisujeme údaje do medzipamäte a ukladáme aktualizovanú postupnosť zápisu.

Vyskúšajme to:

@Test public void givenCircularBuffer_whenAnElementIsEnqueued_thenSizeIsOne () {CircularBuffer buffer = nový CircularBuffer (defaultCapacity); assertTrue (buffer.offer ("štvorec")); assertEquals (1, buffer.size ()); } 

3.4. Anketa

Nakoniec implementujeme anketa operácia, ktorá načíta a odstráni nasledujúci neprečítaný prvok. The anketa operácia neodstráni prvok, ale zvýši sekvenciu čítania.

Poďme to implementovať:

public E poll () {boolean isEmpty = writeSequence <readSequence; if (! isEmpty) {E nextValue = data [readSequence% capacity]; readSequence ++; návrat nextValue; } return null; } 

Tu čítame údaje v aktuálnej sekvencii čítania výpočtom indexu v poli. Potom zvyšujeme postupnosť a vraciame hodnotu, ak vyrovnávacia pamäť nie je prázdna.

Vyskúšajme to:

@Test public void givenCircularBuffer_whenAnElementIsDequeued_thenElementMatchesEnqueuedElement () {buffer CircularBuffer = nový CircleBuffer (defaultCapacity); buffer.offer („Triangle“); Tvar reťazca = buffer.poll (); assertEquals ("Trojuholník", tvar); } 

4. Problém výrobcu a spotrebiteľa

Hovorili sme o použití kruhového bufferu na výmenu údajov medzi dvoma alebo viacerými vláknami, čo je príklad problému so synchronizáciou, ktorý sa nazýva problém producent-spotrebiteľ. V Jave môžeme problém producenta a spotrebiteľa vyriešiť rôznymi spôsobmi pomocou semaforov, ohraničených frontov, ring bufferov atď.

Implementujme riešenie založené na kruhovej vyrovnávacej pamäti.

4.1. prchavý Sekvenčné polia

Naša implementácia kruhového bufferu nie je bezpečná pre vlákna. Urobme to bezpečným pre vlákna pre jednoduchý prípad jedného výrobcu a jedného spotrebiteľa.

Výrobca zapíše údaje do medzipamäte a zvýši hodnotu writeSequence, zatiaľ čo spotrebiteľ iba číta z medzipamäte a zvyšuje hodnotu readSequence. Podporné pole je teda bez sporov a my sa môžeme dostať preč bez akejkoľvek synchronizácie.

Stále však musíme zabezpečiť, aby spotrebiteľ mohol vidieť najnovšiu hodnotu produktu writeSequence pole (viditeľnosť) a že writeSequence sa neaktualizuje skôr, ako budú údaje skutočne k dispozícii vo vyrovnávacej pamäti (zoradenie).

V tomto prípade môžeme urobiť medzipamäť medzipamäte tým, že vytvoríme sekvenčné polia prchavý:

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

V ponuka metóda, zápis do prchavý lúka writeSequence zaručuje, že k zápisom do medzipamäte dôjde pred aktualizáciou sekvencie. Súčasne prchavý záruka viditeľnosti zaručuje, že spotrebiteľ bude vždy vidieť najnovšiu hodnotu writeSequence.

4.2. Výrobca

Implementujme jednoduchého producenta Spustiteľné ktorý zapíše do medzipamäte zvonenia:

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

Produkčné vlákno by čakalo na prázdny slot v slučke (rušné čakanie).

4.3. Spotrebiteľ

Implementujeme spotrebiteľa Vyvolávateľná ktorý číta z medzipamäte:

verejné T [] volanie () {T [] položky = (T []) nový objekt [expectCount]; pre (int i = 0; i <items.length;) {T item = buffer.poll (); if (item! = null) {items [i ++] = item; System.out.println ("Spotrebované:" + položka); }} vrátiť položky; } 

Spotrebiteľské vlákno pokračuje bez tlače, ak prijme a nulový hodnota z bufferu.

Napíšme náš kód vodiča:

executorService.submit (new Thread (new Producer (buffer))); executorService.submit (new Thread (new Consumer (buffer)))); 

Vykonávanie nášho programu producent-spotrebiteľ produkuje výstup uvedený nižšie:

Produkoval: Circle Produced: Triangle Consumed: Circle Produced: Rectangle Consumed: Triangle Consumed: Rectangle Produced: Square Produced: Rhombus Consumed: Square Produced: Trapezoid Consumed: Rhombus Consumed: Trapezoid Produced: Pentagon Produced: Pentagram Produced: Hexagon Consumed: Vyrobený Pentagram: Spotrebovaný hexagram: Spotrebovaný hexagon: Hexagram 

5. Záver

V tomto tutoriáli sme sa naučili, ako implementovať Ring Buffer, a preskúmali sme, ako sa dá použiť na riešenie problému producent - spotrebiteľ.

Ako obvykle je zdrojový kód všetkých príkladov k dispozícii na serveri GitHub.