LINUX.ORG.RU
Новости — Linux General  

Абсолютно Честный Планировщик (процессов для ядра)


0

0

В связи с тем, что новый планировщик от Con Kolivas не получил согласия от Линуса, а также не смог решить всех проблем, связанных с "отзывчивостью" компьютера при больших нагрузках, Ingo Molnar решил написать с нуля новый "Абсолютно Честный Планировщик" (для переключения процессов ядром Линукса). Реализация от Ingo имеет следующие преимущества: отказ от использования runqueues, использование жёсткого наносекундного режима переключения задач, который не зависит от частоты процессора и переменной HZ, а самое важное, что в этом планировщике нет никакой эвристики, т.е. достигается максимальная интерактивность всех запущенных в системе процессов. Единственная доступная для регулирования переменная - это /proc/sys/kernel/sched_granularity_ns, которая служит для переключения планировщика между режимами desktop (низкие задержки) и server (хорошее пакетирование заданий). Оригинальный патч размером 100KB был написан всего за 62 часа.

>>> Подробности

★★★★★

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

Ingo Molnar - спец мирового уровня. В очередной раз это доказал

anonymous
()

Мда, прочел, звучит заманчиво. Кто-нибудь из лоровцев потестит? Хотелось бы и в UP и в MP вариантах

annoynimous ★★★★★
()

100 кило всего за 62 часа... сейчас понабегут пыхпыхеры и задвинут баек о том, как круто бы было, если бы ядро переписали на оном, да как мощно оные пыхеры строчили гигабайтные патчи ежемесячно...

Посмотрим, что ж такого известный джедай RT-фронта наваял с таким количеством Заглавных Буковок и сколько данных потеряется при работе...

Gharik ☆
()

> Оригинальный патч размером _100KB_ был написан всего за 62 часа.

Заснул на клавиатуре? :-)

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

Скорее всего, в патче этом процентов 70% содержимого, если не больше, - вода, необходимая для работы patch.

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

Половину написал, половину удалил. Но все равно круто. Тут бывает, что над 2 строчками пару дней бъешься...


kernel/sched.c | 1454 ++++++++++++++++------------------------------------------------
 1 file changed, 372 insertions(+), 1082 deletions(-)
and even adding all the scheduling modules, the total size impact is
relatively small:

 18 files changed, 1454 insertions(+), 1133 deletions(-)

anonymous
()

А что бы им с CPU шедулерами не сделать как с IO ? Т.е. несколько шедулеров, опция при компиляции ядра какой использовать. И девелоперы довольны - никого не послали, весь работающий код включили, и юзерам щастье - какое поле для экспериментов.

anonymous
()

Буагага нравится патч от Ingo:
--- linux.orig/kernel/sched.c
+++ linux/kernel/sched.c
@@ -16,6 +16,7 @@
* by Davide Libenzi, preemptible kernel bits by Robert Love.
* 2003-09-03 Interactivity tuning by Con Kolivas.
* 2004-04-02 Scheduler domains code by Nick Piggin
+ * 2007-04-15 Con Kolivas was dead right: fairness matters! :)
*/

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

А нахрен 20 шедулеров если есть один заведомо лучший?

anonymous
()

не собирается ядро:( ядро gentoo-2.6.20 откатился назад...

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

Элементарно: единица времени - нано секунда.

TheMixa ★★★
()

> отказ от использования runqueues

не понял, опять что ли скалится как O(n)?

anonymous
()

Прочитал как абсолютно частный плонировщик

fk_
()
Ответ на: комментарий от tailgunner

А, ну уже задали :)

Вкратце: предлагаемый планировщик имеет O(log(n)) сложность, что является некоторым шагом назад, но все же гораздо лучше, чем O(n).

annoynimous ★★★★★
()

>..а самое важное, что в этом планировщике нет никакой эвристики..

Хм, а хуже не будет?

anonymous
()

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

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

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

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

>А что бы им с CPU шедулерами не сделать как с IO ? Т.е. несколько шедулеров, опция при компиляции ядра какой использовать

Так Ingo это и сделал. Просто в лучших традициях лор-а по сцылкам не ходить. Новость несовсем полностью перевели, в оригинале она звучит так: "Modular Scheduler Core and Completely Fair Scheduler [CFS]" те планировщики будут модульными.

anonymous
()
Ответ на: комментарий от comnimh

> Я правильно понимаю, что это такой "закос" под рилтайм-системы?

Нисколько.

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

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

Ingo вроде в RH работает. Или уже нет?

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

> а потом говорят о вкладе компаний в разработку ядра

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

> сообществу

Ты всё перепутал. Вот хорший пример, когда компания RedHat, в лице Ingo Molnar, вкладывает в ядро Linux!

dmesg
()
Ответ на: комментарий от annoynimous

>Вкратце: предлагаемый планировщик имеет O(log(n)) сложность, что является некоторым шагом назад, но все же гораздо лучше, чем O(n).

Нет. У этого планировщика совсем другая архитектура, раньше был либо массив задач (О(n) чтобы найти задачу с наивысшим приоритетом и переключиться на нее), либо два массива ("отработавших" свое время и еще нет, второй массив отсортирован в порядке возрастания, поэтому за одну операцию находилась нужная задача, плюс иногда делать переключение массивов - O(1) чтобы найти задачу). Теперь же по сути тоже, что и было в O(1), только задачи кладутся в дерево согласно их приоритету (времени, оставшемуся от timeslice), и дерево постоянно перемешивается (вместо того, как раньше менялись массивы).

Касательно четсности - насколько я понял, новый алгоритм просто подсчитывает время, оставшееся от выданного процессу на исполнение в данный интервал, что иявляется приоритетом, без подсчета интерактивности и прочих хитрых коэффициентов.

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

>> Вкратце: предлагаемый планировщик имеет O(log(n)) сложность, что является некоторым шагом назад, но все же гораздо лучше, чем O(n).

> Нет.

Ingo с тобой не согласен :)

Отрывок из обсуждения:

">__enqueue_task_fair doesn't appear to be
> constant time (rbtree insert complexity).. [...]

i've been worried about that myself"

Так что формально алгоритм таки _не является_ O(1), он просто очень эффективен :D

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

>>__enqueue_task_fair doesn't appear to be > constant time (rbtree insert complexity).. [...]

>i've been worried about that myself"

>Так что формально алгоритм таки _не является_ O(1), он просто очень эффективен :D

Насколько я понял (это не утверждение, а мое наблюдение), дерево балансируется постоянно, при этом "вытаскивание" наиболее приоритетной задачи (хотя теперь этот термин несколько некорректен) происходит напрямую из корня, в зависимости от того, как она отработает, добавление может занять больше. Раньше вытаскивание задачи происходило за 2 операции (ffs в битовой маске и собственно удаление из очереди), а добавление не требовало дополнительных операций.

Так что формально поиск новой задачи О(1), а добавление ее в очередь - О(log(N)) :)

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

> Элементарно: единица времени - нано секунда.

Ваше понимание принципов работы ядра просто на грани фантастики 8-)

anonymous
()
Ответ на: комментарий от TheMixa

> Элементарно: единица времени - нано секунда.

Ваше понимание принципов работы ядра просто на грани фантастики 8-)

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

> А что бы им с CPU шедулерами не сделать как с IO ? Т.е. несколько шедулеров, опция при компиляции ядра какой использовать. И девелоперы довольны - никого не послали, весь работающий код включили, и юзерам щастье - какое поле для экспериментов.

уже есть гораздо лучше: ядру передается параметр elevator=планировщик и все, ни какой перекомпиляции

так же можно использовать один планировщик в окружении другого планировщика

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

>Вкратце: предлагаемый планировщик имеет O(log(n)) сложность, что является некоторым шагом назад, но все же гораздо лучше, чем O(n).

Напомните плиз, что такое O(n) :) А то забыть успел материал первого курса :) К тому же я так эту тему и не понял... Писал во всяких выражениях, потому что "так полагается", как блондинки пишут dx в интегралах :)

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

O(n) - читается о большое от эн, означает величина пропорциональная n ,в пределе конечно, применяется для описания отношения предельных величин, т.е. lim(X)/lim(n) -> const*n. Еще есть O(1) - постоянная величина т.е отношение lim(x)/lim(n) -> const, o(n) - бесконечно малая величина по отношению к n, т.е. lim(X)/lim(n) - > 0. Здесь в контексте имеется ввиду время работы алгоритма в зависимости от количества процессов.

Кстати, кто нибуди попробовал? У меня после патча перестал запускатся syslog-ng.

anonymous_pro
()
Ответ на: комментарий от v1go

>Ассимптотическая сложность алгоритма...

Летят на воздушном шаре Холмс и Ватсон. Шар остыл и спустился в гористой местности. Ватсон спрашивает у прхожего:'Где мы находимся'. Тот отвечает:'Вы находитесь в корзине воздушного шара'- и пошел дальше.

-Как вам нравится этот математик, Ватсон?

-Холмс, но откуда такая уверенность, что он математик.

-Он дал совершенно точный, полный, и никому не нужный ответ. ;)

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

> Еще есть O(1) - постоянная величина т.е отношение lim(x)/lim(n) -> const

Это не правильно.

Тот факт, что |f(n)| <= C|g(n)| для всех n >= N обычно записывают как f = O(g). Стремления к константе это не предполагает.

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

Нет правильно! Подставте в ваше выражение вместо g единицу и получите константу. Кстати вы изложили то же, что и я, но в других обозначениях. Честно говоря, может в другом случае я бы не обратил на этот пост внимания, но здесь, помоему, мое изложение более понятно для не подготовленного читателя, т.е. читателя не изучавшего углубленно матанализ и функан.

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

Для переодических функций действительно предел неуместен, ладно согласен O(1) - функция ограниченая константой.

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