¿Cómo diseñar mejor una cola de trabajos con restricciones?

8

Considera la siguiente situación:

  • Tiene un programa que crea numerosos "trabajos" que deben procesarse y los coloca en una cola.
  • Tiene otros programas de trabajadores que toman el siguiente "trabajo" en línea para que puedan procesar ese trabajo.
  • Cada trabajo tiene una categoría.
  • Puede haber cualquier número de categorías.
  • Dos trabajos que tienen la misma categoría no pueden ser procesados al mismo tiempo por trabajadores separados.
  • Un trabajador puede procesar un trabajo a la vez.

Una cola tradicional no funcionaría en esta situación porque existe la posibilidad de que múltiples trabajos de la misma categoría se procesen simultáneamente, lo que no está permitido.

Puede hacer que el trabajador verifique el trabajo que toma y ver si esa categoría de trabajo tiene otro trabajador que actualmente se está procesando en su contra y, si es así, volver a enviar el trabajo a la cola para ser procesado más adelante. Esto parece una manera ineficiente de resolver este problema. ¿Existen estructuras de datos o patrones de diseño que puedan resolver este problema?

Si necesita más aclaraciones, hágamelo saber.

    
pregunta merp 22.04.2016 - 19:28

2 respuestas

4

Este problema tiene dos partes.

Uno: la lista desconocida de categorías posibles.

Dos: comunicación entre procesos entre los trabajadores para evitar que dos trabajos de la misma categoría se procesen simultáneamente.

Si tenía una lista conocida de categorías, puede tener una cola y un trabajador por categoría.

Con las categorías desconocidas, aún puede tener una cola por categoría, pero tener un trabajador de cola por categoría requiere que supervise todas las colas y active nuevos trabajadores cuando aparezca una nueva categoría.

Esto se puede lograr con un trabajador 'maestro' que reparte trabajos

Todos los trabajos van en la cola 'maestra'.

El trabajador de categoría

crea una cola privada y se registra con el maestro como disponible para trabajar.

el trabajador maestro recoge trabajos, verifica la categoría, verifica los trabajadores disponibles y asigna el trabajo a uno de ellos poniéndolo en su cola privada.

El maestro puede realizar un seguimiento de la categoría asignada al trabajador.

el maestro recoge el siguiente trabajo, es la misma categoría y el trabajador todavía está ocupado, por lo que coloca los trabajos en una cola de espera específica para cada categoría

el maestro obtiene el siguiente trabajo, es una nueva categoría por lo que lo asigna a otro trabajador de categoría.

El trabajador de categoría completa el trabajo y se vuelve a registrar para el trabajo

el maestro controla las colas en espera y la cola maestra el siguiente trabajo y las asigna a los trabajadores de categorías disponibles.

Si un trabajador de categoría se bloquea durante un trabajo, no se volverá a registrar. Por lo tanto, el maestro puede tener alguna lógica de tiempo de espera donde se dará por vencido y comenzará a asignar las categorías a otro trabajador.

También debe tener cuidado de tener solo un solo trabajador maestro en un momento dado. Esto confirma un bloqueo exclusivo en la cola maestra de algún tipo

    
respondido por el Ewan 22.04.2016 - 20:10
2

La desventaja de su propuesta ineficiente se produce cuando hay 2 trabajos para una categoría. Ahora uno está funcionando ... y todos los demás están haciendo una espera ocupada.

Puede hacer que esto sea lo suficientemente bueno haciendo que los trabajadores escaneen la cola para una próxima tarea factible, luego devuelvan todo menos la cola si encuentran una. Alternativamente devuelve todo, luego duerme. Si el tiempo de inactividad tiene algo de aleatoriedad y retroceso exponencial, la "espera ocupada" no estará demasiado ocupada.

Para un enfoque más eficiente, un trabajador que toma un trabajo es responsable de hacer esa categoría hasta que no quede nada más de esa categoría. Luego vuelves a ser un trabajador regular. Pero hay algunas sutilezas.

Para verlos, supongamos que podemos bloquear try y release (ambos no bloqueantes) y nuestras operaciones de cola son add , get y is_empty con get siendo un bloque y esperar operación.

Asumiremos una cola general, y luego, para cada categoría, una cola y un bloqueo.

Aquí está el flujo de trabajo básico.

while obj = get from main queue:
    if try category lock:
        do obj job
        do_whole_category_queue()
    else:
        add obj to category queue
        if try category lock:
            do_whole_category_queue()

donde

procedure do_whole_category_queue
    while not category queue is_empty:
        obj = get from category queue
        do obj job
    release category lock
    if not is_empty category queue:
        if try category lock:
            do_whole_category_queue()

Tenga en cuenta el apretón de manos de bloqueo cuidadoso aquí. El trabajador prueba el bloqueo y, si está bloqueado, agrega el trabajo a la cola. Pero luego tiene que probar el bloqueo nuevamente para verificar que aún es responsabilidad de otra persona hacer el trabajo. En caso de que el trabajador de la categoría haya terminado mientras estaba haciendo la manipulación de la cola.

(Este es el tipo de detalle de bloqueo que las personas a menudo cometen errores. El error será imposible de reproducir de manera confiable, pero los errores se producen de forma aleatoria e indiscutible en la producción ...)

    
respondido por el btilly 23.04.2016 - 02:51

Lea otras preguntas en las etiquetas