2009-10-14 23 views
7

Tengo algunos problemas para comprender la idea de una cola simultánea. Entiendo que una cola es una estructura de datos FIFO o primer llegado primer servido.concurrent queue - pregunta general (descripción y uso)

Ahora cuando agregamos la parte de simultaneidad, que interpreto como seguridad de subprocesos (por favor, avíseme si es incorrecta), las cosas se ponen un poco borrosas. Por concurrencia nos referimos a la forma en que varios hilos pueden agregarse a la cola, o eliminar (dar servicio a un elemento) de la cola. ¿La simultaneidad proporciona una sensación de orden a estas operaciones?

Agradecería mucho una descripción general de la funcionalidad de una cola simultánea. Una publicación similar here no es tan general como esperaba.

También existe tal cosa como una cola de prioridad concurrente? ¿Cuál sería su uso?

Muchas gracias de antemano, por cualquier breve explicación o enlaces útiles sobre este tema.

Respuesta

0

Debe comenzar revisando la definición de interfaz BlockingQueue, ya que es la piedra angular para usar colas para la comunicación entre hilos y contiene métodos de utilidad para permitir que los hilos de productor y consumidor accedan a la cola de forma bloqueada o no. Esto, junto con el acceso seguro de subprocesos es mi comprensión de lo que constituye una "cola concurrente" (aunque nunca he oído hablar de esa frase - BlockingQueue simplemente existe en el paquete java.util.concurrent).

Para responder a la segunda parte de su pregunta, la implementación de la cola de prioridad que debe estudiar es PriorityBlockingQueue. Esto puede ser útil si los hilos del productor están produciendo tareas de diferentes prioridades (por ejemplo, solicitudes de "usuarios normales" y "usuarios avanzados") y desea controlar el orden en que las tareas son procesadas por su (s) hilo (s) de consumo. . Una posible trampa para evitar es la inanición de tareas de baja prioridad que nunca se eliminan de la cola debido a la afluencia constante de tareas de mayor prioridad.

0

Entiendo por concurrencia que la cola es segura para subprocesos. Esto no significa que será eficiente. Sin embargo, me imagino que la cola de Java utiliza una implementación sin bloqueos, lo que significa que hay poco o nada de penatly cuando dos subprocesos intentan hacer un push o un pop al mismo tiempo. Lo que generalmente ocurre es que usan bloqueo atómico en un nivel de ensamblador que asegura que el mismo objeto no se pueda abrir dos veces.

Una vez escribí una cola FIFO sin bloqueos (en Delphi) que funcionó muy bien. Mucho más eficiente que una versión anterior que usaba secciones críticas. La versión CS se detuvo, especialmente con muchos hilos que intentan acceder a la cola. Sin embargo, la versión sin bloqueo no tenía cuellos de botella, muchos hilos accedían a ella mucho.

+0

Adquirir un bloqueo para modificar una implementación de Queue segura para subprocesos agrega poca sobrecarga y todas las implementaciones de BlockingQueue dentro del paquete java.util.concurrent usarán al menos un bloqueo (algunos usan dos para poner/tomar). Sin bloqueos, los productores/consumidores no pueden realizar bloqueos de puts/takes y las operaciones masivas (por ejemplo, drainTo) no se pueden realizar atómicamente. – Adamski

+0

Pensé que Java usa colas sin bloqueo: http://java.sun.com/j2se/1.5.0/docs/api/java/util/concurrent/ConcurrentLinkedQueue.html – Steve

5

La idea de que un BlockingQueue ofrece poca sobrecarga es un fallo bit inicial. La adquisición de un bloqueo invoca una sobrecarga considerable. Solo con el cambio de contexto estamos hablando de miles de instrucciones. No solo eso, sino que el progreso de un hilo afectará directamente a otro hilo. Ahora, no es tan malo como lo era hace años, pero en comparación con el no bloqueo, es sustancial.

cerraduras uso de BlockingQueue de exclusión mutua

ArrayBlockingQueue, LinkedBlockingQueue, PriorityBlockingQUeue: son tres de cola de bloqueo, mientras que

ConcurrentLinkedQueue, java 1.7 LinkedTransferQueue: Utiliza el Michael y Scott, el algoritmo no cola de bloqueo.

En contención moderada a baja (que es más un escenario del mundo real), las colas que no bloquean significativamente superan las colas de bloqueo.

Y para tener en cuenta el comentario de Steve sobre la falta de cuellos de botella. Bajo fuerte contención, un algoritmo que no bloquea puede bloquear el cuello en los intentos constantes de cas, mientras que el bloqueo suspenderá los hilos. Luego vemos que un BlockingQueue bajo fuerte contención ligeramente realiza una cola que no bloquea, pero ese tipo de contención no es una norma de ninguna manera.

Cuestiones relacionadas