Введение к работе
Актуальность. Для систем реального времени, к которым, безусловно, относятся и навигационные комплексы (НК), вопросы планирования вычислительного процесса имеют важное значение. Эти вопросы встают как на уровне НК при распределенных вычислениях, так и на уровне его однопроцессорных систем. В настоящей работе вычислительный процесс рассматривается как последовательность исполняемых задач, а под планированием понимается поиск для задач наилучшей упорядоченности с точки зрения заданного критерия. Характерными особенностями проблемы планирования в вычислительных системах навигационного комплекса, являются периодичность исполняемых задач, наличие для них директивных сроков, необходимость обеспечения для интервалов исполнения задач достаточно точной временной привязки, иерархическое отношение предшествования между задачами, априорная размещенность задач по процессорам НК.
Проблеме планирования вычислительного процесса всегда уделялось и продолжает уделяться достаточно большое внимание. Широкое освещение известных результатов можно найти в работах Коффмана Э.Г., Левина В.И., Топоркова В.В., Костенко В.А., Stankovic J.A, Cottet F., Liu J.W.S. Целый ряд решений вопросов планирования был предложен в рамках теории расписаний в работах Конвея Р.В., Танаева B.C., Brucker Р. и многих других. Тем не менее, в настоящее время многие проблемы из этой области и, в особенности для систем реального времени не решены с достаточной полнотой. Так, известные алгоритмы поиска оптимальных планов характеризуются высокой алгоритмической сложностью, поэтому на практике обычно используют приближенные локально-оптимальные алгоритмы или алгоритмы, основанные на эвристиках. Однако и эти алгоритмы достаточно сложны и не учитывают особенностей организации вычислительного процесса в навигационном комплексе, которые характерны для многих систем реального времени. Кроме того, следует констатировать, что в литературе практически отсутствуют
формальные алгоритмы планирования, учитывающие в используемых критериях фактор точности временной привязки исполняемых задач.
Исходя из вышесказанного, представляется актуальным совершенствование методов планирования вычислительного процесса по пути их формализации, снижения вычислительной сложности, расширения их возможностей за счет учета особенностей НК, а также снижения трудоемкости в результате автоматизации процедур планирования.
Цель работы и задачи исследования. Цель исследования состоит в разработке формальных методов планирования вычислительного процесса НК, эффективных как по критериям качества формируемых планов, так и по вычислительным затратам. Для достижения этой цели были решены следующие задачи:
анализ современных методов планирования вычислительного процесса в системах реального времени;
разработка методов планирования вычислительного процесса в системах НК, учитывающих фактор точности временной привязки исполняемых задач;
разработка методов планирования вычислительного процесса, учитывающих особенности НК;
разработка программных средств, поддерживающих процедуру планирования вычислительного процесса в НК, позволяющих снизить трудоемкость разработки, отладки и корректировки плана вычислительного процесса;
подтверждение эффективности разработанных методов и программных средств по результатам их практической апробации.
Методы исследования. Для решения поставленных задач использовались методы дискретной математики, теории расписаний, теории вероятностей, теории алгоритмов.
Научная новизна
1. Предложены методы однопоточного планирования вычислительного процесса, оптимальные по критерию минимума максимального отклонения от
заданных директивных сроков и не требующие перебора вариантов, для трех разрешимых случаев распределенных систем с иерархическим отношением предшествования для решаемых задач. Методы характеризуются вычислительной сложностью не хуже квадратичной.
Разработан субоптимальный метод однопоточного планирования вычислительного процесса для распределенных систем реального времени с иерархическим отношением предшествования для решаемых задач. Метод опирается на алгоритмы планирования для разрешимых случаев и характеризуется квадратичной вычислительной сложностью.
Произведен анализ эффективности предложенного субоптимального метода с использованием случайной генерации примеров. В результате установлено, что метод несущественно проигрывает методу оптимального планирования, минимизирующему максимальное отклонение от заданных директивных сроков.
Предложен метод многопоточного планирования вычислительного процесса для распределенных систем реального времени, учитывающий особенности современных навигационных комплексов.
Разработан метод планирования для однопроцессорной системы реального времени, оптимальный по критерию минимума заданного функционала от неточности временной привязки задач. Метод справедлив как в случае независимых задач, так и в случае зависимых задач.
Предложен метод планирования независимых задач для однопроцессорной системы реального времени, использующий критерий минимума средней неточности временной привязки при ограничениях по директивным срокам для решаемых задач.
Произведен анализ эффективности предложенного метода с использованием случайной генерации примеров. В результате установлено, что метод несущественно проигрывает методу оптимального планирования.
Практическая ценность
Разработанное программное обеспечение, в котором реализован метод многопоточного планирования, позволяет существенно сократить временные затраты на составление планов вычислительного процесса в навигационных комплексах. Программное обеспечение применено в опытно-конструкторских разработках цифрового вычислительного комплекса типа «Струна», входящего в состав морского навигационного комплекса типа «Симфония».
Разработанный метод планирования с минимизацией средней неточности временной привязки задач применен в гидроакустическом лаге изделия «Амазонка».
Основные положения, выносимые на защиту:
субоптимальный метод однопоточного планирования вычислительного процесса для распределенных систем реального времени с иерархическим отношением предшествования для решаемых задач;
результаты анализа эффективности субоптимального метода однопоточного планирования вычислительного процесса для распределенных систем реального времени с иерархическим отношением предшествования для решаемых задач;
метод многопоточного планирования вычислительного процесса, учитывающий особенности построения современных навигационных комплексов;
методы планирования для однопроцессорной системы реального времени, оптимальные по критерию минимума заданного функционала от неточности временной привязки задач.
Апробация работы. Материалы диссертации докладывались на международных научно-технических конференциях «Кибернетика и высокие технологии XXI века» (Воронеж, 2007; 2009), на 3-й Всероссийской научно-технической конференции «Методы и средства обработки информации» МСО-2009 (Москва, 2009), на XXVI конференции памяти выдающегося конструктора гироскопических приборов Н.Н. Острякова (Санкт-Петербург,
2008), на IX, X, XI, и XII конференциях молодых ученых «Навигация и управление движением» (Санкт-Петербург, 2007-2010).
Публикации. По материалам диссертации имеется 13 опубликованных работ, из них 2 статьи в научно-технических журналах («Вестник компьютерных и информационных технологий» и «Гироскопия и навигация»), рекомендуемых ВАК Минобразования и науки РФ, 9 докладов и 1 реферат доклада на международных и всероссийских конференциях, 1 свидетельство о государственной регистрации ПО для ЭВМ.
Структура и объем диссертации. Диссертация состоит из введения, четырех разделов, заключения и списка использованных источников, содержащего 80 наименований. Объем работы составляет 149 страниц, включая 59 рисунков и 24 таблицы.
