Презентация "Основы операционных систем" по информатике – проект, доклад

Основы операционных систем

Лекция 3. Планирование процессов

Уровни планирования процессов

Долгосрочное планирование – планирование заданий. Среднесрочное планирование – swapping. Краткосрочное планирование – планирование использования процессора.

Цели планирования

Справедливость Эффективность Сокращение полного времени выполнения (turnaround time) Сокращение времени ожидания (waiting time) Сокращение времени отклика (response time)

Желаемые свойства алгоритмов планирования

Предсказуемость Минимизация накладных расходов. Равномерность загрузки вычислительной системы. Масштабируемость.

Параметры планирования

Статические параметры вычислительной системы – например, предельные значения ее ресурсов. Статические параметры процесса – кем запущен, степень важности, запрошенное процессорное время, какие требуются ресурсы и т.д. Динамические параметры вычислительной системы – например, количество свободных ресурсов в данный момент. Динамические параметры процесса – текущий приоритет, размер занимаемой оперативной памяти, использованное процессорное время и т.д.

статические динамические

CPU burst и I/O burst

Важные динамические параметры процесса

a=1 b=2 read c Ожидание окончания ввода a=a+c∗b print a Ожидание окончания вывода

CPU burst I/O burst

Вытесняющее и невытесняющее планирование

Перевод процесса из состояния исполнение в состояние закончил исполнение Перевод процесса из состояния исполнение в состояние ожидание Принятие только вынужденных решений – невытесняющее планирование Перевод процесса из состояния исполнение в состояние готовность Перевод процесса из состояния ожидание в состояние готовность Принятие вынужденных и невынужденных решений –вытесняющее планирование

Вынужденное принятие решения

Невынужденное принятие решения

Алгоритмы планирования

FCFS (First Come – First Served)

t 18 17 13 0 P0 P1 P2 исполнение готовность 1 5

RR (Round Robin) Процесс 1 Процесс 2 Процесс 3 Процесс 4 Процессор

Остаток времени CPU burst = кванта времени: По окончании кванта процесс помещается в конец очереди готовых к исполнению процессов; на исполнение выбираем новый процесс из начала очереди готовых.

Величина кванта времени – 4

И Г Очередь готовых

Величина кванта времени – 1

SJF (Shortest Job First) невытесняющий P3

вытесняющий

τ(n) – величина n-го CPU burst T(n+1) – предсказание для n+1-го CPU burst α – параметр от 0 до 1 T(n+1)= α τ(n) + (1 – α)T(n), T(0) – произвольно Если α = 0, то T(n+1) = T(n) =…= T(0), нет учета последнего поведения Если α = 1, то T(n+1) = τ(n), нет учета предыстории

приближение

В системе разделения времени N пользователей: Ti – время нахождения i-го пользователя в системе τi – суммарное процессорное время процессов i-го пользователя τi ‹‹ Ti /N τi ›› Ti /N (τi N) / Ti – коэффициент справедливости. На исполнение выбираются готовые процессы пользователя с наименьшим коэффициентом справедливости

Гарантированное планирование

– пользователь обделен

– пользователю благоволят

Приоритетное планирование

Каждому процессу процессор выделяется в соответствии с приписанным к нему числовым значением - приоритетом

Параметры для назначения приоритета бывают: -внешние -внутренние

Политика изменения приоритета: -статический приоритет -динамический приоритет

Многоуровневые очереди (Multilevel Queue)

Системные процессы приоритет 0

Процессы ректората приоритет 1

Процессы преподавателей приоритет 2

Фоновые процессы приоритет 3

Процессы студентов приоритет 4

FCFS RR

Многоуровневые очереди с обратной связью (Multilevel Feedback Queue)

Очередь 0 – Приоритет 0

Очередь 1 – Приоритет 1

Очередь 2 – Приоритет 2

Очередь 3 – Приоритет 3

RR с квантом времени 8

RR с квантом времени 16

RR с квантом времени 32

Клавиатурный ввод

Дисковый I/O

Для полного описания необходимо задать - количество очередей в состоянии готовность - алгоритм планирования между очередями - алгоритмы планирования внутри очередей - куда помещается родившийся процесс - правила перевода процессов из одной очереди в другую