Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Планирование процессов
Содержание
- 1. Планирование процессов
- 2. Лекция 3. Планирование процессов
- 3. Уровни планирования процессовДолгосрочное планирование – планирование заданий.Среднесрочное планирование – swapping.Краткосрочное планирование – планирование использования процессора.
- 4. Цели планированияСправедливость ЭффективностьСокращение полного времени выполнения (turnaround time)Сокращение времени ожидания (waiting time)Сокращение времени отклика (response time)
- 5. Желаемые свойства алгоритмов планированияПредсказуемостьМинимизация накладных расходов. Равномерность загрузки вычислительной системы. Масштабируемость.
- 6. Параметры планированияСтатические параметры вычислительной системы – например,
- 7. CPU burst и I/O burstВажные динамические параметры
- 8. Вытесняющее и невытесняющее планированиеПеревод процесса из состояния
- 9. Алгоритмы планированияFCFS (First Come – First Served)t1817130P0P1P2исполнениеготовностьготовностьисполнениеисполнениеисполнениеготовностьготовность1исполнение5исполнение18
- 10. Алгоритмы планированияRR (Round Robin)Процесс 1Процесс 2Процесс 3Процесс
- 11. Алгоритмы планированияОстаток времени CPU burst кванта времени:По
- 12. Алгоритмы планированияRR (Round Robin)Величина кванта времени – 4 ИИИИГГГГГГГГP0P1P2Очередь готовыхP0исполнениеP1P2P0P1P2P0ИИИИГГГГГГГГP2P0ИГP0ИИИИИИИИИ
- 13. Алгоритмы планированияRR (Round Robin)Величина кванта времени – 1 ИГГP0P1P2Очередь готовыхP0исполнениеP1P2P0P2P0P0P1ИГГP1P2P1ИГГP0P1ИГP1ИГИГИГИГИГИИИИИИИИИ
- 14. Алгоритмы планированияSJF (Shortest Job First)невытесняющийИГГГИИИГГГГГГИИИИИГГГГГИИИИИИИP0P1P2готовностьP3исполнениеP3P1P0P2
- 15. Алгоритмы планированияSJF (Shortest Job First)вытесняющийИГP0P1P2готовностьP3исполнениеP3P1P0P2ГИИИГГГГИИГГИГГИИИИИГГГГГИИИИИИ
- 16. Алгоритмы планированияτ(n) – величина n-го CPU burstT(n+1)
- 17. Алгоритмы планированияВ системе разделения времени N пользователей:
- 18. Алгоритмы планированияПриоритетное планированиеКаждому процессу процессор выделяется в
- 19. Алгоритмы планированияПриоритетное планированиеневытесняющийИГP0P1P2готовностьP3исполнениеP3P1P0P2ГИИИГГИИГГИГИИИИИГГГГГИИИИИИГГГГ
- 20. Алгоритмы планированияПриоритетное планированиевытесняющийИГP0P1P2готовностьP3исполнениеP3P1P0P2ГИИИГГИИГГИГИИИИИГГГГГИИИИИИГГГГГГГГ
- 21. Алгоритмы планированияМногоуровневые очереди(Multilevel Queue)Системные процессы приоритет 0Процессы
- 22. Алгоритмы планированияМногоуровневые очереди с обратной связью(Multilevel Feedback
- 23. Алгоритмы планированияМногоуровневые очереди с обратной связью(Multilevel Feedback
- 24. Скачать презентанцию
Лекция 3. Планирование процессов
Слайды и текст этой презентации
Слайд 3Уровни планирования процессов
Долгосрочное планирование – планирование заданий.
Среднесрочное планирование – swapping.
Краткосрочное
планирование – планирование использования процессора.
Слайд 4Цели планирования
Справедливость
Эффективность
Сокращение полного времени выполнения (turnaround time)
Сокращение времени ожидания
(waiting time)
Сокращение времени отклика (response time)
Слайд 5Желаемые свойства
алгоритмов планирования
Предсказуемость
Минимизация накладных расходов.
Равномерность загрузки вычислительной системы.
Масштабируемость.
Слайд 6Параметры планирования
Статические параметры вычислительной системы – например, предельные значения ее
ресурсов.
Статические параметры процесса – кем запущен, степень важности, запрошенное процессорное
время, какие требуются ресурсы и т.д.Динамические параметры вычислительной системы – например, количество свободных ресурсов в данный момент.
Динамические параметры процесса – текущий приоритет, размер занимаемой оперативной памяти, использованное процессорное время и т.д.
статические
динамические
Слайд 7CPU burst и I/O burst
Важные динамические параметры процесса
a=1
b=2
read c
Ожидание окончания
ввода
a=a+c∗b
print a
Ожидание окончания
вывода
CPU burst
CPU burst
I/O 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
исполнение
готовность
готовность
готовность
готовность
Процесс 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
RR
RR
RR
RR
Слайд 22Алгоритмы планирования
Многоуровневые очереди с обратной связью
(Multilevel Feedback Queue)
Очередь 0 –
Приоритет 0
Очередь 1 – Приоритет 1
Очередь 2 – Приоритет 2
Очередь
3 – Приоритет 3RR с квантом времени 8
RR с квантом времени 16
RR с квантом времени 32
FCFS
Клавиатурный ввод
Дисковый I/O
Слайд 23Алгоритмы планирования
Многоуровневые очереди с обратной связью
(Multilevel Feedback Queue)
Для полного описания
необходимо задать
- количество очередей в состоянии готовность
- алгоритм планирования между
очередями- алгоритмы планирования внутри очередей
- куда помещается родившийся процесс
- правила перевода процессов из одной очереди в другую
