Архитектура операционных систем Лекция 1.3
Уровни планирования процессов
Цели планирования
Желаемые свойства алгоритмов планирования
Параметры планирования
CPU burst и I/O burst
Вытесняющее и невытесняющее планирование
Алгоритмы планирования
Алгоритмы планирования
Алгоритмы планирования
Алгоритмы планирования
Алгоритмы планирования
Алгоритмы планирования
Алгоритмы планирования
Алгоритмы планирования

Архитектура операционных систем

1. Архитектура операционных систем Лекция 1.3

2. Уровни планирования процессов

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

3. Цели планирования

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

4. Желаемые свойства алгоритмов планирования

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

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

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

6. CPU burst и I/O burst

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

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

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

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

FCFS (First Come – First Served)
Процессы
P20
P1
P02
Продолжительность CPU burst
13
1
4
13
1
готовность
исполнение
P0
готовность
готовность
исполнение
P1
исполнение
исполнение
исполнение
готовность
P2
исполнение
0
1
5
13
17
18
8 t

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

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

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

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

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

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

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

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

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

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

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

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

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

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
Г
Г
Г
Г
Г
Г
Г
Г
Г
Г
Г
Г И И И И И И
P1
14
15
16
17
18
И И
Г И И И И И
P2
P3
13
И И Г
Г
И И И
готовность
исполнение
P2013
P0
P1
P2
P3
15
English     Русский Правила