LINUX.ORG.RU

Con Kolivas вернулся: встречайте BFS

 , , ,


0

0

Con Kolivas вернулся с новым планировщиком задач для Линукс ядра BFS (Brain Fuck Scheduler). Цитата:

Почему я написал его?

После многих лет использования моего старого ядра [Линукса] и многочисленных обновлений железа, в конце концов у меня появилось оборудование, которое требовало новых драйверов ядра, а также мне хотелось попробовать новые файловые системы. Загрузка в стандартное ядро [основная ветка на kernel.org] была достаточно обнадёживающей в том, что поведение планировщика стало гораздо лучше, чем в старых ядрах. Однако, много времени не потребовалось, чтобы я разочаровался и в этом [планировщике]. Случайные зависания при движении курсора мыши и нажатиях клавиш, странное распределение процессорного времени при разных вариантах нагрузки на систему и непредсказуемое поведение - это всё то, что, я надеялся, уже исправили. Поэтому я сделал то, чего поклялся никогда не делать - изучил код [планировщика CFS в ядре]. Увидев, что он превратился в монстра невероятных размеров, я сел и поразмыслил, что же в нём не так.

Одна из основных особенностей "справедливости" и интерактивности, за которую я всегда ратовал — это простая семантика того, как должно распределяться процессорное время; с гарантированными низкими задержками так, чтобы интерактивность была гарантирована архитектурой системы, а не так, чтобы она была привинчена с краю [bolted on]. По сути CFS так и делает, но у CFS есть кое-что ещё. CFS варьирует отрезки времени с тем, чтобы попытаться сохранить список завершения задач и определяет распределение процессорного времени, основываясь на отношении работы, поделённой на отдых. CFS также спроектирован, чтобы работать на супер-компьютерах - то, что обычный человек никогда даже не увидит.

Все эти подсчёты времени сна - это то, что, как я обнаружил, ответственно за различное поведение системы при различных нагрузках на неё - то, что вызывает относительное "голодание" и нечестность распределения процессорного времени. Хотя, надо отдать должное, в CFS это не сильно выражено, и это замечательно. Но, тем не менее, поведение системы при работе CFS - это не то ощущение, которое я бы хотел получить при работе планировщика. Правильный планировщик должен "думать" только о будущем (не подсчитывая время сна), а CFS, увы, не загружает полностью достаточно ненагруженную систему с небольшим количеством процессоров.

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

Что же это такое?

BFS - это аббревиатура от Brain Fuck Scheduler (позволю себе оставить без перевода). Он был разработан по принципу "гляжу только вперёд" и позволяет выжать максимум из достаточно слабых компьютеров, при этом он не ориентирован на суперкомпьютеры. BFS ориентирован на десктоп, имеет при этом по дизайну сверхнизкие задержки для великолепной интерактивности, вместо того, чтобы заниматься подсчётами, при этом BFS имеет настоящую "честность" (распределения процессорного времени), хорошее распределение уровней NICE и отличную масштабируемость при обычных нагрузках.

Отличная масштабируемость при обычных нагрузках? Разве тут нет противоречия?

Многие годы мы нагружали свои Linux системы так, чтобы работы было больше, чем у нас есть процессоров, потому что все мы считали, что jobservers ограничены в своих способностях по полному использованию процессоров (поэтому на 4х процессорном компьютере мы запускали компиляцию в шесть потоков). Мой планировщик доказал, что jobserver ни в чём не виноват, потому что на компьютере с 4 процессорами четыре потока при использовании BFS завершают работу быстрее, чем *любое* количество jobserver'ов при использовании CFS. Предлагаю вам посмотреть на графики обратной масштабируемости Сергея Беляшева, показывающие нагрузку на систему при разном количестве "задач" (jobs) на 4х ядерном компьютере. Планировщик задач в основном ядре никогда не может нагрузить машину полностью - он не может выжать максимум из вашей настольной системы ни при каких обстоятельствах. Отмечу, что этот график достаточно стар - масштабируемость с тех пор улучшилась.

Далее Кон объясняет выбор его имени (потому что, скорее всего, этот планировщик никогда не появится в основном ядре, и BFS не ориентирован на супер-компьютеры, например, на NUMA машины) и даёт рекомендации по его использованию (просто наложите патч на ядро).

>>> BFS Faq

★★★★★

Проверено: boombick ()

Ответ на: Re: Con Kolivas вернулся: встречайте BFS от tempuser001

Re: Con Kolivas вернулся: встречайте BFS

> И он, увы, прав.

Он просто не видит другой стороны палки: серьёзный рынок серверов и суперкомпьютеров у Linux уже есть, а серьёзного рынка в стороне десктопов ещё нет. Компании (и многие "одиночки" кстати тоже), которые вовлечены в разработку и продвижение linux, просто боятся потерять превосходство на серверах и суперкомпьютерах в погоне за десктопами. Потому что если это произойдёт, то Linux моментально склеит ласты да ещё и утащит за собой идею "opensource в бизнесе".

Deleted ()

Re: Con Kolivas вернулся: встречайте BFS

ждём в Ubuntu Desktop по умолчанию?

sniper21 ★★★★★ ()

Re: Con Kolivas вернулся: встречайте BFS

Наконец-то кто-то кончил жевать сопли, сел и сделал!

Arceny ★★ ()

Re: Con Kolivas вернулся: встречайте BFS

вот и будут у линукса несколько планировщиков - для десктопов , для супер-компьютеров , для домохозяек , кто там еще ?

kto_tama ★★★★★ ()

Re: Con Kolivas вернулся: встречайте BFS

То есть он [Con Colivas], считает что планировщик [BFS] уже стабилен и его [планировщик] можно использовать на боевом десктопе [Линукс]?

UserUnknown ★★★★★ ()

Re: Con Kolivas вернулся: встречайте BFS

перевод конечно не в умате, но итак попрет

z0D5e8n7x_2 ()
Ответ на: Re: Con Kolivas вернулся: встречайте BFS от UserUnknown

Re: Con Kolivas вернулся: встречайте BFS

> То есть он [Con Colivas], считает что планировщик [BFS] уже стабилен и его [планировщик] можно использовать на боевом десктопе [Линукс]?

Is this stable?

Probably not. I use it on half a dozen machines but the code only booted for
the first time successfully on the 25th August 2009 so you work out how new
it is.

Deleted ()

Re: Con Kolivas вернулся: встречайте BFS

Ждем в Ubuntu Desktop.

PS. Карикатура шикарная!

adarovsky ★★★★ ()
Ответ на: Re: Con Kolivas вернулся: встречайте BFS от UserUnknown

Re: Con Kolivas вернулся: встречайте BFS

Читай фак по ссылке. Планировщик еще не стабилен, но уже работает. Первая успешная загрузка случилась 25го августа.

Reset ★★★★★ ()

Re: Con Kolivas вернулся: встречайте BFS

> Случайные зависания я движении курсора мыши и нажатий клавиш,

Язык рускэ?

sersto ()

Re: Con Kolivas вернулся: встречайте BFS

> BFS не ориентирован на супер-компьютеры, например, на NUMA машины

NUMA -- это любая многосокетная система, имеющая процессоры с интегрированным контроллером памяти. То есть все многосокетные системы от AMD и новые от Intel (те что на Nehalem). Какие нафиг суперкомпьютеры?

Relan ★★★★★ ()
Ответ на: Re: Con Kolivas вернулся: встречайте BFS от Deleted

Re: Con Kolivas вернулся: встречайте BFS

> Он просто не видит другой стороны палки: серьёзный рынок серверов и суперкомпьютеров у Linux уже есть, а серьёзного рынка в стороне десктопов ещё нет. Компании (и многие "одиночки" кстати тоже), которые вовлечены в разработку и продвижение linux, просто боятся потерять превосходство на серверах и суперкомпьютерах в погоне за десктопами. Потому что если это произойдёт, то Linux моментально склеит ласты да ещё и утащит за собой идею "opensource в бизнесе".

Дать выбор планировщика в зависимости от назначения компа.

sersto ()
Ответ на: Re: Con Kolivas вернулся: встречайте BFS от Reset

Re: Con Kolivas вернулся: встречайте BFS

>> Что мешает сделать несколько планировщиков ?

ничто не мешает
планировщиков и должно быть много

kto_tama ★★★★★ ()
Ответ на: Re: Con Kolivas вернулся: встречайте BFS от Reset

Re: Con Kolivas вернулся: встречайте BFS

> Что мешает сделать несколько планировщиков ?

Ничего не мешает. В ядре ЕМНИП даже есть фреймворк для планировщиков, чтобы их можно было несколько держать. Старый планировщик Коливаса не включили в ядро, так как не были уверены в том, что он - надёжный мейнтейнер (всё-таки планировщик - это не какой-то там драйвер для USB-хренульки, на который можно и забить). Он сам же и подтвердил это недоверие, тут же эпично хлопнув дверью =).

Deleted ()
Ответ на: Re: Con Kolivas вернулся: встречайте BFS от Reset

Re: Con Kolivas вернулся: встречайте BFS

> Что мешает сделать несколько планировщиков ?

Переключаться между ними в run time нельзя -- только пересобирать ядро.

Relan ★★★★★ ()
Ответ на: Re: Con Kolivas вернулся: встречайте BFS от Relan

Re: Con Kolivas вернулся: встречайте BFS

>Переключаться между ними в run time нельзя -- только пересобирать ядро.

У вас часто в рантайме меняется архитектура?

UserUnknown ★★★★★ ()
Ответ на: Re: Con Kolivas вернулся: встречайте BFS от Relan

Re: Con Kolivas вернулся: встречайте BFS

>То есть все многосокетные системы от AMD и новые от Intel (те что на Nehalem). Какие нафиг суперкомпьютеры?

Они перестали быть SMP?

Evil_And ★★ ()
Ответ на: Re: Con Kolivas вернулся: встречайте BFS от Deleted

Re: Con Kolivas вернулся: встречайте BFS

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

Собирайте для серверов и суперкомпьютеров ядро с другим планировщиком, чем для десктопов. Ваш КО.

TyhDyh ()
Ответ на: Re: Con Kolivas вернулся: встречайте BFS от Relan

Re: Con Kolivas вернулся: встречайте BFS

И чё? И так многие сборщики дистрибутивов делают несколько вариантов ядер в зависимости от машины desktop/laptop/server ... Почему бы в этих разных типах ядер не использовать разные планировщики?

Reset ★★★★★ ()
Ответ на: Re: Con Kolivas вернулся: встречайте BFS от TyhDyh

Re: Con Kolivas вернулся: встречайте BFS

> Собирайте для серверов и суперкомпьютеров ядро с другим планировщиком, чем для десктопов. Ваш КО.

Microsoft Windows Mobile Edition
Microsoft Windows Embedded Edition
Microsoft Windows Home Edition
Microsoft Windows Workstation Edition
Microsoft Windows Server Edition
Microsoft Windows Cluster Edition

Deleted ()

Re: Con Kolivas вернулся: встречайте BFS

Как ни печально, но таки да, проблема с декстопом всё ещё актуальна. Попробую вечерком погонять...

Ximen ★★★★ ()
Ответ на: Re: Con Kolivas вернулся: встречайте BFS от Reset

Re: Con Kolivas вернулся: встречайте BFS

> И чё? И так многие сборщики дистрибутивов делают несколько вариантов ядер в зависимости от машины desktop/laptop/server ... Почему бы в этих разных типах ядер не использовать разные планировщики?

Да пожалуйста, никто не мешает! Нужно только соблюсти два пункта:
1) Написать подходящий планировщик
2) Поддерживать его в дальнейшем
К сожалению у Коливаса получается только п.1.

Deleted ()

Re: Con Kolivas вернулся: встречайте BFS

Ура! Анестезиолог вернулся!

mv ★★★★★ ()
Ответ на: Re: Con Kolivas вернулся: встречайте BFS от Relan

Re: Con Kolivas вернулся: встречайте BFS

А зачем переключаться? Для однопроцессорной системы один планировщик, для многопроцессорной другой. Собрал ядро и радуешься)

Ardling ()

Re: Con Kolivas вернулся: встречайте BFS

Чем BFQ не устраивает?!

Boy_from_Jungle ★★★★ ()
Ответ на: Re: Con Kolivas вернулся: встречайте BFS от kto_tama

Re: Con Kolivas вернулся: встречайте BFS

>вот и будут у линукса несколько планировщиков - для десктопов , для супер-компьютеров , для домохозяек , kto_tama еще ?

и это же прекрасно, товарищи! сегодня же опробую. ждем включения в gentoo-sources.

ps. по ссылке LOR-эффект, посему вопрос - оно на >=2.6.31.rc5 накатывается?

k0l0b0k ★★ ()
Ответ на: Re: Con Kolivas вернулся: встречайте BFS от UserUnknown

Re: Con Kolivas вернулся: встречайте BFS

> То есть он [Con Colivas], считает что планировщик [BFS] уже стабилен и его [планировщик] можно использовать на боевом десктопе [Линукс]?

CK - ровный пацан, сделавший вагон добра для Линукса на десктопе. Кому, как не ему доверять?

mv ★★★★★ ()
Ответ на: Re: Con Kolivas вернулся: встречайте BFS от Deleted

Re: Con Kolivas вернулся: встречайте BFS

как вариант пусть сделает подробнейшее описание алгоритма и кода и отдаст планировщик в хорошие руки

Reset ★★★★★ ()
Ответ на: Re: Con Kolivas вернулся: встречайте BFS от sniper21

Re: Con Kolivas вернулся: встречайте BFS

> это плохо?

Это не смертельно, но всё-таки не очень хорошо. Линукс сейчас двигается в сторону универсальности. Ради интереса можешь посмотреть например rt-патчи: http://www.kernel.org/pub/linux/kernel/projects/rt/older/ (hint: смотреть на объём; hint2: он уменьшается).

Deleted ()
Ответ на: Re: Con Kolivas вернулся: встречайте BFS от Ximen

Re: Con Kolivas вернулся: встречайте BFS

>> Как ни печально, но таки да, проблема с декстопом всё ещё актуальна. Попробую вечерком погонять...

а то

kto_tama ★★★★★ ()
Ответ на: Re: Con Kolivas вернулся: встречайте BFS от Reset

Re: Con Kolivas вернулся: встречайте BFS

> как вариант пусть сделает подробнейшее описание алгоритма и кода и отдаст планировщик в хорошие руки

Вариант. Но опять же: в прошлый раз никто не подобрал =).

Deleted ()

Re: Con Kolivas вернулся: встречайте BFS

бггг - по сцылке LOR-эффект

ent4jes ()
Ответ на: Re: Con Kolivas вернулся: встречайте BFS от UserUnknown

Re: Con Kolivas вернулся: встречайте BFS

>>Переключаться между ними в run time нельзя -- только пересобирать ядро.

> У вас часто в рантайме меняется архитектура?

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

Relan ★★★★★ ()
Ответ на: Re: Con Kolivas вернулся: встречайте BFS от Deleted

Re: Con Kolivas вернулся: встречайте BFS

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

TyhDyh ()
Ответ на: Re: Con Kolivas вернулся: встречайте BFS от TyhDyh

Re: Con Kolivas вернулся: встречайте BFS

> Для тебя наверное будет шоком, но разные дистрибутивы собирают ядра с разными патчами. Не все используют ванила. И это только десктоп. Не говоря уж о различиях ядер на суперкомпьютерах и во встроенных системах.

И это плохо. И мейнтейнеры дистрибутивов это знают. И они продвигают свои патчи в апстрим.

Deleted ()
Ответ на: Re: Con Kolivas вернулся: встречайте BFS от ent4jes

Re: Con Kolivas вернулся: встречайте BFS

>бггг - по сцылке LOR-эффект

очевидно же - Кон накатил новый шедулер на боевой сервер. Результат мы видим :)

k0l0b0k ★★ ()
Ответ на: Re: Con Kolivas вернулся: встречайте BFS от Relan

Re: Con Kolivas вернулся: встречайте BFS

> Переключаться между ними в run time нельзя -- только пересобирать ядро

Да? а это что? http://www.imagebin.ca/view/7MQQXxIt.html ну и планировщики по умолчанию для новых процессов точно также настраиваются...

Fragster ()
Ответ на: Re: Con Kolivas вернулся: встречайте BFS от Deleted

Re: Con Kolivas вернулся: встречайте BFS

>Вариант. Но опять же: в прошлый раз никто не подобрал =).

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

TyhDyh ()
Ответ на: Re: Con Kolivas вернулся: встречайте BFS от Deleted

Re: Con Kolivas вернулся: встречайте BFS

>> И это плохо. И мейнтейнеры дистрибутивов это знают.

отнюдь
линукс - масштабируемая система
в отличие от

kto_tama ★★★★★ ()
Ответ на: Re: Con Kolivas вернулся: встречайте BFS от Fragster

Re: Con Kolivas вернулся: встречайте BFS

> Да? а это что? http://www.imagebin.ca/view/7MQQXxIt.html ну и планировщики по умолчанию для новых процессов точно также настраиваются...

Это неточность формулировки. То что слева - это настройки планировщика CFS (Completely Fair Scheduler).

Deleted ()
Ответ на: Re: Con Kolivas вернулся: встречайте BFS от Evil_And

Re: Con Kolivas вернулся: встречайте BFS

>>То есть все многосокетные системы от AMD и новые от Intel (те что на Nehalem). Какие нафиг суперкомпьютеры?

> Они перестали быть SMP?

Нет. Только если планировщик не учитывает NUMA топологию, то это может сильно ухудшить производительность.

Relan ★★★★★ ()

Re: Con Kolivas вернулся: встречайте BFS

Наверняка у Колинза, как у бывшего анестезиолога, остались связи для приобретения веществ.

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

Turbid ★★★★★ ()
Ответ на: Re: Con Kolivas вернулся: встречайте BFS от kto_tama

Re: Con Kolivas вернулся: встречайте BFS

> линукс - масштабируемая система

Что лучше:
1) "Масштабируемость" через редактирование исходников (патченье)
2) Через пересборку ядра с новыми опциями
3) Через изменение параметра работающего ядра в реальном времени
?

Deleted ()
Ответ на: Re: Con Kolivas вернулся: встречайте BFS от z0D5e8n7x_2

Re: Con Kolivas вернулся: встречайте BFS

Перевод вполне хорош. Единственное очевидное замечание - jobs в этом контексте не работники, а задания.

AVL2 ★★★★★ ()
Ответ на: Re: Con Kolivas вернулся: встречайте BFS от Deleted

Re: Con Kolivas вернулся: встречайте BFS

> Это неточность формулировки. То что слева - это настройки планировщика CFS (Completely Fair Scheduler). ну так почему не дописать туда еще один алгоритм?

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