автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Методика повышения эффективности статического планирования для мультипроцессорных систем жесткого реального времени

На правах рукописи

ДОКУЧАЕВ АНДРЕЙ НИКОЛАЕВИЧ

/

МЕТОДИКА ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ СТАТИЧЕСКОГО ПЛАНИРОВАНИЯ ДЛЯ МУЛЬТИПРОЦЕССОРНЫХ СИСТЕМ ЖЕСТКОГО РЕАЛЬНОГО ВРЕМЕНИ

Специальность 05.13.01 — Системный анализ, управление и обработка информации (технические науки)

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

IЯ НОЯ 2013

Санкт-Петербург 2013

005540638

005540638

Работа выполнена на кафедре «Системы обработки информации и управления» Балтийского государственного технического университета «ВОЕНМЕХ» им.

Д.Ф. Устинова

Научный руководитель:

кандидат технических наук, доцент Кононов Олег Александрович

Официальные оппоненты:

доктор технических наук, профессор Никифоров Виктор Викентьевич

кандидат технических наук, доцент Душутина Елена Владимировна

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

Защита состоится « 24 » декабря 2013 г. в 14 часов на заседании диссертационного совета Д.212.010.03 Балтийского государственного технического университета «ВОЕНМЕХ» им. Д.Ф. Устинова по адресу: 190005, Санкт-Петербург, 1ая Красноармейская ул., д. 1.

С диссертацией можно ознакомиться в библиотеке Балтийского государственного технического университета «ВОЕНМЕХ» им. Д.Ф. Устинова. Автореферат разослан: « 18» ноября 2013 г.

Ученый секретарь Диссертационного совета

Ю.В. Петров

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

К моменту проведения данного диссертационного исследования сформировалось три основных подхода к решению задачи планирования в мультипроцессорных СРВ:

1. Динамическое планирования (планирование с использованием динамических приоритетов задач) - подход, характеризующийся проведением основных мероприятий планирования непосредственно во время эксплуатирования системы посредством изменения приоритетов.

2. Раздельное статическое планирование - подход характеризуется закреплением групп задач за различными исполнительными ресурсами с фиксированными приоритетами, заданными на этапе проектирования.

3. Глобальное статическое планирование - при реализации данного подхода все задачи могут потреблять ресурсы произвольных исполнительных ресурсов, при этом приоритеты являются фиксированными и заданными на этапе проектирования.

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

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

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

Объект исследования. Объектом исследования является мультипроцессорная событийно-управляемая система жесткого реального времени.

Предмет исследования. Предметом исследования являются процедуры статического планирования событийно-управляемых мультипроцессорных СРВ.

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

Задачи исследования:

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

2. Определение и обоснование выбора математической модели задачи (объекта планирования) мультипроцессорной СРВ, а также ее уточнение.

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

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

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

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

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

На защиту выносятся следующие научные результаты:

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

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

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

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

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

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

2. Разработаны процедуры планирования задач, отличающиеся от известных использованием модели объекта планирования, предложенной в настоящей работе. Их исследование позволило установить, что распределение

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

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

4. Разработаны методы устранения допущений, заложенных в предложенной математической модели задачи, что позволяет применять на практике процедуры планирования ее использующие при проектировании СУ, выполненных на основе мультипроцессорных событийно-управляемых СРВ.

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

Внедрение. Разработанные в рамках настоящего диссертационного исследования алгоритмы и методы планирования и анализа использованы в ОАО «Концерн «НПО «Аврора» в составе математического и программного обеспечения систем управления корабельными техническими средствами. Предложенные способы повышения эффективности распределения ресурсов мультипроцессорных и многоядерных СРВ при обработке поступающего потока запросов на планирование внедрены на предприятии ООО «СВД Встраиваемые Системы» в виде программного модуля диспетчеризации (ПМД). По результатам практического использования ПМД в рамках производственной деятельности предприятия принято решение о включении данного модуля в состав «Защищенной операционной системы реального времени «Нейтрино» (КПД. 10964-01)», соответствующей требованиям к средствам вычислительной техники (СВТ) по 3 классу защиты информации от несанкционированного доступа (НСД), 2 уровню контроля отсутствия не декларированных возможностей (НДВ), а также соответствию реальных и декларированных возможностей (РДВ) - сертификат МО РФ №1740 от 20.12.2011.

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

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

общероссийских научных конференциях, в том числе на: II общероссийской молодежной научно-технической конференции «Молодежь, Техника, Космос» (Санкт-Петербург, 2010 г.); III общероссийской молодежной научно-технической конференции «Молодежь, Техника, Космос» (Санкт-Петербург, 2011 г.); I международной научно-практической конференции «Применение инновационных технологий в научных исследованиях» (Курск, 2010 г.); II международной научно-практической конференции «Применение инновационных технологий в научных исследованиях» (Курск, 2011 г.); VIII международной научно-технической конференции «Современные инструментальные системы, информационные технологии и инновации» (Курск, 2010 г.); IX всероссийской научно-практической конференции «Молодежь и современные информационные технологии» (Томск, 2011 г.).

Публикации. По теме диссертационного исследования опубликовано 14 работ, включая 5 статей в журналах, включенных в перечень изданий, рекомендованных ВАК, 7 работ в материалах международных и общероссийских научных конференций, а также 1 свидетельство о государственной регистрации программы для ЭВМ.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и списка литературы, включающего 118 наименований. Основная часть работы содержит 131 страницу, 20 рисунков и 15 таблиц.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

История исследования вопроса распределения вычислительных ресурсов в СРВ связана с именами таких ученых, как: С. Liu, I. Layland, А. Мок, J.P. Lehman, L. Sha, R. Rajkumar, J.P. Lehoczky, S.K. Dhall, M. Klein. Среди современных исследователей наиболее известны: M.B. Данилов, В. Andersson, J. Jonsson, R.I. Davis, A. Burns, G. Lipari, E. Bini, G. Buttazzo, M. Borger, D.Y. Ding, M. Joseph, J. Andersson, S.A. Baruah, T.P. Baker, M. Cirinei, L. Lundberg, M. Bertogna, Nan Guan, M. Stigge, Wang Yi, Ge Yu, R.A. Veltre; J. Carpenter, S. Funk, P. Holman, A. Srinivasan, J. Goossens и другие. На протяжении четырех десятилетий исследования данной проблемы было предложено множество подходов к планированию систем жесткого реального времени, имеющих в своем распоряжении как один исполнительный ресурс, так и несколько. На первом этапе исследований (до 1978 г.) наиболее значимые результаты

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

- Планирование с динамическими приоритетами (Scheduling with Dynamic Priorities) — подход, при котором объекты планирования не обладают фиксированными приоритетами в то время, как решения по назначению задач на выполнение принимаются в процессе функционирования системы планировщиком. Необходимо отметить, что разрабатывались методы планирования с динамическими приоритетами, относящиеся как к процедурам глобального, так и раздельного планирования. В первом случае подразумевается существование единой очереди задач для всех имеющихся исполнительных ресурсов. Для раздельного же планирования предусматривается использование изолированных очередей задач для каждого планирования. Таким образом, для последних параллельно должна решаться задача эффективного распределения задач по очередям, а соответственно и между исполнительными ресурсами.

- Планирование со статическими приоритетами (Scheduling with Static Priorities; Scheduling with Fixed Priorities) - подход, при котором каждой задаче реального времени ставится в соответствие фиксированный числовой идентификатор (приоритет), характеризующий степень его критичности. При этом способе распределения вычислительных ресурсов порядок назначения задач на выполнение определяется исключительно их приоритетами, что позволяет осуществлять мероприятия по анализу выполнимости математического обеспечения СРВ, эффективному назначению приоритетов и распределению вычислительных ресурсов уже на этапе проектирования системы.

Необходимо отметить, что в рамках обозначенного временного интервала мультипроцессорное планирование со статическими приоритетами рассматривалось исключительно с позиции процедур раздельного планирования. Причиной подобного недооценивания глобальных методов стало открытие в 1978 г. эффекта Далла. Исследование данного явления ошибочно переводило глобальное мультипроцессорное планирование в разряд неэффективных практик распределения вычислительных ресурсов в событийно-управляемых систем жесткого реального времени, поскольку демонстрировало при указанных условиях невозможность успешного выполнения ряда систем, состоящих из т+1 задачи, в СРВ с т ИР даже при незначительных требованиях к вычислительным ресурсам мультипроцессора. Исследования В. Andersson и J. Jonsson позволили в 2000 г. объяснить эффект Далла с позиции разнородности задач по части требований к вычислительным

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

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

- Динамическое планирование не поддерживается ни одной коммерческой ОС РВ. В данном аспекте, надежды на применение динамического планирования в существующих проектах на поздних стадиях реализации при использовании коммерческих ОС РВ отсутствуют. Необходимо отметить, что основные международные стандарты ОС РВ регламентируют лишь статические виды планирования. Среди подобных стандартов присутствуют: POSIX (Portable Operating System Interface based on UNIX operating systems), OSEK/VDX (Open systems and the corresponding interfaces for automotive electronics / Vehicle Distributed eXecutive), AR1NC - APEX (Avionics Application Standard Software Interface - APplication/EXecutive) и MICRO-ITRION (Industrial TRON - The Real-time Operating system Nucleus).

- Динамическое планирование менее предсказуемо (время отклика задач на событие достигает минимума лишь при статическом распределении вычислительных ресурсов).

- Динамическое планирование практически не поддается контролю (при статическом планировании для уменьшения времени отклика произвольной задачи достаточно повысить ее приоритет).

- Статическое планирование в оби/ем случае проще реализуемо, так как отсутствует необходимость контроля абсолютных значений крайних сроков завершения всех N задач. Например, для СРВ с единственным исполнительным ресурсом, известны реализации статического планирования, характеризующиеся сложностью вычислений 0(1), в то время как динамическое EDF планирование реализуемо лишь за 0(log N).

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

К наиболее известным коммерческим ОС РВ, широко применяющимся в отечественной промышленности относятся QNX Neutrino RTOS (QNX Software Systems), VxWorks (Wind River Systems) и oc2000 (НИИСИ РАН). Ввиду поддержки всеми упомянутыми ОС РВ международного стандарта POSIX применение в них планирования с динамическими приоритетами не предусмотрено. При учете данных обстоятельств, а также по результатам анализа материалов, посвященных современным исследованиям в области управления вычислительными ресурсами в мультипроцессорных СРВ, было выявлено, что для отечественной промышленности особо актуальны

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

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

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

где Ир(т.) - подмножество задач гчей приоритет выше, чем приоритет задачи т.; С^ - время, требуемое задаче для успешного выполнения; -

период порождения экземпляров задач; т - число исполнительных ресурсов; /X - крайний срок завершения задачи. Выражение (1) позволяет ввести

разновидность задач - задачи ^о-типа, характеризующиеся функцией (р^..

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

С.

от базовой процедуры планирования, является: — > -- (базовый метод

На следующем этапе проведено исследование влияния задач <р-типг на эффективность планирования мультипроцессорных событийно-управляемых

(1)

Т. Зт-2

С

RM-US), либо -

(базовый метод 8М-и8).

СРВ. При этом генерировались системы задач с равномерно распределенными параметрами в количестве 10000 наборов для каждой пары (и, U), где п - число задач, U - суммарная вычислительная нагрузка на исполнительные ресурсы

{U = £С. /Т. ). При этом для каждой системы задач в наборе посредством (1) /=1 '' '

производился анализ влияния задач ^г>-типа на осуществимость планирования методом RM-US. Результаты исследования представлены на рис. 1, где F -количество невыполнимых (по причине наличия задач <р-типа) наборов задач.

Рис. 1. Влияние задач (/»-типа на эффективность планирования мультипроцессорных СРВ при

m=4 (а) и т=8 (б)

Анализ результатов исследования влияния объектов <р- типа на планирование мультипроцессорных СРВ показывает, что наличие единственной задачи </>типа является достаточным условием невозможности успешного выполнения всей системы в рамках глобального статического планирования. Для учета подобных явлений в процедурах планирования в рамках настоящего исследования предложены следующие подходы к распределению вычислительных ресурсов (базовые методы планирования RM-US и SM-US):

1. Процедуры планирования RM-US/light и SM-US/light подразумевают назначение задачам (р-тнпг. наивысших приоритетов, что позволяет исключить их влияние на эффективность распределения ресурсов.

2. Процедуры планирования RMMS-FP и SMMS-FP подразумевают наделение высокоприоритетных тяжелых задач способностью периодически принудительно освобождать исполнительный ресурс на заданный интервал

С DÇ

времени В? с периодом ТУ .

3. Процедуры планирования RM-US/part и SM-US/part предполагают группирование высокоприоритетных тяжелых задач и закрепление их за выделенными исполнительными ресурсами.

Для анализа выполнимости систем задач, использующих {Ш-иЗЛ^М, 8М-и8/Пц1П, ЯМ-иБ/раП и 8М-Ш/раП, применимы с незначительными изменениями известные методики анализа выполнимости математического обеспечения. Подобные методики зачастую опираются на оценку величины времени отклика задач (К,), характеризующую фактическое время выполнения задачи т. с учетом потребления вычислительных ресурсов

высокоприоритетными задачами. Основное положение гласит: если для каждой т. выполняется К- < О., система задач успешно выполнима в рамках

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

Для оценки времени отклика легких задач, при использовании процедур планирования ЯММБ-РР и БММБ-РР, допустимо использование, предложенного в настоящей диссертационной работе, выражения:

н М ¥ ¿1

Л,=С/ +

Гл." / с Г/?.] \ >

< тк + тах 0 ,Я.-Ск- к. ск К / тк -ч )

(2)

где Л - число тяжелых задач; приоритет г- меньше приоритета (тяжелым задачам назначаются максимальные приоритеты); а также:

1 Т)

Су + шах

0,гшп

сг

тт

Я .,/?.-Г I

я.

I

т.

Л

т. ]

■с.

■ (3)

При этом необходимо воспользоваться заменой тяжелых объектов

планирования г .=(С .;7\.) соответствующими моделями: г .= С-;7\ , где J J J J J J у

с'к=тк5-вк->тгтг-

При помощи (2) и (3) можно осуществлять анализ выполнимости системы задач, использующих процедуры планирования ЯММБ-РР и БММЗ-РР. При этом необходимо задаться начальным приближением для рекуррентного

выражения (2): Я^ = С.. Тем не менее, известно, что выражение (2) обладает

изрядной долей пессимизма.

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

исполнению, не может быть назначена на выполнение ввиду занятости

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

Руководствуясь подобными соображениями рекуррентное уравнение (2) преобразуется в:

Я.=С.+

I

7 е Л/ЧО 1

1МС2(Я.) +

] е Мах(1,т-1)

-П }

1ШЕР2{Я.)

(4)

причем: = Ы!)!СЩС] + тт(С^., Л^С(/,)7\); Щ =

IV

N02

Щ = Ып. 7

N02

(£)С. + тт(С.,Ь- ЫЫС2ЩТВБ)-, ММС2Щ =

ЦТ._ 55

ЦТ

7

/у/2(«) =

т\п{]УС12(Я.),Я.-С.+\),т . еО 7 г / ; "у

тЩУ^1 (Л.),Д. - С. + \),г . <£ О

¡уС12щ = мС12щС'^ + т1п(с' ^ + ^ _ с'

7

7

7

7 7

Л'С/2(/,)7,А5);

/гр Щ = N(¡I ЩС . + тт(С Ь + Я - С . - И^1 (ЦТ.);

J J 3 3 3 3

№.12щ =

(ь + я.-с' )/тВ5

7 7/7

(ь+я.-с .)/т.

7 77 7

В выражении (4) под О понимается совокупность тяжелых задач, реализующих принудительные периодические вытеснения. Параметр (Я.) -

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

включает учет величины интерференции от экземпляров задач,

выполняющихся до момента порождения экземпляра т■.

Таким образом, использование в сочетании с (4) моделирующих задач т .

позволяет осуществлять анализ выполнимости математического обеспечения СРВ при планировании с принудительными периодическими вытеснениями.

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

При оценке числа вытеснений в мультипроцессорных СРВ необходимо учитывать как приоритеты задач, так и их распределение между исполнительными ресурсами. Рассмотренное множество задач Я = {Т|, г^.....тп) выполняется в рамках глобального статического

планирования гДе /п№ ~ правило назначения

" А J J /

приоритетов и / - правило перепланирования, включающее

А 7 7

принцип назначения исполнительных ресурсов. Величины V® с Л и VI с Л

есть подмножества активных задач непосредственно перед возникновениему'-го события перепланирования и после него, причем V/: | V® ¡< т; | И. |< т. Задачи

характеризуются = (С\,7\,О.,Р.,А.(/^)), где Р. - приоритет, - число

вытеснений за время [0;/^], причем \//:Р. С каждой задачей

V V ?

ассоциируются события перепланирования е = Ух^Л,

характеризующееся моментами времени порождения и завершения ее экземпляров. Для оценки числа вытеснений для у наиболее приоритетных задач параметр выбирается кратным величине НОК(Т^)\ к е [1;./]. При

достаточном применима оценка числа вытеснений (переключений

исполнительных ресурсов):

_ Д,(/с)

А (( )= * д (5)

к 5 1./Т, о к

При выполнении условия:

Уе :тееЛ;

З((е*,теук):тк^;гк^);е*к; (б)

7'

можно утверждать, что событие \е1,те\ является источником вытеснения

экземпляра задачи г, в момент свершения события. Выражение (6) позволяет к

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

в . ^ . г ] 8

1. Для выполнить

2.

3. Для всех к=1..п выполнить

4. Если г. е V® л г, £ а к Ф е то

к ] к ) 5" А*<'*> = А*<'*> + 1

Посредством выражения (5) осуществим учет влияния переключений исполнительных ресурсов на эффективность планирования:

С -> С\ + со■ А.(/^). На рис. 2 представлены результаты оценки относительного

прироста в эффективности распределения вычислительных ресурсов для методов БМИБ-РР (а), БМ-Ш/раП (б) и БМ-Ш/ИдЫ: (в) по отношению к базовой процедуре БМ-Ш при ш=4 и различных затратах на единичное переключение исполнительного ресурса. Анализ эффективности производился при помощи выражения (4). Величина Р3 (выраженная в процентном отношении) характеризует относительный прирост числа успешно выполняющихся наборов задач. Абсолютные значения (Р2, %) эффективности планирования приведены в таблице 1, причем со - длительность единичного переключения.

Таблица 1. Результаты экспериментальной оценки эффективности методики

и, % 80 8! 82 83 84 85 86 87 88 89

о>=0% Р2,%:8М-118 49.07 43.06 37.88 32.89 27.40 22.50 18.01 13.90 9.76 7.00

Р2,%:8ММ8-РР 65.10 58.97 55.01 49.30 43.71 37.98 33.41 26.96 20.96 16.21

03=1% Р2,%:8М-и8 48.39 42.39 37.28 32.41 26.92 22.08 17.63 13.62 9.57 6.83

63.77 57.76 53.49 47.93 42.47 36.64 32.38 26.10 20.33 15.65

оз=2% Р2,%:8М-Ш 47.69 41.57 36,62 31.79 26.41 21.71 17.19 13.33 9.41 6.67

Р2,%:8ММ8-РР 62.46 56.35 52.10 46.50 42.33 35.57 31.35 25.24 19.71 15.00

о)=5% Р2,%:8М-и8 45.60 39.78 34.82 30.17 25.16 20.57 16.42 12.52 8.80 6.33

58.49 52.64 47.96 42.87 37.78 32.33 28.51 22.91 17.54 13.34

Анализ полученных результатов позволяет утверждать, что эффективность планирования методами ЗМ-Ш/рай и ЭМ-ШЛ^Ы существенно ниже, чем у метода БММЗ-РР, причем, на эффективность распределения вычислительных ресурсов первого метода оказывают колоссальное влияние именно переключения исполнительных ресурсов. В тоже время процедура планирования БМ-иЗ/^Ы оказывается наименее чувствительной к наличию неидеальных переключений исполнительных ресурсов, однако, относительный прирост эффективности данного метода на высоких нагрузках и оказывается незначительным.

Можно заметить (таблица 1), что в диапазонах и е [70;79] и и е [80;89] при со = 1% (1% от времени исполнения задачи, характеризующейся и = 50% и максимально возможным периодом) наблюдается абсолютный прирост эффективности процедуры 8ММ8-РР по отношению к базовому методу ЗМ-Ш в среднем на 10.68% и 13.90%, в тоже время, при со = 5% прирост естественным образом снижается до соответствующих 9.08% и 11.42%. Для СРВ, имеющих /я = 8 ИР, данная величина оценивается как 8.14% и 14.95% при со = 1%; и 7.34% и 13.02% при со = 5%.

1 10 = 0% 2 и) = 1% 3 ш = 2% 4 ш = 5 % 5 и) = 10%

е' Г

1 з\Ч Ж

а)

1 со = 0%

2 со = 1%

3 со = 2%

4 со = 5%

5 со = 10%

70 75 80 85 90 60 65

У

85 90

б)

1 У V2

1 со = 0% 2 ш = 1% 3 ш = 2% 4 ш = Е% 5 о) = 10%

/у 'А,

в)

Рис. 2. Относительный прирост эффективности планирования при использовании разработанной методики и учете переключений исполнительных ресурсов

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

пропуски крайних сроков завершения клиентами т.. Для т. (4) принимает вид:

V

■С.+

I

] е МО

J v I

у е Мах(/', пг - 1)

] '

/ т

+ 0

Я'

(7)

5

где 0 = 8 + В Я Я Я

8 /(Гю-Г) Я Я Я

ж ........ • ; ,9а /

ГГ*'""''"'^::

1А.....,.,1..,.....,1 ,1,...... И „

Щ Обработка і;іпрое;і

— Блокирование іадачи

— Разблокирование задачи

/ А? 4С........

/ \ 1, , г

і

Пропуск задачей крайнего срока б)

Рис. 3 Реализация сервера в виде высокоприоритетной тяжелой задачи при планировании методами ІШ.Ш-УР/ХММЗ-РР

Поскольку Г| на рис. 3(а) выполняется на высоком приоритете, обработку

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

длительность обработки типового запроса серверной задачей г^ при отсутствии

принудительных вытеснений. В большинстве случаев ¿>| может полагаться

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

определяется как 8. = 8. + рВ. , где р характеризует число вытеснений,

произошедших за время обработки запроса.

Оценка влияния серверных задач, разработанных с применением принудительных периодических вытеснений, подразумевает использование выражения (7), результаты исследования представлены на рис. 4. Обозначены следующие сценарии: - планирование базовым методом }2 -

планирование в отсутствии взаимодействующих задач, ]3 - планирование при наличии единственной легкой клиентской задачи; )4 - планирование при наличии двух легких клиентских задач.

Величина J. = 1 / п. (дробность) характеризует степень неравномерности

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

60

4(1

20

80

85 б)

■ jl ■ j2 Bj3

□ H

90

Рис. 3.7. Эффективность планирования при наличии межзадачного взаимодействия (тяжелый сервер) для J■ = 0.5 (а) и J. = 0.25 (б)

При разработке оценки (4) использовались моделирующие объекты планирования, что обусловило привнесение погрешности при неравномерном распределении принудительных вытеснений. Для ее устранения предлагается воспользоваться в ИТОГОВОЙ оценке Ri следующим приемом. При вычислении

NCI CI2

интерференций / (Л.)и I.(R.) для тяжелых задач r^eQ таких, что

T. >TBS-п

NCI CI 2

величины W. (L) и W.(L) в выражении (4) могут

J J J оцениваться как:

W^C2(L) = N^C{L)Cj + min {С j,N^CC Щ ■ cj + min(C\

- N (L)T. - N NCC ( L)T BS )); J J J J

wÇI2{L) = n'j1 (L)Cj + min(C;.,/vyc/(.L)C . + min(c\,L + R.-Cj • -N?1 (L)Tj - (L)T?S )),

(7)

NNCC{L) = J

причем, Nj'^ (L) =

L-NNC{L)T. _J J

LIT. J

Y ВS

nÇci(L)=

, NCj!(L)--

,CI,

L + R.-C . J J

T.

J

L + R.-C.-N. (L)T. J J J J

jBS

В результате дополнения выражения (4) посредством величин IV С/2

и IV (/,) (7) получена уточненная оценка эффективности распределения

вычислительных ресурсов ИР процедурой планирования 11ММ8-РР. В диапазонах (7б[70;79] и £/е[80;89] при « = 1%, т = 4 и п = 2т + 1 наблюдается абсолютный прирост эффективности Г2 (число выполнимых наборов задач в рамках рассматриваемой процедуры планирования и оговоренных условий) в среднем равный 11.03% и 17.15% соответственно. В тоже время, при увеличении накладных расходов на переключение исполнительных ресурсов до а> = 5% прирост естественным образом снижается до 9.56% и 14.86% соответственно.

В таблице 2 приведены абсолютные значения эффективности планирования.

Таблица 2. Уточнение экспериментальной оценки эффективности методики

и, % 80 81 82 83 84 85 86 87 88 89

01=1% ЇЇ2, Уо^М-Ш 47.76 43.64 38.17 32.18 27.03 22.50 17.22 13.02 10.19 6.25

Р2, %:5ММ8-РР 64.59 61.50 56.49 50.55 46.01 40.39 34.88 30.55 25.58 19.62

«=5% Р2, %:8М-Ш 44.99 41.05 35.78 29.95 25.16 20.89 15.99 11.93 9.35 5.88

Р2, %:5ММ5-РР 59.52 56.47 51.68 46.03 41.30 36.55 31.45 27.30 22.48 17.39

Очевидно, что наличие моделирующих задач т . - в выражении

оценки времени отклика (4) оказывает ощутимое негативное влияние на осуществляемую с его помощью оценку эффективности распределения вычислительных ресурсов ИР мультипроцессорных событийно-управляемых СРВ.

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

ЗАКЛЮЧЕНИЕ

Основные результаты диссертационной работы можно кратко представить в следующем виде:

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

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

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

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

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

6. Результаты экспериментальных исследований подтвердили высокую эффективность предложенного подхода (например, при и е [80;89] число выполнимых наборов задач возросло на и 17.15%) по сравнению с известными рассмотренными процедурами планирования, что подтверждается как аналитическими, так и модельными исследованиями. В результате практического использования разработанной методики зафиксирован 25% экономический эффект.

ПУБЛИКАЦИИ ПО ТЕМЕ ИССЛЕДОВАНИЯ

Публикации в ведущих рецензируемых изданиях и журналах, рекомендованных ВАК:

1. Докучаев А.Н. Метод глобальной мультипроцессорной диспетчеризации для встраиваемых систем специального назначения и систем реального времени // Горный информационно-аналитический бюллетень (научно-технический журнал), №12, Москва, 2011. - С. 149-154.

2. Докучаев А.Н. Задачи ф-типа как средство расширения границ применимости статической диспетчеризации в мультипроцессорных системах реального времени при высокой нагрузке // Системы управления и информационные технологии, №3.2(45), Воронеж, 2011. - С. 224-229.

3. Докучаев А.Н. Защищенная ОС РВ нового поколения: особенности архитектуры и средства защиты информации // Автоматизация в промышленности, №201202, Москва, 2012. - С. 51-55.

4. Докучаев А.Н. Особенности диспетчеризации сверхлегких задач в мультипроцессорных вычислительных системах реального времени // Информационные технологии, №2, Москва, 2012. - С. 14-18.

5. Докучаев А.Н. К оценке эффективности механизмов диспетчеризации мультипроцессорных систем реального времени с учетом влияния длительных блокировок // Программная инженерия, №9, Москва, 2012. — С. 2-7.

Публикации в других изданиях:

1. Докучаев А.Н. Алгоритмы планирования задач в операционных системах реального времени, ориентированных на мультипроцессорные архитектуры. // "Молодежь. Техника. Космос": труды 11 Общероссийской молодежной научно-технической конференции. - БГТУ «Военмех», С-Пб.: 2010г.-С. 223-225.

2. Докучаев А.Н. Оценка времени отклика задач в мультипроцессорных системах реального времени при частотно-монотонном планировании с принудительными периодическими вытеснениями // Материалы VIII Международной научно-технической конференции "Современные инструментальные системы, информационные технологии и инновации". -ЮЗГУ, Курск.: 2010г. - С. 115-119.

3. Докучаев А.Н. Измерение времени переключения контекстов задач в мультипроцессорных вычислительных системах реального времени при приоритетно-управляемом планировании // Материалы Международной научно-практической конференции "Применение инновационных технологий в научных исследованиях". - ЮЗГУ, Курск.: 2010г. - С. 261-265.

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

Молодежь и современные информационные технологии: материалы IX Всероссийской научно-практической конференции студентов, аспирантов и молодых ученых с международным участием. Т. 2. - ТПУ, Томск, 2011г. - С. 18-19.

5. Докучаев А.Н. Оценка числа вытеснений при глобальной мультипроцессорной диспетчеризации в системах жесткого реального времени // "Молодежь. Техника. Космос": труды III Общероссийской молодежной научно-технической конференции. - БГТУ «Военмех», С-Пб.: 2011г. - С. 167169.

6. Докучаев А.Н. Исследование применимости алгоритмов мультипроцессорной диспетчеризации RM-US и SM-US в системах реального времени с высокой нагрузкой // "Молодежь. Техника. Космос": труды III Общероссийской молодежной научно-технической конференции. - БГТУ «Военмех», С-Пб.: 2011г. - С. 169-171.

7. Докучаев А.Н. К вопросу об интерференционном характере методов оценки времени отклика в мультипроцессорных системах реального времени // Сборник трудов II Международной научно-практической конференции "Применение инновационных технологий в научных исследованиях". - ЮЗГУ, Курск, 2011 г.-С. 189-194.

8. Докучаев А.Н., Третьяков В.А. Особенности реализации комплекса средств защиты информации в сертифицированном изделии «Защищенная операционная система реального времени «Нейтрино» (КПДА. 10964-01)» // Системы управления и обработки информации: научн.-техн. сб. / ОАО «Концерн «НПО «Аврора», СПб., 2012, №24. - С. 43-46.

Патенты н свидетельства:

1. Свидетельство о государственной регистрации программы для ЭВМ № 2011617924 от 10.10.2011 «Оценка диспетчеризируемости задач в мультипроцессорных системах реального времени при использовании методов планирования, базирующихся на принудительных периодических вытеснениях».

Подписано в печать 15.11.2013 г. Заказ № 0048 Формат бумаги 60x84/16.Бумага офсетная. Тираж 100 экз. усл. п.л. 1,5 Типография ООО «Сан Принт» 1-я Красноармейская д.24.

БАЛТИЙСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

«ВОЕНМЕХ» им. Д.Ф. УСТИНОВА

На правах рукописи

04201454712 Докучаев Андрей Николаевич

МЕТОДИКА ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ СТАТИЧЕСКОГО ПЛАНИРОВАНИЯ ДЛЯ МУЛЬТИПРОЦЕССОРНЫХ СИСТЕМ ЖЕСТКОГО РЕАЛЬНОГО ВРЕМЕНИ

05.13.01 - Системный анализ, управление и обработка информации

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель: кандидат технических наук Кононов Олег Александрович

Санкт-Петербург - 2013

ОГЛАВЛЕНИЕ

Основные термины и условные сокращения.......................................................4

Введение...................................................................................................................6

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

1.1. Обзор подходов к планированию задач в системах жесткого реального времени...............................................................................................................15

1.1.1. Классификация алгоритмов планирования задач реального времени ..........................................................................................................................17

1.1.2. Классическая теория частотно-монотоннного анализа....................22

1.1.3. Развитие идей частотно-монотонного анализа для мультипроцессорных систем реального времени.......................................27

1.2. Модели распределения вычислительных ресурсов при статическом мультипроцессорном планировании...............................................................30

1.2.1. Традиционные модели распределения вычислительных ресурсов 30

1.2.2. Современные модели распределения вычислительных ресурсов .. 35 Выводы по главе 1.................................................................................................42

2. Методика повышения эффективности использования вычислительных ресурсов при статическом планировании мультипроцессорных систем жесткого реального времени................................................................................45

2.1. Постановка задачи повышения эффективности планирования.............45

2.1.1. Уточнение классификации объектов планирования........................46

2.1.2. Анализ применимости уточненной классификации для решения поставленной задачи......................................................................................53

2.2. Системные основы оценки эффективности планирования....................57

2.2.1. Подходы к моделированию задач реального времени.....................57

2.2.2. Методы анализа выполнимости планирования в мультипроцессорных системах жесткого реального времени..................63

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

2.3.1. Поиск методов эффективного статического мультипроцессорного планирования..................................................................................................69

2.3.2. Разработка методов анализа выполнимости объектов планирования ..........................................................................................................................75

Выводы по главе 2.................................................................................................87

3. Исследование особенностей применения разработанной методики в реальных системах жесткого реального времени..............................................89

3.1. Уточнение методов анализа выполнимости объектов планирования для применения в реальных системах....................................................................89

3.1.1. Влияние переключений исполнительных ресурсов на оценку эффективности планирования.......................................................................89

3.1.2. Взаимодействие объектов планирования..........................................99

3.1.3. Устранение допущений в формировании моделирующих объектов при неравномерном распределении принудительных вытеснений........105

3.2. Анализ характеристик предложенных методов....................................112

Выводы по главе 3...............................................................................................118

4. Практическое использование разработанной методики.............................120

4.1. Решение производственных задач с использованием методики повышения эффективности распределения вычислительных ресурсов.... 120

4.2. Внедрение результатов диссертационного исследования....................130

Выводы по главе 4...............................................................................................132

Заключение..........................................................................................................133

Список использованных источников................................................................135

Приложение 1. Свидетельство о государственной регистрации программы для эвм..................................................................................................................148

Приложение 2. Акты о внедрении.....................................................................149

\

ОСНОВНЫЕ ТЕРМИНЫ И УСЛОВНЫЕ СОКРАЩЕНИЯ

Deadline - крайний (предельный) срок завершения исполнения задачи.

EDF - алгоритм планирования «ближайший предельный срок первым».

Global Scheduling - глобальное мультипроцессорное планирование.

IEC - международная электротехническая комиссия.

ISO - международная организация по стандартизации.

Laxity - запас времени.

Laxity-driven scheduling - планирование, основанное на вычислении запаса времени (преимущественно с динамическими приоритетами).

LLF - алгоритм планирования «задача с наименьшим запасом времени первая».

Partitioned Scheduling - раздельное мультипроцессорное планирование.

POSIX (от англ. Portable Operating System Interface for Unix) — стандарт, регламентирующий переносимые интерфейсы ОС семейства Unix.

RM-US, SM-US, RMZL, FPZL - алгоритмы глобального мультипроцессорного планирования.

RMA (от англ. Rate-Monotonic Analysis) - частотно-монотонный анализ.

RMFF, RMNF, RMBF, FFDUF, RM-FFDU, RMST, RMGT, RMFF-WC, RMNF-WC, RMBF-WC, RMDP - алгоритмы раздельного мультипроцессорного планирования.

RMS - алгоритм частотно-монотонного планирования.

RTA (от англ. Response Time Analysis) - анализ времени <}тклика.

Время выполнения задачи в худшем случае (от англ. Worst-Case Execution Time) - характеристика задачи, определяющая требуемое ей количество ресурсов исполнительного ресурса в отсутствии вытеснений.

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

Задача - объект планирования; задание - экземпляр задачи.

Интерференция задачи - характеристика степени влияния высокоприоритетных задач на задачи с меньшим приоритетом.

Исполнительный ресурс (ИР) - модуль, выполняющий математическое и алгоритмическое обеспечение СРВ.

Критический сценарий - наихудший сценарий выполнения высокоприоритетных задач и возникновения событий перепланирования.

Миграция - способность задачи потреблять ресурсы различных ИР.

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

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

Оптимальное планирование - планирование, обеспечивающее выполнимость каждой задачи для любой выполнимой данным классом методов системы задач.

Переключение исполнительного ресурса - процесс переключения исполнительного ресурса на выполнение другой задачи.

Перепланирование - событие переключения исполнительного ресурса.

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

Приоритет - численная характеристика "важности" задачи.

Симметричное мультипроцессирование (от англ. Symmetric Multiprocessing), асимметричное мультипроцессирование (от англ. Asymmetric Multiprocessing) - архитектуры мультипроцессорных ЭВМ.

СРВ - Система Реального Времени.

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

ВВЕДЕНИЕ

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

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

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

наибольшее внимание будет уделено именно тем СРВ, в распоряжении которых имеется несколько исполнительных ресурсов. Для краткости технические средства, имеющие в своем распоряжении несколько ИР (не взирая на принадлежность ИР к микропроцессорным средствам или же к узлам ЛВС), выполняющих задачи реального времени, предлагается именовать мультипроцессором.

К моменту проведения данного диссертационного исследования сформировалось три основных подхода к решению задачи планирования в мультипроцессорных СРВ:

1. динамическое планирование (распределение вычислительных ресурсов с использованием динамических приоритетов задач) - подход, характеризующийся проведением основных мероприятий планирования непосредственно во время эксплуатирования системы посредством изменения приоритетов;

2. раздельное статическое планирование - подход характеризуется разделением всех задач на группы и их закрепление за различными исполнительными ресурсами с назначением фиксированных* приоритетов, заданных еще на этапе проектирования;

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

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

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

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

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

«

Степень научной разработанности проблемы. Теоретические вопросы распределения вычислительных ресурсов в системах жесткого реального времени посредством механизма планирования, а также основы классической теории частотно-монотонного анализа были широко исследованы в работах С. Liu, I. Layland, А. Мок, J.P. Lehman, L. Sha, D.Y. Ding, M. Joseph, P. Pandya, E. Bini, G. Buttazzo, R. Rajkumar, J.P. Lehoczky, M. Borger, M. Klein, R.A. Veltre; J. Carpenter, S. Funk, P. Holman, A. Srinivasan, J. Andersson, S. Baruah,

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

трудах S.K. Dhall, C.L. Liu, B.B. Никифорова, L. Sha, T. Abdelzaher, К. Arzen, В. Andersson, S. Baruah, J. Jonsson, S. Funk, J. Goossens, R.I. Davis, A. Burns, E. Bini, G.C. Buttazzo, J.P. Lehman, D.Y. Ding, T.P. Baker, M. Cirinei, M. Bertogna, G. Lipari, Nan Guan, M. Stigge, Wang Yi, Ge Yu. В том числе ими были предложены математические модели и методы, позволяющие проводить анализ эффективности алгоритмов планирования СРВ, а также синтезировать модели систем задач реального времени.

В работах В. Andersson, S.A. Baruah, J. Jonsson, T.P. Baker, L. Lundberg произведен анализ применимости глобальных дисциплин планирования в мультипроцессорных СРВ, а также предложены методы анализа выполнимости математического обеспечения подобных систем. Кроме того, в данных работах приводится ряд контраргументов, направленных против применения раздельного статического планирования для решения задачи распределения вычислительных ресурсов в мультипроцессорных СРВ.

Объект исследования. Объектом исследования является мультипроцессорная событийно-управляемая СРВ.

Предмет исследования. Предметом исследования являются процедуры статического планирования событийно-управляемых мультипроцессорных СРВ.

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

»

Задачи исследования:

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

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

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

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

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

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

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

*

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

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

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

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