java - sustitucion - Elegir una estructura de datos para una variante del problema del consumidor productor
problemas de excedentes del consumidor y del productor (2)
Parece que realmente deberías tener dos colas:
- Sin procesar
- En progreso
Un consumidor arrojaría atómicamente (a través de un bloqueo) de la cola no procesada y la agregaría a la cola en progreso. De esta forma, múltiples consumidores pueden trabajar simultáneamente ... pero el productor puede tomar una instantánea de ambas colas cuando sea necesario. Cuando el consumidor finaliza una tarea, la elimina de la cola en progreso. (Eso realmente no necesita ser una cola, ya que nada es "tirador" de ella como tal. Solo una colección que puede agregar y eliminar fácilmente).
Dado que necesitará bloqueo para hacer la transferencia atómica, probablemente no necesite que las colas subyacentes sean simultáneas; ya estará protegiendo todo el acceso compartido.
En este momento, tengo una cola, con múltiples productores y un solo consumidor.
La operación del hilo del consumidor es lenta. Además, el consumidor toma el elemento de la cola a través de una operación de observación, y hasta que se complete la operación de consumo, el elemento no puede eliminarse de la cola. Esto se debe a que el hilo del productor como operación secundaria también toma una instantánea de todos los elementos que no se procesan completamente en ese momento.
Ahora, quiero cambiar mi código para admitir múltiples consumidores. Entonces, digamos que tengo tres hilos, un hilo tomará el primer elemento, que se puede leer a través de una operación de asomarse. El segundo hilo de consumidor puede ir para el segundo elemento, pero no tengo forma de recuperarlo ya que la cola no admite la recuperación del segundo elemento.
Entonces, la opción de usar un ConcurrentLinkedQueue estándar (que estoy usando en este momento) está fuera.
Estoy pensando en usar una cola de prioridad, pero luego tendré que asociar con cada elemento una bandera que me diga si este elemento ya está siendo utilizado por algún hilo o no.
¿Qué estructura de datos es más adecuada para este problema?
Estoy de acuerdo con Jon Skeet (+1) en que necesita dos tiendas para registrar artículos en espera y en progreso. LinkedBlockingQueue y LinkedBlockingQueue que cada uno de tus consumidores llamara a take() en él. Cuando un elemento llega a la cola, será tomado por uno de los consumidores.
La grabación de lo que está en progreso y lo que se completa sería una operación separada. Mantendría un HashSet de todos los elementos que aún no se han completado y mi productor agregaría primero (atómicamente) el elemento al HashSet de elementos no completados y luego mostraría el elemento en la cola. Una vez que un consumidor ha terminado su trabajo, elimina el elemento del HashSet.
Su productor puede escanear el HashSet para determinar qué está pendiente.