LinkedBlockingQueue vs ConcurrentLinkedQueue

112

Mi pregunta se relaciona con esta pregunta formulada anteriormente. En situaciones en las que estoy usando una cola para la comunicación entre los hilos del productor y del consumidor, ¿la gente generalmente recomendaría usar LinkedBlockingQueueo ConcurrentLinkedQueue?

¿Cuáles son las ventajas / desventajas de usar uno sobre el otro?

La principal diferencia que puedo ver desde la perspectiva de la API es que a LinkedBlockingQueuese puede limitar opcionalmente.

java multithreading data-structures concurrency queue Adamski
fuente

Respuestas:

110

Para un hilo de productor / consumidor, no estoy seguro de que ConcurrentLinkedQueuesea ​​una opción razonable, no se implementa BlockingQueue, que es la interfaz fundamental para las colas de productor / consumidor en mi opinión. Tendría que llamar poll(), esperar un poco si no hubiera encontrado nada y luego sondear de nuevo, etc., lo que provocaría retrasos cuando llega un nuevo elemento e ineficiencias cuando está vacío (debido a que se despierta innecesariamente de la suspensión). .

De los documentos de BlockingQueue:

BlockingQueue Las implementaciones están diseñadas para usarse principalmente para colas de productores-consumidores.

Sé que no dice estrictamente que solo se deben usar las colas de bloqueo para las colas de productor-consumidor, pero aun así ...

Jon Skeet
fuente
4
Gracias Jon, no me había dado cuenta. Entonces, ¿dónde / por qué usarías ConcurrentLinkedQueue?
Adamski
27
Cuando necesita acceder a la cola desde muchos subprocesos, pero no necesita "esperar".
Jon Skeet
2
A ConcurrentLinkedQueuetambién es útil si su hilo está comprobando varias colas. Por ejemplo, en un servidor multiinquilino. Suponiendo que, por razones de aislamiento, no utilice una sola cola de bloqueo y un discriminador de inquilinos en su lugar.
LateralFractal
su caso solo es válido si usamos cola limitada , en cola ilimitadatake() y put()simplemente consume recursos adicionales (términos de sincronización) que ConcurrentLinkedQueue . aunque es el caso de usar colas limitadas para escenarios de Productor-consumidor
amarnath harish
@Adamski IMO, ConcurrentLinkedQueue es solo una lista enlazada para ser utilizada en un entorno de subprocesos múltiples. La mejor analogía para esto sería ConcurrentHashMap y HashMap.
Nishit
69

Esta pregunta merece una mejor respuesta.

Java ConcurrentLinkedQueuese basa en el famoso algoritmo de Maged M. Michael y Michael L. Scott para colas sin bloqueo sin bloqueo .

"Sin bloqueo" como término aquí para un recurso en disputa (nuestra cola) significa que independientemente de lo que haga el programador de la plataforma, como interrumpir un hilo, o si el hilo en cuestión es simplemente demasiado lento, otros hilos compiten por el mismo recurso todavía podrá progresar. Si hay un bloqueo involucrado, por ejemplo, el hilo que sostiene el bloqueo podría interrumpirse y todos los hilos que esperan ese bloqueo se bloquearían. Los bloqueos intrínsecos (la synchronizedpalabra clave) en Java también pueden tener una penalización severa para el rendimiento, como cuando el bloqueo sesgadoestá involucrado y tiene contención, o después de que la máquina virtual decida "inflar" el bloqueo después de un período de gracia de giro y bloquear los subprocesos en conflicto ... por lo que en muchos contextos (escenarios de contención baja / media), comparar y Los conjuntos de referencias atómicas pueden ser mucho más eficientes y esto es exactamente lo que están haciendo muchas estructuras de datos sin bloqueo.

Java ConcurrentLinkedQueueno solo no bloquea, sino que tiene la asombrosa propiedad de que el productor no compite con el consumidor. En un escenario de productor único / consumidor único (SPSC), esto realmente significa que no habrá disputas de las que hablar. En un escenario de productor múltiple / consumidor único, el consumidor no competirá con los productores. Esta cola tiene contención cuando varios productores lo intentan offer(), pero eso es concurrencia por definición. Es básicamente una cola sin bloqueos de propósito general y eficiente.

En cuanto a que no sea un BlockingQueue, bueno, bloquear un hilo para esperar en una cola es una forma terriblemente terrible de diseñar sistemas concurrentes. No lo hagas. Si no puede descubrir cómo usar un ConcurrentLinkedQueueen un escenario de consumidor / productor, simplemente cambie a abstracciones de nivel superior, como un buen marco de actor.

Alexandru Nedelcu
fuente
8
Según su último párrafo, ¿por qué dice que esperar en una cola es una forma terrible de diseñar sistemas concurrentes? Si tenemos un grupo de subprocesos con 10 subprocesos que comen tareas de una cola de tareas, ¿qué tiene de malo bloquear cuando la cola de tareas tiene menos de 10 tareas?
Pacerier
11
@AlexandruNedelcu No puedes hacer una afirmación tan radical como "terriblemente terrible", donde muy a menudo los marcos de actores que dices que usen usan grupos de subprocesos que tú mismo usas en BlockingQueue . Si necesita un sistema altamente reactivo y sabe cómo lidiar con la contrapresión (algo que mitigan las colas de bloqueo), el no bloqueo es claramente superior. Pero ... a menudo, el bloqueo de IO y el bloqueo de colas pueden superar el no bloqueo, especialmente si tiene tareas de ejecución prolongada que están vinculadas a IO y no se pueden dividir y conquistar.
Adam Gent
1
@AdamGent: los marcos de actores tienen implementación de buzones de correo basados ​​en colas de bloqueo, pero eso es un error en mi opinión, porque el bloqueo no funciona en límites asincrónicos y, por lo tanto, solo funciona en demostraciones. Para mí, esto ha sido una fuente de frustración, ya que, por ejemplo, la noción de Akka de lidiar con el desbordamiento es bloquear, en lugar de soltar mensajes, hasta la versión 2.4, es decir, que aún no ha salido. Dicho esto, no creo que haya casos de uso en los que el bloqueo de colas pueda ser superior. También está combinando dos cosas que no deberían combinarse. No he hablado sobre el bloqueo de E / S.
Alexandru Nedelcu
1
@AlexandruNedelcu, aunque en general estoy de acuerdo con usted sobre la contrapresión, todavía no he visto un sistema "sin bloqueo" de arriba a abajo. En algún lugar de una pila de tecnología, ya sea Node.js, Erlang, Golang, está utilizando una especie de estrategia de espera, ya sea una cola de bloqueo (bloqueos) o CAS girando su bloqueo y, en algunos casos, una estrategia de bloqueo tradicional es más rápida. Es muy difícil no tener bloqueos debido a la consistencia y esto es especialmente importante con el bloqueo de io y los programadores que son ~ Productor / Consumer. ForkJoinPool funciona con tareas de ejecución corta y todavía tiene bloqueos giratorios CAS.
Adam Gent
1
@AlexandruNedelcu Supongo que si puede mostrarme cómo puede usar un ConcurrentLinkedQueue (que no está limitado por cierto, de ahí mi débil argumento de contrapresión) para el patrón Productor / Consumer, que es un patrón necesario para los programadores y la combinación de hilos, creo que cederé y admitiré que BlockingQueue nunca debe usarse (y no puede hacer trampa y delegar en otra cosa que haga la programación, es decir, akka, ya que eso a su vez hará el bloqueo / espera, ya que es un productor / consumidor).
Adam Gent
33

LinkedBlockingQueuebloquea al consumidor o al productor cuando la cola está vacía o llena y el hilo consumidor / productor respectivo se pone en suspensión. Pero esta característica de bloqueo tiene un costo: cada operación de compra o venta se bloquea entre los productores o consumidores (si es que hay muchos), por lo que en escenarios con muchos productores / consumidores la operación puede ser más lenta.

ConcurrentLinkedQueueno está usando bloqueos, sino CAS , en sus operaciones de venta / adquisición, lo que potencialmente reduce la contención con muchos hilos de productores y consumidores. Pero al ser una estructura de datos "sin esperar", ConcurrentLinkedQueueno se bloqueará cuando esté vacía, lo que significa que el consumidor tendrá que lidiar con los valores take()devueltos null"esperando ocupado", por ejemplo, con el hilo del consumidor consumiendo CPU.

Entonces, cuál es "mejor" depende del número de hilos de consumo, de la tasa que consumen / producen, etc. Se necesita un punto de referencia para cada escenario.

Un caso de uso particular en el ConcurrentLinkedQueueque claramente es mejor es cuando los productores primero producen algo y terminan su trabajo colocando el trabajo en la cola y solo después de que los consumidores comienzan a consumir, sabiendo que terminarán cuando la cola esté vacía. (aquí no hay concurrencia entre productor-consumidor sino solo entre productor-productor y consumidor-consumidor)

dcernahoschi
fuente
una duda aquí. Como mencionaste, el consumidor espera cuando la cola está vacía ... ¿cuánto tiempo espera? ¿Quién lo notificará para que no espere?
Brinal
@brindal La única forma de esperar, que yo sepa, es en un bucle. Lo cual es un problema importante al que no se le ha prestado mucha atención en las respuestas aquí. El simple hecho de ejecutar un bucle a la espera de datos consume mucho tiempo de procesador. Lo sabrás cuando tus fans empiecen a acelerar. El único remedio es poner un sueño en el circuito. Entonces es un problema en un sistema con flujo de datos inconsistente. Quizás no entiendo bien la respuesta de AlexandruNedelcu, pero un sistema operativo en sí mismo es un sistema concurrente, que sería enormemente ineficiente si estuviera lleno de bucles de eventos sin bloqueo.
orodbhen
bien, pero si unbounded blockingqueuese usa, sería mejor que el concurrente basado en CASConcurrentLinkedQueue
amarnath harish
@orodbhen Ponerse a dormir tampoco eliminaría el desperdicio. El sistema operativo tiene que hacer mucho trabajo para sacar un hilo de la suspensión y programarlo y ejecutarlo. Si los mensajes aún no están disponibles, ese trabajo realizado por su sistema operativo se desperdicia. Recomendaría que es mejor usar BlockingQueue, ya que fue diseñado específicamente para problemas entre productores y consumidores.
Nishit
en realidad, estoy muy interesado en la parte de "tasa de consumo / producción", entonces, ¿cuál es mejor si la tasa sube?
workplaylifecycle
0

Otra solución (que no escala bien) son los canales de encuentro: java.util.concurrent SynchronousQueue

Ovidiu Lupas
fuente
0

Si su cola no es expandible y contiene solo un hilo productor / consumidor. Puede utilizar la cola sin bloqueo (no es necesario bloquear el acceso a los datos).

Rahul
fuente