Atomske spremenljivke
Večnitne aplikacije, ki se izvajajo na večjedrnih procesorjih ali večprocesorskih sistemih, lahko dobro izkoristijo strojno opremo in so zelo prilagodljive. Te cilje lahko dosežejo tako, da njihove niti večino svojega časa porabijo za opravljanje dela, ne pa da čakajo na opravljeno delo ali čakajo na pridobitev ključavnic za dostop do skupnih podatkovnih struktur.
Vendar pa tradicionalni Java sinhronizacijski mehanizem, ki uveljavlja medsebojna izključenost (nit, ki drži ključavnico, ki varuje nabor spremenljivk, ima ekskluziven dostop do njih) in vidljivost (spremembe zaščitenih spremenljivk postanejo vidne drugim nitim, ki kasneje pridobijo ključavnico), vpliva na izkoriščenost strojne opreme in razširljivost, kot sledi:
- Izbrana sinhronizacija (več niti neprestano tekmujejo za ključavnico) je drago in posledično trpi prepustnost. Glavni razlog za stroške je pogosto spreminjanje konteksta; operacija preklopa konteksta lahko traja več ciklov procesorja. V nasprotju, neovirana sinhronizacija je poceni za sodobne JVM-je.
- Ko nit, ki drži ključavnico, zamuja (npr. Zaradi zamude pri razporejanju), nobena nit, ki zahteva to zaklepanje, ne napreduje in strojna oprema se ne uporablja tako dobro, kot bi bila sicer.
Morda mislite, da lahko uporabite hlapljivo
kot alternativa za sinhronizacijo. Vendar hlapljivo
spremenljivke rešujejo samo problem vidnosti. Ni jih mogoče uporabiti za varno izvajanje atomskih zaporedij branja-spreminjanja-pisanja, ki so potrebna za varno izvajanje števcev in drugih entitet, ki zahtevajo medsebojno izključitev.
Java 5 je predstavila sinhronizacijsko alternativo, ki ponuja medsebojno izključitev v kombinaciji z zmogljivostjo hlapljivo
. To atomska spremenljivka Alternativa temelji na navodilu za primerjavo in zamenjavo mikroprocesorja in je v veliki meri sestavljena iz vrst v java.util.concurrent.atomic
paket.
Razumevanje primerjanja in zamenjave
The primerjaj in zamenjaj (CAS) Navodilo je neprekinjeno navodilo, ki bere pomnilniško lokacijo, primerja prebrano vrednost s pričakovano vrednostjo in shrani novo vrednost na mesto pomnilnika, ko se prebrana vrednost ujema s pričakovano vrednostjo. V nasprotnem primeru se nič ne naredi. Dejanska navodila mikroprocesorja se lahko nekoliko razlikujejo (npr. Vrnite true, če je CAS uspel, ali false drugače namesto prebrane vrednosti).
Navodila za mikroprocesor CAS
Sodobni mikroprocesorji ponujajo nekakšna navodila CAS. Na primer, mikroprocesorji Intel ponujajo cmpxchg
družina navodil, medtem ko mikroprocesorji PowerPC ponujajo povezavo med obremenitvijo (npr. lwarx
) in pogojno za shranjevanje (npr. stwcx
) navodila za isti namen.
CAS omogoča podporo atomskim zaporedjem branja-spreminjanja-pisanja. Običajno bi uporabljali CAS na naslednji način:
- Preberite vrednost v z naslova X.
- Izvedite večstopenjsko izračunavanje, da izpeljete novo vrednost v2.
- S CAS spremenite vrednost X iz v v v2. CAS uspe, ko se vrednost X med izvajanjem teh korakov ni spremenila.
Če želite videti, kako CAS ponuja boljšo zmogljivost (in razširljivost) v primerjavi s sinhronizacijo, si oglejte primer števca, ki vam omogoča, da preberete njegovo trenutno vrednost in povečate števec. Naslednji razred izvaja števec na osnovi sinhronizirano
:
Seznam 4. Counter.java (različica 1)
števec javnega razreda {private int value; javno sinhronizirano int getValue () {vrnjena vrednost; } javni sinhronizirani int inkrement () {return ++ vrednost; }}
Visoka prepirka za zaklepanje monitorja bo povzročila pretirano preklapljanje konteksta, ki lahko upočasni vse niti in povzroči slabo razšireno aplikacijo.
Alternativa CAS zahteva izvajanje navodil za primerjavo in zamenjavo. Naslednji razred posnema CAS. Uporablja sinhronizirano
namesto dejanskih navodil strojne opreme za poenostavitev kode:
Seznam 5. EmulatedCAS.java
javni razred EmulatedCAS {zasebna int vrednost; javno sinhronizirano int getValue () {vrnjena vrednost; } javno sinhronizirano int compareAndSwap (int pričakovanoVrednost, int novoVrednost) {int readValue = vrednost; če je (readValue == pričakovana vrednost) vrednost = newValue; vrni readValue; }}
Tukaj, vrednost
identificira pomnilniško mesto, ki ga lahko pridobi getValue ()
. Prav tako compareAndSwap ()
izvaja algoritem CAS.
Naslednji razred uporablja EmulatedCAS
izvajati ne-sinhronizirano
števec (pretvarjaj se EmulatedCAS
ne zahteva sinhronizirano
):
Seznam 6. Counter.java (različica 2)
števec javnega razreda {private EmulatedCAS value = new EmulatedCAS (); javni int getValue () {vrnitev value.getValue (); } javni int prirastek () {int readValue = value.getValue (); while (value.compareAndSwap (readValue, readValue + 1)! = readValue) readValue = value.getValue (); vrni readValue + 1; }}
Števec
enkapsulira EmulatedCAS
primerek in objavi metode za pridobivanje in priraščanje vrednosti števca s pomočjo tega primerka. getValue ()
pridobi "trenutna vrednost števca" in prirastek ()
varno poveča vrednost števca.
prirastek ()
večkrat prikliče compareAndSwap ()
do readValue
vrednost se ne spremeni. Nato lahko to vrednost spremenite. Kadar ne gre za zaklepanje, se izognemo prepirom skupaj s pretiranim preklapljanjem konteksta. Zmogljivost se izboljša in koda je bolj razširljiva.
ReentrantLock in CAS
Tega ste se že naučili ReentrantLock
ponuja boljše rezultate kot sinhronizirano
pod visoko prepirom niti. Če želite povečati zmogljivost, ReentrantLock
S sinhronizacijo upravlja podrazred povzetka java.util.concurrent.locks.AbstractQueuedSynchronizer
razred. Ta razred pa izkoristi nedokumentirano ned.misc. Nevarno
razred in njegovo compareAndSwapInt ()
CAS metoda.
Raziskovanje paketa atomskih spremenljivk
Ni vam treba izvajati compareAndSwap ()
prek neprenosljivega Java Native Interface. Namesto tega Java 5 to podporo ponuja prek java.util.concurrent.atomic
: zbirka orodij razredov, ki se uporabljajo za programiranje posameznih spremenljivk brez zaklepanja in brez varenj.
Po navedbah java.util.concurrent.atomic
je Javadoc, ti razredi
hlapljivo
vrednosti, polja in elemente matrike tistim, ki zagotavljajo tudi atomsko pogojno operacijo posodabljanja obrazca logična primerjavaAndSet (pričakovana vrednost, posodobitevVrednost)
. Ta metoda (ki se razlikuje v vrstah argumentov v različnih razredih) atomsko nastavi spremenljivko na updateValue
če trenutno vsebuje pričakovana vrednost
, poroča resnično o uspehu. Ta paket ponuja razrede za logično logiko (AtomicBoolean
), celo število (AtomicInteger
), dolgo celo število (AtomicLong
) in referenca (AtomicReference
) vrste. Ponuja tudi različice matrike celih, dolgih celih števil in referenc (AtomicIntegerArray
, AtomicLongArray
, in AtomicReferenceArray
), označljivi in žigosani referenčni razredi za atomsko posodabljanje para vrednosti (AtomicMarkableReference
in AtomicStampedReference
), in več.
Izvedba compareAndSet ()
Java implementira compareAndSet ()
prek najhitreje dostopnega izvornega konstrukta (npr. cmpxchg
ali load-link / store-conditional) ali (v najslabšem primeru) vrtljive ključavnice.
Razmislite AtomicInteger
, ki vam omogoča posodobitev int
vrednost atomsko. Ta razred lahko uporabimo za izvajanje števca, prikazanega na seznamu 6. Seznam 7 predstavlja enakovredno izvorno kodo.
Seznam 7. Counter.java (različica 3)
uvoz java.util.concurrent.atomic.AtomicInteger; javni razred Counter {private AtomicInteger value = new AtomicInteger (); public int getValue () {vrnitev value.get (); } javni int prirastek () {int readValue = value.get (); while (! value.compareAndSet (readValue, readValue + 1)) readValue = value.get (); vrni readValue + 1; }}
Seznam 7 je zelo podoben seznamu 6, le da ga nadomešča EmulatedCAS
s AtomicInteger
. Mimogrede, lahko poenostavite prirastek ()
Ker AtomicInteger
dobavlja svoje int getAndIncrement ()
metoda (in podobne metode).
Fork / Join framework
Računalniška strojna oprema se je močno razvila od prvega nastopa Jave leta 1995. Takrat so enoprocesorski sistemi prevladovali v računalniški krajini in Java-ovi primitivi za sinhronizacijo, kot je npr. sinhronizirano
in hlapljivo
, kot tudi knjižnica navojev ( Navoj
razred), so bili na splošno ustrezni.
Večprocesorski sistemi so se pocenili in razvijalci so se morali znajti v ustvarjanju aplikacij Java, ki so učinkovito izkoriščale vzporednost strojne opreme, ki so jo ponujali ti sistemi. Kmalu pa so ugotovili, da je bilo Java-jeve primitive in knjižnico z nizkimi nivoji navojev v tem kontekstu zelo težko uporabiti, zato so bile rešitve, ki izhajajo iz tega, pogosto prepletene z napakami.
Kaj je paralelizem?
Vzporednost je sočasno izvajanje več niti / nalog prek neke kombinacije več procesorjev in procesorskih jeder.
Okvir Java Concurrency Utilities poenostavlja razvoj teh aplikacij; vendar pripomočki, ki jih ponuja ta okvir, ne merijo na tisoče procesorjev ali procesorskih jeder. V naši večjedrni dobi potrebujemo rešitev za doseganje natančnejše vzporednosti ali pa obdelujemo procesorje v prostem teku, tudi če je z njimi veliko dela.
Rešitev tega problema je v svojem prispevku predstavil profesor Doug Lea, ki je predstavil idejo za ogrodje fork / join na osnovi Jave. Lea opisuje ogrodje, ki podpira "slog vzporednega programiranja, v katerem se težave rešujejo tako, da se (rekurzivno) razdelijo na podopravila, ki se rešujejo vzporedno." Okvir Fork / Join je bil sčasoma vključen v Javo 7.
Pregled ogrodja Fork / Join
Okvir Fork / Join temelji na posebni storitvi izvršitelja za izvajanje posebne vrste nalog. Sestavljen je iz naslednjih vrst, ki se nahajajo v java.util.concurrent
paket:
ForkJoinPool
: anExecutorService
izvajanje, ki tečeForkJoinTask
s.ForkJoinPool
ponuja metode oddaje nalog, kot sovoid izvedba (naloga ForkJoinTask)
, skupaj z metodami upravljanja in spremljanja, kot soint getParallelism ()
inlong getStealCount ()
.ForkJoinTask
: abstraktni osnovni razred za naloge, ki se izvajajo vForkJoinPool
kontekstu.ForkJoinTask
opisuje niti podobne entitete, ki imajo veliko lažjo težo kot običajne niti. Številne naloge in podopravila lahko gosti zelo malo dejanskih niti v aForkJoinPool
primer.ForkJoinWorkerThread
: razred, ki opisuje nit, ki jo upravljaForkJoinPool
primer.ForkJoinWorkerThread
je odgovoren za izvršitevForkJoinTask
s.Rekurzivno delovanje
: abstraktni razred, ki opisuje rekurzivni brez rezultatovForkJoinTask
.Rekurzivna naloga
: abstraktni razred, ki opisuje rekurzivno nošenje rezultatovForkJoinTask
.
The ForkJoinPool
Izvršilna služba je vstopna točka za oddajo nalog, ki so običajno opisane v podrazredih Rekurzivno delovanje
ali Rekurzivna naloga
. V zakulisju je naloga razdeljena na manjše naloge, ki so vilice (porazdeljeno med različne niti za izvedbo) iz področja. Naloga čaka do pridružil (njegova podopravila se končajo tako, da se lahko kombinirajo rezultati).
ForkJoinPool
upravlja področje delovnih niti, kjer ima vsaka delovna nit svojo dvojno delovno vrsto (deque). Ko naloga naloži novo podopravilo, nit potisne podopravilo na glavo njegovega okna. Ko se opravilo poskuša povezati z drugo nalogo, ki še ni končana, nit izstreli še eno nalogo z glave deque in jo izvede. Če je deque niti prazen, poskuša ukrasti drugo nalogo z repa deque druge niti. To krajo dela vedenje poveča pretočnost in hkrati zmanjša prepir.
Uporaba ogrodja Fork / Join
Fork / Join je bil zasnovan za učinkovito izvajanje deli in vladaj algoritme, ki probleme rekurzivno delijo na podprobleme, dokler niso dovolj preprosti za neposredno reševanje; na primer, združevanje. Rešitve teh podproblemov se kombinirajo, da se zagotovi rešitev prvotnega problema. Vsak podproblem se lahko samostojno izvede na drugem procesorju ali jedru.
Lea opisuje naslednjo psevdokodo, ki opisuje vedenje deli in vladaj:
Reševanje rezultatov (težava problema) {če (težava je majhna) težavo reši drugače {problem razdeli na neodvisne dele, razširi nove podopravila, da reši vsak del, združi vse podoprave, sestavi rezultat iz podresultov}}
Psevkodo predstavlja a rešiti
metoda, ki se imenuje z nekaterimi problem
rešiti in ki vrne a Rezultat
ki vsebuje problem
rešitev. Če je problem
premajhna za reševanje z vzporednostjo, rešena je neposredno. (Režijski stroški uporabe vzporednosti pri majhnem problemu presegajo vse pridobljene koristi.) V nasprotnem primeru je problem razdeljen na podopravila: vsak podopravek se neodvisno osredotoči na del problema.
Delovanje vilice
zažene novo podopravilo fork / join, ki se bo izvajalo vzporedno z drugimi podopravili. Delovanje pridruži se
zakasni trenutno opravilo, dokler razčlenjeno podopravilo ne konča. Na neki točki problem
bo dovolj majhen za zaporedno izvajanje, njegov rezultat pa bo združen z drugimi podrezultati, da se doseže splošna rešitev, ki se vrne klicatelju.
Javadoc za Rekurzivno delovanje
in Rekurzivna naloga
Predavanja predstavljajo nekaj primerov algoritma za deljenje in osvajanje, ki se izvajajo kot naloge fork / join. Za Rekurzivno delovanje
primeri razvrstijo matriko dolgih celih števil, povečajo vsak element v matriki in seštejejo kvadratke vsakega elementa v matriki dvojno
s. Rekurzivna naloga
osamljeni primer izračuna Fibonaccijevo število.
Seznam 8 predstavlja aplikacijo, ki prikazuje primer sortiranja v kontekstih, ki niso fork / join in fork / join. Predstavlja tudi nekaj časovnih informacij, ki so v nasprotju s hitrostmi razvrščanja.