streamalism.org

1. Oversigt

I denne vejledning ser vi på begrebet arbejde stjæle i Java.

2. Hvad er arbejde at stjæle?

Arbejds stjæling blev introduceret i Java med det formål at reducerer strid i applikationer med flere tråde. Dette gøres ved hjælp af gaffel / sammenføjningsrammen.

2.1. Opdel og sejr tilgang

I gaffel / sammenføjningsrammen, problemer eller opgaver er rekursivt opdelt i underopgaver. Underopgaverne løses derefter individuelt, hvor underresultaterne kombineres for at danne resultatet:

Resultat løser (Problem problem) {hvis (problemet er lille) direkte løser problemet andet {del problemet i uafhængige dele fork del nye underopgaver for at løse hver del sammenføj alle delopgaver komponere resultat fra underresultater}}

2.2. Arbejdstråde

Den nedbrudte opgave løses ved hjælp af arbejdertråde leveret af en trådpulje. Hver medarbejdertråd har underopgaver, den er ansvarlig for. Disse lagres i køer med dobbelt ende (deques).

Hver arbejdertråd får underopgaver fra sin deque ved kontinuerligt at poppe en underopgave fra toppen af ​​deque. Når en arbejdertråds deque er tom, betyder det, at alle underopgaver er blevet poppet af og afsluttet.

På dette tidspunkt vælger arbejdertråden tilfældigt en peer-thread-pool-tråd, den kan "stjæle" arbejde fra. Derefter bruger den den første ind, først ud-tilgang (FIFO) til at tage underopgaver fra halen af ​​offerets deque.

3. Gaffel / Deltag i Framework Implementation

Vi kan oprette en arbejde-stjæle tråd pool ved hjælp af enten ForkJoinPool klasse eller Eksekutører klasse:

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

Det Eksekutører klasse har en overbelastet newWorkStealingPool metode, der tager et heltalargument, der repræsenterer niveau af parallelisme.

Executors.newWorkStealingPool er en abstraktion af ForkJoinPool.commonPool. Den eneste forskel er det Executors.newWorkStealingPool opretter en pool i asynkron tilstand og ForkJoinPool.commonPool ikke.

4. Synkron versus asynkron trådpuljer

ForkJoinPool.commonPool bruger en last-in, first-out (LIFO) køkonfiguration, hvorimod Executors.newWorkStealingPool bruger først-ind, først-ud tilgang (FIFO).

Ifølge Doug Lea har FIFO-tilgangen disse fordele i forhold til LIFO:

• Det reducerer uenighed ved at lade stjælere arbejde på den modsatte side af deken som ejere
• Den udnytter egenskaberne ved rekursive dividerings- og − erobringsalgoritmer til at generere “store” opgaver tidligt

Det andet punkt ovenfor betyder, at det er muligt yderligere at nedbryde en ældre stjålet opgave med en tråd, der stjal den.

I henhold til Java-dokumentationen, indstilling asyncMode til rigtigt kan være velegnet til brug med opgaver i begivenhedsstil, der aldrig sammenføjes.

5. Arbejdseksempel - Find primtal

Vi bruger eksemplet på at finde primtal fra en samling af tal for at vise fordelene ved beregningstiden ved den arbejde-stjæle ramme. Vi viser også forskellene mellem brug af synkron og asynkron trådpulje.

5.1. Problemet med primtalene

At finde primtal fra en samling tal kan være en beregningsdygtig proces. Dette skyldes hovedsageligt størrelsen på nummersamlingen.

Det Primtal klasse hjælper os med at finde primtal:

offentlig klasse PrimeNumbers udvider RecursiveAction {private int lowerBound; privat int upperBound; privat int granularitet; statisk endelig Liste GRANULARITIES = Arrays.asList (1, 10, 100, 1000, 10000); private AtomicInteger noOfPrimeNumbers; PrimeNumbers (int lowerBound, int upperBound, int granularity, AtomicInteger noOfPrimeNumbers) {this.lowerBound = lowerBound; this.upperBound = upperBound; denne.granularitet = granularitet; this.noOfPrimeNumbers = noOfPrimeNumbers; } // andre konstruktører og metoder private List subTasks () {List subTasks = new ArrayList (); for (int i = 1; i <= this.upperBound / granularity; i ++) {int upper = i * granularity; int nedre = (øvre - granularitet) + 1; subTasks.add (nye PrimeNumbers (nedre, øvre, noOfPrimeNumbers)); } returnere underopgaver } @ Override beskyttet ugyldig beregning () {if (((upperBound + 1) - lowerBound)> granularitet) {ForkJoinTask.invokeAll (subTasks ()); } andet {findPrimeNumbers (); }} ugyldig findPrimeNumbers () {for (int num = lowerBound; num <= upperBound; num ++) {hvis (isPrime (num)) {noOfPrimeNumbers.getAndIncrement (); }}} public int noOfPrimeNumbers () {returner noOfPrimeNumbers.intValue (); }}

Et par vigtige ting at bemærke om denne klasse:

• Det strækker sig Rekursiv handling, som giver os mulighed for at implementere beregne metode, der bruges til computere ved hjælp af en trådpulje
• Det opdeler rekursivt opgaver i underopgaver baseret på granularitet værdi
• Konstruktørerne tager nederste og øverst bundne værdier, der styrer det rækkeområde, vi vil bestemme primtal for
• Det gør det muligt for os at bestemme primtal ved hjælp af enten en arbejdsstjælende trådpulje eller en enkelt tråd

5.2. Løsning af problemet hurtigere med trådbassiner

Lad os bestemme primtal på en enkelt tråd og også ved hjælp af arbejdsstjælende trådpuljer.

Lad os først se enkelttrådet tilgang:

PrimeNumbers primes = nye PrimeNumbers (10000); primes.findPrimeNumbers ();

Og nu, den ForkJoinPool.commonPool nærme sig:

PrimeNumbers primes = nye PrimeNumbers (10000); ForkJoinPool pool = ForkJoinPool.commonPool (); pool.invoke (primtal); pool.shutdown ();

Endelig skal vi se på Executors.newWorkStealingPool nærme sig:

PrimeNumbers primes = nye PrimeNumbers (10000); int parallelisme = ForkJoinPool.getCommonPoolParallelism (); ForkJoinPool stealer = (ForkJoinPool) Executors.newWorkStealingPool (parallelisme); stealer.invoke (primer); stealer.shutdown ();

Vi bruger påberåbe sig metode til ForkJoinPool klasse for at videregive opgaver til trådpuljen. Denne metode tager forekomster af underklasser af Rekursiv handling. Ved hjælp af Java Microbench Harness benchmarker vi disse forskellige tilgange i forhold til hinanden med hensyn til den gennemsnitlige tid pr. Operation:

# Kør komplet. Samlet tid: 00:04:50 Benchmark Mode Cnt Score Fejl Enheder PrimeNumbersUnitTest.Benchmarker.commonPoolBenchmark avgt 20 119.885 ± 9.917 ms / op PrimeNumbersUnitTest.Benchmarker.newWorkStealingPoolBenchmark avgt 20 119.791 ± 7.811 ms / op PrimeNumbersUnitTest.bt. ms / op

Det er klart, at begge ForkJoinPool.commonPool og Executors.newWorkStealingPool tillad os at bestemme primtal hurtigere end med en enkelt-trådet tilgang.

Gaffel / join pool-rammen giver os mulighed for at nedbryde opgaven i underopgaver. Vi opdelte samlingen af ​​10.000 heltal i partier på 1-100, 101-200, 201-300 og så videre. Vi bestemte derefter primtal for hvert parti og stillede det samlede antal primtal til rådighed med vores noOfPrimeNumbers metode.

5.3. Stjæler arbejde at beregne

Med en synkron trådpulje, ForkJoinPool.commonPool lægger tråde i puljen, så længe opgaven stadig er i gang.Som et resultat afhænger niveauet af arbejde stjæling ikke af niveauet for opgavens granularitet.

Den asynkrone Executors.newWorkStealingPoolstyres mere, så det niveau for arbejde, der stjæler, afhænger af niveauet for opgavens granularitet.

Vi får niveauet for at stjæle ved hjælp af getStealCount af ForkJoinPool klasse:

lange stjæler = forkJoinPool.getStealCount ();

Bestemmelse af antallet af arbejdsstyverier for Executors.newWorkStealingPool og ForkJoinPool.commonPool giver os en anden adfærd:

Executors.newWorkStealingPool -> Granularitet: [1], stjæler: [6564] Granularitet: [10], stjæler: [572] granularitet: [100], stjæler: [56] granularitet: [1000], stjæler: [60] granularitet : [10000], Steals: [1] ForkJoinPool.commonPool -> Granularity: [1], Steals: [6923] Granularity: [10], Steals: [7540] Granularity: [100], Steals: [7605] Granularity: [1000], stjæler: [7681] granularitet: [10000], stjæler: [7681]

Når granularitet skifter fra fin til grov (1 til 10.000) til Executors.newWorkStealingPool, niveauet for at stjæle arbejde falder. Derfor er antallet af stjæle en, når opgaven ikke opdeles (granularitet på 10.000).

Det ForkJoinPool.commonPool har en anden adfærd. Niveauet for at stjæle arbejde er altid højt og påvirkes ikke meget af ændringen i opgavens granularitet.

Teknisk set er vores primtal eksempel, der understøtter asynkron behandling af opgaver i hændelsesstil. Dette skyldes, at vores implementering ikke håndhæver sammenføjning af resultater.

En sag kan gøres Executors.newWorkStealingPool tilbyder den bedste ressourceudnyttelse til løsning af problemet.

6. Konklusion

I denne artikel kiggede vi på stjæling af arbejde, og hvordan man anvender det ved hjælp af gaffel / sammenføjningsrammen. Vi kiggede også på eksemplerne på stjæling af arbejde, og hvordan det kan forbedre behandlingstid og ressourceudnyttelse.

Som altid er den fulde kildekode for eksemplet tilgængelig på GitHub.