Лекция 4. Статико-динамическое планирование (1185228)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

ИНФОРМАЦИОННО-УПРАВЛЯЮЩИЕ СИСТЕМЫРЕАЛЬНОГО ВРЕМЕНИЛекция 4:Статико-динамическое планирование вычисленийв системах интегрированной модульной авионикиКафедра АСВК,Лаборатория Вычислительных КомплексовБалашов В.В.Федеративная ИУС РВФедеративная ИУС РВ• Специализированные блоки– по назначению– по архитектуре• ПО различных подсистем – на различныхблоках– изоляция по памяти– нет конкуренции подсистем за процессорноевремя• Недостатки:– низкая переносимость и повторнаяиспользуемость ПО– «зоопарк» процессорных архитектур ипрограммных интерфейсовИУС РВ c архитектурой ИМАИУС РВ с архитектурой ИМАс сетью на базе коммутатораВычисленияВычисленияВычисленияВычисленияВычисленияКоммутаторВычисленияКоммуникацииКоммуникацииГрафикаГрафикаИУС РВ c архитектурой ИМА• Логически единый распределенныйвычислитель– унифицированные модули нескольких типов– единая архитектура процессоров– унифицированный программный интерфейс• Разделение вычислительных ресурсовмежду ПО различных подсистем• Проблемы:– изоляция по памяти– разделение процессорного времени• Решение: каждой подсистеме  разделИМА и разработка ПО• Особенности:– Стандартное API со стороны ОС– Статическое разделение времени, памятии ресурсов• Преимущества:– Надежность– Переносимость– Возможность повторного использования– Модульность– Упрощение верификации и сертификацииСтруктура ПО.

Интерфейс APEXРаздел 2Раздел 3Задача 1.1Задача 2.1Задача 3.1Задача 1.2Задача 2.2Задача 3.2Задача 1.3Задача 2.3Задача 3.3Интерфейс APEXОперационная системаСистемное ПОАппаратное обеспечениеприкладное ПОРаздел 1Взаимодействие междуразделами• Порты с очередью сообщений• Порты с перезаписью сообщений– Буфер фиксированной длины– Сообщение в буфере перезаписывается– Отправка с заданным периодомВзаимодействие внутриразделов• Обмен данными– Передача сообщений– Общая память• Механизмы синхронизации– Семафоры– СобытияРабочая нагрузка• периодические задачи• сообщения• зависимости по данным11Синхронизация на практике• Ожидание данных только от задач с той жечастотой– «синхронная» зависимость по данным• Отправитель выполняется чаще получателя:– на входе получателя почти всегда актуальныеданные– ожидать нет смысла• Отправитель выполняется реже получателя– ожидание нарушает требования по частоте длязадачи-получателяСостояния задач в ARINC653неактивнаготовностьожиданиевыполнениеВыполнение задач в системе• Задачи раздела выполняются в рамках окон– статическое расписание окон– границы окон одинаковы для всех ядер одного модуля• Между разделами происходит переключение контекста• Работы в окне: динамическое планирование––––очередь выполненияприоритетывытеснениеожидание входных данных• Незавершенная работа может быть возобновлена вследующем окнеЯдро 11-11-11-2Модуль 1Ядро 2Модуль 2 Ядро 12-12-24-13-14-24-1Модуль 2 Модуль 1Пример расписанияП1П2П1П2Задача планирования:входные данные• Описание системы ИМА– набор модулей– модуль  набор и типы процессорных ядер– ядро  верхняя граница загрузки• Описание рабочей нагрузки––––наборы задач, сообщений, разделовзадача  период, приоритет, WCET (для типа ядра)раздел  задачи, допустимые ядрасообщение  отправитель, получатель, размер,длительность передачи (через память, через сеть)– свободные задачи, допустимые ядра16Задача планирования: цели• Составить разделы из свободных задач– Трафик между разделами  min– Загрузка ядра разделом ≤ Umax(при выполнении раздела целиком на одном ядре)• Привязать разделы к ядрам– Трафик между модулями  min(минимизация загрузки сети)– Загрузка ядра ≤ Umax(ядро)– Привязка к допустимым ядрам T F  n2ni 0ii1n1– Выполнение условий динамической планируемости– Инкрементальная привязка (расширение прежней)• Построить расписание окон для каждого ядра– Корректность расписание проверяется моделированием работыдинамического планировщика– Расписание считается корректным, если все задачивыполняются в пределах директивных сроков (Д.С.

= период)17при длительностях выполнения, равных WCETОграничения корректности•••••Раздел привязан ровно к одному ядруНе более одного раздела в окнеОкна не пересекаются по времениРаботы выполняются в рамках окон разделаВ каждый момент времени выполняется неболее одной работы• Все работы выполняются полностью• Выполняются зависимости по данным• Соблюдаются приоритетыЖадный алгоритм привязки разделовк процессорным ядрамВыбрать непривязанный раздел Р с максимальнымтрафиком между Р и привязанными разделами.Для каждого модуля рассчитать трафик между Р иразделами, привязанными к ядрам других модулей.Упорядочить модули по убыванию этого трафика.В цикле по модулям:1.2.3.4.••5.6.если раздел Р может быть привязан к какому-либо ядруданного модуля без нарушения ограничений на загрузкуядра, то привязать Р к этому ядру и выйти из цикла;иначе, если разделы на данном модуле могут бытьперераспределены между ядрами этого модуля так, чтобы вдостаточной мере «разгрузить» одно из ядер, то выполнитьперераспределение, привязать Р к этому ядру и выйти изцикла;Если на шаге 4 не выбрано никакое ядро, то стоп (неуспех).Если остались непривязанные разделы, то перейти к шагу 1,19иначе стоп (успех).Альтернативные алгоритмы привязкиразделов к процессорным ядрам• Метод ветвей и границ– Критерий отсечения: загрузка ядра превышаетдопустимую, или ранее найдено лучшее решение– Недостаток: время выполнения на реальных данных• Упаковка в контейнеры– Ядро = контейнер• емкость = Umax(ядро)– Раздел = объект• объем = вклад раздела в загрузку ядра• стоимость = трафик, становящийся «внутренним» длямодуля в случае привязки раздела к ядру этого модуля– Проблемы:• объем объекта зависит от выбора контейнера(длительность выполнения задачи зависит от типа ядра)• стоимость объекта зависит от расположения другихобъектовПостроение расписания: схемаалгоритма1.

Построение графа зависимостей работ2. Уточнение директивных интервалов работна основе зависимостей3. Построение последовательностейвыполнения работ «слева направо»,параллельно для всех ядер4. Построение расписания окон на основепостроенной последовательности работ5. Назначение приоритетов задач на основепостроенной последовательности работУточнение директивного срокаДедлайн задачи 1-1Модуль 1Ядро 11-2M1Модуль 2Ядро 13-12-11-2M2Раздел 1M23-23-3Раздел 2Раздел 33-31-1M13-22-13-1Переключениеконтекста иинициализация окнаПланирование «слева направо»1. Работа помещается в список готовых длявыполнения, если:––Начался ее директивный интервалПолучены все синхронные входящиесообщения для данной работы2. Очередная работа для размещениявыбирается из списка:––Если отсутствуют готовые работы с большимприоритетомПо критерию EDF (если приоритет еще неопределен)Модель вычислительногопроцесса•••Служит для проверки корректностирасписания оконМодель основана на событияхСхема работы:1.

Создание начальных событий2. Выбор событий с минимальным временем3. Обновление списка готовых к выполнениюработ4. Обработка выбранных событий5. Если список событий не пуст, переход к п.2Типы событий•••••Открытие окнаЗакрытие окнаНачало директивного интервалаЗавершение работыДоставка сообщенияРабота моделиРабота моделиРабота моделиНедостатки моделиРешение:не выполнять низкоприоритетные задачи, покаесть высокоприоритетные, ожидающие сообщенийАдаптация к изменениямЧастоты илидлительностиСписки задачили приоритетыСписок разделовили модулиПроверкана моделиЗаданиеприоритетовДополнениепривязкиПостроениерасписанияАдаптациярасписанияПостроение«с нуля»ОКFailПерспективные задачи• Построение расписания с минимизациейзатрат на переключение контекста• Корректировка распределения разделов поядрам при неуспешном построении расписания• Построение расписания, гарантированнокорректного при временах выполнения задач,меньших чем WCET• Минимизация сетевой загрузки с учётомсинхронности зависимостей по данным– сообщения, которые ожидает задача-получатель,следует передавать через память (=> привязкаотправителя и получателя к одному модулю)• Совместное планирование задач иконфигурирование сетиСпасибо за внимание.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций