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

Considere la siguiente situación:

• Tiene un programa que crea numerosos 'trabajos' que deben procesarse y los coloca en una cola.
• Usted 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.
• Podría 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.

Podría hacer que el trabajador verifique el trabajo que toma y vea si esa categoría de trabajos tiene otro trabajador que actualmente está procesando en su contra, y si es así, vuelva a enviar el trabajo a la cola para procesarlo más adelante. Esto parece una forma 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.

Hay dos partes para este problema.

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 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 el trabajo.

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

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

master 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 de la categoría

master 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 trabajar

verificaciones maestras con colas y cola maestra en el siguiente trabajo y asigna a trabajadores de categoría disponibles.

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

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

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

Puede hacer esto lo suficientemente bueno haciendo que los trabajadores escaneen la cola para una próxima tarea factible, y luego devuelvan todo menos eso a la cola si encuentran una. Alternativamente devuelva todo, luego duerma. Si el sueño 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 tryy releasebloqueamos (tanto sin bloqueo) como nuestras operaciones de cola add, gety is_emptyal getser una operación de bloqueo y espera.

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

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

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()

dónde

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 cuidadoso apretón de manos de bloqueo aquí. El trabajador prueba el bloqueo y, si está bloqueado, agrega el trabajo a la cola. Pero luego debe probar la cerradura nuevamente para verificar que todavía es responsabilidad de otra persona hacer el trabajo. Por si acaso el trabajador de categoría terminó mientras estaba haciendo la manipulación de la cola.

(Este es el tipo de detalle de bloqueo que la gente suele arruinar. El error será imposible de reproducir de manera confiable, pero se arruina de manera aleatoria e inequívoca en la producción ...)