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

РГ6 од

С.ПЕТЕРБУРГСКИЙ ГОСУДЛРСТГ<!:'!1Н1Л1 ИНСТИТУТ

- 8 ОКТ Ш&чной механики и оптики

(ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)

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

ИЕГЛОВ АНЛРЕЙ ЮРЬЕВИЧ

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

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

АВТОРЕФЕРАТ

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

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

Г-лота ьшмхшмш в Санкт-Ийтёрбу^гском l'íxiy д аро f r-, t? 11 ном институте точной механики и оптики (техническом ушнк;(х;итете)

(Иатнадыше оппонент: доктор ïuxiiH'iocKitx наук,

ПрС/феОООр

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

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

Очлн Мы'ешш Зч-дороьнч Берлин Алы;оан,цр Наумович Гапьдштейи Норна иоломсшокич

йе,цу1Дч<; прс'дщпштне: Лилст-Петербургский Государственной

научно - исследователь с»;»|й•шютатут ' "Глубин"

¡'«ынта 4,«!с«:-|)тацни состоится ОХ^Ял^Я___1996

» ___чаоов »а ьаседанпи дисое^тацигтшяо соыега

Л О!г..ü;.: при Сишет-Петег'ЗД/гекои Государственном ll.'ir.r.ir. то Точной Механики и Оптики (ТУ) и о адресу: IV/«i И, C.-a:m-4leiepöypr, ул.С:-Лллнокай,14.

о i-iадией ¡.южно Oi'Hfjjîc t.i.iTticn в fmfijjHoiVKe института. Hfl ..¡ ■ -1 ат разослан ____" ¿»96 г.

г

y.ii i iJ.1 i. Kpt'rapi, «lUT.'l^uliir'tnlOrO i

roiir'K» л ;i;.3-LJD.02 V \ д.т.к.

ii¡ * »¡liccop \\ A.B. Ушаков

ОШЛЛ ХЛ!'АК'ПЛЮТИКА ГЛП01Ы

Апгуаиьип'ггь пробда»мм. Опередатее до недавнего ирсысии раявити« р. во осач сезяатш и использования распределении/, ви-числительних систем (НС) имели сосредоточенные ВС, отлтзкячгея высокой У'1г»)ек1 ивжхзтью межчодульпмч взаимодействий по параллельной системной шине, либо г-ысокоск'фостннм коммутируемом каняпач (трпненьэгерныэ системы). ¿тффективиость функционирования сосре-дот ¡''(мнм« систем, ЯВЛЯЮЩИХСЯ кол.г.екТИГАЧИ ВЫЧИСЛГТеЛОЙ ¡1 1'рвД-подагаших, в-первую очередь, крупноблочное распараллеливание задам, прежде осу го определяется эффект явностью языков параллельного программирования.

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

Особое-место среди рассредоточенных ПС занимают проблем-по- оррентгроввипые ВП (ПОЛО • и ЛШ, используемые в задачах управления ОТО), в частности в. системах автоматического управления ГОЛУ) I! на нижних уровнях автоматизированных систем укрепления (АСУ). Требования»'! к работе в реальном масштабе времени 1И.1В) протекания управляемого процесса построение ВС здесь ограничивается -яееткпмп с-'рипотешгоми на время реакции системы на входные воздействия, вначекия которых могут, быть достаточна мал* (•огу-г- составлять миллисекунды и .их доли). -Таким оврагом,при возможности существенного увеличения мощности вычислителей, например путем объединения их в сосредоточенные ЕС (магистраль-ио-модульные УВС), ограничения на производительность межмодульные взаимодействий, вызванные требованиям« к высокой помехозащищенности передачи данных мевду вычислителями, остаются (в сс:г«-мэниых стандартах на пнтег^-'юм УВС физическая скорость передачи

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

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

С учетом требований к высокой надежности и модульности построения рассматриваемых ВС выдвигается требование распределенного или децентрализованного управления множественным доступом' к каналу связи магистральной топологии (к которому уже может подключаться любой иной общий ресурс, в частности сервер ЛВС), при этом задача управления доступом должна быть в равной мере распределена между всеми абонентами ВС, -т.е. • должна решаться устройством децентрализованного управления множественным доступом (УДУМД), задача проектирования которого сводится'к проектирован;!;:: дисциплины обслуживания и способа эффективной ее распределений») аппаратурной реализации.

Вольной вклад в развитие различных аспектов проблемы управления множественным доступом к ресурсам ВС распределенной обработки внесли учение России и стран СНГ Евреиноь Э.В., Хорошевский В.Г., Марчук Г.И.. Прангищвили И.В., Самойленко С.И., Каляев A.A., Поспелов Д.А., Варшавский В.И, Якубайтис Э.А. и др. ;

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

Чрезвычайно остро на эффективность построения исследуемых; систем сказывается предоставление сегодня крыше ограниченных возможностей диспетчеризации заявок в РМВ - современными стандарта*« на интерфейсы рассредоточенных УВС с децентрализованным управлением множественным доступом - регламентируется лишь дисциплина обслуживания в циклическом порядке (ДОЦП). Это не повво-ляei вагиазтъ от перегрузок высокоприоритетные заявки, имевдие более аесткле требования. к вреиени обслуживания. Реализация

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

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

Предметом исследования в диссертации являются: методы построения и проектирования УДУЩ в рассредоточенных ПОВС и ЛВС для УЬС, дищш:лЯлы иОсЛуживаНИИ ЬШЬОК В РМВ При функциональном распараллеливании . задач (методы диспетчеризации) и методы их проектирования, методы децентрализованного управления множественным доступом, включая способы передачи полномочий между абонентами ВС на право занятия ресурса, методы их проектировании и реализации,возможности унификации методов и аппаратурных средств.

Цель и задачи исследования. Целью диссертации является повышение эффективности проектирования и функционирования рассре- ■ доточенных ПОВС и ЛВС РМВ, в первую очередь для использования в УВС: САУ и на нижних уровнях АСУ, "узким местом" которых является связной ресурс, определяющий производительность ВС, за счет повышения эффективности управления множественным к нему доступом абонентов ВС, реализуемого распределенным УДУМД.'

Для решения поставленной цели в диссертации исследуются и разрабатываются следующие вопросы: -

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

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

тивно реализующих предлагаемый класс ДО со смешанными приоритетами (ДОСП).сочетающих в себе ОР и относительный приоритет (ОП)-- методов ДКУ для различных приложений исследуемых систем;

- рааработка методов построении и проектирования УДУ1ДД, в части проектирования ДОР (ДОСП), метода управления множественным доступом, в том числе и способа передачи полномочий в системе, структуры устройства с учетом унификации предлагаемых подходов.

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

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

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

- предложен новый принцип ОР для рассредоточенных ВС и ЛВС РМВ, "узким местом" функционирования которых является связной ресурс, состоящий в построении ДОР реализацией обслуживания заявок с назначаемыми динамическими ОП, изменяемыми по расписанию при каждом занятии ресурса ВС;

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

- разработан ряд новых ДОР (ДОСП) РЕМ,в основу которых подсоски предложенные принципы ОР и ОСП, предложена их классификаций ;

- предлслей • новый подход к проектированию расписаний FM3 (ДОР), Ь' основу которого положено отображение расписаний времен-suaiii ' характеристиками • обслуживания гаяьок, . разработаны методы

. nccrfÇôHHft и прсйкгирова-ш сппыалъкьрс (канокичесюк) расписаний, гкасчаа сиосэСа' задания приоритетов, для • альтернативных '

постановок задачи теории расписаний - детерминированной .и стохастической;

- предложен к использованию в рассредоточенных ВС РМВ принцип ДКУ РМВ, реализующий ДОР при оптимальности ЗРТ- расписаний и . позволяющий строить ДОСП, как единый (унифицированный) подход к,-построению разработанного ряда ДО РМВ , разработан ряд унифйци- . рованных методов ДКУ, отличие которых задается видом кодов 01! и их комбинаций, определена область эффективности методов, предложена их классификация;

- предложен новый подход к. повышению эффективности ДКУ в рамту р«тлизусмого оптимального 5РТ-расписания, состоящий в оп-' тималыюм кодировании', ОП абонентов и задании оптимальных правил смены кодов при занятии ресурса (динамическое кодирование), разработаны методы оптимального кодирования, в основе которых нахо- • дится различный приоритет уровней логического "О" и "1", предложена их классификация;

- получена новая обобщенная (каноническая) структура УДУМД, реализующая ДОР (ДОСП) РМВ методами ДКУ, учитывающая альтернативные способы задания приоритетов обслуживания заявок в РМВ.

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

Основнйе научно-методические разработки, представленные в .. диссертации, внедрены на предприятиях: . НИИ'"Рубин", ИМ "Дельта", ЛОТ "Интелтех" (правоприемник НИИ ЭТУ), использованы в лекционных курсах на кафедре ВТ ГИТМО (ТУ): "Управляющие вычислительные системы", "Теория информации и.системы передачи данных".

На защиту выносятся: • - системный подход к/построению и проектированию УДУЩ, реализующий предложенные взаимосвязанные принципы повышения эффек-

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

- новый принцип ОР для рассредоточенных' ВС РМВ, состоящий в построении ДОР реализацией динамических ОП, изменяемых по расписание при кладом вайятим ресурса, обеспечивающий высокую г^фек- -тинниеть ДОР и ьонмолкоить построении ■ ДОСП при аяьтернатиьнш способах задания ОП: с целью ващиты от-перегрузок заявок ГМ>, с. целью внеочередного (вне расписания) обслуживания' особо ¡.а+.ми;.-для ВС заявок;

- методы построения и проектирования ДОР (ДОСП) РМВ V, постановке детерминированной и стохастической задач теории расписаний , решаемых с целью эффективного использования ресурса гц-и различных видах.ограничений на качество обслуживания заяьок в исследуемых ВС, классификация разработанного ряда ДОР (ДОСШ PiV.fi;

- методы построения и проектирования ДКУ РМВ, предложс-шого. как унифицированный принцип реализации ДОР РМВ', обеспечивающий в системе оптимальное ЗРТ-расписание, . для исследуемых прилс*.«лшй ВС в рамках предложенной единой концепции реализации расписаний

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

- методы построения и проектирования приоритетных и оптимальных динамических кодов ОП абонентов,включая методы статического кодирования ОП и правила их изменения по расписанию, обеспечивающие эффективное ДКУ доступом к ресурсу ВС в любой момент времени ее-функционирования;

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

Апробация работы. Основные результаты работы докладывались и -обсуждались на:. XI Белорусской.зимней школе-семинаре "Исследование сетей связи и компьютерных сетей методами массового обс.«у-. ддоакия"(Минск, 1335), 11 'Межведомственной научно-технической К£К4*?*Н13'.5Г "ПрС'5лемж:е вопросы' сбора, обработки и передачи ин-в' сложных- радиотехнических] системах" (г.Пушкин, 1'УЛ),

11 Международной конференции "Математические алгоритмы" Гг.н.Новгород.-1995), II Международной конференции "Развитие и применение открытых систем" (Петрозаводск,1995), Х1У и XV Всесоюзных -школах-семинарах по вычислительным сетям (Минск,1989; ■ Ленинград ,1уУО), Всесоюзных конференциях: "Проблемы создания и ис- : пользования отраслевых информационно-диспетчерских систем на основе компьютеризации перспективных средстЕ связи" (Калуга, 1988), "Повышение эффективности производства и качества услуг связи на базе млектронизации предприятий связи" (Воронеж,19&8), на 46 и 47 научно-технических конференциях, посвященных Дню радио "Актуальные проблемы развития радиотехники, электроники, связи" (С.Петербург, 1991 и 1992), отраслевых конференциях: "Интегральные оптические сети связи" (Ленинград,1939), "Пути совершенство-' вания сетей и .комплексов технических средств связи" (Ленинград, 1989), на ХУП научно-технической, конференции профессорско-преподавательского состава ГИГМО (С.Петербург,1995), научных семинарач ЛИТМО, ЛИПО"Краснвя Заря", НИИ ЭТУ, НИИ "Рубин",НИИ "Дельта".

Публикации. Результаты проведенных исследований опубликованы в 77 печатных работах, в том числе получено 34 авторских свидетельств на изобретение СССР и 4 авторских свидетельств на патент !\">.

Структура и объем диссертации.Диссертация состоит из введения, нести глав, заключения, списка литературы ( 184 наимеиова-,;.тия.) и двух приложений, содержит 264 машинописных страниц основного текста, 86 рисунков.

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

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

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

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

В главе рассмотрены альтернативные пути повышения эффективности использования ресурса: реализацией ДО с относительными приоритетами (ДООП), реализацией приоритетной ДО по расписанию (ДОР). Первый подход позволяет защищать от перегрузок более приоритетные заявки, за счет отказа в.обслуживании низкоприоритетных заявок, что, с учетом введенной классификации заявок, можно эффективно использовать. . Данный подход реализуется методами децентрализованного кодового управления (ДКУ) и децентрализованного пространственно-временного управления (ДПВУ), где.последний неэффективен в рассредоточенных системах, так Ka¿ .требует линий арбитража. Недостатком ДООП является невозможность ее использования в;РМВ. ДОР имеет своим достоинством возможность использования в РМВ,. т.к. заранее заданное .расписание передачи полномочий не позволяет монополизировать ресурс более приоритетным -абонентам. К недостаткам' ДОР можно отнести следующее: ограниченная возможность защиты от перегрузок более приоритетных заявок, невозможность реализации.внеочередного обслуживания заявок, низкая '■ аффективност!»' передачи полномочий по расписанию в рассматриваемых 'приложениях, из-за передачи прав-по расписанию вне аависи-: мости от активности абонента. Последний недостаток проиллюстрирован прогедоппш. иссдедоваысм для маркерного метода (ДОЦП /частный случай ДОР) при. альтернативных способах реализации канального кадр§ для УВС - в стандартах niniMAP и MIL-STD-1553В.

' Результатом исследований явился обоснованный.вывод о нивкой : ь^-ктнбности известных ' ■ методов проектирования и построения .. УДГДЙ для исмЭДУешХ систем/, ограниченных ДОЦП, и определение /возможных путей 1Ю£ш;ения• эф^ектиЕНости управления множественным жозтурси; сдетсящх; в разр^отке методов, диспетчеризации, pea-

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

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

Общая идея предлагаемого подхода состоит в реализации ДОР путем динамической смены ОП в исходной ДООП в процессе функционирования системы в соответствии с заданным расписанием.

Лемма. ДОР, получаемая посредством динамической смены ОП, реализует РМВ при смене ОП, регламентируемой расписанием, во время'каждого занятия ресурса системы.

Для описания ДООП используем матрицу приоритетов, представляющую собой квадратную матрицу Q-Cqu] размерности МхМ по числу М абонентов. Элемент матрицы qi j задает ОП абонента 1 по отношению к j : 0 - нет приоритета, 1 - есть. Для описания ДОР (в общем случае ДОСП) используем граф изменения матрицы ОП в моменты времени ts занятия ресурса в соответствии с расписанием. Пример графа бесприоритетной ДОР, реализуемой методом динамической смены ОП, для случая М-4 .цикл расписания которой имеет вид (1,2,3,4), представлен на рис.1. Бесприоритетность расписания

\11 2 3 4 Ml 2 3 4 All 2 3 4 VII 2 3 4

1 Г 1 1 - ■ i 1

1 0 111 1 0 ООО 1 0100 1 0 1 10

- >2 о n i 1 1 ->2 1 0 1 1 ->2 0 0 0 0 ->2 0 0 10

3 0 0 0 lj 3 1 0 0 1 3 110 1 3 0 0 0 0

4 0 0 0 01 4 1 ООО 4 110 0 4 1110

tl t2 t3 t4

Рис.1

обеспечивается тем, что каждый пользователь входит в расписание равное число раз, в общем случае может быть более одного, например (1,1,2,2,3,3,4,4). . . .

Лемма. В любой момент времени ^ ОП йе должен' совпасть у нескольких абонентов системы (в противном случае в рассредоточенной системе неминуем конфликт сообщений в канале, недопусти->лй при функционировании системы в РМВ).;

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

различное число раз, например (1,2,1,3,1,4).

0Г1 в рамках ОР однозначно задаются расписанием, где в каж-- . дый момент времени 011 абонентов соответствует порядку передачи полномочий,, исключая повторные передачи прав одному абоненту в ■•' цикле ОР, . 'например для расписания (1,2,1,3) в момент ^ - ОП [•1,2,31, в 1г - [2,1,3], В 13 - 11,3,2], В 14 - 13,1,2].

Примеры графов ДОСП, иллюстрирующих альтернативные способы задания ОП, соответственно для защиты от перегрузок заявок РМВ и С' целью выделения внеочередных заявок, для М-4 представлены на . рис.2, на рк-о.2.а. 1 и 2 абоненты имеют ОП над 3 и 4, а 3 н;ц 4,

VII 2 3 4 \Л 2 3 4 \]1 2 3 4 VI I 2 3 4 1 г т . 1 г п 1 1 ' '1 00 11 10 111 10 111 ->2 10 11-, г>2 0 0 1 1 ->2 0 0 0 1 ---1

3 0 0 0 1 зооо1; 30100

4 0000 4 00 0 0 4 0000

11 12 и

а. о.

Рис.2

1 и 2 образуют бесприоритетное ОР (1,2), на рис.2.6.1 абонент ,имеет ОП над остальными, 2 и 3 над 4, а 2 и 3 бесприоритетное ОР между Собой (2,3). Обозначим, соответственно ДОСП [(1,2),3,4] и '11,(2,3),41, где в круглых скобках отмечен цикл ОР, в квадратных (будем называть это Циклом ДОСП) - ОП абонентов, упорядоченный в порядке . записи. В общем случае цикл ДОСП может содержать несколько циклов ДОР, например для М-8 [(1,2,1,3),4,5,(6,7,8)]. При отсутствии в ДО цикла ОР, например [1,2,3,4].имеем ДООП.'

Для ДО с динамическими ОП. изменяемыми по расписанию, функ- ' ция приоритетности заявки т,гп-1,М имеет вид ___ /

Фт(1)-ашз(1з<1п<13+1) + /Цпс1(Ьс1.с1-1,6),

где Ог,1... -исходный ОП заявки поступающей в момент 1п , , соответс-тьувиДй б -му состоянию цикла расписания, длиной 8 : 5-1,6 ; Лс<,..с1 - приращение (может иметь отрицательные значения) приоритета за^шки, получаемое при смене состояний цикла расписания 1а,сИ,(3 Для заявок, обслуживаемых с ОП, для любого б-1,(3 И для лйбого .3-1,Б : йтэ- сопб1 .. ■:

^ассифика^ методов диспетчеризации, получаемых с исп-псаььоваьиеы предложенного подхода, составляет следующие ДО: ДОР с йесприсршеТпым. и приоритетным расписаниями, ДОСП с ОП заявок либо ' внеочередных заяьск,'. а также и тех, и;других видов ;ДХП) . Длл: ¿¡реп юсюда реализация нескольких • .'р&гп.одмЗ : 5 ; ..которые соответственно мзгут Сыть

0 111 0 0 11 0 0 0 1 0 0 0 0

беснриоритетными. приоритетными, теми и другими.Кроме того,возможны болеем сложные методы диспетчеризации,. в которых в цикле ДОСН изменяются циклы 0Р,0И циклов ОР и- отдельных абонентов и т.д.Для каждой ДО может использоваться как ординарная, так и любая групповая,в частности вентильная стратегии обслуживания заявок.

По второй главе применительно к рассматриваемой задаче, где в основе ДО РБ'М лежит передача прав на обслуживание заявок в ВС по расписанию, исследуются проблемы ОР, в результате чего делаются выводы, что существующие сегодня способы, численного описания. формального представления и проектирования ДОР для рассматриваемых приложений ВС мало пригодны. Предлагается способ формального описания ОР И® временными характеристиками цикла расписания, имеющего для каждого т -го абонента ВС вид . . т-----т--------.ГМ, -*гит1 ¡^ (Тгпш+ТгрО-

где ТптЛотЛппт - соответственно, время арбитража (предоставления абоненту прав на занятие ресурса с' момента выставления им требования ресурса в систему), обслуживания заявки, занятия ресурса для информационного с ним взаимодействия,передачи полномочий следующему по расписангао абоненту, Кгнт)- коэффициент частоты предоставления прав 1 -му абоненту относительно т -го в цикле расписания. Если все параметры расписания •"'гппт.Кп (т) Лгрм ограничены, имеем расписание РМВ с характеристиками Трат, ТГот."1-1,М . Введенное описание ОР позволяет трактовать приоритет РМВ абонента т над абонентом га' кал отношение 5щ-т,-Тгот''/Тгот . при этом говорить, что абонент т во столько раз приоритетнее ш' , во сколько.раз ТГои.меньше ТГОт' Св все заявки должны быть обслужены). ■ С учетом возможности задания нескольких очередностей передачи прав абоненту в цикле расписания, например (1,2,3,4,1,2), с номерами 1-1,Ь (здесь т-1Л.-2), будем разделять задание' приоритетного расписания по гарантированным 5щНТГот1 > 1-1,1-} и средним гарантированным ЕщгТгот! 'математическое ожидание) характеристикам ОР,- Тогда бесприоритетным будем называть расписание (например,ОВД), для которого характеристики ТГот и Тгот всех абонентов си-'.темы совпадают. Таким образом, из (1) следует, что приоритет расписания РМВ может зада ваться тремя параметрами ТГппш»Кг 1 (т) Лгрш и различными их комбинациями. Очередность передачи прав при анализе ОР РМВ будем

(1)

анаиийировать. на' графах цикла ивммн^ния максимального он (.каждой вершине графа- соответствует матрица 011);'" направленными дугами. шшшстрируется смена .максимального ОН в цикле расписания (петля обозначает, Что ОП не изменились. отсутствие ветвлений ■ выходит одна дуга -вырожденность града, реализующая альтернативный спо- ■ сиб задания равного приоритета).

ИВчдено понятие канонического расписания ГШ, .-отличающееся . тем, что при передаче прав в соответствии с которым между M ' .поль'и.ыт-лями, разбитыми на г уровнем приоритета r-l.R.if.i-l .Мг; для ыч-х m, : Trom ." ТГот " Тгот - min.

JU;mmu. . Каноническое расписание РМВ оптимально.

(.вдетый!. ОЦП (вырожденный РШШ) реализует каноническое (оптимальное) бесприоритетное расписание РМВ, а Д0Ц11 беснриори-тетна, »-ели для всех абонентов ВС совпадают, значения параметров Тн-., •

Л'-ьа.1.1. PacriHCítHiie РМВ, РГ1ТГШ которого имеет ветвления, ы i ¡ a i приоритетно.

1>-«||»чиская интерпретация канонического- расписания предс-тавля. т ию.:>ю радиальный граф с поочередной передачей прав (Priilill), получаемый с использованием следующих правил: из каждой верц.ши i приоритета должно выходить ровно Mrvi/Mr . дуг, где Мги-'М,- ... (это .является и ограничением на общность ка-

нонического расписания), все вершины приоритета R должны соединяться с ьершшой приоритета 1 (в которую дуги входят), для каждой |;.<ол< дую:иий очередности передачи прав на каждом-уровне приоритет л выбирается ноЕая вершина. Характеристики канонического рас пил линя имеют вид

6,-r— (KMr-l)/(RMr'-l) при ЬеЬЫрОЛСДсННОМ РГППП,

(Мг/(Sr-t Dï^q.1 (Sqtl) -1 ) Trpm+Trnnm ûr-r------:-:-

(Mr'/(Sr-+1 (Sq+1 )-l ) Trpm+Trnnm при ..лдешюы РГППН на уровне приоритета г, имеющем 3Г«Ю уровней Вироаденности (ограничение Mi'+i^Mr-të+k) (Sr+l),k-0,l ,2,... ).

Исследованы альтернативные принципы построения (в том числе И назначений приоритетов абонентам ВС), соответственно проектирования, ÜP. Первый представляет собою постановку и решение де-■.гернинигоБаиной задачи теории расписаний: Mlljían»- -» mln,1W < V Trct.r, -irг"»-Mf, r-l,R и сводится к построению расписания -' «деяачекием абонентам БС приоритетов,и гаданием очередности, пе-

редачи праи м«жлу «ими <; ндмгьи минимизаций производительности pecvpo.4 (.¡уц-сь издается условием 1П.„„ ► max ) при-соблюдении ограничений ГШ. С - учетом ¡изданного алгоритма Функционирования ВС, синтезируемого с целью минимизации числа Lrm взаимодействий с ресурсом продолжительностью Тп,„, какднм абонентом системы, время Реакции Ггрст in-го абонента. на входное воздействие составляет Jrrrm - Trp?.m+I.ri»Trom. где ТГр-:.п, - продолжительность' решения задачи собственно вычислителем. При бес приоритетном ОЦП прои.-шоди-•тельность ресурса задается для всех m неравенствами

~rD?nitLi-mTrom int (ТГрСПЬт-Г,М> и характеризуется коэффициентом ее избыточности для каждого абонента ВС: брг.т-'Ггрсп/вйПтТгрст • Неизбыточное (оптимальное) использование 'ресурса достигается при назначении приоритетов або-, нентов и:? условия

Тгрсп/Пгрот"1 Lrm from) : йрст" - •

rninm-fTrpcrnATrpjm+LrniTrom)) Проведено исследование эффективности рассматриваемого подхода при различных соотношениях Trp?m-kTrom и различных !.гт, в результате которого сделан вывод о высокой его эффективности при сильных различиях значений Тгрзт и ТГот Для различных Lrm - так при ¡-mi -1 для М-16 при к-1 в пределе имеем трехкратный выигрыш в производительности, при к-0,01 -четырехкратный, соответственно при М-64 в 8 и 16 раз (при Lrm -3, М-16, к-1 уже четырехкратный). Заметим, что параметр тго,п здесь определяется ОНИ. Отсутствие выигрыша при условии к-100 подтверждает неактуальность исследуемой задачи для сосредоточенных ВС.

Для получения канонического расписания в общем случае рассмотрены два подхода, положенные в основу разработанной методики проектирования расписаний РМВ: уменьшение ТГрст более приоритетного абонента возможно лишь за счет уменьшения числа уровней приоритета R /уменьшение Тгрст менее приоритетного абонента при запасе в ограничении на Тгрст более приоритетного абонента при сохранен!'!! переменным R возможно реализацией вырожденности РГЛПП ца менее приоритетном уровне. Итерационная процедура синтеза расписания FT© состоит из двух этапов.На первом этапе с. использованием полученных рекурентных соотношений

/ Troitir-i-<n-r-i+R-1) (TrptTmn)

{ Tromr^j-^ViTromi-l»_

Trpm-Trp ■ Trnnm-Trnn ,M.

для нёвырсвденного гра&а, для вырожденного РГП11П (Sr-l,Lr.Sr^O)' . I' r=lSr+R)(TriJ+'-lYnn) ___

| Trornr=i-^LlSi»ontl)Si (Tromi-l - (L.-Sj) (Trp+Tmn)), i-?,R , 1грт~Тгр.Тгппт"Тгпп»П1"1 .M и двух подходов к изменению расписаний в рамках РГ11ГШ исходное множество субонентов разбивается на приоритеты с учетом вырожденности К,Мг.г-1 ,R,ERr=iMr~M,Si =1,L.r. "ir.-зг . что при полученном максимальном Тгр (минимальной производительности ресурса) обеспечивает выполнение ограничений РМВ. Па втором этапе, с исполь-воьсишем правил синтеза РГ1ШП строится граф передачи прав в рамках полученного на первом этапе разбиения абонентов на приоритеты с: учетом заданной вырожденности графа.

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

Альтернативный подход к проектированию расписаний состоит в синтезе SP.T-расписаний - "короткая работа" вперед '(SPT-p). Под длиной работы Тот понимается время

Tom-Trimnl''lpm •

Если 'i'ourf (Tnnm) ('¡то имеет место в рассредоточенных УВС, характеры: ,'емих малыми объемами передаваемых ьа сеанс обмена данных) актуальна . задача минимизации .Непроизводительных затрат времени на передачу прав в системе абонентам, не требующим ресурс, который, ь предположении, что только К»а») предоставлений прав i -м абиНиптам из Kim (ш) используется, имеют вид

(Кг i Cm)-Ki (но )Tnmn • (2)

CaiffcuTCTBeHHO, основой синтеза SPT-p будет предоставление прав на ачннтие ресурса чаще тому пользователю, который чаще требует ресурс, т.е. ,Kj(m)-fUm) . где Ат- интенсивность поступления (потока) m -х.заявок.

Лемма. SPT-p оптимально, если оно реализует РГППП, задаваем

Mi-ill .•»сдовилыи _

Х„,г/Лтг-Пг'"11 -1 (Ml+1/Mi). г < г', г'-1, R. Подобные SPT-p назовем каноническими. Разработаны два способу ¡|с.<.П1А-,иния канонических SPT-P. соответственно введением петель в .РГШД1 при Xr,r/W>nr'*'1i-%(Mi+t/Mi) и реализацией вырожденности ИШ1 на уровне г* при Xn-j/W'<nr'-1i»i(Ma+i/Mj), учтенные в • адатветствуввэй методике синтеза SPT-p в рамках решения стохас-; тической аадача синтеза расписания: • М.|1|ДТат mln, Tcmr < •• Tt ecu > П-r-l.M;-, r-l,R.

С учетсы-.' негсйцгэшости- испол^&ОЕ.анкл классических плодов

пннярат.ч теории массового обслужинанид 1; рамках анализа расписаний (и.ч согодияшний день испольвуютея аппроксимирующие функции, имеюгаие ь<оьма ограниченные возможности и пригодные в большинстве случаи-; .лишь для анализа ОНИ), к 'данных приложениях применяются методы статистического моделирования, использование которых целесообразно уже в рамках заданного каким-либо образом расписания. Поэтому актуальной является проблема разработки процедуры, опрсдилятей методы зядания исходных расписаний, пути и способы . их '.".м-нений с учетом результатов статистического моделирования.

учетом многообразия ограничений на качество обслуживания ?аяь'.ж в рассматриваемых приложениях ВС разработана сообщенная методология проектирования расписаний. В основе синтеза ЛОР для ВО с жесткими ограничениями лежит разработанная методика синтеза приоритетного расписания , что также необходимо и при комбинации видов ограничений. В основе же синтеза ДОР для систем с р.ероят-. ностнши ограничениями (в основе экономия мощности ресурса) лежит разработанная методика синтеза ЗРТ-р. Для ВС с жесткими ограничениями синтез расписания на этом завершается, с вероятностными - анализируется выполнение ограничений в рамках полученного расписания. При невыполнении для исследуемых заявок задаются но- ^ вые значения ТГК1,?т (увеличиваются, либо уменьшаются полученные значения этих параметров для исходного расписания). После лтого (задали вероятностные ограничения новыми гарантированными пначе-' ниямп, что возможно т.к. в любом случае имеем расписание ГМВ). можно перейти к синтезу расписания в рамках детерминированной ■ ■•адачи. Данная процедура итерационно повторяется до получения расписания с требуемым качеством обслуживания заявок. Таким образен, пинте?-расписания ВС предполагает использование единой разработанной методологии проектирования, в рамкач которой - использования одинаковой итерационной процедуры, в основе которой лежит разработанная . методика синтеза приоритетного расписания. Различие для ВС с различными ограничениями на качество обслуживания (вероятностные и комбинированные) составляет использование различных подходов при проектировании исходного расписания - для последующего итерационного преобразования" (различных методик синтеза оптимального расписания). Здесь представлена методология синтеза расписаний РМВ для ПОВС, для ЛВС она аналогична с тем лишь отличием, что в качестве ограничений используются не параметры Тгрсш. а параметры ТГОт ( не заданы ЬГщ и Трэт ).

В третьей главе исследуются вопросы построения и проектиро-

ваиия ДОШ (ДОР) РМВ, а ociiow. реализации которых нслиоль-и.ч идея метода ДКУ, выбор заявок для обслуживания при котором исушчсг вляется поразрядным сравнением кодов ОН. чем обеспечиваются он тимальность расписания - GPT-p.

Исследована эффективность ДОСП нмв в альтернативных пршк- . жешшх использования ОП. Эффективность использования он с цел на защити от перегрузок заявок РМВ, с. учетом известного закона Vox-ранения времени ожидания для ДО ElimRiWi-const , где '. 1-1.1. уровни 0П,К'] -. загрузки уровней 1 ,Wi'- среднее время ожидания заявок класса-1 , дает соответственно выигрыш для заявок ¡-'МЬ ОП 1 (для них имеем ОЦП) и проигрыш для заявок Ш 2 (пусть между coöl.h дня них также ОЦП) или ДО [(1,2;... ,S ), (3 + )-,... ,М ) !•

.W-W1-W2-C I :--—---- I, с-о.{£1-"21-1хг'»(й,])

i il-K'i)il-K-) 1 -R1 . (¡im ...Орноотке заявок с ОП по схеме, характеризуемой тем, что и систему поступает М простейших потоков .с интенсивностями 'Ль ...,Лм и длительностями обслуживания it,'.... ,Ум со вторыми на-

Ч..Ш. НСМИ моментами Y(ö)l.....l(2,MSRl-£K«»lRm.R2-^m-L+lR»i -со-

о-гьесс.iMH-HHO загрузки, создаваемые потекши различных ОП (обслу-жи| а;лк- заявок каждого »usacca реализуется на основе дисциплины Flr'i'i. fliuic-v! покажем, что подобное упрощение корректно для. метода ДКУ:.. Н-ецниа ожидания заявок монотонно убывают с ростом ОП. Ваш -и ньляется оценка выигрыша заявок РШ именно по параметру РМВ, 1, частности Тгот • В предположении, что заявки РМВ имеют ОНИ и TriKiiii,Trpm соответственно совпадают - для ь-ех ш (бесприори-тетн;.<; расписание) имеем выигрыш, получаемый в обслуживании вая-- вок 1MB

ДТгопг(М-3)(Тгпп+Тгр)

или, соответственно в относительных единицах öTror,-M/S . Это го-' ворито том, что в предположении Тгош>Тгрзт. за счет введения ОД в послуаив-ннии заявок, требования к качеству обслуживания заявок РШ мохно обеспечить с экономией производительности ресурса ("узкого места") в M/S раз, причем в отличие от метода пос-трое1 нил приоритетного расписания вдесь выигрыш может быть получен и для система ОЦП РМВ. ЗДфективность введения в систему внеочередных '-ь<шок ОП имеет смысл оценивать мерой внеочередности их обс-лучиивашы или предоставляемым для них значением параметра ТГОт , с.хтлыШ(Щ!м для' одной'валька ОП Тгй.-м-'2Тгпп+Т; ,., (при .дьух и бо-

Лг*;': l'BülCK C'I НгОбХОДИМО УЧеСГЬ рс-£ь3и«уемуи ДЛп «ИХ- ДО.)..

Особенность. |11л!Лдо№-:ниог0 метода ДКУ состоит в том,, что в' любий м<.!м>унт времени МП взаимно однозначно сопоставляется матриц» кпдоп ¡"'И (МКЩ.'пример которой, в предположении, что "1" г- разряде кодового слога приоритетнее "О" (.по "1." права Переда-

К'ГСЛ, ПО

О"

та "го П'.>р',-|д|у

нетл приоритет разряда кода убывает по мере рос-'■ого номера и ,' приведен на рис.3. Соответствующим

МП

4

МК11

т

3 4

4

1 !

П 1 О I

Рис.3

образом (заменой МП на МК11 го все времени , см.рис. 1,2) получается грат]) ДО для метода ДКУ. При управлении доступом к ресурсу дсуи.ествляется поразрядное (начиная с более приоритетных разрядов) сравнение кодов ОП абонентов,затребовавших к данному моменту времени ресурс, с отключением по каждому разряду менее приоритетного абонента - при однозначном кодировании доступ к -ресурсу получает только один абонент.

.Лемма. Метод ДКУ реализует оптимальное ?РТ-р передачи полномочий (отсутствует поочередная их передача от одного абонента другому - право предоставляется сразу всем, после что выбирается приоритетный).

Оценка эффективности метода ДКУ, реацизующего оптимальное ¿РТ-р.проведена с использованием следующих моделей: аппроксимирующей функции (наиболее точной сегодня модели для метола поочередной передачи прав ) ОЦП для однолинейной (.'МО ОЦП а М очередями неограниченной длины с ординарной стратегией обслуживания заявок, где ,-<„, средние затраты (случайно) на передачу полномочий, «¡(2)т- вторые моменты,«-Е^т^тйт - соответственно за полный Цикл при ОЦП (остальные параметры те же, что и для предыдущей модели) !-!?+РП1 • /-/? К

.-Ют - ---— X----X

1-К-Ат«т р

и-т

Е?4!-! Х1К

(?)

1

2 (1-й

Е«,

(2)

для передачи прав предполагалась• поочередная передача адреса (кодового'слова ПокДО' • разрядов) абонента. Соответственно. п

этих же предположениях для метода ДНУ (для любого m имеем)

(Ь U'me) 1("';... ": V'mc 'i/"

2(1-R) i •',,,:

■здесь отсутствует передача прав в явном виде, a in„: складывается из двух составляющих Трш и Tnnm ( где ТПит в. рассматриваемом случаи fnnm-const ), на параметр W не сказывается несимк^трич-ностваагрузки системы. Исследование проведено для примера УВС, харгилч-риауемой следующими параметрами:М -256, обгем ш-редньае-мой нифирмат.пи 1 байт, длина информационного кадра (в дошмх рекомендации MIL-STD-1553В) 4 одиннадцати разрядных слова,, длина наркера задается длиной кодового слова. Показано, что максимальный выигрыш от использования ДКУ получается для 01Ш (с-спил-вен-. но, i-.ojih при несимметричной загрузке для метода поочередной передача реализуется SPT-p), где он весьма велик нрежд« всего для HiiiiK.i;'. и средних загрузок, составляя десятки pan. При неспммет-.ричииЛ нагрузке (реализуется SPT-p) также получа«м выигрыш, т.к. ДКУ р!-али;-.ует оптимальное (наивысшая эффективность) :;рт- р. Длаее исследована проблема оптимального кодирования приоритетов абонентов Iii!.

Таким образом, метод ДКУ для,исследуемый приложений ВС об-л^и1'- j олидумдими ъажнийшимй особенностями, обусловливающими целесообразность его использования: оптимальным образом реализует ДОР тш'Пмальиое SPT-p), позволяет строить ДОС'П, причем в рамках едшь л :> механизма управления множественным доступом - дин.чмичес-кои • a: li.jii (либо оез изменения) кодов ОП абонентов ВС.

[.и,,ьраьансь с учетом сказанного к выражению (2), отмечаем, 4iv- л-',: ДК1' всегда Kpj (ш)-Кнт) и ДТат-ГПпппО . Предположим, что г а арбитраж заявок по каждому разряду кода ОП nm-1,Nm (число котарьч при равномерном коде n-Üog2M], где D-2 - основание кода» приходятся удельные затраты Тщчу .откуда получаем

(3)

(3) определяет альтернативные пути уменьшения Тпшп Кос. следствие Тррст. задаваемые изменением параметров Nm и ТПпу". flaptwft иь них может быть сформулирован в постановке задачи опти-цл/лього кодирования: для заданного вероятностного ансамбля ■ <to,;v,bl?VfiPnri> . где Pn( ~ распределение вероятностей заявок на мнслесгве М , накти множество кодов ОП длиной^Mw, m-l.M, обраща-¡¡ ;,i!x .ч минимум среднею скорость кодирования R-l^V-iftbNrr,- Для ре-рассмотренной классической вадачи теории информации может

бить мснавьзглод, например метод ХаМмена. Особенностью другой постановки задачи оптимального кодирования ОП будет приоритет уровня "1" над уровнем "О" (исходно задали таким образом) в каждом разряде кода с Л1 , что может быть учтено при задании характеристик интенсивности поступления заявок р: 0 Чр <1. Разработаны и и-.'.следи,паны методы поэтапного арбитража при ДКУ - но части разрядов кода 011 как дли равномерного, так и для неравномерного кодов I часть разрядов кода не дают в общем случае однозначного д<.-К1.д«К'1«!Ш1и абонентов, что требует обнаружения конфликтов од-ио1'рем- нш.го занятии ресурса несколькими абонентами) - конфликтное 'кодирование, критерием оптимальности которого будет

1<Р»ъР) , ГДе Р£т(рт,р) - верОЯТ-носчь иднсниачного декодирования по Бщ разрядам кода, при условии оптимального выбора -*■ гп1п.

Лемма. 11а интервале изменения параметра р : О р С 1 всегда найдутся значения Pi.P2.P3 . где ра < рг < рз . такие что шши» -щуп -»ффектмвность имеют кодовые слова (содержимое од- ' ноги оа:- ( ллм вс.;х кодов 011) содержащие большее число единиц -неравномерный по "1" код (рг),равное число единиц и нулей - равномерный код IР2'.большее число нулей - неравномерный по "О" код ЦЫ.

¡■ы д. ны понятия предельно неравномерных по "1" и по "О" кодов, примеры которых для случая М -4 представлены соответственно на рис.4.а и 4.6, первый из которых эффективен при р -» 0, второй

\ iii 1 о 3 4 \ гп 1 2 3 4

11 г п

1 1 1 1 1 1 0 0 0 1

2 0 1 1 1 2 0 0 1 0

3 0 0 1 1 3 0 1 0 0

4 0 0 0 1 4 . 1 0 0 0

а. 0.

Рис.4

при р - 1, причем, предельно неравномерный по "О" код обеспечивает поэтапный бесконфликтный арбитраж (бесконфликтное кодирование) .

Следотьия.

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

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

абоненток.

В полной мере длиной кода ОН параметр Тпши определяется в тех приложениях ВС, когда время распространения сигнала но каналу тс намного меньше периода выдачи информационных битов в канал' связи Ти : Хс < Ти ■ Для альтернативных- приложений: > ги разработан метод оптим,ального кодирования, состоящий в минимизации параметра ТПпу • Идея данного подхода - группового кодирования, Н|л>илл««.:трй11шс1шцш' для М -ь на рис.Ь, состоит в дискретном уменьшении параметра ТППу ( Для ДКУ - 2тс.) за счет разбиения абонентов "на группы, с последующим, арбитражем заявок внутри группы абонентов, продолжительность которого соответственно сос-тавляет.-Тппу (2т.'с ) - по первому разряду,Тмп.у/£ ( в,.: ) - по второму и т.д., в общем случае 2тс/2пп>~1 . откуда получаем, что затраты времени на арбитра« при данном-способе-оптимального кодирования ( в общем случае - равномерного) ..составляют: ШТПлт (М •"•) < 4тс.

, \ Ш 1 ' 2 3 4. 5 б 7 У

О О О О (1 1 1 1) О 0 (1 1) 0 0 (1 1) О (1) 0 (1) 0 (1) О ( Г)

РИС.5 .

Лемма. Всегда - при любом расположении абонентов в системе, их можно разбить на группы либо по числу абонентов., либо по длине участков канала, таким образом, что Потери на арбитраж составят: ПгаТппш (М-«°) < 4хс.

Разработана единая методология оптимавьного кодирования 011, .учитывающая возможность и очередность применения предложенных методов для синтеза оптимальных кодов. С использованием выражения (4) проведена оценка верхней границы эффективности методов оптимального кодирования/для предельной несимметричности загруз-, ки системы, где при оптимальном неравномерном коде имеем Х1>Аг-..-Ам,Мт=1-1 ,- и для симметричной загрузки в области эффективного использования метода . группового кодирования, где для всех лсЛт-ПоггМ]. Показано, что здесь может быть получен выигрыш в условии стационарности загрузки системы, составляющий для к;--~«гдуемой системы (с теми же параметрами, ч-то и ВС, исследуе-/шее) до 25%'; т.е. может быть получен существенный выигрыш в эффективности функционирования системы в области высоких загрузок. Высокая эффективность методов подтверждена и результатами исследований изменения коэффициента использования . пропускной

1

2 3

способности канала сьяяи ЕС.

Ранее отмечалось,- что изменение параметра Nm является одной и;; шгмлошострй изменения параметра Trnnm . т.е. задания приоритетов о&слухишшя ыдаж.в РМВ. С учетом этого разработан метод приоритетного кодирования, в основе которого лежит использование неравенства Кргmira-для префиксных кодов Lwm»iü"Nr,4l. Код строится F; два гсрапа: исходя из соображений задания приоритетов абоненты-, знцачп'ся длины кодов с проверкой на возможность и оптимальное« построения префиксных кодов,после чего строится код с заданными д.«ии.'1ми, в основе • чего лежит правило - коды OII Ц абонентов с. од и лаковой длиной кода ОП должны различаться в старших ' I loypúJ разрядах кода.

С. учч'тт полученных результатов, связанных с особенностями при;., i, «. .i },-.■ ида ды, уточнены задачи отдельных методов проектирования ДО РМВ в рамках общей методологии,представленной ранее, в частности - в.задачи синтеза SPT- р здесь входит нострое-1U!'- oimití:ai.rtoro кода ОП, в рамках синтеза приоритетного расписания i-i:.:nojii.с.уется метод приоритетного кодирования ОП, в результате применения которого задаются значения параметров Тгппт

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

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

С целью эффективного использования в системе разработанных V способов оптимального кодирования ОП в главе исследуется проблема изменения кодов ОП в процессе функционирования системы в соответствии с графом ДО, рассматриваемая как задача оптимального ' динамического кодирования ОП.

Лемма. Динамический • код ОП оптимален., если оптимален сое- :

тавляющий его в каждый момент времени функционирования системы• статический код ОН.

Под статическим понимаем любой код,составляющий в сооот-ветствующий момент времени динамический код ОП (элемент динамического кода).

Критерием оптимальности динамического кода ОП, реапизумцего изменение статического коДа в соответствии'с заданным расписани ем, будет скорость динамического кодирования П^-^'т-аРт'-тп.- где Рш ~ распределение вероятностей статических кодов ОП на множестве М : Е^1П1=1рт -1 , задающих средние скорости кодирования !?„, условием оптимального выбора кода будет:Рд->шп .

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

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

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

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

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

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

Лемма. Разработанные методы динамического кодирования обеспечивают совпадение скоростей динамического и оптимального статического кодов ОП Рд-К^пг-пйп или реализуют в ВС все преимущества разработанных методов оптимального кодирования ОП для метода ДКУ.

Для ДОСП кроме того, необходимо уточнить в какие моменты

времени изменять приоритеты заявок ИЛВ при двух типов заявок с системе - РМВ и ОП (для ДОР определили ранее).

Лемма. Для обеспечения максимальной эффективности обслуживания приоритетных заявок Р№ изменение статических кодов ОН по расписанию следует осуществлять при занятий ресурса заявками лю- . бых классов приоритетов (в противном случае - при изменении только- занятием ресурса заявкой ОП параметр ТГОт приоритетной заявки ГMB увеличится на Тгпп+ТГр - считаем их соответственно сониадаклцими для всех абонентов ВС).

(.' учетом обоснования использования для управления множественным доступом к ресурсу в исследуемых приложениях ВС метода ДКУ, реализующего оптимальное SPT-p, и выделенных на основании (1) способов задания соответственно реализации приоритетного обслуживания ь РМВ - изменением параметров , разработана каноническая структура УДУМД, определен состав и назначение его функциональных блоков и их связи. Под канонической здесь понимаем структуру устройства, реализующую все предоставляемые возможности задания приоритетов и содержащую М однотипных модулей,являющихся принадлежностью соответствующих абонентов ВС и совместно решающих распределенную между абонентами^системы задачу арбитража. Каждый из модулей содержит следующие основные блоки: статического кода (ECK), динамического кода (БДК), передачи полномочий (БПП), задания длительности информационного взаимодействия с ресурсом (ЕЗДИВ). БПП служит для реализации метода ДКУ - поразрядного сравнения кодов приоритетов в канале, получаемых от ЕДК, при активизации абонента и разрешения Доступа к каналу абонента, если он оказывается приоритетным, обнаружения занятия ресурса для информационного взаимодействия одним ив абонентов ВС - вырабатывает управляющий сигнал изменения кода приоритета (ИКП),поступающий во все блоки. БСК служит для хранений и изменения (например, при комбинирований) статичеС|«эго кода ОП, соответствующего начальному моменту времени функционирования ВС, для выдачи кода в этот момент ВДК. БДК принимает код ОП от БСК в исходные моменты времени и ватем при каждом занятии ресурса - по сигналу ИКП, изменяет его (РМВ, либо не изменяет - СП) в соответствии с заранее заданным расписанием. ЕЗДИВ реализует те же функции, что БСК и БДК, но по параметру ТГр . Задается исходный код длительности информационного взаимодействия абонента с. ресурсом, посту- . пающий абоненту вместе с сигналом разрешения ему доступа к ресурсу и регламентирующий продолжительность занятия. Кед длитесь-

-

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

В пятой, главе разрабатываются и исследуются методы ДКУ ¡МВ, или принципы построения важнейшего уз.га УДУМД - Б1Ш. для различных приложений- исследуемых ВС РМВ, с учетом .разработанных ранее методов оптимального кодирования ОП абонентов ВС. В общем случае . метод ДКУ. предполагает поразрядное (начиная со старшего разряда)-сравнение кодов ОП при управлении доступом к ресурсу, при котором в бит-синхронном, либо ином режиме канал занимается передачей зонда абонентами, имеющими в анализируемом разряде кода более приоритетное значение "1". Поступление из канала зонда абоненту, имеющему в анализируемом разряде менее приоритетное значение"0", .' исключает его из "борьбы за канал".

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

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

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

сипкиюм одновременно всем абонентам ВС (нет необходимости в передаче кода, например маркера)..

Как для информационных, так и для зондовых методов могут быть эффективны как'равномерный, так и неравномерный коды ОП, при использовании придельно неравномерного по."О" кода в обоих случаях имеем бесконфликтную передачу полномочий. Разработана концепция комбинирования методов, реализуемого с целью элективного управления множественным доступом на всем интервале изменения- параметра Р : 0 ' 1 , основанного на использовании во всех случаях единого механизма доступа и реализации комбинирования подходов исключительно за счет смены исходных статических кодов 01! (комбинирование на'"уровне кодов 0Г1).

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

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

I ППЛ1 (Р. Рт) - (1- (1-р)М)^т-1РтНтТппу. информационного ДКУ ' ТиППт(Р.Рп,) С(Рпт(Р.Рт)-Рт-1 (р.Рт)) (Пп)Тпп./+(пт-Шк) 1.

при передаче полномочий конфликтом ресурса

ТИКппт(Р,Рт) -^тт=11(Рпт(Р,Рт)-Рпт-1(Р-.Рт))(Г1„г:1)Тк], соответственно,для способа поочередной передачи полномочий (например, маркерного) ]

Тпппт(Р^Рт) -1?',1-11С1мР1(1-Р)М"1---1?И/1а=1аТлпт-1. п,1,

М

где Тппу - продолжительность передачи прав по одному разряду ко-• да ОП, Тк - затраты времени на обнаружение конфликта, ТПпт-1. м -затраты времени на поочередную передачу прав между очередными абонентами в расписании. Частным случаем р -1 задаются детерминированные модели ДКУ, используемая для оценки эффективности ис-. пользования методов в РМВ, для вондового метода Тэппт(Р~1) " £^т=1РпЛпТппу» для информационного с передачей прав конфликтом

Тикппт(Р-1) -^1Рт(пт-1)Т„.

Для равномерного, кода ОП соответственно получаем

Т3ппт(Р~1) ~ МТппу. ТикПпт(р-1) ~(№-1)Т|{.

В результате проведенного исследования эффективности альтернативных методов ДКУ сделаны выводы, что при условии Тс * Ти (достаточно широкий класс УВС, что обусловливается ограничениями на физическую скорость передачи данных по каналу связи) наиболее эффективны зондовые методы (полное кодирование), при хс - Тц эффективными могут быть как зондовые, так и информационные, причем синхронные и асинхронные, но при тс > ти эффективными уже становятся асинхронные информационные конфликтнее методы (синхронные как зондовые, так и информационные здесь могут быть эффективны только при групповом кодировании ОП). Это вызвано тем,' что, как показали проведенные исследования, асинхронный и синхронный способы передачи прав имеют равную эффективность при тс - Тц , при тс < % эффективнее синхронная передача полномочий, при тс > т1Г - асинхронная. При р -» 1 эффективны бесконфликтные способы, реализуемые в ДКУ использованием предельно неравномерных по "О" кодов ОП.

При проектировании УДУМД сделанные выводы должны учитываться следующим образом. Так для приложений ВС, задаваемых условием тс < ти синтезируется только полный код ОП; реализуется зондовый метод ДКУ. В противном случае, исследуются и способы полного, и способы поэтапного кодирования,. при тс > тн поэтапное кодирова-. ние, для полного исследуются групповые коды ОП. Здесь уже могут быть эффективны и зондовые, и информационные методы ДКУ, поэтому выбор метода" осуществляется следующим. образом - синтезируется

га -

полный кол и поэтапный, для поэтапного выбирается оптимальный способ передачи полномочий, сравнивается эффективность зондового и оптимального информационного способов. Искомый параметр Тгппт. определяемый для оптимального метода ДКУ с учетом заданных Р.Рт учитывается при синтезе ДО РМЬ при определении параметра ТГрт .

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

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

В достой главе разрабатываются функциональные схемы блоков Б1Ш,СОК,БДК канонической структуры УДУМД с учетом особенностей разработанных методов ДКУ РМВ. В частности, разработаны унифицированные структуры БШ], ■ реализующие альтернативные методы ДКУ -зондовые и информационные с учетом многообразия их модификаций.В рамках разработки схем БСК исследованы проблемы реализации альтернативных способов изменения исходных статических кодов 0П -адаптивно к изменению загрузки канала (к изменению параметра р ) и адаптивно к изменению характеристики эффективности обслуживания заявок (к изменению параметра Тот .при этом может быть учтен ОП абонента). При разработке схем БДК исследована важнейшая проблема (которая в первую очередь должна быть решена для любого метода ОР) включения абонента в уже функционирующую ВС, состоящая в том, что в'различные моменты времени ОП абонента различен и должен быть однозначно определен при его включении. Предложены три'стратегии включения абонента, для которых разработаны функциональные схемы БДК:включение с максимальным ОП,- бесприоритетное и комбинированное включение. Первый подход, разработанный для зондовых методов ДКУ, состоит в резервировании кода максимального ОП системы для включаемого абонента. Включаемый абонент (абоненты) имеет ОП, получив доступ к каналу передачей специального управляющего кадра включаемый абонент возвращает ВО ь ис-

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

. Предложенные Принципы построения устройств и методы их проектирования рассмотрены в рамках предложенного системного подхода к построению и проектированию ДУМД для исследуемых приложений ВС.

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

ЗАКЛЮЧЕНИЕ .

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

К основным научным результатам диссертационной работы относится следующее. ■-■'"■

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

2. В рамках разработки системного подхода к построению УДУМД для ВС исследуемых приложений предложены и исследованы следующие взаимосвязанные принципы построения систем управления

-множественным'доступом:''.Л'

- принципы построения ДОР РМВ и ДОСП (ОР и ОП), состоящие в

со -

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

Другим важным результатом, полученным В "главе, является разработка общего подхода (методологии) проектирования УДУМД для ВС РМВ, в основе которого лежат разработанные ранее методы, состоящего в задании очередности их применения для различных приложений ВС. Обобщенный подход состоит в следующем. В первую очередь, для любого метода ДКУ строится код ОП (соответственно, оптимальный -.с учетом параметров р и/или Рш , групповое кодирование при тс » гн, либо приоритетный) в соответствии с разработанной методологией кодирования ОП. Затем, с использованием предложенного подхода к анализу эффективности методбв ДКУ на разработанных вероятностных, моделях с учетом параметров М,тс,ти выбирается оптимальный метод ДКУ РМВ, для которого уже определяются значения параметра ТГппш . В.последнюю очередь, с учетом выбранного метода ДКУ РМВ и заданных М,Тгппш . с учетом заданных ограничений Тгрст (либо Р(Трст<ТГрст)). соответственно заданных параметров алгоритма функционирования 1ЮЕС ТГряя. 1-гм (Для ЛВС задается лишь Тгот .соответственно Р(Тот<ТГсп|)) . ДЛЯ построенного кода ОП (оптимального, либо приоритетного, с использованием раз- ', работанной методики синтеаируется ДОР (ЯРСй) РШ, -Т.е. задается расписание смены ОП, и задается необходимая производительность связного ресурса. Для ВС с жесткими ограничениями на качество обслуживания заявок на последнем этапе проектирования может быть'

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

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

- принципы ДКУ РМВ, реализующие предложенные принципы построения ДОР (ДОСП) РМВ, за счет отображения матрицы 011 в матрицу кодов ОП,'соответственно'-графа смены матриц ОП в граф смены матриц кодов ОП, и обеспечивающие оптимальность ЗРТ-расписаний передачи прав на доступ к ресурсу в ВС;

- принципы оптимального кодирования ОП абонентов ВС, обеспечивающие повышение эффективности передачи полномочий на доступ к ресурсу в ВС в рамках оптимального ЗРТ-расписания. реализуемого предложенными принципами ДКУ РМВ, учитывающие приоритет логической единицу в кодовом слове ОП; -,'.•'

- принципы оптимального динамического кодирования ОП абонентов ВС, реализующие расписания РМВ принципами ДКУ, в рамках которых обеспечивающие оптимальность статических кодов ОП абонентов в каждый момент времени функционирования ВС;

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

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

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

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

ношению числа заявок-И»© к числу низко приоритетных-заявок ОП, где требования к производительности ресурса уже и при ОЦП могут снижаться в единицы и десятки раз;

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

4. В рамках разработки системного подхода к проектированию УДУЬ'Д определены критерии оптимальности решений , разработаны

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

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

- методы проектирования ДОСП (РМВ и ОП) при альтернативных способах задания ОП абонентов ВС на детерминированных и стохастических ' моделях;

- методы построения оптимальных статических кодов ОП абонентов во ( полное и поэтапное кодирование) в рамках оптимальных ЗРТ-расписаний передачи прав, реализуемых методами ДКУ РМВ; .

- методы построения оптимальных динамических кодов ОП або-' нентов ВС в рамках заданных расписаний РМВ и статических кодов ОП абонентов;

- методы выбора оптимальных способов ДКУ РМВ из разработанного унифицированного ряда с использованием разработанных вероятностных и детерминированных моделей систем управления множественным доступом.

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

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

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

дор рмв и досп рмв.

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

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

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

1. Щеглов А.Ю. Ускоренное зондирование канала данный - новый принцип случайного доступа в локальных вычислительных сетях// Изв. РАН.Техническая кибернетика. - 1994. - N2.

С.129-136..

2. Богатырев В.А., Щеглов А.Ю. Метод динамического разделения канала в пространстве - новый способ множественного доступа // Изв.АНСССР.Техническая кибернетика. - 1990. - N3.

С. 184-192.

3. Щеглов А.Ю. Высокопроизводительный метод децентрализованного кодового управления- для неоднородной микропроцессорной системы// Кибернетика и системный анализ. - 1994. - N2. -С.176-180.

4. Щеглов А.Ю.1 Алгоритм динамического изменения приоритетов для высокопроизводительного метода ДКУ реального времени//. Кибернетика и системный анализ. -.1994. - N5. - 'С. 179-181.

5. Щеглов А.Ю. Счетно-интервальный способ множественного . доступа для ЛВС реального времени// Автоматика и вычислительная

техника. - 1991. - N5. - С.74-77.

G. r..i[ ;-'ЛЫ|>--в В. Д., Щеглов А.Ю. Интервальный множественный дост/н к динамически сегментируемому каналу// Автоматика и вычислительна! техника.- 1990. -'N3. - С.46-62.

V. Богатырев' В. А., Щеглов А.Ю. Метод эстафетного доступа о контролем несущей для локальной вычислительной сети// Автоматика и вычислительная техника. - 1989. - N5. - С.85.

8. щеглов а.ю. Высокопроизводительные счетные методы доступа для локальной вычислительной сети реального времени// Электронное моделирование. - 1992. - 14,N2.- С.104-107.

9. Щеглов А.ю. Способы реализации работоспособного синхронного множественного доступа// Электронное моделирование. - 1994. '- 16, N3. - С. 32-38.

10. Щеглов А.Ю. Интервальный метод доступа с абсолютной синхронизацией абонентов системы// Электронное моделирование.-1993. - 15,Mb. - С.93-94.

11. Щеглов А.Ю. Ускоренный метод децентрализованного кодового управления доступом к моноканалу в реальном времени// Электронное моделирование. - 1993. - 15,N3. - С.88-92.

12. Щеглсв А.Ю. Высокопроизводительный интервальный метод множественного доступа с естественной синхронизацией абонентов системы// Электронное моделирование. - 1993. - 15,N2. - С.93-95.

13. Щеглов А.Ю. Синхронный метод доступа для сегментированного кольца// Электоонное моделирование. - 1993. - 15,N1. -С.85-87.

14. Щеглов А.Ю. Способ случайного занятия канала с обнаружением несущей реального времени// Электронное моделирование. -1993. - 15,N6. - С.90-91. '

15. Щеглов А.Ю. Метод децентрализованного пространственно-временного управления кольцевым однонаправленным информационным каналом// Электронное моделирование. - 1394. - 16,N2. .-С.86-88.

16. Щеглов А.Ю., Плешкова H.A. Метод синхронного доступа// Электронное моделирование. - 1992. - 14,N4. - С.88-90.

17. Щеглов А.Ю., Куконин А.Ю. Метод децентрализованного кодового управления доступом к каналу с передачей полномочий// Электронное моделирование. - 1991. - 13,Мб. - 0.32-34.

18. Богатырев В.А., Щеглов А.Ю. Полиэстафетный метод доступа к магистрали для локальной вычислительной сети// Электронное моделирование. - 1989. - 11,N3. - С.97-99.

19. Богатырев Б. А., Щеглов А.Ю. Высокоскоростные а:шЛи

-

детерминированного множественного доступа к-динамически сегментируемому каналу кольцевой топологии// Электронное моделирование. - 1991,- 13,N1. - С.17-20.

20.- Щеглов А.Ю. Принцип различия длины кода приоритета для реализации метода • децентрализованного кодового управления локальной вычислительной сетью реального времени/'/Электронное моделирование. - 1995. - 17,N1 - С.70-73.

21. Щеглов А.Ю. Производительный децентрализованный арбитр для локальной'вычислительной сети// Управляющие системы и машины. - 1991. - N5. - С.85-88.

22. Куконин А.Ю., Щеглов А.Ю. Методы децентрализованного управления доступом к каналу малых локальных вычислительных сетей// Управляющие системы и машины. - 1992. - N7/8. - С.124- 127.

23. Богатырев В.А., Щеглов А.Ю. Полиэстафетный метод для управляющей локальной вычислительной сети с кольцевой структурой // Управляющие системы и машины. - 1989. - N6. - с.54-57.

24. Богатырев В.А., Щеглов А.Ю. Полизстафетный-метод доступа с проверкой несущей для локальной вычислительной ^сети'. с магистральной структурой// Механизация и автоматизация управления.- 1990. - N2. -.с!48-50.

25. Богатырев В.А., Щеглов А.Ю. Интервально-маркерный множественный доступ для управляющей локальной вычислительной сети// Механизация и автоматизация управления. - 1991. - N2. -С.44 - 46.

. 25. Богатырев В.А., Щеглов А.Ю. Метод структурной адаптации многомашинной вычислительной системы к потоку требований моноканала при приоритетном полиэстафетном множественном доступе// Техника средств связи. Сер.ЗУ. - 1990.- Вып.З. - С.14-17.

27. Богатырев В.А., Щеглов А.Ю. Метод структурной адаптации многомашинной вычислительной системы к потоку требований моноканала, замкнутого в петлю // Техника'средств связи. Сер.ЗУ. -1990.- Вып.1. - С.30 - 34. •

28. Щеглов А.Ю. Приоритетные счетные методы доступа для локальных вычислительных сетей// Системы и средства телекоммуникаций. - 1992. - N5/6. - С.40-42.

29'. Щеглов А.Ю. Метод динамической сегментации волоконно-оптической линии связи локальной вычислительной сети// Средства свя-ви. - 1992. - ВЫП.4. - С.26-29. .

30. Щеглов А.Ю., Богатырев В. А. К вопросу о построении децентрализованных арбитров с циклической структурой// Системы уп-

равлеиин производственными процессами. Межвузовский сборник научных трудов.- Новочеркасск: ПШ, 1989. - С. 95-103.

31. Щеглов ■ А.Ю. Элементы теории управления множественным доступом пользователей к общим ресурсам вычислительной системы// Вторая Международная конференция "Развитие и применение открытых систем". Тезисы докладов. - м.:Совет РАН по автоматизации научных исследований, 1905. - С.74-76.

Куконин А.Ю., Щеглов А.Ю. Метод доступа к общей магистрали Л1..С децентрализованного управления объектами реального времени// Материалы 46-й научн.-техн.конф., 'посвящ. Дню радио. Л.: .ЩШТП, 1991. - С. 51-52.

33. Кутузов В.Е., Щеглов А.Ю. Счетные методы множественного доступа для ЛВС реального ьримени. // Там же. - С.56-57.

34. Щеглов А.Ю. Элементы теории управления множественным доступом пользователей к общим ресурсам ■ вычислительной системы// Вторая межведомственная научн.техн.конф. "Проблемные вопросы сбора, обработки и передачи информации в сложных радиотехни-'• ческих систем;«".Тезисы докладов. - г.Пушкин, '1995. - С.£00.

35. Щеглов А.Ю. Ускоренный метод децентрализованного кодового управления // Материалы 47- й научн.техн. конф., поев. Дню радио. - Л.:ДДНТП,1992. - С.58-59.

36. Щеглов А.Ю. Построение работоспособного децентррали&о-ванного арбитра для ,нравляющей локальной вычислительной сети// Повышение эффективности производства и качества продукции (услуг) связи на Сазе электронизации оборудования предприятий связи. Тезисы докладов Всесоквн.научн.техн.совещания. - М.-Воронеж: ЦП НТО им.Л.С.Попова,1988. - С.57-58.

37. Щеглов А.Ю., Богатырев В.А. Интерьально-маркерный Щ к динамически сегментируемой магистрали// ХУ Всесоюзная шкода-семинар по ВС. Тезисы докладов. - М.-Ленинград:ИСК АНСССР,1990. -Т.1. - С.271-275.

38. Щеглов А;Ю., Богатырев В.А., Иванов Л.С. Архитектуры локальной информационно-вычислительной сети с адаптируемой к потоку требований структурой///.IУ Всесоюзная школа- семинар по ВС, Тезисы докладов. - М.-Минск:НСК АНСССР,198Г<. - Г.1. - С.282-287.

.39. Щеглов А.Ю., Богатырев В.А. Полиэстафегньй метод доступа к моноканалу для локальной вычислительной сети// Проблемы . создания и использования отраслевых информационно-диспотческих систем . на основе компьютеризации и перспективных средств связи. Тезисы докладов Всесоюзн.научн.техн.конф. М.-Калуга:Радио и

СВЯЗЬ,1903. - С.104-105.

-30. Патент РФ'N2020560.- Устройство для подключения источника информации к общей магистрали/ В.Е.Кутузов,•А.Ю.Щеглов// Открытия,- изобретения,1994. - Был.N13.

41. Патент га N2020061. Устройство для подключения источника информации к общей магистрали/ В.Е.Кутузов, А.Ю.Шеглов// Открытия, изобретения,1934. - Еюл.N18.

42. Патент РФ N2023234. Устройство для подключения абонентов к общей магистрали/ 'А.Ю.Куконин, Л.Ю.Щеглов// Открытия, изобретения, 1994. - Вил.М21.

43. Патент Р8 №0£3г03. многокан&чьное устройство для подключения патентов к общей магистрали/ А.Ю.Щеглов// Открытия, изобретения,1994. - Кол.N21.

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

11оддясз&о к печати I0.CjG.9B г. . (¡бт-ем 2,2 и.л.

Зпняз Г»8 Тиряя КО ркз. бесплатно.

ЗРотанрпнт. ИТМО. 190000, Санкт-Петербург, -пер.Гримгот,- .14