Разработка точных и приближенных алгоритмов составления расписаний и синтеза систем жесткого реального времени

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

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

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

Пример 2. Системы управления ядерными реакторами на АЭС получают в режиме реального времени данные с множества датчиков и должны на их основе оперативно осуществлять управляющие воздействия на ректор. В случае, если какие-либо работы этой системы реального времени не будут выполнены в директивный срок, ядерная реакция может выйти из-под контроля и привести к крайне нежелательным последствиям вплоть до взрыва реактора.

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

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

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

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

Пример 7. При проведении Олимпийских Игр составляется расписание всевозможных состязаний и игр. Каждая игра должна пройти в определенном месте, некоторые игры должны быть назначены в одном и том же месте, но в разное время, и некоторые игры должны быть обязательно закончены перед тем, как начнутся другие. Например, ни одна финальная игра не может быть сыграна, пока в отборочных играх не определяться две лучшие команды.

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

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

Необходимо отметить, что корректность систем реального времени зависит не только от правильности результатов ее вычислений, но и от времени, за которое эти результаты были получены. Составление расписаний реального времени — важная часть подобных систем, так как проектировщик системы должен быть уверен в том, что все задания будут исполнены в срок. Одними из основополагающих работ в области планирований вычислений и многопроцессорных систем, идеи, подходы и основные положения которых использовались в настоящей работе, можно назвать [1], [2], [3] и [4]. 5.

Хорошие и относительно современные обзоры по составлению расписаний в системах реального времени можно найти в [5] и [6], а подробное резюме по результатам сравнения различных алгоритмов составления многопроцессорных расписаний приведено в [7].

Согласно общепринятой теории, все алгоритмы составления расписаний делятся на два класса: первые относятся к диспетчеризации с приоритетным управлением (priority-driven dispatching), вторые — к диспетчеризации с управлением при помощи временной шкалы (timeline-driven dispatching). В алгоритмах диспетчеризации с приоритетным управлением, точное время, в которое начнется или завершится какая-либо работа, заранее неизвестно. Время назначения каждой работы зависит от основанного на характеристиках данной работы приоритета относительно других задач, которые необходимо выполнить системе. В свою очередь, в алгоритмах диспетчеризации с управлением при помощи временной шкалы для составления расписания используется только временная шкала. Таким образом, время назначения и выполнения каждой работы известно заранее.

Составление расписаний с прерываниями обычно применяется в системах, в которых невелико время переключения контекста. Примерами систем реального времени, в которых реализованы многопроцессорные расписания с прерываниями, могут служить RT-Mach [8] и LynxOS [9]. Большинство систем реального времени с возможностью прерывания работ используют диспетчеризацию с приоритетным управлением, как и большинство систем, рассмотренных и предложенных в данной работе. Поэтому остановимся подробнее именно на этом классе алгоритмов.

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

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

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

Один из наиболее фундаментальных результатов в теории составления статических расписаний для систем реального времени с прерываниями получили Лю и Лейланд в работе [10], в которой изучались периодически возникающие работы. Они разделили алгоритмы составления расписаний с прерываниями работ на два класса — статических приоритетов и динамических приоритетов. В алгоритме, относящемся к классу статических приоритетов, приоритет каждой из работ задается тогда, когда эта работа назначается на выполнение и остается неизменным на всех этапах ее выполнения. Напротив, в алгоритме динамических приоритетов приоритет каждой работы может изменяться в процессе выполнения каждого из ее этапов. Для каждого из этих классов они указали (и доказали оптимальность в случае однопроцессорной системы) следующие алгоритмы:

1. Для класса статических приоритетов они предложили семейство алгоритмов, названное RM (Rate-Monotonic, «алгоритм монотонных коэффициентов»). Основная идея этих алгоритмов состоит в том, что всем работам назначаются неизменные приоритеты, которые вычисляются по некой формуле 7 коэффициенту) исходя из известных характеристик работ. Например, в [10] такие коэффициенты обратно пропорциональны периоду возникновения работ, и доказано, что в однопроцессорном случае, когда директивный интервал для каждой работы равен периоду ее возникновения подобный RM-алгоритм поиска допустимого расписания является точным, а в [23] рассмотрен случай, когда директивный интервал может быть меньше, чем период возникновения и для такого случая предложен RM-алгоритм, коэффициенты приоритетов работ в котором обратно пропорциональны соответствующим дедл айнам.

2. Для класса динамических приоритетов было предложено семейство алгоритмов, названное EDF (earliest deadline first, «вначале — ближайший срок завершения»). Основная идея этих алгоритмов заключается в том, что самой приоритетной в каждый момент времени среди доступных в этот момент работ считается та работа, директивный срок окончания которой наступит раньше всех остальных. В [24] показано, что в однопроцессорном случае оптимальным с точки зрения минимизации общего времени выполнения работ будет являться то расписание, которое в каждый момент времени выполняет ту работу, директивный срок завершения выполнения которой наступит ранее остальных.

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

Щей двух классов алгоритмов, предложенных Лю и Лейландом в 1973 году, оказались очень жизнеспособными, и по сей день в этом отношении не было изобретено ничего принципиально нового, то есть все разработанные до настоящего времени алгоритмы являются лишь усовершенствованными и дополненными RM и EDF. Недавно, например, один из RM-алгоритмов был выбран для составления расписаний на выполнение множества независимых автоматических работ, возникающих на Международной Космической 8.

Станции. Этот алгоритм встроен в бортовую вычислительную систему и напрямую поддерживается используемым там компилятором языка Ада.

Несмотря на то, что для однопроцессорной системы RM является оптимальным алгоритмом в случае периодически возникающих задач, a EDF — в апериодическом случае, ни один из них не является оптимальным в случае многопроцессорной системы. Более того, даже для однопроцессорных систем до сих пор не были решены задачи построения допустимых расписаний в случае, когда есть одновременно периодические и апериодические задачи (в данной работе рассматривается только чисто апериодический случай), а также случай построения синхронизованных расписаний ввода-вывода и вычислений (в Главе 3 настоящей работы впервые построен точный алгоритм для одного из частных случаев такой задачи). Изолированная задача распределения памяти при заданном расписании выполнения работ в однопроцессорной системе реального времени была изучена Сушковым и Логиновой в [17] и [49].

В многопроцессорном случае известно существенно меньше теоретических результатов, чем в однопроцессорном, во многом благодаря тому, что многие частные случаи задачи составления допустимого многопроцессорного расписания, как будет показано ниже, являются NP-трудными. В силу этого, как указано в [7], актуальным в настоящее время подходом, имеющим большое практическое значение, является рассмотрение упрощенных постановок и частных случаев исходной задачи, а также построение, наряду с точными, эвристических алгоритмов сравнительно невысокой вычислительной сложности. Два этих подхода и применяются в данной работе для построения алгоритмов, решающих задачу о многопроцессорном расписании в системе жесткого реального времени в ее различных вариантах.

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

Решение задачи построения вычислительных систем выполняется, как правило, поэтапно. В соответствии с рассматриваемой детализацией аппаратных и программных средств вычислительной системы выделяется несколько уровней проектирования. Как правило, таких уровней три: абстрактный, системный и уровень регистровых передач [25, 26, 27, 28]. На абстрактном уровне рассматриваются ограничения на сроки выполнения прикладной программы и аппаратные ресурсы и анализируется возможность построения системы с учётом выполнения этих ограничений. На системном уровне определяются характеристики основных структурных ко мпонентов вычислительной системы, например, процессоров и устройств ввода-вывода. На уровне регистровых передач происходит проектирование системы с использованием конкретной элементной базы для дальнейшей непосредственной реализации системы. К задачам регистрового уровня построения вычислительных систем относятся, например, задачи автоматического проектирования микросхем, трассировки плат и размещения микросхем на плате.

К настоящему времени уже разработан ряд промышленных систем, автоматизирующих решение задачи синтеза вычислительных систем на уровне регистровых передач [29, 30, 31]. Однако методов, полностью автоматизирующих решение задачи построения структур вычислительных систем на системном и абстрактном уровне, на данный момент не известно. Указанные причины обуславливают актуальность задачи разработки методов, которые позволили бы автоматизировать и ускорить процесс синтеза структур вычислительных систем. В [18] приведены ограничения на необходимые и достаточные производительности процессоров системы жесткого реального времени в случае периодически возникающих работ и отсутствия ограничения по памяти процессоров, задача синтеза системы в этом случае свелась к задаче целочисленного линейного программирования, в [32], [33], [34] и [35] предложены генетические алгоритмы синтеза рассматриваемых систем.

Целями настоящей диссертационной работы являются:

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

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

Данная диссертационная работа состоит из введения, постановки рассматриваемой задачи, пяти глав и заключения.

Заключение

.

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

В Главе 1 была рассмотрена задача поиска решений в многопроцессорной системе реального времени, в которой разрешены прерывания и переключения работ, переключения работ не требуют дополнительных затрат, связи между процессорами образуют полный граф, а ограничения по памяти отсутствуют. Для этого случая приведен известный точный полиномиальный алгоритм, который, однако, бывает затруднительно применять на практике в системах большой размерности из-за достаточно высокой степени полинома вычислительной сложности (0{тъпъj). Поэтому в данной главе были предложены два более быстрых эвристических алгоритма (0(тп) и При помощи значительного количества более 20 000) численных экспериментов при различных значениях параметров задачи исследованы границы корректности применения предложенных эвристических алгоритмов, получена сравнительная статистическая информация относительно некорректной работы алгоритмов (второй алгоритм медленнее, чем первый, зато обеспечивает в среднем в несколько раз меньший процент некорректной работы — 3% против 20%), даны рекомендации по их практическому применению.

Во второй главе условия задачи из первой главы усложнились введением временных затрат процессоров на прерывания и возобновления работ. Было рассмотрено три различных модели образования таких затрат, при условии что во всех этих случаях затраты на прерывания и возобновления малы относительно характерной длины директивных интервалов работ. Предложенные в Главе 1 эвристические алгоритмы были адаптированы для этого случая и было определено количество прерываний, которое генерирует в построенном допустимом расписании каждый из этих алгоритмов (соответственно, 2(п-1)т и (я-1)). Несмотря на то, что для решения задачи из предыдущей главы второй алгоритм был предпочтительнее в смысле корректности его работы, в этом варианте задачи из-за того, что он генерирует большее количество прерываний, чем первый, начиная с некой относительной величины прерывания первый алгоритм становился предпочтительнее. Поэтому для каждой из трех моделей образования затрат на переключения было исследовано, при каких значениях параметров, задающих отношение величины прерываний к характеристической длине директивных интервалов работ первый алгоритм становится предпочтительнее второго в смысле более высокой вероятности корректности его работы.

В Главе 3 рассмотрен ранее неисследованный вариант задачи о поиске допустимого расписания в многопроцессорной системе с ограничениями по памяти процессоров и конечной скоростью ввода-вывода данных, в котором процессоры, помимо скорости выполнения работ, характеризуются скоростью загрузки данных. Рассмотрен случай одинаковых директивных интервалов для всех работ. Для однопроцессорного случая построен точный алгоритм, решающий задачу за полиномиальное время 0{n2ogn} и теоретически обоснована его корректность. Далее рассмотрен многопроцессорный случай этой задачи, доказана ее NP-трудность как в случае когда переключения работ с процессора на процессор разрешены, так и в случае когда они не допускаются. Поэтому для ее практического решения был разработан эвристический алгоритм вычислительной сложности 0{n2mogri), котрый, как показали проведенные численные эксперименты, эффективно решает задачу, в случае, когда максимальные длительности выполнения работ и загрузки данных существенно меньше, чем длина общего директивного интервала всех работ. Представлено теоретическое объяснение этого полученного эмпирически свойства алгоритма, даны рекомендации по его практическому применению. Для выявления случаев некорректной работы эвристического алгоритма для рассмотренной в данной главе задачи был также построен точный алгоритм и дано теоретическое обоснование его корректности.

В Главе 4 рассмотрена задача поиска допустимого расписания в многопроцессорной системе реального времени с ограничениями по объему памяти процессоров в случае неполного графа связей между процессорами. Для некоторого упрощения условий задачи считалось, что все процессоры работают дискретными синхронизованными по времени тактами. Обоснована NP-трудность этой задачи. Для решения задачи построена многопродуктовая потоковая сеть специального вида и доказано, что решение исходной задачи существует тогда и только тогда, когда в построенной сети существует многопродуктовый поток, обладающий рядом указанных свойств. Показано, что построение расписания сводится к нахождению такого потока, которое, в свою очередь, сводится к решению задачи булева линейного программирования. Указаны наиболее эффективные псевдополиномиальные алгоритмы решения такой задачи.

В пятой и заключительной главе работы была рассмотрена задача синтеза, то есть задача построения многопроцессорной системы, в которой при заданном множестве работ допустимое расписание с прерываниями заведомо существует. Была указана система неравенств, задающая допустимую с точки зрения существования допустимого расписания область производительности процессоров в случае, когда ограничения на объем памяти процессоров отсутствуют. Были указаны методы решения возникающих в связи с этим различных оптимизационных задач (например, минимизация суммы производительностей процессоров), которые в данном случае сводятся к решению задачи целочисленного линейного программирования. Во второй части Главы 5 была рассмотрена ранее неисследованная задача синтеза системы реального времени в случае ограничений по объему памяти процессоров (считается, что загрузка и выгрузка данных работ из памяти процессоров осуществляется за пренебрежимо малое время). Была получена система неравенств, связывающая искомые производительности процессоров и их объемы памяти с параметрами работ. Было доказано, что выполнение этой системы является необходимым и достаточным условием для существования в рассмотренной системе допустимого расписания с прерываниями, то есть решения поставленной задачи синтеза. Были указаны методы решения возникающих здесь различных оптимизационных задач, которые в данном случае сводятся к решению задачи целочисленного квадратичного программирования с булевскими переменными.

Наиболее перспективным представляется развитие предложенных в данной работе методов и подходов по следующим направлениям:

— построение эффективных эвристических алгоритмов, решающих задачу поиска допустимого расписания в постановке Главы 4 (многопроцессорная система с ограничениями по памяти и неполным графом связей между процессорами) существенно быстрее, чем указанный там псевдополиномиальный точный алгоритм, неприменимый в практических задачах большой размерности;

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