Алгоритм отправки заданий в несколько очередей Threadpool

Question

Мне любопытно узнать, существует ли широко распространенное решение для управления ресурсами потоков в пуле потоков с учетом следующего сценария / ограничений:

1. Входящие вакансии одинаковы природа и может быть обработана любым нить в бассейне.
2. Входящие вакансии будут «сгруппированы» в разные очереди, основанные на некотором атрибуте входящая работа такая, что все рабочие места ДОЛЖЕН идти в ту же корзину / очередь обрабатываться серийно.
3. Некоторые ведра будут менее заняты, чем другие в разных точках во время время жизни программы.

Мой вопрос касается теории реализации пула потоков. Какой алгоритм можно использовать для эффективного распределения доступных потоков для входящих заданий во всех сегментах?

Редактировать : Еще одной целью разработки было бы устранить как можно большую задержку между помещением в очередь задания и его получением для обработки, предполагая, что имеются свободные незанятые потоки.

Edit2 : В случае, если я имею в виду, существует относительно большое количество очередей (50-100), которые имеют непредсказуемые уровни активности, но, вероятно, только 25% из них будут активны в в любой момент времени.

Первое (и наиболее дорогостоящее) решение, о котором я могу подумать, - это просто назначить 1 поток каждой очереди. Хотя это обеспечит немедленный прием входящих запросов, это явно неэффективно.

Второе решение состоит в том, чтобы объединить очереди вместе на основе ожидаемых уровней активности, чтобы количество очередей соответствовало количеству потоков в пуле, позволяя назначить один поток каждой очереди. Проблема здесь будет в том, что входящие задания, которые в противном случае могли бы обрабатываться параллельно, будут вынуждены ждать друг друга.

Третье решение - создать максимальное количество очередей, по одной для каждого набора заданий, которые должны обрабатываться последовательно, но распределять потоки только на основе количества очередей, которые мы ожидаем быть занятыми в любой момент времени (что также может быть настроенным бассейном во время выполнения). Так что вот в чем заключается мой вопрос: учитывая, что у нас больше очередей, чем потоков, как пул может распределять свободные потоки для входящих заданий наиболее эффективным способом?

Я хотел бы знать, существует ли широко принятый подход. Или, если есть разные подходы - кто использует какой? Каковы преимущества / недостатки и т. Д.?

Edit3 : Это может быть лучше всего выражено в псевдокоде.

Answer 1

ДОБАВЛЕНО: Теперь я склонен согласиться с тем, что вы можете начать с простого и просто сохранить отдельный поток для каждого сегмента, и только если понимается, что в этом простом решении есть проблемы, вы ищете что-то другое.И лучшее решение может зависеть от того, какие именно проблемы вызывает простой.

В любом случае, я оставляю свой первоначальный ответ ниже с добавлением запоздалой мысли.

---

Вы можете сделатьспециальные глобальные очереди сигналов «задание доступно в сегменте X».

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

Когда входящее задание передается в корзину по порядку, необходимо проверить, назначен ли уже рабочий поток этой корзине.Если назначено, новое задание будет в конечном итоге обработано этим рабочим потоком, поэтому сигнал отправлять не нужно.Если не назначен рабочий, проверьте, пусто ли ведро или нет.Если пусто, поместите в глобальную очередь сигналов сигнал о том, что в этот сегмент поступило новое задание;если не пустой, такой сигнал должен был быть сделан уже, и рабочий поток должен скоро прибыть, поэтому ничего не делайте.

ДОБАВЛЕНО: У меня возникла мысль, что моя идея выше может вызвать голод для некоторых заданий, если числопотоков меньше, чем количество «активных» сегментов и при этом происходит бесконечный поток входящих задач.Если все потоки уже заняты, и новое задание поступает в сегмент, который еще не обработан, может пройти много времени, прежде чем поток освободится для работы над этим новым заданием.Таким образом, необходимо проверить, есть ли работающие без дела, и если нет, создать нового ... который добавляет больше сложности.

Answer 2

Вам, вероятно, следует исключить номер2 из вашей спецификации.Все, что вам действительно нужно соблюдать, - это то, что потоки занимают сегменты и обрабатывают очереди внутри блоков по порядку.Нет смысла обрабатывать сериализованную очередь с другим пулом потоков или выполнять некоторую сериализацию задач параллельно.Таким образом, ваша спецификация просто сводится к тому, что потоки перебирают fifo в контейнерах, и это до пула менеджера, чтобы вставить правильно построенные сегменты.Таким образом, ваша корзина будет:

struct task_bucket
{
    void *ctx; // context relevant data
    fifo_t *queue; // your fifo
};

Тогда вы должны сделать пул потоков достаточно умным, чтобы знать, что делать на каждой итерации очереди.Например, ctx может быть указателем на функцию, а очередь может содержать данные для этой функции, поэтому рабочий поток просто вызывает функцию на каждой итерации с предоставленными данными.

Отражение комментариев: Если размерСписок сегментов известен заранее и вряд ли изменится за время существования программы, вам необходимо выяснить, важно ли это для вас.Вам понадобится какой-нибудь способ, чтобы потоки могли выбрать корзину, которую нужно взять.Самый простой способ - иметь очередь FIFO, которая заполнена менеджером и очищена потоками.Классический читатель / писатель.

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

Обе эти стратегии предполагают, что рабочие отбрасывают корзины, а менеджер создает новые.

Если важно хранить сегменты, вы рискуете, когда работники будут следить только за последним измененным заданием, поэтому менеджеру потребуется либо переупорядочить список сегментов, либо изменить приоритеты каждого сегмента, и работник выполнит итерацию в поисках самого высокого приоритета.,Важно, чтобы память ctx оставалась актуальной во время работы потоков, иначе потоки также должны будут это скопировать.Рабочие могут просто назначить очередь локально и установить для нее значение NULL в корзине.

Answer 3

Сохраняйте это простым: Я бы использовал 1 поток на очередь. Простота многого стоит, а темы довольно дешевые. 100 потоков не будут проблемой в большинстве ОС.

Используя поток для каждой очереди, вы также получаете настоящий планировщик. Если поток блокируется (зависит от того, что вы делаете), другой поток может быть поставлен в очередь. Вы не получите тупик, пока каждый не блокируется. То же самое нельзя сказать, если вы используете меньше потоков - если очереди, которые потоки оказываются обслуживающими, блокируются, то даже если другие очереди «работают», и даже если эти другие очереди могут разблокировать заблокированные потоки, вы будет тупик.

Теперь, в определенных сценариях, использование пула потоков может стоить того. Но тогда вы говорите об оптимизации конкретной системы, и детали имеют значение. Насколько дороги темы? Насколько хорош планировщик? Как насчет блокировки? Как долго очереди, как часто обновляются и т. Д.

Итак, в общем, имея только информацию о том, что у вас есть около 100 очередей, я бы просто выбрал поток для каждой очереди. Да, есть некоторые накладные расходы: все решения будут иметь это. Пул потоков будет представлять проблемы синхронизации и накладные расходы. И накладные расходы ограниченного числа потоков довольно незначительны. Вы в основном говорите о 100 МБ адресного пространства - не обязательно памяти. Если вы знаете, что большинство очередей будут простаивать, вы могли бы дополнительно реализовать оптимизацию, чтобы остановить потоки в пустых очередях и запускать их при необходимости (но остерегайтесь условий гонки и перебоя).