streamalism.org

1. Uvod

U ovom vodiču, razgovarat ćemo o raznim opcijama za implementaciju LIFO podataka sigurne u niti.

U strukturu podataka LIFO elementi se ubacuju i dohvaćaju prema principu Last-In-First-Out. To znači da se prvi dohvaća zadnji umetnuti element.

U računalnoj znanosti, stog je izraz koji se koristi za označavanje takve strukture podataka.

A stog je zgodan za rješavanje nekih zanimljivih problema poput procjene izraza, implementacije operacija poništavanja itd. Budući da se može koristiti u istodobnim okruženjima izvršenja, možda ćemo ga morati učiniti sigurnim za nit.

2. Razumijevanje Stogovi

U osnovi, a Stog moraju primijeniti sljedeće metode:

1. gurnuti() - dodaj element na vrh
2. pop () - dohvatiti i ukloniti gornji element
3. zaviriti () - dohvatiti element bez uklanjanja iz temeljnog spremnika

Kao što je već spomenuto, pretpostavimo da želimo mehanizam za obradu naredbi.

U ovom je sustavu poništavanje izvršenih naredbi važna značajka.

Općenito, sve se naredbe guraju u stog i tada se operacija poništavanja može jednostavno implementirati:

• pop () metoda za dobivanje posljednje izvršene naredbe
• nazovite poništi () metoda na iskočenom naredbenom objektu

3. Razumijevanje sigurnosti navoja u Stogovi

Ako struktura podataka nije zaštićena nitima, ako joj se istovremeno pristupa, možda će na kraju imati uvjete utrke.

Ukratko, uvjeti utrke nastaju kada ispravno izvršavanje koda ovisi o vremenu i slijedu niti. To se događa uglavnom ako više od jedne niti dijeli strukturu podataka, a ta struktura nije dizajnirana u tu svrhu.

Ispitajmo metodu u nastavku iz klase Java Collection, ArrayDeque:

javna E anketaFirst () {int h = head; E rezultat = (E) elementi [h]; // ... uklonjene su ostale knjigovodstvene radnje, radi jednostavnosti head = (h + 1) & (elements.length - 1); povratni rezultat; }

Da bismo objasnili potencijalno stanje utrke u gornjem kodu, pretpostavimo dvije niti koje izvršavaju ovaj kod kako je dano u slijedu dolje:

• Prva nit izvršava treći redak: postavlja rezultat objekt s elementom na indeksu ‘head’
• Druga nit izvršava treći redak: postavlja rezultat objekt s elementom na indeksu ‘glava’
• Prva nit izvršava peti redak: resetira indeks ‘head’ na sljedeći element u pozadinskom nizu
• Druga nit izvršava peti redak: resetira indeks ‘head’ na sljedeći element u pozadinskom nizu

Ups! Sad bi obje izvedbe vratile isti objekt rezultata.

Da bi se izbjegli takvi uvjeti utrke, u ovom slučaju nit ne bi trebao izvršavati prvu liniju dok druga nit ne završi resetiranje indeksa ‘head’ na petoj liniji. Drugim riječima, pristup elementu u indeksu ‘glava’ i resetiranje indeksa ‘glava’ trebali bi se dogoditi atomski za nit.

Jasno je da u ovom slučaju ispravno izvršavanje koda ovisi o vremenu niti i stoga nije sigurno.

4. Sklopovi zaštićeni navojem pomoću brava

U ovom ćemo odjeljku razgovarati o dvije moguće opcije za konkretne implementacije sigurnih niti stog.

Konkretno, pokrivat ćemo Javu Stog i ukrašen bez konca ArrayDeque.

Obje koriste brave za međusobno isključivi pristup.

4.1. Korištenje Jave Stog

Java Collections ima naslijeđenu implementaciju za zaštitu niti Stog, na temelju Vektor što je u osnovi sinkronizirana varijanta ArrayList.

Međutim, službeni dokument sam predlaže razmatranje upotrebe ArrayDeque. Stoga nećemo ulaziti u previše detalja.

Iako je Java Stog je siguran za nit i jednostavan za upotrebu, glavni su nedostaci ove klase:

• Nema podršku za postavljanje početnog kapaciteta
• Za sve operacije koristi brave. To bi moglo naštetiti izvedbi izvršavanja s jednim navojem.

4.2. Koristeći ArrayDeque

Koristiti Deque Sučelje je najprikladniji pristup za LIFO podatkovne strukture jer pruža sve potrebne operacije stoga.ArrayDeque je jedna od takvih konkretnih provedbi.

Budući da se za operacije ne koriste brave, izvršavanja s jednim navojem funkcionirala bi sasvim u redu. Ali za izvršenja s više niti, to je problematično.

Međutim, možemo implementirati uređivač sinkronizacije za ArrayDeque. Iako se ovo izvodi slično kao Java Collection Framework Stog razreda, važno pitanje Stog klase, riješen je nedostatak početnog postavljanja kapaciteta.

Pogledajmo ovaj razred:

javna klasa DequeBasedSynchronizedStack {// Interna Deque koja se ukrašava za sinkronizaciju. privatni ArrayDeque dequeStore; javni DequeBasedSynchronizedStack (int početni kapacitet) {this.dequeStore = novi ArrayDeque (početni kapacitet); } javni DequeBasedSynchronizedStack () {dequeStore = novi ArrayDeque (); } javni sinkronizirani T pop () {return this.dequeStore.pop (); } javni sinkronizirani void push (element T) {this.dequeStore.push (element); } javni sinkronizirani T peek () {return this.dequeStore.peek (); } javna sinkronizirana veličina int () {return this.dequeStore.size (); }}

Imajte na umu da se naše rješenje ne primjenjuje Deque za jednostavnost, jer sadrži mnogo više metoda.

Također, Guava sadrži SynchronizedDeque što je produkcijski spremna izvedba uređenog ArrayDequeue.

5. Sklopovi bez navoja bez zaključavanja

ConcurrentLinkedDeque je implementacija sustava bez zaključavanja Deque sučelje. Ova je implementacija potpuno zaštićena od niti jer koristi učinkovit algoritam bez zaključavanja.

Implementacije bez zaključavanja imune su na sljedeće probleme, za razliku od onih temeljenih na zaključavanju.

• Inverzija prioriteta - To se događa kada nit niskog prioriteta drži bravu potrebnu niti visokog prioriteta. To bi moglo dovesti do blokiranja niti visokog prioriteta
• Zastoji - To se događa kada različite niti zaključavaju isti skup resursa u drugom redoslijedu.

Povrh toga, implementacije bez zaključavanja imaju neke značajke zbog kojih su savršene za upotrebu u okruženjima s jednim ili više navoja.

• Za nepodijeljene strukture podataka i za jednonitni pristup, izvedba bi bila jednaka ArrayDeque
• Za zajedničke strukture podataka, izvedba varira ovisno o broju niti koje mu istovremeno pristupaju.

A što se tiče iskoristivosti, to se ne razlikuje od ArrayDeque jer oba primjenjuju Deque sučelje.

6. Zaključak

U ovom smo članku razgovarali o stog struktura podataka i njegove prednosti u dizajniranju sustava kao što su Command Process Engine i Expression evaluatori.

Također, analizirali smo različite implementacije steka u okviru Java kolekcija i raspravljali o njihovim izvedbama i nijansama sigurnosti niti.

Kao i obično, primjeri koda mogu se naći na GitHubu.