PowerPoint Presentation : Лекция №10 ПЛАНИРОВАНИЕ В СИСТЕМАХ С ОДНИМ ПРОЦЕССОРОМ
PowerPoint Presentation : Лекция №10 Цель планирования Планирование – ключ к многозадачности Цель планирования процессора состоит в распределении времени процессов, выполняемых процессором таким образом, чтобы удовлетворять требованиям системы, таким, как время отклика, пропускная способность и эффективность работы процессора.
PowerPoint Presentation : Лекция №10 Типы планирования процессора Выделяют следующие типы планирования: Долгосрочное планирование. Решение о добавлении процесса в пул выполняемых процессов. Среднесрочное планирование. Решение о добавлении процесса к числу процессов, полностью или частично размещенных в основной памяти. Краткосрочное планирование. Решение о том, какой из доступных процессов будет выполняться процессором.
PowerPoint Presentation : Лекция №10 Место планирования в диаграмме переходов состояний Новый Готовый/ приостановленный Готовый Заблокирован-ный/приостановленный Заблориван-ный Выполняю-щийся Выход Долгосрочное планирование Среднесрочное планирование Краткосрочное планирование
PowerPoint Presentation : Лекция №10 Сущность планирования По сути планирование представляет собой управление очередями с целью минимизации задержек. Долгосрочное планирование Краткосрочное планирование Среднесрочное планирование Среднесрочное планирование Вход Выход Процессор Очередь готовых заданий Очередь готовых приостановленных заданий Очередь заблокирован-ных приостановленных заданий Очередь заблокированных заданий Ожидание события Событие
PowerPoint Presentation : Лекция №10 Долгосрочное планирование Долгосрочный планировщик создает процессы из очереди заданий решая два основных вопроса: Способна ли операционная система работать с дополнительными процессами? Какое именно задание следует превратить в процесс? Ответ на первый вопрос определяется уровнем многозадачности системы (сколько процессов одновременно в состоянии поддерживать ОС). Ответ на второй может основываться на различных критериях: первый пришел, первый обслужен ; приоритет ; требования к вводу выводу и т.д.
PowerPoint Presentation : Лекция №10 Среднесрочное планирование Среднесрочное планирование является частью системы свопинга, в нем используются алгоритмы описанные в лекции «Виртуальная память».
PowerPoint Presentation : Лекция №10 Краткосрочное планирование Краткосрочный планировщик (диспетчер) определяет, какой именно процесс будет выполняться следующим. Критерии краткосрочного планирования: Пользовательские Системные Кроме этого критерии могут быть связаны или не связаны с производительностью.
PowerPoint Presentation : Лекция №10 Пользовательские критерии Связанные с производительностью Время оборота. Интервал времени между подачей процесса и его завершением Время отклика. Время между подачей запроса и началом получения ответа на него. Не связанные с производительностью Предсказуемость. Данное задание должно выполняться примерно за одно и то же количество времени и с одной и той же стоимостью, независимо от загрузки системы.
PowerPoint Presentation : Лекция №10 Системные критерии Связанные с производительностью Пропускная способность. Стремление максимизировать количество процессов, завершающихся за единицу времени. Использование процессора. Стремление максимизировать процент времени, в течении которого процессор занят. Не связанные с производительностью Беспристрастность. Все процессы должны рассматриваться как равнозначные и ни один не должен подвергнуться голоданию. Использование приоритетов. Отдавать предпочтение процессам с более высоким приоритетом. Баланс ресурсов. Поддерживает равномерную максимальную загруженность ресурсов.
PowerPoint Presentation : Лекция №10 Алгоритмы краткосрочного планирования Наиболее часто на практике можно встретить использование следующих алгоритмов: «Первым поступил – первым обслужен» ( FCFS) Круговое планирование ( RR ) Выбор самого короткого процесса ( SPN) Наименьшее остающееся время ( SRT) Наивысшее отношение отклика ( HRRN) Снижение приоритета
PowerPoint Presentation : Лекция №10 «Первым поступил – первым обслужен» FCFS (First-come-first-served) – алгоритм строгой очередности. Как только процесс становиться готовым к выполнению, он присоединяется к очереди готовых процессов. При прекращении выполнения текущего процесса для выполнения выбирается первый в очереди процесс. Достоинства: Минимальные накладные расходы. Недостатки: Плохо сказывается на коротких процессах и процессах с интенсивным вводом-выводом.
PowerPoint Presentation : Лекция №10 Круговое планирование RR (Round Robin) – «карусель» или «круговорот» - вытесняет процессы используя таймер. Таким образом между прерываниями от таймера каждый процесс получает свой квант времени . Достоинства: Минимальные накладные расходы. Хорошее время отклика для коротких процессов. Недостатки: Снижается пропускная способность особенно при малом кванте времени.
PowerPoint Presentation : Лекция №10 Выбор самого короткого процесса SPN (shortest process next) – невытесняющая стратегия, при которой выбирается процесс с наименьшим ожидаемым временем исполнения. Достоинства: Хорошее время отклика для коротких процессов. Недостатки: Плохо сказывается на длинных процессах. Возможно голодание. Трудно точно оценить заранее время работы процесса. Повышаются накладные расходы.
PowerPoint Presentation : Лекция №10 Наименьшее остающееся время SRT (shortest remaining time) – планирование при котором выбирается процесс с наименьшим ожидаемым временем окончания. Фактически SPN с возможностью вытеснения. Достоинства: Хорошее время отклика. Улучшены условия длинных процессов по сравнению с SPN . Недостатки: Все еще плохо сказывается на длинных процессах. Возможно голодание. Повышаются накладные расходы
PowerPoint Presentation : Лекция №10 Наивысшее отношение отклика HRRN (highest response ratio next) – еще одна невытесняющая стратегия – попытка улучшить SPN , учитывая возраст процесса. Из очереди готовых процессов выбирается процесс с наибольшим отношением отклика R: R = (w+s)/s , Где w – время ожидания процесса. s – ожидаемое время обслуживания. Достоинства: Хорошее время отклика и для коротких и для длинных процессов. Нет голодания. Недостатки: Требуется оценка времени обслуживания.
PowerPoint Presentation : Лекция №10 Снижение приоритета Вытесняющая стратегия, улучшающая положение коротких процессов, не требуя оценки времени обслуживания. Организуется несколько очередей с убывающим приоритетом. При входе процесса в систему от попадает в очередь RQ0 с наивысшим приоритетом. После одного или нескольких вытеснений в очередь RQ1 , приоритет которой ниже и т.д. пока не достигнет фоновой очереди или не завершится. Достоинства: Не требуется оценка времени обслуживания Недостатки: Не удается полностью избежать возможности голодания