Инструментальная система построения расписания обмена данными по каналу с централизованным управлением

Введение

Большинство современных бортовых вычислительных систем реального времени (ВСРВ) являются распределёнными. В их состав входят датчики, органы управления, вычислительные узлы, хранилища данных и устройства вывода, соединённые коммуникаци­онными каналами. В бортовых системах реального времени широко используется архитектура, основанная на каналах с централизованным управлением. Примерами каналов с централизованным управлением являются MIL STD-1553B (ГОСТ Р 52070-2003, МКИО) [1], STANAG 3910 [2], FC-AE-1553 [3].

Канал обеспечивает обмен данными между устройствами, присоединёнными к нему (далее – оконечные уст­ройст­­ва). Обмен представляет собой последовательность передач прикладных и служебных данных между оконечными устройствами. Следуя принятой терминологии, каждую передачу будем называть работой. Время начала каждой работы определяет расписание, которое строят заранее и которое не меняется в ходе функционирования бортовой системы. Расписание исполняется контроллером, который является одним из оконечных устройств. Только контроллер канала может инициировать обмен данными; другие оконечные устройства выполняют команды, отданные контроллером (схема ведущий – подчинённый), что гарантирует отсутствие коллизий.

На расписание накладываются технологические ограничения, которые определяются особенностями оборудования и системного программного обеспечения ВСРВ. Число работ, входящих в расписание обмена, для современных бортовых ВСРВ может достигать нескольких сотен.

На сегодня хорошо осознаны невозможность ручного построения расписания для современных ВСРВ и необходимость автоматизации построения расписания, которое бы включало все работы и удовлетворяло всем наложенным ограничениям. Существую­щие инструментальные системы для статического планирования вычислительных задач и/или обмена данными в бортовых системах реального времени [4, 5] не поддерживают ряд практически важных ограничений на расписание (примеры ограничений приводятся далее).

В данной статье представлена инструментальная система, поддерживающая автоматическое построение расписаний обмена данными по каналу с централизованным управлением MIL STD-1553B. Описаны требования к системе, функциональность, технологический процесс использования и примеры её практического применения.

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

Структура рабочей нагрузки на канал и расписания обмена

Рабочая нагрузка на канал с централизованным управлением состоит из набора сообщений, каждое из которых необходимо периодически передавать по каналу. Для каждого сообщения известна его длительность и требуемая частота передачи. Одному сообщению может соответствовать несколько работ. Длительность интервала планирования l_int, для которого должно быть построено расписание, равна наимень­шему общему кратному периодов сообщений (период является обратной величиной к частоте передачи). Коли­чество работ в рамках интервала планирования, соответствующих сообщению, равняется отношению l_int к пери­о­ду сообщения.

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

Для некоторых сообщений могут быть заданы фазовые сдвиги, которые сужают директивные интервалы соответствующих работ. Поясним, как директивные интервалы работ определяются по периоду и фазовым сдвигам сообщения. Пусть есть сообщение m с длительностью d, периодом T и фазовыми сдвигами φ₁ и φ₂. Пусть ν₁, ν₂ и ν₃ – первые три работы данного сооб­щения (общее число его работ равняется l_int/T). Характеристики этих работ вычисляются следующим образом (i = 1, 2, 3):

• левая граница директивного интервала s_i = (i – 1) × T + φ₁;

• правая граница директивного интервала f_i = (i – 1) × T + φ₂;

• директивный интервал [s_i; f_i];

• длительность t_i = d.

На рис. 1 изображены директивные ин­тервалы (толстые горизонтальные линии) для работ v₁, v₂ и v₃. Каждая работа должна быть выполнена внутри своего директивного интервала.

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

Ограничения на корректность расписания

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

1. Общие ограничения:
   а) отсутствие коллизий (интервалы вы­полнения работ не должны пересекаться);
   б) каждая работа должна выполняться внутри своего директивного интервала;
   в) недопустимо прерывание работ.

2. Ограничения, обусловленные технологическими требованиями к обмену данными, например:
   а) длительность подцикла;
   б) резерв времени в начале подцикла;
   в) резерв времени в конце подцикла;
   г) сдвиг, на который можно сместить расписание вправо по временной оси без нарушения директивных сроков и других ограничений;
   д) максимально допустимое число ра­бот в цепочке;
   е) ограничения на порядок работ в цепочке (например, работа по передаче сообщения m₂ может быть размещена в цепочке только после работы по передаче сообщения m₁).

Рис. 2 иллюстрирует ограничения 2а–2д. 

Конкретный набор технологических ограничений на корректность расписания определяется особенностями оборудования и системного программного обеспечения, используемого в целевой бортовой ВСРВ. Следова­тель­но, важным требованием к алгоритму построения расписаний является возможность настройки на различные наборы ограничений.

Перечисленные ограничения применяются к известным авторам бортовым ВСРВ, основанным на каналах MIL STD-1553B. Эти ограничения определяются не спецификой данного стандарта, а циклической схемой обмена данными и особенностями её реализации. Например, резерв времени в начале подцикла (см. ограничение 2б) необходим для того, чтобы перепрограммировать адаптер контроллера для выполнения следующей цепочки работ. Возможно применение этих ограничений в каналах с централизованным управ­лением:

• FC-AE-1553, разработанном для упро­щения миграции с унаследованных систем на основе MIL STD-1553B с минимальными изменениями в логике обмена;

• STANAG 3910, в котором управляющая шина построена по стандарту MIL STD-1553B.

Существующие инструментальные системы построения расписания вычислений в бортовых ВСРВ

Существует ряд инструментальных систем [4–7], поддерживающих построение расписаний для бортовых ВСРВ. Оценим возможность применения этих систем для построения статического расписания обмена данными по каналу с централизованным управлением в рамках циклической схемы обмена данными с введёнными ограничениями на корректность расписания.

Инструментальная система [4] стро­ит статические расписания выполнения вычислительных задач и обмена дан­ными для систем, использующих концепцию Integrated Modular Avio­nics. В качестве целевой системы в [4] рассматриваются подсистемы бортовой ВСРВ самолёта Boeing 777. Эти подсистемы используют шину ARINC 659 для обмена данными между модулями. Расписание обмена данными подчинено расписанию выполнения вычислительных задач, которое стро­ится в первую очередь. Алгоритм построения статического расписания обмена данными, описанный в [4], требует допустимости прерывания передачи сообщений (в то время как для каналов с централизованным управлением прерывание выполнения работ обычно недопустимо). Кроме того, этот алгоритм предполагает возможность начать передачу сообщения в любой момент времени (тем самым никакие сложные ограничения на корректность расписания не поддерживаются). Важной особенностью рассматриваемой в [4] инструментальной системы является возможность расширения подсистемы планирования посредством программных модулей, однако в статье не показано, что таким образом можно преодолеть фундаментальные ограничения алгоритма.

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

Коммерческие программные инструменты проектирования систем реального времени, такие как RapidRMA [6] и TimeWiz [7], специализируются на анализе возможности динамического построения расписаний в ВСРВ и основываются на теории частотно-монотонного планирования [8], которая не учитывает введённые технологические ограничения на корректность расписания.

В табл. 1 приведены сводные результаты оценки применимости инструментальных систем [4–7] для статического построения расписания обмена с учётом описанных технологических ограничений на корректность расписания. 

Ни одна из этих систем «как есть» не подходит для решения данной задачи, причём общим недостатком систем является отсутствие поддержки циклической схемы обмена и технологических ограничений на расписание. Исходные коды рассмотренных инструментальных систем недоступны, а механизмы расширения программными модулями (в случае наличия таковых) не могут устранить базовые ограничения этих систем.

Технологический процесс построения расписания обмена данными

Схема процесса

Предлагаемый технологический процесс построения расписания обмена данными предполагает следующую последовательность дейст­вий/ шагов:

1. создание проекта – наполнение базы данных информацией о структуре бортовой сети и характеристиках рабочей нагрузки на каналы передачи данных;

2. автоматическое построение расписания обмена данными, являющегося полным (включающим все работы) и корректным (удовлетворя­ющим всем ограничениям на корректность расписания):

3. при необходимости – ручная корректировка расписания;

4. в случае если нельзя построить полное и корректное расписание – автоматическая корректировка технологических ограничений таким образом, чтобы построение расписания с обновлёнными требованиями было возможным;

5. генерация программного кода, зада­ющего расписание для устройств, присоединённых к каналу;

6. генерация отчётов о входных данных (заданных на шаге 1) и построенных расписаниях для включения в документацию бортовой ВСРВ.

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

Категориям данных соответствуют прямоугольники (с прерывистой границей – для входных данных, со сплошной – для выходных). Дейст­виям соответствуют прямоугольники со скруглёнными углами и курсивной подписью. Шаг 1 технологического процесса на диаграмме не отражён.

Требования к инструментальной поддержке процесса

Для поддержки описанного технологического процесса инструментальная система построения расписания обмена данными должна:

• поддерживать выполнение всех шагов процесса;

• иметь модульную структуру, соответствующую шагам технологического процесса;

• обеспечивать хранение исходных данных и результатов каждого шага в базе данных;

• предоставлять графический интерфейс для взаимодействия с пользователем.

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

• для учёта различных технологических ограничений на корректность расписания;

• настройки шаблона генерируемого программного кода;

• настройки шаблонов отчётов;

• построения расписаний для различных стандартов каналов с централизованным управлением [1–3].

Ни одна из рассмотренных ранее инструментальных систем не удовлетворяет всем перечисленным требованиям.

Инструментальная система построения расписания и её применение

Инструментальная система построения расписания обмена данными

Коллективом Лаборатории вычислительных комплексов факультета вы­числительной математики и кибернетики (ВМК) МГУ им. М.В. Ломо­но­сова создана инструментальная система (ИС) «САПР циклограмм», удовлетворяющая требованиям, перечисленным в предыдущем разделе. ИС «САПР циклограмм» имеет модульную структуру (рис. 4), что позволяет путём локальных модификаций обеспечивать:

• работу с различными схемами БД (на практике схема БД частично определяется требованиями организации-заказчика);

• поддержку различных форматов генерируемого кода и формируемых отчётов;

• поддержку различных технологических ограничений на расписание обмена данными;

• настройку алгоритмов построения расписаний и алгоритмов корректировки технологических ограничений на специфику рабочей нагрузки на канал для конкретного класса ВСРВ.

ИС «САПР циклограмм» реализована на языке С++ с применением библиотеки графического интерфейса wxWidgets. В качестве СУБД поддерживается MySQL 5.x. ИС функционирует под управлением ОС Windows (XP и старше), а также Debian Linux. На рис. 5 и 6 приведены примеры экранных окон пользовательского интерфейса ИС «САПР циклограмм».

В качестве алгоритмов построения расписания в ИС используются:

• жадные алгоритмы [9], обладающие высоким быстродействием, но требующие настройки на специфику рабочей нагрузки;

• муравьиные алгоритмы [10], автоматически настраивающиеся на специфику рабочей нагрузки, но обладающие более высокой вычислительной сложностью по сравнению с жадными алгоритмами.

Корректировка технологических ограничений на расписание выполняется алгоритмами, описанными в [11].

ИС «САПР циклограмм» поддерживает генерацию кода задания расписания для ОС РВ «Багет», применяемой в бортовых ВСРВ отечественной разработки. Генерация кода для других ОС РВ, поддерживающих выполнение статических расписаний обмена по каналу MIL STD-1553B (в частности, QNX и VxWorks), обеспечивается за счёт настройки шаблона генерируемого кода. Шаблон ориентирован на табличную форму задания расписания. Для поддержки иной формы задания расписания (например, процедурной) достаточно внести в программный модуль генерации кода локальные модификации, не затрагивающие прочие модули ИС.

Расписания, построенные ИС «САПР циклограмм», совместимы с адаптерами MIL STD-1553B, поддерживающими выполнение цепочек работ. Такие адаптеры поставляются фир­­мами DDC, Condor Engineering, «Эл­кус» и предназначены для функционирования под управлением ОС РВ QNX, VxWorks, а также ОС Linux с расширениями реального времени.

Примеры применения инструментальной системы

В данном разделе описаны два примера промышленного применения ИС «САПР циклограмм».

Построение расписаний обмена данными для авиационных бортовых систем

С 2007 года ИС «САПР циклограмм» применяется для проектирования информационно-управляющих систем современных летательных аппаратов. ИС интегрирована в общий технологический процесс проектирования бортовой ВСРВ; она получает начальные данные из баз данных проекта заказчика и генерирует программный код, определяющий расписание, в требуемом формате. ИС «САПР циклограмм» на данный момент применена в двух разработках, в каждой из которых использовано несколько каналов MIL STD-1553B. Некоторые из этих каналов характеризуются высокой загрузкой (более 60%) и разнообразием частот сообщений (6 и более), что делает построение расписания для них нетривиальной задачей.

ИС «САПР циклограмм» интегрирована со стендом испытаний бортовой ВСРВ [12], используемым для тестирования бортовых систем. При работе стенда обмен данными выполняется в соответствии с расписаниями, построенными ИС; необходимые данные загружаются в стенд из базы данных проекта. Стенд построен на базе промышленных ЭВМ FASTWEL/До­ло­мант с применением адаптеров MIL STD-1553B производства ЗАО «Эл­кус».

Построение расписаний обмена данными для судовых бортовых систем

ИС «САПР циклограмм» была адаптирована и использована для проектирования судовых бортовых ВСРВ. В ходе адаптации был расширен набор поддерживаемых технологических требований и добавлена поддержка нескольких форматов баз данных проекта.

Каждая из целевых бортовых ВСРВ содержит более восьми каналов MIL STD-1553B. В соответствии с иерархической организацией ВСРВ каналы име­ют различные роли:

• центральный канал с наиболее сложной рабочей нагрузкой;

• периферийные каналы, соединяющие устройства в рамках подсистем;

• локальные каналы, соединяющие между собой основное и резервное устройства в паре с «горячим» резервированием.

С помощью системы ИС «САПР циклограмм» были успешно построены расписания для всех типов каналов.

Заключение

Описанная в данной статье инструментальная система «САПР циклограмм» применяется для построения расписаний обмена данными по каналам стандарта MIL STD-1553B в авиационных и судовых бортовых ВСРВ. Применение ИС «САПР циклограмм» позволило автоматизировать решение задачи построения расписаний, а также формирование программного кода, задающего расписание, и отчётов для включения в документацию на ВСРВ.

В настоящее время коллективом разработчиков ИС «САПР циклограмм» ве­дутся работы по расширению применяемых в ИС алгоритмов

• для построения расписаний по перспективным бортовым каналам с централизованным управлением, в частности FC-AE-1553;

• построения совместных расписаний выполнения вычислительных задач и обмена данными. ●

Литература

1. ГОСТ Р 52070–2003. Интерфейс магистральный последовательный системы элект­ронных модулей. – М. : Изд-во стан­­дартов, 2003. – 23 с.

2. Guide to Digital Interface Standards for Mi­litary Avionic Applications : Technical report ASSC/110/6/2-ISSUE 3. – Avionics Sys­tems Standardization Committee (ASSC). – 2006. – 249 p.

3. Information technology – Fibre Channel – Part 312: Avionics environment upper layer protocol MIL-STD-1553B Notice 2 (FC-AE-1553) : Technical Report TR 14165-312:2009. – International Organization for Stan­dardization (ISO). – 2009. – 84 p.

4. Lee Y.-H., Kim D., Younis M., Zhou J. Scheduling tool and algorithm for integrated modular avionics systems // Proc. 19th Di­gital Avionics Systems Conference, October 2000. – Vol. 1. – Pp. 1C2/1–1C2/8.

5. Goltz H.-J., Pieth N. A Tool for Generating Partition Schedules of Multiprocessor Sys­tems // Proc. 23rd Workshop on (Constraint) Logic Programming, September 2009. – Pp. 67–176.

6. Rapid RMA: The Art of Modeling Real-Time Systems [Электронный ресурс]. – Режим доступа : http://www.tripac.com/rapid-rma.

7. Douglass B.P. Doing Hard Time: Developing Real-Time Systems with UML, Objects, Fra­meworks, and Patterns // Addison-Wes­ley, 1999.

8. Liu C. L., Layland J. W. Scheduling Algo­rithms for Multiprogramming in a Hard-Re­al-Time Environment // Journal of the ACM. –1973. – Vol. 20. – No. 1. – Pp. 46–61.

9. Костенко В.А. Алгоритмы построения рас­писаний для одноприборных систем, входящих в состав систем реального времени // Методы и средства обработки информации : труды Третьей всероссийской научной конференции. – М. : Изда­тельский отдел факультета ВМК МГУ им. М.В. Ломоносова, 2009. – С. 245–258.

10. Balashov V.V., Balakhanov V.A., Kostenko V.A et al. A technology for scheduling of data exchange over bus with centralized control in onboard avionics systems // Proc. Institute of Mechanical Engineers, Part G: Journal of Ae­rospace Engineering. – 2010. – Vol. 224. – No. 9. – Pp. 993–1004.

11. Балашов В.В. Обеспечение совмести­мости требований к расписанию обмена по каналу с централизованным управлением [текст] : дис. … канд. физ.-мат. наук : 05.13.11 / МГУ им. М.В. Ломоносова. – М., 2010. – 171 с.

12. Стенд полунатурного моделирования для разработки встроенных вычислительных систем реального времени / Бала­шов В.В., Бахмуров А.Г., Волканов Д.Ю. и др. // Труды Четвёртой всероссийской научно-практической конференции «Ими­­та­ционное моделирование. Теория и практика» (ИММОД-2009). – СПб. : ОАО «ЦТСС», 2009. – С. 215–220.

E-mail: breeze256@mail.ru