¿Qué implementación de cola concurrente debo usar en Java?

De los JavaDocs:

• Un ConcurrentLinkedQueue es una opción apropiada cuando muchos hilos compartirán el acceso a una colección común. Esta cola no permite elementos nulos.
• ArrayBlockingQueue es un clásico "búfer acotado", en el que una matriz de tamaño fijo contiene elementos insertados por 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 generalmente tiene un mayor rendimiento que las colas basadas en matrices, pero un rendimiento menos predecible en la mayoría de las aplicaciones concurrentes.

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

No entiendo qué implementación usar. ¿Alguien puede explicar cuáles son las diferencias?

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

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

Tomando el más fácil primero, ArrayBlockingQueuees una cola de un tamaño fijo. Entonces, si establece el tamaño en 10 e intenta insertar un undécimo elemento, la instrucción de inserción se bloqueará hasta que otro hilo elimine un elemento. El problema de la equidad es qué 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 recibe. De lo contrario, un subproceso dado puede esperar más que otros subprocesos, lo que provoca un comportamiento impredecible (a veces un subproceso solo tomará varios segundos porque otros subprocesos que comenzaron más tarde se procesaron primero). La desventaja es que se necesitan gastos generales para gestionar la equidad, lo que ralentiza el rendimiento.

La diferencia más importante entre LinkedBlockingQueuey ConcurrentLinkedQueuees que si solicita un elemento de a LinkedBlockingQueuey la cola está vacía, su hilo esperará hasta que haya algo allí. A ConcurrentLinkedQueueregresará de inmediato con el comportamiento de una cola vacía.

Cuál depende de si necesita el bloqueo. Cuando tienes muchos productores y un consumidor, parece que sí. Por otro lado, donde tiene muchos consumidores y solo un productor, es posible que no necesite el comportamiento de bloqueo y puede estar feliz de que los consumidores verifiquen si la cola está vacía y continúen si es así.

ConcurrentLinkedQueue significa que no se toman 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 head / tail 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á nuevamente.

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

La equidad significa que la implementación de bloqueo mantendrá los hilos ordenados. Es decir, si el hilo A entra y luego el hilo B entra, el hilo A obtendrá primero el bloqueo. Sin equidad, no está definido realmente qué sucede. Lo más probable es que sea el próximo hilo 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 poner 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 reposo. Tienes que manejar eso tú mismo.

El título de su pregunta menciona el bloqueo de colas. Sin embargo, noConcurrentLinkedQueue es una cola de bloqueo.

Los BlockingQueues son ArrayBlockingQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, PriorityBlockingQueue, y SynchronousQueue.

Algunos de estos no son claramente ajuste para su propósito ( DelayQueue, PriorityBlockingQueuey SynchronousQueue). LinkedBlockingQueuey LinkedBlockingDequeson idénticos, excepto que este último es una Cola de doble extremo (implementa la interfaz Deque).

Como ArrayBlockingQueuesolo es útil si desea limitar la cantidad de elementos, me quedaría con ellos LinkedBlockingQueue.

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

1. SynchronousQueue(Tomado de otra pregunta )

SynchronousQueuees más un traspaso, mientras que el LinkedBlockingQueuesolo permite un solo elemento. La diferencia es que la put()llamada a a SynchronousQueueno volverá hasta que haya una take()llamada correspondiente , pero con un LinkedBlockingQueuetamaño de 1, la put()llamada (a una cola vacía) volverá inmediatamente. Es esencialmente la BlockingQueueimplementación para cuando realmente no quieres una cola (no quieres mantener ningún dato pendiente).

2. LinkedBlockingQueue( LinkedListImplementación pero no exactamente JDK Implementación de LinkedListUtiliza un nodo de clase interna estático para mantener enlaces entre elementos)

Constructor para LinkedBlockingQueue

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 )
}

Clase de nodo utilizada para mantener enlaces

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

3) ArrayBlockingQueue (Implementación de matriz)

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();
}

En mi humilde opinión, la diferencia más grande entre ArrayBlockingQueuey LinkedBlockingQueueestá clara desde el constructor uno tiene la estructura de datos subyacente Array y otra lista enlazada .

ArrayBlockingQueueutiliza el algoritmo de doble condición de bloqueo único y LinkedBlockingQueuees una variante del algoritmo de "cola de dos bloqueos" y tiene 2 bloqueos y 2 condiciones (takeLock, putLock)

ConcurrentLinkedQueue no tiene 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, pruebe ConcurrentLinkedQueue + LockSupport.