2015-07-14
1651
- оптимален в системах реального времени
Оценка длины среднего периода активности вычисляется по формуле:
T (n + 1) = a*tn + (1 - a)*tn
T – текущее значение энного CPU burst
T (n + 1) – следующее его значение, которое мы предсказываем
А – коэффициент старения информации (от 0 до 1);
Вытесняющие алгоритмы планирования бывают разные:
- на основе квантования
- на основе приоритетов
- смешанные
1) Квантование – каждому потоку последовательно выделяется квант процессорного времени.
Смена потоков происходит при:
- поток завершился и покинул систему
- произошла ошибка
- поток перешел в заблокированное состояние
- поток исчерпал свой квант (переходит в состояние готовности)
Кванты бывают:
- одинаковые для всех потоков.
- разные
Длина кванта – q. Количество потоков – n. Поток ждет (n-1)*q времени. Чем больше потоков, тем больше ждет, но если квант достаточно маленький – это время ожидания все равно не заметно для пользователя. Обычно оно составляет десятки миллисекунд.
Но чем больше квант – тем больше вероятность, что поток все сделает в первом же цикле, и зависимость времени ожидания потока от времени выполения снижается. Если квант совсем большой – то система превращается в систему линейной обработки.
|
|
|
Кванты для одного потока бывают:
- фиксированной величины
- изменяться в течение жизни потока. (Например, сначала дают большой квант, а потом все меньше и меньше. Короткие задачи выполняются сразу, а длинные вычисления идут в фоновом режиме.)
Система может формировать несколько очередей готовых к выполнению потоков, в зависимости от того, сам ли поток отдал квант или его у него забрали (использован квант до конца или нет), и первыми брать на выполнение из очереди, где собрались потоки, недоиспользовавшие свои кванты.
При алгоритмах, основанных на квантовании, совершенно не учитывается предварительная инфа о задачах (длинные или короткие, важные или нет, сколько они будут использовать процессор, а сколько – устройства ввода-вывода).
2) Алгоритмы планирования, основанные на приоритетах
При приоритетном обслуживании каждый поток обладает изначально известной характеристикой – приоритетом.
Приоритет – число, характеризующее степень привилегированности потока при использовании процессорного времени. Чем выше приоритет – тем выше привилегии, тем меньше поток стоит в очередях.
Приоритет может быть целым, дробным, положительным, отрицаетельным, чем меньше – тем больше, чем больше – тем меньше и тд, в разных системах.
Приоритет потока непосредственно связан с приоритетом процесса, который назначался ему системой при его создании. Система при создании процесса, анализирует, системный он или пользовательский, каковы права пользователя, создавшего его, были ли явные указания на повышение приоритета – и на основании этого назначает потоку определнный приоритет.
|
|
|
Приоритеты бывают:
- фиксированные (один раз назначен – и до конца процесса не меняется)
- динамические (меняются в течение жизни потока)
- по инициативе юзера (он выполняет нужную команду) – в современных системах этого стараются избегать, повышать приоритеты потока могут только админы, и то в определенных пределах.
- по инициативе самого потока (обращается с вызовом к ОСи);
- по инициативе ОС в зависимости от ситуации в системе.
Приоритетное обслуживание бывает:
- с относительными приоритетами
Поток выбран и исполняется, хот гром греми.
Подходит для систем пакетной обработки
- с абсолютными приоритетами
Поток исполняется, пока в очереди не появится процесс с более высоким приоритетом.
Подходит для систем, где нужна быстрая реакция на событие.
3) Смешанные алгоритмы планирования
Используется как система квантования, так и система приоритетов. Например, в основе лежит квантование, но величина кванта и порядок выбора потока на исполнение определяется его приоритетами. Большинство ОС работают так.
13. Приоритеты и концепции планирования потоков в Windows 2000, ОС Unix System V и OS/2.
