Слайд 1Операционные системы
Евгений Власов
Слайд 2Алгоритмы планирования процессов
Решение о том, кому дать следующий квант времени
процессора определяет планирование.
Планирование процессов в ОС это процесс выбора –
кто будет исполняться следующим и как долго это будет исполняться.
ВАЖНО! Не путать с диспетчеризацией (переключением контекста), которая является просто механизмом передачи управления.
Слайд 3Классы планировщиков
Пакетный
Итерактивный
Реального времени
Слайд 4Пакетный – ориентирован на длительные задачи, которые требуют больших вычислительных
ресурсов, где не требуется частое прерывание. Т.е. подразумевают обработку больших
задач большими пакетами, нет ограничения на время выполнения.
Интерактивный – ориентирован на снижение времени отклика, т.е. чтобы система казалась ”отзывчивой”. Обычные абонентские системы на ПК – это интерактивные системы, когда в ответ на действие пользователя (например перемещение мыши) ОС что-то делает. И всегда пользователю хочется, чтобы этот ответ происходил как можно быстрее.
Главное чтобы на поступающий в систему запрос был получен максимально быстро ответ. Запрос – это любое взаимодействие с компьютером.
Слайд 5Реального времени – специализированные класс, ориентированный на дедлайн – предельный
срок завершения какой-либо работы. Главное, чтобы определенное действие завершалось к
определенному сроку, это понятие называется дедлайн. Поступающий запрос должен быть обработан не более, чем в определенный промежуток времени. Классический пример СРВ – управление ядерным реактором, в котором превышение времени отклика приведет к аварийной ситуации.
Слайд 6Уровни планирования
Долговременное(долгосрочное) – решает какие новые задачи будут добавлены
(концептуальные вопросы).
Среднесрочное – решает нужно ли временно выгружать программу во
вторичную память (какую и вообще нужно ли это).
Краткосрочный – решает, какому потоку дать следующий квант процессорного времени и какой длины. Координирует выполняющиеся потоки на разных ЦП.
Слайд 7Цели планирования
Справедливость
Эффективность
Сокращение полного времени выполнения (turnaround time)
Сокращение времени ожидания
(waiting time)
Сокращение времени отклика (response time)
Слайд 8Справедливость
гарантировать каждому заданию или процессу определенную часть времени использования процессора
в компьютерной системе, при этом не допуская возникновения ситуации, когда
процесс одного пользователя постоянно занимает процессор, в то время как процесс другого пользователя фактически не начинал выполняться.
Слайд 9Эффективность
постараться занять процессор на все 100% рабочего времени, не позволяя
ему простаивать в ожидании процессов, готовых к исполнению. В реальных
вычислительных системах загрузка процессора колеблется от 40 до 90%.
Слайд 10Сокращение полного времени выполнения (turnaround time)
обеспечить минимальное время между стартом
процесса или постановкой задания в очередь для загрузки и его
завершением.
Слайд 11Сокращение времени ожидания
( waiting time )
сократить время, которое проводят процессы в
состоянии готовность и задания в очереди для загрузки.
Слайд 12Сокращение времени отклика
( response time )
минимизировать время, которое требуется процессу в
интерактивных системах для ответа на запрос пользователя.
Слайд 13Желаемые свойства алгоритмов планирования
Предсказуемость
Минимизация накладных расходов.
Равномерность загрузки вычислительной системы.
Масштабируемость.
Слайд 14Предсказуемость
Одно и то же задание должно выполняться приблизительно за одно
и то же время. Применение алгоритма планирования не должно приводить, к примеру,
к извлечению квадратного корня из 4 за сотые доли секунды при одном запуске и за несколько суток – при втором запуске.
Слайд 15Минимизация накладных расходов.
Если на каждые 100 миллисекунд, выделенные процессу
для использования процессора, будет приходиться 200 миллисекунд на определение того,
какой именно процесс получит процессор в свое распоряжение, и на переключение контекста, то такой алгоритм, очевидно, применять не стоит.
Слайд 16Равномерность загрузки вычислительной системы
ОС обеспечивает доступ процессам ко всем ресурсам
ВС, избегая по возможности ситуации когда нужные процессу ресурсы недоступны
из-за некорректного планирования.
Слайд 17Масштабируемость
способность системы, сети или процесса справляться с увеличением рабочей нагрузки
(увеличивать свою производительность) при добавлении ресурсов и/или увеличении нагрузки.
Например,
рост количества процессов в системе в два раза не должен приводить к увеличению полного времени выполнения процессов на порядок
Слайд 18Статические
параметры планирования
Статические параметры вычислительной системы – например, предельные значения ее
ресурсов.
Статические параметры процесса – кем запущен, степень важности, запрошенное процессорное
время, какие требуются ресурсы и т.д.
Слайд 19Динамические параметры планирования
Динамические параметры вычислительной системы – например, количество свободных
ресурсов в данный момент.
Динамические параметры процесса – текущий приоритет, размер
занимаемой оперативной памяти, использованное процессорное время и т.д.
Слайд 20Алгоритмы планирования
First-Come, First-Served (FCFS)
Round Robin (RR)
Shortest-Job-First (SJF)
Гарантированное планирование
Приоритетное планирование
Многоуровневые очереди
(Multilevel Queue)
Многоуровневые очереди с обратной связью (Multilevel Feedback Queue)
Слайд 21Алгоритмы планирования
FCFS (First Come – First Served)
t
18
17
13
0
P0
P1
P2
исполнение
готовность
готовность
исполнение
исполнение
исполнение
готовность
готовность
1
исполнение
5
исполнение
18
Слайд 22Алгоритмы планирования
RR (Round Robin)
Процесс 1
Процесс 2
Процесс 3
Процесс 4
готовность
готовность
готовность
исполнение
Процессор
Процесс 3
Процесс 3
Процесс
4
исполнение
готовность
готовность
готовность
Процесс 1
Процесс 2
готовность
Процесс 4
готовность
Процесс 2
исполнение
готовность
Слайд 23Алгоритмы планирования
Остаток времени CPU burst
до истечения кванта;
на исполнение выбираем новый процесс из начала очереди
готовых;
Остаток времени CPU burst >= кванта времени:
По окончании кванта процесс помещается в конец очереди готовых к исполнению процессов;
на исполнение выбираем новый процесс из начала очереди готовых.
RR (Round Robin)
Слайд 24Алгоритмы планирования
RR (Round Robin)
Величина кванта времени – 4
И
И
И
И
Г
Г
Г
Г
Г
Г
Г
Г
P0
P1
P2
Очередь готовых
P0
исполнение
P1
P2
P0
P1
P2
P0
И
И
И
И
Г
Г
Г
Г
Г
Г
Г
Г
P2
P0
И
Г
P0
И
И
И
И
И
И
И
И
И
Слайд 25Алгоритмы планирования
RR (Round Robin)
Величина кванта времени – 1
И
Г
Г
P0
P1
P2
Очередь готовых
P0
исполнение
P1
P2
P0
P2
P0
P0
P1
И
Г
Г
P1
P2
P1
И
Г
Г
P0
P1
И
Г
P1
И
Г
И
Г
И
Г
И
Г
И
Г
И
И
И
И
И
И
И
И
И
Слайд 26Алгоритмы планирования
SJF (Shortest Job First)
невытесняющий
И
Г
Г
Г
И
И
И
Г
Г
Г
Г
Г
Г
И
И
И
И
И
Г
Г
Г
Г
Г
И
И
И
И
И
И
И
P0
P1
P2
готовность
P3
исполнение
P3
P1
P0
P2
Слайд 27Алгоритмы планирования
SJF (Shortest Job First)
вытесняющий
И
Г
P0
P1
P2
готовность
P3
исполнение
P3
P1
P0
P2
Г
И
И
И
Г
Г
Г
Г
И
И
Г
Г
И
Г
Г
И
И
И
И
И
Г
Г
Г
Г
Г
И
И
И
И
И
И
Слайд 28Приоритетное планирование
каждому процессу присваивается определенное числовое значение – приоритет, в
соответствии с которым ему выделяется процессор. Процессы с одинаковыми приоритетами
планируются в порядке FCFS.
Планирование с использованием приоритетов может быть как вытесняющим, так и невытесняющим. При вытесняющем планировании процесс с более высоким приоритетом, появившийся в очереди готовых процессов, вытесняет исполняющийся процесс с более низким приоритетом. В случае невытесняющего планирования он просто становится в начало очереди готовых процессов. Давайте рассмотрим примеры использования различных режимов приоритетного планирования.
Слайд 29Многоуровневые очереди (Multilevel Queue)
