streamalism.org

1. Introduktion

I denne vejledning lærer vi, hvad ikke-blokerende datastrukturer er, og hvorfor de er et vigtigt alternativ til låsebaserede samtidige datastrukturer.

Først går vi over nogle vilkår som forhindringsfri, låsefriog ventefri.

For det andet ser vi på de grundlæggende byggesten i ikke-blokerende algoritmer som CAS (sammenligne-og-bytte).

For det tredje ser vi på implementeringen af ​​en låsfri kø i Java, og endelig beskriver vi en tilgang til, hvordan man opnår Vent-frihed.

2. Lås mod sult

Lad os først se på forskellen mellem en blokeret og en sultende tråd.

På ovenstående billede erhverver tråd 2 en lås på datastrukturen. Når tråd 1 også forsøger at erhverve en lås, skal den vente, indtil tråd 2 frigør låsen; det fortsætter ikke, før det kan få låsen. Hvis vi suspenderer tråd 2, mens den holder låsen, bliver tråd 1 nødt til at vente for evigt.

Det næste billede illustrerer trådsult:

Her får tråd 2 adgang til datastrukturen, men får ikke en lås. Tråd 1 forsøger at få adgang til datastrukturen på samme tid, registrerer den samtidige adgang og vender straks tilbage og informerer tråden om, at den ikke kunne afslutte (rød) operationen. Tråd 1 prøver derefter igen, indtil det lykkes at fuldføre handlingen (grøn).

Fordelen ved denne tilgang er, at vi ikke har brug for en lås. Hvad der dog kan ske er, at hvis tråd 2 (eller andre tråde) får adgang til datastrukturen med høj frekvens, så har tråd 1 behov for et stort antal forsøg, indtil den endelig lykkes. Vi kalder dette sult.

Senere får vi se, hvordan sammenligne-og-bytte operation opnår ikke-blokerende adgang.

3. Typer af ikke-blokerende datastrukturer

Vi kan skelne mellem tre niveauer af ikke-blokerende datastrukturer.

3.1. Hindringsfri

Hindring-frihed er den svageste form for en ikke-blokerende datastruktur. Her kræver vi kun, at en tråd garanteres at fortsætte, hvis alle andre tråde er suspenderet.

Mere præcist vil en tråd ikke fortsætte med at sulte, hvis alle andre tråde er suspenderet. Dette adskiller sig fra at bruge låse i den forstand, at hvis tråden ventede på en lås, og en tråd, der holder låsen, er suspenderet, ville ventetråden vente for evigt.

3.2. Låsefri

En datastruktur giver låsefrihed, hvis mindst én tråd til enhver tid kan fortsætte. Alle andre tråde kan sulte. Forskellen til hindring-frihed er, at der er mindst en tråd, der ikke sulter, selvom ingen tråde er ophængt.

3.3. Vent-fri

En datastruktur er ventefri, hvis den er låsefri, og hver tråd garanteres at fortsætte efter et endeligt antal trin, dvs. trådene sulter ikke efter et "urimeligt stort" antal trin.

3.4. Resumé

Lad os sammenfatte disse definitioner i grafisk repræsentation:

Den første del af billedet viser forhindringsfrihed, da tråd 1 (overtråd) kan fortsætte (grøn pil), så snart vi suspenderer de andre tråde (nederst i gul).

Den midterste del viser låsefrihed. I det mindste kan tråd 1 udvikle sig, mens andre måske sulter (rød pil).

Den sidste del viser ventefrihed. Her garanterer vi, at tråd 1 kan fortsætte (grøn pil) efter en bestemt periode med sult (røde pile).

4. Ikke-blokerende primitiver

I dette afsnit vil vi se på tre grundlæggende operationer, der hjælper os med at opbygge låsefri operationer på datastrukturer.

4.1. Sammenlign og bytt

En af de grundlæggende handlinger, der bruges til at undgå låsning, er sammenligne-og-bytte (CAS) drift.

Idéen med sammenligning og udskiftning er, at en variabel kun opdateres, hvis den stadig har den samme værdi som på det tidspunkt, hvor vi havde hentet værdien af ​​variablen fra hovedhukommelsen. CAS er en atomoperation, hvilket betyder, at hentning og opdatering sammen er en enkelt operation:

Her henter begge tråde værdien 3 fra hovedhukommelsen. Tråd 2 lykkes (grøn) og opdaterer variablen til 8. Da den første CAS ved tråd 1 forventer, at værdien stadig er 3, mislykkes CAS (rød). Derfor henter tråd 1 værdien igen, og den anden CAS lykkes.

Det vigtige her er, at CAS ikke erhverver en lås på datastrukturen, men vender tilbage rigtigt hvis opdateringen var vellykket, vender den ellers tilbage falsk.

Følgende kodestykke skitserer, hvordan CAS fungerer:

flygtig int-værdi; boolsk cas (int forventet værdi, int ny værdi) {hvis (værdi == forventet værdi) {værdi = ny værdi; returner sandt; } returner falsk; }

Vi opdaterer kun værdien med den nye værdi, hvis den stadig har den forventede værdi, ellers returnerer den falsk. Følgende kodestykke viser, hvordan CAS kan kaldes:

ugyldig testCas () {int v = værdi; int x = v + 1; mens (! cas (v, x)) {v = værdi; x = v + 1; }}

Vi forsøger at opdatere vores værdi, indtil CAS-operationen lykkes, dvs. returnerer rigtigt.

Det er dog muligt, at en tråd sidder fast i sult. Det kan ske, hvis andre tråde udfører en CAS på den samme variabel på samme tid, så operationen vil aldrig lykkes for en bestemt tråd (eller det vil tage urimelig lang tid at få succes). Stadig, hvis sammenligne-og-bytte mislykkes, vi ved, at en anden tråd er lykkedes, og dermed sikrer vi også globale fremskridt som krævet for låsefrihed.

Det er vigtigt at bemærke, at hardwaren skal understøtte sammenligne-og-bytte, for at gøre det til en virkelig atomoperation uden brug af låsning.

Java giver en implementering af sammenligne-og-bytte i klassen sun.misc. usikker. I de fleste tilfælde bør vi dog ikke bruge denne klasse direkte, men Atomic-variabler i stedet.

Desuden, sammenligne-og-bytte forhindrer ikke A-B-A-problemet. Vi ser på det i det følgende afsnit.

4.2. Load-Link / Store-betinget

Et alternativ til sammenligne-og-bytte er load-link / butik-betinget. Lad os først besøge igen sammenligne-og-bytte. Som vi har set før, opdaterer CAS kun værdien, hvis værdien i hovedhukommelsen stadig er den værdi, vi forventer, at den er.

Imidlertid lykkes CAS også, hvis værdien var ændret, og i mellemtiden er ændret tilbage til sin tidligere værdi.

Billedet nedenfor illustrerer denne situation:

Både tråd 1 og tråd 2 læser værdien af ​​variablen, som er 3. Derefter udfører tråd 2 en CAS, der lykkes at sætte variablen til 8. Derefter udfører tråd 2 en CAS for at sætte variablen tilbage til 3, hvilket også lykkes. Endelig udfører tråd 1 en CAS, der forventer værdien 3 og også lykkes, selvom værdien af ​​vores variabel blev ændret to gange imellem.

Dette kaldes A-B-A-problemet. Denne adfærd er naturligvis ikke et problem afhængigt af brugssagen. Det er dog måske ikke ønsket for andre. Java giver en implementering af load-link / butik-betinget med AtomicStampedReference klasse.

4.3. Hent og tilføj

Et andet alternativ er hent og tilføj. Denne operation forøger variablen i hovedhukommelsen med en given værdi. Igen er det vigtige punkt, at operationen sker atomisk, hvilket betyder, at ingen anden tråd kan blande sig.

Java giver en implementering af hent og tilføj i dets atomklasser. Eksempler er AtomicInteger.incrementAndGet (), som øger værdien og returnerer den nye værdi; og AtomicInteger.getAndIncrement (), som returnerer den gamle værdi og derefter forøger værdien.

5. Adgang til en sammenkædet kø fra flere tråde

For bedre at forstå problemet med to (eller flere) tråde, der får adgang til en kø samtidigt, lad os se på en sammenkædet kø og to tråde, der forsøger at tilføje et element samtidigt.

Køen, vi vil se på, er en dobbelt forbundet FIFO-kø, hvor vi tilføjer nye elementer efter det sidste element (L) og variablen hale peger på det sidste element:

For at tilføje et nyt element skal trådene udføre tre trin: 1) Opret de nye elementer (N og M), med markøren til det næste element indstillet til nul; 2) har henvisningen til det forrige element punkt til L og henvisningen til det næste element af L punkt til henholdsvis N (M). 3) Har hale peg på henholdsvis N (M):

Hvad kan gå galt, hvis de to tråde udfører disse trin samtidigt? Hvis trinnene i ovenstående billede udføres i rækkefølgen ABCD eller ACBD, L samt hale, vil pege på M. N forbliver afbrudt fra køen.

Hvis trinnene udføres i rækkefølgen ACDB, hale vil pege på N, mens L vil pege på M, hvilket vil medføre en inkonsekvens i køen:

Selvfølgelig er en måde at løse dette problem på at have en tråd til at erhverve en lås i køen. Den løsning, vi ser på i det følgende kapitel, løser problemet ved hjælp af en låsefri operation ved hjælp af den CAS-operation, vi har set tidligere.

6. En ikke-blokerende kø i Java

Lad os se på en grundlæggende låsfri kø i Java. Lad os først se på klassemedlemmerne og konstruktøren:

offentlig klasse NonBlockingQueue {privat final AtomicReference hoved, hale; privat endelig størrelse AtomicInteger; public NonBlockingQueue () {head = new AtomicReference (null); hale = ny AtomicReference (null); størrelse = nyt AtomicInteger (); størrelse. sæt (0); }}

Den vigtige del er erklæringen af ​​hoved- og halehenvisninger som AtomicReferences, hvilket sikrer, at enhver opdatering af disse referencer er en atomoperation. Denne datatype i Java implementerer det nødvendige sammenligne-og-bytte operation.

Lad os derefter se på implementeringen af ​​Node-klassen:

privat klasse Node {privat flygtig T-værdi; privat flygtig Node næste; privat flygtig knude forrige; offentlig knude (T-værdi) {this.value = værdi; this.next = null; } // getters og setters}

Her er den vigtige del at erklære referencerne til den forrige og næste node som flygtige. Dette sikrer, at vi altid opdaterer disse referencer i hovedhukommelsen (er således direkte synlige for alle tråde). Det samme for den aktuelle nodeværdi.

6.1. Låsefri tilføje

Vores låsefrie tilføje operation vil sikre, at vi tilføjer det nye element i halen og ikke afbrydes fra køen, selvom flere tråde ønsker at tilføje et nyt element samtidigt:

public void add (T element) {if (element == null) {throw new NullPointerException (); } Node node = ny node (element); Node nuværendeTail; gør {currentTail = tail.get (); node.setPrevious (nuværendeTail); } mens (! tail.compareAndSet (currentTail, node)); hvis (node.previous! = null) {node.previous.next = node; } head.compareAndSet (null, node); // til indsættelse af det første elementstørrelse.incrementAndGet (); }

Den væsentlige del at være opmærksom på er den fremhævede linje. Vi forsøger at tilføje den nye node til køen, indtil CAS-operationen lykkes at opdatere halen, som stadig skal være den samme hale, som vi tilføjede den nye node.

6.2. Låsfri få

I lighed med tilføjelsesoperationen vil den låsefrie get-operation sikre, at vi returnerer det sidste element og flytter halen til den aktuelle position:

public T get () {if (head.get () == null) {throw new NoSuchElementException (); } Node nuværendeHoved; Node næsteNode; gør {currentHead = head.get (); nextNode = currentHead.getNext (); } mens (! head.compareAndSet (currentHead, nextNode)); size.decrementAndGet (); returner currentHead.getValue (); }

Igen er den væsentlige del at være opmærksom på den fremhævede linje. CAS-operationen sikrer, at vi kun flytter det aktuelle hoved, hvis der ikke er fjernet nogen anden node i mellemtiden.

Java leverer allerede en implementering af en ikke-blokerende kø, den ConcurrentLinkedQueue. Det er en implementering af den låsefri kø fra M. Michael og L. Scott, der er beskrevet i dette papir. En interessant sidebemærkning her er, at Java-dokumentationen siger, at det er et ventefri kø, hvor det faktisk er låsefri. Java 8-dokumentationen kalder korrekt implementeringen låsefri.

7. Ventfri køer

Som vi har set, er ovenstående implementering låsefridog ikke ventefri. Det mens sløjfer i begge tilføje og få metode kan potentielt løkke i lang tid (eller, selvom det er usandsynligt, for evigt), hvis der er mange tråde, der får adgang til vores kø.

Hvordan kan vi opnå ventefrihed? Implementeringen af ​​ventefrie algoritmer er generelt ganske vanskelig. Vi henviser den interesserede læser til dette papir, der beskriver en ventfri kø i detaljer. Lad os i denne artikel se på den grundlæggende idé om, hvordan vi kan nærme os en ventetid-implementering af en kø.

En ventefri kø kræver, at hver tråd gør garanteret fremskridt (efter et begrænset antal trin). Med andre ord, mens sløjfer i vores tilføj og få-metoder skal lykkes efter et bestemt antal trin.

For at opnå dette tildeler vi en hjælpetråd til hver tråd. Hvis denne hjælpertråd lykkes at tilføje et element til køen, vil det hjælpe den anden tråd med at indsætte sit element, inden der indsættes et andet element.

Da hjælpertråden har en hjælper selv, og ned på hele listen over tråde, hver tråd har en hjælper, kan vi garantere, at en tråd efterfølger indsættelsen senest, efter at hver tråd har foretaget en indsættelse. Følgende figur illustrerer ideen:

Naturligvis bliver tingene mere komplicerede, når vi kan tilføje eller fjerne tråde dynamisk.

8. Konklusion

I denne artikel så vi det grundlæggende ved ikke-blokerende datastrukturer. Vi forklarede de forskellige niveauer og grundlæggende operationer som sammenligne-og-bytte.

Derefter så vi på en grundlæggende implementering af en låsefri kø i Java. Endelig skitserede vi ideen om, hvordan man opnå Vent-frihed.

Den fulde kildekode til alle eksempler i denne artikel er tilgængelig på GitHub.