Trådsikker implementering af LIFO-datastruktur

1. Introduktion

I denne vejledning Vi diskuterer forskellige muligheder for trådsikker implementering af LIFO-datastruktur.

I LIFO-datastrukturen indsættes og hentes elementer i henhold til Last-In-First-Out-princippet. Dette betyder, at det sidst indsatte element hentes først.

I datalogi, stak er det udtryk, der bruges til at henvise til sådan datastruktur.

EN stak er praktisk at håndtere nogle interessante problemer som ekspressionsevaluering, implementering af fortrydelsesoperationer osv. Da det kan bruges i samtidige eksekveringsmiljøer, er vi muligvis nødt til at gøre det trådsikkert.

2. Forståelse Stakke

Dybest set er en Stak skal implementere følgende metoder:

skubbe() - tilføj et element øverst
pop () - hent og fjern det øverste element
kigge () - hent elementet uden at fjerne det fra den underliggende container

Som diskuteret før, lad os antage, at vi vil have en kommandobehandlingsmotor.

I dette system er fortrydelse af eksekverede kommandoer en vigtig funktion.

Generelt skubbes alle kommandoer på stakken, og derefter kan fortrydelse simpelthen implementeres:

pop () metode til at få den sidst udførte kommando
ring til fortryde () metode på det poppede kommandoobjekt

3. Forståelse af trådsikkerhed i Stakke

Hvis en datastruktur ikke er trådsikker, kan den ende med at have løbsbetingelser, når den åbnes samtidigt.

Race betingelser, i en nøddeskal, opstår, når den korrekte udførelse af kode afhænger af timingen og rækkefølgen af tråde. Dette sker primært, hvis mere end en tråd deler datastrukturen, og denne struktur ikke er designet til dette formål.

Lad os undersøge nedenstående metode fra en Java Collection-klasse, ArrayDeque:

offentlig E pollFirst () {int h = hoved; E resultat = (E) elementer [h]; // ... andre bogføringsoperationer er fjernet, for enkelheds skyld head = (h + 1) & (elements.length - 1); returresultat }

For at forklare den potentielle race-tilstand i ovenstående kode, lad os antage to tråde, der udfører denne kode som angivet i nedenstående rækkefølge:

Første tråd udfører tredje linje: indstiller resultatobjektet med elementet ved indekset 'hoved'
Den anden tråd udfører den tredje linje: indstiller resultatobjektet med elementet ved indekset 'hoved'
Første tråd udfører den femte linje: nulstiller indekset 'head' til det næste element i backing-arrayet
Den anden tråd udfører den femte linje: nulstiller indekset 'head' til det næste element i backing-arrayet

Ups! Nu vil begge henrettelser returnere det samme resultatobjekt.

For at undgå sådanne race betingelser, i dette tilfælde, bør en tråd ikke udføre den første linje, før den anden tråd er færdig med at nulstille 'head' indekset på den femte linje. Med andre ord skal adgang til elementet ved indekset 'hoved' og nulstilling af indekset 'hoved' ske atomisk for en tråd.

Det er klart, at i dette tilfælde afhænger korrekt udførelse af kode af timingen af tråde, og derfor er den ikke trådsikker.

4. Trådsikre stakke ved hjælp af låse

I dette afsnit vil vi diskutere to mulige muligheder for konkrete implementeringer af en trådsikker stak.

Især dækker vi Java Stak og en tråd-sikker dekoreret ArrayDeque.

Begge bruger Låse til gensidig eksklusiv adgang.

4.1. Brug af Java Stak

Java Collections har en ældre implementering for trådsikker Stak, baseret på Vektor som dybest set er en synkroniseret variant af ArrayList.

Imidlertid foreslår det officielle dokument selv at overveje at bruge ArrayDeque. Derfor kommer vi ikke i detaljer.

Selvom Java Stak er trådsikker og ligefrem at bruge, er der store ulemper ved denne klasse:

Det understøtter ikke indstilling af startkapaciteten
Det bruger låse til alle operationer. Dette kan skade ydeevnen for henrettelser med en enkelt gevind.

4.2. Ved brug af ArrayDeque

Bruger Deque interface er den mest bekvemme tilgang til LIFO-datastrukturer, da den giver alle de nødvendige stakoperationer.ArrayDeque er en sådan konkret implementering.

Da det ikke bruger låse til operationerne, ville en-threaded henrettelser fungere fint. Men for henrettelser med flere tråde er dette problematisk.

Vi kan dog implementere en synkroniseringsdekorator til ArrayDeque. Selvom dette fungerer på samme måde som Java Collection Framework Stak klasse, det vigtige spørgsmål om Stak klasse, mangel på indledende kapacitetsindstilling, er løst.

Lad os se på denne klasse:

offentlig klasse DequeBasedSynchronizedStack {// Intern Deque, der bliver dekoreret til synkronisering. private ArrayDeque dequeStore; offentlig DequeBasedSynchronizedStack (int initialCapacity) {this.dequeStore = ny ArrayDeque (initialCapacity); } offentlig DequeBasedSynchronizedStack () {dequeStore = ny ArrayDeque (); } offentlig synkroniseret T pop () {returner this.dequeStore.pop (); } offentligt synkroniseret ugyldigt skub (T-element) {this.dequeStore.push (element); } offentlig synkroniseret T peek () {returner this.dequeStore.peek (); } offentlig synkroniseret int-størrelse () {returner this.dequeStore.size (); }}

Bemærk, at vores løsning ikke implementeres Deque sig selv for enkelhed, da det indeholder mange flere metoder.

Guava indeholder også SynchronizedDeque som er en produktionsklar implementering af en dekoreret ArrayDequeue.

5. Låsfri trådsikker stakke

ConcurrentLinkedDeque er en låsefri implementering af Deque interface. Denne implementering er fuldstændig trådsikker da det bruger en effektiv låsefri algoritme.

Låsefri implementeringer er immune over for følgende problemer, i modsætning til låsebaserede.

Prioriteret inversion - Dette sker, når tråden med lav prioritet holder den lås, som en tråd med høj prioritet har brug for. Dette kan få den højt prioriterede tråd til at blokere
Fastlåsning - Dette sker, når forskellige tråde låser det samme sæt ressourcer i en anden rækkefølge.

Derudover har låsfrie implementeringer nogle funktioner, der gør dem perfekte til brug i både enkelt- og flertrådede miljøer.

Til ikke-delte datastrukturer og til adgang med en tråd, ville ydeevnen være på niveau med ArrayDeque
For delte datastrukturer, ydeevne varierer alt efter antallet af tråde, der får adgang til det samtidigt.

Og med hensyn til anvendelighed er det ikke anderledes end ArrayDeque som begge implementerer Deque interface.

6. Konklusion

I denne artikel har vi diskuteret stak datastruktur og dens fordele ved design af systemer som Command Processing Engine og Expression Evaluators.

Vi har også analyseret forskellige stakimplementeringer i rammerne for Java-samlinger og diskuteret deres præstationer og trådsikkerhedsnuancer.

Som sædvanligt kan kodeeksempler findes på GitHub.

streamalism.org