Как выбрать задачи из списка на основе некоторых связанных метаданных?

Question

У меня есть n задач в списке ожидания. С каждой задачей связана запись, содержащая метаинформацию:

Task1 A,B<br> Task2 A<br> Task3 B,C<br> Task4 A,B,C

И связанная хэш-карта, которая содержит записи типа:

A    1
B    2
C    2

Это означает, что если задача, содержащая в своей метаинформации A, уже запущена, то никакая другая задача, содержащая А может работать одновременно. Тем не менее, поскольку B имеет ограничение в 2 задачи, то либо task1 и task3 могут выполняться вместе, либо task3 и task4. Но задача 1, задача 3 и задача 4 не могут работать вместе, так как будут нарушены пределы A и B, хотя предел C не нарушены.

Если мне нужно выбрать задачи для запуска в разных потоках, какую логику / алгоритм вы бы предложили? И когда эта логика должна быть вызван? Я рассматриваю список задач как общий ресурс, который может быть заблокирован при выполнении задач выбраны для запуска из него. Прямо сейчас, я думаю, что эта логика может быть вызвана, когда задача добавлена ​​в список и также, когда выполняемое задание завершено. Но это может заблокировать добавление новых элементов в список, если я не сделаю копию списка перед запуском логики.

Как изменилась бы ваша логика, если бы я придал более высокий приоритет задачам, которые содержат больше записей, таких как 'A, B, C' чем это к 'A, B'?

Это своего рода продолжение Выбор структуры данных для варианта проблемы потребителя производителя и Как получить доступ к базовой очереди ThreadpoolExecutor потокобезопасным способом , просто на случай, если кто-нибудь задумывается о причинах проблемы.

Answer 1

Да, это противно. Я сразу подумал о массиве / списке семафоров, инициализированных из хеш-карты, из которой любой поток, пытающийся выполнить задачу, должен был бы получить единицы, как определено метаданными. Примерно через секунду я понял, что такой дизайн зашёл бы в тупик довольно быстро!

Я думаю, что одному выделенному производительному потоку придется итерировать список 'readyJobs' в попытке найти задачу, которая может быть выполнена с доступными текущими ресурсами. Это может быть сделано как при появлении новых задач, так и после того, как задача завершена, поэтому освобождайте ресурсы. Поток производителя может ожидать в одной входной очереди (поточно-ориентированная очередь производителя-потребителя), в которую помещаются как новые задачи из [где угодно], так и завершенные задачи, которые находятся в очереди из рабочих потоков (обратный вызов, запущенный рабочими потоками отправляет завершенную задачу в очередь ввода?). Добавление новых задач может быть на короткое время заблокировано, но только тогда, когда входная очередь заблокирована добавлением какой-либо другой задачи.

В случае назначения «приоритетов», вы можете вставить-отсортировать список «ReadyJobs» по своему желанию, чтобы сначала были проверены задачи с более высоким приоритетом, чтобы увидеть, могут ли они выполняться с доступными ресурсами. Если они не могут, то остальная часть списка повторяется, и может выполняться задание с более низким приоритетом.

Я надеюсь, что вы не хотите «выгружать» задачи с более низким приоритетом, чтобы высвобождать ресурсы раньше - это будет очень, очень грязно: (

Rgds, Martin