Interested Article - O(n) scheduler
![](/images/009/026/9026546/1.jpg?rand=181748)
![](https://cdn.wafarin.com/avatars/99c307a7bcd9067efb2967906eef4b87.jpg)
- 2021-04-18
- 1
![](/images/009/026/9026546/2.jpg?rand=371090)
O(n) scheduler — это планировщик использовавшийся в ядре Linux в версиях с 2.4 по 2.6. Начиная с версии 2.6.0, он был заменен на , а начиная с 2.6.23 на CFS.
Алгоритм
Данный планировщик делит время на «эпохи». В рамках одной эпохи процессы выполнялись отведенное им время. Если какой-то процесс выполнялся меньше отведенного времени, то половина отведенного времени добавлялась к времени, которое будет отведено процессу в следующую «эпоху». Планировщик рассматривает все доступные для запуска процессы и находил процесс, значение функции goodness для которого было бы наибольшим.
Преимущества
Данный планировщик показывал себя лучше в сравнении с более примитивным предшественником, в основе которого лежала цикличная очередь.
Недостатки
При росте числа процессов, работа планировщика начинает требовать значительное количество процессорного времени. Выбор следующей задачи сопряжен с проходом всего списка процессов готовых к выполнению, а значит выполняется за О(n) по времени, где n — количество процессов, готовых к исполнению. Так-же он не подходил для систем реального времени и не мог быть масштабирован на новейшие [ когда? ] многоядерные процессоры.
Примечания
- . Дата обращения: 1 июня 2022. 18 марта 2022 года.
![](https://cdn.wafarin.com/avatars/99c307a7bcd9067efb2967906eef4b87.jpg)
- 2021-04-18
- 1