offer - Implementaciones de Java Queue, ¿cuál?

offer java method

Question

De Javadoc:

• Una ConcurrentLinkedQueue es una opción adecuada cuando muchos hilos compartirán 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 suele tener un rendimiento mayor que las colas basadas en arreglos, 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 debería usar ConcurrentLikedQueue u otros (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

1. SynchronousQueue (tomado de otra question )

SynchronousQueue es más un handoff, mientras que LinkedBlockingQueue solo permite un elemento individual. 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 (Implementación de LinkedList pero no exactamente Implementación JDK de LinkedList Utiliza nodo de clase interna estática 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 opinión, la mayor diferencia entre ArrayBlockingQueue y LinkedBlockingQueue es claro desde el constructor, uno tiene la estructura de datos subyacente Array y otra linkedList .

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

Answer 2

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 3

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 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, su 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 4

ConcurrentLinkedQueue no está bloqueado, LinkedBlockingQueue no lo está. 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.

Answer 5

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

Los BlockingQueue 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 final (implementa la interfaz Deque).

Como ArrayBlockingQueue solo es útil si quieres limitar el número de elementos, me quedaría con LinkedBlockingQueue .

Answer 6

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 tomará un bloqueo antes de 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 le toma a mis productores conseguir 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.