ArrayBlockingQueue utiliza un único bloqueo para la inserción y eliminación, pero LinkedBlockingQueue utiliza 2 bloqueos separados

Question

Estaba revisando el código fuente de ArrayBlockingQueue y LinkedBlockingQueue. LinkedBlockingQueue tiene un putLock y un takeLock para insertar y eliminar, respectivamente, pero ArrayBlockingQueue usa solo 1 bloqueo. Creo que LinkedBlockingQueue se implementó según el diseño descrito en Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms. En este documento, mencionan que mantienen un nodo ficticio para que los enqueuers nunca tengan que acceder a la cabeza y los dequeuers nunca tengan que acceder a la cola, lo que evita los escenarios de interbloqueo. Me preguntaba por qué ArrayBlockingQueue no toma prestada la misma idea y usa 2 bloqueos en su lugar.

Answer 1

ArrayBlockingQueue tiene que evitar sobrescribir las entradas para que sepa dónde están el inicio y el final. Un LinkedBlockQueue no necesita saber esto, ya que le permite al GC preocuparse por limpiar los Nodos en la cola.

Answer 2

Me preguntaba por qué ArrayBlockingQueue no toma prestada la misma idea y usa 2 cerrojos en su lugar.

Porque el ArrayBlockingQueue utiliza una estructura de datos mucho más simple para contener los elementos de la cola.

El ArrayBlockingQueue almacena sus datos en una matriz private final E[] items;. Para que varios hilos se ocupen de este mismo espacio de almacenamiento, ya sea al agregarlos o eliminarlos, tienen que usar el mismo bloqueo. Esto no solo se debe a la barrera de la memoria sino a la protección de exclusión mutua, ya que están modificando la misma matriz.

LinkedBlockingQueue por el otro lado es una lista vinculada de elementos de cola que es completamente diferente y permite la posibilidad de tener un doble bloqueo. Es el almacenamiento interno de los elementos en la cola que habilitó las diferentes configuraciones de bloqueo.

Answer 3

Creo que es posible que ABQ tome prestada la misma idea que LBQ. Consulte mi código http://pastebin.com/ZD1uFy7S y una pregunta similar que hice en SO ArrayBlockingQueue: concurrent put and take.

La razón por la que no lo usaron, se debe principalmente a la complejidad en la implementación, especialmente los iteradores, y el intercambio entre la complejidad y el rendimiento no fue tan lucrativo.

Para obtener más información, echa un vistazo a http://jsr166-concurrency.10961.n7.nabble.com/ArrayBlockingQueue-concurrent-put-and-take-tc1306.html.

Answer 4

Se usan 2 bloqueos en LBQ para restringir el acceso a la cabeza y al bloqueo al mismo tiempo. El bloqueo del cabezal no permite que dos elementos se eliminen al mismo tiempo y el bloqueo de cola no permite que dos elementos se agreguen simultáneamente a la cola. los dos cierres juntos evitan las carreras.