Como melhor projetar uma fila de tarefas com restrições?

Considere a seguinte situação:

• Você tem um programa que cria vários 'trabalhos' que precisam ser processados ​​e os coloca em uma fila.
• Você tem outros programas de trabalho que agarram o próximo 'trabalho' na fila para que eles possam processar esse trabalho.
• Cada trabalho tem uma categoria.
• Pode haver qualquer número de categorias.
• Dois trabalhos que têm a mesma categoria não podem ser processados ​​ao mesmo tempo por trabalhadores separados.
• Um trabalhador pode processar um trabalho de cada vez.

Uma fila tradicional não funcionaria nessa situação porque há uma chance de que vários trabalhos da mesma categoria sejam processados ​​simultaneamente, o que não é permitido.

Você pode fazer com que o trabalhador verifique o trabalho que ele agarra e veja se essa categoria de trabalhos tem outro trabalhador que está sendo processado atualmente e, se for o caso, reenvie o trabalho para a fila a ser processada posteriormente. Parece uma maneira ineficiente de resolver esse problema. Existem estruturas de dados ou padrões de design que podem resolver esse problema?

Se você precisar de mais esclarecimentos, entre em contato.

Existem duas partes para esse problema.

Um: a lista desconhecida de categorias possíveis.

Dois: interproceder a comunicação entre os trabalhadores para impedir que dois trabalhos da mesma categoria sejam processados ​​simultaneamente.

Se você tivesse uma lista conhecida de categorias, poderá ter uma fila e um trabalhador por categoria.

Com categorias desconhecidas, você ainda pode ter uma fila por categoria, mas ter um trabalhador de fila por categoria exige que você monitore todas as filas e inicie novos trabalhadores quando uma nova categoria aparecer.

Isso pode ser alcançado com um trabalhador 'mestre' que distribui trabalhos

Todos os trabalhos vão para a fila 'principal'.

O trabalhador da categoria cria uma fila privada e registra com o mestre como disponível para o trabalho.

o trabalhador mestre seleciona trabalhos, verifica a categoria, verifica os trabalhadores disponíveis e atribui o trabalho a um deles, colocando-o em sua fila privada.

O mestre pode acompanhar a categoria atribuída ao trabalhador.

o mestre escolhe o próximo trabalho, é a mesma categoria e o trabalhador ainda está ocupado, colocando os trabalhos em uma fila de espera específica da categoria

master obtém o próximo emprego, é uma nova categoria, por isso o atribui a outro trabalhador da categoria.

O trabalhador da categoria conclui o trabalho e registra novamente o trabalho

o mestre verifica as filas de espera e o próximo trabalho da fila principal e atribui aos trabalhadores da categoria disponíveis.

Se um trabalhador da categoria travar durante um trabalho, ele não será registrado novamente. Portanto, o mestre pode ter alguma lógica de tempo limite em que desistirá e começará a atribuir as categorias a outro trabalhador.

Você também deve ter cuidado para ter apenas um único trabalhador mestre em um determinado momento. Isso nescita um bloqueio exclusivo na fila principal de algum tipo

A desvantagem da sua proposta ineficiente ocorre quando há 2 empregos para uma categoria. Agora um está funcionando ... e todo mundo está fazendo uma espera ocupada.

Você pode fazer isso bom o suficiente, solicitando aos trabalhadores que varram a fila para uma próxima tarefa executável e, em seguida, devolvam tudo, exceto a fila, se encontrarem uma. Alternativamente, devolva tudo e depois durma. Se o sono tiver alguma aleatoriedade e retorno exponencial, a "espera ocupada" não ficará muito ocupada.

Para uma abordagem mais eficiente, um trabalhador que consegue um emprego é responsável por fazer essa categoria até que nada mais seja deixado. Então você volta a ser um trabalhador regular. Mas existem algumas sutilezas.

Para ver aqueles, vamos supor que pudermos trye releasefechaduras (ambos sem bloqueio) e nossas operações de fila são add, gete is_emptycom getsendo uma operação de bloco e espera.

Assumiremos uma fila geral e, para cada categoria, uma fila e um bloqueio.

Aqui está o fluxo básico do trabalhador.

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

Onde

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

Observe o cuidadoso aperto de mão aqui. O trabalhador testa o bloqueio e, se estiver bloqueado, adiciona o trabalho à fila. Mas é necessário testar novamente o bloqueio para verificar se ainda é responsabilidade de outra pessoa fazer o trabalho. Apenas no caso de o trabalhador da categoria terminar enquanto você fazia a manipulação da fila.

(Esse é o tipo de detalhe de bloqueio que as pessoas geralmente estragam. O erro será impossível de reproduzir de maneira confiável, mas estraga aleatoriamente e sem erros na produção ...)