Планирование процессов презентация кратко

Обновлено: 30.06.2024

Презентация на тему: " Основы операционных систем. Тема 3. Планирование процессов." — Транскрипт:

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

2 Тема 3. Планирование процессов

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

4 Цели планирования Справедливость Справедливость Эффективность Эффективность Сокращение полного времени выполнения (turnaround time) Сокращение полного времени выполнения (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 Вытесняющее и невытесняющее планирование 1.Перевод процесса из состояния исполнение в состояние закончил исполнение 2.Перевод процесса из состояния исполнение в состояние ожидание Принятие только вынужденных решений – невытесняющее планирование 3.Перевод процесса из состояния исполнение в состояние готовность 4.Перевод процесса из состояния ожидание в состояние готовность Принятие вынужденных и невынужденных решений – вытесняющее планирование Вынужденное принятие решения Невынужденное принятие решения

9 Алгоритмы планирования Процессы P0P0P0P0 P1P1P1P1 P2P2P2P2 Продолжительность CPU burst 1341 FCFS (First Come – First Served) t P0P0P0P0 P1P1P1P1 P2P2P2P2 исполнение готовность готовность исполнение исполнениеПроцессы P2P2P2P2 P1P1P1P1 P0P0P0P0 Продолжительность CPU burst 1413 исполнение готовность готовность 1 исполнение 5 исполнение 18

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

11 Алгоритмы планирования Остаток времени CPU burst = кванта времени: –По окончании кванта процесс помещается в конец очереди готовых к исполнению процессов; –на исполнение выбираем новый процесс из начала очереди готовых. RR (Round Robin)

12 Алгоритмы планирования Процессы P0P0P0P0 P1P1P1P1 P2P2P2P2 Продолжительность CPU burst 1341 RR (Round Robin) время P0P0P0P0 P1P1P1P1 P2P2P2P2 Величина кванта времени – 4 ИИИИ ГГ ГГ ГГГ Г P0P0P0P0 P1P1P1P1 P2P2P2P2 Очередь готовых P0P0P0P0 исполнение P1P1P1P1 P2P2P2P2 P0P0P0P0 P1P1P1P1 P2P2P2P2 P0P0P0P0 ИИИИ ГГГГ ГГГГ P2P2P2P2 P0P0P0P0 И Г P0P0P0P0 ИИИИИИИИИ

13 Алгоритмы планирования Процессы P0P0P0P0 P1P1P1P1 P2P2P2P2 Продолжительность CPU burst 1341 RR (Round Robin) время P0P0P0P0 P1P1P1P1 P2P2P2P2 Величина кванта времени – 1 И Г Г P0P0P0P0 P1P1P1P1 P2P2P2P2 Очередь готовых P0P0P0P0 исполнение P1P1P1P1 P2P2P2P2 P0P0P0P0 P2P2P2P2 P0P0P0P0 P0P0P0P0 P1P1P1P1 И Г Г P1P1P1P1 P2P2P2P2 P1P1P1P1 И Г Г P0P0P0P0 P1P1P1P1 И Г P1P1P1P1 И Г И Г И Г И ГИ ГИИИИ И И И ИИ

14 Алгоритмы планирования SJF (Shortest Job First) ПроцессыP0P0 P1P1 P2P2 P3P3 Продолжительность CPU burst 5371 невытесняющий время P0P0 P1P1 P2P2 P3P3 И Г Г Г ИИИ ГГГ ГГГИИИИИ ГГ Г ГГ И ИИИИИИ P0P0P0P0 P1P1P1P1 P2P2P2P2 готовность P3P3P3P3 исполнение P3P3P3P3 P1P1P1P1 P0P0P0P0 P2P2P2P2

15 Алгоритмы планирования ПроцессыP0P0 P1P1 P2P2 P3P3 Продолжительность CPU burst6255 Момент появления в очереди0260 SJF (Shortest Job First) вытесняющий И Г P0P0P0P0 P1P1P1P1 P2P2P2P2 готовность P3P3P3P3 исполнение P3P3P3P3 P1P1P1P1 P0P0P0P0 P2P2P2P2 время P0P0 P1P1 P2P2 P3P3 Г И И И ГГ ГГИИ ГГ И Г ГИИИИИ ГГГГГИИИИИИ

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 пользователей: T i – время нахождения i-го пользователя в системе τ i – суммарное процессорное время процессов i-го пользователя τ i T i /N τ i T i /N (τ i N) / T i – коэффициент справедливости. На исполнение выбираются готовые процессы пользователя с наименьшим коэффициентом справедливости Гарантированное планирование – пользователь обделен – пользователю благоволят

18 Алгоритмы планирования Приоритетное планирование Каждому процессу процессор выделяется в соответствии с приписанным к нему числовым значением - приоритетом Параметры для назначения приоритета бывают: -внешние-внутренние Политика изменения приоритета: -статический приоритет -динамический приоритет

19 Алгоритмы планирования время P0P0 P1P1 P2P2 P3P3 Приоритетное планирование невытесняющий И Г P0P0P0P0 P1P1P1P1 P2P2P2P2 готовность P3P3P3P3 исполнение P3P3P3P3 P1P1P1P1 P0P0P0P0 P2P2P2P2 Г И И И ГГ И И ГГ И Г ИИИИИ ГГГГГИИИИИИ ПроцессыP0P1P2P3 Продолжительность CPU burst6255 Момент появления в очереди0260 Приоритет4321 ГГ Г Г

20 Алгоритмы планирования время P0P0 P1P1 P2P2 P3P3 Приоритетное планирование вытесняющий И Г P0P0P0P0 P1P1P1P1 P2P2P2P2 готовность P3P3P3P3 исполнение P3P3P3P3 P1P1P1P1 P0P0P0P0 P2P2P2P2 Г И И И ГГ И И ГГ И Г ИИИИИ ГГГГГИИИИИИ ПроцессыP0P1P2P3 Продолжительность CPU burst6255 Момент появления в очереди0260 Приоритет4321 ГГ ГГГ ГГ Г

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

22 Алгоритмы планирования Многоуровневые очереди с обратной связью (Multilevel Feedback Queue) Очередь 0 – Приоритет 0 Очередь 1 – Приоритет 1 Очередь 2 – Приоритет 2 Очередь 3 – Приоритет 3 RR с квантом времени 8 RR с квантом времени 16 RR с квантом времени 32 FCFS Клавиатурный ввод Дисковый I/O

23 Алгоритмы планирования Многоуровневые очереди с обратной связью (Multilevel Feedback Queue) Для полного описания необходимо задать - количество очередей в состоянии готовность - алгоритм планирования между очередями - алгоритмы планирования внутри очередей - куда помещается родившийся процесс - правила перевода процессов из одной очереди в другую

Переключения контекста это не есть операция
планирования, это техническая операция
Происходит прерывание
Поток вызывает исключение или ловушку
(trap)
После этого выбирается другой поток
Т.е. в процессе переключения контекста
нужно четко выбрать, кому передать
управление.
Уже был затронут вопрос об очереди готовых
процессов. Решение о том, кому дать
следующий квант времени процессора
определяет планирование

3. Планирование

Процесс выбора – кто будет
исполняться следующим и как
долго это будет исполняться
называется планированием
процессов в ОС.
Не путать с переключением
контекста, что является просто
механизмом передачи управления.

4. Классы планировщиков Пакетный

1) Пакетный – ориентирован на
длительные задачи, которые
требуют больших вычислительных
ресурсов, где не требуется частое
прерывание. Т.е. подразумевают
обработку больших задач
большими пакетами, не
ограничения на время выполнения.

5. Классы планировщиков Интерактивный

2) Интерактивный – ориентирован на
снижение времени отклика, т.е. чтобы
система казалась”отзывчивой”. Обычные
абонентские системы на ПК – это
интерактивные системы, когда в ответ на
действие пользователя (например
перемещение мыши) ОС что-то делает. И
всегда пользователю хочется, чтобы этот
ответ происходил как можно быстрее.
Главное чтобы на поступающий в систему
запрос был получен максимально быстро
ответ. Запрос – это любое
взаимодействие с компьютером.

6. Классы планировщиков реального времени

3) Реального времени –
специализированные класс,
ориентированный на дедлайн –
предельный срок завершения какой-либо
работы.
Главное, чтобы определенное действие
завершалось к определенному сроку, это
понятие называется дедлайн.
Поступающий запрос должен быть
обработан не более, чем в определенный
промежуток времени.
Классический пример СРВ – управление
ядерным реактором, в котором
превышение времени отклика приведет к
аварийной ситуации.

7. Уровни планирования

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

8. Уровни планирования

Основной задачей планирования процессов в ОС
является обеспечение высокой производительности
ОС.
Существуют разные метрики, которыми оценивается эта
производительность.
Эти метрики зачастую противоречивы.
Что концептуально требуется при проектировании
планировщика ОС?
-Максимизировать использование ЦП (чтобы он
максимально работал на задачах)
-Максимизировать пропускную способность(число
выполненных запросов в единицу времени)
-Минимизировать среднее время отклика (среднее
время от подачи запроса до завершения обработки
ответа)
-Минимизировать среднее время ожидания (среднее
время от подачи запроса до начала его выполнения)
-Минимизировать энергии (джоулей на инструкцию)

9. Метрики планирования. Пример

ta- время поступления процесса (когда процесс становится готовым к
выполнению)
Tw – время ожидания (которое тратит процесс в очереди на выполнение)
Ts – время выполнения ЦП
Tr – время оборота (общее время на ожидание ивыполнение)
ta
Поступление
Очередь
готовых
Процесс 5 задерживается
предыдущими
процессами,
запланированными к
выполнению
5 прибыл
6 прибыл
1
2
3
Выполнение
4
5 выполняется
На ЦП
Tw
Ts
Tr = Tw+Ts
время

10. Метрики планирования. Пример

На схеме 5 и 6 процессы поступили в
очередь готовых процессов.
5 задержался из-за 1-4 процесов. Для
пятого процесса Tw – время ожидания
Ts – время выполнения ЦП. Время
оборота это время от момента его
поступления до момента, когда
завершилось его выполнение Tr=Tw+Ts

11. Метрики планирования Как выбрать какой процесс будет работать дольше?

FIFO- классика – первым пришел,
первым ушел
Кратчайшая работа следующей,
т.е. следующей выбирается работа,
которая требует наименьшего
времени завершения
Round-robin
Многоуровневая очередь
Многоуровневая очередь с
обратной связью

12. FIFO

В данном случае мы будем его понимать
как невытесняющую многозадачность
Процессы планируются по мере их
поступления
Время выполнения не учитывается
(никак совсем)
Другие процесс с меньшим временем Tr
вынуждены ждать (снижается
отзывчивость системы)
Когда процесс переходит в состояние
готовности он перемещается в конец
очереди

13. Пример FIFO

Допустим есть 3 процесса, которые пребывают в
одно и тоже время t=0 в порядке P1,P2,P3.
У каждого из процессов существует время, которое
ему нужно для выполнения части задачи. Эту
часть задачи, которую ему необходимо
выполнить назовем английским словом Burst. У
трех процессов она разная.
Burst(Р1)=24 (усл.ед.времени)
Burst(Р2)=3
Burst(Р3)=3
Тогда Время ожидания
Wait(P1)=0
Wait(P2)=24
Wait(P3)=27
Среднее время ожидания = 17

14. Пример FIFO

Если эти 3 поступившие процесса запланировать по
другому, можно сильно снизить время отклика
системы.
Допустим процессы поступают в порядке Р2,Р3,Р1
Тогда время ожидания
Р2=0,
Р3=3,
Р1=6
Среднее время ожидания =3 - Оно резко снизилось за
счет того, что мы изменили порядок работы
процессов, поступивших в одно и тоже время.
За данным простым примером скрыта вся мощь и
важность алгоритмов планирования в ОС.

15. Обобщения по FIFO

Он больше других подходит для
длительных, требовательных к
времени ЦП процессов;
Плохое использование ЦП и устройств
вв/выв
Среднее время ожидание сильно
варьируется

16. Кратчайшая работа следующей

Условимся, имеется в виду
невытесняющая политика
планирования – сколько квант
времени запрашивает процесс,
столько ему и выделяется.
Суть процесса - следующим
запланировать тот процесс, который
требует наименьшего времени для
своего выполнения, т.е. процесс
имеющий самое короткое время
обработки

17. Кратчайшая работа следующей Сложности

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

18. Кратчайшая работа следующей вытесняющий вариант

Существует вытесняющий вариант метода кратчайшей работы
следующего.
Сортировка осуществляется по времени, которое нужно
процессу для завершения своей части задачи. Если он
вытесняется в процессе выполнения, то время, которое у
него осталось называется остаточным.
По остаточному времени осуществляется сортировка и
принимается решение, какой процесс будет выполняться
следующим.
Соответственно те процессы, которые выполняются на ЦП
вытесняются тем процессом, который близкий к
завершению, чтобы отработать его и распрощаться с ним.
А те процессы, которым еще долго работать, оставить на
потом и заняться ими “в плотную”. Логика в этом есть

19. Кратчайшая работа следующей обощение

Процессы, уже выполняющиеся на
ЦП вытесняются самым близким к
завершению заданием
Меньше общее время оборота
процесса
Меньше время ожидания ЦП

20. Планирование с приоритетами

Тот же алгоритм кратчайшей работы
следующей можно представить, как
планирование с приоритетом, где приоритет
– наименьшее время работы.
Суть – каждому процессу сопоставляется
некоторое число, которое характеризует,
определяет приоритет этого процесса. Чем
меньше это число, тем выше приоритет.
Проблема старвации – это проблема
“зависания”, “голодания” – если процессу с
высоким приоритетом приспичит выполнить
очень длительную работу, то все остальные
процессы будут “висеть” и ждать

21. Планирование с приоритетами

Время ЦП выделяется процессу с
наивысшим приоритетом (вытесняющим или
невытесняющим) Процесс с низким
приоритетом может вообще никогда не
выполниться, до него не дойдет очередь.
Старвация – ее можно представить как всех
стоящих в очереди и кто
привилегированный лезет вне очереди.
Проявляется в алгоритме КРС
Низкоприоритетные запросы могут никогда
не выполниться.

22. Планирование с приоритетами

23. Round-robin

Данный алгоритм планирования обозначает
циклический алгоритм с вытесняющим планированием.
Каждый процесс получает фиксированный квант
процессорного времени (фиксированную единицу
процессорного времени)
После истечения кванта времени процесс
принудительно вытесняется и помещается в очередь
готовых к выполнению.
Процесс всегда планируются в том же порядке и
каждый процесс получает одинаковый квант времени
Не сложно подсчитать: если квант времени равен q и
n-процессов в очереди, то каждый получит 1/n
времени ЦП, кусками максимум по q
Никакой из процессов не ожидает больше, чем
(n-1)*q единиц времени

24. Производительность Round-robin

Если q большое(стремиться к ∞), то RR
перерождается в алгоритм FIFO
Если q малое (но не стремится к 0, иначе
ПК будет только переключать процессы
и больше не выполнять вообще ничего),
то все хорошо
Нет старвации
Появляется высокая отзывчивость
системы
Равное распределение времени
Если q меньше, чем время,
затрачиваемое на переключение
контекста, тогда диспетчер будет
неэффективным.

25. Недостаток Round-robin

26. Многоуровневые очереди

27. Многоуровневые очереди

28. Многоуровневая очередь с обратной связью

29. Многоуровневая очередь с обратной связью

Планировщик определяется с
многими параметрами:
Числом очередей
Алгоритмами планирования в
каждой очереди
Методом, используемым для
определения принадлежности
процесса к той или иной очереди

30. Многоуровневая очередь с обратной связью. Пример

Есть 3 очереди:
Q0 –RR с квантом времени t=16мс
Q1 –RR с квантом времени t=32мс
Q2 –FIFO
Планирование:
Новый процесс помещается в конец первой очереди Q0
Когда процесс из этой очереди получает ЦП, то
выделяется квант времени t=16мс
Если процесс выполняется дольше, не вернул
управление ОС, то он принудительно вытесняется и
помещается в конец очереди Q1
В очереди Q1
Когда процесс из этой очереди получает ЦП, то
выделяется квант времени t=32мс
Если процесс выполняется дольше, то он
принудительно вытесняется и помещается в конец
очереди Q2 и выполняется по FIFO пока не закончится

Слайды и текст этой презентации

Основные понятия планирования

Планирование - обеспечение поочередного доступа процессов к одному процессору.
Планировщик - отвечающая за это часть ОС.
Алгоритм планирования - используемый алгоритм для планирования.

Основные понятия планирования

Ситуации, когда необходимо планирование:
Когда создается процесс
Когда процесс завершает работу
Когда процесс блокируется на операции ввода/вывода, семафоре, и т.д.
При прерывании ввода/вывода.

Основные понятия планирования

Виды систем:
Системы пакетной обработки - могут использовать неприоритетный и приоритетный алгоритм
Интерактивные системы - могут использовать только приоритетный алгоритм, нельзя допустить чтобы один процесс занял надолго процессор
Системы реального времени - могут использовать неприоритетный и приоритетный алгоритм

Задачи алгоритмов планирования

Для всех систем
Справедливость - каждому процессу справедливую долю процессорного времени
Контроль над выполнением принятой политики
Баланс - поддержка занятости всех частей системы (например: чтобы были заняты процессор и устройства ввода/вывода)

Задачи алгоритмов планирования

Системы пакетной обработки
Пропускная способность - количество задач в час
Оборотное время - минимизация времени на ожидание обслуживания и обработку задач.
Использование процессора - чтобы процессор всегда был занят.

Задачи алгоритмов планирования

Интерактивные системы
Время отклика - быстрая реакция на запросы
Соразмерность - выполнение ожиданий пользователя

Системы реального времени
Окончание работы к сроку - предотвращение потери данных
Предсказуемость -

Основные понятия планирования

Алгоритм планирования без переключений (неприоритетный) - не требует прерывание по аппаратному таймеру, процесс останавливается только когда блокируется или завершает работу.

Основные понятия планирования

Алгоритм планирования с переключениями (приоритетный) - требует прерывание по аппаратному таймеру, процесс работает только отведенный период времени, после этого он приостанавливается по таймеру, чтобы передать управление планировщику.

Таймер – позволяет отсчитывать время выполнения процесса в процессоре и регулировать загрузку процессора
Переключение – позволяет подавать сигналы ядру на приостановку / возобновление процесса с переключением контекста
Приоритеты – позволяют установить порядок переключения процессов в зависимости от различных факторов выполнения процессов

Планирование в системах пакетной обработки

"Первый пришел - первым обслужен" (FIFO - First In Fist Out)
процессор передается тому процессу, который раньше всех других его запросил.
среднее время ожидания для стратегии FIFO часто весьма велико и зависит от порядка поступления процессов в очередь готовых процессов.

Пусть три процесса попадают в очередь одновременно в момент 0 и имеют следующие значения времени последующего обслуживания на ЦП
Вариант 1: П1 (24 мс), П2 (3 мс), П2(3 мс)
Вариант 2: П1 (3 мс), П2 (3 мс), П2(24 мс)

Недостатки:
Процесс, ограниченный возможностями процессора может затормозить более быстрые процессы, ограниченные устройствами ввода/вывода.

Кратчайшая задача – первая (SJF – Shortest Job First)

Пусть 4 процесса попадают в очередь одновременно в момент 0 имеют следующие значения времени последующего обслуживания на ЦП: П1 (6 мс), П2 (8 мс), П3 (7 мс), П4 (3 мс)

Кратчайшая задача – первая (SJF – Shortest Job First)

Преимущества:
Уменьшение оборотного времени
Справедливость

Недостатки:
Длинный процесс, занявший процессор, не пустит более новые короткие процессы, которые пришли позже.

Наименьшее оставшееся время выполнения (SRT – Shortest Remaining Time)

Аналог SJF, но с переключениями.

Если приходит новый процесс, его полное время выполнения сравнивается с оставшимся временем выполнения текущего процесса и выполняется тот процесс, которому осталось наименьшее время выполнения

Планирование в интерактивных системах

Каждому процессу предоставляется квант времени процессора.
Когда квант заканчивается процесс переводится планировщиком в конец очереди.
При блокировке процессор выпадает из очереди
Пример:
П1 (24 мс), П2 (3 мс), П3 (3 мс); q = 4 мс

Недостатки:
При малом кванте - частые переключения, в результате уменьшение производительности
При большом кванте - редкие переключения, в результате происходит увеличение времени ответа на запрос (приближается к FIFO).

Каждому процессу присваивается приоритет, и управление передается процессу с самым высоким приоритетом
Приоритет может быть динамический и статический.

Динамический приоритет может устанавливаться следующим образом:

где Т- часть использованного кванта

Например, если T = 1/50, то приоритет 50,
если использован весь квант, то приоритет 1.

Часто процессы объединяют по приоритетам в группы, и используют
среди групп - приоритетное планирование
внутри группы - циклическое планирование

Методы разделения процессов на группы
Группы с разным квантом времени
Группы с разным назначением процессов

Группы с разным квантом времени

Процесс либо заканчивает работу, либо переходит в другую группу

Группы с разным назначением процессов

Процесс, отвечающий на запрос, переходит в группу с наивысшим приоритетом

Планирование в интерактивных системах

Гарантированное планирование
В системе с n-процессами, каждому процессу будет предоставлено 1/n времени процессора.
Справедливое планирование
Процессорное время распределяется среди пользователей, а не процессов.

Планирование в интерактивных системах

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

Планирование в системах реального времени

Системы реального времени делятся на:
жесткие (жесткие сроки для каждой задачи) - управление движением
гибкие (нарушение временного графика не желательны, но допустимы) - управление видео и аудио

Планирование в системах реального времени

Внешние события, на которые система должна реагировать, делятся:
периодические - потоковое видео и аудио
непериодические (непредсказуемые) - сигнал о пожаре

Планирование в системах реального времени

Чтобы систему реального времени можно было планировать, нужно чтобы выполнялось условие:

m - число периодических событий
i - номер события
P(i) - период поступления события
T(i) - время, которое уходит на обработку события
Перегруженная система реального времени является непланируемой

Общее планирование реального времени

Каждый процесс борется за процессор со своим заданием и графиком его выполнения.

Общее планирование реального времени

Планировщик должен знать:
Частоту , с которой должен работать процесс
объем работ, который ему предстоит выполнить
ближайший срок выполнения очередной порции задания

Общее планирование реального времени

Пример: имеются 3 периодических процесса.
Процесс А запускается каждые 30мс, обработка - 10мс
Процесс В частота = 25 (т.е. каждые 40мс), обработка - 15мс
Процесс С частота =20 (т.е. каждые 50мс), обработка кадра 5мс
10/30+15/40+5/50=0.808

Общее планирование реального времени

Различают 2 алгоритма планирования в системах реального времени:
Статический алгоритм планирования RMS (Rate Monotonic Scheduling) –
Процессы выполняются по приоритету
Приоритет пропорционален частоте
Динамический алгоритм планирования EDF (Earliest Deadline First)
Наибольший приоритет выставляется процессу, у которого осталось наименьшее время выполнения

Алгоритм планирования RMS

Процессы должны удовлетворять условиям:
Процесс должен быть завершен за время его периода
Один процесс не должен зависеть от другого
Каждому процессу требуется одинаковое процессорное время на каждом интервале
У непериодических процессов нет жестких сроков
Прерывание процесса происходит мгновенно

Слайд 1

Слайд 2

Одной из основных подсистем мультипрограммной ОС является подсистема управления процессами и потоками, которая занимается их созданием и уничтожением, поддерживает взаимодействие между ними, а также распределяет процессорное время между несколькими одновременно существующими в системе процессами и потоками. Подсистема управления процессами и потоками ответственна за обеспечение процессов необходимыми ресурсами. ОС поддерживает в памяти специальные информационные структуры, в которые записывает, какие ресурсы выделены каждому процессу. Некоторые из ресурсов выделяются процессу при его создании, а некоторые — динамически по запросам во время выполнения. При выполнении этих функций подсистема управления процессами взаимодействует с другими подсистемами ОС, ответственными за управление ресурсами, такими как подсистема управления памятью, подсистема ввода-вывода, файловая система.

Слайд 3

Слайд 5

Слайд 6

Слайд 7

Слайд 8

Слайд 9

Слайд 10

Слайд 11

Слайд 12

Слайд 13

Слайд 14

Слайд 15

Слайд 16

Слайд 17

Слайд 18

Слайд 19

Слайд 20

Слайд 21

Слайд 22

Слайд 23

Слайд 24

Слайд 25

Слайд 26

Слайд 27

Кто Я? Существуют две альтернативы: Яи – Вечный закон Вечного творения; ял – временный результат Вечного творения. Есть свобода выбора: Что Человек выбирает тем и становится! Важнее исследовать базовые принципы организации Операционных Систем чем конкретную её реализация

Слайд 28

Слайд 29

Слайд 30

Свидетельство и скидка на обучение каждому участнику

Зарегистрироваться 15–17 марта 2022 г.

Описание презентации по отдельным слайдам:

Планирование процессов в операционной системе

Планирование - обеспечение поочередного доступа процессов к одному процессору. Планировщик - отвечающая за это часть операционной системы. Алгоритм планирования - используемый алгоритм для планирования. Основные понятия планирования

Основные понятия планирования Алгоритм планирования без переключений (неприоритетный) - не требует прерывание по аппаратному таймеру, процесс останавливается только когда блокируется или завершает работу. Алгоритм планирования с переключениями (приоритетный) - требует прерывание по аппаратному таймеру, процесс работает только отведенный период времени, после этого он приостанавливается по таймеру, чтобы передать управление планировщику.

Основные понятия планирования Основные три системы: 1. Системы пакетной обработки - могут использовать неприоритетный и приоритетный алгоритм (например: для расчетных программ). 2. Интерактивные системы - могут использовать только приоритетный алгоритм, нельзя допустить чтобы один процесс занял надолго процессор (например: сервер общего доступа или персональный компьютер). 3. Системы реального времени - могут использовать неприоритетный и приоритетный алгоритм (например: система управления автомобилем).

Планирование в системах пакетной обработки 1 "Первый пришел - первым обслужен" (FIFO - First In Fist Out) Процессы ставятся в очередь по мере поступления. Преимущества: Простата Справедливость (как в очереди покупателей, кто последний пришел, тот оказался в конце очереди) Недостатки: Процесс, ограниченный возможностями процессора может затормозить более быстрые процессы, ограниченные устройствами ввода/вывода.

Планирование в интерактивных системах 1 Циклическое планирование Каждому процессу предоставляется квант времени процессора. Когда квант заканчивается процесс переводится планировщиком в конец очереди. При блокировке процессор выпадает из очереди.

Планирование в интерактивных системах 2 Приоритетное планирование Каждому процессу присваивается приоритет, и управление передается процессу с самым высоким приоритетом. Приоритет может быть динамический и статический.

Планирование в интерактивных системах 3 Методы разделения процессов на группы Группы с разным квантом времени Сначала процесс попадает в группу с наибольшим приоритетом и наименьшим квантом времени, если он использует весь квант, то попадает во вторую группу и т.д. Самые длинные процессы оказываются в группе наименьшего приоритета и наибольшего кванта времени.

Планирование в системах реального времени Системы реального времени делятся на: 1. жесткие (жесткие сроки для каждой задачи) - управление движением 2. гибкие (нарушение временного графика не желательны, но допустимы) - управление видео и аудио Внешние события, на которые система должна реагировать, делятся: 1. периодические - потоковое видео и аудио 2. непериодические (непредсказуемые) - сигнал о пожаре

Краткое описание документа:

Тема урока: Основные понятия планирования процессов

Планирование- обеспечение поочередного доступа процессов к одному процессору.

Планировщик- отвечающая за это часть операционной системы.

Алгоритм планирования- используемый алгоритм для планирования.

Читайте также: