Implementaciones de Java Queue, ¿cuál?

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?

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

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 locking. 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 locking, y puede estar contento de hacer que los consumidores comprueben si la cola está vacía y seguir adelante si es así.

ConcurrentLinkedQueue significa que no se realizan lockings (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 locking antes de cualquier modificación. Por lo tanto, sus llamadas de oferta se bloquearán hasta que obtengan el locking. 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 locking mantendrá los hilos ordenados. Es decir, si entra el hilo A y luego entra el hilo B, el hilo A obtendrá primero el locking. 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.

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

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 .

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.

  1. SynchronousQueue (tomado de otra pregunta )

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 item; Node 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 locking único y LinkedBlockingQueue es una variante del algoritmo de "dos cola de locking" y tiene 2 condiciones de 2 lockings (takeLock, putLock)

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