LinkedBlockingQueue vs ConcurrentLinkedQueue

112

Ma question porte sur cette question posée plus tôt. Dans les situations où j'utilise une file d'attente pour la communication entre les threads producteur et consommateur, les gens recommandent-ils généralement d'utiliser LinkedBlockingQueueou ConcurrentLinkedQueue?

Quels sont les avantages / inconvénients de l'utilisation de l'un par rapport à l'autre?

La principale différence que je peux voir du point de vue de l'API est que a LinkedBlockingQueuepeut être facultativement délimité.

java multithreading data-structures concurrency queue Adamski
la source

Réponses:

110

Pour un thread producteur / consommateur, je ne suis pas sûr que ce ConcurrentLinkedQueuesoit même une option raisonnable - il ne met pas en œuvre BlockingQueue, qui est l'interface fondamentale pour les files d'attente producteur / consommateur IMO. Vous auriez à appeler poll(), attendre un peu si vous n'aviez rien trouvé, puis interroger à nouveau, etc. .

À partir de la documentation de BlockingQueue:

BlockingQueue les implémentations sont conçues pour être utilisées principalement pour les files d'attente producteur-consommateur

Je sais que cela ne dit pas strictement que seules les files d'attente de blocage devraient être utilisées pour les files d'attente producteur-consommateur, mais même ainsi ...

Jon Skeet
la source
4
Merci Jon - je n'avais pas remarqué cela. Alors, où / pourquoi utiliseriez-vous ConcurrentLinkedQueue?
Adamski
27
Lorsque vous avez besoin d'accéder à la file d'attente à partir d'un grand nombre de threads, mais que vous n'avez pas besoin "d'attendre" dessus.
Jon Skeet
2
A ConcurrentLinkedQueueest également utile si votre thread vérifie plusieurs files d'attente. Par exemple, dans un serveur multi-tenant. En supposant que pour des raisons d'isolement, vous n'utilisez pas une seule file d'attente de blocage et un discriminateur de locataire à la place.
LateralFractal
votre cas n'est vrai que si nous utilisons une file d'attente limitée , dans une file d'attente illimitéetake() et put()consomme simplement des ressources supplémentaires (en termes de synchronisation) que ConcurrentLinkedQueue . bien qu'il soit le cas d'utiliser des files d'attente limitées pour les scénarios producteur-consommateur
amarnath harish
@Adamski IMO, ConcurrentLinkedQueue est juste une liste liée à utiliser dans un environnement multithread. La meilleure analogie pour cela serait ConcurrentHashMap et HashMap.
Nishit
69

Cette question mérite une meilleure réponse.

Java ConcurrentLinkedQueueest basé sur le célèbre algorithme de Maged M. Michael et Michael L. Scott pour les files d' attente non bloquantes sans verrouillage .

«Non bloquant» comme terme ici pour une ressource contestée (notre file d'attente) signifie que indépendamment de ce que fait le planificateur de la plate-forme, comme interrompre un thread, ou si le thread en question est tout simplement trop lent, d'autres threads se disputent la même ressource pourra encore progresser. Si un verrou est impliqué par exemple, le thread contenant le verrou pourrait être interrompu et tous les threads en attente de ce verrou seraient bloqués. Les verrous intrinsèques (le synchronizedmot - clé) en Java peuvent également entraîner une pénalité sévère pour les performances - comme lors d' un verrouillage biaiséest impliqué et vous avez un conflit, ou après que la machine virtuelle a décidé de "gonfler" le verrou après une période de grâce de rotation et de bloquer les threads en conflit ... c'est pourquoi dans de nombreux contextes (scénarios de conflit faible / moyen), faire comparer et -sets sur des références atomiques peuvent être beaucoup plus efficaces et c'est exactement ce que font de nombreuses structures de données non bloquantes.

Java ConcurrentLinkedQueuen'est pas seulement non bloquant, mais il a la propriété impressionnante que le producteur ne lutte pas avec le consommateur. Dans un scénario producteur / consommateur unique (SPSC), cela signifie vraiment qu'il n'y aura pas de conflit à proprement parler. Dans un scénario de producteur multiple / consommateur unique, le consommateur ne sera pas en conflit avec les producteurs. Cette file d'attente a un conflit lorsque plusieurs producteurs essaient de le faire offer(), mais c'est la concurrence par définition. C'est essentiellement une file d'attente non bloquante à usage général et efficace.

Quant au fait que ce n'est pas un BlockingQueue, eh bien, bloquer un thread pour attendre dans une file d'attente est une façon terriblement terrible de concevoir des systèmes concurrents. Ne fais pas ça. Si vous ne pouvez pas comprendre comment utiliser un ConcurrentLinkedQueuedans un scénario consommateur / producteur, passez simplement à des abstractions de niveau supérieur, comme un bon framework d'acteur.

Alexandru Nedelcu
la source
8
D'après votre dernier paragraphe, pourquoi dites-vous qu'attendre dans une file d'attente est une manière terrible de concevoir des systèmes concurrents? Si nous avons un groupe de threads avec 10 threads qui mangent des tâches d'une file d'attente de tâches, quel est le problème avec le blocage lorsque la file d'attente de tâches a moins de 10 tâches?
Pacerier
11
@AlexandruNedelcu Vous ne pouvez pas faire une déclaration radicale comme "terriblement terrible" où très souvent les frameworks d'acteurs que vous dites utiliser utilisent des threadpools qui sont eux-mêmes ceux de BlockingQueue . Si vous avez besoin d'un système hautement réactif et que vous savez comment gérer la contre-pression (ce que le blocage des files d'attente atténue), le non-blocage est clairement supérieur. Mais ... souvent, le blocage des E / S et le blocage des files d'attente peuvent surpasser le non-blocage, en particulier si vous avez des tâches de longue durée liées aux E / S et ne peuvent pas être divisées et conquises.
Adam Gent
1
@AdamGent - Les frameworks d'acteurs ont une implémentation de boîtes aux lettres basées sur le blocage des files d'attente, mais c'est un bogue à mon avis, car le blocage ne fonctionne pas au-delà des limites asynchrones et ne fonctionne donc que dans les démos. Pour moi, cela a été une source de frustration, comme par exemple la notion d'Akka de gérer le débordement est de bloquer, au lieu de laisser tomber les messages, jusqu'à la version 2.4 qui n'est pas encore sortie. Cela dit, je ne pense pas qu'il existe des cas d'utilisation pour lesquels le blocage des files d'attente peut être supérieur. Vous confondez également deux choses qui ne devraient pas être confondues. Je n'ai pas parlé de blocage des E / S.
Alexandru Nedelcu
1
@AlexandruNedelcu alors que je suis généralement d'accord avec vous sur la contre-pression, je n'ai pas encore vu de système "sans verrouillage" de haut en bas. Quelque part dans une pile technologique, que ce soit Node.js, Erlang, Golang, il utilise une sorte de stratégie d'attente, qu'il s'agisse d'une file d'attente de blocage (verrous) ou d'un CAS qui bloque son blocage et, dans certains cas, une stratégie de verrouillage traditionnelle est plus rapide. Il est très difficile de ne pas avoir de verrous à cause de la cohérence et cela est particulièrement important avec le blocage de io et les ordonnanceurs qui sont ~ Producteur / Consommateur. ForkJoinPool fonctionne avec des tâches en cours d'exécution courtes et il a toujours des verrous de rotation CAS.
Adam Gent
1
@AlexandruNedelcu Je suppose que si vous pouvez me montrer comment vous pouvez utiliser un ConcurrentLinkedQueue (qui n'est pas borné par rapport à mon argument de contre-pression faible) pour le modèle Producteur / Consommateur qui est un modèle nécessaire pour les planificateurs et le threadpool, je pense que je vais céder et admettre que BlockingQueue ne doit jamais être utilisé (et vous ne pouvez pas tricher et déléguer à autre chose en faisant l'ordonnancement, c'est-à-dire akka, car cela à son tour fera le blocage / attente car c'est un producteur / consommateur).
Adam Gent
33

LinkedBlockingQueuebloque le consommateur ou le producteur lorsque la file d'attente est vide ou pleine et que le thread consommateur / producteur respectif est mis en veille. Mais cette fonction de blocage a un coût: chaque opération de vente ou de prise est un verrou disputé entre les producteurs ou les consommateurs (le cas échéant), de sorte que dans les scénarios avec de nombreux producteurs / consommateurs, l'opération peut être plus lente.

ConcurrentLinkedQueuen'utilise pas de verrous, mais CAS , sur ses opérations put / take réduisant potentiellement les conflits avec de nombreux threads producteurs et consommateurs. Mais étant une structure de données « attendre libre », ConcurrentLinkedQueuene bloque pas quand il est vide, ce qui signifie que le consommateur devra faire face aux take()retour des nullvaleurs par « attente occupé », par exemple, avec le fil de consommation dévorant CPU.

Donc, lequel est "meilleur" dépend du nombre de threads consommateurs, du taux de consommation / production, etc. Un benchmark est nécessaire pour chaque scénario.

Un cas d'utilisation particulier où le ConcurrentLinkedQueueest clairement meilleur est lorsque les producteurs produisent d'abord quelque chose et terminent leur travail en plaçant le travail dans la file d'attente et seulement après que les consommateurs commencent à consommer, sachant qu'ils seront terminés lorsque la file d'attente est vide. (ici il n'y a pas de concurrence entre producteur-consommateur mais seulement entre producteur-producteur et consommateur-consommateur)

dcernahoschi
la source
un doute ici. Comme vous l'avez mentionné, le consommateur attend lorsque la file d'attente est vide .. combien de temps il attend. Qui lui notifiera de ne pas attendre?
Brinal
@brindal La seule façon d'attendre, que je sache, est en boucle. C'est un problème important qui n'a pas reçu beaucoup d'attention dans les réponses ici. Le simple fait d'exécuter une boucle en attente de données utilise beaucoup de temps processeur. Vous le saurez quand vos fans commenceront à tourner. Le seul remède est de mettre un sommeil dans la boucle. C'est donc un problème dans un système avec un flux de données incohérent. Peut-être ai-je mal compris la réponse d'AlexandruNedelcu, mais un système d'exploitation lui-même est un système concurrent, qui serait extrêmement inefficace s'il était plein de boucles d'événements non bloquantes.
orodbhen
d'accord, mais si unbounded blockingqueueest utilisé, serait-il meilleur que le concurrent basé sur CASConcurrentLinkedQueue
amarnath harish
@orodbhen Mettre un sommeil n'éliminerait pas non plus le gaspillage. Le système d'exploitation doit faire beaucoup de travail pour sortir un thread de veille et planifier et l'exécuter. Si les messages ne sont pas encore disponibles, le travail effectué par votre système d'exploitation est gaspillé. Je recommanderais qu'il soit préférable d'utiliser BlockingQueue, car il a été spécialement conçu pour le problème producteur-consommateur.
Nishit
en fait, je suis très intéressé par la partie «taux de consommation / production», alors lequel est meilleur si le taux est élevé?
workplaylifecycle
0

Une autre solution (qui ne s'adapte pas bien) est les canaux de rendez-vous: java.util.concurrent SynchronousQueue

Ovidiu Lupas
la source
0

Si votre file d'attente n'est pas extensible et ne contient qu'un seul thread producteur / consommateur. Vous pouvez utiliser la file d'attente sans verrouillage (vous n'avez pas besoin de verrouiller l'accès aux données).

Rahul
la source