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

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

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

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)

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

2.3.2.3.4. Последний шанс.

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

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

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

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

2.3.2.4. EDF.

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

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

2.3.2.5. Сервер, допускающий задержку (DS) и Алгоритм обмена приоритетами (PE).

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

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

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

Этот метод проще в реализации, но хуже в исполнении.

2.4. Методология разработки программного обеспечения.

2.4.1. Основы методологии Real.

Не останавливаясь, в общем, на процессе разработки программного обеспечения, перечислим, какие модели используются в Real для описания разрабатываемой системы:

· Модель требований к системе:

Описательная модель -- в текстовом виде описывает некоторые требования к системе.

Модель случаев использования -- описывает требования, предъявляемые к системе ее окружением, т.е. отвечает на вопрос “что и для кого должна делать система?”.

Функциональная модель -- описывает разбиение случаев использования и функций на подфункции. Дает ответ на вопрос “как должны реализовываться функции системы в терминах своих подфункций?”.

· Динамическая модель:

Модель объектов -- описывает роли объектов системы и отвечает на вопрос “какие объекты взаимодействуют при выполнении функций системы?”.

Модель взаимодействий -- описывает сценарии взаимодействия объектов системы между собой и с пользователями, т.е. дает ответ на вопрос “как объекты взаимодействуют друг с другом для выполнения функций системы?”.

Поведенческая модель -- описывает алгоритмы поведения объектов системы, т.е. отвечает на вопрос “как должен вести себя каждый объект для реализации функций системы?”.

· Статическая модель:

Модель классов -- описывает внутреннюю структуру системы, структуры данных, используемые в ней, т.е. отвечает на вопрос “как должна выглядеть система изнутри?”.

В Real большой упор был сделан на связность моделей, на контроль целостности информации о проекте, представленной внутри как одной модели, так и в нескольких.

2.4.2. Модель требований.

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

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

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

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

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

Страницы: 1, 2, 3, 4, 5, 6, 7, 8