streamalism.org

1. Overzicht

In deze tutorial kijken we naar de concept van werkstelen in Java.

2. Wat is werkstelen?

Werkstelen is in Java geïntroduceerd met als doel het verminderen van conflicten in toepassingen met meerdere threads. Dit wordt gedaan met behulp van het fork / join-framework.

2.1. Verdeel en heers aanpak

In het fork / join-raamwerk, problemen of taken worden recursief onderverdeeld in subtaken. De subtaken worden vervolgens afzonderlijk opgelost, waarbij de subresultaten worden gecombineerd om het resultaat te vormen:

Resultaat oplossen (probleemprobleem) {if (probleem is klein) probleem direct oplossen anders {probleem opsplitsen in onafhankelijke delen nieuwe subtaken splitsen om elk onderdeel op te lossen samen alle subtaken samenstellen resultaat samenstellen uit subresultaten}}

2.2. Worker Threads

De afgebroken taak wordt opgelost met behulp van werkthreads die worden geleverd door een threadpool. Elke werkthread heeft subtaken waarvoor hij verantwoordelijk is. Deze worden opgeslagen in wachtrijen met dubbele uiteinden (deques).

Elke werkthread haalt subtaken uit zijn deque door continu een subtaak van de top van de deque te halen. Wanneer het deque van een werkdraad leeg is, betekent dit dat alle subtaken zijn verwijderd en voltooid.

Op dit punt selecteert de worker-thread willekeurig een peer-thread-pool-thread waarvan het werk kan "stelen". Vervolgens wordt de first-in, first-out-benadering (FIFO) gebruikt om subtaken over te nemen vanaf het uiteinde van de kaart van het slachtoffer.

3. Fork / Join Framework-implementatie

We kunnen een threadpool maken die werk steelt met behulp van de ForkJoinPool klasse of de Uitvoerders klasse:

ForkJoinPool commonPool = ForkJoinPool.commonPool (); ExecutorService workStealingPool = Executors.newWorkStealingPool ();

De Uitvoerders klasse heeft een overbelast newWorkStealingPool methode, waaraan een integer-argument moet doorgegeven worden dat de niveau van parallellisme.

Executors.newWorkStealingPool is een abstractie van ForkJoinPool.commonPool. Het enige verschil is dat Executors.newWorkStealingPool maakt een pool in asynchrone modus en ForkJoinPool.commonPool niet.

4. Synchrone versus asynchrone threadpools

ForkJoinPool.commonPool gebruikt een last-in, first-out (LIFO) wachtrijconfiguratie, terwijl Executors.newWorkStealingPool maakt gebruik van een first-in, first-out-benadering (FIFO).

Volgens Doug Lea heeft de FIFO-benadering deze voordelen ten opzichte van LIFO:

• Het vermindert de strijd door stelen als eigenaren aan de andere kant van de deque te laten opereren
• Het maakt gebruik van de eigenschap van recursieve verdeel-en-heersalgoritmen om vroegtijdig "grote" taken te genereren

Het tweede punt hierboven betekent dat het mogelijk is om een ​​oudere gestolen taak verder op te splitsen door een thread die deze heeft gestolen.

Volgens de Java-documentatie, setting asyncMode naar waar kan geschikt zijn voor gebruik met taken in de stijl van een evenement die nooit worden samengevoegd.

5. Werkvoorbeeld - priemgetallen zoeken

We gebruiken het voorbeeld van het vinden van priemgetallen uit een verzameling getallen om de rekentijdvoordelen van het raamwerk voor werkstelen. We laten ook de verschillen zien tussen het gebruik van synchrone en asynchrone threadpools.

5.1. Het priemgetallenprobleem

Het vinden van priemgetallen uit een verzameling getallen kan een rekenkundig duur proces zijn. Dit komt vooral door de omvang van de verzameling getallen.

De Priemgetallen klasse helpt ons priemgetallen te vinden:

openbare klasse PrimeNumbers breidt RecursiveAction {private int lowerBound uit; privé int upperBound; privé int granulariteit; statische laatste lijst GRANULARITIES = Arrays.asList (1, 10, 100, 1000, 10000); privé AtomicInteger noOfPrimeNumbers; PrimeNumbers (int lowerBound, int upperBound, int granularity, AtomicInteger noOfPrimeNumbers) {this.lowerBound = lowerBound; this.upperBound = upperBound; this.granularity = granulariteit; this.noOfPrimeNumbers = noOfPrimeNumbers; } // andere constructors en methoden private List subTasks () {List subTasks = new ArrayList (); voor (int i = 1; i <= this.upperBound / granularity; i ++) {int upper = i * granularity; int lower = (upper - granulariteit) + 1; subTasks.add (nieuwe PrimeNumbers (lower, upper, noOfPrimeNumbers)); } retourneer subTasks; } @Override beschermde ongeldige compute () {if (((upperBound + 1) - lowerBound)> granulariteit) {ForkJoinTask.invokeAll (subTasks ()); } anders {findPrimeNumbers (); }} void findPrimeNumbers () {for (int num = lowerBound; num <= upperBound; num ++) {if (isPrime (num)) {noOfPrimeNumbers.getAndIncrement (); }}} openbare int noOfPrimeNumbers () {return noOfPrimeNumbers.intValue (); }}

Een paar belangrijke dingen om op te merken over deze les:

• Het strekt zich uit RecursiveAction, waarmee we de berekenen methode die wordt gebruikt bij computertaken met behulp van een threadpool
• Het splitst taken recursief op in subtaken op basis van het granulariteit waarde
• De constructeurs nemen lager en bovenste gebonden waarden die het bereik van getallen bepalen waarvoor we priemgetallen willen bepalen
• Het stelt ons in staat priemgetallen te bepalen met behulp van een werkstelende threadpool of een enkele thread

5.2. Het probleem sneller oplossen met Thread Pools

Laten we priemgetallen bepalen op een manier met één thread en ook door werkstelende threadpools te gebruiken.

Laten we eerst eens kijken naar het single-threaded benadering:

PrimeNumbers priemgetallen = nieuwe PrimeNumbers (10000); primes.findPrimeNumbers ();

En nu, de ForkJoinPool.commonPool nadering:

PrimeNumbers priemgetallen = nieuwe PrimeNumbers (10000); ForkJoinPool-pool = ForkJoinPool.commonPool (); pool.invoke (priemgetallen); pool.shutdown ();

Ten slotte bekijken we het Executors.newWorkStealingPool nadering:

PrimeNumbers priemgetallen = nieuwe PrimeNumbers (10000); int parallellisme = ForkJoinPool.getCommonPoolParallelism (); ForkJoinPool stealer = (ForkJoinPool) Executors.newWorkStealingPool (parallellisme); stealer.invoke (priemgetallen); stealer.shutdown ();

Wij gebruiken de beroep doen op methode van de ForkJoinPool class om taken door te geven aan de threadpool. Bij deze methode worden subklassen van RecursiveAction. Met behulp van Java Microbench Harness vergelijken we deze verschillende benaderingen met elkaar in termen van de gemiddelde tijd per bewerking:

# Rennen voltooid. Totale tijd: 00:04:50 Benchmarkmodus Cnt Score Fout Eenheden PrimeNumbersUnitTest.Benchmarker.commonPoolBenchmark gem. 20119.885 ± 9.917 ms / op PrimeNumbersUnitTest.Benchmarker.newWorkStealingPoolBenchmark gem. 20 119.791 ± 7.811 ms / op. Gem. ms / op

Het is duidelijk dat beide ForkJoinPool.commonPool en Executors.newWorkStealingPool stellen ons in staat priemgetallen sneller te bepalen dan met een single-threaded benadering.

Met het fork / join pool-raamwerk kunnen we de taak opsplitsen in subtaken. We hebben de verzameling van 10.000 gehele getallen opgedeeld in batches van 1-100, 101-200, 201-300 enzovoort. Vervolgens hebben we voor elke batch priemgetallen bepaald en het totale aantal priemgetallen beschikbaar gesteld met onze noOfPrimeNumbers methode.

5.3. Werk stelen om te berekenen

Met een synchrone threadpool, ForkJoinPool.commonPool plaatst threads in de pool zolang de taak nog bezig is.Als gevolg hiervan is het niveau van werkstelen niet afhankelijk van het niveau van taakgranulariteit.

Het asynchrone Executors.newWorkStealingPoolwordt beter beheerd, waardoor het niveau van het stelen van werk afhankelijk kan zijn van het niveau van de granulariteit van de taak.

We krijgen het niveau van werkstelen met behulp van de getStealCount van de ForkJoinPool klasse:

lange steelt = forkJoinPool.getStealCount ();

Het bepalen van het aantal werkstelen voor Executors.newWorkStealingPool en ForkJoinPool.commonPool geeft ons ongelijk gedrag:

Executors.newWorkStealingPool -> Granulariteit: [1], Steelt: [6564] Granulariteit: [10], Steelt: [572] Granulariteit: [100], Steelt: [56] Granulariteit: [1000], Steelt: [60] Granulariteit : [10000], Steelt: [1] ForkJoinPool.commonPool -> Granulariteit: [1], Steelt: [6923] Granulariteit: [10], Steelt: [7540] Granulariteit: [100], Steelt: [7605] Granulariteit: [1000], steelt: [7681] Granulariteit: [10000], steelt: [7681]

Wanneer de granulariteit verandert van fijn naar grof (1 tot 10.000) voor Executors.newWorkStealingPoolneemt het niveau van werkstelen af. Daarom is het aantal stelen één wanneer de taak niet is opgesplitst (granulariteit van 10.000).

De ForkJoinPool.commonPool heeft een ander gedrag. Het niveau van het stelen van werk is altijd hoog en wordt niet veel beïnvloed door de verandering in de granulariteit van taken.

Technisch gezien is ons voorbeeld met priemgetallen een voorbeeld dat asynchrone verwerking van taken in gebeurtenisstijl ondersteunt. Dit komt doordat onze implementatie het samenvoegen van resultaten niet afdwingt.

Daar kan een zaak van worden gemaakt Executors.newWorkStealingPool biedt het beste gebruik van middelen om het probleem op te lossen.

6. Conclusie

In dit artikel hebben we gekeken naar het stelen van werk en hoe dit toe te passen met behulp van het fork / join-framework. We hebben ook gekeken naar de voorbeelden van werkstelen en hoe dit de verwerkingstijd en het gebruik van middelen kan verbeteren.

Zoals altijd is de volledige broncode van het voorbeeld beschikbaar op GitHub.