Atomové proměnné
Vícevláknové aplikace, které běží na vícejádrových procesorech nebo víceprocesorových systémech, mohou dosáhnout dobrého využití hardwaru a mohou být vysoce škálovatelné. Těchto cílů mohou dosáhnout tím, že jejich vlákna tráví většinu času prováděním práce, spíše než čekáním na dokončení práce, nebo čekáním na získání zámků za účelem přístupu ke sdíleným datovým strukturám.
Nicméně tradiční Java synchronizační mechanismus, který vynucuje vzájemné vyloučení (vlákno, které drží zámek, který chrání sadu proměnných, má k nim výhradní přístup) a viditelnost (změny chráněných proměnných se stanou viditelnými pro další vlákna, která následně získají zámek), ovlivňuje využití hardwaru a škálovatelnost, a to následovně:
- Napadená synchronizace (více vláken neustále soutěžících o zámek) je nákladné a výsledkem je propustnost. Hlavním důvodem výdajů je časté střídání kontextu, ke kterému dochází; operace přepínání kontextu může trvat mnoho cyklů procesoru. V porovnání, nekontrolovaná synchronizace je levná pro moderní JVM.
- Když je vlákno, které drží zámek, zpožděno (např. Kvůli zpoždění plánování), žádné vlákno, které vyžaduje tento zámek, neprovede žádný pokrok a hardware se nepoužívá, stejně jako by to jinak mohlo být.
Možná si myslíte, že můžete použít nestálý
jako alternativa synchronizace. Nicméně, nestálý
proměnné řeší pouze problém viditelnosti. Nelze je použít k bezpečné implementaci atomových sekvencí pro čtení, úpravy a zápis, které jsou nezbytné pro bezpečnou implementaci čítačů a dalších entit, které vyžadují vzájemné vyloučení.
Java 5 představila alternativu synchronizace, která nabízí vzájemné vyloučení v kombinaci s výkonem nestálý
. Tento atomová proměnná alternativa je založena na instrukci mikroprocesoru pro srovnání a výměnu a skládá se převážně z typů v java.util.concurrent.atomic
balík.
Porozumění porovnání a výměně
The porovnat a vyměnit (CAS) instrukce je nepřerušitelná instrukce, která čte paměťové místo, porovnává čtenou hodnotu s očekávanou hodnotou a ukládá novou hodnotu do paměťového místa, když se čtená hodnota shoduje s očekávanou hodnotou. Jinak se nic neděje. Skutečná instrukce mikroprocesoru se může poněkud lišit (např. Vrátit true, pokud bylo CAS úspěšné, nebo false, namísto čtení hodnoty).
Pokyny CAS pro mikroprocesor
Moderní mikroprocesory nabízejí nějaký druh CAS instrukce. Například mikroprocesory Intel nabízejí cmpxchg
řada instrukcí, zatímco mikroprocesory PowerPC nabízejí funkci load-link (např. lwarx
) a podmíněné v obchodě (např. stwcx
) pokyny pro stejný účel.
CAS umožňuje podporovat atomové sekvence čtení, úpravy a zápisu. Obvykle byste CAS používali následovně:
- Načíst hodnotu v z adresy X.
- Proveďte vícestupňový výpočet, abyste odvodili novou hodnotu v2.
- Pomocí CAS změňte hodnotu X z v na v2. CAS uspěje, když se hodnota X při provádění těchto kroků nezměnila.
Chcete-li zjistit, jak CAS nabízí lepší výkon (a škálovatelnost) při synchronizaci, zvažte příklad čítače, který vám umožní přečíst jeho aktuální hodnotu a zvýšit počítadlo. Následující třída implementuje čítač založený na synchronizované
:
Výpis 4. Counter.java (verze 1)
public class Counter {private int value; public synchronized int getValue () {návratová hodnota; } public synchronized int increment () {návrat ++ hodnota; }}
Vysoké soupeření o zámek monitoru bude mít za následek nadměrné přepínání kontextu, které může zpozdit všechna vlákna a vést k aplikaci, která nebude dobře škálovat.
Alternativa CAS vyžaduje implementaci instrukce porovnání a výměny. Následující třída emuluje CAS. Využívá to synchronizované
místo skutečné hardwarové instrukce ke zjednodušení kódu:
Výpis 5. EmulatedCAS.java
public class EmulatedCAS {private int value; public synchronized int getValue () {návratová hodnota; } public synchronized int compareAndSwap (int expectValue, int newValue) {int readValue = value; if (readValue == expectValue) value = newValue; vrátit readValue; }}
Tady, hodnota
identifikuje místo v paměti, které lze načíst getValue ()
. Taky, compareAndSwap ()
implementuje algoritmus CAS.
Následující třída používá Emulované CAS
implementovat non-synchronizované
pult (předstírat, že Emulovaný CAS
nevyžaduje synchronizované
):
Výpis 6. Counter.java (verze 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; }}
Čelit
zapouzdřuje Emulované CAS
instance a deklaruje metody pro načítání a zvyšování hodnoty čítače s pomocí této instance. getValue ()
načte instanci "aktuální hodnotu čítače" a přírůstek()
bezpečně zvýší hodnotu čítače.
přírůstek()
opakovaně vyvolává compareAndSwap ()
dokud readValue
hodnota se nemění. Tuto hodnotu pak můžete změnit. Pokud není zapojen žádný zámek, je zabráněno sporům spolu s nadměrným přepínáním kontextu. Zlepšuje se výkon a kód je škálovatelnější.
ReentrantLock a CAS
Dříve jste se to naučili Znovu zadejte zámek
nabízí lepší výkon než synchronizované
pod velkým soupeřením. Chcete-li zvýšit výkon, Znovu zadejte zámek
Synchronizace je řízena podtřídou abstraktu java.util.concurrent.locks.AbstractQueuedSynchronizer
třída. Tato třída zase využívá neregistrované slunce.misc.nebezpečný
třída a její compareAndSwapInt ()
CAS metoda.
Zkoumání balíčku atomových proměnných
Nemusíte implementovat compareAndSwap ()
prostřednictvím nepřenosného nativního rozhraní Java. Místo toho Java 5 nabízí tuto podporu prostřednictvím java.util.concurrent.atomic
: sada nástrojů tříd používaných k bezzámkovému programování bezpečnému pro vlákna na jednotlivých proměnných.
Podle java.util.concurrent.atomic
Javadoc, tyto třídy
nestálý
hodnoty, pole a prvky pole na ty, které také poskytují atomickou operaci podmíněné aktualizace formuláře boolean compareAndSet (expectValue, updateValue)
. Tato metoda (která se liší v typech argumentů napříč různými třídami) atomicky nastavuje proměnnou na updateValue
pokud aktuálně drží očekávaná hodnota
, informující o úspěchu. Tento balíček nabízí kurzy pro Boolean (AtomicBoolean
), celé číslo (AtomicInteger
), dlouhé celé číslo (AtomicLong
) a odkaz (Atomová reference
) typy. Nabízí také maticové verze celého čísla, dlouhého celého čísla a reference (AtomicIntegerArray
, AtomicLongArray
, a AtomicReferenceArray
), označitelné a orazítkované referenční třídy pro atomovou aktualizaci dvojice hodnot (AtomicMarkableReference
a AtomicStampedReference
), a více.
Implementace compareAndSet ()
Java implementuje porovnáníAndSet ()
prostřednictvím nejrychlejšího dostupného nativního konstruktu (např. cmpxchg
nebo load-link / store-conditional) nebo (v nejhorším případě) spin zámky.
Zvážit AtomicInteger
, který vám umožní aktualizovat int
hodnota atomově. Tuto třídu můžeme použít k implementaci čítače zobrazeného v seznamu 6. Výpis 7 představuje ekvivalentní zdrojový kód.
Výpis 7. Counter.java (verze 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; }}
Výpis 7 je velmi podobný výpisu 6 kromě toho, že nahrazuje Emulovaný CAS
s AtomicInteger
. Mimochodem, můžete to zjednodušit přírůstek()
protože AtomicInteger
dodává své vlastní int getAndIncrement ()
metoda (a podobné metody).
Vidlice / Připojit rámec
Počítačový hardware se významně vyvinul od debutu Javy v roce 1995. V dnešní době dominovaly výpočetní prostředí a synchronizační primitivy Javy jednoprocesorové systémy, jako například synchronizované
a nestálý
, stejně jako jeho knihovna vláken ( Vlákno
třídy) byly obecně přiměřené.
Multiprocesorové systémy zlevnily a vývojáři zjistili, že potřebují vytvářet aplikace Java, které efektivně využívají hardwarový paralelismus, který tyto systémy nabízejí. Brzy však zjistili, že nízkoúrovňové podprocesy a knihovna Java se v této souvislosti velmi obtížně používají a výsledná řešení byla často plná chyb.
Co je to paralelismus?
Rovnoběžnost je současné provádění více podprocesů / úkolů prostřednictvím kombinace více procesorů a jader procesorů.
Rámec Java Concurrency Utilities zjednodušuje vývoj těchto aplikací; nástroje nabízené tímto rámcem se však neomezují na tisíce procesorů nebo jader procesorů. V naší éře mnoha jader potřebujeme řešení pro dosažení jemnějšího paralelismu, nebo riskujeme udržení nečinnosti procesorů, i když je pro ně spousta práce.
Profesor Doug Lea představil řešení tohoto problému ve svém příspěvku představujícím myšlenku rámce fork / join založeného na Javě. Lea popisuje rámec, který podporuje „styl paralelního programování, ve kterém jsou problémy řešeny (rekurzivně) rozdělením na dílčí úkoly, které jsou řešeny paralelně.“ Rámec Fork / Join byl nakonec zahrnut do prostředí Java 7.
Přehled rámce Fork / Join
Rámec Fork / Join je založen na speciální službě provádějící speciální úkol. Skládá se z následujících typů, které jsou umístěny v java.util.concurrent
balík:
ForkJoinPool
: anExecutorService
implementace, která běžíForkJoinTask
s.ForkJoinPool
poskytuje metody zadávání úkolů, napříkladvoid execute (úkol ForkJoinTask)
spolu s metodami řízení a monitorování, jako jeint getParallelism ()
adlouhý getStealCount ()
.ForkJoinTask
: abstraktní základní třída pro úkoly, které běží v rámci aForkJoinPool
kontext.ForkJoinTask
popisuje entity podobné vláknům, které mají mnohem nižší váhu než normální vlákna. Mnoho úkolů a dílčích úkolů může být hostitelem velmi málo skutečných vláken v aForkJoinPool
instance.ForkJoinWorkerThread
: třída, která popisuje vlákno spravované aForkJoinPool
instance.ForkJoinWorkerThread
je odpovědný za provedeníForkJoinTask
s.RecursiveAction
: abstraktní třída, která popisuje rekurzivní výsledekForkJoinTask
.RecursiveTask
: abstraktní třída, která popisuje rekurzivní výsledkyForkJoinTask
.
The ForkJoinPool
služba vykonavatele je vstupním bodem pro odesílání úkolů, které jsou obvykle popsány podtřídami RecursiveAction
nebo RecursiveTask
. V zákulisí je úkol rozdělen na menší úkoly, které jsou rozeklaný (distribuováno mezi různými vlákny k provedení) z fondu. Úkol čeká na připojil se (jeho dílčí úkoly končí, aby bylo možné kombinovat výsledky).
ForkJoinPool
spravuje fond pracovních vláken, kde každé pracovní vlákno má svou vlastní oboustrannou pracovní frontu (deque). Když úkol rozdělí nový dílčí úkol, podproces posune dílčí úkol na hlavu jeho deque. Když se úkol pokusí připojit k jinému úkolu, který nedokončil, vlákno vyskočí z úkolu svého úkolu další úkol a provede úkol. Pokud je deque vlákna prázdné, pokusí se ukrást další úkol z ocasu deque jiného vlákna. Tento kradení prací chování maximalizuje propustnost a zároveň minimalizuje spory.
Pomocí rozhraní Fork / Join
Fork / Join byl navržen tak, aby efektivně provádět algoritmy rozděl a panuj, které rekurzivně dělí problémy na dílčí problémy, dokud nejsou dostatečně jednoduché na přímé řešení; například sloučení. Řešení těchto dílčích problémů jsou kombinována, aby poskytla řešení původního problému. Každý dílčí problém lze provést nezávisle na jiném procesoru nebo jádře.
Leaův článek představuje následující pseudokód k popisu chování rozděl a panuj:
Výsledek vyřešit (Problémový problém) {if (problém je malý) přímo vyřešit problém jiný {rozdělit problém na nezávislé části vidlice nové dílčí úkoly k řešení každé části spojit všechny dílčí úkoly sestavit výsledek z dílčích výsledků}}
Pseudokód představuje a řešit
metoda, která se nazývá s některými problém
vyřešit a které vrací a Výsledek
který obsahuje problém
řešení. Pokud problém
je příliš malý na řešení paralelismem, je vyřešen přímo. (Režie použití paralelismu na malý problém převyšuje jakoukoli získanou výhodu.) Jinak je problém rozdělen na dílčí úkoly: každý dílčí úkol se samostatně zaměřuje na část problému.
Úkon Vidlička
zavádí nový dílčí úkol fork / join, který bude spuštěn souběžně s dalšími dílčími úkoly. Úkon připojit
odloží aktuální úkol, dokud nedojde k dokončení rozvětveného dílčího úkolu. V určitém okamžiku se problém
bude dostatečně malý na to, aby byl proveden postupně, a jeho výsledek bude kombinován spolu s dalšími dílčími výsledky, aby se dosáhlo celkového řešení vráceného volajícímu.
Javadoc pro RecursiveAction
a RecursiveTask
třídy představuje několik příkladů algoritmu rozděl a panuj implementovaných jako úkoly vidlice / spojení. Pro RecursiveAction
příklady třídí pole dlouhých celých čísel, zvyšují každý prvek v poli a sčítají čtverce každého prvku v poli dvojnásobek
s. RecursiveTask
Osamělý příklad spočítá Fibonacciho číslo.
Výpis 8 představuje aplikaci, která ukazuje příklad řazení v kontextech non-fork / join i fork / join. Poskytuje také některé informace o načasování pro srovnání rychlostí řazení.