streamalism.org

1. Áttekintés

Ebben az oktatóanyagban megtanuljuk, hogyan kell megvalósítani a gyűrűpuffert Java-ban.

2. Ring puffer

A Ring Buffer (vagy Circular Buffer) egy korlátozott kör alakú adatstruktúra, amelyet két vagy több szál közötti adatok pufferelésére használnak. Amint folyamatosan írunk egy gyűrűs pufferre, a végére érve körbetekerik.

2.1. Hogyan működik

A gyűrűpuffert egy fix méretű tömb felhasználásával valósítják meg, amely körbefut a határokon.

A tömbön kívül három dolgot nyomon követ:

• a következő elérhető rés a pufferben egy elem beillesztésére,
• a puffer következő olvasatlan eleme,
• és a tömb vége - az a pont, ahol a puffer körbeteker a tömb elejéig

A gyűrűs puffer e követelmények kezelésének mechanikája a megvalósítástól függ. Például a témával kapcsolatos Wikipedia-bejegyzés négymutatót alkalmazó módszert mutat.

A megközelítést Disruptor gyűrűpuffer szekvenciák segítségével történő megvalósításából kölcsönözzük.

Az első dolog, amit tudnunk kell, a kapacitás - a puffer rögzített maximális mérete. Következő, két monoton növekedést fogunk használniszekvenciák:

• Írja a szekvenciát: -1-től kezdődően 1-gyel növekszik, amikor beillesztünk egy elemet
• Olvassa el a Szekvencia: 0-tól kezdődően 1-gyel növekszik, amikor egy elemet fogyasztunk

A tömb indexéhez leképezhetünk egy szekvenciát egy mod művelet segítségével:

arrayIndex = sorozat% kapacitás 

A A mod művelet a határok köré tekeri a sorrendet, hogy rést nyerjen a pufferben:

Nézzük meg, hogyan illesztenénk be egy elemet:

puffer [++ writeSequence% capacity] = elem 

Egy elem beszúrása előtt előre növeljük a szekvenciát.

Egy elem fogyasztásához utólagos növekedést hajtunk végre:

elem = puffer [readSequence ++% kapacitás] 

Ebben az esetben utólagos növekedést hajtunk végre a szekvencián. Egy elem fogyasztása nem távolítja el a pufferből - csak addig marad a tömbben, amíg felül nem íródik.

2.2. Üres és teljes pufferek

Amint körbetekerjük a tömböt, elkezdjük felülírni az adatokat a pufferben. Ha a puffer megtelt, akkor választhatjuk, hogy felülírjuk-e a legrégebbi adatokat, függetlenül attól, hogy az olvasó elfogyasztotta-e, vagy megakadályozhatjuk az elolvasatlan adatok felülírását.

Ha az olvasó megengedheti magának, hogy kihagyja a köztes vagy a régi értékeket (például egy részvényárfolyam-ticker), akkor felülírhatjuk az adatokat, anélkül, hogy megvárnánk a felhasználást. Másrészt, ha az olvasónak el kell fogyasztania az összes értéket (mint például az e-kereskedelmi tranzakcióknál), akkor várnunk kell (blokk / foglalt-várakozás), amíg a pufferben rendelkezésre áll egy rés.

A puffer megtelt, ha a puffer mérete megegyezik a kapacitásával, ahol a mérete megegyezik az olvasatlan elemek számával:

méret = (writeSequence - readSequence) + 1 isFull = (méret == kapacitás) 

Ha az írási szekvencia elmarad az olvasási szekvenciától, akkor a puffer üres:

isEmpty = writeSequence <readSequence 

A puffer visszaadja a nulla érték, ha üres.

2.2. Előnyök és hátrányok

A gyűrűpuffer hatékony FIFO puffer. Rögzített méretű tömböt használ, amelyet előre el lehet osztani, és hatékony memóriaelérési mintát tesz lehetővé. Az összes puffer művelet állandó idő O (1), beleértve egy elem fogyasztását, mivel ez nem igényli az elemek váltását.

A másik oldalon kritikus a gyűrűpuffer helyes méretének meghatározása. Például az írási műveletek hosszú ideig blokkolhatnak, ha a puffer alulméretezett és az olvasás lassú. Használhatunk dinamikus méretezést, de ehhez adatok mozgatására lenne szükség, és a fent tárgyalt előnyök nagy részét kihagyjuk.

3. Megvalósítás Java-ban

Most, hogy megértettük a gyűrűpuffer működését, folytassuk a Java alkalmazásban.

3.1. Inicializálás

Először definiáljunk egy konstruktort, amely inicializálja a puffert egy előre meghatározott kapacitással:

public CircularBuffer (int kapacitás) {this.kapacitás = kapacitás; this.data = (E []) új objektum [kapacitás]; this.readSequence = 0; this.writeSequence = -1; } 

Ez létrehoz egy üres puffert és inicializálja a szekvenciamezőket az előző szakaszban leírtak szerint.

3.3. Ajánlat

Ezután megvalósítjuk a ajánlat művelet, amely a következő elérhető résbe beilleszt egy elemet a pufferbe, és visszatér igaz a sikerről. Visszatér hamis ha a puffer nem talál üres rést, vagyis nem írhatjuk felül az olvasatlan értékeket.

Végezzük el a ajánlat módszer Java-ban:

nyilvános logikai ajánlat (E elem) {logikai isFull = (writeSequence - readSequence) + 1 == kapacitás; if (! isFull) {int nextWriteSeq = writeSequence + 1; adatok [nextWriteSeq% kapacitás] = elem; writeSequence ++; return true; } return false; } 

Tehát növeljük az írási sorrendet, és kiszámoljuk a tömb indexét a következő elérhető réshez. Ezután írjuk az adatokat a pufferbe, és tároljuk a frissített írási sorrendet.

Próbáljuk ki:

@Test public void givenCircularBuffer_whenAnElementIsEnqueued_thenSizeIsOne () {CircularBuffer buffer = new CircularBuffer (defaultCapacity); assertTrue (buffer.offer ("Négyzet")); assertEquals (1, buffer.size ()); } 

3.4. Közvélemény kutatás

Végül megvalósítjuk a közvélemény kutatás művelet, amely lekéri és eltávolítja a következő olvasatlan elemet. A közvélemény kutatás A művelet nem távolítja el az elemet, hanem növeli az olvasási sorrendet.

Végezzük el:

nyilvános E poll () {logikai isEmpty = writeSequence <readSequence; if (! isEmpty) {E nextValue = adatok [readSequence% kapacitás]; readSequence ++; return nextValue; } return null; } 

Itt az aktuális olvasási sorrend adatait olvassuk a tömb indexének kiszámításával. Ezután növeljük a sorrendet és visszaadjuk az értéket, ha a puffer nem üres.

Próbáljuk ki:

@Test public void givenCircularBuffer_whenAnElementIsDequeued_thenElementMatchesEnqueuedElement () {CircularBuffer buffer = new CircularBuffer (defaultCapacity); buffer.offer ("Háromszög"); Karakterlánc alakja = buffer.poll (); assertEquals ("háromszög", alak); } 

4. Termelő-fogyasztó probléma

Beszéltünk egy gyűrűs puffer használatáról két vagy több szál közötti adatcserére, amely példa egy szinkronizálási problémára, amelyet Producer-Consumer problémának hívnak. A Java-ban a termelő-fogyasztó problémáját különféle módokon oldhatjuk meg szemaforok, korlátozott sorok, gyűrűpufferek stb.

Vezessünk be egy gyűrűpufferen alapuló megoldást.

4.1. illó Szekvencia mezők

A gyűrűs puffer megvalósítása nem biztonságos a menetben. Tegyük szálbiztonságossá az egyszerű egytermelő és egyfogyasztó esetében.

A gyártó adatokat ír a pufferbe, és növeli a writeSequence, míg a fogyasztó csak a pufferből olvas és növeli a readSequence. Tehát, a háttértömb nem vitatott és szinkronizálás nélkül megúszhatjuk.

De még mindig biztosítanunk kell, hogy a fogyasztó lássa a legfrissebb értéket writeSequence mező (láthatóság), és hogy a writeSequence nem frissül, mielőtt az adatok ténylegesen rendelkezésre állnak a pufferben (megrendelés).

A gyűrűpuffert egyidejűvé és zármentessé tehetjük ebben az esetben a szekvenciamezők létrehozásával illó:

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

Ban,-ben ajánlat módszer, írjon a illó terület writeSequence garantálja, hogy az írások a pufferbe a szekvencia frissítése előtt történnek. Ugyanakkor a illó a láthatósági garancia biztosítja, hogy a fogyasztó mindig a legújabb értékét lássa writeSequence.

4.2. Termelő

Vezessünk be egy egyszerű producert Futható amely a gyűrűpufferbe írja:

public void run () {for (int i = 0; i <item.length;) {if (buffer.offer (items [i])) {System.out.println ("Előállítva:" + elemek [i]) ; i ++; }}} 

A producer szál egy üres rést várna egy hurokban (foglalt-várakozás).

4.3. Fogyasztó

Megvalósítjuk a fogyasztót Hívható amely a pufferből olvasható:

nyilvános T [] hívás () {T [] tételek = (T []) új objektum [várható szám]; for (int i = 0; i <tételek.hossz;) {T elem = puffer.poll (); if (elem! = null) {item [i ++] = item; System.out.println ("Elfogyasztva:" + elem); }} visszaküldendő tételek; } 

A fogyasztói szál nyomtatás nélkül folytatódik, ha a nulla érték a pufferből.

Írjuk meg a vezető kódunkat:

végrehajtóService.submit (új szál (új Producer (puffer))); végrehajtóService.submit (új szál (új fogyasztó (puffer))); 

Termelő-fogyasztó programunk végrehajtása az alábbiakhoz hasonló eredményt hoz létre:

Gyártva: Kör Gyártva: Háromszög elfogyasztva: Gyártott téglalap: Fogyasztott téglalap: Elfogyasztott téglalap: Téglalap gyártva: Szögletes Gyártva: Elfogyasztott rombusz: Szögletes Gyártva: Trapéz elfogyasztva: Rombusz elfogyasztva: Trapéz előállítva: Pentagon Gyártva: Pentagram Gyártva: Hatszög fogyasztva: Pent Pentagram előállítva: Hexagram fogyasztva: Hatszög fogyasztva: Hexagram 

5. Következtetés

Ebben az oktatóanyagban megtanultuk, hogyan kell megvalósítani a gyűrűpuffert, és feltártuk, hogyan lehet a gyártó-fogyasztó problémáját megoldani.

Szokás szerint az összes példa forráskódja elérhető a GitHubon.