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

шшиотврстю гражданской авиации московский шститут иншеров 1радданской авиации

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

ЯРОНСКИЙ Михаил Васильевич

УДК 681.3-519.6

•РАЗРАБОТКА МЕТОДОВ АНАЛИЗА И ОПТИМИЗАЦИЯ ПРОЦЕССОВ ДОСЖИЕИВЩИ ЗАДАЧ В СИСТЕМАХ РЕАЛЬНОГО ВРЕМЕНИ

Специальность 05.13.13 - Вычислительные машины, комплексы, системы и оети

-АВТОРЕФЕРАТ диссертации на соискание ученой отепеш кандидата технических наук

Москва - 1989

..-(■ ."V./ -") ..V

_ Работа выполнена_ в .Московском_ институте. инженеров.граддан'

окой авиации.

Научный руководитель - заол. деятель науки и техники РСФСР»

доктор технических наук» профессор ... В.И.ВАСИЛЬЕВ

Официальные оппоненты - доктор технических наук, црофеосор

Ю-Г.ЗОЛОТАРЕВ

кандидат технических наук В.В.РОЩИН

Ведущая организация - ЩО "Програшпром".

Защита ооотоятоя ^«£¡^¿£1990 г. в ¿У часов на заседании снецаалиащххванного совета К.072.05.01 Ыооковокого института инженеров гражданской авиации но адресу: 125493, Москва, Кронштадтский бул., 20. .

С диосертацпей можно ознакомиться в библиотеке МИИГА.

Автореферат разоодан 1989 г.

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

Л.Г.РСЫАНОВ

■J

: j ,s ОВДАЯ ХАРАШШСТШ РАБОТЫ

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

В соответствии о Координационным планом работ ГКНТ СМ ССОР на 12-ю пятилетку то решению научно-технических проблем 0.80.09 (задание 05.02.03;, 0,80.02 в отрасли предусматривается создание информационно-вычислительной сети, дальнейшее развитие системы продажи билетов и бронирования мест "Сирена-Й", типовой системы управления технологическими процессами ОАО, интегрированной сети связи ГА, интегрированных систем управления авиа-прэдприятаями (ИАСУ - Аэропорт), а также единой автоматизированной сиотемы управления воздушным движением (SAC УВД). При создании такого рода систем, которые базируются на вычислительном комплексе (БК) реального времени, основной задачей является удовлетворение качества функционирования последнего в условиях воздействия неоднородного и смещенного графика, отказов и восстановлений элементов этих систем. .

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

4 ...

сертециэнной работы. . ,

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

Поставленная пэль достигается решением следующих основных задач: .... ■ ■ ■

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

2. разработки формальных моделей систем реального времени.

3. разработки формальных моделей диспетчеров реального времени (ДРВ).

4. разработки метода исследования векторных СМО о переориентацией.

5. разработки архитектуры автоматизированной оистемы имитационного моделирования систем реального времени (АСШ СРВ).

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

Методы исследования. Решение поставленных задач проведено с использованием теории случайных процессов, теории ыасоового обслуживания (2М0), методов оптимизации. В случаях, когда аналитические реиешга получить затруднительно, используется метод имитационного даделирования, развитый применительно к задачам Ш) Н.П,Бусленко. Все формальные преобразования, относящиеся к преобразованиям абстрактных структур данных, выполнены о использованием идей и методов А.П.Ершова. Оптимизация процессов диспетчеризации проводится на основе методов динамического программирования.

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

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

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

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

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

5. Для такой модели узла СеМО разработан метод анализа, позволяющий аппроксимировать ее стандартной моделью СМО т*ша

м/$п/. ' •

6. С использованием этого метода показано, что уравнением динамики процесса функционирования СеМО является уравнение Динд-ли-Такача и приведено его решение в терминах преобразований Лапласа-Стялтьеса. *

7. Для исследования СеМО, не доцуокащих аналитических приближений, разработана система имитационного моделирования СРВ и приведена ее логическая структура.

8. Для всех рассматриваемых ДРВ сформулированы оптимизационные задачи и приведена общая схема алгоритма их решения.

{Трал, веская некность. Результатами проведенных исследования является ^орьалыстй язык описания ВСРВ, метод исследования, ал-

горитмы и программа, позволяющие оценить зсачеотво функционирования ВСРВ на разных стадиях проектирования, разработанные алгоритмы оптимизации позволяют получить оптимальный вектор управляющие параметров в зависимости от структуры ВСРВ, алгоритмов ее функциошфования и принятой системы оценки качества функционирования и принятой системы оценки качества функционирования. Применение разработанных алгоритмов а программ в ряде практических случаев позволило увеличить эффективность на величину порядка . 20-40%. С использованием результатов работы выработаны рекомендации по рациональной организации Ш в ВЕС автоматизированной системы УЗД (АС УЖ) и центре обработки данных ИЛ.СУ Бел.УГА.

Внедрение -результатов работы. Результаты диссертационной работы внедрены:

в работах, проводимых в ЦНИИ АСУ ГА по созданий научно-методических основ развития АСУ авиапредприятий к созданию интегрированных АСУ, (шифр тем 3.1.8 и 3.06.1.4 плана НИР МГА, шифр теш ШИТА 05-86), с экономическим эффектом 16,8 тыс. руб.;

в работах, проводимых в НЗЦ АУВД (НЭР "Модель", шифр тем МШГА 87-88 и 87-89), с экономически/ эффектом 13,1 тыс. руб.

Агообашя работц. Основные положения диссертационной работы и отдельные ее результаты докладывались и обсувдались на: Всесоюзной научно-технической конференции "Проблема совершенствования процессов технической эксплуатации авиационной техники, инженерно-авиационного обеспечения полетов в условиях ускорения научно-технического прогресса" (г. Москва, апрель 1988 г.); ХП научно-технической конференции молодых ученых "Молодежь за ускорение научно-технического прогресса", института ПермНИШ нефть (г. Пермь, октябрь 1986 г.); XIX и XX научно-техничеоких конференциях молодых ученых и специалистов института ТатНШЗИ нефть (г. Бугульма, апрель 1985, 1987 гг.) и научно-технических семинарах

в ШИТА (1987-1989 гг.}.

Публикации. По материалам диссертация опубликовано 7 работ.

Структура и объем диссертационной работы. Работа состоит из введения, четырех разделов, заключения, списка используемых источников (80 наименований) и приложений. Содержит страниц машинописного текста, ¡6 рисунков, 9 таблиц, Б приложениях приведены струхстура и текста исходных модулей разработанного программного обеспечения, а таете акты о внедрении результатов диссертационной работы.

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

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

I. МЕТОДОЛОгаЧЕСКИЕ .ПРИЩШЫ ОРГАНИЗАЦИИ ВЕШСЖГЕЛЫЖ ПРОЦЕССОВ В СИСТЕМАХ РЕАЛЬНОГО ВРЕМЕНИ

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

время репония основных функциональных задач;

8 ;' ■ ■ коэффициенты ухудеояия качества обслуживания. .

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

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

1. Уровень детализацда .структурного описания ВСРВ должен ' охватывать все разделяемые ресурсы ВСРВ. '

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

3. Управление ВП в ВСРВ - это набор определенных правил, характеризующихся измеримыми параметрами, на' основании которых осуществляется доступ к разделяемым ресурсам ВСРВ.

4. Логическим носителем этих правил является диспетчер реального времени.

5. Оптимизация управления в ВСРВ цроводится по пространству параметров ДРВ. •• ". ;

Для определения значений внесистемных характеристик ВСРВ необходимо учитывать следующие внешние процессы функционирования ВСРВ: .••■:■' ■'

процессы поступления транзакций на решение основных функ- : щональншс задач;

процессы отказов основных структурных элементов ВСРВ; процессы восстановления основных структурных элементов, а также следующие внутренние процессы:

процессы потерь транзакций в ограниченных буферных накопи-

....телях; ■• '.д--^----------- . .....

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

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

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

правилом'определения момента времени отключения источника , от ресурса.

В работе рассматриваются следующие реализации первого пра- . вила: - -г " "

циклический олфоо (С); квазицикличеокий опрос (К); случайный опрос (Р), . .

а также следующие реализации второго правила: с опустошением (I); . вентильное (2);

о ограничением (3); •• . - \

ординарное (4);

с сокращением (5) ; ■ . ,.'•,' .

• Бернулли (6); ,

гистереэисное (7); • о временной отсечкой (8). .

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

(о.яд). . ; . .

где ас^с.к.р}, ^€{^.3,4,5,^,83. те {с 2, 5*},

.<3 и Я определяют регипзаг^ш указанных выше первого и второго

правила соответственно, а Т обозначает порядок обслуживания транзакций:

в гфямом порядке (I*); в инверсном порядке (2*); приоритетов обслуживание (3*).

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

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

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

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

архитектура ВСРВ, под которой понимается состав и соединенна ыезду собой ресурсов (размеченный ориентированный граф);

задачи ВСРВ, как объекты, конкурирующие за ресурс (маршрут общем случае случайный - в гоатае);

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

тем строится математическая модель ВСРВ. _

■ 2. ТЕ0Р1ЛЖЕСКИЕ ОСНОВЫ да1ШЕРИЗА1Щ ЗЫШЗЖЕЕЛЫЖ ПРОЦЕССОВ В СИСТЕМАХ РЕАЛЬКОГО ВРЕМЕНИ .

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

В настоящее время отсутствуют общие методы анализа СэМО. Поэтому используют ряд искусственных приемов, позволяющих свести задачу анализа СеМО к задаче декомпозиции СеМО с последующим анализом ее составных частей.; ■ "._.,.

В работе.принято, что все выходные потоки узлов аппроксимируются экспоненциальными распределения!.®!; СеМО не содержи контуров. Поэтому задача анализа сводится к последовательному анализу ее узлов. Узел СеМО анализируется посредством расщепления его на N независимых одноканаяышх СЫО типа /М/6/1/. N обозначает число входов векторной СМО. Существо метода расщепления заключается в следующем.. ... •

, Определение 2.1. Задержкой начала обслуживания заявки называется интервал времени от момента окончания обслуживания всех заявок, накопленных к моменту поступления заявки, и моментом начала ее обслуживания.

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

Определение 2.3. Текущей работой прибора обслуживания (ПО) . называется сумма длительностей обслуживания всех заявок, находя-

12 .

щихся в система.____ _ ; ..'.»'•. У,

Используя эти определения, в работе доказывается, что век- • торная СМО с переориентацией функционирует-точно так же, как и одноканальиая СЮ типа /М/3/1/ в случае, - если <з имеет следующий вид: .. ' '

ЧМР* 1ВМ*Е(«)ИМ г.рЛ :

где В(*)- функция распределения (ф.р.) длительности обслуживания заявки;

Е(х)- ф.р. задержки начала обслуживания заявки;

ф.р. длительности прерывания обслунивания заявки; р - вероятность того, что заявка будет обслужена без за- . держки и без црерывания;

руо, - вероятность того, что процесс обслуживания заявки будет прерван т раз;

* - символ стилтьесовой свертки;

ы рва

Введем следуюцие обозначения:

' .Л»(л4,Л»,...,Лм), вектор нагрузки СМО;

- вектор параметров ф.р. в (зс);

-вектор

управляющих параметров, определяющих процесс диспетчеризации.

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

где ри'.СЛ,^,®) - вероятность того, что в момент прихода заявки потока буфер тыл пуст {далее слова "вероятность того, что" 1 опускаются);

*

2) диспетчер! (я, 2, I ): ,

где p'i> - заявка . 1-го потока поступила в пустой буфер и ПО еще не переключился на обслуживание заявок i -го буфера;!

pit5 - заявка I -го потока, поступила не в пустой буфер и ПО еще не переключился на обслуживание заявок i. -го буфера; •

pit - заявка L -го потока является первой после переключения ПО на обслуживание заявок i-го буфера;

Pw - заявка >-го потока является на первой после переключения ПО на обслуживание заявок i -го буфера;

3) диспетчеры (х, 3, I*):

. где - заявка i -го потока поступила в буфер, когдттам на-

ходилось заявок, & «о,..., и ПО еще не переклычшюя

на обслуживание заявок '«. -го буфера; ■ •' '.'

v - после подключения, ПО к L-му буферу заявка является

первой, и после отключения ПО от L-го буфера в бурере останется заявок; •.

рЗД - после поступления заявки число заявок в буфере tie будет равно &(£Vt+'0 . и ПО еще нэ перонлотилс^'на обслуживание заявок t -го буфера; ' ; . .

заявка,. поступпйзая после'подключения ПО к Гч.г/ бу-фзру,: после отключения застанет в буфере из более ,. 4) диспетчеры (к, 4, I ):

В*(зг,(¿да}"- __

5) диспетчеры (к, 5, I*):

Се) ''.>•'

где ри - к моменту начала обслуживания заявки I -го потока ПО отключится от 1-го буфера; .

6) диспетчера (х, 6, I ): ".'

где - в момент прихода заявки ПО ещё не подключился к «■

буферу и заявка является первой в буфере; :

р»; - в момент прихода заявки ПО еще не подключился к I -му буферу и заявка является не первой в буфере и к моменту начала обслуживания заявки ПО переключится на слёдужщий буфер;

' р»; - в момент прихода заявки ПО еще не подключился к I -члу буферу и заявка является не первой в буфере и к моменту начала обслуаивания заявки ПО не переключился на следующий бу] Рч1 - в момент прихода заявки НО подключен к «. -му буфе] .и к моменту начала обслуживания заявки ПО не переключился на с ■ 'дующий буфер; ' ''•;..'■ ' : - ■ /

'ра - в момент прихода' заявки ПО подключен к/'ь -му буфер к к моменту начала обслуживания заявки ПО переключился на след гаций буфер;

7) диспетчеры (*, 7, I):

, где р^, - к моменту начала обслуживания заявки ПО отклкяихся

"от 1-го буфера; -

• - *

8) диспетчер (к, 8, I):

„где ри - в процессе обслуживания заявка ПО не переключился.на другой буфер. .

. • Приведенные выше формулы для определения ФРОДО позволяют использовать. результаты теории (ЗЛО типа /М/в/1/<»/. Уравнением динамики процесса функционирования ВСРВ, под которым понимается уравнение, позволяющее определить функцию '

wU,xЗ*p{s*(tW<c},

где 5*0:) - виртуальная текущая работа СМО, - является интегро-дифференциальное уравнение:

дг ою о

где А - интенсивность входящего потока заявок;

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

^ "аП^мТГРмТ'

и моменты, реальной длительности 0ЖИДШ1ИЯ:

ж = мА м, [б*(«)з ~ м, [ в (*)], .

На основании этих результатов в работе получены выражения для определения моментоз виртуальной длительности озадания в случае диспетчеров (х, 8, ,

Диспетчер (С. 8. I ). "Заданы V; ¡.г^м

*

Э-О

где ci i. - ДЛИТвЛЬНОСТЬ ЮД1ШН,6!Р ПО к Л.-МУ буферу,

V0, ж

При условии, что и . шрвий

момент виртуальной длительности ожидания начала обслуживания •

^ ■

Диспетчер (К. О, I ).. Заданы Уц 1м,ы

л?, _

. где t? - дополнящие интервалы простоя; ■ '■-:

• . w v

■ T « S S .

«м . v. ■

•'•,■'■Диспетчер (P, 8, I*).'Заданы У;, Ы.Н .'•. ,•*;■

При'условии, что ^["Ц^Л-ЛИ^ .

у; ^

i ' - • Разработанный метод анализа векторных CMQ в работе назван, методом ФРОДО. Для остальных iPB получить в замкнутом аналитическом ввдз ФРОДО не удается. Поэтому метод ФРОДО используется в сочо^шси с вычаслйтелкпяА экспериментом, позволяющем определить Ч, спектра ФРОДО, под которыми понимается сеглейство функций.: ,

где - номер правила определения момента отключения;

I - номер входа векторной (МО.

, / 3. АВТОМАТИЗИРОВАННАЯ СИСТЕМА ШМГАДЙОННОГО МОДЕЛИРОВАНИЯ " СИСТЕМ РЕАЛЬНОГО ВРШЕНИ

АСШ СРВ предназначена для организации корректного вычислительного эксперимента над формальным объектом, которым является СеМО. АСШ СРВ включает:

подсистемы проверки базовых распределений "Х,1" по критерию равномерной сходимости (I) и критериям Колмогорова и (2); подсистему анализа тестовых СМО (3); подсистему диалогового ввода заданий на моделирование (4); операционный блок (5);

подсистему анализа результатов моделирования (6); сцравично-обучшощую подсистему (7). Подсистемы I и 2 предназначены для проверки статистической корректности предъявляемых последовательностей с.А. ; подсистема . 3 - для анализа точности известных преобразований с.в. ; подсистема 4 - для проверки синтаксической и семантической корректное-' ти. вводимых заданий на моделирование. Операционный блок предназначен для реализации собственно вычислительного эксперимента. Подсистема 6 по формализованному запросу выдает пользователю результаты моделирования.

Разработанный пакет прикладных программ (ПШ1) отличается от известных:

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

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

18 -. - ■;;. . наличием средств испытания моделей. t : Второй из перечисленных принципов реализуется путем использования параметрических стандартных "конструкций описания модели, в результате чего для перехода от модели одного реального объекта , : к модели другого достаточно изменить параметры базовой модели. Третий принцип реализован в АСЙМ СРВ путем включения в состав ба-. зовше математических моделей ряда таких моделей, для которых известны точные аналитические" решения.

Разработанный'1ШП позволяет проводить ■ исследование процессов функционирования различных ВСРВ без. этапа прикладного про- . граьмцрования. и этапа ^отладки.имитационной модели. -. ;■•.'■.

4. ОПТИМИЗАЦИЯ ПРОЦЕССОВ ДИСПЕТЧЕРИЗАЦИИ ЗАД/н В сиспшх . " РЕАЛЬНОГО ВРЕМЕНИ ■

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

Z, - £. ?,;-<ч(л.В,к). . ■

гг. йс^слдф^б^слдк),

гъ * tcf(ii)-v«1(iU,bli))+ i sM (a.b.ik),

z, * (*i(a.b(!k), Тя(л,в,к),...,'гДа1в,»:)),

Zsvimi «ЛД4

z* с К^.агддк), vr^AB.iK).....mw(iiAB,K)V

(MwUAM,... АСадк))] (

где IK - пространство решений (область управляющих параметров диспетчеров РВ);

^(ЛДК) - средаеэ время пребывания заявки в .системе.; -^(ЛДК) - коэффициент потерь заявок по i -му входу системы; т^ЛДК) - коэффициент превышения нормативного времени пребывания заявки в системе;

С;, Si _ соответствующие весовые коэффициенты. Требования оптимизации при использовании этих критериев следующие:

Z, —- ,

.к

А — ^,

vnin,

Ze —V r»in.

Б к 1

2 . f*m (t'AIMO 6i.íÑ

где t°, m!, - нормативные значения соответствующих величин ti, mnl, ki.

*

Для диспетчеров (je, 8, I ) задача оптимизации ставится следующим образом. Найти такие íef, чтобы

X

2 -- 2Г h

i г< '

(Л, а,I-) » п

vnin.,

IK

гЦ-ь^ЛдвД)]

и при этом JU -Я?' (Л, В Д) <4 где ^

j»< fc-o

£ рй(а,в(^гм,1&1(* (I.ípS

'Для решения этой задачи используется эврпстический алгоритм, кото-

' ' • 20 рнй ,баз)^уехся.на ^ледущэ&.овд ; ,;..,.._.. .

Определение 4.1. Чувствительностью I -го входа к изменению ' т-й компоненты вектора . называется величина :

где .,'. • ■'../. ■ ....'' • '",/■■." ■■•:'

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

В работе приведены формальные постановки и алгоритмы решения задачи оптимизации для диспетчеров (к, 8, I ). Для остальных . : ДРВ приведены алгоритмы решения задач, основанные на выявленной характера изменений компонент функционалов от монотонного изменения их параметров, которые позволяют находить локальный экстремум функционала. Выигрыш от оптимизации в случае, когда общая загрузка системы находятся в интервале 0,5-0,9, достигает валичл-ны 20-40$.

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

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

ССНОШЫБ РЕЗУЛЬТАТЫ РАБОТЫ .

Основные результата диссертационной работы сводятся к слодую-

ЧЯ»: .. .'■ ■:•'.'■■;.'•'-•:''.:'-

I. В процесса авамза сущестзугаах СРВ проведена структура-

: ' •. ■ . 21 ; зация объекта исследования и .показано, что уровень, конфликтов за использование ресурсов СРВ регулируется рациональной организацией вычислительного процесса в ней.

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

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

,4. С использованием теории абстрактных структур данных и. спецификаций построена математическая модель СРВ как параметрическая сеть массового обслуживания (СеМО) со смешанными источни- . ками заявок, контурами и петля;,га. Узел такой сети представляет ■ собой векторную СМО о неоднородным прибором обслуживания и переменным режимом работы, ' ■

5. Для такой модели узла СеМО разработан метод анализа, позволяющий аппроксимировать ее стандартной моделью СМО типа /1И/©/1/. С использованием этого метода показано, что уравнение динамики процесса функционирования узла СРВ является уравнение Линдли-Такача и приведено его решение в- терминах преобразований Лапласа-Стилтьеса. Для ряда частных случаев решение уравнения ; Линдли-Такача получено в явном виде.

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

причем псследоЕаш!Я.мо51НО..дровода15„как„со леей сетью, так и с .. отдельными фрагментами.

7. Для всех рассматриваемых диспетчеров РВ сформулированы оптимизационные задачи и приведена общая схема алгоритма их решения,

8. Результаты работы внедрены в ЦНИИ АСУ ГА и НЭЦ АУДЦ.

Результаты проведенных исследований позволяют сделать следующие в н в .о д ш

1. Заданное качество функционирования СРВ достигается рацц- . опальной организацией процессов диспетчеризации транзакций.

2. При проектировании систем диспетчеризации в СРВ целесообразно использовать предаонешше автором методологические принципы организации ВЯ в СРВ, модели и методы анализа систем диспетчеризации, а также автоматизированную систему имитационного моделирования (АСШ СРВ).

3. При исследовании процессов функционирования СРВ в ЛСШ СРВ время моделирования не превышает 1-1,5 ч (ЭВМ ЕС-1061).

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

временем решения основных функциональных задач;

относительными'коэффициентами потерь транзакций;

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

5. Выигрыш от оптимизации достигает величины порядка 20-40$.

•3. Использованию результатов работы при проектировании и анализе СРВ дало экономический эффект порядка 30 тыс. р^б.

По результата« "¿следований опубликованы следупдш работы:

I. Еаглгй П.А., ЯровскпЗ Ы.В. Анализ централизовашпа алго-р^п'?? доступа к ресурсам 1ШС ГА // Применение ыпкро-ЭЗЛ ищк- .

ропроцеосоров в системах управления и сетях передачи данных в ГА. -М.: МИИГА, 1988. - С. 127-132.

2. Иванов В.А., Яронский М.В., Шаглий Ц.А. Об одном методе нахождения стационарных характеристик векторных СМО // Проблемы совершенствования процессов технической эксплуатации авиационной техники, инженерно-авиационного обеспечения полетов в условиях ускорения научно-техничвокого прогресса: Тез. докл. Всесо-юз. научно-техн. конф. 13-15 апреля 1988 г. - М.: МИИГА, 1988. -С. 130. : -

3. Кузьмин А.Л., Яронский М.В. Использование динамических приоритетов в АСУ реального времени // Применение микроЭШ и микропроцессоров в системах управления и сетях передачи данных в ГА. -М.: МИИГА, 1988. - С. 87-95.

4. Яронский М.В. Простой подход к программированию диалога // Методы управления, оптимизация и проектирование сетей передачи в ГА. -М.: МИИГА, 1987. - С. 77-81.

i' ■

5. Васильев В.И., Яронский М.В., Шаглий П.А. Инструмента®,- . ная система имитационного моделирования процессов функционирования сетей обмена данными // Проблемы совершенствования процессов . технической эксплуатации авиационной техники, инженерно-авиаци-. онного обеспечения полетов в условиях ускорения научно-технического прогресса: Тез. докл. Всесоюз. научно-тех. конф. 13-15 ап- •• реля 1988 г; - М.: МИИГА, 1988. - С. 130.

6. Васильев В.И., Шаглий П.А. . Яронский М.В. Методы управления вычислительным процессом в системах реального времени // Сети и системы обмена данными в автоматизированных системах ГА. -М.: МИИГА, 1989. - С. 70-79. ■

7. Шаглий П.А., Яронский М.В. Анализ систем массового обслуживания с переориентацией // Сети и системы обмена данными в автоматизированных системах ГА. - М.: МИИГА, 1989. - С. 86-100. .

„„ .8. Шаглий П.А., ^Яронс1шй^.В^^ализ^гфиорих0Тншс_схем:уп--равления вычислительным процессом в СРВ // Сети и системы обмена данными в автоматизированных системах ГА. - М.: ШИТА, 1989. -С. 101-105.