Планирование апериодических задач

2.3.1.4.    Планирование апериодических задач

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

Другой метод основан на использовании того факта, что выполнение задачи может быть динамически сдвинуто влево или вправо по временной шкале до тех пор, пока все временные ограничения для всех задач всё ещё выполнимы. Задачи должны быть прерываемыми.

2.3.1.5.    Планирование, управляемое приоритетами.

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

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

2.3.2.  Обзор методов.

2.3.2.1.    Rate-monotonic (RM).

Метод назначает статические приоритеты задачам основываясь на их периодах. В этом методе приоритеты определяются следующим образом: задача с самым маленьким периодом получает самый высокий приоритет.

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

Исходный RM подход имеет ряд ограничений:

·     Все задачи должны быть независимы друг от друга, т.е. между ними нет ни взаимодействия, ни общих ресурсов.

·     Все задачи должны быть периодическими.

·     Все задачи могут быть приостановлены другими задачами с более высокими приоритетами. Однако ни одна задача не может блокироваться, ожидая внешнего события.

·     Время выполнения постоянно.

·     Для задач определено время выполнения в худшем случае.

·     Все задачи имеют крайний срок, эквивалентный их периоду.

Было проведено большое количество исследований для расширения этих методов. В результате этих работ были сняты или ослаблены ограничения, налагаемые на задачи в исходной модели.

Так в протоколе приоритетных границ (Priority Ceiling Protocol) и некоторых других похожих (Stack Resource Protocol) удалось избавиться от ограничения на взаимодействие задач. Также было предложено много методов приведения непериодических задач к периодическим.

2.3.2.2.    Deadline Monotonic (DM).

Метод может быть использован для планирования задач, у которых крайние сроки меньше или равны периодам. Он ослабляет ограничение на величину крайнего срока в схеме планирования RM. В этом случае приоритет, назначенный задаче, обратно пропорционален величине её крайнего срока, то есть задача с самым коротким крайним сроком имеет самый высокий приоритет независимо от её периода. Если две задачи имеют одинаковые крайние сроки, то они получают приоритеты в произвольном порядке относительно друг друга. Метод может обслуживать как периодические, так и спорадические задачи.

Такой метод расстановки приоритетов будет оптимальным, если выполняются следующие условия:

·     множество задач – фиксированное множество жёстких задач;

·     задачи периодические или спорадические;

·     задачи имеют определённое (известное) время выполнения в худшем случае;

·     для задач определён критический момент, то есть время выполнения в худшем случае.

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

2.3.2.3.    Планирование апериодических задач.

2.3.2.3.1.      Метод фонового выполнения.

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

2.3.2.3.2.      Метод опроса.

Метод использует отдельную периодическую задачу с высоким приоритетом для поддержки выполнения апериодических задач.

Оба этих метода неэффективны, когда время ответа апериодической задачи важно.

2.3.2.3.3.      Алгоритм безотлагательного сервера (IS)

Это также подход сохранения пропускной способности. Он также использует периодический сервер, который имеет самый высокий приоритет, но не обязательно самый короткий период. Сервер приостанавливается, если не осталось ни одной апериодической задачи, и активизируется немедленно при прибытии апериодической задачи.

Похожие работы

Разработка отказоустойчивой операционной системы реального времени для вычислительных систем с максимальным рангом отказоустойчивости

Скачать

148576

34

0

... элементов, глобальное пространство имен, а также лавинообразную первоначальную загрузку сети. Таким образом ОСРВ SPOX имеет необходимые механизмы для создания отказоустойчивой распределенной операционной системы реального времени, концепция построения которой описана в главе 2. 4.3 Аппаратно-зависимые компоненты ОСРВ Модули маршрутизации, реконфигурации, голосования реализованы как аппаратно- ...

Основные понятия и программное обеспечение систем реального времени

Скачать

47787

0

3

... запрошенный ею ресурс, произошло связанное с ней внешнее событие, исчерпался заданный интервал времени и т. п. Заканчивая рассмотрение основных принципов планирования задач, необходимо отметить, что тема эта далеко не исчерпана. Диапазон систем реального времени весьма широк, начиная от полностью статических систем, где все задачи и их приоритеты заранее определены, до динамических систем, где ...

Разработка операционных систем

Скачать

106529

0

0

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

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

Скачать

97444

7

6

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