Atomimuuttujat
Monisäikeisillä sovelluksilla, jotka toimivat moniytimisillä prosessoreilla tai moniprosessorijärjestelmillä, voidaan saavuttaa hyvä laitteiston käyttö ja olla erittäin skaalautuvia. He voivat saavuttaa nämä tavoitteet siten, että ketjut viettävät suurimman osan ajastaan työn suorittamiseen pikemminkin kuin odottavat työn suorittamista tai odottavat lukkojen hankkimista jaettujen tietorakenteiden käyttämiseksi.
Javan perinteinen synkronointimekanismi, joka kuitenkin toimii yhteinen poissulkeminen (langalla, jolla lukkoa pidetään muuttujien joukossa, on yksinoikeus käyttää niitä) ja näkyvyys (muutokset vartioituihin muuttujiin tulevat näkyville muille lukkoon myöhemmin saaneille säikeille), vaikuttaa laitteiston käyttöön ja skaalautuvuuteen seuraavasti:
- Väitetty synkronointi (useat langat kilpailevat jatkuvasti lukosta) on kallista, ja sen vuoksi läpäisykyky kärsii. Tärkein syy kustannuksiin on usein tapahtuva kontekstinvaihto; kontekstikytkennän suorittaminen voi kestää useita prosessorisyklejä. Verrattuna, jatkumaton synkronointi on edullinen nykyaikaisissa JVM: issä.
- Kun lukkoa pitävä säie viivästyy (esim. Ajoitusviiveen takia), mikään lukitusta vaativa säie ei edisty, eikä laitteistoa käytetä niin hyvin kuin muuten voisi olla.
Saatat ajatella, että voit käyttää haihtuva
synkronointivaihtoehtona. Kuitenkin, haihtuva
muuttujat ratkaisevat vain näkyvyysongelman. Niitä ei voida käyttää atomien luku-, muokkaus- ja kirjoitusjaksojen turvalliseen toteuttamiseen, jotka ovat tarpeen laskureiden ja muiden keskinäistä poissulkemista vaativien entiteettien turvalliseen toteuttamiseen.
Java 5 esitteli synkronointivaihtoehdon, joka tarjoaa keskinäisen poissulkemisen yhdistettynä haihtuva
. Tämä atomimuuttuja Vaihtoehto perustuu mikroprosessorin vertailu- ja vaihtokäskyihin ja koostuu suurelta osin java.util.concurrent.atomic
paketti.
Ymmärrä vertailu ja vaihto
vertaa ja vaihda (CAS) käsky on keskeytymätön käsky, joka lukee muistipaikan, vertaa luettua arvoa odotettuun arvoon ja tallentaa uuden arvon muistipaikkaan, kun luettu arvo vastaa odotettua arvoa. Muuten mitään ei tehdä. Varsinainen mikroprosessorikäsky voi poiketa jonkin verran (esim. Palauta true, jos CAS onnistui tai väärä muuten luetun arvon sijaan).
Mikroprosessorin CAS-ohjeet
Nykyaikaiset mikroprosessorit tarjoavat jonkinlaista CAS-ohjetta. Esimerkiksi Intel-mikroprosessorit tarjoavat cmpxchg
ohjeet, kun taas PowerPC-mikroprosessorit tarjoavat latauslinkin (esim. lwarx
) ja ehdollinen myymälälle (esim. stwcx
) ohjeet samaan tarkoitukseen.
CAS mahdollistaa atomien luku-, muokkaus- ja kirjoitusjaksojen tukemisen. Käytät yleensä CAS: ta seuraavasti:
- Lue arvo v osoitteesta X.
- Suorita monivaiheinen laskenta uuden arvon v2 saamiseksi.
- Muuta X: n arvo v: stä v2: ksi CAS: llä. CAS onnistuu, kun X: n arvo ei ole muuttunut suoritettaessa näitä vaiheita.
Jos haluat nähdä, kuinka CAS tarjoaa paremman suorituskyvyn (ja skaalautuvuuden) synkronoinnin aikana, harkitse laskuriesimerkkiä, jonka avulla voit lukea sen nykyisen arvon ja lisätä laskuria. Seuraava luokka toteuttaa laskurin, joka perustuu synkronoitu
:
Listaus 4. Counter.java (versio 1)
julkinen luokka Laskuri {private int value; julkinen synkronoitu int getValue () {return value; } julkinen synkronoitu int-lisäys () {return ++ value; }}
Näytön lukituksen suuri kilpailu johtaa liialliseen tilanvaihtoon, mikä voi viivästyttää kaikkia ketjuja ja johtaa sovellukseen, joka ei skaalaa hyvin.
CAS-vaihtoehto vaatii vertailu- ja vaihtokäskyn toteuttamisen. Seuraava luokka jäljittelee CAS: ää. Se käyttää synkronoitu
todellisen laitteisto-ohjeen sijaan koodin yksinkertaistamiseksi:
Listaus 5. EmulatedCAS.java
julkinen luokka EmulatedCAS {private int value; julkinen synkronoitu int getValue () {return value; } julkinen synkronoitu int verrattAndSwap (int odotettavissa oleva arvo, int uusi arvo) {int lukema = arvo; if (lukuarvo == odotettavissa oleva arvo) arvo = uusi arvo; return readValue; }}
Tässä, arvo
tunnistaa muistipaikan, jonka voi noutaa getValue ()
. Myös, vertaaAndSwap ()
toteuttaa CAS-algoritmin.
Seuraava luokka käyttää Emuloitu CAS
toteuttaasynkronoitu
laskuri (teeskennellä sitä Emuloitu CAS
ei vaadi synkronoitu
):
Listaus 6. Counter.java (versio 2)
julkinen luokka Laskuri {private EmulatedCAS value = new EmulatedCAS (); public int getValue () {return value.getValue (); } public int increment () {int readValue = value.getValue (); while (value.compareAndSwap (readValue, readValue + 1)! = readValue) readValue = value.getValue (); paluu readValue + 1; }}
Laskuri
kapseloi Emuloitu CAS
ja julistaa menetelmät laskurin arvon noutamiseksi ja lisäämiseksi tämän ilmentymän avulla. getValue ()
hakee ilmentymän "nykyisen laskurin arvon" ja lisäys ()
lisää laskurin arvoa turvallisesti.
lisäys ()
toistuvasti vertaaAndSwap ()
siihen asti kun readValue
arvo ei muutu. Sitten on vapaa muuttaa tätä arvoa. Kun lukitusta ei ole, kiistelyä ja liiallista tilanvaihtoa vältetään. Suorituskyky paranee ja koodi on skaalautuvampi.
ReentrantLock ja CAS
Olet aiemmin oppinut sen ReentrantLock
tarjoaa paremman suorituskyvyn kuin synkronoitu
korkean langankilpailun alla. Suorituskyvyn parantamiseksi ReentrantLock
Synkronointia hallitsee abstraktin alaluokka java.util.concurrent.locks.AbstractQueuedSynchronizer
luokassa. Tämä luokka puolestaan hyödyntää dokumentoimattomia sun.misc. vaarallinen
luokka ja sen vertaaAndSwapInt ()
CAS-menetelmä.
Atomimuuttujapaketin tutkiminen
Sinun ei tarvitse toteuttaa vertaaAndSwap ()
ei-kannettavan Java Native Interface -liitännän kautta. Sen sijaan Java 5 tarjoaa tämän tuen kautta java.util.concurrent.atomic
: työkaluryhmä luokista, joita käytetään lukitsemattomaan, langattomaan ohjelmointiin yksittäisille muuttujille.
Mukaan java.util.concurrent.atomic
Javadoc, nämä luokat
haihtuva
arvot, kentät ja taulukkoelementit niille, jotka tarjoavat myös lomakkeen ehdollisen ehdollisen päivitysoperaation looginen vertailuAndSet (odotettavissa oleva arvo, päivitysarvo)
. Tämä menetelmä (joka vaihtelee argumenttityypeittäin eri luokissa) asettaa atomimuuttujan arvoksi updateValue
jos sillä on tällä hetkellä odotettu arvo
, raportoi tosi menestyksestä. Tämä paketti tarjoaa luokat Boolean (AtomicBoolean
), kokonaisluku (AtomicInteger
), pitkä kokonaisluku (AtomicPitkä
) ja viite (AtomicReference
) tyypit. Se tarjoaa myös kokonaisluvun, pitkän kokonaisluvun ja viitteen (AtomicIntegerArray
, AtomicLongArray
ja AtomicReferenceArray
), merkittävät ja leimatut vertailuluokat arvoparin päivittämiseen atomisesti (AtomicMarkableReference
ja AtomicStampedReference
), ja enemmän.
VertailuAndSetin () käyttöönotto
Java toteuttaa vertaa ja asettaa ()
nopeimman saatavilla olevan natiivirakenteen kautta (esim. cmpxchg
tai latauslinkki / kauppaehtoinen) tai (pahimmassa tapauksessa) pyöritä lukot.
Harkitse AtomicInteger
, jonka avulla voit päivittää int
arvo atomisesti. Voimme käyttää tätä luokkaa toteuttamaan luettelossa 6 esitetyn laskurin. Listaus 7 esittää vastaavan lähdekoodin.
Listaus 7. Counter.java (versio 3)
tuo java.util.concurrent.atomic.AtomicInteger; julkinen luokka Laskuri {private AtomicInteger value = new AtomicInteger (); public int getValue () {return value.get (); } public int increment () {int readValue = value.get (); while (! value.compareAndSet (readValue, readValue + 1)) readValue = arvo.get (); paluu readValue + 1; }}
Listaus 7 on hyvin samanlainen kuin Listaus 6 paitsi että se korvaa Emuloitu CAS
kanssa AtomicInteger
. Voit muuten yksinkertaistaa lisäys ()
koska AtomicInteger
toimittaa omat int getAndIncrement ()
menetelmä (ja vastaavat menetelmät).
Haarukka / Liity-kehys
Tietokonelaitteisto on kehittynyt merkittävästi Javan debyytin jälkeen vuonna 1995. Tuolloin yhden prosessorin järjestelmät hallitsivat tietojenkäsittelyympäristöä ja Javan synkronointiprimitiivejä, kuten synkronoitu
ja haihtuva
, samoin kuin sen langankirjasto ( Lanka
luokka) olivat yleensä riittäviä.
Moniprosessorijärjestelmät halpenivat, ja kehittäjät huomasivat tarvitsevansa luoda Java-sovelluksia, jotka hyödyntivät tehokkaasti näiden järjestelmien tarjoamaa laitteiston rinnakkaisuutta. Pian he kuitenkin havaitsivat, että Javan matalan tason ketjutuksen primitiivejä ja kirjastoa oli erittäin vaikea käyttää tässä yhteydessä, ja tuloksena olleissa ratkaisuissa oli usein virheitä.
Mikä on rinnakkaisuus?
Rinnakkaisuus on useiden ketjujen / tehtävien samanaikainen suorittaminen jonkin prosessorin ja prosessoriydinten yhdistelmän kautta.
Java Concurrency Utilities -kehys yksinkertaistaa näiden sovellusten kehittämistä; tämän kehyksen tarjoamat apuohjelmat eivät kuitenkaan laajene tuhansiin prosessoreihin tai prosessorin ytimiin. Monen ytimen aikakaudellamme tarvitsemme ratkaisun hienomman rinnakkaisuuden saavuttamiseksi, tai vaarana on pitää prosessorit joutokäynnillä, vaikka heillä olisi paljon työtä.
Professori Doug Lea esitti ratkaisun tähän ongelmaan artikkelissaan, jossa esiteltiin ajatus Java-pohjaiseen haarukka- / liittymiskehykseen. Lea kuvaa kehystä, joka tukee "rinnakkaisen ohjelmoinnin tyyliä, jossa ongelmat ratkaistaan jakamalla (rekursiivisesti) ne rinnakkain ratkaistaviksi alatehtäviksi". Fork / Join -kehys sisältyi lopulta Java 7: ään.
Yleiskatsaus Fork / Join-kehykseen
Fork / Join-kehys perustuu erityiseen toimeenpanopalveluun erityistehtävän suorittamiseksi. Se koostuu seuraavista tyyppeistä, jotka sijaitsevat java.util.concurrent
paketti:
HaarukkaLiity uima-allas
: anExecutorService
toteutettava toteutusHaarukkaLiity Tehtävä
s.HaarukkaLiity uima-allas
tarjoaa tehtävänlähetysmenetelmiä, kutenvoid execute (ForkJoinTask-tehtävä)
sekä hallinto- ja seurantamenetelmät, kutenint getParallelism ()
japitkä getStealCount ()
.HaarukkaLiity Tehtävä
: abstrakti perusluokka tehtäville, jotka suoritetaan a: ssaHaarukkaLiity uima-allas
yhteydessä.HaarukkaLiity Tehtävä
kuvaa lankamaisia kokonaisuuksia, joilla on paljon kevyempi paino kuin tavallisilla langoilla. Monia tehtäviä ja alitehtäviä voi isännöidä hyvin harvoilla todellisilla ketjuilla a: ssaHaarukkaLiity uima-allas
ilmentymä.HaarukkaJoinWorkerThread
: luokka, joka kuvaa a: n hallinnoimaa ketjuaHaarukkaLiity uima-allas
ilmentymä.HaarukkaJoinWorkerThread
on vastuussa suorittamisestaHaarukkaLiity Tehtävä
s.Rekursiivinen toiminta
: abstrakti luokka, joka kuvaa rekursiivista tulostaHaarukkaLiity Tehtävä
.Rekursiivinen tehtävä
: abstrakti luokka, joka kuvaa rekursiivista tuloksen kantamistaHaarukkaLiity Tehtävä
.
HaarukkaLiity uima-allas
toteuttajapalvelu on lähtökohta tehtävien lähettämiselle, jotka tyypillisesti kuvataan alaluokilla Rekursiivinen toiminta
tai Rekursiivinen tehtävä
. Kulissien takana tehtävä on jaettu pienempiin tehtäviin haarukkainen (jaettu eri säikeiden kesken suoritettavaksi) poolista. Tehtävä odottaa liittyi (sen alitehtävät päättyvät, jotta tulokset voidaan yhdistää).
HaarukkaLiity uima-allas
hallinnoi työntekijälankojen ryhmää, jossa jokaisella työntekijälangalla on oma kaksipäinen työjono (deque). Kun tehtävä haarautuu uuteen alatehtävään, lanka työntää alitehtävän purkamisen päähän. Kun tehtävä yrittää liittyä toiseen tehtävään, joka ei ole vielä valmis, ketju pudottaa toisen tehtävän irti päähänsä ja suorittaa tehtävän. Jos ketjun purku on tyhjä, se yrittää varastaa toisen tehtävän toisen säikeen jäljen hännästä. Tämä työn varastaminen käyttäytyminen maksimoi läpäisykyvyn ja minimoi kiistat.
Fork / Join-kehyksen käyttäminen
Fork / Join on suunniteltu toteuttamaan tehokkaasti jaa ja hallitse algoritmit, joka jakaa ongelmat rekursiivisesti alaongelmiin, kunnes ne ovat riittävän yksinkertaisia ratkaistavaksi suoraan; esimerkiksi yhdistämislaji. Näiden alaongelmien ratkaisut yhdistetään tarjoamaan ratkaisu alkuperäiseen ongelmaan. Jokainen alaongelma voidaan suorittaa itsenäisesti eri prosessorilla tai ytimellä.
Lea: n paperi esittää seuraavan näennäiskoodin kuvaamaan jakamisen ja valloittamisen käyttäytymistä:
Tuloksen ratkaisu (Ongelmaongelma) {jos (ongelma on pieni) suoraan ratkaise ongelma muu {jaa ongelma itsenäisiksi osiksi, haaroita uudet alitehtävät, jotta jokainen osa ratkaistaan, liity kaikkiin alitehtäviin, kirjoita tulos aliedoksista}}
Pseudokoodi esittää a ratkaista
menetelmä, jota kutsutaan joidenkin kanssa ongelma
ratkaista ja joka palauttaa a Tulos
joka sisältää ongelma
ratkaisu. Jos ongelma
on liian pieni ratkaistavaksi rinnakkaisuuden kautta, se ratkaistaan suoraan. (Rinnakkaisuuden käyttäminen pienten ongelmien yhteydessä ylittää saavutetun hyödyn.) Muuten ongelma jaetaan alitehtäviin: kukin osa-tehtävä keskittyy itsenäisesti osaan ongelmaa.
Operaatio haarukka
käynnistää uuden haarukka / liity-alatehtävän, joka suoritetaan rinnakkain muiden alitehtävien kanssa. Operaatio liittyä seuraan
viivästyttää nykyistä tehtävää, kunnes haaroitettu alatehtävä on valmis. Jossain vaiheessa ongelma
on tarpeeksi pieni suoritettavaksi peräkkäin, ja sen tulos yhdistetään yhdessä muiden alitulosten kanssa saavuttaakseen kokonaisratkaisun, joka palautetaan soittajalle.
Javadoc for the Rekursiivinen toiminta
ja Rekursiivinen tehtävä
luokat esittelee useita jakamisen ja valloittamisen algoritmiesimerkkejä, jotka on toteutettu haarukka / liity tehtävinä. Sillä Rekursiivinen toiminta
esimerkit lajittelevat matriisin pitkiä kokonaislukuja, lisäävät matriisin kutakin elementtiä ja summaavat kunkin elementin neliöt kaksinkertainen
s. Rekursiivinen tehtävä
Yksinäinen esimerkki laskee Fibonacci-luvun.
Listaus 8 esittää sovelluksen, joka näyttää lajitteluesimerkin ei-haarukka- / liittymis- sekä haarukka- / liittymiskonteksteissa. Siinä on myös joitain ajoitustietoja lajittelunopeuksien vertailemiseksi.