L3_SO_Planificarea_Proceselor(RU) (1)

1.

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

2.

Содержание
• Уровни планирования
• Критерии планирования и требования к алгоритмам
планирования
• Параметры планирования
Вытесняющее и не вытесняющее планирование
Алгоритмы планирования
16.02.2021

3.

Уровни планирования
• Долгосрочное планирование
• Краткосрочное планирование
• Среднесрочное планирование
16.02.2021

4.

Criterii de planificare
• Справедливость – гарантировать каждому процессу определенную часть
времени использования процессора, стараясь не допустить возникновения
ситуации, когда процесс одного пользователя постоянно занимает процессор, в
то время как процесс другого пользователя фактически не начинал
выполняться.
• Эффективность – занять процессор на все 100% рабочего времени, не
позволяя ему простаивать в ожидании процессов, готовых к исполнению. В
реальных ВС загрузка процессора - от 40 до 90%.
• Сокращение полного времени выполнения ( turnaround time ) – обеспечить
минимальное время между стартом процесса и его завершением.
• Сокращение времени ожидания ( waiting time ) – сократить время, которое
проводят процессы в состоянии готовность.
• Сокращение времени отклика ( response time ) – минимизировать время,
которое требуется процессу в интерактивных системах для ответа на запрос
пользователя.
16.02.2021

5.

Параметры планирования
Статические параметры:
Статические параметры КС
Статические параметры процесса
Динамические параметры:
Динамические параметры КС
Динамические параметры процесса
16.02.2021

6.

Paрамeтры планирования
Динамические параметры процесса :
Активность любого процесса представляет собой
последовательность циклов использования ЦП и
ожидание завершения операций ввода-вывода. Период
непрерывного использования
процессора называется
CPU burst, а непрерывный период
операций ввода-вывода
называется i/o burst.
16.02.2021

7.

Вытесняющее и не вытесняющее планирование
Планировщик процессов может принимать решение о запуске
нового процесса из числа готовых к выполнению в следующих
четырех случаях:
1. Когда процесс переводится из состояния RUN в состояние
закончил выполнение.
2. Когда процесс переводится из состояния RUN в WAIT
3. Когда процесс переводится из состояния RUN в состояние
READY (например, после прерывания от taimer-a).
4. Когда процесс переводится из состояния WAIT в сост. READY
(закончилась операция i/o или произошло другое событие).
16.02.2021

8.

Вытесняющее и не вытесняющее планирование
Если SO планирует только в вынужденных ситуациях
(случаи 1, 2, 4), говорят, что это не вытесняющее
планирование
(nonpreemtive).
Если
планировщик
принимает
как
принудительные,
так
и
не
принудительные
решения,
это
называется
вытесняющим планированием (preemtive).
Термин "вытесняющее планирование" возник потому,
что исполняющийся процесс помимо своей воли может
быть вытеснен из состояния исполнение другим
процессом.
16.02.2021

9.

Алгоритмы планирования
Каждая из операций управления процессами,
выполняемых
компонентами
ОС,
основана
на
алгоритмах, которые должны отвечать следующим
условиям:
• достигать эффективности КС
• предоставить очень короткое время их выполнения
и низкое потребление системных ресурсов.
16.02.2021

10.

Алгоритмы планирования
1. Алгоритм First-Come, First-Served (FCFS)
Этот алгоритм выполняет не вытесняющее планирование:
процесс, который имеет в своем распоряжении процессор,
владеет им пока не истечет его CPU burst (время, необходимое
для выполнения). После этого из начала очереди выбирается
новый процесс для выполнения.
Процессы
p0 p1 p2
CPU burst
13 4 1
Среднее время ожидания:
(0 + 13 + 17) / 3 = 10
Среднее время выполнения :
(13 + 17 + 18) / 3 = 16
16.02.2021

11.

Алгоритмы планирования
Если те же процессы расположены по порядку p2, p1, p0:
Среднее время ожидания :
(5 + 1 + 0) / 3 = 2
Среднее время выполнения :
(18 + 5 + 1) / 3 = 8
16.02.2021

12.

Алгоритмы планирования
2. Алгоритм Round Robin (RR)
Модификацией
алгоритма
FCFS
является
алгоритм
RR,
реализованный только в режиме вытесняющего планирования.
ОС устанавливает таймер, в
течение которого выполняется
каждый процесс.
16.02.2021

13.

Алгоритмы планирования
Алгоритм Round Robin (RR) q = 4 у.е.в.
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15 16 17 18
P0
E
E
E
E
G
G
G
G
G
E
P1
G
G
G
G
E
E
E
E
P2
G
G
G
G
G
G
G
G
E
E
E
E
E
E
E
E
E
Среднее время ожидания:
(5 + 4 + 8) / 3 = 5,6 (6)
Среднее время выполнения :
(18 + 8 + 9) / 3 = 11,6 (6)
16.02.2021

14.

Алгоритмы планирования
3. Алгоритм Shortest-Job-First (SJF)
При рассмотрении алгоритмов FCFS и RR заметили,
насколько существенным для них является порядок
расположения процессов в очереди процессов, готовых к
исполнению. Если бы мы знали время следующих CPU
burst для процессов, находящихся в состоянии RUN, то
могли бы выбрать для исполнения не процесс из начала
очереди, а процесс с минимальной длительностью CPU
burst.
SJF алгоритм может быть как вытесняющим, так и не
вытесняющим.
Рассмотрим
пример
работы
не
вытесняющего алгоритма SJF.
16.02.2021

15.

Алгоритмы планирования
Процесс
p0
p1
p2 р3
CPU burst
5
3
7
1
Время
1
2
3
4
5
6
7
8
9
Р0
Г
Г
Г
Г
И
И
И
И
И
Р1
Г
И
И
И
Р2
Г
Г
Г
Г
Г
Г
Г
Г
Г
Р3
И
10
11
12
13
14
15
16
И
И
И
И
И
И
И
среднее время ожидания : (4 + 1 + 9 + 0)/4 = 3,5 е.в.
среднее время выполнения : (4 + 1 + 9 + 0)/4 = 3,5 е.в.
16.02.2021

16.

Алгоритмы планирования
Рассмотрим пример работы вытесняющего алгоритма SJF. Для этого
возьмем ряд процессов p0, p1, p2 и p3 с различными временами CPU
burst и различными моментами их появления в очереди процессов,
готовых к исполнению.
Процесс
p0
p1
p2 р3
CPU burst
6
2
7
5
Появление
1
3
7
1
1
2
3
4
5
6
7
8
Г
Г
Г
Г
Г
Г
Г
И И И И И И
Г
Г
Время
Р0
Р1
10
11
12
13
14
15
И И Г
Г
Г
Г
Г
Г
Г
17
18
19
20
И И И И И И И
И И И
среднее время ожидания : (7 + 0 + 7 + 2)/4 = 4 е.в.
среднее время выполнения : (13 + 2 + 14 + 7)/4 = 9 е.в.
16.02.2021
16
И И
Р2
Р3
9

17.

Алгоритмы планирования
Основную
сложность
при
реализации
алгоритма
SJF
представляет
невозможность
точного
знания
продолжительности очередного CPU burst для исполняющихся
процессов. В пакетных системах количество процессорного
времени, необходимое заданию для выполнения, указывает
пользователь при формировании задания. Если пользователь
укажет больше времени, чем ему нужно, он будет ждать
результата дольше, чем мог бы, так как задание будет загружено
в систему позже. Если же он укажет меньшее количество
времени, задача может не досчитаться до конца. Таким образом,
в пакетных системах решение задачи оценки времени
использования
процессора
перекладывается
на
плечи
пользователя. При краткосрочном планировании мы можем
делать только прогноз длительности следующего CPU burst,
исходя из предыстории работы процесса.
16.02.2021

18.

Алгоритмы планирования
4. Приоритетное планирование
При
приоритетном
планировании
каждому
процессу
присваивается определенное числовое значение – приоритет, в
соответствии с которым ему выделяется процессор. Процессы с
одинаковыми приоритетами планируются в порядке FCFS.
Для алгоритма SJF в качестве такого приоритета
выступает оценка продолжительности следующего CPU burst.
Чем меньше значение этой оценки, тем более высокий
приоритет имеет процесс. Для алгоритма гарантированного
планирования приоритетом служит вычисленный коэффициент
справедливости. Чем он меньше, тем больше у процесса
приоритет.
16.02.2021

19.

Алгоритмы планирования
Планирование с использованием приоритетов может быть
как вытесняющим, так и не вытесняющим. При вытесняющем
планировании
процесс
появившийся
в
исполняющийся
с
более
высоким
очереди
готовых
процессов,
процесс
с
более
низким
приоритетом,
вытесняет
приоритетом.
В
случае не вытесняющего планирования он просто становится в
начало очереди готовых процессов.
Рассмотрим
пример
использования
вытесняющего планирования.
16.02.2021
приоритетного
не

20.

Алгоритмы планирования
Процесс
p0
p1
p2 р3
СР.ВР.ОЖИД.: (14 + 3 + 1 + 0)/4 = 4.5
CPU burst
6
2
7
5
СР.ВР. ВЫПОЛН.: (20 + 5 + 8 + 5) /4 =9.5
Появление
1
3
7
1
Приоритет 4
3
2
1
Время
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15 16 17 18 19 20
Р0
Г
Г
Г
Г
Г
Г
Г
Г
Г
Г
Г
Г
Г
Г
Г
Г
Г
И
И
И
И
И
И
И
И
И
Р1
Г
Р2
Р3
16.02.2021
И
И
И
И
И
И
И
И
И
И
И

21.

Алгоритмы планирования
Иным будет предоставление процессора процессам в случае
вытесняющего приоритетного планирования.
Процесс
p0
p1
p2 р3
СР.ВР.ОЖИД.: (14 + 10 + 0 + 0)/4 = 6
CPU burst
6
2
7
5
СР.ВР. ВЫПОЛН.: (20 + 12 + 7 + 5) /4 =11
Появление
1
3
7
1
Приоритет 4
3
2
1
Время
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15 16 17 18 19 20
Р0
Г
Г
Г
Г
Г
Г
Г
Г
Г
Г
Г
Г
Г
Г
Г
Г
Г
И
Г
Г
Г
Г
Г
Г
Г
И
И
И
И
И
И
И
И
Р1
Р2
Р3
16.02.2021
И
И
И
И
И
И
И
И
И
И
И

22.

Алгоритмы планирования
В рассмотренном выше примере приоритеты процессов с течением
времени не изменялись. Такие приоритеты принято называть статическими.
Механизмы статической приоритетности легко реализовать, и они сопряжены
с относительно небольшими издержками на выбор наиболее приоритетного
процесса. Однако статические приоритеты не реагируют на изменения
ситуации в вычислительной системе, которые могут сделать желательной
корректировку порядка исполнения процессов. Более гибкими являются
динамические приоритеты процессов, изменяющие свои значения по ходу
исполнения процессов. Начальное значение динамического приоритета,
присвоенное процессу, действует в течение лишь короткого периода времени,
после чего ему назначается новое, более подходящее значение. Как правило,
изменение приоритета процессов проводится согласованно с совершением
каких-либо других операций: при рождении нового процесса, при
разблокировке или блокировании процесса, по истечении определенного
кванта времени или по завершении процесса. Примером алгоритма с
динамическими приоритетами является алгоритм SJF.
16.02.2021

23.

Алгоритмы планирования
Заключение
Одним из наиболее ограниченных ресурсов ВС является процессорное
время. Для его распределения между многочисленными процессами в системе
приходится применять процедуру планирования процессов. По степени
длительности влияния планирования на поведение ВС различают
краткосрочное, среднесрочное и долгосрочное планирование процессов.
Конкретные алгоритмы планирования процессов зависят от поставленных
целей, класса решаемых задач и опираются на статические и
динамические
параметры
процессов
и
компьютерных
систем.
Различают вытесняющий и не вытесняющий режимы планирования. При не
вытесняющем планировании исполняющийся процесс уступает процессор
другому процессу только по собственному желанию, при вытесняющем
планировании исполняющийся процесс может быть вытеснен из состояния
исполнения помимо своей воли.
16.02.2021

24.

Алгоритмы планирования
Простейшим
алгоритмом
планирования
является
не
вытесняющий алгоритм
FCFS, который, однако, может
существенно задерживать короткие процессы, не вовремя
перешедшие в состояние готовность. В системах разделения
времени широкое распространение получила вытесняющая
версия этого алгоритма – RR. Среди всех не вытесняющих
алгоритмов оптимальным с точки зрения среднего времени
ожидания процессов является алгоритм SJF.
Будучи наиболее сложными в реализации алгоритмы
приоритетного планирования обеспечивают гибкое поведение
вычислительных систем и их адаптивность к решению задач
разных классов.
16.02.2021