Для Linux представлен планировщик задач BLD (Barbershop Load Distribution)
13 февраля 2012 года
В списке рассылки разработчиков ядра Linux представлена реализация альтернативного алгоритма планирования задач - BLD (Barbershop Load Distribution). В отличие от используемого в настоящее время планировщика, BLD ограничивается решением задачи по корректному распределению нагрузки путем отслеживания не всех привязанных к CPU очередей, а только наиболее и наименее загруженных очередей выполнения (rq, runqueue). BLD не пытается балансировать нагрузку на систему в контексте отслеживания бездействующих idle-процессов, а акцентирует внимание на распределении всей нагрузки между имеющимися процессорами наиболее простым путём с минимальным числом усложнений.
Для пояснения сути нового алгоритма приведена аналогия с парикмахерской в которой менеджер (планировщик задач) выстраивает клиентов (процессы) в несколько очередей (runqueue) к парикмахерам (CPU), с учётом загруженности парикмахеров организуя очередь так, чтобы клиенту пришлось ждать как можно меньше времени. При использовании алгоритма BLD при приходе нового "клиента" (процесса) планировщик выбирает наименее загруженную очередь и помещает в неё процесс. При этом на BLD ложится задача по вычислению нагрузки в каждой очереди и перегруппировки очередей в соответствии с вычисленной нагрузкой. Соответственно процесс для выполнения снимается с верхушки наиболее загруженной очереди, а вновь прибывающие заявки помещаются в конец наименее нагруженной очереди. Так как перераспределение списка очередей происходит постоянно, удаётся добиться равномерного распределения ресурсов между ожидающими выполнения задачами, без использования методов балансировки нагрузки и без оглядки на число CPU.
Классический планировщик задач ядра Linux при поступлении нового процесса пытается выявить наименее загруженный CPU, постоянно пересчитывая параметры каждой очереди. Одновременно, с целью обеспечения оптимальной балансировки, те же операции проделываются при принятии решения о том какой процесс следует начать выполнять внутри очереди. Если очередь к CPU пуста (idle), планировщик пытается переместить в неё элементы из наиболее загруженной очереди другого CPU, выступая в роли балансировщика нагрузки.
В настоящее время для тестирования подготовлен базовый прототип BLD, который ещё нуждается в доработке, чистке и оптимизации. Тем не менее BLD уже показывает хорошую производительность для таких типов нагрузки, как сборка ядра из исходных текстов. Из проблемных областей называется недостаточная справедливость при выполнении такой активности, как порождение одним процессом произвольного числа нитей. По мнению автора разработки, проводить сравнения производительности пока рано, прототип пока нацелен на обкатку базовых принципов. Главным достоинством BLD является сам подход, показывающий что достаточно простыми методами можно добиться равномерного распределения нагрузки, не заботясь особенно о том сколько CPU используется в системе и соответственно без лавинообразного падения производительности на накладные расходы при увеличении числа CPU (BLD обеспечивает уровень производительности O(n), где n - число CPU).
Источники
правитьЛюбой участник может оформить статью: добавить иллюстрации, викифицировать, заполнить шаблоны и добавить категории.
Любой редактор может снять этот шаблон после оформления и проверки.
Комментарии
Если вы хотите сообщить о проблеме в статье (например, фактическая ошибка и т. д.), пожалуйста, используйте обычную страницу обсуждения.
Комментарии на этой странице могут не соответствовать политике нейтральной точки зрения, однако, пожалуйста, придерживайтесь темы и попытайтесь избежать брани, оскорбительных или подстрекательных комментариев. Попробуйте написать такие комментарии, которые заставят задуматься, будут проницательными или спорными. Цивилизованная дискуссия и вежливый спор делают страницу комментариев дружелюбным местом. Пожалуйста, подумайте об этом.
Несколько советов по оформлению реплик:
- Новые темы начинайте, пожалуйста, снизу.
- Используйте символ звёздочки «*» в начале строки для начала новой темы. Далее пишите свой текст.
- Для ответа в начале строки укажите на одну звёздочку больше, чем в предыдущей реплике.
- Пожалуйста, подписывайте все свои сообщения, используя четыре тильды (~~~~). При предварительном просмотре и сохранении они будут автоматически заменены на ваше имя и дату.
Обращаем ваше внимание, что комментарии не предназначены для размещения ссылок на внешние ресурсы не по теме статьи, которые могут быть удалены или скрыты любым участником. Тем не менее, на странице комментариев вы можете сообщить о статьях в СМИ, которые ссылаются на эту заметку, а также о её обсуждении на сторонних ресурсах.