Найти минимальный размер очереди среди потоков
Я пытаюсь реализовать новую технику планирования с помощью многопоточности. Каждый поток имеет свою собственную локальную очередь. Идея состоит в том, что каждый раз, когда задача создается из потока программы, она должна искать минимальные размеры очереди (очередь с меньшим количеством задач) среди очередей и ставить в нее очередь.
Способ распределения нагрузки между потоками, где менее занятые очереди ставятся в очередь больше.
Можете ли вы предложить некоторые логические (или) идеи, как динамически находить очереди минимального размера среди заданных очередей с точки зрения программирования.
Я работаю над Visual Studio 2008, языком программирования C ++ в нашей собственной многопоточной библиотеке, реализующей парадигму многоуровневого синхронного потока данных.
Решение
Если вы действительно хотите попробовать это, может ли каждая очередь не просто содержать общедоступный элемент ‘int count’, обновленный с помощью atomic inc / dec, когда задачи выдвигаются / выталкиваются?
Стоит ли такая конструкция затрат на управление и случайные «ошибки», когда задача ставится в очередь в потоке, который выполняет особенно длинное задание, когда другой поток собирается снять с очереди очень короткую работу, — это другая проблема.
Другие решения
Как вы видите, попытка найти менее загруженную очередь громоздка и может оказаться неэффективным методом, поскольку вы можете добавить больше работы в очереди только с одной тяжелой задачей, тогда как очереди с небольшими задачами не будут иметь больше заданий и станут быстро неактивными.
Вы бы лучше использовать работа краже эвристический: когда поток выполняет свои собственные задания, он просматривает очереди других потоков и «крадет» некоторую работу вместо того, чтобы оставаться в бездействии или прерываться.
Тогда система будет автоматически уравновешена с каждым активным потоком, пока не будет недостаточно работы для всех.
У вас не должно быть ситуации с незанятыми потоками и работой, ожидающей обработки.
Почему потоки не извлекают свою работу из «основной» рабочей очереди?
Если вы действительно пытаетесь распределить рабочие элементы из основного источника среди набора рабочих, то, как вы говорите, вы выполняете балансировку нагрузки. В этом случае вы на самом деле говорите о планировании, если только вы не выполняете балансировку в стиле циклического перебора. Планирование является очень глубоким предметом в вычислительной технике, вы можете легко потратить недели или месяцы на изучение этого.
Вы можете синхронизировать счетчик между потоками. Но я думаю, это не то, что вы хотите.
Поскольку вы хотите реализовать все с использованием потока данных, все должно быть очередями.
Первый вариант — запросить количество заданий в очереди. Я думаю, что это нелегко, если вам нужен один шаблон чтения / записи, потому что вам, вероятно, придется использовать блокировку для этой операции, а это не то, что вам нужно. Примечание: я просто предполагаю, что здесь нельзя использовать очереди без блокировки; либо у вас есть счетчик, либо вы используете разницу в два указателя, либо у вас есть замок.
Второй вариант (который можно сделать с помощью кода без блокировок) — отправить команду обратно в поток диспетчера, сообщив ему, что рабочий поток x выполнил задание. При таком подходе у вас есть n очередей, каждая из которых от одного рабочего потока до потока диспетчера.