streamalism.org

1. Úvod

V tomto návode prediskutujeme rôzne možnosti implementácie dátovej štruktúry LIFO bezpečnej pre vlákna.

V dátovej štruktúre LIFO sa prvky vkladajú a načítajú podľa princípu Last-In-First-Out. To znamená, že naposledy vložený prvok sa získa ako prvý.

V informatike stoh je termín používaný na označenie takejto dátovej štruktúry.

A stoh je užitočné sa vysporiadať s niektorými zaujímavými problémami, ako je vyhodnotenie výrazu, implementácia operácií vrátenia späť, atď. Pretože sa dá použiť v súbežných prostrediach vykonávania, bude pravdepodobne potrebné zaistiť jeho bezpečnosť voči vláknam.

2. Porozumenie Stohy

V zásade a Stoh musí implementovať nasledujúce metódy:

1. tam() - pridať prvok v hornej časti
2. pop () - vyzdvihnúť a odstrániť horný prvok
3. nahliadnuť () - načítať prvok bez vybratia z podložnej nádoby

Ako sme už diskutovali, predpokladajme, že chceme mať procesor na spracovanie príkazov.

V tomto systéme je zrušenie vykonaných príkazov dôležitou vlastnosťou.

Všeobecne sa všetky príkazy tlačia do zásobníka a potom je možné jednoducho implementovať operáciu vrátenia späť:

• pop () metóda na získanie posledného vykonaného príkazu
• zavolajte na Vrátenie späť() metóda na vyskočenom príkazovom objekte

3. Pochopenie bezpečnosti nití v Stohy

Ak dátová štruktúra nie je bezpečná pre vlákna, pri súčasnom prístupe k nej môžu vzniknúť podmienky pre preteky.

Stručne povedané, závodné podmienky nastávajú, keď správne spustenie kódu závisí od načasovania a postupnosti vlákien. Stáva sa to hlavne vtedy, ak dátovú štruktúru zdieľa viac ako jedno vlákno a táto štruktúra nie je navrhnutá na tento účel.

Pozrime sa na nižšie uvedenú metódu z triedy Java Collection, ArrayDeque:

public E pollFirst () {int h = hlava; E výsledok = (E) prvky [h]; // ... ďalšie účtovné operácie odstránené, pre jednoduchosť head = (h + 1) & (elements.length - 1); návratový výsledok; }

Aby sme vysvetlili možnú podmienku rasy vo vyššie uvedenom kóde, predpokladajme dve vlákna vykonávajúce tento kód, ako je uvedené v nasledujúcej postupnosti:

• Prvé vlákno vykoná tretí riadok: nastaví výsledný objekt s prvkom v indexe „hlava“
• Druhé vlákno vykoná tretí riadok: nastaví výsledný objekt s prvkom v indexe „hlava“
• Prvé vlákno vykoná piaty riadok: vynuluje index „hlava“ na ďalší prvok v podpornom poli
• Druhé vlákno vykoná piaty riadok: vynuluje index „head“ na ďalší prvok v podpornom poli

Ojoj! Teraz by obe vykonania vrátili rovnaký výsledný objekt.

Ak sa chcete vyhnúť takýmto pretekovým podmienkam, v tomto prípade by vlákno nemalo vykonávať prvý riadok, kým druhé vlákno nedokončí vynulovanie indexu „hlavy“ v piatom riadku. Inými slovami, prístup k prvku v indexe „head“ a vynulovanie indexu „head“ by sa pre vlákno malo uskutočniť atomicky.

Je zrejmé, že v tomto prípade správne vykonanie kódu závisí od načasovania vlákien, a preto nie je bezpečné pre vlákna.

4. Stohy bezpečné pre závit pomocou zámkov

V tejto časti si rozoberieme dve možné možnosti konkrétnych implementácií bezpečných pre vlákna stoh.

Obzvlášť sa budeme venovať Jave Stoh a zdobené bezpečným pre nite ArrayDeque.

Oba používajú zámky na vzájomne sa vylučujúci prístup.

4.1. Používanie Java Stoh

Java Collections má staršiu implementáciu pre bezpečné používanie vlákien Stoh, založené na Vektor čo je v podstate synchronizovaný variant ArrayList.

Samotný oficiálny dokument však navrhuje zvážiť použitie ArrayDeque. Preto sa nebudeme príliš rozpisovať.

Aj keď Java Stoh je bezpečný z hľadiska vlákien a je priamo použiteľný, má táto trieda veľké nevýhody:

• Nemá podporu pre nastavenie počiatočnej kapacity
• Pre všetky operácie používa zámky. To by mohlo poškodiť výkonnosť vykonávania s jedným vláknom.

4.2. Použitím ArrayDeque

Pomocou Deque rozhranie je najpohodlnejším prístupom k dátovým štruktúram LIFO, pretože poskytuje všetky potrebné operácie so zásobníkmi.ArrayDeque je jednou z takýchto konkrétnych implementácií.

Pretože to na operácie nepoužíva zámky, vykonali by sa vykonania s jedným vláknom dobre. Ale pre popravy s viacerými vláknami je to problematické.

Môžeme však implementovať synchronizačný dekorátor pre ArrayDeque. Aj keď to funguje podobne ako v Java Collection Framework Stoh triedy, dôležitá otázka Stoh triedy, nedostatok úvodného nastavenia kapacity, je vyriešený.

Poďme sa pozrieť na túto triedu:

verejná trieda DequeBasedSynchronizedStack {// Interný Deque, ktorý je zdobený pre synchronizáciu. súkromné ​​pole ArrayDeque dequeStore; public DequeBasedSynchronizedStack (int initialCapacity) {this.dequeStore = new ArrayDeque (initialCapacity); } public DequeBasedSynchronizedStack () {dequeStore = new ArrayDeque (); } public synchronized T pop () {return this.dequeStore.pop (); } verejné synchronizované void push (T element) {this.dequeStore.push (element); } public synchronized T peek () {return this.dequeStore.peek (); } public synchronized int size () {return this.dequeStore.size (); }}

Upozorňujeme, že naše riešenie sa neimplementuje Deque samo o sebe pre jednoduchosť, pretože obsahuje oveľa viac metód.

Guava tiež obsahuje SynchronizedDeque čo je výroba pripravená implementácia zdobeného ArrayDequeue.

5. Stohy bezpečné pre zaistenie závitov

ConcurrentLinkedDeque je bezbariérová implementácia Deque rozhranie. Táto implementácia je úplne bezpečná pre vlákna používa efektívny algoritmus bez blokovania.

Implementácie bez blokovania sú imúnne voči nasledujúcim problémom, na rozdiel od implementácií založených na zámkoch.

• Prioritná inverzia - K tomu dôjde, keď vlákno s nízkou prioritou drží zámok potrebný pre vlákno s vysokou prioritou. Môže to spôsobiť zablokovanie vlákna s vysokou prioritou
• Zablokovanie - K tomu dôjde, keď rôzne vlákna uzamknú rovnakú skupinu zdrojov v inom poradí.

Okrem toho majú implementácie bez blokovania niektoré funkcie, vďaka ktorým sú ideálne na použitie v prostredí s jedným aj viacerými vláknami.

• Pre nezdieľané dátové štruktúry a pre jednovláknový prístup, výkon by bol na úrovni ArrayDeque
• Pre zdieľané dátové štruktúry výkon sa líši podľa počtu vlákien, ktoré k nej pristupujú súčasne.

A z hľadiska použiteľnosti sa nelíši od ArrayDeque keďže obaja implementujú Deque rozhranie.

6. Záver

V tomto článku sme diskutovali o stoh dátová štruktúra a jej výhody pri navrhovaní systémov ako Command processing engine a Expression evaluators.

Analyzovali sme tiež rôzne implementácie zásobníkov v rámci kolekcií Java a diskutovali sme o ich nuanciách v oblasti výkonu a bezpečnosti vlákien.

Ako obvykle, príklady kódov nájdete na GitHub.