Статья "Inside the Linux 2.6 Scheduler" общедоступно рассказывает
о реализации планировщика задач в новом Linux ядре (O(1) - затраты на планирование распределения квантов времени, не зависят от текущего числа задач в системе).URL: http://www.arstechnica.com/etc/linux/index.html
Новость: http://www.opennet.me/opennews/art.shtml?num=3229
Сложность O(N) - в примитивных алгоритмах (вряд ли можно написать алгоритм с O(N^2)).
Я понимаю, когда сложность сводится до O(log(N)), но не верю в O(1), т.к. всегда будут случаи, когда несколько задач одновременно приобретают наивысший на данный момент приоритет, а ещё надо регулярно корректировать приоритет у каждой задачи.
почему же не могут?
вспомним из школы алгоритм планирования процессов Round-Robin. Имеется очередь процессов. Берётся первый из них, запускается и после кванта времени ставится в конец.
Имееем явный O(1). Теперь всякими извращениями добавляем сюда приоритет и возможнось возникновения процессов в других состояниях (stopped, etc) - и получаем чистый O(1)
> почему же не могут?
> вспомним из школы алгоритм планирования процессов Round-Robin.
> Имеется очередь процессов. Берётся первый из них, запускается
> и после кванта времени ставится в конец. Имееем явный O(1).
> Теперь всякими извращениями добавляем сюда приоритет и возможнось
> возникновения процессов в других состояниях (stopped, etc) -
> и получаем чистый O(1)Вот как только мы добавим приоритеты и состояния процессов, так сразу станет невозможно использовать Round-Robin, а любой другой алгоритм стОит дороже, чем O(1). Причём чем сильнее мы хотим увеличить эффективность многозадачности, тем сложнее будет алгоритм и тем больше времени он будет занимать сам (особенно в вырожденных ситуациях - например, при большом количестве процессов с одинаковым приоритетом).