Планирование процессов в операционной системе

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

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

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

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

6 CPU burst и I/O burst Важные динамические параметры процесса a=1 b=2 read c Ожидание окончания ввода a=a+c b print a Ожидание окончания вывода CPU burst I/O burst

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

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

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

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

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

12 Алгоритмы планирования Процессы 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 ИИИИИИИИИ

13 Алгоритмы планирования Процессы 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 И Г И Г И Г И ГИ ГИИИИ И И И ИИ

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

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