O(n) планировщик

Расположение «планировщика O(n)» (планировщика процессов) в упрощенной структуре ядра Linux.

Планировщик O (n) — планировщик , используемый в ядре Linux между версиями 2.4 и 2.6. Начиная с версии 2.6.0 он был заменен планировщиком O(1) , а в версии 2.6.23 — текущим планировщиком Completely Fair (CFS).

Алгоритм

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

Преимущества

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

Недостатки

Если количество процессов велико, планировщик может использовать значительную часть процессорного времени. Выбор следующей задачи для запуска требует повторения всех запланированных на данный момент задач, поэтому планировщик работает за время O(n) , где n — количество запланированных процессов.