Atomiske variabler
Flertrådede applikasjoner som kjører på flerkjerneprosessorer eller flerprosessorsystemer, kan oppnå god maskinvarebruk og være svært skalerbare. De kan oppnå disse målene ved at trådene bruker mesteparten av tiden på å utføre arbeid i stedet for å vente på at arbeidet skal oppnås, eller vente på å skaffe seg låser for å få tilgang til delte datastrukturer.
Imidlertid Java's tradisjonelle synkroniseringsmekanisme, som håndhever gjensidig utelukkelse (tråden som holder låsen som beskytter et sett med variabler, har eksklusiv tilgang til dem) og synlighet (endringer i de beskyttede variablene blir synlige for andre tråder som senere får låsen), påvirker maskinvareanvendelse og skalerbarhet, som følger:
- Kontinuerlig synkronisering (flere tråder som konstant konkurrerer om en lås) er dyrt og gjennomstrømningen lider som et resultat. En viktig årsak til utgiften er den hyppige bytte av kontekst som finner sted; en kontekstbryteroperasjon kan ta mange prosessersykluser å fullføre. I motsetning, ukontrollert synkronisering er billig på moderne JVM.
- Når en tråd som holder en lås er forsinket (f.eks. På grunn av en planleggingsforsinkelse), gjør ingen tråd som krever at låsen gjør fremgang, og maskinvaren blir ikke brukt så godt som den ellers kan være.
Du tror kanskje du kan bruke flyktige som et synkroniseringsalternativ. Derimot, flyktige variabler løser bare synlighetsproblemet. De kan ikke brukes til å implementere de atomare lese-modifiser-skriv-sekvensene som er nødvendige for å implementere tellere og andre enheter som krever gjensidig ekskludering på en sikker måte.
Java 5 introduserte et synkroniseringsalternativ som tilbyr gjensidig ekskludering kombinert med ytelsen til flyktige. Dette atomvariabel alternativet er basert på en mikroprosessorens sammenlignings-og-bytte-instruksjon og består i stor grad av typene i java.util.concurrent.atomic pakke.
Forstå sammenligning og bytte
De sammenlign og bytt (CAS) instruksjon er en avbruddsfri instruksjon som leser en minneplassering, sammenligner leseverdien med en forventet verdi og lagrer en ny verdi i minneplasseringen når leseverdien samsvarer med den forventede verdien. Ellers blir ingenting gjort. Den faktiske instruksjonen til mikroprosessor kan variere noe (for eksempel return true hvis CAS lyktes eller falsk ellers i stedet for leseverdien).
CAS-instruksjoner for mikroprosessor
Moderne mikroprosessorer tilbyr en slags CAS-instruksjon. For eksempel tilbyr Intel-mikroprosessorer cmpxchg instruksjonsfamilie, mens PowerPC-mikroprosessorer tilbyr lastekobling (f.eks. lwarx) og butikkbetinget (f.eks. stwcx) instruksjoner for samme formål.
CAS gjør det mulig å støtte sekvenser for atom-read-modify-write-sekvenser. Du bruker vanligvis CAS som følger:
- Les verdi v fra adresse X.
- Utfør en flerstegsberegning for å utlede en ny verdi v2.
- Bruk CAS til å endre verdien på X fra v til v2. CAS lykkes når X-verdien ikke har endret seg mens du utfører disse trinnene.
For å se hvordan CAS gir bedre ytelse (og skalerbarhet) over synkronisering, bør du vurdere et moteksempel som lar deg lese den nåværende verdien og øke telleren. Følgende klasse implementerer en teller basert på synkronisert:
Oppføring 4. Counter.java (versjon 1)
offentlig klasseteller {privat int-verdi; offentlig synkronisert int getValue () {returverdi; } offentlig synkronisert int-trinn () {return ++ verdi; }}Høy påstand om skjermlåsen vil resultere i overdreven kontekstbytte som kan forsinke alle trådene og resultere i et program som ikke skalerer godt.
CAS-alternativet krever en implementering av sammenlignings-og-bytt-instruksjonen. Følgende klasse etterligner CAS. Det bruker synkronisert i stedet for den faktiske maskinvareinstruksjonen for å forenkle koden:
Oppføring 5. EmulatedCAS.java
offentlig klasse EmulatedCAS {private int-verdi; offentlig synkronisert int getValue () {returverdi; } offentlig synkronisert int CompareAndSwap (int forventet verdi, int newValue) {int readValue = verdi; hvis (readValue == forventet verdi) verdi = newValue; returner readValue; }} Her, verdi identifiserer et minneplassering som kan hentes av getValue (). Også, CompareAndSwap () implementerer CAS-algoritmen.
Følgende klasse bruker EmulatedCAS å implementere en ikke-synkronisert counter (late som EmulatedCAS krever ikke synkronisert):
Oppføring 6. Counter.java (versjon 2)
offentlig klasseteller {privat EmulatedCAS-verdi = ny EmulatedCAS (); public int getValue () {return value.getValue (); } offentlig intrement () {int readValue = value.getValue (); while (value.compareAndSwap (readValue, readValue + 1)! = readValue) readValue = value.getValue (); return readValue + 1; }}Disk innkapsler en EmulatedCAS forekomst og erklærer metoder for å hente og øke en motverdi med hjelp fra denne forekomsten. getValue () henter forekomstens "gjeldende motverdi" og økning () øker tellerverdien trygt.
økning () gjentar gjentatte ganger CompareAndSwap () før readValueVerdien endres ikke. Det er da gratis å endre denne verdien. Når ingen lås er involvert, unngås strid sammen med overdreven kontekstbytte. Ytelsen forbedres og koden er mer skalerbar.
ReentrantLock og CAS
Du har tidligere lært det ReentrantLock tilbyr bedre ytelse enn synkronisert under høy trådstrid. For å øke ytelsen, ReentrantLockSynkroniseringen styres av en underklasse av det abstrakte java.util.concurrent.locks.AbstractQueuedSynchronizer klasse. I sin tur utnytter denne klassen papirløse sun.misc. usikre klasse og dens CompareAndSwapInt () CAS-metoden.
Utforske pakken med atomvariabler
Du trenger ikke implementere CompareAndSwap () via det ikke-bærbare Java Native Interface. I stedet tilbyr Java 5 denne støtten via java.util.concurrent.atomic: et verktøysett med klasser som brukes til låsfri, trådsikker programmering på enkeltvariabler.
I følge java.util.concurrent.atomicer Javadoc, disse klassene
flyktige verdier, felt og matriseelementer til de som også gir en atomisk betinget oppdateringsoperasjon av skjemaet boolsk CompareAndSet (forventet verdi, oppdateringsverdi). Denne metoden (som varierer i argumenttyper på tvers av forskjellige klasser) setter atomisk en variabel til updateValue hvis den for øyeblikket holder forventet verdi, rapporterer sant om suksess. Denne pakken tilbyr klasser for boolsk (AtomicBoolean), heltall (AtomicInteger), langt heltall (AtomicLong) og referanse (AtomicReference) typer. Det tilbyr også matrixversjoner av heltall, langt heltall og referanse (AtomicIntegerArray, AtomicLongArray, og AtomicReferenceArray), merkbare og stemplede referanseklasser for atomoppdatering av et par verdier (AtomicMarkableReference og AtomicStampedReference), og mer.
Implementering CompareAndSet ()
Java implementerer sammenlignAndSet () via den raskeste tilgjengelige innfødte konstruksjonen (f.eks. cmpxchg eller last-link / butikk-betinget) eller (i verste fall) spinnlås.
Ta i betraktning AtomicInteger, som lar deg oppdatere en int verdi atomisk. Vi kan bruke denne klassen til å implementere telleren vist i Listing 6. Listing 7 presenterer den tilsvarende kildekoden.
Oppføring 7. Counter.java (versjon 3)
importere java.util.concurrent.atomic.AtomicInteger; public class Counter {private AtomicInteger value = new AtomicInteger (); public int getValue () {return value.get (); } offentlig int-trinn () {int readValue = value.get (); while (! value.compareAndSet (readValue, readValue + 1)) readValue = value.get (); return readValue + 1; }} Oppføring 7 er veldig lik Oppføring 6 bortsett fra at den erstatter EmulatedCAS med AtomicInteger. Du kan forresten forenkle økning () fordi AtomicInteger leverer sine egne int getAndIncrement () metode (og lignende metoder).
Gaffel / Bli med ramme
Datamaskinvare har utviklet seg betydelig siden Javas debut i 1995. Tilbake på dagen dominerte enkeltprosessorsystemer databehandlingslandskapet og Java's synkroniseringsprimitiver, som f.eks. synkronisert og flyktige, samt trådbiblioteket ( Tråd klasse, for eksempel) var generelt tilstrekkelig.
Multiprosessorsystemer ble billigere, og utviklere fant seg nødt til å lage Java-applikasjoner som effektivt utnyttet maskinvareparallellismen som disse systemene tilbød. Imidlertid oppdaget de snart at Java's lavnivå-threading-primitiver og bibliotek var veldig vanskelig å bruke i denne sammenhengen, og de resulterende løsningene var ofte full av feil.
Hva er parallellisme?
Parallelisme er samtidig utføring av flere tråder / oppgaver via en kombinasjon av flere prosessorer og prosessorkjerner.
Java Concurrency Utilities-rammeverket forenkler utviklingen av disse applikasjonene; verktøyene som tilbys av dette rammeverket, skaleres imidlertid ikke til tusenvis av prosessorer eller prosessorkjerner. I vår mange-kjerne tid trenger vi en løsning for å oppnå en mer detaljert parallellitet, eller vi risikerer å holde prosessorer inaktive selv når det er mye arbeid for dem å håndtere.
Professor Doug Lea presenterte en løsning på dette problemet i sitt papir som introduserte ideen om et Java-basert gaffel / sammenføyningsrammeverk. Lea beskriver et rammeverk som støtter "en stil med parallell programmering der problemer løses ved (rekursivt) å dele dem opp i deloppgaver som løses parallelt." Fork / Join-rammeverket ble til slutt inkludert i Java 7.
Oversikt over Fork / Join-rammeverket
Fork / Join-rammeverket er basert på en spesiell utførertjeneste for å kjøre en spesiell type oppgave. Den består av følgende typer som ligger i java.util.concurrent pakke:
ForkJoinPool: enExecutorServiceimplementering som kjørerForkJoinTasks.ForkJoinPoolgir oppgaver for innsending av oppgaver, for eksempelvoid execute (ForkJoinTask-oppgave), sammen med styrings- og overvåkingsmetoder, for eksempelint getParallelism ()oglang getStealCount ().ForkJoinTask: en abstrakt basisklasse for oppgaver som kjører innenfor enForkJoinPoolkontekst.ForkJoinTaskbeskriver trådlignende enheter som har mye lettere vekt enn vanlige tråder. Mange oppgaver og deloppgaver kan være vert for veldig få faktiske tråder i enForkJoinPoolforekomst.ForkJoinWorkerThread: en klasse som beskriver en tråd som administreres av enForkJoinPoolforekomst.ForkJoinWorkerThreader ansvarlig for utførelseForkJoinTasks.Rekursiv handling: en abstrakt klasse som beskriver en rekursiv resultatløsForkJoinTask.Rekursiv oppgave: en abstrakt klasse som beskriver en rekursiv resultatbæringForkJoinTask.
De ForkJoinPool executor service er inngangspunktet for å sende inn oppgaver som vanligvis beskrives av underklasser av Rekursiv handling eller Rekursiv oppgave. Bak kulissene er oppgaven delt inn i mindre oppgaver som er gaffelt (distribuert mellom forskjellige tråder for utførelse) fra bassenget. En oppgave venter til ble med (deloppgavene fullføres slik at resultatene kan kombineres).
ForkJoinPool administrerer en pool av arbeidertråder, der hver arbeidertråd har sin egen arbeidskø med dobbelt slutt (deque). Når en oppgave gir en ny deloppgave, skyver tråden deloppgaven på hodet til dens deque. Når en oppgave prøver å slutte seg til en annen oppgave som ikke er ferdig, spretter tråden en annen oppgave fra hodet til dekningen og utfører oppgaven. Hvis trådens deque er tom, prøver den å stjele en annen oppgave fra halen til en annen tråds deque. Dette arbeid å stjele atferd maksimerer gjennomstrømningen mens den minimerer striden.
Bruke Fork / Join-rammeverket
Fork / Join ble designet for å utføre effektivt del-og-erobre algoritmer, som rekursivt deler opp problemer i underproblemer til de er enkle å løse direkte; for eksempel en sammenslåingssortering. Løsningene på disse delproblemene kombineres for å gi en løsning på det opprinnelige problemet. Hvert delproblem kan utføres uavhengig på en annen prosessor eller kjerne.
Lea's papir presenterer følgende pseudokode for å beskrive skillet og erobre oppførselen:
Resultat løse (Problem problem) {if (problemet er lite) direkte løse problemet annet {del problemet i uavhengige deler gaffel nye deloppgaver for å løse hver del bli med i alle deloppgaver komponere resultat fra underresultater}} Pseudokoden presenterer en løse metoden som kalles med noen problem å løse og som returnerer a Resultat som inneholder problemsin løsning. Hvis den problem er for liten til å løse via parallellitet, løses den direkte. (Omkostningene ved å bruke parallellitet på et lite problem overstiger all oppnådd fordel.) Ellers er problemet delt inn i deloppgaver: hver deloppgave fokuserer uavhengig av seg på en del av problemet.
Operasjon gaffel lanserer en ny gaffel / delta deloppgave som vil utføres parallelt med andre deloppgaver. Operasjon bli med forsinker den gjeldende oppgaven til den delte deloppgaven er ferdig. På et tidspunkt kan den problem vil være liten nok til å utføres sekvensielt, og resultatet vil bli kombinert sammen med andre delresultater for å oppnå en samlet løsning som returneres til den som ringer.
Javadoc for Rekursiv handling og Rekursiv oppgave klasser presenterer flere skill-og-erobre algoritmeeksempler implementert som gaffel / sammenføyningsoppgaver. Til Rekursiv handling eksemplene sorterer en matrise med lange heltall, inkrementerer hvert element i en matrise, og summerer kvadratene til hvert element i en matrise av dobbelts. Rekursiv oppgavesitt ensomme eksempel beregner et Fibonacci-tall.
Listing 8 presenterer et program som viser sorteringseksemplet i ikke-gaffel / sammenføyning samt gaffel / sammenføyning. Den presenterer også litt tidsinformasjon for å kontrastere sorteringshastighetene.
