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

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

Специальность 05.13.05 — Элементы и устройства вычислительной техники и систем управления

АВТОРЕФЕРАТ

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

005564431

Саратов 2015

005564431

Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего образования «Саратовский государственный технический университет имени Гагарина Ю.А.»

Научный руководитель: Садомцев Юрий Васильевич,

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

Официальные оппоненты: Андрейченко Дмитрий Константинович,

доктор физико-математических наук, профессор,

ФГБОУ ВПО «Саратовский государственный университет имени Н.Г. Чернышевского», заведующий базовой кафедрой математического обеспечения вычислительных комплексов и информационных систем Епифанов Антон Сергеевич, кандидат физико-математических наук, Институт проблем точной механики и управления РАН (г. Саратов), старший научный сотрудник лаборатории системных проблем управления и автоматизации в машиностроении

Ведущая организация: Филиал ФГУП «НПЦ АП им. H.A. Пилюгина» -

«ПО «Корпус» (г. Саратов)

Защита диссертации состоится «21» декабря 2015 г. в 13:00 на заседании диссертационного совета Д 212.242.08 при ФГБОУ ВО «Саратовский государственный технический университет имени Гагарина Ю.А.» по адресу: 410054, г. Саратов, ул. Политехническая, 77, корп. 1, ауд. 319.

С диссертацией можно ознакомиться в библиотеке ФГБОУ ВО «Саратовский государственный технический университет имени Гагарина Ю.А.» и на сайте www.sstu.ru

Автореферат разослан « 2 1 » октября 2015 г.

Ученый секретарь »

диссертационного совета г-П/k?*? Терентьев Александр Александрович

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

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

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

Вопросами повышения эффективности диспетчеризации в системах реального времени занимались многие ученые, среди которых большой вклад внесли J. Nilsson, G. Buttazzo, G. Fohler, D. Isovic, M. Behnam, M.B. Кавалеров, H.H. Матушкин, В. Wittenmark, M. Törngren. Некоторые, например G. Fohler, M.B. Кавалеров и др., изучали особенности управления выполнением заданий именно в устройствах СУ. Однако многие вопросы, связанные с особенностями СУ и принципами функционирования их элементов, остаются недостаточно проработанными.

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

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

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

Вышеизложенное определяет цель и задачи диссертационной работы.

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

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

модификации базовых моделей функционирования ЦВУ для описания выявленных особенностей.

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

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

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

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

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

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

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

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

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

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

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

Работа соответствует паспорту научной специальности 05.13.05 «Элементы и устройства вычислительной техники и систем управления» в пунктах: 1 «Разработка научных основ создания и исследования общих свойств и принципов функционирования элементов, схем и устройств вычислительной техники и систем управления»; 2 «Теоретический анализ и экспериментальное исследование функционирования элементов и устройств вычислительной техники и систем управления в нормальных и специальных условиях с целью улучшения технико-экономических и эксплуатационных характеристик»; 4 «Разработка научных подходов, методов, алгоритмов и программ, обеспечивающих надежность, контроль и диагностику функционирования элементов и устройств вычислительной техники и систем управления».

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

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

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

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

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

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

5) Структура и принцип функционирования аппаратного диспетчера -устройства, реализующего часть функций по переключению между заданиями аппаратными средствами, а также принципы его взаимодействия с ЦВУ.

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

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

Реализация и внедрение результатов работы проведены совместно с ОАО «КБ Электроприбор» в рамках исследовательских и опытно-конструкторских работ по изделиям КРД (комплексный регулятор двигателя), ПКД (пульт контроля и диагностики) и СУДГ (система управления и диагностики генератора), что подтверждается актами внедрения.

Апробация работы и публикации. Основные результаты работы докладывались и обсуждались на 6 международных конференциях: международная конференция «Проблемы управления, обработки и передачи информации (АТМ-2011)», Саратов, 2011; XXVI международная научная конференция «Математические методы в технике и технологиях - ММТТ-26», Саратов, Нижний Новгород, 2013; международная конференция «Проблемы управления, обработки и передачи информации (АТМ-2013)», Саратов, 2013; XXVII международная научная конференция «Математические методы в технике и технологиях - ММТТ-27», Саратов, Тамбов, 2014; 13-я международная конференция "Авиация и космонавтика - 2014", Москва, 2014; XXVIII международная научная конференция «Математические методы в технике и технологиях - ММТТ-28», Саратов, 2015; и представлены в 20 печатных работах, 5 из которых - в изданиях, включенных в перечень рекомендуемых ВАК РФ. Имеются 3 свидетельства о регистрации программы для ЭВМ.

Результаты диссертационного исследования включены в Отчет о выполнении НИР по теме «Разработка Д18ТЕХ — простота и качество экзоядра», поддержанной по программе «У.М.Н.И.К.» Фондом содействия развитию малых форм предприятий в научно-технической сфере (договор № 4122ГУ2/2014 и № 470ГУ1/2013).

Личный вклад автора состоит в разработке модели функционирования устройства [3], в разработке методик оценки выполнимости и интеграции диспетчера в набор заданий [2, 4, 5]; помимо этого, автор принимал участие в проектировании и реализации инструментальных средств для исследования результатов работы [1, 8, 11,14, 21-23].

Структура и объем работы. Работа состоит из введения, 5 глав, заключения, списка сокращений и условных обозначений, списка терминов, списка цитируемой литературы и приложений. Общий объем составляет 147 страниц, включая 63 рисунка, 6 таблиц, список литературы из 132 наименований и 3 приложения.

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

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

В первой главе представлено описание модели функционирования ЦВУ (ФЦВУ). В качестве базовой выбрана модель, построенная на понятиях и положениях, используемых в работах М.В. Кавалерова, H.H. Матушкина, G. Buttazzo, К. Tindel и др. Функционирование ЦВУ представляется как последовательное непрерывное выполнение «заданий» из заданного набора.

Задание (task) - часть ЦВУ, выполненная аппаратными или программными средствами, реализующая некоторую самостоятельную функцию. Обозначается т,, где i — порядковый номер, 0<i<n, п - общее количество заданий в наборе, обрабатываемом ЦВУ. Задание может находиться в следующих состоящих (рисунок 1): run — при выполнении задания процессором, ready — выполнение отложено, wait - задание выполнено, fail - выполнение задания отменено. Задание может запускаться на выполнение неограниченное число раз, а каждый запуск называется запросом (instance) задания и обозначается ти, где j — номер запроса.

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

|г, (/) е {wait, run, ready, fail}

О)

т„ (t) e {wait, run, ready, fail}

Состояние заданий во времени изменяется по принципу, определяемому параметрами этих заданий: Р, — приоритет задания; Т, — период инициации запросов заданий; Ф, - время первого запроса задания (фазовый сдвиг); С, -максимальное время выполнения запроса задания; D, - относительный крайний срок завершения каждого запроса задания; type, — тип задания. В зависимости от соотношения параметров различных заданий, могут встречаться такие ситуации, когда одни задания вытесняются другими (рисунок 2). Из параметров заданий могут быть выражены параметры запросов заданий (рисунок 2): аи - момент инициации запроса, stJ - момент начала выполнения запроса, c(J - время выполнения запроса (без учета времени вытеснения другими заданиями), ft) — момент завершения выполнения запроса, rtJ - время отклика запроса (время выполнения с учетом вытеснения), du — крайний срок завершения выполнения запроса.

-Запуск системы—| V

wait )

'A M

I ready j—^ fail i

X

Рисунок 1 - Граф состояний задания

л,

"4-4

¡Фк

Л, f

6J

Рисунок 2 - Примеры выполнения запроса задания в цифровом вычислительном устройстве: а - выполнение запроса задания без вытеснения; б - отложенное выполнение и вытеснение запроса задания Поведение задания зависит от типа задания type,. Так, для периодических (type, = periodic) заданий, параметры Т\ и Ф, отражают точные значения периода и фазы, а для спорадических (type, = sporadic) - минимальные значения (рисунок 3):

V(i: type, = periodic), wait, при(ф,. + j-T; +0,)</<(Ф, +0' + 1)'71).'<ф,

rim,ready,wait, в другихсяучаях

V(i: type, = sporadic),

(2)

wait, run, ready, wait,

при

kj + А>'<к,.,,)'<Ф„Ч/:аш >аи + Т,;а„ >Ф,)

в других случаях

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

Ф,

Т.

Т.

Ф,

Т.

type, = periodic

а)

type. - sporadic б)

Рисунок 3 - Поведение задний разных типов: а - периодического; б - спорадического.

В модифицированную модель включен регулярный тип заданий. Инициация заданий этого типа возможна в произвольные моменты, но ограничена временными отрезками, равными заданному периоду, за счет чего средняя частота запросов является постоянной (рисунок 4). Такое поведение часто встречается в ЦВУ, работающих в составе СУ. К этому типу могут быть отнесены практически все обработчики прерываний от внешних устройств. В отличие от спорадических заданий, для регулярных справедливо:

V/, Тг0-0+ Ф, ^<ТГ] + Ф,. (3)

rt : Ф, Г, т, ■. т. у;

m ЯЛ. ш

0

type, = regular

Рисунок 4 - Инициация и выполнение запросов регулярного задания

При описании задания с использованием спорадического и регулярного типов, в последнем случае оценка его влияния на другие задания оказывается меньшей (глава 2).

Все описанные выше типы заданий являются типами «жесткого» (hard) реального времени. В модифицированную модель также добавлены типы «строгого» (firm) реального времени (РВ). К ним отнесены все задания, для которых справедливо T,>D,. Для таких типов принято что, если новый запрос инициируется до завершения предыдущего, то событие инициации и собственно запрос игнорируются. По сравнению со стандартным определением «строгих» заданий через {т.к}, где из к запросов должны быть обязательно выполнены т, принятое определение существенно упрощает тест выполнимости набора заданий.

С учетом вышесказанного, модифицированная модель ФЦВУ содержит следующие типы заданий, р/, ph, sh, sf, rh, rf. Здесь буква p в названии указывает на принадлежность к периодическому типу, 5 - спорадическому, г -регулярному. Буква / означает тип «строгого» РВ, h - «жесткого» РВ.

В модель также добавлен параметр, описывающий механизм реализации приоритетов р <в{р,а], где р - реализация программой-диспетчером, а -механизмом прерываний. Реализация приоритета определяет способ переключения на выполнение данного задания. В использовавшихся ранее моделях задания считались реализованными программным диспетчером. Это добавляло большую избыточность и ухудшало результаты прогнозирования выполнимости набора, что доказано в главе 4. Различие поведения заданий с аппаратным и программным переключением приведены на рисунке 5.

а) б)

Рисунок 5 - Поведение заданий с аппаратным (а) и программным (б) способами реализации приоритетов для случая Р, > Р2 > Рг, Т1уг - задание, реализующее диспетчеризацию

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

Неоднородность заданий заключается в том, что в устройствах СУ каждому типу заданий соответствуют реализации конкретных функций системы. Как следствие, вероятность наличия в наборе заданий каждого типа не является одинаковой. На основе исследования реальных ЦВУ установлено, что типы заданий ограничены следующим набором: pf, ph, sh, rh. При этом каждый тип имеет собственные определенные ограничения на С,, £>,, Р, и Рг

Автономность ЦВУ выражается в неизменяемости количества и характеристик заданий в процессе эксплуатации устройства (рассматривается только диспетчеризация с постоянными приоритетами, т. к. она обеспечивает наибольшую предсказуемость и является наиболее применимой во встроенных системах.):

п = const,

V/, D, -const, С, = const, Tt =const, Ф( =const, type, =const., P, =const,

Pt = const.

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

Наличие заданий управления объектом. В ЦВУ СУ всегда имеется часть программного и аппаратного обеспечения, реализующая функции цифрового регулятора. Поэтому в наборе заданий ЦВУ всегда имеются задания тс<т, тас1 (ввод — расчет — вывод, далее — задания управления). Они имеют одинаковый период, равный периоду дискретизации Td СУ, одинаковый тип ph и строгую последовательность выполнения, которая может быть выражена через характеристики Ф,, С,, D, этих заданий:

. (5)

На временные интервалы между запусками заданий управления наложены ограничения:

где Дs^j = - asamJ - задержка между инициацией и запуском запроса задания, реализующего ввод информации, Asac, у = sac: i - aact J - задержка между инициацией и запуском запроса задания, реализующего вывод управляющего воздействия.

Задача оценки данных задержек решалась в работах C.-Y. Као, В. Linkoln, G. Fohler и др. Однако каждое решение предусматривает использование определенной модели ФЦВУ, не всегда подходящей для устройств СУ. В простейшем случае задержки могут быть оценены как допуск задания X,, который на практике должен закладываться достаточно малым:

maxiQ^/UA'-A-C,.. (7)

KJ-i )

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

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

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

Продуктивность Б отражает вероятность успешной оценки выполнимости заданий:

E = Ns/Nu, (8)

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

Времешгая неопределенность характеризует максимально возможное отклонение периода дискретизации Td от его номинального значения:

Д = тах((Я„„ - Clam)/Tj, (Лоя-О/Г,), (9)

где С,ат и Саа - максимальные времена выполнения задания ввода информации с датчиков т„т и задания вывода управляющего воздействия racl; R,am и Raa -отклики этих заданий.

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

Величина выбранных показателей существенно зависит от рассматриваемого набора заданий. Обобщенными показателями «сложности» набора заданий можно считать коэффициент использования вычислительных ресурсов U =^С,/Т1, количество заданий в наборе п и, в ряде случаев, время выполнения диспетчера Clys. Эти параметры используются для определения уравнений регрессии и

сравнительного анализа предлагаемых решений.

Во второй главе описывается процедура оценки выполнимости набора заданий. Основная часть процедуры организации диспетчеризации заключается в назначении постоянных приоритетов всем заданиям в наборе по некоторому алгоритму. Оценка выполнимости является заключающей частью подготовки устройства к работе, в ходе которой формируется заключение о работоспособности ЦВУ (в том смысле, что все задания, при заданных приоритетах, могут быть выполнены даже при максимальной нагрузке на вычислительную часть устройства). При разработке алгоритма проведения теста выполнимости использованы результаты C.L. Liu, J.W. Layland, М. Joseph, P. Pandya, K.W. Tindell, A. Burns, A.J. Wellings и др.

Для оценки выполнимости проводится вычисление максимального времени «отклика» каждого задания R, в наборе. Отклик задания - это время, которое при

наихудшем стечении обстоятельств, может пройти с момента инициации запроса задания до момента завершения его выполнения, Л;>С,. Основная идея теста выполнимости состоит в том, что отклик каждого задания, при учете влияния на него других заданий из набора, должен быть меньше относительного крайнего срока завершения этого задания:

(Ю)

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

с,, л(=л;,эл;=лг', (11)

д9+| ■

Мк

где к:кФ1,Рк>Рп ^ - номер итерации.

Вычисление (11) проводится, начиная с задания с максимальным приоритетом, в итерационной процедуре и продолжается до тех пор, пока Л,' увеличивается, или не выполнится (10).

В настоящей работе в базовую формулу (11) добавляется учет заданий с одинаковыми приоритетами. Эта особенность использована в главе 3. Показано что в наихудшем случае влияние задания с аналогичным приоритетом равносильно влиянию задания с более высоким приоритетом. Это изменяет ограничения в формуле (11) следующим образом:

к-.к*иРк>Р.. (12)

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

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

т

к---*---И

Рисунок 6 - Запросы регулярных заданий

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

вид:

: ¡уре, е {рИ,р/,зИ,*/}), Л,3+1 =С, :!уре,е {г/г, г/}), Л?+| = 2С, + £

V/

Rf

л;

т,

+1

с,

л,. =л«,эл; = л,®+1,

где к-.кФ1,Р,>Р1,1урек=рИ,р/,зИ,5/, /:/*;, Р, ¿Р,,^, =гЬ,г/, я итерации.

(13)

номер

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

Утверждение. Если при рассмотрении двух периодических заданий г, и г,,

для произвольного Ь, О<Ь. Ф<Ь-Тк+Фк, Ф = тах^Ц)ф( j, при переборе всех

натуральных g, ограниченных условием

y[g-.b + \<g<b + \ + fyT^, tf = lcm|Ur,j (14)

существует натуральное h, удовлетворяющее неравенству

^„-<t>,+{g-1i)Tl,+Tl-Rl<h.Tl<Ot^, + (g-\)-Tt+Tl + Rk, (15)

то в этом и только в этом случае задания г, и г, являются взаимовлияющими.

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

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

Для наиболее используемого классического подхода учет диспетчера осуществляется на основе ряда упрощений [A. Bums, K.W. Tindell, A.J. Wellings и др.]. Диспетчер инициируется равномерно через заданные промежутки времени. Время его работы включается во время выполнения прикладных заданий. Их отклики округляются до кратных периоду служебного задания, т. к. этот период является минимальной мерой времени выполнения.

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

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

K«, I.г"/,,, !,.••) (рисунок 7), каждое из которых отвечает за инициацию или завершение одного из прикладных заданий. Это позволяет точнее прогнозировать влияние диспетчера, но приводит к значительному увеличению заданий в наборе.

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

v(/ -.type, e [ph,pf,jA,5/}), Я/" = С,. + £ V(;: type, e Ц л/}), Л,«+l = 1С, + £

V/

tf.9

V«

R?

- + l

- + 2

(16)

Л, = Л*, э Я,' = ,

л» j

где g - номер итерации; k:k*i,Pk > Р,, typek = ph,pf,sh,sf;

l:l*i,P, >P,,type, =rh, rf, spt; m.l<m<n,m*i,Pm >P„typem =rt.

В четвертой главе описаны результаты

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

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

выполнимости этих наборов формировались оценки

продуктивности Е и среднего временной неопределенности 0. Эксперимент проводился в следующих диапазонах факторов: и = 5.. 15, С,^ =1. 5, 0.1 <£/<1.5.

Параметры тестовых наборов заданий удовлетворяют условиям (4) и (5), а также следующим отношениям:

сгН 1 t

i-1 1 t

1

я® 1

сi—1-1 i

Щ

t

Я- !-1 1 t

Рисунок 7 — Условное деление задания диспетчера

type, е {ph,pf,sh,rh}

C, <Т,

D, >С,

V(,: type, е {рй, rh, sh}), D, < Т, И': = ^ 1 ~ ^ " Р< = Р

V(i: е {sh, rh}), 2п +1 < Р., < Зи, Я, = а V(;: = ph), п + \<Р,<2п,Р, = р

(17)

Параметры используемых законов распределения с соответствующими ограничениями представлены в таблице 1. Здесь верхние индексы обозначают: а -для заданий с аппаратной реализацией приоритета, р - с программной, h -жесткого РВ, / - строгого РВ, pf,ph,sh,rh - для заданий соответствующего типа. Период дискретизации Тл = 0.005 с.. При генерации типа заданий type, использовался закон с вероятностью выбора типа pf - 0.12027, типа ph - 0.38163, типа sh - 0.21591, типа rh - 0.2822.

Таблица 1 - Характеристики распределений параметров заданий в ЦВУ СУ

Параметр Распределение Мат. ожидание Дисперсия Мин. знач. Макс.знач.

т;/тё гамма 0,072 0,030 0 -

т,р/т, гамма 1,290 0,602 0 -

с,"/т, гамма 2,454 -и/п 3,156-([//л)г 0 1

ср/т, гамма 1,526 -и/п 1,584 -(и/ л)2 0 1

Ч /11 гамма 0,253-(У/л 0,123 (и/п)2 0 1

АЧт, гамма 0,373 0,112 С,/Г, 1

О'/Т, гамма 2,200 0.200 1 -

ф ,/т, гамма 0,150 0,061 0 . -

р, равномерное - - в соотв. с (17) в соотв. с (17)

Все числовые значения, используемые при генерации тестовых данных, получены в экспериментальных исследованиях испытательных прототипов таких устройств СУ, как ПКД, СУДГ, КРД (ОАО «КБ Электроприбор») различных модификаций.

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

Ёь°" = ехр(-0.793\ и п), Е" = ехр(—0.7512С/-л). (18)

где ЕЬа" - оценка продуктивности при использовании базовой модели ФЦВУ, Е" - модифицированной. Выражение (18) показывает, что с увеличением коэффициента использования процессора и и количества заданий в наборах л, в последнем случае продуктивность снижается медленнее. Таким образом, если некоторый набор, описанный базовой моделью ФЦВУ, является невыполнимым, то существует вероятность, что его выполнимость окажется положительной при описании модифицированной моделью.

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

Е" = ехр(-0.7468•£/• и), =ехр(-0.5831-(/• л). (19)

где Е" - оценка продуктивности диспетчеризации при использовании модифицированной модели без учета взаимовлияния, Ё"°р' - с учетом. Этот результат демонстрирует существенное увеличение продуктивности во втором случае.

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

15

Г^ е {1 ООО ■ С„, 500 ■ С,,, 250■ , 100• С^, 50• С^, 10• С^,, 5 ■ С,„} , где С„„ - время выполнения задания-диспетчера. Результаты представлены на рисунках 8 и 9.

—г—

О Р.5 / /.Л Л Л.* 1 1.5 (I 0 5 I М

а) б) я)

Рисунок 8 - Продуктивность диспетчеризации при использовании классического подхода к организации диспетчера (1) и апериодического (2) при а) л = 5, С<уу = 3 ; б) « = 10, С =3 ;

в) л = 15, С =3

........."V

V

а) в) ч)

Рисунок 9- Продуктивность диспетчеризации при использовании классического подхода к организации диспетчера (1) и апериодического (2) при а) « = 10, Сзуз = 1; б) и = 10,Са1в=3;

В) „ = 10, С =5

Как видно из рисунков, во всех случаях продуктивность выше при использовании апериодического подхода. Продуктивность обоих подходов уменьшается при увеличении каждого из факторов: на рисунке 8 можно проследить динамику по п, на рисунке 9 - по С, динамика по и представлена на обоих рисунках. Среднее по всем исследуемым точкам преимущество апериодического подхода в производительности Е" - Ер =0-688. Это говорит о том, что в исследуемой области апериодический подход обеспечивает выполнимость для более чем вдвое большего количества наборов, чем классический.

Графики среднего временной неопределенности 0 = Д. вычисляемой для каждого тестового набора по формуле (9), представлены на рисунке 10. Как следует из рисунка, в большинстве случаев 0 меньше при апериодическом подходе. Следовательно, при его использовании выше вероятность, что смещение во времени моментов ввода-вывода информации для СУ будет меньше, т.е. процесс управления будет иметь лучшее качество. Среднее по всем исследуемым точкам преимущество апериодического подхода 0.0127, что означает возможное сокращение временной неопределенности при использовании апериодического подхода в среднем на 0.0127 ■ Тг,.

0.15 0.1 0.05 О

0 0.15

1 0.1

// ..._..... 2 \

/

: и

О

1.5

и)

Рисунок 10-Оценки среднего временной неопределенности, полученные при использовании классического подхода (1) и апериодического (2) при а) п = 5, С = 1; б) п = 10, Ст = 3;

в) л = 15, С,^ =5

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

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

Сократить время С^ позволит выделение функций программно реализованного диспетчера в отдельное устройство, называемое в данной работе «аппаратным диспетчером» (АД). Функциональная схема АД представлена на рисунке 11.

Рисунок 11 - Функциональная схема аппаратного диспетчера

Аппаратный диспетчер взаимодействует с ЦВУ по параллельной системной шине (с линиями адреса, данных и управляющими линиями) и одной сигнальной линии, подключенной к входу внешнего прерывания ЦВУ. Эта линия предназначена для информирования ЦВУ о наступлении событий, связанных со срабатыванием таймеров в составе АД.

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

Т. к. АД реализован в виде параллельной логической схемы, то выдача номера активного задания происходит для ЦВУ мгновенно (меньше такта центрального процессора ЦВУ). Таким образом, при применении АД время Сгу1 сокращается до минимальной величины. Дальнейшее уменьшение С невозможно, т. к. оно связано с внутренними особенностями процессора ЦВУ (обработка контекстов, смена режима функционирования).

Основные результаты работы состоят в следующем:

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

2) Разработан алгоритм формирования условия выполнимости для модифицированной модели ФЦВУ. Отличие предложенной методики анализа заключается в возможности обработки заданий нестандартных типов.

3) Предложен способ усовершенствования теста выполнимости, увеличивающий вероятность получения положительной оценки выполнимости при наличии в наборе большого количества периодических заданий. Это условие является распространенным для ЦВУ в составе СУ.

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

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

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

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

Полученные результаты позволяют повысить эффективность ЦВУ в составе

Основные результаты опубликованы в следующих работах: Публикации в центральных изданиях, включенных в перечень ВАК РФ

1. Соколов, А. О. Защищенный модуль управления памятью для микроконтроллера / А. О. Соколов, J1. А. Блюштейк // Вестник Саратовского государственного технического университета. - Саратов, 2013. - Т. 1,№ 1(69).-С. 204-208.

2. Соколов, А. О. Показатели качества программного обеспечения цифровых регуляторов / А. О. Соколов, О. А. Терентьев // Вестник Воронежского государственного технического университета - Воронеж, 2013. - Т. 9, № 4. - С. 98-102.

3. Соколов, А. О. Модель программного обеспечения систем реального времени / А. О. Соколов//Программная инженерия.-2014.-№7.-С. 9-16.

4. Соколов, А. О. Оценка выполнимости наборов задач реального времени / А. О. Соколов//Программная инженерия. - 2014. 9. - С. 23-29.

5. Соколов, А. О. Оценка влияния апериодического диспетчера в системах реального времени/А. О. Соколов//Программная инженерия. - 2015.-№ 1.-С. 12-23.

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

6. Соколов, А. О. Применение оценочных параметров для уточнения показаний датчиков / А. О. Соколов, О. В. Ушакова // Проблемы управления, обработки и передачи информации (АТМ-2011) : сб. трудов И Междунар. науч. конф.: в 2т. - Саратов, 2012. - Т. 2. -С. 14-16.

7. Соколов, А. О. Контроль периода дискретизации в современных САУ методом двойного цикла / А. О. Соколов // Проблемы управления, обработки и передачи информации (АТМ-2011): сб. трудов II Междунар. науч. конф.: в 2т. - Саратов,2012.-Т. 2. - С. 16-18.

8. Соколов, А. О. Быстродействующая операционная система реального времени для высоконадежных систем / А. О. Соколов // Участники школы молодых ученых и программы УМНИК: сб. трудов XXV Междунар. науч. конф.-Саратов, 2012.-С. 108-110.

9. Соколов, А. О. Упрощение верификации встраиваемых систем средствами операционной системы реачьного времени / А. О. Соколов // Математические методы в технике и технологиях - ММТТ-26 : сб. трудов XXVI Междунар. науч. конф.: в 10 т. Т. 9. Секция И.-Н. Новгород.2013.-С. 118-121.

10. Соколов, А. О. Экзоядро с точки зрения систем реального времени / А. О. Соколов // Математические методы в технике и технологиях - ММТТ-26 : сб. трудов XXVI Междунар. науч. конф.: в 10т. Т. 9. Секция 11.-Нижний Новгород, 2013.-С. 121-124.

11. Соколов, А. О. JUSTEX - простота и качество экзоядра / А. О. Соколов // Участию! школы молодых ученых и программы УМНИК : сб. тр. XXVI Междунар. науч. конф.: в 2 ч. Ч. 1. - Саратов, 2013. -С. 17-20.

12. Соколов, А. О. Использование моделей надежности программного обеспечения на разных этапах жизненного цикла / А. О. Соколов // Проблемы управления, обработки и передачи информации (АТМ-2013): сб. тр. III Междунар. науч. конф.: в 2 т. - Саратов, 2013. — Т. 2.-С. 203-207.

13. Соколов, А. О. Модель оценки надежное™ программного обеспечения методами классической теории надежности / А. О. Соколов // Проблемы управления, обработки и передачи информации (АТМ-2013): сб. тр. III Междунар. науч. конф.: в 2 т. - Саратов, 2013. -Т. 2.-С. 207-213.

14. Соколов, А. О. Повышение портируемости встроенной операционной системы / А. О. Соколов // Математические методы в технике и технологиях - ММТТ-26 : сб. тр. XXVI Междунар. науч. конф.: в2ч. 4.2.-Ангарск [идр.], 2013.-С. 195-199.

15. Ломсадзе, А. Д. Модель программного обеспечения цифрового регулятора / А. Д. Ломсадзе, А. О. Соколов, О. А. Терентьев // Проблемы управления, обработки и передачи информации (АТМ-2013): сб. тр. III Междунар. науч. конф.: в 3 т. - Саратов, 2013. -Т. 3.-С. 132-138.

16. Соколов, А. О. Инструменты разработки программного обеспечения автономных программно-аппаратных комплексов / А. О. Соколов, О. А. Терентьев // 13-я Международная конференция "Авиация и космонавтика - 2014". 17-21 ноября 2014 года. Москва Тезисы. -СПб., 2014.-С. 439-441.

П.Соколов, А.О. Повторное использование программного обеспечения в цифровых устройствах авиационной техники / А. О. Соколов, О. А. Теренгьев // Авиация и космонавгика-2014: тезисы 13-й Междунар. конф., Москва,17-21 ноября2014 года.-СПб., 2014.-С. 453-454.

18. Ломсадзе, А. Д Модель вычислительных процессов в цифровой системе автоматического управления / А. Д. Ломсадзе, С. А. Крайнев, А. О. Соколов // Математические методы в технике и технологиях - ММТТ-27: сб. тр. XXVII Междунар. науч. конф.: в 12т. Т. 9.-Саратов,2014.-С. 177-181.

19. Прусов, Д. Ю. Устройство управления памятью для микроконтроллерных устройств / Д.Ю. Прусов, А.О. Соколов // Математические методы в технике и технологиях -ММТТ-27: сб. тр. XXVII Междунар. науч. конф.: в 12 т. Т. 9. - Саратов, 2014. - С. 173-177.

20. Sokolov, А. О. Classification of digital controller software quality / A. O. Sokolov, K. G. Sokolova // Математические методы в технике и технологиях - ММТТ-27: сб. тр. XXVII Междунар. науч. конф.: в 12 т. Т.6.-Тамбов, 2014.-С. 135-138.

Свидетельства на программы для ЭВМ

21. Российская Федерация. Свидетельство о регистрации программы для ЭВМ №2013617231. CV / А. О. Соколов, О. А. Терентьев, В. Ю. Челмадеев; заявитель и патентообладатель ОАО «КБ Электроприбор» (RU). -заявка№2013612567; заявл. 01.04.13 ; опубл. 06.08.13.

22. Российская Федерация. Свидетельство о регистрации программы для ЭВМ №2013617167. OBS / ДЮ.Бабанов, А.О.Соколов, О.А.Теренгьев; заявитель и патентообладатель ОАО «КБ Электроприбор» (RU). - заявка №2013613253 ; заявл. 23.04.13 ; опубл. 02.08.13.

23. Российская Федерация. Свидетельство о регистрации программы для ЭВМ №2015616776. JustOS / А. О. Соколов; заявитель и патентообладатель ФГБОУ ВПО СГТУ имени Гагарина Ю.А. (RU). - заявка № 2015613310; заявл. 23.04.15 ; опубл. 22.06.15.

Подписано в печать 13.10.15 Формат 60x84 1/16

Бум. офсет. Усл. печ. л. 1,0 Уч.-изд. л. 1,0

Тираж 100 экз. Заказ 118 Бесплатно

Саратовский государственный технический университет

410054, Саратов, Политехническая ул., 77 Отпечатано в Издательстве СГТУ. 410054, Саратов, Политехническая ул., 77 Тел.: 24-95-70; 99-87-39, e-mail: izdat@sstu.ru