streamalism.org

1. Introduksjon

I denne opplæringen lærer vi hva ikke-blokkerende datastrukturer er og hvorfor de er et viktig alternativ til låsebaserte samtidige datastrukturer.

Først vil vi gå over noen begreper som hindringsfri, låsfritt, og ventetid.

For det andre skal vi se på de grunnleggende byggesteinene for ikke-blokkerende algoritmer som CAS (sammenlign og bytt).

For det tredje vil vi se på implementeringen av en låsfri kø i Java, og til slutt vil vi skissere en tilnærming til hvordan man kan oppnå vent-frihet.

2. Lås mot sult

La oss først se på forskjellen mellom en blokkert og en sultende tråd.

På bildet ovenfor får Thread 2 en lås på datastrukturen. Når tråd 1 også prøver å skaffe seg en lås, må den vente til tråd 2 slipper låsen; det vil ikke fortsette før det kan få låsen. Hvis vi suspenderer tråd 2 mens den holder låsen, må tråd 1 vente for alltid.

Det neste bildet illustrerer trådsult:

Her får tråd 2 tilgang til datastrukturen, men får ikke en lås. Tråd 1 prøver å få tilgang til datastrukturen på samme tid, oppdager samtidig tilgang, og kommer umiddelbart tilbake og informerer tråden om at den ikke kunne fullføre (rød) operasjonen. Tråd 1 vil deretter prøve igjen til den lykkes med å fullføre operasjonen (grønn).

Fordelen med denne tilnærmingen er at vi ikke trenger en lås. Det som imidlertid kan skje er at hvis tråd 2 (eller andre tråder) får tilgang til datastrukturen med høy frekvens, så trenger tråd 1 et stort antall forsøk til den endelig lykkes. Vi kaller dette sult.

Senere får vi se hvordan sammenlign-og-bytt operasjonen oppnår ikke-blokkerende tilgang.

3. Typer av ikke-blokkerende datastrukturer

Vi kan skille mellom tre nivåer av ikke-blokkerende datastrukturer.

3.1. Hindringsfri

Hindring-frihet er den svakeste formen for en ikke-blokkerende datastruktur. Her krever vi bare at en tråd garantert vil fortsette hvis alle andre tråder er suspendert.

Mer presist, en tråd vil ikke fortsette å sulte hvis alle andre tråder er suspendert. Dette er forskjellig fra å bruke låser i den forstand, at hvis tråden ventet på en lås og en tråd som holder låsen er suspendert, ville ventetråden vente for alltid.

3.2. Låsfritt

En datastruktur gir låsefrihet hvis minst en tråd når som helst kan fortsette. Alle andre tråder kan være sultne. Forskjellen til hindring-frihet er at det er minst en tråd som ikke sulter, selv om ingen tråder er suspendert.

3.3. Vent-fri

En datastruktur er ventfri hvis den er låsfri, og hver tråd er garantert å fortsette etter et endelig antall trinn, det vil si at tråder ikke sulter etter et "urimelig stort" antall trinn.

3.4. Sammendrag

La oss oppsummere disse definisjonene i grafisk fremstilling:

Den første delen av bildet viser hindring-frihet da tråd 1 (overtråd) kan fortsette (grønn pil) så snart vi suspenderer de andre trådene (nederst i gult).

Midtdelen viser låsefrihet. I det minste kan tråd 1 utvikle seg mens andre kan sulte (rød pil).

Den siste delen viser ventefrihet. Her garanterer vi at tråd 1 kan fortsette (grønn pil) etter en viss periode med sult (røde piler).

4. Ikke-blokkerende primitiver

I denne delen ser vi på tre grunnleggende operasjoner som hjelper oss med å bygge låsfrie operasjoner på datastrukturer.

4.1. Sammenlign og bytt

En av de grunnleggende operasjonene som brukes for å unngå låsing er sammenlign-og-bytt (CAS) drift.

Ideen med sammenligning og bytte er at en variabel bare oppdateres hvis den fremdeles har samme verdi som den gangen vi hadde hentet verdien til variabelen fra hovedminnet. CAS er en atomoperasjon, som betyr at henting og oppdatering sammen er en enkelt operasjon:

Her henter begge trådene verdien 3 fra hovedminnet. Tråd 2 lykkes (grønn) og oppdaterer variabelen til 8. Ettersom den første CAS etter tråd 1 forventer at verdien fortsatt er 3, mislykkes CAS (rød). Derfor henter tråd 1 verdien igjen, og den andre CAS lykkes.

Det viktige her er at CAS ikke får en lås på datastrukturen, men returnerer ekte Hvis oppdateringen var vellykket, kommer den ellers tilbake falsk.

Følgende kodebit skisserer hvordan CAS fungerer:

flyktig int-verdi; boolsk cas (int forventet verdi, int ny verdi) {hvis (verdi == forventet verdi) {verdi = ny verdi; returner sant; } returner falsk; }

Vi oppdaterer bare verdien med den nye verdien hvis den fremdeles har den forventede verdien, ellers returnerer den falsk. Følgende kodebit viser hvordan CAS kan kalles:

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

Vi prøver å oppdatere verdien vår til CAS-operasjonen lykkes, det vil si returnerer ekte.

Det er imidlertid mulig at en tråd setter seg fast i sult. Det kan skje hvis andre tråder utfører en CAS på samme variabel samtidig, slik at operasjonen aldri vil lykkes for en bestemt tråd (eller det tar urimelig lang tid å lykkes). Likevel, hvis sammenlign og bytt mislykkes, vi vet at en annen tråd har lyktes, og dermed sikrer vi også global fremgang, slik det er nødvendig for låsefrihet.

Det er viktig å merke seg at maskinvaren skal støtte sammenlign og bytt, for å gjøre det til en virkelig atomoperasjon uten bruk av låsing.

Java gir en implementering av sammenlign og bytt i klassen sun.misc. usikre. I de fleste tilfeller bør vi imidlertid ikke bruke denne klassen direkte, men Atomic-variabler i stedet.

Dessuten, sammenlign og bytt forhindrer ikke A-B-A-problemet. Vi ser på det i neste avsnitt.

4.2. Load-Link / Store-Conditional

Et alternativ til sammenlign og bytt er last-link / butikk-betinget. La oss først gå tilbake sammenlign og bytt. Som vi har sett før, oppdaterer CAS bare verdien hvis verdien i hovedminnet fortsatt er verdien vi forventer at den skal være.

Imidlertid lykkes også CAS hvis verdien hadde endret seg, og i mellomtiden har endret seg tilbake til sin tidligere verdi.

Bildet nedenfor illustrerer denne situasjonen:

Både tråd 1 og tråd 2 leser verdien av variabelen, som er 3. Deretter utfører tråd 2 en CAS, som lykkes med å sette variabelen til 8. Deretter utfører tråd 2 en CAS for å sette variabelen tilbake til 3, som også lykkes. Til slutt utfører tråd 1 en CAS, og forventer verdien 3, og lykkes også, selv om verdien av variabelen vår ble endret to ganger i mellom.

Dette kalles A-B-A-problemet. Denne oppførselen er kanskje ikke noe problem, avhengig av brukssaken, selvfølgelig. Imidlertid er det kanskje ikke ønskelig for andre. Java gir en implementering av last-link / butikk-betinget med AtomicStampedReference klasse.

4.3. Hent og legg til

Et annet alternativ er hent og legg til. Denne operasjonen øker variabelen i hovedminnet med en gitt verdi. Igjen, det viktige poenget er at operasjonen skjer atomisk, noe som betyr at ingen annen tråd kan forstyrre.

Java gir en implementering av hent og legg til i sine atomklasser. Eksempler er AtomicInteger.incrementAndGet (), som øker verdien og returnerer den nye verdien; og AtomicInteger.getAndIncrement (), som returnerer den gamle verdien og deretter øker verdien.

5. Få tilgang til en koblet kø fra flere tråder

For å bedre forstå problemet med to (eller flere) tråder som får tilgang til en kø samtidig, la oss se på en koblet kø og to tråder som prøver å legge til et element samtidig.

Køen vi ser på er en dobbeltkoblet FIFO-kø der vi legger til nye elementer etter det siste elementet (L) og variabelen hale peker på det siste elementet:

For å legge til et nytt element må trådene utføre tre trinn: 1) lage de nye elementene (N og M), med pekeren til neste element satt til null; 2) ha henvisningen til det forrige elementet punkt til L og henvisningen til det neste elementet av L punkt til henholdsvis N (M). 3) Har hale pek på henholdsvis N (M):

Hva kan gå galt hvis de to trådene utfører disse trinnene samtidig? Hvis trinnene i bildet ovenfor utføres i rekkefølgen ABCD eller ACBD, L, så vel som hale, vil peke på M. N vil forbli frakoblet fra køen.

Hvis trinnene utføres i rekkefølgen ACDB, hale vil peke på N, mens L vil peke på M, noe som vil føre til en inkonsekvens i køen:

Selvfølgelig er en måte å løse dette problemet på å ha en tråd til å skaffe seg en lås i køen. Løsningen vi vil se på i det følgende kapittelet vil løse problemet ved hjelp av en låsfri operasjon ved å bruke CAS-operasjonen vi har sett tidligere.

6. En ikke-blokkerende kø i Java

La oss se på en grunnleggende låsfri kø i Java. La oss først se på klassemedlemmene og konstruktøren:

offentlig klasse NonBlockingQueue {privat finale AtomicReference hode, hale; privat slutt AtomicInteger størrelse; public NonBlockingQueue () {head = new AtomicReference (null); hale = ny AtomicReference (null); størrelse = nytt AtomicInteger (); størrelse. sett (0); }}

Den viktige delen er erklæringen om hodet og halen referanser som AtomicReferences, som sikrer at enhver oppdatering av disse referansene er en atomoperasjon. Denne datatypen i Java implementerer det nødvendige sammenlign og bytt operasjon.

La oss deretter se på implementeringen av Node-klassen:

privat klasse Node {privat flyktig T-verdi; privat flyktig Node neste; privat flyktig Node tidligere; offentlig node (T-verdi) {this.value = verdi; this.next = null; } // getters og setters}

Her er den viktige delen å erklære referansene til forrige og neste node som flyktige. Dette sikrer at vi alltid oppdaterer disse referansene i hovedminnet (og dermed er direkte synlige for alle tråder). Det samme for den faktiske nodeverdien.

6.1. Låsfritt legge til

Vårt låsfritt legge til operasjonen vil sørge for at vi legger til det nye elementet i halen og ikke blir koblet fra køen, selv om flere tråder vil legge til et nytt element samtidig:

public void add (T element) {if (element == null) {throw new NullPointerException (); } Node node = new Node (element); Node currentTail; gjør {currentTail = tail.get (); node.setPrevious (currentTail); } mens (! tail.compareAndSet (currentTail, node)); hvis (node.previous! = null) {node.previous.next = node; } head.compareAndSet (null, node); // for å sette inn den første elementstørrelsen.incrementAndGet (); }

Den viktigste delen å være oppmerksom på er den uthevede linjen. Vi prøver å legge til den nye noden i køen til CAS-operasjonen lykkes med å oppdatere halen, som fortsatt må være den samme halen som vi la til den nye noden.

6.2. Låsfritt få

I likhet med tilleggsoperasjonen, vil den låsfrie get-operasjonen sørge for at vi returnerer det siste elementet og flytter halen til gjeldende posisjon:

public T get () {if (head.get () == null) {throw new NoSuchElementException (); } Node currentHead; Node nesteNode; gjør {currentHead = head.get (); nextNode = currentHead.getNext (); } while (! head.compareAndSet (currentHead, nextNode)); size.decrementAndGet (); return currentHead.getValue (); }

Igjen, den viktigste delen å være oppmerksom på er den uthevede linjen. CAS-operasjonen sikrer at vi bare flytter det nåværende hodet hvis ingen annen node er fjernet i mellomtiden.

Java gir allerede en implementering av en ikke-blokkerende kø, den ConcurrentLinkedQueue. Det er en implementering av den låsfrie køen fra M. Michael og L. Scott beskrevet i denne artikkelen. En interessant sidemerknad her er at Java-dokumentasjonen sier at det er en ventefritt kø, hvor det faktisk er låsfritt. Java 8-dokumentasjonen kaller implementeringen riktig låsfritt.

7. Ventekøer

Som vi har sett, er implementeringen ovenfor låsfrittimidlertid ikke ventefritt. De samtidig som sløyfer i begge legge til og få metoden kan potensielt løkke i lang tid (eller, selv om det er lite sannsynlig, for alltid) hvis det er mange tråder som får tilgang til køen vår.

Hvordan kan vi oppnå ventefrihet? Implementeringen av ventefrie algoritmer er generelt ganske vanskelig. Vi henviser den interesserte leseren til denne artikkelen, som beskriver en ventfri kø i detalj. I denne artikkelen, la oss se på den grunnleggende ideen om hvordan vi kan nærme oss en ventfri implementering av en kø.

En ventfri kø krever at hver tråd gjør garantert fremgang (etter et endelig antall trinn). Med andre ord, samtidig som sløyfer i våre add and get-metoder må lykkes etter et visst antall trinn.

For å oppnå det tildeler vi en hjelpetråd til hver tråd. Hvis den hjelpetråden lykkes med å legge til et element i køen, vil det hjelpe den andre tråden med å sette inn elementet før det setter inn et annet element.

Ettersom hjelpertråden har en hjelper i seg selv, og nedover hele listen over tråder, hver tråd har hjelper, kan vi garantere at en tråd lykkes med innsettingen sist etter at hver tråd har gjort en innsetting. Følgende figur illustrerer ideen:

Selvfølgelig blir ting mer kompliserte når vi kan legge til eller fjerne tråder dynamisk.

8. Konklusjon

I denne artikkelen så vi grunnleggende om ikke-blokkerende datastrukturer. Vi forklarte de forskjellige nivåene og grunnleggende operasjoner som sammenlign-og-bytt.

Så så vi på en grunnleggende implementering av en låsfritt kø i Java. Til slutt skisserte vi ideen om hvordan du skal oppnå vent-frihet.

Den fullstendige kildekoden for alle eksemplene i denne artikkelen er tilgjengelig på GitHub.