Архитектура операционных систем. Уровни планирования процессов. (Лекция 3)

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

АРХИТЕКТУРА
ОПЕРАЦИОННЫХ
СИСТЕМ
ЛЕКЦИЯ 1.3

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

УРОВНИ ПЛАНИРОВАНИЯ
ПРОЦЕССОВ
• ДОЛГОСРОЧНОЕ ПЛАНИРОВАНИЕ – ПЛАНИРОВАНИЕ
ЗАДАНИЙ.
• СРЕДНЕСРОЧНОЕ ПЛАНИРОВАНИЕ – SWAPPING.
• КРАТКОСРОЧНОЕ ПЛАНИРОВАНИЕ – ПЛАНИРОВАНИЕ
ИСПОЛЬЗОВАНИЯ ПРОЦЕССОРА.
2

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

ЦЕЛИ ПЛАНИРОВАНИЯ
3

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

ЖЕЛАЕМЫЕ СВОЙСТВА
АЛГОРИТМОВ ПЛАНИРОВАНИЯ
4

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

ПАРАМЕТРЫ ПЛАНИРОВАНИЯ
СТАТИЧЕСКИЕ ПАРАМЕТРЫ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ –
НАПРИМЕР, ПРЕДЕЛЬНЫЕ ЗНАЧЕНИЯ ЕЕ РЕСУРСОВ.
СТАТИЧЕСКИЕ ПАРАМЕТРЫ ПРОЦЕССА – КЕМ ЗАПУЩЕН,
СТЕПЕНЬ ВАЖНОСТИ, ЗАПРОШЕННОЕ ПРОЦЕССОРНОЕ ВРЕМЯ,
КАКИЕ ТРЕБУЮТСЯ РЕСУРСЫ И Т.Д.
статические
ДИНАМИЧЕСКИЕ ПАРАМЕТРЫ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ –
НАПРИМЕР, КОЛИЧЕСТВО СВОБОДНЫХ РЕСУРСОВ В ДАННЫЙ
МОМЕНТ.
ДИНАМИЧЕСКИЕ ПАРАМЕТРЫ ПРОЦЕССА – ТЕКУЩИЙ
ПРИОРИТЕТ, РАЗМЕР ЗАНИМАЕМОЙ ОПЕРАТИВНОЙ ПАМЯТИ,
ИСПОЛЬЗОВАННОЕ ПРОЦЕССОРНОЕ ВРЕМЯ И Т.Д.
динамические
5

6. CPU burst и I/O burst

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
исполнение
8
0
1
5
13
17
18
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
И И
Г И И И И И
P2
P3
13
И И Г
Г
И И И
готовность
исполнение
P2013
P0
P1
P2
P3
15
18