O(n) scheduler

Эту статью предлагается удалить. Пояснение причин и соответствующее обсуждение вы можете найти на странице Википедия:К удалению/10 июля 2022. Пока процесс обсуждения не завершён, статью можно попытаться улучшить, однако следует воздерживаться от переименований или немотивированного удаления содержания, подробнее см. руководство к дальнейшему действию. Не снимайте пометку о выставлении на удаление до подведения итога обсуждения. Последнее изменение сделано участником InternetArchiveBot (вклад · журналы) в 09:45, 12 июня 2023 (UTC; около 535 дней назад). Администраторам и подводящим итоги: ссылки сюда история журналы удалить

O(n) scheduler^[1] — это планировщик использовавшийся в ядре Linux в версиях с 2.4 по 2.6. Начиная с версии 2.6.0, он был заменен на O(1) scheduler, а начиная с 2.6.23 на CFS.

Данный планировщик делит время на «эпохи». В рамках одной эпохи процессы выполнялись отведенное им время. Если какой-то процесс выполнялся меньше отведенного времени, то половина отведенного времени добавлялась к времени, которое будет отведено процессу в следующую «эпоху». Планировщик рассматривает все доступные для запуска процессы и находил процесс, значение функции goodness для которого было бы наибольшим.

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

При росте числа процессов, работа планировщика начинает требовать значительное количество процессорного времени. Выбор следующей задачи сопряжен с проходом всего списка процессов готовых к выполнению, а значит выполняется за О(n) по времени, где n — количество процессов, готовых к исполнению. Так-же он не подходил для систем реального времени и не мог быть масштабирован на новейшие^{[когда?]} многоядерные процессоры.