Системное программное обеспечение Лекция 3 Планирование процессов

Цели планирования 2 Рациональное использование ограниченных ресурсов. Необходимы критерии и алгоритмы.

Уровни планирования 3

4

Долгосрочное планирование 5

Краткосрочное планирование 6

Среднесрочное планирование 7

Критерии планирования 8

Требования к алгоритмам 9

Противоречивость требований 10

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

Статические параметры 12

Динамические параметры 13

Фрагмент деятельности процесса 14

Планировщик 15

Когда работает планировщик 16

Методы планирования 17

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

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

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

First-Come, First-Served (FCFS) 21

Алгоритм FCFS Процессp0p1p2 Продолжительность CPU burst Полное время выполнения t в : t в (p0)=13, t в (p1)=17, t в (p2)=18. Среднее полное время выполнения t ср в : t ср в = ( )/3 = 16.

Алгоритм FCFS Полное время выполнения t o : t в (p0)=18, t в (p1)=5, t в (p2)=1. Среднее полное время выполнения t ср в : t ср в = ( )/3 = 8, что почти в 2 раза меньше, чем при первой расстановке процессов. Время ожидания t o для процесса: t o (p0)= 5, t o (p1)= 1, t o (p2)= 0. Среднее время ожидания t o ср составит t ср в =( )/3 = 2. Это в 5 (!) раз меньше, чем в предыдущем случае. 23

Round Robin (RR) 24

Вытеснение процесса 25

RR Время p0ИИИИГГГГГИИИИИИИИИ p1ГГГГИИИИ p2ГГГГГГГГИ 26 RR c величиной кванта времени равной 4 t ср в =( )/3 = 11,6 t ср о =( )/3 = 5,6 *На производительность алгоритма RR сильно влияет величина кванта времени.

RR RR c величиной кванта времени равной 1 t ср в =( )/3 = 10 t ср о =( )/3 = 4 Примечание: при очень больших величинах кванта времени, когда каждый процесс успевает завершить свой CPU burst до возникновения прерывания по времени, алгоритм RR вырождается в алгоритм FCFS. 27 Время p0ИГГИГИГИГИИИИИИИИИ p1ГИГГИГИГИ p2ГГИ

Shortest-Job-First (SJF) 28

Невытесняющий SJF Процессp0p1p2p3 Продолжительность CPU burst время p0p0 ГГГГИИИИИ p1p1 ГИИИ p2p2 ГГГГГГГГГИИИИИИИ p3p3 И t ср в =( )/4 = 8,5 t ср о = ( )/4 = 3,5 Алгоритм SJF является оптимальным с точки зрения минимизации среднего времени ожидания среди класса невытесняющих алгоритмов.

Вытесняющий SJF 30 ПроцессВремя появления в очереди Продолжительность очередного CPU burst p0p0 06 p1p1 22 p2p2 67 p3p3 05 время p0p0 ГГГГГГГИИИ p1p1 ИИ p2p2 ГГГГ p3p3 ИИГГИИИ ИИИ ГГГИИИИИИИ t ср в =( )/4 = 11 t ср о = (16)/4 = 4 Основную сложность при реализации алгоритма SJF представляет невозможность точного знания продолжительности очередного CPU burst для исполняющихся процессов.

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

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

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

Невытесняющее приоритетное планирование SJF Процес с Время появления в очереди Продолжительнос ть очередного CPU burst Приори тет p0p0 064 p1p1 223 p2p2 672 p3p время p0p0 ГГГГГГГГГГ p1p1 ГГГИИ p2p2 ГИИИ p3p3 ИИИИИ ГГГГИИИИИИ ИИИИ

Вытесняющее приоритетное планирование SJF время p0p0 ГГГГГГГГГГ p1p1 ГГГИГГГГ p2p2 ИИИИ p3p3 ИИИИИ ГГГГИИИИИИ ГГГИ ИИИ Процес с Время появления в очереди Продолжительнос ть очередного CPU burst Приори тет p0p0 064 p1p1 223 p2p2 672 p3p3 051 В рассмотренных примерах приоритеты процессов с течением времени не изменялись. Такие приоритеты принято называть статическими. Более гибкими являются динамические приоритеты процессов, изменяющие свои значения по ходу исполнения процессов.

Алгоритм с динамическими приоритетами 36

Многоуровневые очереди 37

Многоуровневые очереди с обратной связью 38

39

Описание алгоритма 40

Обобщение 41

Заключение 42