14. Циклическая исполняющая система. Понятие кадра и основного цикла. Ограничения на размер кадра. Рисунок, пояснения.
Циклическая исполняющая система
Использование циклических исполняющих систем (ЦИС) достаточно распространено потому что такие системы просты и формируют полностью предсказуемый план представления. ЦИС могут рассматривается как планировщики, который заранее обусловлено чередуют и последовательно планируют выполнение периодических задач в соответствии с графиками. В общих чертах ЦИС – это таблица вызова процедур, где каждая задача является процедурой с единственным циклом do. При использовании подхода ЦИС решения по планированию принимаются периодически, а не в произвольный момент времени. Временный интервалы планирования момента принятия решений называются кадрами (фреймами) или малыми (второстепенными) циклами. Каждый кадр имеет продолжительность f называемое длинной кадра. Основной цикл есть минимальное время необходимое для выполнения задач, назначенных процессору с учетом предельных сроков и периодов для этих процессов. Основной цикл или гиперпериод есть наименьшее общее кратное всех периодов. Так как решения по планированию принимаются только в начале каждого кадра, то для каждого кадра отсутствует его прерывание при выполнении. Фаза каждой периодической задачи есть неотрицательное число кратное размеру кадра. Рис. 10.1.
Кадры должны иметь достаточную длину чтобы каждая задача могла начаться и закончиться в одном кадре. Это означает что размер кадра f должен быть больше чем время выполнения ei каждой задачи.
Для обеспечения длины циклического плана короткой на сколько это возможно длина фрейма должна быть такой, при которой гиперпериод будет целой часть от числа фреймов.
Чтобы все задачи были выполнены к их граничному времени, кадры должны быть достаточно малы для того, чтобы, между временем запуска и граничным временем выполнения каждой задачи существовал хотя бы один кадр.
Следующее отношение показывает наихудший сценарий, который возникает, когда период процесса следует сразу же за началом кадра и, следовательно, процесс не может быть запущен до следующего кадра.
15. Приоритетное фиксированное планирование с монотонной частотой. Основные результаты применения политики алгоритма монотонной частоты.
Фиксированное приоритетное планирование с монотонной частотой
При планировании с фиксированными приоритетами приоритет каждой задачи фиксирован по отношении к другим задачам. Основополагающим алгоритмом фиксированных приоритетов является алгоритм монотонной частоты (МЧ) – это оптимальный алгоритм статических приоритетных задач, в котором задачи с более коротким периодом назначается более высокий приоритет, чем задачам с длинным периодом. Теорема известная как теорема монотонной частоты является самым важным и полезным результатом теорий СРВ. Она может быть сформирована следующим образом: задано набор периодических задач и планирование с вытесняющими приоритетами; тогда назначения приоритетов таким образом, что задачи с более короткими периодами имеют более высокий приоритет (монотонная частота) дает оптимальный алгоритм планирования.
Оптимальность МЧ подразумевает, что если существует перечень задач, которые учитывают все временный ограничения с временными приоритетами, то использование алгоритма МЧ обеспечит необходимое планирование. Критическое время для задач определяется как время, при котором время задачи будет иметь наибольшее время отклика. Доказано, критический момент для любой задачи наступает всякий раз, когда задача запрашивается одновременно с более задачами высокого приоритета. Показано также что для проверки алгоритма МЧ достаточно проверить случаи когда фазы всех задач равны 0.
Пример использования алгоритма МЧ: таблица задает список задач для иллюстрации планирования МЧ.
Рисунок отображает МЧ планирования для определенного списка задач. Все задачи запускаются во времени равным 0. Поскольку у тау1 наименший период, то эта задача с наивысшим приоритетом и она рланируется первой. При время 4 запускается второй экземпляр тау1 и вытесняет тау3 так как у нее менший приоритет. Формула загрузки процессора:
Основные результаты применения политики МЧ
С практической точки зоения в случаи со статическими приоритетами важно знать при какаих условиях существует приемлемый план. Из следующей теоремы вытекает использование планирования АМЧ. Предполагается что относительный придельный срок завершения каждой задачи равен ее периоду. Теорема (граничное значение АМЧ): любое множество из периодических задач может быть подвержено МЧ планированию если загрузка процессора U не более чем m*(21/n - 1). Это оначает что где бы не находилась U на или ниже заданной границы загрузки план может быть составлен с использованием АМЧ.
Заметим что предел нагрузки при использовании АМЧ является достаточным но необходимым. На практике возможно построить список задач с общей наргузкой процессора больше придела АМЧ. При этом список может быть АМЧ планируемым. Многие сложные СРВ без проблем строятся с использованием более 80% нагрузки процессора.