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