streamalism.org

1. Introduksjon

I denne veiledningen, Vi diskuterer ulike alternativer for trådsikre implementeringer av LIFO-datastruktur.

I LIFO-datastrukturen blir elementene satt inn og hentet i henhold til Last-In-First-Out-prinsippet. Dette betyr at det sist innsatte elementet blir hentet først.

I informatikk, stable er begrepet som brukes til å referere til slik datastruktur.

EN stable er praktisk å håndtere noen interessante problemer som uttrykksevaluering, implementering av angreoperasjoner osv. Siden det kan brukes i samtidige kjøringsmiljøer, kan det hende vi trenger å gjøre det trådsikkert.

2. Forståelse Stabler

I utgangspunktet, a Stable må implementere følgende metoder:

1. trykk() - legg til et element øverst
2. pop () - hente og fjerne toppelementet
3. kikke () - hent elementet uten å fjerne det fra den underliggende beholderen

Som diskutert tidligere, la oss anta at vi vil ha en kommandobehandlingsmotor.

I dette systemet er å angre utførte kommandoer en viktig funksjon.

Generelt skyves alle kommandoene på bunken, og deretter kan angreoperasjonen bare implementeres:

• pop () metode for å få den siste utførte kommandoen
• Ring angre () metoden på det poppede kommandoobjektet

3. Forstå trådsikkerhet i Stabler

Hvis en datastruktur ikke er trådsikker, kan den ende opp med løpsforhold når den er tilgjengelig samtidig.

Løpsforhold, i et nøtteskall, oppstår når riktig utførelse av kode avhenger av tidspunktet og sekvensen av tråder. Dette skjer hovedsakelig hvis mer enn en tråd deler datastrukturen, og denne strukturen ikke er designet for dette formålet.

La oss undersøke en metode nedenfor fra en Java Collection-klasse, ArrayDeque:

offentlig E pollFirst () {int h = hode; E resultat = (E) elementer [h]; // ... andre bokføringsoperasjoner fjernet, for enkelhets skyld head = (h + 1) & (elements.length - 1); returresultat; }

For å forklare den potensielle løpetilstanden i ovennevnte kode, la oss anta to tråder som utfører denne koden som gitt i sekvensen nedenfor:

• Første tråd utfører tredje linje: setter resultatobjektet med elementet på indeksen 'head'
• Den andre tråden utfører den tredje linjen: setter resultatobjektet med elementet på indeksen 'head'
• Første tråd utfører den femte linjen: tilbakestiller indeksen ‘head’ til neste element i backing array
• Den andre tråden utfører den femte linjen: tilbakestiller indeksen 'head' til neste element i backing array

Beklager! Nå ville begge henrettelsene returnere det samme resultatobjektet.

For å unngå slike løpsforhold, i dette tilfellet, bør en tråd ikke utføre den første linjen før den andre tråden er ferdig med å tilbakestille 'head' -indeksen på den femte linjen. Med andre ord, tilgang til elementet ved indeksen 'head' og tilbakestilling av index 'head' bør skje atomisk for en tråd.

Klart, i dette tilfellet avhenger riktig utførelse av kode av tidspunktet for tråder, og det er derfor ikke trådsikkert.

4. Trådsikre stabler ved bruk av lås

I denne delen vil vi diskutere to mulige alternativer for konkrete implementeringer av en trådsikker stable.

Spesielt dekker vi Java Stable og en trådsikker dekorert ArrayDeque.

Begge bruker Låser for gjensidig eksklusiv tilgang.

4.1. Bruke Java Stable

Java Collections har en eldre implementering for trådsikker Stable, basert på Vector som i utgangspunktet er en synkronisert variant av ArrayList.

Imidlertid foreslår det offisielle dokumentet selv å vurdere å bruke ArrayDeque. Derfor vil vi ikke komme i for mye detalj.

Selv om Java Stable er trådsikker og rett frem å bruke, er det store ulemper med denne klassen:

• Den har ikke støtte for å stille inn startkapasiteten
• Den bruker låser for alle operasjoner. Dette kan skade ytelsen for enkelttrådede henrettelser.

4.2. Ved hjelp av ArrayDeque

Bruker Deque grensesnitt er den mest praktiske tilnærmingen for LIFO-datastrukturer, da den gir alle nødvendige stabeloperasjoner.ArrayDeque er en slik konkret implementering.

Siden den ikke bruker låser for operasjonene, vil henrettelser med enkelt tråd fungere helt fint. Men for henrettelser med flere tråder er dette problematisk.

Imidlertid kan vi implementere en synkroniseringsdekorator for ArrayDeque. Selv om dette fungerer på samme måte som Java Collection Framework Stable klasse, den viktige saken av Stable klasse, mangel på innledende kapasitetsinnstilling, er løst.

La oss ta en titt på denne klassen:

offentlig klasse DequeBasedSynchronizedStack {// Intern Deque som blir dekorert for synkronisering. private ArrayDeque dequeStore; public DequeBasedSynchronizedStack (int initialCapacity) {this.dequeStore = new ArrayDeque (initialCapacity); } offentlig DequeBasedSynchronizedStack () {dequeStore = ny ArrayDeque (); } offentlig synkronisert T pop () {returner this.dequeStore.pop (); } offentlig synkronisert ugyldig trykk (T-element) {this.dequeStore.push (element); } offentlig synkronisert T-titt () {returner this.dequeStore.peek (); } offentlig synkronisert int-størrelse () {returner this.dequeStore.size (); }}

Merk at løsningen vår ikke implementeres Deque seg selv for enkelhet, ettersom den inneholder mange flere metoder.

Guava inneholder også SynchronizedDeque som er en produksjonsklar implementering av en dekorert ArrayDequeue.

5. Låsfrie trådsikre stabler

ConcurrentLinkedDeque er en låsfri implementering av Deque grensesnitt. Denne implementeringen er helt trådsikker da den bruker en effektiv låsfri algoritme.

Låsfrie implementeringer er immun mot følgende problemer, i motsetning til låsebaserte.

• Prioritert inversjon - Dette skjer når tråden med lav prioritet holder den låsen som trengs med høy prioritet. Dette kan føre til at tråden med høy prioritet blokkeres
• Låsesperre - Dette skjer når forskjellige tråder låser det samme settet med ressurser i en annen rekkefølge.

På toppen av det har låsfrie implementeringer noen funksjoner som gjør dem perfekte å bruke i både enkelt- og flertrådede miljøer.

• For ikke-delte datastrukturer og for tilgang med en tråd, vil ytelsen være på nivå med ArrayDeque
• For delte datastrukturer, ytelse varierer avhengig av antall tråder som får tilgang til den samtidig.

Og når det gjelder brukervennlighet, er det ikke annerledes enn ArrayDeque som begge implementerer Deque grensesnitt.

6. Konklusjon

I denne artikkelen har vi diskutert stable datastruktur og fordelene ved å designe systemer som Command Processing Engine og Expression Evalators.

Vi har også analysert forskjellige stakkimplementeringer i Java-samlingsrammeverket og diskutert deres ytelse og trådsikkerhetsnyanser.

Som vanlig kan kodeeksempler finnes på GitHub.