1727696493_Лекция4_5_Планирование_процессов

1.

Планирование
процессов
Лекция 4, 5
Чем тщательнее мы планируем свою деятельность,
тем меньше времени остается на ее осуществление.
Из анналов Госплана

2.

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

3.

3

4.

Уровни планирования
• Планирование
заданий
долгосрочное
планирование процессов
• Отвечает за порождение новых процессов в системе,
определяя
степень
мультипрограммирования,
число процессов, одновременно находящихся в
системе
• Если степень мультипрограммирования системы
постоянна, то новые процессы могут появляться
только после завершения ранее загруженных

5.

Уровни планирования
• Планирование использования процессора краткосрочное планирование процессов
• Осуществляется весьма часто, как правило, не реже
одного раза в 100 миллисекунд
• Оказывает влияние на функционирование системы
до наступления очередного аналогичного события,
т. е. в течение короткого промежутка времени

6.

Уровни планирования
• В некоторых ВС бывает выгодно временно удалить
какой-либо частично выполнившийся процесс из
оперативной памяти на диск, а позже вернуть его
обратно для дальнейшего выполнения
• Swapping (“перекачка”), в профессиональной
литературе используется транслитерация - свопинг
• Требуется дополнительный промежуточный уровень
планирования процессов — среднесрочный

7.

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

8.

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

9.

Планирование процессов
Цели планирования
1.
2.
Справедливость: гарантировать каждому
заданию или процессу некоторую часть времени
использования процессора в компьютерной
системе, не допуская ситуаций, когда процесс
одного пользователя постоянно занимает
процессор, а процесс другого пользователя
фактически не выполняется
Эффективность: постараться занять процессор
на все 100% рабочего времени, не позволяя ему
простаивать в ожидании процессов, готовых к
исполнению (в реальных ВС загрузка
процессора колеблется от 40 до 90 %)

10.

Планирование процессов
Цели планирования
3.
4.
5.
Сокращение полного времени выполнения (turnaround
time): обеспечить минимальное время между стартом
процесса или постановкой задания в очередь для
загрузки и его завершением
Сокращение времени ожидания (waiting time):
минимизировать время, которое проводят процессы в
состоянии готовность и задания в очереди для
загрузки
Сокращение времени отклика (response time):
минимизировать время, которое требуется процессу в
интерактивных системах для ответа на запрос
пользователя

11.

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

12.

Планирование процессов
Желаемые свойства алгоритмов
1.
2.
3.
4.
Предсказуемость: одно и то же задание должно
выполняться приблизительно за одно и то же время
Минимальные накладные расходы – сокращение
времени работы самого алгоритма планирования
Равномерная загрузка ресурсов ВС с предпочтением
процессов, которые будут занимать
малоиспользуемые ресурсы
Масштабируемость: алгоритмы должны сохранять
работоспособность при увеличении нагрузки

13.

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

14.

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

15.

Планирование процессов
Вытесняющее и невытесняющее
• Перевод процесса из состояния «исполнение» в состояние
«закончил исполнение»
• Перевод процесса из состояния «исполнение» в состояние
«ожидание»
Вынужденное принятие решения
• Перевод процесса из состояния «исполнение» в состояние
«готовность»
• Перевод процесса из состояния «ожидание» в состояние
«готовность»
Невынужденное принятие решения

16.

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

17.

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

18.

Алгоритмы планирования
FCFS (First Come – First Served)
Процессы
Продолжительность CPU burst
P0
13
P1
4
13 17 18
16
3
0 13 17
wt
10
3
tt
исполнение
P0
исполнение
готовность
P1
исполнение
готовность
P2
0
13
17
P2
1
18
t

19.

Алгоритмы планирования
FCFS (First Come – First Served)
Процессы
Продолжительность CPU burst
готовность
P0
P2
1
P1
4
18 5 1
8
3
5 1 0
wt
2
3
tt
исполнение
готовность
P1
исполнение
P2
0
1
5
P0
13
18
t

20.

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

21.

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

22.

Алгоритмы планирования
RR (Round Robin)
Процессы
Продолжительность CPU burst
P0
13
P1
4
P2
1
Величина кванта времени – 4
время
tt
1
5
6
7
8
9
10
P0
И И И И Г
Г
Г
Г
Г
И И И И И И И И И
P1
Г
Г
Г
Г
P2
Г
Г
Г
Г Г
18 8 9
2
11
3
3
2
wt
3
4
11
12
13
14
15
16
17
И И И И
5 4 8
2
5
3
3
Г
Г
Г И
Исполнение
P012
Очередь готовых
P021
P021
P02
18

23.

Алгоритмы планирования
RR (Round Robin)
Процессы
Продолжительность CPU burst
P0
13
P1
4
P2
1
Величина кванта времени – 1
время
tt
1
2
3
4
P0
И Г
Г
И Г
P1
Г
И Г
P2
Г
Г
18 9 3
10
3
Г
5
6
7
И Г
И Г
8
9
И Г
И Г
10
11
12
13
14
15
16
17
И И И И И И И И И
И
И
wt
5 5 2
4
3
Исполнение
P102
18
Очередь готовых
P102
P102
P102

24.

Алгоритмы планирования
SJF (Shortest Job First) невытесняющий
tt
Процессы
P0
P1
P2
P3
Продолжительность CPU burst
5
3
7
1
время
1
2
3
4
5
6
P0
Г
Г
Г
Г
И
И И
P1
P2
Г
Г
И И
Г Г
P3
И
9 4 16 1
1
7
4
2
wt
И
Г Г
4 1 9 0
1
3
4
2
Г
7
Г
8
9
10
11
12
13
14
15
16
И И
И
И И
И
И
И И
Г
Г
готовность
исполнение
P2013
P0
P1
P2
P3

25.

Алгоритмы планирования
SJF (Shortest Job First) вытесняющий
Процессы
P0
P1
P2
P3
Продолжительность CPU burst
6
2
5
5
Момент появления в очереди
0
2
6
0
время
1
2
3
4
5
6
7
8
9
10
11
12
P0
Г
Г
Г
Г
Г
Г
Г
Г
Г
Г
Г
Г И И И И И И
15
16
17
18
Г И И И И И
P2
tt
14
И И
P1
P3
13
И И Г
18 2 6 7
1
8
4
4
wt
Г
И И И
12 0 1 2
3
3
4
4
готовность
исполнение
P2013
P0
P1
P2
P3

26.

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

27.

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

28.

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

29.

Алгоритмы планирования
Приоритетное планирование невытесняющее
Процессы
P0
P1
P2
P3
Продолжительность CPU burst
6
2
5
5
Момент появления в очереди
0
2
6
0
Приоритет
4
3
2
1
время
1
2
3
4
5
6
7
8
9
10
11
12
P0
Г
Г
Г
Г
Г
Г
Г
Г
Г
Г
Г
Г И И И И И И
Г
Г
Г И И
P1
14
15
16
17
18
Г И И И И И
P2
P3
13
И И И И И
18 5 6 5
1
tt
8
4
2
12 3 1 0
wt
4
4
исполнение
P2013
готовность
P0
P1
P2
P3

30.

Алгоритмы планирования
Приоритетное планирование вытесняющее
Процессы
P0
P1
P2
P3
Продолжительность CPU burst
6
2
5
5
Момент появления в очереди
0
2
6
0
Приоритет
4
3
2
1
время
1
2
3
4
5
6
7
8
9
10
11
12
P0
Г
Г
Г
Г
Г
Г
Г
Г
Г
Г
Г
Г И И И И И И
Г
Г
Г И Г Г
Г
Г
Г
И
P1
14
15
16
17
18
И И И И И
P2
P3
13
И И И И И
18 10 5 5
1
tt
9
4
2
12 8 0 0
wt
5
4
исполнение
P2013
готовность
P0
P1
P2
P3

31.

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

32.

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

33.

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