Основы операционных систем

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
P0
5
время
1
2
3
4
5
6
P0
Г
Г
Г
Г
И
И И
P1
P2
Г
Г
И И
Г Г
P3
И
И
Г Г
Г
7
Г
8
9
P1
3
P3
1
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