streamalism.org

1. Bemutatkozás

Ebben az oktatóanyagban megvitatjuk a Thread-safe LIFO Data struktúra megvalósításának különféle lehetőségeit.

A LIFO adatstruktúrában az elemeket a Last-In-First-Out elv szerint illesztik be és kapják le. Ez azt jelenti, hogy az utoljára beillesztett elemet kapják le először.

A számítástechnikában Kazal az ilyen adatszerkezet kifejezésére használt kifejezés.

A Kazal hasznos olyan érdekes problémák kezelésében, mint a kifejezés kiértékelése, a visszavonási műveletek végrehajtása stb. Mivel párhuzamos végrehajtási környezetekben használható, előfordulhat, hogy szálbiztonságossá kell tennünk.

2. Megértés Verem

Alapvetően a Kazal a következő módszereket kell végrehajtania:

1. nyom() - adjon hozzá egy elemet a tetején
2. pop() - hozza le és távolítsa el a felső elemet
3. kandikál() - lehívja az elemet anélkül, hogy eltávolítaná az alatta lévő tárolóból

Amint azt korábban tárgyaltuk, tegyük fel, hogy parancsfeldolgozó motort akarunk.

Ebben a rendszerben a végrehajtott parancsok visszavonása fontos jellemző.

Általánosságban elmondható, hogy az összes parancs a veremre tolódik, majd a visszavonási művelet egyszerűen végrehajtható:

• pop() metódus az utoljára végrehajtott parancs megszerzéséhez
• hívja a visszavonás () metódus a felbukkanó parancsobjektumon

3. A szálbiztonság megértése Verem

Ha egy adatstruktúra nem szálbiztos, akkor egyidejű hozzáférés esetén versenykörülmények lehetnek.

A versenyfeltételek dióhéjban akkor fordulnak elő, amikor a kód helyes végrehajtása a szálak időzítésétől és sorrendjétől függ. Ez főleg akkor történik, ha egynél több szál osztja meg az adatstruktúrát, és ezt a struktúrát nem erre a célra tervezték.

Vizsgáljuk meg az alábbi módszert egy Java Collection osztályból, ArrayDeque:

nyilvános E pollFirst () {int h = fej; E eredmény = (E) elemek [h]; // ... egyéb könyvelési műveletek eltávolítva, az egyszerűség kedvéért head = (h + 1) & (elements.length - 1); visszatérési eredmény; }

A potenciális versenyfeltételek magyarázatához a fenti kódban tegyük fel, hogy két szál hajtja végre ezt a kódot az alábbi sorrendben megadottak szerint:

• Az első szál a harmadik sort hajtja végre: az eredményobjektumot a „head” indexben lévő elemmel állítja be
• A második szál a harmadik sort hajtja végre: az eredményobjektumot a „head” indexben lévő elemmel állítja be
• Az első szál végrehajtja az ötödik sort: visszaállítja az index „fejét” a háttér tömb következő elemére
• A második szál végrehajtja az ötödik sort: visszaállítja az index „head” elemet a háttér tömb következő elemére

Hoppá! Most mindkét végrehajtás ugyanazt az eredményobjektumot adja vissza.

Az ilyen versenykörülmények elkerülése érdekében ebben az esetben egy szálnak nem szabad végrehajtania az első sort, amíg a másik szál befejezi a „head” index visszaállítását az ötödik sornál. Más szavakkal, az index „head” eleméhez való hozzáférésnek és az „head” index visszaállításának atomszerűen kell történnie egy szál esetében.

Nyilvánvaló, hogy ebben az esetben a kód helyes végrehajtása a szálak időzítésétől függ, ezért ez nem biztonságos a szálak számára.

4. Menetbiztos halmok zárak használatával

Ebben a részben a szálbiztonság konkrét megvalósításának két lehetséges lehetőségét tárgyaljuk Kazal.

Különösen kitérünk a Java-ra Kazal és szálbiztosan díszített ArrayDeque.

Mindkettő a zárakat kölcsönösen kizárja.

4.1. A Java használata Kazal

A Java Gyűjteményeknek van egy korábbi szálbiztonsági megvalósítása Kazal, alapján Vektor amely alapvetően a szinkronizált változata Tömb lista.

Maga a hivatalos doki azonban javasolja a felhasználás megfontolását ArrayDeque. Ezért nem fogunk túlságosan részletezni.

Bár a Java Kazal menetbiztos és egyenesen használható, ennek az osztálynak vannak főbb hátrányai:

• Nem támogatja a kezdeti kapacitás beállítását
• Az összes művelethez zárakat használ. Ez árthat az egyszálas végrehajtások teljesítményének.

4.2. Használata ArrayDeque

Használni a Deque Az interfész a legkényelmesebb megközelítés a LIFO adatstruktúrák számára, mivel biztosítja az összes szükséges veremműveletet.ArrayDeque egy ilyen konkrét megvalósítás.

Mivel a műveletekhez nem használ zárakat, az egyszálú végrehajtások nagyon jól működnek. De a többszálú kivégzéseknél ez problematikus.

Szinkronizáló dekorátort azonban megvalósíthatunk a ArrayDeque. Bár ez hasonlóan működik, mint a Java Collection Framework Kazal osztály, a fontos kérdés Kazal osztály, a kezdeti kapacitásbeállítás hiánya megoldott.

Vessünk egy pillantást erre az osztályra:

public class DequeBasedSynchronizedStack {// belső Deque, amelyet a szinkronizáláshoz díszítenek. magán ArrayDeque dequeStore; public DequeBasedSynchronizedStack (int initialCapacity) {this.dequeStore = new ArrayDeque (kezdeti kapacitás); } public DequeBasedSynchronizedStack () {dequeStore = new ArrayDeque (); } nyilvános szinkronizált T pop () {return this.dequeStore.pop (); } nyilvános szinkronizált void push (T elem) {this.dequeStore.push (elem); } nyilvános szinkronizált T peek () {return this.dequeStore.peek (); } public synchronized int size () {return this.dequeStore.size (); }}

Ne feledje, hogy megoldásunk nem valósul meg Deque maga az egyszerűség kedvéért, mivel sokkal több módszert tartalmaz.

Továbbá, Guava tartalmaz SynchronizedDeque amely a díszítés gyártásra kész megvalósítása ArrayDequeue.

5. Zármentes szálbiztos verem

ConcurrentLinkedDeque zár nélküli megvalósítása Deque felület. Ez a megvalósítás teljesen menetes mivel hatékony zármentes algoritmust használ.

A zár nélküli megvalósítások immunisak a következő problémákkal szemben, ellentétben a zár alapúakkal.

• Prioritás inverzió - Ez akkor fordul elő, amikor az alacsony prioritású szál tartja a magas prioritású szál számára szükséges zárat. Ez a magas prioritású szál blokkolását okozhatja
• Holtpontok - Ez akkor fordul elő, amikor a különböző szálak ugyanazt az erőforráskészletet más sorrendben zárolják.

Ráadásul a zár nélküli megvalósításoknak vannak olyan funkcióik, amelyek tökéletesen használhatók mind egy-, mind többszálas környezetben.

• Nem megosztott adatstruktúrákhoz és egyszálú hozzáférés, a teljesítmény egyenlő lenne ArrayDeque
• Megosztott adatstruktúrák esetén a teljesítmény az egyidejűleg hozzáférő szálak számától függ.

A használhatóság szempontjából pedig nem más, mint ArrayDeque mivel mindkettő megvalósítja a Deque felület.

6. Következtetés

Ebben a cikkben megvitattuk a Kazal az adatstruktúra és annak előnyei olyan rendszerek tervezésében, mint a Command feldolgozó motor és az Expression kiértékelők.

Elemeztük a Java gyűjtemény keretrendszerének különféle megvalósításait, és megvitattuk azok teljesítményét és szálbiztonsági árnyalatait.

Szokás szerint kódpéldák találhatók a GitHubon.