форумы  помощь  поиск  регистрация  майллист  ВХОД  слежка

Вариант для распечатки		Архивированная нить - только для чтения!  Пред. тема | След. тема
Форумы Разговоры, обсуждение новостей (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. "Ну не могут затраты времени на планирование задач не зависет..."

Сообщение от Дмитрий Ю. Карпов 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. "затраты времени на планирование задач"
	Сообщение от Дмитрий Ю. Карпов on 29-Дек-03, 17:22
	> почему же не могут? > вспомним из школы алгоритм планирования процессов Round-Robin. > Имеется очередь процессов. Берётся первый из них, запускается > и после кванта времени ставится в конец. Имееем явный O(1). > Теперь всякими извращениями добавляем сюда приоритет и возможнось > возникновения процессов в других состояниях (stopped, etc) - > и получаем чистый O(1) Вот как только мы добавим приоритеты и состояния процессов, так сразу станет невозможно использовать Round-Robin, а любой другой алгоритм стОит дороже, чем O(1). Причём чем сильнее мы хотим увеличить эффективность многозадачности, тем сложнее будет алгоритм и тем больше времени он будет занимать сам (особенно в вырожденных ситуациях - например, при большом количестве процессов с одинаковым приоритетом).
	Cообщить модератору | Наверх | ^

Удалить

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