Ohjelmointi

Java 101: Java-samanaikaisuus ilman kipua, osa 2

Edellinen 1 2 3 4 Sivu 3 Seuraava Sivu 3/4

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:

  1. Lue arvo v osoitteesta X.
  2. Suorita monivaiheinen laskenta uuden arvon v2 saamiseksi.
  3. 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 readValuearvo 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 ReentrantLockSynkronointia 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.atomicJavadoc, nämä luokat

laajentaa käsitystä 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, AtomicLongArrayja 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: an ExecutorService toteutettava toteutus HaarukkaLiity Tehtäväs. HaarukkaLiity uima-allas tarjoaa tehtävänlähetysmenetelmiä, kuten void execute (ForkJoinTask-tehtävä)sekä hallinto- ja seurantamenetelmät, kuten int getParallelism () ja pitkä getStealCount ().
  • HaarukkaLiity Tehtävä: abstrakti perusluokka tehtäville, jotka suoritetaan a: ssa HaarukkaLiity 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: ssa HaarukkaLiity uima-allas ilmentymä.
  • HaarukkaJoinWorkerThread: luokka, joka kuvaa a: n hallinnoimaa ketjua HaarukkaLiity uima-allas ilmentymä. HaarukkaJoinWorkerThread on vastuussa suorittamisesta HaarukkaLiity Tehtäväs.
  • Rekursiivinen toiminta: abstrakti luokka, joka kuvaa rekursiivista tulosta HaarukkaLiity Tehtävä.
  • Rekursiivinen tehtävä: abstrakti luokka, joka kuvaa rekursiivista tuloksen kantamista HaarukkaLiity 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ää ongelmaratkaisu. 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 kaksinkertainens. 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.