Планирование процессов. (Тема 5)

1. планирование

ПЛАНИРОВАНИЕ
Курс лекций
«Системное программное обеспечение»
«System Software»
«Операционные системы»
для студентов специальностей АСОИ и ИИ
Павел Кочурко
доцент кафедры ИИТ, к.т.н.

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

1. Долгосрочное
1
Планирование заданий отвечает
за порождение новых процессов в
системе
2
Г
О
В
3
2. Краткосрочное,
диспетчеризация
Планирование использования
процессора отвечает за выбор
процесса из очереди готовности
3. «Среднесрочное»
Когда и какой из процессов
нужно перекачать на диск и
вернуть обратно, свопинг

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

• Справедливость
гарантировать каждому заданию или процессу определенную
часть времени использования процессора в компьютерной
системе
• Эффективность
постараться занять процессор на все 100% рабочего времени, не
позволяя ему простаивать в ожидании процессов, готовых к
исполнению
• Сокращение полного времени выполнения
T t = Tw + T x
• Сокращение времени ожидания
• Сокращение времени отклика
в интерактивных системах

4. Стратегии планирования

Планирование производится, когда:
Вынужденные ситуации
1.
2.
Текущий процесс завершился
Текущий процесс заблокирован
Невынужденные ситуации
3.
4.
Закончился квант времени,
выделенный текущему процессу
Новый процесс поступил в
очередь готовности
4
Г
Невытесняющее планирование 1 2
Вытесняющее планирование
1 2 3 4
3
4
О
В
2
1

5. Алгоритмы планирования систем пакетной обработки: FCFS

First Come First Served
П1: 10 тактов, П2: 4 такта, П3: 1 такт
П1
П2
П3
0
5
10
15
5
10
15
13
1
5
15
7
t
П3
П2
П1
0
10
14
15
t
+: простота реализации
-: зависимость от порядка поступления процессов, большое время отклика

6. Алгоритмы планирования систем пакетной обработки: SJN

Shortest Job Next
П3
П2
П1
1
5
15
0
5
10
15
7
t
+: оптимальный невытесняющий алгоритм
П1: 10 тактов, П2: 4 такта, П3: 1 такт
П1: ?? тактов, П2: ?? такта, П3: ?? такт
-: алгоритм нереализуем, поскольку априори не
известно, сколько времени нужно процессу для
выполнения

7. Алгоритмы планирования систем пакетной обработки: SRT

Shortest Remain Time
П3
П2
П1
П4
0
5
10
15
t
+: оптимальный вытесняющий алгоритм
П1: осталось 8 тактов, П4: 4 такта
П1: осталось ?? тактов, П4: ?? тактов
-: алгоритм нереализуем, поскольку априори не известно,
сколько времени осталось процессам для выполнения

8. Алгоритмы планирования интерактивных систем: RR

Round Robin
ЦПУ
1
8 2
3
7
654
Чем меньше квант
процессорного
времени,
тем лучше?
П1
П2
П3
П1
П2
П3
П1
П2
П3
П1
П2
П3
=10
10
14
15
15
11
7
15
9
5
15
9
3
13
=3
11
=2
9,7
=1
9

9. Алгоритмы планирования интерактивных систем: RR

• Чем меньше квант –
тем меньше среднее полное время выполнения
тем больше накладные расходы на переключение контекста
• При слишком больших квантах RR вырождается в FCFS
• При слишком малых квантах ОС вместо полезной
работы занимается переключением процессов

10. Приоритетное планирование

Приоритет – это число, определяющее степень
привилегированности одного процесса перед другими
• Схема с абсолютными приоритетами
Вытесняющее планирование
• Схема с относительными приоритетами
Невытесняющее планирование
• Статические приоритеты
Постоянные
• Динамические приоритеты
Изменяются в зависимости от поведения (действий) процесса
• Групповые приоритеты
Внутри групп – процессы равнозначны, циклическое планирование

11. Вопросы?

ВОПРОСЫ?
http://iit.bstu.by/ss