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

• Автор: Дашевский, Владимир Павлович
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Санкт-Петербург
• Количество страниц: 141 с. : ил.

СОДЕРЖАНИЕ Введение

Глава 1. Организация выполнения задач в СРВ.

1.1. Модель многозадачной СРВ.

1.1.1. Состояния задачи и переходы между ними.

1.1.2. Требования реального времени в вычислительных системах .

1.1.3. Используемые обозначения.

1.2. Планирование в СРВ.

1.2.1. Методы оценки эффективности планирования.

1.2.2. Парадигмы планирования

1.3. Анализ выполнимости задач в СРВ.

1.3.1. Основные понятия, применяемые для анализа выполнимости

1.3.2. Методы детерминированного анализа
1.3.3. Стохастические факторы в системах реального времени.
1.3.4. Методы вероятностного анализа.
1.4. Постановка задачи диссертации.
1.5. Заключение по главе 1.
Глава 2. Методы вероятностного анализа СРВ с независимыми периодическими задачами, сроки которых не превышают их периода.
2.1. Предположения относительно системы задач.
2.2. Формулировка задачи вероятностного анализа СРВ.
2.3. Алгоритм вероятностного анализа задачи.
2.4. Оценка сложности алгоритма.
2.5. Сравнение результатов вероятностного анализа с результатами численного моделирования
2.6. Заключение по главе
Глава 3. Вероятностный анализ СРВ с независимыми периодическими задачами с произвольными сроками выполнения.
3.1. Буферизация внешних запросов на выполнение задач.
3.1.1. Постановка задачи вероятностного анализа в системе с буферизацией запросов
3.1.2. Применимость вероятностного анализа к системам с буферизацией запросов
3.1.3. Сравнение результатов вероятностного анализа с численным моделированием.
3.1.4. Сравнение системы с буферизацией запросов с системой без буферизации запросов.
3.2. Порождение нескольких экземпляров одной задачи.
3.2.1. Формулировка задачи вероятностного анализа.
3.2.2. Применимость метода вероятностного анализа к системам с порождением нескольких экземпляров одной задачи
3.3. Заключение по главе 3.
Глава 4. Взаимное влияние задач, решаемых на одном микропроцессоре.
4.1. Переключение контекстов задач
4.1.1. Релаксационная модель поведения процессора при переключении контекста задач.
4.1.2. Методы экспериментального исследования характеристик системы при переключении контекста.
4.1.3. Поправки для анализа выполнимости задач
4.2. Заключение по главе 4.
Глава 5. Применение разработанных методов анализа выполнимости при проектировании системы связи удаленных телефонных станций средствами сети I
5.1. Общее описание проблемы.
5.2. Архитектура многоканального шлюза I
5.3. Архитектура программного обеспечения для многоканальной
цифровой обработки аудиоданных на одном .
5.3.1. Задачи обработки аудиоданных
5.3.2. Требования реального времени при обработке аудиоданных
5.4. Вероятностный анализ набора задач одного
5.4.1. Постановка задачи вероятностного анализа для кодирования и декодирования потоков аудиоданных.
5.4.2. Модельные профили времени выполнения задач
5.4.3. Результаты анализа для разного количества задач.
5.5. Обсуждение результатов исследований.
5.6. Заключение по главе 5.
Заключение.
Литература


Анализ предоставляет разработчику сведения о выполнимости задач до построения реальной системы и дает возможность оценить запас временной прочности системы на случай нарушения предполагаемых условий ее работы. В четвертом разделе на основе результатов проведенного исследования формулируется задача диссертации. В пятом разделе дается общее заключение по главе 1. Организация работы в реальном времени единственной задачи не представляет особых трудностей. Обеспечение своевременного выполнения нескольких задач с разными характеристиками в рамках одной системы представляет определенные трудности. Для преодоления этих трудностей за последние тридцать лет создан мощный теоретический аппарат ,,4,,,9, в основе которого лежит модель многозадачной СРВ. Ниже приводятся основные понятия, используемые для теоретического рассмотрения систем реального времени. Основным понятием модели является понятие задача. Задача представляет собой совокупность вычислений и операций вводавывода, семантически связанных между собой. Выполнение задачи осуществляется одним процессором и требует процессорного времени. Отсутствие возможности предоставить процессорное время сразу всем задачам является главной трудностью для их своевременного выполнения. Целью теории СРВ является ответ на вопрос, как обеспечить своевременное выполнение каждой задачи при известных характеристиках задач и процессоров системы. Для большинства областей применения СРВ характерно циклическое выполнение задач ,. При этом выполнение каждой задачи повторяется во времени, но, возможно, с другими входными данными. Реализация такого поведения в вычислительных системах заключается в том, что одна и та же программа выполняется многократно, производя при этом считывание измерение входных данных, вычисление и вывод результатов управление. Каждый такой цикл выполнения задачи принято называть экземпляром задачи. Экземпляры одной задачи не обязательно следуют друг за другом после выполнения одного экземпляра задачи СРВ может ожидать внешнего события или выполнять экземпляр другой задачи. Выполнение каждого экземпляра задачи принято связывать с поступлением в систему запроса на решение задачи. СРВ. В любом случае появление запроса на решение задачи должно быть сначала зарегистрировано в системе, а затем привести к активации очередного экземпляра этой задачи. Поступление запросов на решение разных задач приводит к тому, что в системе может одновременно существовать несколько активных экземпляров задач. Выбор наиболее важного из них входит в задачу планирования см. Активный экземпляр задачи, выбранный планировщиком, становится выполняемым и получает процессор. Нго выполнение продолжается до тех пор, пока он не завершится, либо в систему не поступит запрос на решение экземпляра другой задачи, который будет обладать большим приоритетом по сравнению с текущим выполняемым экземпляром. Момент времени, в который происходит завершение экземпляра задачи, называют моментом отклика экземпляра задачи, а время, прошедшее между поступлением запроса на решение задачи и моментом отклика, называют временем отклика экземтяра задачи. Время отклика представляет собой одну из важнейших характеристик СРВ. Способность СРВ выполнять задачи с малым временем отклика называют реактивностью. Принято различать время отклика экземпляра задачи и время выполнения экземпляра задачи. Под временем выполнения понимают время, в течение которого задача может быть выполнена без влияния со стороны других задач. Обычно этот параметр используется при анализе систем реального времени для расчета гарантируемого времени отклика задачи. Поскольку в СРВ обычной является ситуация, когда задачи, выполняемые на одном процессоре, влияют друг на друга, то время отклика задачи превосходит время ее выполнения. Выполнение нескольких задач на одном процессоре требует распределения процессорного времени между ними. Для этого каждой задаче назначается приоритет. Приоритет задачи в самом общем смысле означает право первоочередного выполнения задачи по отношению к другим задачам. Приоритет является отношением частичного порядка между задачами.