Programmering

Java 101: Java-samtidighed uden smerte, del 2

Forrige 1 2 3 4 Side 3 Næste Side 3 af 4

Atomiske variabler

Multitrådede applikationer, der kører på multicore-processorer eller multiprocessorsystemer, kan opnå god hardwareudnyttelse og være meget skalerbare. De kan nå disse mål ved at lade deres tråde bruge det meste af deres tid på at udføre arbejde i stedet for at vente på, at arbejde skal udføres, eller vente på at få låse for at få adgang til delte datastrukturer.

Imidlertid Java's traditionelle synkroniseringsmekanisme, som håndhæver gensidig udelukkelse (tråden, der holder låsen, der beskytter et sæt variabler, har eksklusiv adgang til dem) og sigtbarhed (ændringer af de beskyttede variabler bliver synlige for andre tråde, der efterfølgende erhverver låsen), påvirker hardwareudnyttelse og skalerbarhed som følger:

  • Indsat synkronisering (flere tråde, der konstant konkurrerer om en lås) er dyrt, og gennemstrømningen lider som følge heraf. En væsentlig årsag til udgiften er den hyppige kontekstskift, der finder sted; en kontekstskifteoperation kan tage mange processorcyklusser at gennemføre. I modsætning, ukontrolleret synkronisering er billig på moderne JVM'er.
  • Når en tråd, der holder en lås, er forsinket (f.eks. På grund af en planlægningsforsinkelse), gør ingen tråd, der kræver, at låsen gør noget fremskridt, og hardwaren bruges ikke så godt som den ellers kan være.

Du tror måske, du kan bruge flygtige som et synkroniseringsalternativ. Imidlertid, flygtige variabler løser kun synlighedsproblemet. De kan ikke bruges til sikkert at implementere de atomare læs-modificer-skriv-sekvenser, der er nødvendige for sikkert at implementere tællere og andre enheder, der kræver gensidig udelukkelse.

Java 5 introducerede et synkroniseringsalternativ, der tilbyder gensidig udelukkelse kombineret med ydeevnen af flygtige. Det her atomvariabel Alternativet er baseret på en mikroprocessors sammenlignings-og-swap-instruktion og består stort set af typerne i java.util.concurrent.atomic pakke.

Forstå sammenligning-og-swap

Det sammenligne og bytte (CAS) instruktion er en uafbrydelig instruktion, der læser en hukommelsesplacering, sammenligner læseværdien med en forventet værdi og gemmer en ny værdi på hukommelsesplaceringen, når læseværdien svarer til den forventede værdi. Ellers gøres intet. Den aktuelle mikroprocessorinstruktion kan afvige noget (f.eks. Returnere true hvis CAS lykkedes eller falsk på anden måde i stedet for den læste værdi).

Mikroprocessor CAS instruktioner

Moderne mikroprocessorer tilbyder en slags CAS-instruktion. For eksempel tilbyder Intel-mikroprocessorer cmpxchg instruktionsfamilie, hvorimod PowerPC-mikroprocessorer tilbyder load-link (f.eks. lwarx) og butiksbetinget (f.eks. stwcx) instruktioner til samme formål.

CAS gør det muligt at understøtte atomare read-modify-write sekvenser. Du bruger typisk CAS som følger:

  1. Læs værdi v fra adresse X.
  2. Udfør en flertrinsberegning for at udlede en ny værdi v2.
  3. Brug CAS til at ændre værdien af ​​X fra v til v2. CAS lykkes, når X's værdi ikke har ændret sig under udførelsen af ​​disse trin.

For at se, hvordan CAS tilbyder bedre ydelse (og skalerbarhed) i forhold til synkronisering, skal du overveje et modeksempel, der giver dig mulighed for at læse dens aktuelle værdi og øge tælleren. Følgende klasse implementerer en tæller baseret på synkroniseret:

Liste 4. Counter.java (version 1)

offentlig klassetæller {privat int-værdi; offentlig synkroniseret int getValue () {returværdi; } offentlig synkroniseret int-trin () {return ++ -værdi; }}

Høj strid om skærmlåsen vil resultere i overdreven skift af kontekst, der kan forsinke alle tråde og resultere i et program, der ikke skaleres godt.

CAS-alternativet kræver en implementering af sammenlignings-og-swap-instruktionen. Følgende klasse efterligner CAS. Det bruger synkroniseret i stedet for den faktiske hardwareinstruktion for at forenkle koden:

Fortegnelse 5. EmulatedCAS.java

offentlig klasse EmulatedCAS {private int værdi; offentlig synkroniseret int getValue () {returværdi; } offentlig synkroniseret int CompareAndSwap (int forventet værdi, int ny værdi) {int readValue = værdi; hvis (readValue == forventet værdi) værdi = newValue; returner readValue; }}

Her, værdi identificerer en hukommelsesplacering, som kan hentes af getValue (). Også, sammenlignAndSwap () implementerer CAS-algoritmen.

Følgende klasse bruger EmulatedCAS at gennemføre en ikke-synkroniseret tæller (foregiv det EmulatedCAS kræver ikke synkroniseret):

Liste 6. Counter.java (version 2)

offentlig klassetæller {privat EmulatedCAS-værdi = ny EmulatedCAS (); public int getValue () {return value.getValue (); } offentlig int-stigning () {int readValue = value.getValue (); while (value.compareAndSwap (readValue, readValue + 1)! = readValue) readValue = value.getValue (); returner readValue + 1; }}

Tæller indkapsler en EmulatedCAS forekomst og erklærer metoder til at hente og øge en modværdi med hjælp fra denne forekomst. getValue () henter instansens "aktuelle tællerværdi" og stigning () øger tællerværdien sikkert.

stigning () gentagne gange påberåber sig sammenlignAndSwap () så længe readValueværdi ændres ikke. Det er så gratis at ændre denne værdi. Når ingen lås er involveret, undgås strid sammen med overdreven kontekstskift. Ydeevnen forbedres, og koden er mere skalerbar.

ReentrantLock og CAS

Det har du tidligere lært ReentrantLock tilbyder bedre ydelse end synkroniseret under strid med høj tråd. For at øge ydeevnen ReentrantLockSynkronisering styres af en underklasse af det abstrakte java.util.concurrent.locks.AbstractQueuedSynchronizer klasse. Til gengæld udnytter denne klasse de udokumenterede sun.misc. usikker klasse og dens sammenlignAndSwapInt () CAS-metode.

Udforskning af atomvariablerpakken

Du behøver ikke implementere sammenlignAndSwap () via den ikke-bærbare Java Native Interface. I stedet tilbyder Java 5 denne support via java.util.concurrent.atomic: et værktøjssæt med klasser, der bruges til låsefri, trådsikker programmering på enkelte variabler.

Ifølge java.util.concurrent.atomic's Javadoc, disse klasser

udvide begrebet flygtige værdier, felter og matrixelementer til dem, der også giver en atomær betinget opdateringsoperation af formularen boolsk comparAndSet (forventet værdi, opdateringsværdi). Denne metode (som varierer i argumenttyper på tværs af forskellige klasser) indstiller atomisk en variabel til updateValue hvis det i øjeblikket holder forventet værdi, rapporterer sandt om succes.

Denne pakke tilbyder klasser til boolsk (AtomicBoolean), heltal (AtomicInteger), langt heltal (AtomicLong) og reference (AtomicReference) typer. Det tilbyder også matrixversioner af heltal, langt heltal og reference (AtomicIntegerArray, AtomicLongArrayog AtomicReferenceArray), markerede og stemplede referenceklasser til atomopdatering af et par værdier (AtomicMarkableReference og AtomicStampedReference), og mere.

Implementering CompareAndSet ()

Java implementerer sammenlignAndSet () via den hurtigst tilgængelige native konstruktion (f.eks. cmpxchg eller load-link / store-betinget) eller (i værste fald) spin låse.

Overveje AtomicInteger, som lader dig opdatere en int værdi atomisk. Vi kan bruge denne klasse til at implementere tælleren vist i Listing 6. Listing 7 viser den tilsvarende kildekode.

Liste 7. Counter.java (version 3)

import java.util.concurrent.atomic.AtomicInteger; offentlig klassetæller {privat AtomicInteger-værdi = nyt AtomicInteger (); public int getValue () {return value.get (); } offentlig int-stigning () {int readValue = value.get (); while (! value.compareAndSet (readValue, readValue + 1)) readValue = value.get (); returner readValue + 1; }}

Listing 7 svarer meget til Listing 6 bortset fra at den erstatter EmulatedCAS med AtomicInteger. I øvrigt kan du forenkle stigning () fordi AtomicInteger leverer sine egne int getAndIncrement () metode (og lignende metoder).

Gaffel / Deltag ramme

Computerhardware har udviklet sig betydeligt siden Javas debut i 1995. Dengang dominerede enkeltprocessorsystemer computerlandskabet og Java's synkroniseringsprimitiver, såsom synkroniseret og flygtige, samt dets trådbibliotek ( Tråd klasse, for eksempel) var generelt passende.

Multiprocessorsystemer blev billigere, og udviklere befandt sig nødt til at oprette Java-applikationer, der effektivt udnyttede den hardware-parallelisme, som disse systemer tilbød. Imidlertid opdagede de snart, at Java's primære primære tråde og bibliotek med lavt niveau var meget vanskelige at bruge i denne sammenhæng, og de resulterende løsninger blev ofte fyldt med fejl.

Hvad er parallelisme?

Parallelisme er samtidig udførelse af flere tråde / opgaver via en kombination af flere processorer og processorkerner.

Java Concurrency Utilities-rammen forenkler udviklingen af ​​disse applikationer; de værktøjer, der tilbydes af denne ramme, skaleres dog ikke til tusindvis af processorer eller processorkerner. I vores mange-kerne-æra har vi brug for en løsning til opnåelse af en mere detaljeret parallelitet, eller vi risikerer at holde processorer inaktive, selv når der er meget arbejde for dem at håndtere.

Professor Doug Lea præsenterede en løsning på dette problem i sit papir, der introducerede ideen til en Java-baseret fork / join-ramme. Lea beskriver en ramme, der understøtter "en stil med parallel programmering, hvor problemer løses ved (rekursivt) at opdele dem i underopgaver, der løses parallelt." Fork / Join-rammen blev til sidst inkluderet i Java 7.

Oversigt over Fork / Join-rammen

Fork / Join-rammen er baseret på en særlig eksekutortjeneste til at køre en særlig slags opgave. Den består af følgende typer, der er placeret i java.util.concurrent pakke:

  • ForkJoinPool: en ExecutorService implementering, der kører ForkJoinTasks. ForkJoinPool giver metoder til indsendelse af opgaver, såsom ugyldig udførelse (ForkJoinTask-opgave)sammen med styrings- og overvågningsmetoder, såsom int getParallelism () og lang getStealCount ().
  • ForkJoinTask: en abstrakt basisklasse for opgaver, der kører inden for en ForkJoinPool sammenhæng. ForkJoinTask beskriver trådlignende enheder, der har en meget lettere vægt end normale tråde. Mange opgaver og underopgaver kan være vært for meget få aktuelle tråde i en ForkJoinPool eksempel.
  • ForkJoinWorkerThread: en klasse, der beskriver en tråd, der administreres af en ForkJoinPool eksempel. ForkJoinWorkerThread er ansvarlig for udførelsen ForkJoinTasks.
  • Rekursiv handling: en abstrakt klasse, der beskriver en rekursiv resultatløs ForkJoinTask.
  • Rekursiv opgave: en abstrakt klasse, der beskriver en rekursiv resultatbæring ForkJoinTask.

Det ForkJoinPool eksekutortjeneste er indgangspunktet for indsendelse af opgaver, der typisk beskrives af underklasser af Rekursiv handling eller Rekursiv opgave. Bag kulisserne er opgaven opdelt i mindre opgaver, der er forked (distribueret mellem forskellige tråde til udførelse) fra puljen. En opgave venter til sluttede sig (dens underopgaver slutter, så resultaterne kan kombineres).

ForkJoinPool administrerer en pulje af arbejdstråde, hvor hver arbejdstråd har sin egen arbejdskø med dobbelt ende (deque). Når en opgave sender en ny delopgave, skubber tråden delopgaven på hovedet af dens deque. Når en opgave forsøger at slutte sig til en anden opgave, der ikke er afsluttet, springer tråden en anden opgave fra hovedet på dens deque og udfører opgaven. Hvis trådens deque er tom, forsøger den at stjæle en anden opgave fra halen på en anden tråds deque. Det her arbejde stjæle adfærd maksimerer gennemstrømning og minimerer strid

Brug af rammen Fork / Join

Fork / Join blev designet til at udføre effektivt del-og-erobre algoritmer, som rekursivt deler problemer i underproblemer, indtil de er enkle nok til at løse direkte; for eksempel en flettsortering. Løsningerne på disse underproblemer kombineres for at give en løsning på det oprindelige problem. Hvert delproblem kan udføres uafhængigt af hinanden på en anden processor eller kerne.

Lea's papir præsenterer følgende pseudokode for at beskrive adskillelses-og-erobre opførsel:

Resultat løser (Problem problem) {hvis (problemet er lille) direkte løser problemet andet {del problemet i uafhængige dele fork del nye underopgaver for at løse hver del sammen alle delopgaver komponere resultat fra underresultater}}

Pseudokoden præsenterer en løse metode, der kaldes med nogle problem at løse, og som returnerer en Resultat der indeholder problem's løsning. Hvis den problem er for lille til at løse via parallelisme, den løses direkte. (Omkostningerne ved at bruge parallelisme på et lille problem overstiger enhver opnået fordel.) Ellers er problemet opdelt i underopgaver: hver delopgave fokuserer uafhængigt på en del af problemet.

Operation gaffel lancerer en ny fork / join-underopgave, der udføres parallelt med andre underopgaver. Operation tilslutte forsinker den aktuelle opgave, indtil den forkedede delopgave er færdig. På et eller andet tidspunkt kunne den problem vil være lille nok til at blive udført sekventielt, og dets resultat kombineres sammen med andre underresultater for at opnå en samlet løsning, der returneres til den, der ringer op.

Javadoc til Rekursiv handling og Rekursiv opgave klasser præsenterer flere dele-og-erobre algoritme eksempler implementeret som fork / join opgaver. Til Rekursiv handling eksemplerne sorterer en matrix med lange heltal, inkrementerer hvert element i en matrix og summerer kvadraterne for hvert element i en matrix af dobbelts. Rekursiv opgave's ensomme eksempel beregner et Fibonacci-nummer.

Listing 8 præsenterer et program, der demonstrerer sorteringseksemplet i ikke-fork / join samt gaffel / join-sammenhænge. Det præsenterer også nogle timingoplysninger for at kontrastere sorteringshastighederne.