Совместное планирование вычислений и обменов в информационно-управляющих системах реального времени

• Автор: Шестов, Пётр Евгеньевич
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Москва
• Количество страниц: 134 с. : ил.

Содержание
Введение

Глава 1. Задача построения совместимых расписаний вычислений и обменов

1.1. Содержательная постановка задачи

1.2. Математическая модель исходных данных

1.3. Математическая модель расписания и условий его корректности

1.4. Математическая постановка задачи

1.5. Классификация задачи

1.6. Практически значимые частные задачи

1.7. Выводы
Глава 2. Обзор возможных подходов к построению алгоритмов решения задачи и алгоритмов решения «близких» задач
2.1. Близкие задачи и алгоритмы их решения
2.2. Возможные подходы к решению поставленной задачи
2.3. Методы разработки алгоритмов построения статических многоприборных расписаний
2.4. Выводы
Глава 3. Алгоритмы решения задачи построения совместимых расписаний
3.1. Жадный алгоритм
3.2. Алгоритм, основанный на методе ветвей и границ
3.3. Жадный алгоритм со сдвигом расписания
Глава 4. Экспериментальное исследование разработанных ал-

горитмов
4.1. Цели исследования
4.2. Формирование исходных данных для экспериментов
4.3. Методика статистической обработки результатов экспериментов
4.4. Схема проведения экспериментов
4.5. Исследование жадного алгоритма
4.6. Исследование алгоритма, основанного на методе ветвей и границ
4.7. Исследование жадного алгоритма со сдвигом расписания
4.8. Выводы
Глава 5. Описание инструментального программного средства построения совместимых расписаний
5.1. Требования к инструментальному средству
5.2. Архитектура инструментального средства построения.совместимых расписаний
Заключение
Литература
Приложение А. Подробное описание жадного алгоритма
Приложение Б. Сложность жадного алгоритма для случая наибольшего числа возвратов
Приложение В. Подробное описание жадного алгоритма со сдвигом расписания
Приложение Г. Построение графа работ и сообщений по шаблону

Введение
Информационно-управляющие системы реального времени (ИУС РВ) используются для управления сложными техническими системами. Например, летательными аппаратами, кораблями, искусственными спутниками и т.п. Одним из важнейших требований к функционированию ИУС РВ является выполнение ограничений реального времени. Ограничения реального времени задаются в виде директивных интервалов для прикладных задач и сообщений. Прикладные задачи должны быть выполнены в рамках заданных директивных интервалов. Сообщения должны быть переданы в рамках заданных директивных интервалов. При нарушении этих ограничений ИУС РВ теряет свою работоспособность. На всех этапах разработки ИУС РВ необходимо строить расписание выполнения прикладных задач и расписание передачи сообщений для проверки возможности выполнения ограничений реального времени.
Разработка подобных ИУС РВ является сложным техническим процессом. Часто возникает задача модернизации таких систем, либо повторного использования отдельных подсистем ранее разработанных ИУС РВ. Причем изменение функционирования повторно используемых подсистем невозможно. Отсюда следует, что они обладают фиксированным интерфейсом, с помощью которого остальные устройства (в том числе другие подсистемы) в составе ИУС РВ взаимодействуют с такими подсистемами. Фиксирован формат сообщений и состав слов данных, которые получают и передают подсистемы.
К функционированию ИУС РВ предъявляется ряд требований, связанных не только с работой в реальном времени, но и обусловленных используемыми техническими стандартами, протоколами обмена данных, особенностями работы аппаратных и системных программных средств.
Настоящая диссертация посвящена алгоритмам построения совместимых

жества всех узлов системы.
Каждое задание состоит из модулей, минимальных единиц планирования. На множестве модулей одного задания может быть определено отношение предшествования. Модули бывают двух типов: вычислительные и коммуникационные. Время выполнения вычислительного модуля зависит от узла, на который он назначен. Каждому коммуникационному модулю соответствует партнер по коммуникации - коммуникационный модуль другого задания. Время выполнения коммуникационного модуля М3 зависит от того, на какой узел назначен партнер, и равно е31оса1, если партнер выполняется на том же узле (локальная коммуникация), и е3гето1е, если на другом (удаленная коммуникация), причем е31оса1 ^ е>ето(е. Временные задержки (например, на передачу служебных слов) при передаче сообщения между коммуникационными модулями Мг и М3, выполняющимися на разных узлах системы, фиксированы и заданы.
Отношение времени, которое прошло от директивного срока начала задания до завершения выполнения задания, к длительности директивного срока называется нормализованным временем отклика. В [69] ставится задача нахождения расписания, в котором минимизируется максимум нормализованного времени отклика, взятый по всем заданиям и зависящий от конкретного размещения модулей заданий по узлам системы. Напомним, что в понятие расписания также включается размещение заданий по вычислительным узлам.
Алгоритм решения основан на методе ветвей и границ. Дерево поиска состоит из частичных или полных расписаний. У каждой вершины ровно столько потомков, сколько вычислительных узлов в системе. Если считать, что задано для планирования т заданий, то на уровне к дерева поиска запланировано ровно к заданий (корень считается вершиной уровня 0). Вершины