Методы разделения процессов на группы
Группы с разным квантом времени Сначала процесс попадает в группу с наибольшим приоритетом и наименьшим квантом времени, если он использует весь квант, то попадает во вторую группу и т.д. Самые длинные процессы оказываются в группе наименьшего приоритета и наибольшего кванта времени.
Процесс либо заканчивает работу, либо переходит в другую группу Этот метод напоминает алгоритм - "Кратчайшая задача - первая".
Группы с разным назначением процессов
Процесс, отвечающий на запрос, переходит в группу с наивысшим приоритетом. Такой механизм позволяет повысить приоритет работы с клиентом.
Гарантированное планирование В системе с n-процессами, каждому процессу будет предоставлено 1/n времени процессора.
Лотерейное планирование Процессам раздаются "лотерейные билеты" на доступ к ресурсам. Планировщик может выбрать любой билет, случайным образом. Чем больше билетов у процесса, тем больше у него шансов захватить ресурс.
Справедливое планирование Процессорное время распределяется среди пользователей, а не процессов. Это справедливо если у одного пользователя несколько процессов, а у другого один.
Планирование в системах реального времени Системы реального времени делятся на: жесткие (жесткие сроки для каждой задачи) - управление движением гибкие (нарушение временного графика не желательны, но допустимы) - управление видео и аудио Внешние события, на которые система должна реагировать, делятся: периодические - потоковое видео и аудио непериодические (непредсказуемые) - сигнал о пожаре Что бы систему реального времени можно было планировать, нужно чтобы выполнялось условие:
m - число периодических событий i - номер события P(i) - период поступления события T(i) - время, которое уходит на обработку события Т.е. перегруженная система реального времени является не планируемой.
Планирование однородных процессов В качестве однородных процессов можно рассмотреть видео сервер с несколькими видео потоками (несколько пользователей смотрят фильм). Т.к. все процессы важны, можно использовать циклическое планирование. Но так как количество пользователей и размеры кадров могут меняться, для реальных систем он не подходит.
Общее планирование реального времени Используется модель, когда каждый процесс борется за процессор со своим заданием и графиком его выполнения. Планировщик должен знать: частоту, с которой должен работать каждый процесс объем работ, который ему предстоит выполнить ближайший срок выполнения очередной порции задания Рассмотрим пример из трех процессов. Процесс А запускается каждые 30мс, обработка кадра 10мс Процесс В частота 25 кадров, т.е. каждые 40мс, обработка кадра 15мс Процесс С частота 20 кадров, т.е. каждые 50мс, обработка кадра 5мс
Три периодических процесса Проверяем, можно ли планировать эти процессы. 10/30+15/40+5/50=0.808<1 Условие выполняется, планировать можно. Будем планировать эти процессы статическим (приоритет заранее назначается каждому процессу) и динамическим методами.
4.4.3 Статический алгоритм планирования RMS (Rate Monotonic Scheduling) Процессы должны удовлетворять условиям: Процесс должен быть завершен за время его периода Один процесс не должен зависеть от другого Каждому процессу требуется одинаковое процессорное время на каждом интервале У непериодических процессов нет жестких сроков Прерывание процесса происходит мгновенно Приоритет в этом алгоритме пропорционален частоте. Процессу А он равен 33 (частота кадров) Процессу В он равен 25 Процессу С он равен 20 Процессы выполняются по приоритету.
Статический алгоритм планирования RMS (Rate Monotonic Scheduling)
4.4.4 Динамический алгоритм планирования EDF (Earliest Deadline First) Наибольший приоритет выставляется процессу, у которого осталось наименьшее время выполнения. При больших загрузках системы EDF имеет преимущества. Рассмотрим пример, когда процессу А требуется для обработки кадра - 15мс. Проверяем, можно ли планировать эти процессы. 15/30+15/40+5/50=0.975<1 Загрузка системы 97.5%
Динамический алгоритм планирования EDF (Earliest Deadline First)
Алгоритм планирования RMS терпит неудачу.
|
