streamalism.org

1. Oversikt

I denne opplæringen vil vi se på begrepet arbeid stjele i Java.

2. Hva er arbeid å stjele?

Arbeids stjeling ble introdusert i Java med sikte på reduserer strid i applikasjoner med flere tråder. Dette gjøres ved hjelp av gaffel / sammenføyningsrammen.

2.1. Del og erobre tilnærming

I rammen for gaffel / sammenføyning, problemer eller oppgaver blir rekursivt delt inn i underoppgaver. Underoppgavene løses deretter individuelt, med delresultatene kombinert for å danne resultatet:

Resultat løse (Problem problem) {if (problemet er lite) direkte løse problemet annet {del problemet i uavhengige deler gaffel nye deloppgaver for å løse hver del bli med i alle deloppgaver komponere resultat fra underresultater}}

2.2. Arbeidstråder

Den nedbrutte oppgaven løses ved hjelp av arbeidertråder levert av et trådbasseng. Hver arbeidstakertråd vil ha underoppgaver den er ansvarlig for. Disse lagres i dobbeltkøer (deques).

Hver arbeidertråd får underoppgaver fra deken ved kontinuerlig å peke en underoppgave fra toppen av deken. Når en arbeidertråds deque er tom, betyr det at alle underoppgavene er poppet av og fullført.

På dette punktet velger arbeidertråden tilfeldig en peer-thread-pool-tråd den kan "stjele" arbeid fra. Deretter bruker den først inn, først ut-tilnærmingen (FIFO) for å ta underoppgaver fra halen av offerets deque.

3. Gaffel / Bli med Framework Implementation

Vi kan opprette en arbeidsstele trådgruppe ved hjelp av enten ForkJoinPool klasse eller Utførere klasse:

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

De Utførere klasse har en overbelastet newWorkStealingPool metoden, som tar et heltallargument som representerer nivå av parallellitet.

Executors.newWorkStealingPool er en abstraksjon av ForkJoinPool.commonPool. Den eneste forskjellen er at Executors.newWorkStealingPool oppretter et basseng i asynkron modus og ForkJoinPool.commonPool gjør ikke det.

4. Synkron mot asynkron trådbasseng

ForkJoinPool.commonPool bruker en last-in, first-out (LIFO) køkonfigurasjon, mens Executors.newWorkStealingPool bruker først inn, først ut-tilnærming (FIFO).

Ifølge Doug Lea har FIFO-tilnærmingen disse fordelene fremfor LIFO:

• Det reduserer striden ved å ha stjelerne på den motsatte siden av dekken som eiere
• Den utnytter egenskapen til rekursive dividerings- og erobringsalgoritmer for å generere “store” oppgaver tidlig

Det andre punktet ovenfor betyr at det er mulig å bryte ned en eldre stjålet oppgave ytterligere med en tråd som stjal den.

I henhold til Java-dokumentasjonen, innstilling asyncMode til ekte kan være egnet for bruk med hendelsesstiloppgaver som aldri blir med.

5. Arbeidseksempel - Finne primtall

Vi bruker eksemplet på å finne primtall fra en samling av tall for å vise fordelene ved beregningstiden med det arbeidsstyre rammeverket. Vi viser også forskjellene mellom å bruke synkron og asynkron trådbasseng.

5.1. Prime Numbers Problem

Å finne primtall fra en samling av tall kan være en beregningsdyr prosess. Dette skyldes hovedsakelig størrelsen på nummersamlingen.

De Primtall klasse hjelper oss med å finne primtall:

offentlig klasse PrimeNumbers utvider RecursiveAction {private int lowerBound; private int upperBound; privat int granularitet; statisk slutt 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)); } returner underoppgaver; } @ Override-beskyttet ugyldig beregning () {if (((upperBound + 1) - lowerBound)> granularity) {ForkJoinTask.invokeAll (subTasks ()); } annet {findPrimeNumbers (); }} ugyldig findPrimeNumbers () {for (int num = lowerBound; num <= upperBound; num ++) {if (isPrime (num)) {noOfPrimeNumbers.getAndIncrement (); }}} public int noOfPrimeNumbers () {return noOfPrimeNumbers.intValue (); }}

Noen viktige ting å merke seg om denne klassen:

• Det strekker seg Rekursiv handling, som lar oss implementere beregne metoden som brukes i databehandling ved hjelp av en trådgruppe
• Det bryter oppgaver rekursivt inn i underoppgaver basert på detaljnivå verdi
• Konstruktørene tar Nedre og øverste bundne verdier som styrer rekkevidden av tall vi vil bestemme primtall for
• Det gjør det mulig for oss å bestemme primtall ved hjelp av enten en arbeidsstele trådgruppe eller en enkelt tråd

5.2. Løsning av problemet raskere med trådbassenger

La oss bestemme primtall på en tråd med én tråd og også ved hjelp av arbeidsstele trådbassenger.

La oss først se enkelttrådet tilnærming:

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

Og nå, den ForkJoinPool.commonPool nærme seg:

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

Til slutt vil vi ta en titt på Executors.newWorkStealingPool nærme seg:

PrimeNumbers primtall = nye PrimeNumbers (10000); int parallellisme = ForkJoinPool.getCommonPoolParallelism (); ForkJoinPool stealer = (ForkJoinPool) Executors.newWorkStealingPool (parallellisme); stjeler. påkalle (primtall); stealer.shutdown ();

Vi bruker påkalle metoden for ForkJoinPool klasse for å overføre oppgaver til trådpuljen. Denne metoden tar forekomster av underklasser av Rekursiv handling. Ved hjelp av Java Microbench Harness, måler vi disse forskjellige tilnærmingene mot hverandre når det gjelder gjennomsnittlig tid per operasjon:

# Kjør komplett. Total tid: 00:04:50 Referansemodus Cnt Score Feil Enheter PrimeNumbersUnitTest.Benchmarker.commonPoolBenchmark avgt 20 119.885 ± 9.917 ms / op PrimeNumbersUnitTest.Benchmarker.newWorkStealingPoolBenchmark avgt 20 119.791 ± 7.811 ms / op PrimeNumbersUnitTest.b. ms / op

Det er klart at begge ForkJoinPool.commonPool og Executors.newWorkStealingPool tillate oss å bestemme primtall raskere enn med en enkelt tråd.

Rammen for gaffel / bli med i bassenget lar oss dele oppgaven i underoppgaver. Vi brøt ned samlingen på 10 000 heltall i grupper på 1-100, 101-200, 201-300 og så videre. Vi bestemte deretter primtall for hver batch og gjorde det totale antallet primtall tilgjengelig med vårt noOfPrimeNumbers metode.

5.3. Stjele arbeid å beregne

Med en synkron trådgruppe, ForkJoinPool.commonPool legger tråder i bassenget så lenge oppgaven fortsatt pågår.Som et resultat avhenger ikke nivået for å stjele arbeidet av nivået på oppgavens granularitet.

Den asynkrone Executors.newWorkStealingPooler mer styrt, slik at nivået av arbeid som stjeler kan være avhengig av nivået på oppgavens granularitet.

Vi får nivået på å stjele ved hjelp av getStealCount av ForkJoinPool klasse:

lange stjeler = forkJoinPool.getStealCount ();

Bestemme antall arbeidstyverier for Executors.newWorkStealingPool og ForkJoinPool.commonPool gir oss ulik oppførsel:

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

Når granularitet endres fra fin til grov (1 til 10.000) til Executors.newWorkStealingPool, reduseres nivået på å stjele. Derfor er antall stjeler en når oppgaven ikke brytes ned (granularitet på 10.000).

De ForkJoinPool.commonPool har en annen oppførsel. Arbeidet med å stjele er alltid høyt og påvirkes ikke mye av endringen i oppgavegranulariteten.

Teknisk sett er vårt primtalleksempel en som støtter asynkron behandling av oppgaver i hendelsesstil. Dette er fordi implementeringen vår ikke håndhever sammenføring av resultater.

Det kan gjøres en sak om det Executors.newWorkStealingPool tilbyr den beste ressursbruken for å løse problemet.

6. Konklusjon

I denne artikkelen så vi på arbeidstyveri og hvordan vi bruker det ved hjelp av gaffel / sammenføyningsrammeverket. Vi så også på eksemplene på å stjele arbeid og hvordan det kan forbedre behandlingstid og ressursbruk.

Som alltid er hele kildekoden til eksemplet tilgjengelig på GitHub.