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

Сентябрь 1, 2022

Главная
Информатика
Основы операционных систем

Содержание

2. Лекция 3. Планирование процессов
3. Уровни планирования процессов Долгосрочное планирование – планирование заданий. Среднесрочное планирование – swapping. Краткосрочное планирование – планирование
4. Цели планирования Справедливость Эффективность Сокращение полного времени выполнения (turnaround time) Сокращение времени ожидания (waiting time) Сокращение
5. Желаемые свойства алгоритмов планирования Предсказуемость Минимизация накладных расходов. Равномерность загрузки вычислительной системы. Масштабируемость.
6. Параметры планирования Статические параметры вычислительной системы – например, предельные значения ее ресурсов. Статические параметры процесса –
7. CPU burst и I/O burst Важные динамические параметры процесса a=1 b=2 read c Ожидание окончания ввода
8. Вытесняющее и невытесняющее планирование Перевод процесса из состояния исполнение в состояние закончил исполнение Перевод процесса из
9. Алгоритмы планирования FCFS (First Come – First Served) t 18 17 13 0 P0 P1 P2
10. Алгоритмы планирования RR (Round Robin) Процесс 1 Процесс 2 Процесс 3 Процесс 4 готовность готовность готовность
11. Алгоритмы планирования Остаток времени CPU burst процесс освобождает процессор до истечения кванта; на исполнение выбираем новый
12. Алгоритмы планирования RR (Round Robin) Величина кванта времени – 4 И И И И Г Г
13. Алгоритмы планирования RR (Round Robin) Величина кванта времени – 1 И Г Г P0 P1 P2
14. Алгоритмы планирования SJF (Shortest Job First) невытесняющий И Г Г Г И И И Г Г
15. Алгоритмы планирования SJF (Shortest Job First) вытесняющий И Г P0 P1 P2 готовность P3 исполнение P3
16. Алгоритмы планирования τ(n) – величина n-го CPU burst T(n+1) – предсказание для n+1-го CPU burst α
17. Алгоритмы планирования В системе разделения времени N пользователей: Ti – время нахождения i-го пользователя в системе
18. Алгоритмы планирования Приоритетное планирование Каждому процессу процессор выделяется в соответствии с приписанным к нему числовым значением
19. Алгоритмы планирования Приоритетное планирование невытесняющий И Г P0 P1 P2 готовность P3 исполнение P3 P1 P0
20. Алгоритмы планирования Приоритетное планирование вытесняющий И Г P0 P1 P2 готовность P3 исполнение P3 P1 P0
21. Алгоритмы планирования Многоуровневые очереди (Multilevel Queue) Системные процессы приоритет 0 Процессы ректората приоритет 1 Процессы преподавателей
22. Алгоритмы планирования Многоуровневые очереди с обратной связью (Multilevel Feedback Queue) Очередь 0 – Приоритет 0 Очередь
24. Скачать презентацию

Слайд 2

Лекция 3. Планирование процессов

Слайд 3

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

– планирование использования процессора.

Слайд 4

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

time)
Сокращение времени отклика (response time)

Слайд 5

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

Слайд 6

Параметры планирования
Статические параметры вычислительной системы – например, предельные значения ее ресурсов.
Статические

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

статические

динамические

Слайд 7

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

a
Ожидание окончания вывода

CPU burst

I/O burst

Слайд 8

Вытесняющее и невытесняющее планирование
Перевод процесса из состояния исполнение в состояние закончил

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

Вынужденное принятие решения

Невынужденное принятие решения

Слайд 9

Алгоритмы планирования
FCFS (First Come – First Served)
t
18
17
13
0
P0
P1
P2
исполнение
готовность
готовность
исполнение
исполнение
исполнение
готовность
готовность
1
исполнение
5
исполнение
18

Слайд 10

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

Процесс 1

готовность

Процесс 3

Процесс 2

исполнение

готовность

Процесс 4

готовность

Процесс 3

Процесс 1

Процесс 2

исполнение

Процесс 1

Процесс 2

готовность

Слайд 11

Алгоритмы планирования
Остаток времени CPU burst <= кванта времени:
процесс освобождает процессор до

истечения кванта;
на исполнение выбираем новый процесс из начала очереди готовых;
Остаток времени CPU burst >= кванта времени:
По окончании кванта процесс помещается в конец очереди готовых к исполнению процессов;
на исполнение выбираем новый процесс из начала очереди готовых.

RR (Round Robin)

Слайд 12

Алгоритмы планирования
RR (Round Robin)
Величина кванта времени – 4
И
И
И
И
Г
Г
Г
Г
Г
Г
Г
Г
P0
P1
P2
Очередь готовых
P0
исполнение
P1
P2
P0
P1
P2
P0
И
И
И
И
Г
Г
Г
Г
Г
Г
Г
Г
P2
P0
И
Г
P0
И
И
И
И
И
И
И
И
И

Слайд 13

Алгоритмы планирования
RR (Round Robin)
Величина кванта времени – 1
И
Г
Г
P0
P1
P2
Очередь готовых
P0
исполнение
P1
P2
P0
P2
P0
P0
P1
И
Г
Г
P1
P2
P1
И
Г
Г
P0
P1
И
Г
P1
И
Г
И
Г
И
Г
И
Г
И
Г
И
И
И
И
И
И
И
И
И

Слайд 14

Алгоритмы планирования
SJF (Shortest Job First)
невытесняющий
И
Г
Г
Г
И
И
И
Г
Г
Г
Г
Г
Г
И
И
И
И
И
Г
Г
Г
Г
Г
И
И
И
И
И
И
И
P0
P1
P2
готовность
P3
исполнение
P3
P1
P0
P2

Слайд 15

Алгоритмы планирования
SJF (Shortest Job First)
вытесняющий
И
Г
P0
P1
P2
готовность
P3
исполнение
P3
P1
P0
P2
Г
И
И
И
Г
Г
Г
Г
И
И
Г
Г
И
Г
Г
И
И
И
И
И
Г
Г
Г
Г
Г
И
И
И
И
И
И

Слайд 16

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

SJF (Shortest Job First)

приближение

Слайд 17

Алгоритмы планирования
В системе разделения времени N пользователей:
Ti – время нахождения

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

Гарантированное планирование

– пользователь обделен

– пользователю благоволят

Слайд 18

Алгоритмы планирования
Приоритетное планирование
Каждому процессу процессор выделяется в соответствии с приписанным к

нему числовым значением - приоритетом

Параметры для назначения приоритета бывают:
-внешние
-внутренние

Политика изменения приоритета:
-статический приоритет
-динамический приоритет

Слайд 19

Алгоритмы планирования
Приоритетное планирование
невытесняющий
И
Г
P0
P1
P2
готовность
P3
исполнение
P3
P1
P0
P2
Г
И
И
И
Г
Г
И
И
Г
Г
И
Г
И
И
И
И
И
Г
Г
Г
Г
Г
И
И
И
И
И
И
Г
Г
Г
Г

Слайд 20

Алгоритмы планирования
Приоритетное планирование
вытесняющий
И
Г
P0
P1
P2
готовность
P3
исполнение
P3
P1
P0
P2
Г
И
И
И
Г
Г
И
И
Г
Г
И
Г
И
И
И
И
И
Г
Г
Г
Г
Г
И
И
И
И
И
И
Г
Г
Г
Г
Г
Г
Г
Г

Слайд 21

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

приоритет 2

Фоновые процессы приоритет 3

Процессы студентов приоритет 4

FCFS

Слайд 22

Алгоритмы планирования
Многоуровневые очереди с обратной связью
(Multilevel Feedback Queue)
Очередь 0 – Приоритет

Очередь 1 – Приоритет 1

Очередь 2 – Приоритет 2

Очередь 3 – Приоритет 3

RR с квантом времени 8

RR с квантом времени 16

RR с квантом времени 32

FCFS

Клавиатурный ввод

Дисковый I/O

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

Содержание

Лекция 3. Планирование процессов

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

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

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

Параметры планированияСтатические параметры вычислительной системы – например, предельные значения ее ресурсов.Статические

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

Вытесняющее и невытесняющее планированиеПеревод процесса из состояния исполнение в состояние закончил

Алгоритмы планированияFCFS (First Come – First Served)t1817130P0P1P2исполнениеготовностьготовностьисполнениеисполнениеисполнениеготовностьготовность1исполнение5исполнение18

Алгоритмы планированияОстаток времени CPU burst <= кванта времени:процесс освобождает процессор до

Алгоритмы планированияRR (Round Robin)Величина кванта времени – 4 ИИИИГГГГГГГГP0P1P2Очередь готовыхP0исполнениеP1P2P0P1P2P0ИИИИГГГГГГГГP2P0ИГP0ИИИИИИИИИ

Алгоритмы планированияRR (Round Robin)Величина кванта времени – 1 ИГГP0P1P2Очередь готовыхP0исполнениеP1P2P0P2P0P0P1ИГГP1P2P1ИГГP0P1ИГP1ИГИГИГИГИГИИИИИИИИИ

Алгоритмы планированияSJF (Shortest Job First)невытесняющийИГГГИИИГГГГГГИИИИИГГГГГИИИИИИИP0P1P2готовностьP3исполнениеP3P1P0P2

Алгоритмы планированияSJF (Shortest Job First)вытесняющийИГP0P1P2готовностьP3исполнениеP3P1P0P2ГИИИГГГГИИГГИГГИИИИИГГГГГИИИИИИ

Алгоритмы планированияτ(n) – величина n-го CPU burstT(n+1) – предсказание для n+1-го

Алгоритмы планированияВ системе разделения времени N пользователей: Ti – время нахождения

Алгоритмы планированияПриоритетное планированиеКаждому процессу процессор выделяется в соответствии с приписанным к

Алгоритмы планированияПриоритетное планированиеневытесняющийИГP0P1P2готовностьP3исполнениеP3P1P0P2ГИИИГГИИГГИГИИИИИГГГГГИИИИИИГГГГ

Алгоритмы планированияПриоритетное планированиевытесняющийИГP0P1P2готовностьP3исполнениеP3P1P0P2ГИИИГГИИГГИГИИИИИГГГГГИИИИИИГГГГГГГГ

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

Алгоритмы планированияМногоуровневые очереди с обратной связью(Multilevel Feedback Queue)Очередь 0 – Приоритет

Похожие презентации

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

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

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

Параметры планирования
Статические параметры вычислительной системы – например, предельные значения ее ресурсов.
Статические

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

Вытесняющее и невытесняющее планирование
Перевод процесса из состояния исполнение в состояние закончил

Алгоритмы планирования
Остаток времени CPU burst <= кванта времени:
процесс освобождает процессор до

Алгоритмы планирования
SJF (Shortest Job First)
невытесняющий
И
Г
Г
Г
И
И
И
Г
Г
Г
Г
Г
Г
И
И
И
И
И
Г
Г
Г
Г
Г
И
И
И
И
И
И
И
P0
P1
P2
готовность
P3
исполнение
P3
P1
P0
P2

Алгоритмы планирования
SJF (Shortest Job First)
вытесняющий
И
Г
P0
P1
P2
готовность
P3
исполнение
P3
P1
P0
P2
Г
И
И
И
Г
Г
Г
Г
И
И
Г
Г
И
Г
Г
И
И
И
И
И
Г
Г
Г
Г
Г
И
И
И
И
И
И

Алгоритмы планирования
τ(n) – величина n-го CPU burst
T(n+1) – предсказание для n+1-го

Алгоритмы планирования
В системе разделения времени N пользователей:
Ti – время нахождения

Алгоритмы планирования
Приоритетное планирование
Каждому процессу процессор выделяется в соответствии с приписанным к

Алгоритмы планирования
Приоритетное планирование
невытесняющий
И
Г
P0
P1
P2
готовность
P3
исполнение
P3
P1
P0
P2
Г
И
И
И
Г
Г
И
И
Г
Г
И
Г
И
И
И
И
И
Г
Г
Г
Г
Г
И
И
И
И
И
И
Г
Г
Г
Г

Алгоритмы планирования
Приоритетное планирование
вытесняющий
И
Г
P0
P1
P2
готовность
P3
исполнение
P3
P1
P0
P2
Г
И
И
И
Г
Г
И
И
Г
Г
И
Г
И
И
И
И
И
Г
Г
Г
Г
Г
И
И
И
И
И
И
Г
Г
Г
Г
Г
Г
Г
Г

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

Алгоритмы планирования
Многоуровневые очереди с обратной связью
(Multilevel Feedback Queue)
Очередь 0 – Приоритет