implementaciones de Java Queue, ¿cuál?

Question

De Javadoc:

• Un ConcurrentLinkedQueue es una opción apropiada cuando muchos hilos comparten el acceso a una colección común. Esta cola no permite elementos nulos.
• ArrayBlockingQueue es un clásico "buffer delimitado", en el que una matriz de tamaño fijo contiene elementos insertados por los productores y extraídos por los consumidores. Esta clase admite una política de equidad opcional para ordenar hilos de productores y consumidores en espera
• LinkedBlockingQueue suelen tener un rendimiento mayor que las colas basadas en matrices, pero un rendimiento menos predecible en la mayoría de las aplicaciones simultáneas.

Tengo 2 escenarios, uno requiere la cola para admitir a muchos productores (hilos que lo usan) con un consumidor y el otro es al revés.

No entiendo si debo usar ConcurrentLikedQueue o los demás (las implementaciones array o linkedList). ¿Dónde se supone que todas estas implementaciones son concurrentes? Quiero decir, ¿alguien puede explicarme cuál es la diferencia entre ConcurrentLikedQueue y LinkedBlockingQueue?

Además, ¿cuál es la política de equidad opcional en el ArrayBlockingQueue por favor?

Answer 1

Básicamente, la diferencia entre ellos son las características de rendimiento y el comportamiento de bloqueo.

Tomando lo más fácil primero, ArrayBlockingQueue es una cola de un tamaño fijo. Entonces, si establece el tamaño en 10 e intenta insertar un 11º elemento, la instrucción de inserción se bloqueará hasta que otro hilo elimine un elemento. El problema de la equidad es lo que sucede si varios subprocesos intentan insertarse y eliminarse al mismo tiempo (en otras palabras, durante el período en que se bloqueó la cola). Un algoritmo de equidad asegura que el primer hilo que pregunta es el primer hilo que obtiene. De lo contrario, un subproceso dado puede esperar más tiempo que otros subprocesos, lo que provoca un comportamiento impredecible (a veces, un subproceso tardará varios segundos porque otros subprocesos que se iniciaron más tarde se procesaron primero). La desventaja es que se requiere una sobrecarga para gestionar la equidad, ralentizando el rendimiento.

La diferencia más importante entre LinkedBlockingQueue y ConcurrentLinkedQueue es que si solicita un elemento de un LinkedBlockingQueue y la cola está vacía, el hilo esperará hasta que haya algo allí. Un ConcurrentLinkedQueue regresará de inmediato con el comportamiento de una cola vacía.

Depende de si necesita el bloqueo. Donde tiene muchos productores y un consumidor, parece que sí. Por otro lado, cuando tiene muchos consumidores y un solo productor, puede que no necesite el comportamiento de bloqueo, y puede estar contento de hacer que los consumidores comprueben si la cola está vacía y seguir adelante si es así.

Answer 2

El título de su pregunta menciona Colas de bloqueo. Sin embargo, ConcurrentLinkedQueue es no una cola de bloqueo.

Los BlockingQueue s son ArrayBlockingQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, PriorityBlockingQueue y SynchronousQueue.

Algunos de estos claramente no son aptos para su propósito (DelayQueue, PriorityBlockingQueue, y SynchronousQueue). LinkedBlockingQueue y LinkedBlockingDeque son idénticos, excepto que este último es un Queue de doble extremo (implementa la interfaz Deque).

Dado que ArrayBlockingQueue solo es útil si desea limitar el número de elementos, me limitaría a LinkedBlockingQueue.

Answer 3

ConcurrentLinkedQueue significa que no se realizan bloqueos (es decir, no hay llamadas sincronizadas (esto) o Lock.lock). Utilizará una operación CAS - Compare and Swap durante las modificaciones para ver si el nodo cabeza/cola sigue siendo el mismo que cuando comenzó. Si es así, la operación tiene éxito. Si el nodo cabeza/cola es diferente, girará e intentará de nuevo.

LinkedBlockingQueue se bloqueará antes de realizar cualquier modificación. Por lo tanto, sus llamadas de oferta se bloquearán hasta que obtengan el bloqueo. Puede usar la sobrecarga de oferta que toma una TimeUnit para decir que solo está dispuesto a esperar X cantidad de tiempo antes de abandonar el agregado (por lo general, es bueno para las colas de tipo de mensaje donde el mensaje es obsoleto después de X número de milisegundos).

Equidad significa que la implementación de bloqueo mantendrá los hilos ordenados. Es decir, si entra el hilo A y luego entra el hilo B, el hilo A obtendrá primero el bloqueo. Sin equidad, no está definido realmente qué sucede. Lo más probable es que sea el siguiente hilo el que se programe.

En cuanto a cuál usar, depende. Tiendo a usar ConcurrentLinkedQueue porque el tiempo que les toma a mis productores obtener trabajo para colocar en la cola es diverso. No tengo muchos productores produciendo en el mismo momento. Pero el lado del consumidor es más complicado porque la encuesta no entrará en un buen estado de sueño. Tienes que manejar eso tú mismo.

Answer 4

ArrayBlockingQueue tiene una huella de memoria menor, puede reutilizar el nodo del elemento, no como LinkedBlockingQueue que tiene que crear un objeto LinkedBlockingQueue $ Node para cada nueva inserción.

Answer 5

1. SynchronousQueue (tomado de otra question)

SynchronousQueue es más de un traspaso, mientras que el LinkedBlockingQueue simplemente permite que un solo elemento. La diferencia es que la llamada put() a una SynchronousQueue no volverá hasta que haya una llamada take() correspondiente, pero con una LinkedBlockingQueue de tamaño 1, la llamada put() a una cola vacía volverá inmediatamente. Básicamente es la implementación de BlockingQueue para cuando realmente no desea una cola (no desea mantener ningún dato pendiente).

2. LinkedBlockingQueue (Aplicación ListaEnlazada pero no exactamente JDK Implementación de ListaEnlazada Utiliza Nodo clase interna estática para mantener los vínculos entre los elementos)

Constructor para LinkedBlockingQueue

clase Node

public LinkedBlockingQueue(int capacity) 
{ 
     if (capacity < = 0) throw new IllegalArgumentException(); 
     this.capacity = capacity; 
     last = head = new Node<E>(null); // Maintains a underlying linkedlist. (Use when size is not known) 
} 

Se utiliza para mantener los vínculos

static class Node<E> { 
    E item; 
    Node<E> next; 
    Node(E x) { item = x; } 
} 

3.ArrayBlockingQueue (Aplicación Array)

Constructor para ArrayBlockingQueue

public ArrayBlockingQueue(int capacity, boolean fair) 
{ 
      if (capacity < = 0) 
       throw new IllegalArgumentException(); 
      this.items = new Object[capacity]; // Maintains a underlying array 
      lock = new ReentrantLock(fair); 
      notEmpty = lock.newCondition(); 
      notFull = lock.newCondition(); 
} 

mi humilde opinión mayor diferencia entre ArrayBlockingQueue y LinkedBlockingQueue se desprende de constructor uno tiene subyacente matriz de estructura de datos y otra LinkedList.

ArrayBlockingQueue utiliza single-lock double condition algorithm y LinkedBlockingQueue es variante del algoritmo de "dos cola de bloqueo" y tiene 2 cerraduras 2 condiciones (takeLock, putLock)

Answer 6

ConcurrentLinkedQueue está libre de bloqueo, LinkedBlockingQueue no lo es. Cada vez que invocas LinkedBlockingQueue.put() o LinkedBlockingQueue.take(), primero debes adquirir el bloqueo. En otras palabras, LinkedBlockingQueue tiene poca concurrencia. Si le importa el rendimiento, intente ConcurrentLinkedQueue + LockSupport.