ОС РВ, использующие статико-динамическую модель вычислений.

Концепция интегрированной модульной авионики. Стандарт ARINC653.

Применение концепции ИМА к разработке ПО

Слайд 2: ИМА в разработке ПО

Основная идея ИМА — совместная работа разнородных приложений в единой программно-аппаратной системе, с использованием общего аппаратного обеспечения и унифицированного интерфейса операционной системы.

При этом возникает проблема влияния одних приложений на работу других. В системах на основе ИМА эта проблема решается при помощи статического (т.е., определяемого на этапе разработки системы) разделения памяти, времени и доступа к устройствам между приложениями. Благодаря этому влияние приложений друг на друга сведено к минимуму.

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

Структура ПО. Интерфейс APEX. Понятие разделов и задач

Слайд 3: Структура ПО. Интерфейс APEX

Основные составляющие части ПО:

• прикладное ПО;

• операционная система;

• системное ПО, специфичное для конкретной программно-аппаратной системы.

Важным понятием является интерфейс APEX между прикладным ПО и ОС. С точки зрения прикладного ПО, операционная система предоставляет унифицированный интерфейс, не зависящий от особенностей аппаратной части и реализации ОС. Это, в том числе, упрощает разработку конечной системы, позволяя переносить приложения между модулями.

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

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

Далее будем рассматривать ОС со статико-динамическим планированием на примере спецификации ARINC653.

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

Модель вычислений

Слайд 4: Состояния задач

Рассматриваются как периодические, так и апериодические задачи. Периодические задачи ставятся в очередь на выполнение с заданным периодом. Апериодические задачи могут попадать в очередь на выполнение в произвольный момент. Вне зависимости от типа, задача может находиться в одном из четырех режимов:

• неактивна;

• готова к выполнению;

• выполняется;

• ожидает.

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

Слайд 5: Выполнение задач в системе

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

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

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

Взаимодействие задач

В ОС на основе спецификации ARINC653 рассматриваются два вида взаимодействия: взаимодействие между разделами и взаимодействие внутри раздела.

Слайд 6: Взаимодействие между разделами

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

Со стороны раздела, логический канал представлен как входной или выходной порт. Предоставляются два типа каналов:

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

2. Канал с перезаписью сообщения. На стороне отправителя и получателя имеется буфер фиксированной длины. Раздел-отправитель может в произвольный момент поместить в выходной порт сообщение, при этом предыдущее сообщение будет перезаписано вне зависимости от того, было ли оно отправлено. Аналогично, раздел-получатель считывает сообщение из входного порта, содержимое сообщения во входном порте будет перезаписано при получении нового сообщения, вне зависимости от того, было ли прочитано старое.

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

Слайд 7: Взаимодействие внутри разделов

Для взаимодействия задач внутри одного раздела ОС предоставляет более широкие возможности, включающие:

• буферы сообщений;

• общую память;

• семафоры.

• События

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

Конфигурация системы в ARINC653

Слайд 8: Конфигурация системы

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

• информацию о разделах, включая:

  • требования к памяти

  • порты:

    • тип порта (с очередью или с перезаписью);

    • направление порта (входной или выходной);

    • размер буфера;

    • период отправки для портов с перезаписью.

• информацию о логических каналах: привязку входных портов к выходным;

• информацию о расписании окон:

  • список окон для каждого процессора;

  • привязку разделов к окнам.

• информацию для контроля и обработки ошибок

Составление таблиц конфигурации является важной задачей при разработке бортовой ИУС РВ и включает в себя задачи распределение разделов по модулям и процессорам и построение расписаний окон. Подробнее эти задачи будут описаны в следующей части.

Математические модели и задачи.

Задача построения статико-динамического расписания

Слайд 9: Исходные данные

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

• Список вычислительных модулей с информацией о количестве и типах процессоров.

• Список разделов.

• Список вычислительных задач, для которых заданы:

  • раздел;

  • частота;

  • длительность для каждого из типов процессоров;

  • приоритет.

• Список сообщений, для которых заданы:

  • задача-отправитель;

  • задача-получатель;

  • длительность передачи по каналу;

  • длительность передачи через память.

Слайд 10: Конфигурация системы

Требуется построить расписание, включающее:

• привязку разделов к модулям и процессорам;

• расписание окон для каждого модуля;

• привязку разделов к окнам;

• уточненные приоритеты задач.

Слайд 11: Критерии оптимальности

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

Слайд 12: Пример расписания

При этом на расписание накладываются следующие ограничения (здесь и далее будем использовать термин «работа» в значении «экземпляр периодической задачи»):

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

• Загрузка процессоров не должна превышать заданного значения.

• Ограничение реального времени: интервал выполнения работы не нарушает директивного срока.

• Архитектурные ограничения:

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

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

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

  • работы выполняются только в рамках окон, к которым привязан раздел;

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

  • суммарная длительность интервалов, в которых выполняется работа, не меньше длительности работы;

  • работа не начинает выполняться, пока не получит все свои сообщения;

  • работа не начинает выполняться, пока не завершились работы с более высоким приоритетом, начавшиеся раньше.

Слайд 13: Ограничения корректности (1)

Слайд 14: Ограничения корректности (2)

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

Формальное описание модели вычислений

1. Слайд 15: Формальная модель

Описываемая модель вычислений является событийной. Модель работает по следующему алгоритму:

1. Добавление в список событий открытия и закрытия окон и событий начала директивного интервала всех работ.

2. Выбор событий с минимальным временем (их может быть несколько), установка текущего времени на время события.

3. Обновление списков готовых к выполнению и опоздавших на текущий момент работ.

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

1. Обработка событий.

2. Если список событий не пуст, переходим к п. 2.

Слайд 16: Типы событий

Рассматриваются следующие типы событий:

• открытие окна;

• закрытие окна;

• начало директивного интервала работы;

• завершение работы;

• доставка сообщения.

Слайд 17-19: Работа модели

Обработка событий происходит следующим образом:

1. При открытии окна: выбираем из списка и ставим на выполнение работу с наибольшим приоритетом.

2. При закрытии окна:

   1. если задача завершена, то добавляем события доставки сообщений от нее;

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

3. При начале директивного интервала работы, если приоритет работы выше, чем текущей выполняемой, происходит вытеснение:

   1. корректируем оставшуюся длительность текущей выполняемой задачи и возвращаем ее в список готовых работ;

   2. выбираем из списка и ставим на выполнение работу с наибольшим приоритетом.

4. При завершении работы:

   1. добавляем события доставки сообщений от нее;

   2. выбираем из списка и ставим на выполнение работу с наибольшим приоритетом.

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

   1. корректируем оставшуюся длительность текущей выполняемой задачи и возвращаем ее в список готовых работ;

   2. выбираем из списка и ставим на выполнение работу с наибольшим приоритетом.

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

Слайд 20: Недостатки модели

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