streamalism.org

1. Inleiding

In deze tutorial we bespreken verschillende opties voor Thread-safe LIFO-datastructuurimplementaties.

In de LIFO-datastructuur worden elementen ingevoegd en opgehaald volgens het Last-In-First-Out principe. Dit betekent dat het laatst ingevoegde element als eerste wordt opgehaald.

In de informatica, stapel is de term die wordt gebruikt om naar een dergelijke gegevensstructuur te verwijzen.

EEN stapel is handig om een ​​aantal interessante problemen op te lossen, zoals evaluatie van expressies, het implementeren van ongedaan maken van bewerkingen, enz. Aangezien het kan worden gebruikt in gelijktijdige uitvoeringsomgevingen, moeten we het misschien thread-safe maken.

2. Begrip Stapels

Kortom, een Stapel moet de volgende methoden implementeren:

1. Duwen() - voeg bovenaan een element toe
2. knal() - haal en verwijder het bovenste element
3. kijkje() - haal het element op zonder het uit de onderliggende container te halen

Laten we, zoals eerder besproken, aannemen dat we een opdrachtverwerkingsengine willen.

In dit systeem is het ongedaan maken van uitgevoerde opdrachten een belangrijke functie.

Over het algemeen worden alle opdrachten op de stapel geduwd en vervolgens kan de bewerking ongedaan worden gemaakt eenvoudig worden geïmplementeerd:

• knal() methode om de laatst uitgevoerde opdracht op te halen
• bel de ongedaan maken () methode op het gepopte opdrachtobject

3. Inzicht in draadveiligheid in Stapels

Als een datastructuur niet thread-safe is, kan het bij gelijktijdige toegang tot race conditions leiden.

Race conditions, in een notendop, doen zich voor wanneer de juiste uitvoering van code afhangt van de timing en volgorde van threads. Dit gebeurt voornamelijk als meer dan één thread de datastructuur deelt en deze structuur niet voor dit doel is ontworpen.

Laten we een methode hieronder bekijken uit een Java Collection-klasse, ArrayDeque:

openbare E pollFirst () {int h = head; E resultaat = (E) elementen [h]; // ... andere boekhoudkundige bewerkingen verwijderd, voor de eenvoud head = (h + 1) & (elements.length - 1); resultaat teruggeven; }

Om de mogelijke racevoorwaarde in de bovenstaande code uit te leggen, gaan we ervan uit dat twee threads deze code uitvoeren, zoals aangegeven in de onderstaande volgorde:

• Eerste thread voert de derde regel uit: zet het resultaatobject met het element op de index ‘head '
• De tweede thread voert de derde regel uit: zet het resultaatobject met het element op de index ‘head '
• De eerste thread voert de vijfde regel uit: stelt de index ‘head 'opnieuw in op het volgende element in de backing-array
• De tweede thread voert de vijfde regel uit: reset de index ‘head 'naar het volgende element in de backing-array

Oeps! Nu zouden beide uitvoeringen hetzelfde resultaatobject retourneren.

Om dergelijke race-omstandigheden te vermijden, moet een thread in dit geval de eerste regel niet uitvoeren totdat de andere thread klaar is met het resetten van de ‘head'-index op de vijfde regel. Met andere woorden, toegang tot het element bij de index ‘head 'en het resetten van de index‘ head' zou atomair moeten gebeuren voor een thread.

Het is duidelijk dat in dit geval de juiste uitvoering van code afhangt van de timing van threads en daarom niet thread-safe is.

4. Draadveilige stapels met sloten

In deze sectie bespreken we twee mogelijke opties voor concrete implementaties van een thread-safe stapel.

In het bijzonder behandelen we de Java Stapel en een draadkluis versierd ArrayDeque.

Beiden gebruiken sloten voor wederzijds exclusieve toegang.

4.1. Met behulp van de Java Stapel

Java Collections heeft een oudere implementatie voor thread-safe Stapel, gebaseerd op Vector wat in feite een gesynchroniseerde variant is van ArrayList.

Het officiële document stelt echter zelf voor om te overwegen om ArrayDeque. Daarom zullen we niet teveel in detail treden.

Hoewel de Java Stapel schroefdraadveilig en eenvoudig te gebruiken is, heeft deze klasse grote nadelen:

• Het heeft geen ondersteuning voor het instellen van de initiële capaciteit
• Het gebruikt sloten voor alle bewerkingen. Dit kan de prestaties nadelig beïnvloeden voor uitvoeringen met één thread.

4.2. Gebruik makend van ArrayDeque

De ... gebruiken Deque interface is de handigste benadering voor LIFO-datastructuren omdat het alle benodigde stackbewerkingen biedt.ArrayDeque is zo'n concrete implementatie.

Omdat het geen vergrendelingen gebruikt voor de bewerkingen, zouden uitvoeringen met één thread prima werken. Maar voor uitvoeringen met meerdere threads is dit problematisch.

We kunnen echter een synchronisatie-decorateur implementeren voor ArrayDeque. Hoewel dit op dezelfde manier presteert als dat van Java Collection Framework Stapel klasse, de belangrijke kwestie van Stapel klasse, gebrek aan initiële capaciteitsinstelling, is opgelost.

Laten we deze les eens bekijken:

openbare klasse DequeBasedSynchronizedStack {// Interne Deque die wordt ingericht voor synchronisatie. privé ArrayDeque dequeStore; openbare DequeBasedSynchronizedStack (int initialCapacity) {this.dequeStore = nieuwe ArrayDeque (initialCapacity); } openbare DequeBasedSynchronizedStack () {dequeStore = nieuwe ArrayDeque (); } openbare gesynchroniseerde T-pop () {retourneer this.dequeStore.pop (); } openbare gesynchroniseerde ongeldige push (T-element) {this.dequeStore.push (element); } openbare gesynchroniseerde T peek () {retourneer this.dequeStore.peek (); } public synchronized int size () {retourneer this.dequeStore.size (); }}

Merk op dat onze oplossing niet implementeert Deque zichzelf voor de eenvoud, omdat het veel meer methoden bevat.

Guava bevat ook SynchronizedDeque wat een productieklare uitvoering is van een gedecoreerd ArrayDequeue.

5. Vergrendelingsvrije draadveilige stapels

ConcurrentLinkedDeque is een lock-free implementatie van Deque koppel. Deze implementatie is volledig thread-safe omdat het een efficiënt vergrendelingsvrij algoritme gebruikt.

Lock-free implementaties zijn immuun voor de volgende problemen, in tegenstelling tot lock-based.

• Prioriteitsinversie - Dit gebeurt wanneer de draad met lage prioriteit de vergrendeling bevat die nodig is voor een draad met hoge prioriteit. Hierdoor kan de thread met hoge prioriteit worden geblokkeerd
• Deadlocks - Dit gebeurt wanneer verschillende threads dezelfde set bronnen in een andere volgorde vergrendelen.

Bovendien hebben Lock-free-implementaties een aantal functies waardoor ze perfect te gebruiken zijn in zowel single- als multi-threaded omgevingen.

• Voor niet-gedeelde datastructuren en voor single-threaded toegang, de prestaties zouden vergelijkbaar zijn met ArrayDeque
• Voor gedeelde datastructuren, prestaties varieert afhankelijk van het aantal threads dat er tegelijkertijd toegang toe heeft.

En in termen van bruikbaarheid is het niet anders dan ArrayDeque aangezien beide het Deque koppel.

6. Conclusie

In dit artikel hebben we de stapel datastructuur en de voordelen ervan bij het ontwerpen van systemen zoals Command Processing Engine en Expression Evaluators.

We hebben ook verschillende stackimplementaties in het Java-verzamelingsraamwerk geanalyseerd en hun prestaties en veiligheidsnuances voor threads besproken.

Zoals gewoonlijk zijn codevoorbeelden te vinden op GitHub.