В списке рассылки разработчиков ядра 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).
Ссылки по теме
