The OpenNET Project / Index page

[ новости /+++ | форум | теги | ]

форумы  помощь  поиск  регистрация  майллист  ВХОД  слежка  RSS
"OpenNews: Детали реализации планировщика задач в Linux ядре ..."
Вариант для распечатки Архивированная нить - только для чтения! 
Пред. тема | След. тема 
Форумы Разговоры, обсуждение новостей (Public)
Изначальное сообщение [Проследить за развитием треда]

"OpenNews: Детали реализации планировщика задач в Linux ядре ..."
Сообщение от opennews on 28-Дек-03, 13:48 
Статья "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

Cообщить модератору | Наверх | ^

 Оглавление

Сообщения по теме [Сортировка по времени, UBB]


1. "Ну не могут затраты времени на планирование задач не зависет..."
Сообщение от Дмитрий Ю. Карпов email on 28-Дек-03, 13:48 
Сложность O(N) - в примитивных алгоритмах (вряд ли можно написать алгоритм с O(N^2)).
Я понимаю, когда сложность сводится до O(log(N)), но не верю в O(1), т.к. всегда будут случаи, когда несколько задач одновременно приобретают наивысший на данный момент приоритет, а ещё надо регулярно корректировать приоритет у каждой задачи.
Cообщить модератору | Наверх | ^

2. "Ну не могут затраты времени на планирование задач не зависет..."
Сообщение от koka on 28-Дек-03, 15:09 
почему же не могут?
вспомним из школы алгоритм планирования процессов Round-Robin. Имеется очередь процессов. Берётся первый из них, запускается и после кванта времени ставится в конец.
Имееем явный O(1). Теперь всякими извращениями добавляем сюда приоритет и возможнось возникновения процессов в других состояниях (stopped, etc) - и получаем чистый O(1)
Cообщить модератору | Наверх | ^

3. "затраты времени на планирование задач"
Сообщение от Дмитрий Ю. Карпов email on 29-Дек-03, 17:22 
> почему же не могут?
> вспомним из школы алгоритм планирования процессов Round-Robin.
> Имеется очередь процессов. Берётся первый из них, запускается
> и после кванта времени ставится в конец. Имееем явный O(1).
> Теперь всякими извращениями добавляем сюда приоритет и возможнось
> возникновения процессов в других состояниях (stopped, etc) -
> и получаем чистый O(1)

Вот как только мы добавим приоритеты и состояния процессов, так сразу станет невозможно использовать Round-Robin, а любой другой алгоритм стОит дороже, чем O(1). Причём чем сильнее мы хотим увеличить эффективность многозадачности, тем сложнее будет алгоритм и тем больше времени он будет занимать сам (особенно в вырожденных ситуациях - например, при большом количестве процессов с одинаковым приоритетом).

Cообщить модератору | Наверх | ^

Удалить

Индекс форумов | Темы | Пред. тема | След. тема




Партнёры:
PostgresPro
Inferno Solutions
Hosting by Hoster.ru
Хостинг:

Закладки на сайте
Проследить за страницей
Created 1996-2024 by Maxim Chirkov
Добавить, Поддержать, Вебмастеру