O(1) kernel sheduler - по сути не O(1)?

В CFS, ЕМНИП, по очереди на каждое ядро, смотри исходники.

Кроме CFS, можешь еще почитать раздел Goals, Design reasoning и другие разделы планировщика BFS здесь.

Оно O(1) по времени работы: http://en.wikipedia.org/wiki/O(1)_scheduler

Только этот шедулер, слава богу, давно сдох в пользу cfs.

Нашел по ссылке в pdf (joshaas.net).

5.3 Priority Arrays
5.3.1 Overview
This data structure is the basis for most of the Linux 2.6.8.1 scheduler’s ad-
vantageous behavior, in particular its O(1) (constant) time performance. The
Linux 2.6.8.1 scheduler always schedules the highest priority task on a system,
and if multiple tasks exist at the same priority level, they are scheduled round-
robin with each other. Priority arrays make finding the highest priority task in a
system a constant-time operation, and also makes round-robin behavior within
priority levels possible in constant-time. Furthermore, using two priority arrays
in unison (the active and expired priority arrays) makes transitions between
timeslice epochs a constant-time operation. An epoch is the time between when
all runnable tasks begin with a fresh timeslice and when all runnable tasks have
used up their timeslices.

Только этот шедулер, слава богу, давно сдох в пользу cfs.

In versions of Linux kernel 2.6 prior to 2.6.23

Не так уж и давно, но я уже успел забыть про него :)

and also makes round-robin behavior within priority levels possible in constant-time

я не догнал как они этого добились.

Пункт 5.3.3

Priority arrays are an array of linked lists, one for each priority level

А если у меня все процессы с одинаковым приоритетом. т.е. все в одном списке. самый последний в этом списке с флагом что готов к выполнению
Вот и юзкейс когда деградирует до O(N)

Или в списке только готовые к выполнению процессы?

слава богу, давно сдох в пользу cfs.

к сожалению, cfs пока не хотят выпиливать(

Пункт 5.4, оно само умеет динамически повышать и понижать приоритеты.

Если все очереди для всех приоритетов забита готовыми и _ожидающими_ выполнения процессами, тогда все равно O(N)

А понял, там только активные процессы в struct prio_array.
Для неактивных есть отдельная очередь.
Тогда действительно O(1). Интересно, почему все свалили на CFS?

Очередь, вероятно, циклический список. Есть, вероятно, указатель на текущий элемент очереди.

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

Нужно только проверять битмап для поиска очереди с максимальным приоритетом и брать первый попавшийся элемент из этой очереди.

Для неактивных есть отдельная очередь.

Как ты и написал в первом посте :)

Интересно, почему все свалили на CFS?

http://stackoverflow.com/questions/3486651/why-the-move-from-o1-scheduler-to-...

cfs пока не хотят выпиливать(

CFS нормально работает.

И что вместо?

bfs. Ну или может что-то более модульное и мелкое напишут.

BFS до жути плохо работает => не вариант.

BFS до жути плохо работает => не вариант.

Зато лучше, чем CFS.

CFS нормально работает.

Да О(1) ваще ужоснах, если что-то тяжёлое и критичное писать. И с кучей родовых проблем, которые никак решить нельзя. CFS, помнится, версии 2-3-4 недопиленный немного был, но потом всё хорошо стало.

Да О(1) ваще ужоснах, если что-то тяжёлое и критичное писать

ты сейчас о планировщике или об алгоритмах с временем работы O(1)?

Ну речь же о планировщиках идёт, вот и я про них...

Тогда действительно O(1). Интересно, почему все свалили на CFS?

Дело в том, что в реальности разницы в скорости между O(1) и O(logn) нету, она только в теории существует.

Тогда действительно O(1). Интересно, почему все свалили на CFS?

В первую очередь, tick vs tickless. Во-вторую: CFS гораздо более гибок.