Programování

Java 101: Souběžnost prostředí Java bez bolesti, část 2

Předchozí 1 2 3 4 Strana 3 Další Strana 3 ze 4

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ě:

  1. Načíst hodnotu v z adresy X.
  2. Proveďte vícestupňový výpočet, abyste odvodili novou hodnotu v2.
  3. 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 readValuehodnota 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ámekSynchronizace 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.atomicJavadoc, tyto třídy

rozšířit pojem 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: an ExecutorService implementace, která běží ForkJoinTasks. ForkJoinPool poskytuje metody zadávání úkolů, například void execute (úkol ForkJoinTask)spolu s metodami řízení a monitorování, jako je int getParallelism () a dlouhý getStealCount ().
  • ForkJoinTask: abstraktní základní třída pro úkoly, které běží v rámci a ForkJoinPool 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 a ForkJoinPool instance.
  • ForkJoinWorkerThread: třída, která popisuje vlákno spravované a ForkJoinPool instance. ForkJoinWorkerThread je odpovědný za provedení ForkJoinTasks.
  • RecursiveAction: abstraktní třída, která popisuje rekurzivní výsledek ForkJoinTask.
  • RecursiveTask: abstraktní třída, která popisuje rekurzivní výsledky ForkJoinTask.

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ásobeks. RecursiveTaskOsamě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í.