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