streamalism.org

1. Oversigt

I denne vejledning gennemgår vi nogle af de vigtigste implementeringer af samtidige køer i Java. For en generel introduktion til køer henvises til vores guide til Java Kø Interface artikel.

2. Køer

I flertrådede applikationer skal køer håndtere flere samtidige producent-forbrugsscenarier. Det korrekte valg af en samtidig kø kan være afgørende for at opnå god ydeevne i vores algoritmer.

For det første ser vi nogle vigtige forskelle mellem en blokerende kø og en ikke-blokerende. Derefter ser vi på nogle implementeringer og bedste praksis.

2. Blokering vs ikke-blokerende kø

BlockingQueue tilbud en simpel trådsikker mekanisme. I denne kø skal tråde vente på køens tilgængelighed. Producenterne venter på ledig kapacitet, inden de tilføjer elementer, mens forbrugerne venter, indtil køen er tom. I disse tilfælde vil den ikke-blokerende kø enten kaste en undtagelse eller returnere en særlig værdi som f.eks nul eller falsk.

For at opnå denne blokeringsmekanisme er BlockingQueue interface udsætter to funktioner oven på det normale Kø funktioner: sætte og tage. Disse funktioner svarer til tilføje og fjerne i en standard Kø.

3. Samtidig Kø Implementeringer

3.1. ArrayBlockingQueue

Som navnet antyder, bruger denne kø et array internt. Som en konsekvens er det en afgrænset kø, hvilket betyder at den har en fast størrelse.

En simpel arbejdskø er et eksempel på brugssag. Dette scenario er ofte et lavt forhold mellem producent og forbruger, hvor vi deler tidskrævende opgaver på flere medarbejdere. Da denne kø ikke kan vokse på ubestemt tid, størrelsesgrænsen fungerer som en sikkerhedstærskel, hvis hukommelse er et problem.

Når vi taler om hukommelse, er det vigtigt at bemærke, at køen tildeler arrayet på forhånd. Selvom dette kan forbedre kapaciteten, er det kan også forbruge mere hukommelse end nødvendigt. For eksempel kan en kø med stor kapacitet forblive tom i lange perioder.

Også den ArrayBlockingQueue bruger en enkelt lås til begge sætte og tage operationer. Dette sikrer ingen overskrivning af poster på bekostning af et performance hit.

3.2. LinkedBlockingQueue

Det LinkedBlockingQueue bruger en LinkedList variant, hvor hvert køelement er en ny node. Selv om dette i princippet gør køen ubegrænset, har den stadig en hård grænse på Heltal.MAX_VALUE.

På den anden side kan vi indstille køstørrelsen ved hjælp af konstruktøren LinkedBlockingQueue (int-kapacitet).

Denne kø bruger forskellige låse til sætte og tage operationer. Som en konsekvens kan begge operationer udføres parallelt og forbedre kapaciteten.

Siden den LinkedBlockingQueue kan enten være afgrænset eller ubegrænset, hvorfor bruger vi ArrayBlockingQueue over denne? LinkedBlockingQueue skal allokere og deallocere noder hver gang en vare tilføjes eller fjernes fra køen. Af denne grund er en ArrayBlockingQueue kan være et bedre alternativ, hvis køen vokser hurtigt og krymper hurtigt.

Udførelsen af LinkedBlockingQueue siges at være uforudsigelig. Med andre ord er vi altid nødt til at profilere vores scenarier for at sikre, at vi bruger den rigtige datastruktur.

3.3. PriorityBlockingQueue

Det PriorityBlockingQueue er vores go-to-løsning når vi har brug for at forbruge varer i en bestemt rækkefølge. For at opnå dette er PriorityBlockingQueue bruger en array-baseret binær bunke.

Mens det internt bruger en enkelt låsemekanisme, er tage operation kan forekomme samtidigt med sætte operation. Brug af en simpel spinlock gør dette muligt.

En typisk brugssag er at forbruge opgaver med forskellige prioriteter. Vi ønsker ikke, at en opgave med lav prioritet træder i stedet for en høj prioritet.

3.4. DelayQueue

Vi bruger en DelayQueuenår en forbruger kun kan tage en udløbet vare. Interessant nok bruger den en PriorityQueue internt for at bestille varerne efter deres udløb.

Da dette ikke er en almindelig kø, dækker den ikke så mange scenarier som ArrayBlockingQueue eller den LinkedBlockingQueue. For eksempel kan vi bruge denne kø til at implementere en simpel begivenhedssløjfe svarende til hvad der findes i NodeJS. Vi placerer asynkrone opgaver i køen til senere behandling, når de udløber.

3.5. LinkedTransferQueue

Det LinkedTransferQueue introducerer en overførsel metode. Mens andre køer typisk blokerer, når der produceres eller forbruges varer, LinkedTransferQueuetillader en producent at vente på forbruget af en vare.

Vi bruger en LinkedTransferQueue når vi har brug for en garanti for, at en bestemt vare, vi sætter i køen, er taget af nogen. Vi kan også implementere en simpel modtryksalgoritme ved hjælp af denne kø. Faktisk ved at blokere producenter indtil forbrug, forbrugere kan drive strømmen af ​​producerede meddelelser.

3.6. SynchronousQueue

Mens køer typisk indeholder mange emner, SynchronousQueue vil højst altid have en enkelt vare. Med andre ord er vi nødt til at se SynchronousQueue som en enkel måde at udveksle nogle data mellem to tråde.

Når vi har to tråde, der har brug for adgang til en delt tilstand, synkroniserer vi ofte disse med CountDownLatch eller andre synkroniseringsmekanismer. Ved at bruge en SynchronousQueue, vi kan undgå denne manuelle synkronisering af tråde.

3.7. ConcurrentLinkedQueue

Det ConcurrentLinkedQueue er den eneste ikke-blokerende kø i denne vejledning. Derfor giver den en “ventefri” algoritme hvor tilføje og afstemning garanteres at være trådsikre og vende tilbage straks. I stedet for låse bruger denne kø CAS (Compare-And-Swap).

Internt er det baseret på en algoritme fra Enkle, hurtige og praktiske ikke-blokering og blokering af samtidige køalgoritmer af Maged M. Michael og Michael L. Scott.

Det er en perfekt kandidat til moderne reaktive systemer, hvor brug af blokerende datastrukturer ofte er forbudt.

På den anden side, hvis vores forbruger ender med at vente i en løkke, bør vi sandsynligvis vælge en blokerende kø som et bedre alternativ.

4. Konklusion

I denne vejledning gik vi gennem forskellige samtidige køimplementeringer og diskuterede deres styrker og svagheder. Med dette i tankerne er vi bedre rustet til at udvikle effektive, holdbare og tilgængelige systemer.