Rengaspuskurin toteuttaminen Javassa

1. Yleiskatsaus

Tässä opetusohjelmassa opettelemme toteuttamaan rengaspuskurin Javassa.

Rengaspuskuri

Rengaspuskuri (tai ympyränmuotoinen puskuri) on rajattu ympyränmuotoinen tietorakenne, jota käytetään kahden tai useamman säikeen välisen tiedon puskurointiin. Kun jatkamme kirjoittamista rengaspuskuriin, se kietoutuu ympäri, kun se saavuttaa lopun.

2.1. Miten se toimii

Rengaspuskuri on toteutettu käyttämällä kiinteän kokoista matriisia, joka kietoutuu reunoilta ympäri.

Matriisin lisäksi se pitää kirjaa kolmesta asiasta:

• seuraavan vapaan paikan puskurissa, johon voidaan lisätä elementti,
• seuraavan lukemattoman elementin puskurissa,
• ja matriisin lopun – pisteen, jossa puskuri kiertyy ympäri matriisin alkuun

Mekaniikka, jolla rengas puskuri käsittelee näitä vaatimuksia, vaihtelee toteutuksesta riippuen. Esimerkiksi Wikipedian merkintä aiheesta esittelee menetelmän, jossa käytetään neljän osoittimia.

Lainaamme lähestymistapaa Disruptorin rengaspuskurin toteutuksesta, jossa käytetään sekvenssejä.

Ensin on tiedettävä kapasiteetti – puskurin kiinteä maksimikoko. Seuraavaksi käytämme kahta monotonisesti kasvavaa sekvenssiä:

• Kirjoitussekvenssi: alkaa -1:stä, kasvaa 1:llä, kun lisäämme elementin
• Lukusekvenssi: alkaa 0:sta, kasvaa 1:llä, kun kulutamme elementin

Voimme kuvata sekvenssin indeksiin matriisissa käyttämällä mod-operaatiota:

arrayIndex = sequence % capacity

Mod-operaatio kietoo sekvenssin rajojen ympärille, jotta saadaan puskurissa oleva paikka:

Katsotaanpa, miten lisäämme elementin:

buffer = element

Kasvatamme sekvenssiä valmiiksi ennen elementin lisäämistä.

Kuluttaaksemme elementin teemme jälkikorotuksen:

element = buffer

Tässä tapauksessa suoritamme jälkikorotuksen sekvenssille. Elementin kuluttaminen ei poista sitä puskurista – se vain pysyy joukossa, kunnes se ylikirjoitetaan.

2.2. Elementin kuluttaminen. Tyhjät ja täydet puskurit

Kierrettäessä arraya alamme ylikirjoittaa puskurissa olevaa dataa. Jos puskuri on täynnä, voimme valita, että joko ylikirjoitamme vanhimman datan riippumatta siitä, onko lukija kuluttanut sen, tai estämme lukemattoman datan ylikirjoittamisen.

Jos lukijalla on varaa jättää väliin väliin jääviä tai vanhoja arvoja (esimerkiksi pörssikurssin tiketti), voimme ylikirjoittaa datan odottamatta sen kuluttamista. Toisaalta, jos lukijan on kulutettava kaikki arvot (kuten verkkokauppatapahtumissa), meidän on odotettava (block/busy-wait), kunnes puskurissa on vapaa paikka.

Puskuri on täynnä, jos puskurin koko on yhtä suuri kuin sen kapasiteetti, jolloin puskurin koko on yhtä suuri kuin lukemattomien elementtien määrä:

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

Jos kirjoitusjakso on jäljessä lukujonosta, puskuri on tyhjä:

isEmpty = writeSequence < readSequence

Puskuri palauttaa nolla-arvon, jos puskuri on tyhjä:

2.2. Puskuri on täynnä. Edut ja haitat

Rengaspuskuri on tehokas FIFO-puskuri. Se käyttää kiinteän kokoista matriisia, joka voidaan varata etukäteen ja mahdollistaa tehokkaan muistin käyttötavan. Kaikki puskurioperaatiot ovat vakioajassa O(1), mukaan lukien elementin kuluttaminen, koska se ei vaadi elementtien siirtämistä.

Kääntöpuolella rengaspuskurin oikean koon määrittäminen on kriittistä. Esimerkiksi kirjoitusoperaatiot voivat tukkeutua pitkäksi aikaa, jos puskuri on alikokoinen ja lukeminen on hidasta. Voimme käyttää dynaamista kokoa, mutta se edellyttäisi datan siirtelyä ja jättäisimme käyttämättä suurimman osan edellä käsitellyistä eduista.

Toteutus Javassa

Nyt kun olemme ymmärtäneet, miten rengaspuskuri toimii, siirrymme toteuttamaan sen Javassa.

3.1. Rengaspuskuri ja Java. Initialisointi

Määritellään ensin konstruktori, joka alustaa puskurin ennalta määritellyllä kapasiteetilla:

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

Tällöin luodaan tyhjä puskuri ja alustetaan sekvenssikentät edellisessä kappaleessa käsitellyllä tavalla.

3.2. Puskurin alustaminen. Tarjous

Seuraavaksi toteutetaan tarjousoperaatio, joka lisää elementin puskuriin seuraavaan vapaaseen paikkaan ja palauttaa true-arvon onnistuessaan. Se palauttaa false, jos puskurista ei löydy tyhjää paikkaa, eli emme voi ylikirjoittaa lukemattomia arvoja.

Toteutetaan tarjous-metodi Javalla:

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

Toteutetaan siis kirjoitussekvenssi inkrementaalisesti ja lasketaan seuraavan vapaan paikan indeksi matriisissa. Sitten kirjoitamme datan puskuriin ja tallennamme päivitetyn kirjoitussekvenssin.

Kokeillaanpa:

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

3.3. Poll

Toteutetaan lopuksi poll-operaatio, joka hakee ja poistaa seuraavan lukemattoman elementin. Poll-operaatio ei poista elementtiä, vaan kasvattaa lukusekvenssiä.

Toteutetaan se:

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

Tässä luemme dataa nykyisellä lukusekvenssillä laskemalla indeksin matriisissa. Sitten kasvatamme lukujonoa ja palautamme arvon, jos puskuri ei ole tyhjä.

Testataan se:

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

Tuottaja-kuluttaja -ongelma

Olemme puhuneet rengaspuskurin käytöstä kahden tai useamman säikeen välisessä tiedonvaihdossa, mikä on esimerkki synkronointiongelmasta, jota kutsutaan tuottaja-kuluttaja -ongelmaksi. Javassa voimme ratkaista tuottaja-kuluttaja -ongelman monin eri tavoin käyttämällä semaforeja, rajattuja jonoja, rengaspuskureita jne.

Toteutetaan rengaspuskuriin perustuva ratkaisu.

4.1. Haihtuvat sekvenssikentät

Rengaspuskurin toteutuksemme ei ole säikeenkestävä. Tehdään siitä säiketurvallinen yksinkertaisessa yhden tuottajan ja yhden kuluttajan tapauksessa.

Tuottaja kirjoittaa dataa puskuriin ja kasvattaa writeSequencea, kun taas kuluttaja vain lukee puskurista ja kasvattaa readSequencea. Taustamäärikkö on siis contention-free ja pääsemme ilman synkronointia.

Mutta meidän on silti varmistettava, että kuluttaja näkee writeSequence-kentän viimeisimmän arvon (näkyvyys) ja että writeSequencea ei päivitetä ennen kuin data on todella saatavilla puskurissa (järjestys).

Voimme tehdä rengaspuskurista tässä tapauksessa samanaikaisen ja lukkiutumattoman tekemällä sekvenssikentistä volatile:

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

Tarjousmetodissa kirjoitus volatile-kenttään writeSequence takaa, että kirjoitukset puskuriin tapahtuvat ennen sekvenssin päivittämistä. Samalla volatile-näkyvyystakuu takaa, että kuluttaja näkee aina writeSequence-kentän viimeisimmän arvon.

4.2. Haihtuva näkyvyys. Tuottaja

Toteutetaan yksinkertainen tuottaja Runnable, joka kirjoittaa rengaspuskuriin:

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

Tuottajasäie odottaisi tyhjää paikkaa silmukassa (busy-waiting).

4.3. Kuluttaja

Toteutetaan kuluttaja Callable, joka lukee puskurista:

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

Kuluttajalanka jatkaa ilman tulostusta, jos se saa puskurista nolla-arvon.

Kirjoitetaan ajurikoodimme:

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

Tuottaja-kuluttaja -ohjelmamme suorittaminen tuottaa alla olevan kaltaisen tulosteen:

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

Loppupäätelmä

Tässä opetusohjelmassa opimme toteuttamaan rengaspuskurin ja tutkimme, miten sitä voidaan käyttää tuottaja-kuluttaja -ongelman ratkaisemiseen.