LINUX.ORG.RU
Форум — Talks  

Для Linux представлен планировщик задач BLD (Barbershop Load Distribution)


0

1


Собственно, репост с опеннета:

http://www.opennet.ru/opennews/art.shtml?num=33070

В списке рассылки разработчиков ядра Linux представлена реализация альтернативного алгоритма планирования задач - BLD (Barbershop Load Distribution). В отличие от используемого в настоящее время планировщика, BLD ограничивается решением задачи по корректному распределению нагрузки путем отслеживания не всех привязанных к CPU очередей, а только наиболее и наименее загруженных очередей выполнения (rq, runqueue). BLD не пытается балансировать нагрузку на систему в контексте отслеживания бездействующих idle-процессов, а акцентирует внимание на распределении всей нагрузки между имеющимися процессорами наиболее простым путём с минимальным числом усложнений.

Для пояснения сути нового алгоритма приведена аналогия с парикмахерской в которой менеджер (планировщик задач) выстраивает клиентов (процессы) в несколько очередей (runqueue) к парикмахерам (CPU), с учётом загруженности парикмахеров организуя очередь так, чтобы клиенту пришлось ждать как можно меньше времени. При использовании алгоритма BLD при приходе нового «клиента» (процесса) планировщик выбирает наименее загруженную очередь и помещает в неё процесс. При этом на BLD ложится задача по вычислению нагрузки в каждой очереди и перегруппировки очередей в соответствии с вычисленной нагрузкой. Соответственно процесс для выполнения снимается с верхушки наиболее загруженной очереди, а вновь прибывающие заявки помещаются в конец наименее нагруженной очереди. Так как перераспределение списка очередей происходит постоянно, удаётся добиться равномерного распределения ресурсов между ожидающими выполнения задачами, без использования методов балансировки нагрузки и без оглядки на число CPU.

Классический планировщик задач ядра Linux при поступлении нового процесса пытается выявить наименее загруженный CPU, постоянно пересчитывая параметры каждой очереди. Одновременно, с целью обеспечения оптимальной балансировки, те же операции проделываются при принятии решения о том какой процесс следует начать выполнять внутри очереди. Если очередь к CPU пуста (iddle), планировщик пытается переместить в неё элементы из наиболее загруженной очереди другого CPU, выступая в роли балансировщика нагрузки.

В настоящее время для тестирования подготовлен базовый прототип BLD, который ещё нуждается в доработке, чистке и оптимизации. Тем не менее BLD уже показывает хорошую производительность для таких типов нагрузки, как сборка ядра из исходных текстов. Из проблемных областей называется недостаточная справедливость при выполнении такой активности, как порождение одним процессом произвольного числа нитей. По мнению автора разработки, проводить сравнения производительности пока рано, прототип пока нацелен на обкатку базовых принципов. Главным достоинством BLD является сам подход, показывающий что достаточно простыми методами можно добиться равномерного распределения нагрузки, не заботясь особенно о том сколько CPU используется в системе и соответственно без лавинообразного падения производительности на накладные расходы в при увеличении числа CPU (BLD обеспечивает уровень производительности O(n), где n - число CPU).

Источник

Кто-то в курсе уже? Объясните, это очередной велосипед типа BFS? :)

★★★★★

без лавинообразного падения производительности на накладные расходы в при увеличении числа CPU

Лавинообразное падение - это начиная с какого ж числа CPU? С 1000, небось?

Sadler ★★★
()

А нескучные обои есть в комплекте?

firestarter ★★★☆
()
Ответ на: комментарий от anonymous_sapiens

+1

Явно не помешало бы как-то... Ладно, тогда ждем :)

Gonzo ★★★★★
() автор топика

BLD уже показывает хорошую производительность для таких типов нагрузки, как сборка ядра из исходных текстов

Распаковка и компиляция ядра - самые важные бенчмарки ляликса.

tailgunner ★★★★★
()

Rakib Mullick

Майкрософт там ------>

AlexVIP ★
()

Это всё замечательно, но где тесты? Куда смотрит Пхороникс?

kranky ★★★★★
()

Объясните, это очередной велосипед типа BFS? :)

Учитывая, что без BFS линукс на десктопе мало юзабелен, ты сел в лужу.

geekless ★★
()
Ответ на: комментарий от geekless

Использую линукс на десктопе без BFS. В чем эта «мало юзабельность» проявляется?

bhfq ★★★★★
()
Ответ на: комментарий от geekless

без BFS линукс на десктопе мало юзабелен, ты сел в лужу.

Учитывая, что я на десктопе не использую BFS, ты сел в лужу.

Bad_ptr ★★★★★
()
Ответ на: комментарий от firestarter

А ты сможешь в слепом тесте отличить bfs от cfs?

А ты сможешь пропрыгать на голове 20 метров? На моём железе разница весьма и весьма ощутима. Что там на твоём, меня мало волнует. На «слабо» привычки вестись не имею.

geekless ★★
()
Ответ на: комментарий от geekless

без BFS линукс на десктопе мало юзабелен

На моём железе

Проследуйте к ближайшей луже, уважаемый.

kranky ★★★★★
()
Ответ на: комментарий от geekless

12309 такой же миф как и «более отзывчивая система с BFS». Я не использую эти велосипеды, и у меня все ок. А вот как раз, когда я пробовал этот планировщик на двух машинах то на одной стал затыкаться звук и временами даже вешалась система. Для меня это показатель. Зачем этот никому не нужный холивар?

Gonzo ★★★★★
() автор топика
Ответ на: комментарий от Gonzo

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

Я тебе точно так же могу историй успеха рассказать в обратную сторону. А суть же на самом деле не в них, а в том, что BFS и CFS используют разные подходы к планированию. И алгоритм CFS на десктопе неоптимален вообще никак.

Зачем этот никому не нужный холивар?

Откуда я знаю, его же ты начал.

geekless ★★
()
Ответ на: комментарий от Gonzo

12309 такой же миф как и «более отзывчивая система с BFS»

Под 12039 сейчас подразумевают любые тормоза интерфейса (читай, нефоновых процессов), связанные с вводом/выводом. Я вкусил этого добра в полной мере, и если у тебя его не было, то это значит только то, что у тебя его не было.

gaga ★
()
Ответ на: комментарий от gaga

Я об этом и говорю. У кого-то на железе это проявляется, у кого-то нет. geekless чсв-шник просто, и тут я уже ничем не могу помочь. Речь ведь не об этом, я не собирался тут вбросы устраивать :)

Gonzo ★★★★★
() автор топика
Ответ на: комментарий от Gonzo

12309 такой же миф как и «более отзывчивая система с BFS»

Ты волен думать так как угодно тебе и так чтобы не ломалась твоя личная картинка мира, но с BFS отзывчивость десктопа действительно возрастает. Если ко всему этому добавить еще возможность использовать AHCI посредством Noop планировщика, то вообще можно забыть о пресловутом 12309 и совсем небезосновательно заять венду что она иногда серьезно подвисает при копировании большого количества данных.

// Я немного пьян, но думаю изложил нормально.

partyzan ★★★
()
Ответ на: комментарий от partyzan

:)

Ок, пусть будет по-твоему, если ты тоже думаешь, что я решил тут потроллить.

Тему можно закрывать. К тому же, как сказано в тексте «проводить сравнения производительности пока рано, прототип пока нацелен на обкатку базовых принципов.»

Gonzo ★★★★★
() автор топика
Ответ на: комментарий от post-factum

Ясно, спасибо, Саня :) pf-kernel таки юзаю на одной машинке рабочей, признаюсь. На ней всё это тряхомудие с BFS, BFQ и т.д. таки дает бОльшую отзывчивость. Просто тут тролли набежали и как давай меня считать холиварщиком, ну а с такими бесполезно о чем-либо разговаривать.

Gonzo ★★★★★
() автор топика
Ответ на: комментарий от post-factum

И да, если получится, она будет в pf-kernel для 3.3.

Это хорошо. Концепция звучит разумно, я бы попробовал.

Axon ★★★★★
()
Ответ на: комментарий от Nanodesu

Тссс... Ты что, тут сидит geekless, и он тебя сейчас заклюёт! Ты просто ОБЯЗАНА здесь ощутить всю мощь BFS ! Хочешь ты того или нет :)

Gonzo ★★★★★
() автор топика
Ответ на: комментарий от Gonzo

Надо, мне кажется, сразу с конфигом своего железа впечатления выкладывать. И типичными задачами. А 12309.. выяснила недавно, что в рейде один из хардов сбойный был, когда уже рейд разобрала и смарт-лог посмотрела. Всякое бывает.

Nanodesu ★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
Talks