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

Тема 3. Планирование процессов

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

Цели планирования Справедливость Справедливость Эффективность Эффективность Сокращение полного времени выполнения (turnaround time) Сокращение полного времени выполнения (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

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

Алгоритмы планирования Процессы P0P0P0P0 P1P1P1P1 P2P2P2P2 Продолжительность CPU burst 1341 FCFS (First Come – First Served) t P0P0P0P0 P1P1P1P1 P2P2P2P2 исполнение готовность готовность исполнение исполнениеПроцессы P2P2P2P2 P1P1P1P1 P0P0P0P0 Продолжительность CPU burst 1413 исполнение готовность готовность 1 исполнение 5 исполнение 18

Алгоритмы планирования RR (Round Robin) Процесс 1 Процесс 2 Процесс 3 Процесс 4 готовность готовностьготовность исполнение Процессор Процесс 3 Процесс 4 исполнение готовность готовность готовность готовность Процесс 1 готовность готовность Процесс 3 Процесс 2 исполнение готовность Процесс 4 готовность Процесс 3 Процесс 1 Процесс 2 исполнение Процесс 1 Процесс 2 готовность

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

Алгоритмы планирования Процессы P0P0P0P0 P1P1P1P1 P2P2P2P2 Продолжительность CPU burst 1341 RR (Round Robin) время P0P0P0P0 P1P1P1P1 P2P2P2P2 Величина кванта времени – 4 ИИИИ ГГ ГГ ГГГ Г P0P0P0P0 P1P1P1P1 P2P2P2P2 Очередь готовых P0P0P0P0 исполнение P1P1P1P1 P2P2P2P2 P0P0P0P0 P1P1P1P1 P2P2P2P2 P0P0P0P0 ИИИИ ГГГГ ГГГГ P2P2P2P2 P0P0P0P0 И Г P0P0P0P0 ИИИИИИИИИ

Алгоритмы планирования Процессы P0P0P0P0 P1P1P1P1 P2P2P2P2 Продолжительность CPU burst 1341 RR (Round Robin) время P0P0P0P0 P1P1P1P1 P2P2P2P2 Величина кванта времени – 1 И Г Г P0P0P0P0 P1P1P1P1 P2P2P2P2 Очередь готовых P0P0P0P0 исполнение P1P1P1P1 P2P2P2P2 P0P0P0P0 P2P2P2P2 P0P0P0P0 P0P0P0P0 P1P1P1P1 И Г Г P1P1P1P1 P2P2P2P2 P1P1P1P1 И Г Г P0P0P0P0 P1P1P1P1 И Г P1P1P1P1 И Г И Г И Г И ГИ ГИИИИ И И И ИИ

Алгоритмы планирования SJF (Shortest Job First) ПроцессыP0P0 P1P1 P2P2 P3P3 Продолжительность CPU burst 5371 невытесняющий время P0P0 P1P1 P2P2 P3P3 И Г Г Г ИИИ ГГГ ГГГИИИИИ ГГ Г ГГ И ИИИИИИ P0P0P0P0 P1P1P1P1 P2P2P2P2 готовность P3P3P3P3 исполнение P3P3P3P3 P1P1P1P1 P0P0P0P0 P2P2P2P2

Алгоритмы планирования ПроцессыP0P0 P1P1 P2P2 P3P3 Продолжительность CPU burst6255 Момент появления в очереди0260 SJF (Shortest Job First) вытесняющий И Г P0P0P0P0 P1P1P1P1 P2P2P2P2 готовность P3P3P3P3 исполнение P3P3P3P3 P1P1P1P1 P0P0P0P0 P2P2P2P2 время P0P0 P1P1 P2P2 P3P3 Г И И И ГГ ГГИИ ГГ И Г ГИИИИИ ГГГГГИИИИИИ

Алгоритмы планирования τ(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), нет учета предыстории SJF (Shortest Job First) приближение

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

Алгоритмы планирования Приоритетное планирование Каждому процессу процессор выделяется в соответствии с приписанным к нему числовым значением - приоритетом Параметры для назначения приоритета бывают: -внешние-внутренние Политика изменения приоритета: -статический приоритет -динамический приоритет

Алгоритмы планирования время P0P0 P1P1 P2P2 P3P3 Приоритетное планирование невытесняющий И Г P0P0P0P0 P1P1P1P1 P2P2P2P2 готовность P3P3P3P3 исполнение P3P3P3P3 P1P1P1P1 P0P0P0P0 P2P2P2P2 Г И И И ГГ И И ГГ И Г ИИИИИ ГГГГГИИИИИИ ПроцессыP0P1P2P3 Продолжительность CPU burst6255 Момент появления в очереди0260 Приоритет4321 ГГ Г Г

Алгоритмы планирования время P0P0 P1P1 P2P2 P3P3 Приоритетное планирование вытесняющий И Г P0P0P0P0 P1P1P1P1 P2P2P2P2 готовность P3P3P3P3 исполнение P3P3P3P3 P1P1P1P1 P0P0P0P0 P2P2P2P2 Г И И И ГГ И И ГГ И Г ИИИИИ ГГГГГИИИИИИ ПроцессыP0P1P2P3 Продолжительность CPU burst6255 Момент появления в очереди0260 Приоритет4321 ГГ ГГГ ГГ Г

Алгоритмы планирования Многоуровневые очереди (Multilevel Queue) Системные процессы приоритет 0 Процессы ректората приоритет 1 Процессы преподавателей приоритет 2 Фоновые процессы приоритет 3 Процессы студентов приоритет 4 FCFS RR RR RR RR

Алгоритмы планирования Многоуровневые очереди с обратной связью (Multilevel Feedback Queue) Очередь 0 – Приоритет 0 Очередь 1 – Приоритет 1 Очередь 2 – Приоритет 2 Очередь 3 – Приоритет 3 RR с квантом времени 8 RR с квантом времени 16 RR с квантом времени 32 FCFS Клавиатурный ввод Дисковый I/O

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