Atómové premenné
Viacvláknové aplikácie, ktoré bežia na viacjadrových procesoroch alebo na viacprocesorových systémoch, môžu dosiahnuť dobré využitie hardvéru a byť vysoko škálovateľné. Tieto ciele môžu dosiahnuť tým, že svoje vlákna strávia väčšinu času vykonávaním práce, a nie čakaním na dokončenie práce, alebo čakaním na získanie zámkov, aby získali prístup k zdieľaným dátovým štruktúram.
Avšak, Java je tradičný synchronizačný mechanizmus, ktorý vynucuje vzájomné vylúčenie (závit, ktorý drží zámok strážiaci skupinu premenných, má k nim výlučný prístup) a viditeľnosť (zmeny strážených premenných sa stanú viditeľnými pre ďalšie vlákna, ktoré následne získajú zámok), ovplyvňuje využitie hardvéru a škálovateľnosť nasledovne:
- Predpokladaná synchronizácia (viacnásobné vlákna neustále súťaží o zámok) je drahé a tým pádom trpí priepustnosť. Hlavným dôvodom výdavkov je časté prepínanie kontextu, ku ktorému dochádza; operácia prepínania kontextu môže trvať veľa cyklov procesora. Naproti tomu nekontrolovaná synchronizácia je lacná pre moderné JVM.
- Keď sa vlákno, ktoré drží zámok, oneskorí (napr. Kvôli oneskoreniu plánovania), žiadne vlákno, ktoré vyžaduje tento zámok, neurobí žiadny pokrok a hardvér sa nevyužíva tak, ako by inak mohol byť.
Možno si myslíte, že môžete použiť prchavý ako alternatíva synchronizácie. Avšak prchavý premenné riešia iba problém viditeľnosti. Nemôžu sa použiť na bezpečnú implementáciu atómových sekvencií čítania, modifikácie a zápisu, ktoré sú potrebné na bezpečnú implementáciu počítadiel a iných entít, ktoré si vyžadujú vzájomné vylúčenie.
Java 5 predstavila alternatívu synchronizácie, ktorá ponúka vzájomné vylúčenie v kombinácii s výkonom systému Windows prchavý. Toto atómová premenná alternatíva je založená na inštrukcii mikroprocesora na porovnanie a výmenu a väčšinou sa skladá z typov v java.util.concurrent.atomic balíček.
Pochopenie porovnania a výmeny
The porovnávať a vymeniť (CAS) inštrukcia je neprerušiteľná inštrukcia, ktorá číta pamäťové miesto, porovnáva načítanú hodnotu s očakávanou hodnotou a ukladá novú hodnotu do pamäťového miesta, keď sa načítaná hodnota zhoduje s očakávanou hodnotou. Inak sa nič nerobí. Skutočná inštrukcia mikroprocesora sa môže trochu líšiť (napr. Vráti hodnotu true, ak bol CAS úspešný, alebo hodnotu false namiesto načítanej hodnoty).
Pokyny CAS pre mikroprocesor
Moderné mikroprocesory ponúkajú určitý druh inštrukcií CAS. Napríklad mikroprocesory Intel ponúkajú cmpxchg rodina inštrukcií, zatiaľ čo mikroprocesory PowerPC ponúkajú prepojenie typu load-link (napr. lwarx) a podmienené obchodom (napr. stwcx) pokyny na ten istý účel.
CAS umožňuje podporovať atómové sekvencie čítania, modifikácie a zápisu. Spravidla by ste používali CAS nasledovne:
- Prečítajte hodnotu v z adresy X.
- Vykonajte viackrokový výpočet, aby ste odvodili novú hodnotu v2.
- Pomocou CAS zmeňte hodnotu X z v na v2. CAS je úspešný, keď sa pri vykonaní týchto krokov hodnota X nezmenila.
Ak chcete zistiť, ako CAS ponúka lepší výkon (a škálovateľnosť) pri synchronizácii, zvážte príklad počítadla, ktorý vám umožní prečítať jeho aktuálnu hodnotu a zvýšiť počítadlo. Nasledujúca trieda implementuje počítadlo založené na synchronizované:
Zoznam 4. Counter.java (verzia 1)
public class Counter {private int value; public synchronized int getValue () {návratová hodnota; } public synchronized int increment () {návrat ++ hodnota; }}Vysoké tvrdenie o uzamknutí monitora bude mať za následok nadmerné prepínanie kontextu, ktoré môže oneskoriť všetky vlákna a vyústi do aplikácie, ktorá zle škáluje.
Alternatíva CAS vyžaduje implementáciu inštrukcie porovnania a výmeny. Nasledujúca trieda emuluje CAS. Používa to synchronizované namiesto skutočnej hardvérovej inštrukcie na zjednodušenie kódu:
Zoznam 5. EmulatedCAS.java
public class EmulatedCAS {private int value; public synchronized int getValue () {návratová hodnota; } verejné synchronizované int compareAndSwap (int expectValue, int newValue) {int readValue = hodnota; if (readValue == expectValue) value = newValue; vrátiť readValue; }} Tu, hodnotu identifikuje miesto v pamäti, ktoré je možné načítať pomocou getValue (). Tiež compareAndSwap () implementuje algoritmus CAS.
Nasledujúca trieda používa EmulatedCAS implementovaťsynchronizované pult (predstierať, že EmulatedCAS nevyžaduje synchronizované):
Zoznam 6. Counter.java (verzia 2)
public class Counter {private EmulatedCAS value = new EmulatedCAS (); public int getValue () {návratová hodnota.getValue (); } public int increment () {int readValue = value.getValue (); while (value.compareAndSwap (readValue, readValue + 1)! = readValue) readValue = value.getValue (); návrat readValue + 1; }}Počítadlo zapuzdruje an EmulatedCAS inštancia a deklaruje metódy na získanie a zvýšenie hodnoty počítadla pomocou tejto inštancie. getValue () načíta "aktuálnu hodnotu počítadla" inštancie a prírastok () bezpečne zvýši hodnotu počítadla.
prírastok () opakovane vyvoláva compareAndSwap () do readValuehodnota sa nemení. Túto hodnotu potom môžete zmeniť. Ak nejde o zámok, zabráni sa sporom spolu s nadmerným prepínaním kontextu. Zlepšuje sa výkon a kód je škálovateľnejší.
ReentrantLock a CAS
To ste sa predtým dozvedeli ReentrantLock ponúka lepší výkon ako synchronizované pod tvrdením vysokej nite. Na zvýšenie výkonu ReentrantLockSynchronizácia je riadená podtriedou abstraktu java.util.concurrent.locks.AbstractQueuedSynchronizer trieda. Táto trieda zase využíva neregistrované slnko.misc.nebezpečný trieda a jej compareAndSwapInt () Metóda CAS.
Skúmanie balíka atómových premenných
Nemusíte implementovať compareAndSwap () prostredníctvom neprenosného natívneho rozhrania Java. Namiesto toho Java 5 ponúka túto podporu prostredníctvom java.util.concurrent.atomic: sada nástrojov pre triedy, ktoré sa používajú na bezpečné uzamykanie a bezpečné programovanie vlákien na jednotlivých premenných.
Podľa java.util.concurrent.atomicJavadoc, tieto triedy
prchavý hodnoty, polia a prvky poľa na tie, ktoré tiež poskytujú operáciu atómovej podmienenej aktualizácie formulára boolean compareAndSet (expectValue, updateValue). Táto metóda (ktorá sa líši v typoch argumentov v rôznych triedach) atomicky nastavuje premennú na updateValue ak v súčasnosti drží očakávaná hodnota, hlásiaci pravdu o úspechu. Tento balík ponúka kurzy pre Boolean (AtomicBoolean), celé číslo (AtomicInteger), dlhé celé číslo (AtomicLong) a odkaz (Atómová referencia) typy. Ponúka tiež verzie poľa celé číslo, dlhé celé číslo a referencia (AtomicIntegerArray, AtomicLongArraya AtomicReferenceArray), označiteľné a opečiatkované referenčné triedy pre atómovú aktualizáciu dvojice hodnôt (AtomicMarkableReference a AtomicStampedReference), a viac.
Implementuje sa porovnanie AndSet ()
Java implementuje compareAndSet () prostredníctvom najrýchlejšieho dostupného natívneho konštruktu (napr. cmpxchg alebo load-link / store-conditional) alebo (v najhoršom prípade) spin zámky.
Zvážte AtomicInteger, ktorý umožňuje aktualizovať int hodnota atómovo. Túto triedu môžeme použiť na implementáciu počítadla zobrazeného v zozname 6. Zoznam 7 predstavuje ekvivalentný zdrojový kód.
Zoznam 7. Counter.java (verzia 3)
import java.util.concurrent.atomic.AtomicInteger; public class Counter {private AtomicInteger value = new AtomicInteger (); public int getValue () {návratová hodnota.get (); } public int increment () {int readValue = value.get (); while (! value.compareAndSet (readValue, readValue + 1)) readValue = value.get (); návrat readValue + 1; }} Zoznam 7 je veľmi podobný záznamu 6, až na to, že nahrádza EmulatedCAS s AtomicInteger. Mimochodom, môžete to zjednodušiť prírastok () pretože AtomicInteger dodáva svoje vlastné int getAndIncrement () metóda (a podobné metódy).
Vidlica / Pripojte sa k rámcu
Počítačový hardvér sa významne vyvinul od debutu Javy v roku 1995. V dnešnej dobe jednoprocesorové systémy dominovali nad výpočtovým prostredím a synchronizačnými prvkami Javy, ako napr. synchronizované a prchavý, ako aj jej knižnicu vlákien ( Závit triedy) boli všeobecne adekvátne.
Multiprocesorové systémy zlacneli a vývojári museli vytvárať aplikácie Java, ktoré efektívne využívali hardvérový paralelizmus, ktorý tieto systémy ponúkali. Čoskoro však zistili, že nízkoúrovňové závitové primitívy a knižnica Java sa v tomto kontexte používajú veľmi ťažko a výsledné riešenia boli často posiate chybami.
Čo je to paralelizmus?
Paralelizmus je simultánne vykonávanie viacerých vlákien / úloh prostredníctvom kombinácie viacerých procesorov a jadier procesora.
Rámec Java Concurrency Utilities zjednodušuje vývoj týchto aplikácií; pomocné programy ponúkané týmto rámcom sa však nerozširujú na tisíce procesorov alebo jadier procesorov. V našej mnohojadrovej ére potrebujeme riešenie na dosiahnutie jemnozrnnejšej paralelnosti, alebo riskujeme udržanie nečinnosti procesorov, aj keď je pre nich veľa práce.
Profesor Doug Lea vo svojom príspevku predstavil riešenie tohto problému, v ktorom predstavil myšlienku rámca fork / join založeného na prostredí Java. Lea popisuje rámec, ktorý podporuje „štýl paralelného programovania, v ktorom sa problémy riešia (rekurzívne) rozdelením na čiastkové úlohy, ktoré sa riešia paralelne.“ Rámec Fork / Join bol nakoniec zahrnutý do Java 7.
Prehľad rámca Fork / Join
Rámec Fork / Join je založený na špeciálnej službe vykonávateľa na vykonávanie špeciálneho druhu úloh. Skladá sa z nasledujúcich typov, ktoré sa nachádzajú v java.util.concurrent balenie:
ForkJoinPool: anExecutorServiceimplementácia, ktorá bežíForkJoinTasks.ForkJoinPoolposkytuje metódy zadávania úloh, ako naprvoid execute (úloha ForkJoinTask), spolu s metódami riadenia a monitorovania, ako naprint getParallelism ()adlho getStealCount ().ForkJoinTask: abstraktná základná trieda pre úlohy, ktoré prebiehajú v rámci aForkJoinPoolkontext.ForkJoinTaskpopisuje entity podobné vláknam, ktoré majú oveľa ľahšiu váhu ako bežné vlákna. Mnoho úloh a čiastkových úloh môže byť hostených veľmi málo skutočnými vláknami v aForkJoinPoolinštancia.ForkJoinWorkerThread: trieda, ktorá popisuje vlákno spravované aForkJoinPoolinštancia.ForkJoinWorkerThreadje zodpovedný za vykonanieForkJoinTasks.RekurzívnaAkcia: abstraktná trieda, ktorá popisuje rekurzívne výsledkyForkJoinTask.RecursiveTask: abstraktná trieda, ktorá popisuje rekurzívne vynášanie výsledkovForkJoinTask.
The ForkJoinPool služba exekútora je vstupným bodom na predkladanie úloh, ktoré sú zvyčajne opísané v podtriedach RekurzívnaAkcia alebo RecursiveTask. V zákulisí je úloha rozdelená na menšie úlohy, ktoré sú rozdvojený (distribuované medzi rôznymi vláknami na vykonanie) z fondu. Úloha čaká do pripojil (jeho podradené úlohy sa dokončia, aby bolo možné kombinovať výsledky).
ForkJoinPool spravuje skupinu pracovných vlákien, kde každé pracovné vlákno má svoj vlastný obojstranný pracovný rad (deque). Keď úloha rozdelí novú podúlohu, vlákno tlačí podúlohu na hlavu jej deque. Keď sa úloha pokúsi spojiť s inou úlohou, ktorá sa nedokončila, vlákno vysunie ďalšiu úlohu z jej hlavy a vykoná ju. Ak je vlákno vlákna prázdne, pokúsi sa ukradnúť ďalšiu úlohu z chvosta vlákna iného vlákna. Toto kradnutie prace správanie maximalizuje priepustnosť a zároveň minimalizuje spory.
Pomocou rámca Fork / Join
Vidlica / Pripojenie bola navrhnutá tak, aby sa efektívne vykonávala algoritmy rozdelenia a dobývania, ktoré rekurzívne delia problémy na čiastkové problémy, až kým nie sú dostatočne jednoduché na priame riešenie; napríklad zlúčenie. Riešenia týchto čiastkových problémov sa kombinujú, aby poskytli riešenie pôvodného problému. Každý čiastkový problém je možné vykonať nezávisle na inom procesore alebo jadre.
Príspevok Lea predstavuje nasledujúci pseudokód popisujúci správanie rozdelenia a dobývania:
Výsledok vyriešiť (Problémový problém) {if (problém je malý) priamo vyriešiť problém iný {rozdeliť problém na samostatné časti rozvetviť nové čiastkové úlohy na vyriešenie každej časti spojiť všetky čiastkové úlohy zostaviť výsledok z čiastkových výsledkov}} Pseudokód predstavuje a vyriešiť metóda, ktorá sa volá s niektorými problém vyriešiť a ktoré vracia a Výsledok ktorý obsahuje problémriešenie. Ak problém je príliš malý na to, aby sa dal vyriešiť paralelizmom, je vyriešený priamo. (Réžia použitia paralelizmu na malom probléme prevyšuje akýkoľvek získaný úžitok.) Inak je problém rozdelený na čiastkové úlohy: každá čiastková úloha sa samostatne zameriava na časť problému.
Prevádzka vidlička zavádza novú podúlohu fork / join, ktorá sa bude vykonávať paralelne s ostatnými podúlohami. Prevádzka pripojiť sa oneskorí aktuálnu úlohu, kým sa nerozdvojená čiastková úloha neskončí. V určitom okamihu problém bude dostatočne malý na to, aby sa dal vykonať postupne, a jeho výsledok sa skombinuje spolu s ďalšími čiastkovými výsledkami, aby sa dosiahlo celkové riešenie, ktoré sa vráti volajúcemu.
Javadoc pre RekurzívnaAkcia a RecursiveTask triedy predstavuje niekoľko príkladov algoritmu rozdelenia a dobývania implementovaných ako úlohy vidlice / spojenia. Pre RekurzívnaAkcia príklady triedia pole dlhých celých čísel, zvyšujú každý prvok v poli a sčítajú druhé mocniny každého prvku v poli dvojitýs. RecursiveTaskOsamelý príklad počíta Fibonacciho číslo.
Zoznam 8 predstavuje aplikáciu, ktorá demonštruje príklad triedenia v kontextoch non-fork / join, ako aj fork / join. Poskytuje tiež niektoré informácie o načasovaní, ktoré majú kontrastovať s rýchlosťami triedenia.
