OSDev

для всех
Текущее время: 24 июл 2019, 10:10

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 102 ]  На страницу Пред.  1 ... 7, 8, 9, 10, 11  След.
Автор Сообщение
 Заголовок сообщения: Re: Планировщик
СообщениеДобавлено: 30 июл 2011, 18:54 

Зарегистрирован: 10 май 2007, 11:33
Сообщения: 1204
Himik писал(а):
Подобные шаги нарушают принцип приоритетности, поэтому не вижу вариантов - у системы должно быть просто достаточно производительности.
Система может выявить перегрузку на этапе тестирования производительности, и сразу выдать предупреждение.
Приоритетное планирование имеет одну широко известную проблему (см. "инверсия приоритетов"), не зависящую от производительности, которая каким-либо образом должна быть решена в использующих его ядрах. Формально противоречия "основному правилу" быть не должно, т.к. приоритет удерживающего ресурс низкоприоритетного потока должен быть доведен как минимум до приоритета ожидающего ресурс высокоприоритетного потока (временно). На основе этого же решения можно решить проблему, когда имеет место не просто "кислородное голодание" низкоприоритетных потоков, а полное "отсутствие кислорода" у них.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Планировщик
СообщениеДобавлено: 30 июл 2011, 20:55 

Зарегистрирован: 21 сен 2007, 17:24
Сообщения: 1087
Откуда: Балаково
phantom-84 писал(а):
Приоритетное планирование имеет одну широко известную проблему (см. "инверсия приоритетов")

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

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

Лекарство простое - дополнительные буферы для потоков данных. Тогда, если занят один мютекс, то просто использовать другой мютекс с другим буфером.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Планировщик
СообщениеДобавлено: 15 авг 2011, 20:48 
Аватара пользователя

Зарегистрирован: 20 апр 2011, 10:54
Сообщения: 145
Фейлы понял. Код на помойку.
Почитал вики ВНИМАТЕЛЬНО. Понял, что лучше так:
имеется два основнх типа потоков: RealTime и Normal (с подтипами).
Планировщик разбит на свитчер и собственно планировщик.
Свитчер (который запускается по таймеру) имеет два коротких (около 64 элементов) Раунд-Робина (RealTime и Normal).
Свитчер запускает RealTime потоки, или, если ни одного RealTime потока нету, Normal потоки по очереди.
Когда Normal потоки кончились, запускается собственно планировщик. Он выбирает из очереди с приоритетами Normal потоки и заносит их в Раунд-Робин свитчера.
Все RealTime потоки хранятся в списке свитчера.

Опытные ОСДеверы, ткните носом в ошибки, а то опять стучать в них лбом что-то не хочется.

СПАСИБО!

_________________
Found a CPU. LAPIC ID: 00


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Планировщик
СообщениеДобавлено: 15 авг 2011, 21:00 
Аватара пользователя

Зарегистрирован: 20 апр 2011, 10:54
Сообщения: 145
Да, кстати, насчет реентерабельности...
Может, проще всего не помещать в ядро реентерабельные вызовы, а обрабатывать почти все в RealTime потоках?

_________________
Found a CPU. LAPIC ID: 00


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Планировщик
СообщениеДобавлено: 16 авг 2011, 08:07 

Зарегистрирован: 10 май 2007, 11:33
Сообщения: 1204
418ImATeapot писал(а):
Свитчер (который запускается по таймеру) имеет два коротких (около 64 элементов) Раунд-Робина (RealTime и Normal).
Не понятно, откуда и зачем взялось число 64. В кольцевой очереди должны находиться все готовые потоки данного приоритетного класса.

Цитата:
Когда Normal потоки кончились, запускается собственно планировщик. Он выбирает из очереди с приоритетами Normal потоки и заносит их в Раунд-Робин свитчера.
Из той же оперы. Если normal-потоки кончились, свитчер уже обрабатывает еще менее приоритетную очередь (idle, system idle) или непосредственно сам усыпляет процессор (если менее приоритетных потоков нет или они вообще не предусмотрены).

Цитата:
Да, кстати, насчет реентерабельности...
Может, проще всего не помещать в ядро реентерабельные вызовы, а обрабатывать почти все в RealTime потоках?
Ты собрался повышать приоритет любого потока до чистого realtime при входе в ядро, чтобы сделать системные вызовы не вытесняемыми по таймеру? Тогда это уже ближе к нереентерабельности системных вызовов. Вообще нечто подобное используется (когда приоритетных классов достаточно много), чтобы сделать одни потоки не вытесняемыми по отношению к другим потокам только по факту их превосходства в приоритете, т.е. вообще без каких-либо блокировок.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Планировщик
СообщениеДобавлено: 16 авг 2011, 13:04 
Аватара пользователя

Зарегистрирован: 20 апр 2011, 10:54
Сообщения: 145
phantom-84 писал(а):
418ImATeapot писал(а):
Свитчер (который запускается по таймеру) имеет два коротких (около 64 элементов) Раунд-Робина (RealTime и Normal).
Не понятно, откуда и зачем взялось число 64. В кольцевой очереди должны находиться все готовые потоки данного приоритетного класса.

Цитата:
Когда Normal потоки кончились, запускается собственно планировщик. Он выбирает из очереди с приоритетами Normal потоки и заносит их в Раунд-Робин свитчера.
Из той же оперы. Если normal-потоки кончились, свитчер уже обрабатывает еще менее приоритетную очередь (idle, system idle) или непосредственно сам усыпляет процессор (если менее приоритетных потоков нет или они вообще не предусмотрены)


Приоритетов ОЧЕНЬ много. Но они интересуют только планировщик, свитчер использует только два приоритета - RealTime and Normal. Суть в том, что планировщик выбирает наиболее приоритетные Normal потоки и отправляет их свитчеру, чтобы свитчеру самому не возиться с приоритетами.
Очередь свитчера фиксированной длины, для скорости. Делать ее динамической - по-моему слишком затратно. Слишком длинной - Sleep потеряет точность. Поскольку Sleep проверяется только в планировщике, ее точность зависит от частоты вызова планировщика. Точности в 1.5 с. по-моему должно хватить, дальше пусть приложение само корректирует Sleep через RDTSC.

Возможно, я неправильно понимаю термин RealTime. У меня это - поток который занимает точно 1/(длинна Раунд-Робина) апптайма (в данном случае 1/64).

Цитата:
Цитата:
Да, кстати, насчет реентерабельности...
Может, проще всего не помещать в ядро реентерабельные вызовы, а обрабатывать почти все в RealTime потоках?

Ты собрался повышать приоритет любого потока до чистого realtime при входе в ядро, чтобы сделать системные вызовы не вытесняемыми по таймеру? Тогда это уже ближе к нереентерабельности системных вызовов. Вообще нечто подобное используется (когда приоритетных классов достаточно много), чтобы сделать одни потоки не вытесняемыми по отношению к другим потокам только по факту их превосходства в приоритете, т.е. вообще без каких-либо блокировок.


Я имел в виду другое. Ядро, которое запускается в потоке, из которого было вызвано - это только распределитель ресурсов и IPC. Все остальное - в паралельных поотоках (возможно, с приостановкой основного потока).

_________________
Found a CPU. LAPIC ID: 00


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Планировщик
СообщениеДобавлено: 16 авг 2011, 17:41 

Зарегистрирован: 10 май 2007, 11:33
Сообщения: 1204
418ImATeapot писал(а):
Приоритетов ОЧЕНЬ много. Но они интересуют только планировщик, свитчер использует только два приоритета - RealTime and Normal. Суть в том, что планировщик выбирает наиболее приоритетные Normal потоки и отправляет их свитчеру, чтобы свитчеру самому не возиться с приоритетами.
Так и есть. Свитчер работает только с текущей кольцевой очередью. Переключением кольцевых очередей занимается планировщик.

Цитата:
Очередь свитчера фиксированной длины, для скорости. Делать ее динамической - по-моему слишком затратно.
Слишком затратно делать ее статической. Свитчер делает только одну короткую операцию - при истечении кванта времени текущего потока переключается на следующий поток в этой очереди.

Цитата:
Возможно, я неправильно понимаю термин RealTime. У меня это - поток который занимает точно 1/(длинна Раунд-Робина) апптайма (в данном случае 1/64).
Тут есть несколько различные трактовки. Но в целом realtime-поток - это поток, который выполняется до тех пор, пока либо сам не отдаст управление (потоку с таким же приоритетом), либо пока не будет прерван еще более приоритетным realtime-потоком. У меня есть единственный в своем роде system realtime-поток (максимальный приоритет), который за счет своей уникальности автоматически вытесняет все остальные потоки. Обычные realtime-потоки сейчас работают по принципу "application realtime" - это когда они также являются вытесняемыми по таймеру, только их кванты соответствуют реальным временным промежуткам, определяемым разработчиками ПО, а не генерируются ядром ОС, исходя из своих собственных интересов, уровня производительности аппаратуры и т.п. При таких условиях свитчер может даже не делать различий между normal- и realtime-потоками, т.к. по таймеру переключаются и одни, и другие, а system realtime- не переключается за счет того, что он единственный.

Цитата:
Я имел в виду другое. Ядро, которое запускается в потоке, из которого было вызвано - это только распределитель ресурсов и IPC. Все остальное - в паралельных поотоках (возможно, с приостановкой основного потока).
Т.е. ты предлагаешь на каждый "чих" приложения (обращение к ядру) запускать отдельный realtime-поток? Слишком накладно. Пусть уж лучше конкретный системный вызов определяется с тем, нужно ли ему запускать новый поток, обращаться к какому-либо служебному потоку ядра или все можно сделать "по-быстрому" в контексте текущего потока.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Планировщик
СообщениеДобавлено: 16 авг 2011, 19:30 
Аватара пользователя

Зарегистрирован: 20 апр 2011, 10:54
Сообщения: 145
phantom-84 писал(а):
418ImATeapot писал(а):
Приоритетов ОЧЕНЬ много. Но они интересуют только планировщик, свитчер использует только два приоритета - RealTime and Normal. Суть в том, что планировщик выбирает наиболее приоритетные Normal потоки и отправляет их свитчеру, чтобы свитчеру самому не возиться с приоритетами.
Так и есть. Свитчер работает только с текущей кольцевой очередью. Переключением кольцевых очередей занимается планировщик.


Да, опять какого-то кракозябра я загнул. Или просто сформулировал неправильно?

Я имел ввиду, что планировщик ФОРМИРУЕТ очередь заново. Из своих внутренних списков. В порядке приоритетов, предсказывая Waking-Up.

А свитчер просто проходит очередь от начала и доконца и вызывает планировщик снова. Т. е. очередь Normal потоков вовсе не "Раунд".

А "RealTime" потоки тогда - потоки, которые гарантировано запустятся в течении одного цикла.

Извиняюсь за расплывчивость формулировок.

Цитата:
Цитата:
Я имел в виду другое. Ядро, которое запускается в потоке, из которого было вызвано - это только распределитель ресурсов и IPC. Все остальное - в паралельных поотоках (возможно, с приостановкой основного потока).
Т.е. ты предлагаешь на каждый "чих" приложения (обращение к ядру) запускать отдельный realtime-поток? Слишком накладно. Пусть уж лучше конкретный системный вызов определяется с тем, нужно ли ему запускать новый поток, обращаться к какому-либо служебному потоку ядра или все можно сделать "по-быстрому" в контексте текущего потока.

Нет, не на каждый чих. Только когда нужно. Но максимально увеличить количество случаем, когда нужно.

_________________
Found a CPU. LAPIC ID: 00


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Планировщик
СообщениеДобавлено: 16 авг 2011, 20:22 

Зарегистрирован: 10 май 2007, 11:33
Сообщения: 1204
418ImATeapot писал(а):
Я имел ввиду, что планировщик ФОРМИРУЕТ очередь заново. Из своих внутренних списков. В порядке приоритетов, предсказывая Waking-Up.
Перемешивает в одной очереди потоки с разными приоритетами?

Цитата:
А свитчер просто проходит очередь от начала и доконца и вызывает планировщик снова. Т. е. очередь Normal потоков вовсе не "Раунд".
Вот это "проходит" и напрягает. При помощи статической очереди невозможно сделать так, чтобы поток мог быть изъят из ее середины (в случае необходимости) и при этом в следующем элементе гарантированно присутствовал реальный поток, а не "пустое место". А чтобы периодически отдавать управление планировщику (для инверсии приоритетов и т.п.), достаточно иметь специальный счетчик, инкрементируемый при каждом вызове свитчера и сигнализирующий о необходимости выполнить спец. действия на любом его значении, равном определенной целой степенью двойки.

Цитата:
А "RealTime" потоки тогда - потоки, которые гарантировано запустятся в течении одного цикла.
Ты хочешь ограничить количество realtime-потоков? А также какая разница, один цикл или много, если по времени даже один цикл может быть растянут на бесконечно долгое время.

Цитата:
Нет, не на каждый чих. Только когда нужно. Но максимально увеличить количество случаем, когда нужно.
Может, лучше максимально уменьшить. А то я тебе без проблем "максимально увеличу количество случаев", просто создавая новый поток (или даже несколько потоков) на каждый "чих" )))


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Планировщик
СообщениеДобавлено: 17 авг 2011, 12:46 
Аватара пользователя

Зарегистрирован: 20 апр 2011, 10:54
Сообщения: 145
phantom-84 писал(а):
418ImATeapot писал(а):
Я имел ввиду, что планировщик ФОРМИРУЕТ очередь заново. Из своих внутренних списков. В порядке приоритетов, предсказывая Waking-Up.
Перемешивает в одной очереди потоки с разными приоритетами?


Да, смешивает. Приоритет в данном случае указывает на шансы данного потока попасть в очередь.
Т. е. в очередь попадают 64 потока с максимальным (время простоя << приоритет).
Цитата:

Цитата:
А свитчер просто проходит очередь от начала и доконца и вызывает планировщик снова. Т. е. очередь Normal потоков вовсе не "Раунд".
Вот это "проходит" и напрягает. При помощи статической очереди невозможно сделать так, чтобы поток мог быть изъят из ее середины (в случае необходимости) и при этом в следующем элементе гарантированно присутствовал реальный поток, а не "пустое место". А чтобы периодически отдавать управление планировщику (для инверсии приоритетов и т.п.), достаточно иметь специальный счетчик, инкрементируемый при каждом вызове свитчера и сигнализирующий о необходимости выполнить спец. действия на любом его значении, равном определенной целой степенью двойки.

Пусть "пустое место" будет "бездействие системы".
Соответственно, чтобы удалить поток из очереди свитчера, достаточно заменить его "дескриптор" на "дескриптор" "бездействие системы".

_________________
Found a CPU. LAPIC ID: 00


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 102 ]  На страницу Пред.  1 ... 7, 8, 9, 10, 11  След.

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
cron
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB