Atominiai kintamieji
Daugiasluoksnės programos, veikiančios daugialypiuose procesoriuose arba daugiaprocesorinėse sistemose, gali gerai išnaudoti aparatinę įrangą ir būti labai keičiamos. Jie gali pasiekti šiuos tikslus, kai jų gijos praleidžia didžiąją laiko dalį atlikdami darbus, o ne laukia, kol darbas bus atliktas, arba laukia, kol įsigis spynas, kad galėtų pasiekti bendrąsias duomenų struktūras.
Tačiau „Java“ tradicinis sinchronizavimo mechanizmas, kuris įgyvendinamas abipusė atskirtis (siūlas, laikantis užraktą, kuris saugo kintamųjų rinkinį, turi išskirtinę prieigą prie jų) ir matomumas (saugomų kintamųjų pakeitimai tampa matomi kitoms gijoms, kurios vėliau įgyja spyną), daro įtaką aparatūros naudojimui ir masteliui taip:
- Teigiama sinchronizacija (kelios gijos, nuolat konkuruojančios dėl spynos) yra brangu, todėl nukenčia pralaidumas. Pagrindinė išlaidų priežastis yra dažnas konteksto keitimas; konteksto perjungimo operacijai atlikti gali prireikti daug procesoriaus ciklų. Priešingai, nekontroliuojamas sinchronizavimas yra nebrangus šiuolaikiniams JVM.
- Kai užrakto laikymo gija atidedama (pvz., Dėl planavimo vėlavimo), nė viena gija, kuriai reikalingas užraktas, nepadaro jokios pažangos ir aparatinė įranga nėra naudojama taip gerai, kaip galėtų būti kitaip.
Galite pagalvoti, kad galite naudoti nepastovus kaip sinchronizavimo alternatyva. Tačiau nepastovus kintamieji sprendžia tik matomumo problemą. Jie negali būti naudojami saugiai įgyvendinti atomines skaitymo, modifikavimo ir rašymo sekas, kurios yra būtinos saugiam skaitiklių ir kitų objektų, kuriems reikia abipusės pašalinimo, įgyvendinimui.
„Java 5“ pristatė sinchronizavimo alternatyvą, kuri siūlo abipusę atskirtį kartu su „Windows“ veikimu nepastovus. Tai atominis kintamasis alternatyva yra pagrįsta mikroprocesoriaus palyginimo ir keitimo instrukcija ir daugiausia susideda iš tipų java.util.concurrent.atomic pakuotė.
Suprasti palyginimą ir apsikeitimą
palyginti ir keistis (CAS) instrukcija yra nepertraukiama instrukcija, nuskaitanti atminties vietą, palyginanti perskaitytą reikšmę su laukiama verte ir išsauganti naują vertę atminties vietoje, kai perskaityta vertė atitinka numatomą vertę. Priešingu atveju nieko nedaroma. Tikroji mikroprocesoriaus instrukcija gali šiek tiek skirtis (pvz., Grąžinti teisingą, jei CAS pavyko ar klaidinga, vietoj nuskaitytos vertės).
Mikroprocesoriaus CAS instrukcijos
Šiuolaikiniai mikroprocesoriai siūlo tam tikrą CAS instrukciją. Pavyzdžiui, „Intel“ mikroprocesoriai siūlo cmpxchg instrukcijų šeima, o „PowerPC“ mikroprocesoriai siūlo „load-link“ (pvz., žvynelis) ir parduotuvėje su sąlyga (pvz., stwcx) to paties tikslo instrukcijos.
CAS leidžia palaikyti atomines skaitymo, modifikavimo ir rašymo sekas. Paprastai naudosite CAS taip:
- Skaitykite v reikšmę iš adreso X.
- Atlikite daugiapakopį skaičiavimą, kad gautumėte naują reikšmę v2.
- Naudokite CAS, kad pakeistumėte X reikšmę iš v į v2. CAS pavyksta, kai atliekant šiuos veiksmus X vertė nepasikeitė.
Norėdami sužinoti, kaip CAS siūlo geresnį našumą (ir mastelį) per sinchronizavimą, apsvarstykite skaitiklio pavyzdį, kuris leidžia jums perskaityti dabartinę jo vertę ir padidinti skaitiklį. Ši klasė įgyvendina skaitiklį pagal sinchronizuotas:
4 sąrašas. Counter.java (1 versija)
public class Skaitliukas {private int value; public synchronized int getValue () {return value; } viešasis sinchronizuotas int prieaugis () {return ++ value; }}Didelė konkurencija dėl monitoriaus užrakto sukels pernelyg didelį konteksto perjungimą, kuris gali atitolinti visas gijas ir sukelti netinkamo mastelio programą.
CAS alternatyvai reikia įdiegti palyginimo ir keitimo instrukciją. Ši klasė imituoja CAS. Jis naudoja sinchronizuotas vietoj faktinės aparatinės įrangos instrukcijos kodui supaprastinti:
Sąrašas 5. „EmulatedCAS.java“
viešoji klasė „EmulatedCAS“ {private int value; public synchronized int getValue () {return value; } viešasis sinchronizuotas int palyginkAndSwap (int numatomaValue, int naujaVertė) {int skaitymoVertė = reikšmė; if (readValue == numatomaValue) reikšmė = newValue; grąžinti readValue; }} Čia vertė identifikuoja atminties vietą, kurią gali gauti getValue (). Be to, palygintiAndSwap () įgyvendina CAS algoritmą.
Ši klasė naudoja „EmulatedCAS“ įgyvendinti nesinchronizuotas skaitiklis (apsimesk „EmulatedCAS“ nereikalauja sinchronizuotas):
6 sąrašas. Counter.java (2 versija)
public class Counter {private EmulatedCAS value = new EmulatedCAS (); public int getValue () {return value.getValue (); } public int prieaugis () {int readValue = value.getValue (); while (value.compareAndSwap (readValue, readValue + 1)! = readValue) readValue = value.getValue (); grąžinti readValue + 1; }}Skaitliukas apgaubia „EmulatedCAS“ egzempliorius ir paskelbia metodus, kaip nuskaityti ir padidinti skaitiklio vertę, naudojant šio egzemplioriaus pagalbą. getValue () nuskaito egzemplioriaus „dabartinę skaitiklio vertę“ ir prieaugis () saugiai padidina skaitiklio vertę.
prieaugis () pakartotinai kviečia palygintiAndSwap () iki readValuevertė nesikeičia. Tada galite laisvai pakeisti šią vertę. Kai nėra užrakto, išvengiama ginčų ir per didelio konteksto perjungimo. Našumas gerėja, o kodas yra labiau keičiamo dydžio.
„ReentrantLock“ ir CAS
Anksčiau to išmokote „ReentrantLock“ siūlo geresnį našumą nei sinchronizuotas esant dideliems siūlams. Norėdami padidinti našumą, „ReentrantLock“Sinchronizavimą valdo abstrakto poklasis java.util.concurrent.locks.AbstractQueuedSynchronizer klasė. Savo ruožtu ši klasė naudoja dokumentus be dokumentų sun.misc.Nesaugu klasė ir jos palygintiAndSwapInt () CAS metodas.
Atominių kintamųjų paketo tyrimas
Jums nereikia įgyvendinti palygintiAndSwap () per nešiojamą „Java Native Interface“. Vietoj to, „Java 5“ siūlo šį palaikymą per java.util.concurrent.atomic: klasių įrankių rinkinys, naudojamas vieniems kintamiesiems programuoti be užrakinimo, siūlų saugumui.
Pagal java.util.concurrent.atomicJavadoc, šios klasės
nepastovus reikšmes, laukus ir masyvo elementus tiems, kurie taip pat teikia formos atomo sąlyginio atnaujinimo operaciją loginis palygintiAndSet (numatytasValue, updateValue). Šis metodas (kuris skiriasi pagal argumentų tipus skirtingose klasėse) iš esmės nustato kintamąjį į updateValue jei šiuo metu ji turi tikėtina vertė, praneša apie sėkmę. Šiame pakete siūlomos „Boolean“ („AtomicBoolean“), sveikasis skaičius (AtomicInteger), ilgasis sveikasis skaičius (AtomicLong) ir nuoroda (AtomicReference) tipai. Ji taip pat siūlo masyvo sveiko skaičiaus, ilgojo sveiko skaičiaus ir nuorodos („AtomicIntegerArray“, „AtomicLongArray“ir „AtomicReferenceArray“), žymimos ir antspauduotos atskaitos klasės, skirtos atominei porai verčių atnaujinti („AtomicMarkableReference“ ir AtomicStampedReference), ir dar.
„Salīdzinti“ ir „Set“ () diegimas
Java įgyvendina palygintiAndSet () per greičiausią galimą savąjį konstrukciją (pvz., cmpxchg arba „load-link / store-conditional“) arba (blogiausiu atveju) verpimo spynos.
Apsvarstykite AtomicInteger, kuris leidžia atnaujinti tarpt vertė atomiškai. Šią klasę galime panaudoti skaitikliui, parodytam 6 sąraše. 7 sąraše pateikiamas lygiavertis šaltinio kodas.
7 sąrašas. Counter.java (3 versija)
importuoti java.util.concurrent.atomic.AtomicInteger; public class Counter {private AtomicInteger value = new AtomicInteger (); public int getValue () {return value.get (); } public int prieaugis () {int readValue = value.get (); while (! value.compareAndSet (readValue, readValue + 1)) readValue = value.get (); grąžinti readValue + 1; }} 7 sąrašas labai panašus į 6 sąrašą, išskyrus tai, kad jis pakeičia „EmulatedCAS“ su AtomicInteger. Beje, galite supaprastinti prieaugis () nes AtomicInteger tiekia savo int getAndIncrement () metodas (ir panašūs metodai).
„Fork / Join“ sistema
Kompiuterinė aparatinė įranga gerokai patobulėjo nuo „Java“ debiuto 1995 m. Tais laikais vieno procesoriaus sistemos dominavo skaičiavimo srityje ir „Java“ sinchronizavimo primityviuose, pvz., sinchronizuotas ir nepastovus, taip pat jo gijų biblioteka ( Siūlas klasės), paprastai buvo tinkami.
Daugiaprocesorinės sistemos atpigo ir kūrėjams reikėjo sukurti „Java“ programas, kurios efektyviai išnaudotų šių sistemų siūlomą aparatūros lygiagretumą. Tačiau jie netrukus atrado, kad „Java“ žemo lygio sriegimo primityvus ir biblioteką šiame kontekste buvo labai sunku naudoti, o gautuose sprendimuose dažnai buvo klaidų.
Kas yra lygiagretumas?
Lygiagretumas yra tuo pačiu metu vykdomas kelias gijas / užduotis naudojant kelis procesorius ir procesoriaus šerdis.
„Java Concurrency Utilities“ sistema supaprastina šių programų kūrimą; tačiau šios sistemos siūlomos komunalinės paslaugos nesiekia tūkstančių procesorių ar procesoriaus branduolių. Mūsų daugelio branduolių eroje mums reikia sprendimo, kaip pasiekti tikslesnį lygiagretumą, arba rizikuojame palaikyti procesorius tuščiąja eiga net tada, kai jiems tenka daug dirbti.
Profesorius Dougas Lea savo darbe pristatė šios problemos sprendimą, pristatydamas „Java“ pagrindu sukurtos šakės / prisijungimo sistemos idėją. Lea apibūdina sistemą, palaikančią „lygiagretaus programavimo stilių, kuriame problemos sprendžiamos (rekursyviai) skaidant jas į lygiagrečiai išspręstas užduotis“. „Fork / Join“ karkasas galiausiai buvo įtrauktas į „Java 7“.
„Fork / Join“ sistemos apžvalga
„Fork / Join“ sistema yra pagrįsta specialia vykdytojo paslauga, skirta vykdyti ypatingos rūšies užduotis. Jis susideda iš šių tipų, esančių java.util.sąlyga paketas:
„ForkJoinPool“: anExecutorServicevykdomas įgyvendinimas„ForkJoinTask“s.„ForkJoinPool“pateikia užduočių pateikimo metodus, tokius kaipvoid execute („ForkJoinTask“ užduotis), kartu su valdymo ir stebėjimo metodais, tokiais kaipint getParallelism ()irilgas „getStealCount“ ().„ForkJoinTask“: abstrakti pagrindinė užduočių, vykdomų per a, klasė„ForkJoinPool“kontekste.„ForkJoinTask“apibūdina į siūlus panašius objektus, kurių svoris yra daug mažesnis nei įprastų siūlų. Daugelį užduočių ir antrinių užduočių gali priglobti labai nedaug faktinių a„ForkJoinPool“instancija.„ForkJoinWorkerThread“: klasė, apibūdinanti giją, kurią valdo a„ForkJoinPool“instancija.„ForkJoinWorkerThread“yra atsakingas už vykdymą„ForkJoinTask“s.Rekursinis veiksmas: abstrakti klasė, kurioje aprašomas rekursinis rezultatas be rezultatų„ForkJoinTask“.RecursiveTask: abstrakti klasė, apibūdinanti rekursinį rezultatą„ForkJoinTask“.
„ForkJoinPool“ vykdytojo paslauga yra pradinis taškas pateikiant užduotis, kurios paprastai apibūdinamos Rekursinis veiksmas arba RecursiveTask. Užkulisiuose užduotis yra padalinta į mažesnes užduotis, kurios yra šakėmis (paskirstytas skirtingoms gijoms vykdyti) iš telkinio. Užduotis laukia, kol prisijungė (jos užduotys baigiamos, kad būtų galima derinti rezultatus).
„ForkJoinPool“ valdo darbininkų gijų grupę, kur kiekviena darbuotojo gija turi savo dvigubą darbo eilę (deque). Kai užduotis išsišakoja naują antrinę užduotį, gija pastumia antrinę užduotį ant jos išardymo galvos. Kai užduotis bando prisijungti prie kitos neužbaigtos užduoties, gija iššoka kitą užduotį nuo jos pabaigos ir vykdo užduotį. Jei gijos deque yra tuščia, ji bando pavogti kitą užduotį iš kitos gijos deque uodegos. Tai darbo vagystė elgesys maksimaliai padidina pralaidumą, tuo pačiu sumažinant ginčus.
„Fork / Join“ sistemos naudojimas
„Fork / Join“ sukurta efektyviai vykdyti skaldyk ir užvaldyk algoritmus, kuris rekursyviai skirsto problemas į subproblemas, kol jos yra pakankamai paprastos, kad jas būtų galima tiesiogiai išspręsti; pavyzdžiui, suliejimo rūšis. Šių papildomų problemų sprendimai yra derinami, kad būtų pateiktas pirminės problemos sprendimas. Kiekviena subproblema gali būti vykdoma atskirai, naudojant skirtingą procesorių ar branduolį.
Lea darbe pateikiamas šis pseudokodas, apibūdinantis padalijimo ir užkariavimo elgesį:
Rezultato sprendimas (problemos problema) {jei (problema yra maža) tiesiogiai išspręskite problemą kita {išskaidykite problemą į savarankiškas dalis, kad išspręstumėte naujas paprogrames, kad išspręstumėte kiekvieną dalį, sujunkite visas antrines užduotis, sukurkite rezultatą subresults}} Pseudokodas pateikia a išspręsti metodas, kuris vadinamas kai kuriais problema išspręsti ir kuris grąžina a Rezultatas kuriame yra problemasprendimas. Jei problema yra per mažas, kad būtų galima išspręsti per lygiagretumą, jis išspręstas tiesiogiai. (Lygiagretumo mažoje problemoje naudojimas viršija bet kokią gautą naudą.) Priešingu atveju problema yra suskirstyta į užduotis: kiekviena užduotis savarankiškai sutelkia dėmesį į dalį problemos.
Operacija šakutė paleidžia naują šakės / prisijungimo antrinę užduotį, kuri bus vykdoma lygiagrečiai su kitomis antrinėmis užduotimis. Operacija prisijungti atideda dabartinę užduotį, kol baigsis šakotas antrinis uždavinys. Tam tikru momentu problema bus pakankamai mažas, kad būtų galima vykdyti nuosekliai, o jo rezultatas bus sujungtas su kitais pavėluotais rezultatais, kad būtų pasiektas bendras sprendimas, kuris būtų grąžintas skambinančiajam.
Javadoc for the Rekursinis veiksmas ir RecursiveTask klasėse pateikiami keli padalijimo ir užkariavimo algoritmo pavyzdžiai, įgyvendinami kaip šakės / prisijungimo užduotys. Dėl Rekursinis veiksmas pavyzdžiai rūšiuoja ilgų sveikųjų skaičių masyvą, padidina kiekvieną masyvo elementą ir susumuoja kiekvieno elemento kvadratus dvigubais. RecursiveTaskVienintelis pavyzdys apskaičiuoja Fibonači skaičių.
8 sąraše pateikiama programa, parodanti rūšiavimo pavyzdį ne šakės / jungties, taip pat šakės / prisijungimo kontekstuose. Taip pat pateikiama tam tikra laiko informacija, kad būtų galima palyginti rūšiavimo greitį.
