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

На ггр-тмх рукоппсп

РГ6 од

КОВАЛЕНКО Алексей Алексеевич

РАЗРАБОТКА МЕТОДОВ И СРЕДСТВ СПЕЦИФИКАЦИИ ВЗАИМОДЕЙСТВИЯ РАСПРЕДЕЛЕННЫХ СИСТЕМ НА ОСНОВЕ КОМПОЗИЦИОКАЛЬНЫХ СЕТЕЙ ПЕТРИ

03.13.11 - Математическое и программное обеспечение екгшслтггслвных мпдпга, комплексов, систем а сетей

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

Владивосток 1990

Работа выполнена в Институте автоматики и процессов управления Дальневосточного отделения Российской Академии Наук.

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

Анпсимов Н.А.

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

профессор .Клещёв А.С.

Защита состоится "12" шоля 1956 года в 10 часов на заседании диссертационного совета Д 003.30.01 в Институте автоматики р процессов .управления Дальневосточного отделения РАН по адресу:

690041, г. Владивосток, ул. Радио, 5

С диссертацией можно рзпакомится в о'пблиотеке Института автоматики е процессов управления Дальневосточного отделения РАН.

Автореферат разослан "--^~."пюня 1996 г.

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

кандидат технических наук, Денисов С.Б.

Ведущее предприятие: Институт систем информатики

имени А.П.Ершова

СО РАН (г. Новосибирск)

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

Актуальность проблемы. Информационный прогресс современного индустриального общества осгговттаается. на использовании параллельных л распределенных вычислительных систем, решающих задачи- передала п обработка значительных объемов информации, управления сложными техпологическимп объектами, оказания экспертной поддержки для принятие ответстпетшых решений п различных областях лародпо-хозягствянЕой деятельпости. Развитое способов п средств передачи дал-гпхх различного типа явилось основой для революционных изменений л технологиях обработки информации, делая гас сушоствешхо распредеяеп-шага йа уроппе п физической, к логической структуры. Доступность п эффективность использования сетеыдх технологий, п том числе и благодаря г.семттриот? с»т Тг»*«гае<;, прнзела к существенному распгорсшпо рынка прнложепвй распределенных.систем. Следствием того, что производство такнх систем приобрело индустриальный масштабы, является возникновение массовой потребности п мзтодах п инструментальных средствах, позволяющих адекватный образом огагшзать поведение рас-пределгшшх спсте« реальных размеров.

Трудность оппсашМ'рсслрсягпсЕПЫХ г.кчислптельпых систем лежит в пе.'декватпостп позедопзя таких систем липеЙЕЛ!}' характеру мыш-лс1Ш,ч разработчика. Стапдартшге подходы х спецификации поведения обмчных систем, как правило сснояашше только па здравом смысле и тщательности разработки спе51ифшсацпй, и случае раеттределе шых систем могут пт>1тог.сти к стсрктнч дефекта.»!, прогпяепве которых в отвзт-стаезнкх прт;саишшх чрелато серьезными последствиями. Это связано с наличием качественно новых типов логических некорректностей, таких как тупиковые состояния, непроизводительные циклы, переполнения л др. Полохсенпо ухудшается сщз и тем, что ошибки такого рода трудно обпаружпмы на традиционных этапах тестарочанпс л отладки.

Решетке данной проблемы идет по путл разработки п развитая формальных моделей и методоз для описания поведения параллельных процессов п их взаимодействия, с помощью которых желаемые свойства логической корректности можно гарантировать еще на ранних этапах логического проектирования системы. Значительная работа в этом направлении как зарубежных исследователей Р.Милнера, К.Петри, Ч.Хоара, так и отечественных ученых О.Л.Бандмап, В.И.Варшавского, Ю.Г.Карпова,' В.Е.Котова, В.Г.Лазарева, Е.И.Пийпь, С Л..Юд:щкого послужила созданию прочного теоретического фундамента с целью дальнейшего развития формальных моделей и инструментальных средств для описания взаимо-

действпя распределгнных систем.

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

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

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

1 В рамках научно-исследовательских тем Института автоматики и процессов управления ДВО РАН: е "Иссйедозаиис и разработка методов анализа и синтеза про ¿околов сетей ЭВМ", N гос. регистрации 01.9.10016315. в "Формальные методы п средства разработки программного обес-" печекия распределенных вычислительных систем", N гос. регистрации 01.9.50006312,

2. В рамках конкурсного научно-исследова,тельского проекта отделения информатики, вычислительной техники и автоматизации АН "Си° стема автоматизированной разработки протоколов сетей ЭВМ".

3. В рамках проектов Российского фонда фундаментальных исследований:

• "Основы композициональной теории сетей Петри", грант 93013-17372.

* "Композициональные методы разработки сетевых протоколов", грант 96-01-00177.

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

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

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

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

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

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

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

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

о Разработаны методы асинхронной композиции сетей Петрп по локальным состояниям (местам сетей Петри) :

— введено понятие макроместа сетп Петрп и па его основе определена операция стщэоппЗаппи; •

— исследована синхронизация сетей Петри по локальным состояниям на оскозе иаркпрезок;

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

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

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

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

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

Реализация результатов работь.. Предложенные методы и инструментальные средства использовались в процессе создания среды визуального программирования миссии надводного неуправляемого аппарата, которая в настоящее время эксплуатируется в Институте проблем морских технологий ДВО РАН.

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

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

Апробация работы. Основные научные и практические результаты работы дохлаДЫБалссь и обсуждались па следующих международных и отечественных конференциях п семинарах:

• Международных конференциях: Международная конференция "Технология программирования 90-х" (Киев, 1991); Международная конференция "Приложения и теория сетей Петры" (Шеффилд, Англия, 19?2); Международный симпозиум "Новейшие технологии и автоматизация производства (ЕТЕА'94)" (Токио, Япония, 1994); Международный симпозиум "Моделирование, анализ "и симуляция компьютерных и телекоммуникационных систей (МА8СОТ8-95)" (Дарем, США, 1995); Медздународтшй симпозиум "Параллельные алгоритмы/Архитектурный синтез"' (Айзу, Япония, 1995); Международный симпозиум "Спецификация, тестирование и верификация протоколов (Р8ТУ-95)" (Варшава, Польша, 1995); Международная конференция "Математическое моделирование в криптография (РММС-95)" (Владивосток, Россия, 1995); Международная конференция "Новейшие технологии и приложения в коммуникациях (е1аСОЛ-95)и(Иортленд, Орегон, США, 1996); о Всесоюзных конференциях; ыколах и семинарах: Всесоюзная школа-семинар по вычислительным сетям (Алма - Ата, 1992); Всесоюзная

конференция "Технология программирования" (Киев, 1990); Дальневосточная математическая школа (Находха, 1994); V совещание по распределенным вычислительным системам п сетям (ЗБЗ-92), (Калининград, 1992);

• Семинарах Института автоматики я процессов управления ДВО РАН в 1990 -1903 гг.

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

Структура п объем работы. Диссертант: состоит из введения, четырех глав, заключения, сцнсха литературы л приложений. Основное содержание составляет 121 страницу, в том числе.32 иллюстрации. Список литературы включает 101 напкеиовангга.

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

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

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

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

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

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

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

в развйьцЛ формальным аппаратом, позволяющим специфицировать поведение распределенных систем с различной степенью детализации;

-7© богатым набором матештачесгсг: методов, алгоритмов и-автоматизированных средств анализа на свойства лоппсской корректности;

« попятным и наглядным графическим представлением,- существенно

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

Большим преимуществот.1 сетей Петри гвляется существование множества различных расширений, что позволяет адаптироваться под конкретную прикладную область. Вместе с тем, необходимо отметить, что па базовом уроппе в сетях Петри отсутствуют средства кегшозпшгонал!.-иостк з модульности. Работы по распигреким сетей Петря в этом направлении в поскяднее время проводились в рпмках международных проектов DEMON л Caliban. В института' аатоматпкп и процессов управлэ-mu г.Впадшюстск получили дальнейшее развитие идеи алгебраического нреяставления сетей,, заложенные В.Е.Котовом.

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

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

Формально, сетью, заданной на мпо:хестве К, называется набор N — (S,T), где S --- {si, л-;,5П} - множество мест (S П К — 0); Т С Р(5) х К х V(S) + множество переходов; с : Т —♦ К - пометочяая функция. 'P(S) означает мультимножество мест. Форма представления сетей Петри немного отличается от общепринятых, но при этом значительно упрощает дальнейшие определения сипхрошпацни ео точкам доступа.

Есле t = (Qi,a,Qj) € T To "t — Qi, t' = Q2, a(t) = а. Множества '¡ и i" называются входными выходным для t. Соответственно, cr(t) называется именем перехода.

Динамика поведения моделируемой системы находит свое отражение в функционировании сета Петра, для чего определяется функция маркировки мест М: S —» jVö- Чтобы переход мог сработать необходимо, чтобы выполнялось условие его возбужденности: Ч < М. Графически сети изображаются з вн^е графа, в котором места представлены кружочками, а переходы - прямоугольниками. Места и переходы соединяются ориентированными дугами.

Вводится понятие точек доступа через переходы, формализующие информацию о том - каким образом и какие пмешо переходы необходимо синхронизировать при параллельной композиции сетей. Для сети N = {S,T) точкой доступа через переходы (ТДП) называется а — (Alph, с), где Alph - множество кадимых пометок; а : Т —> Alph U {г} - цодгеточ-ная функция, r {s Alph - вевндамый символ. Согласно данному определению ТДП определяет видимость во внешнем скрузкеаш: срабатывание определенного множества переходов. Для компактного ерэдзтазле-пи" сетей с ТДП определяется сетевой объект - Е (N,Г}, гдз: N -сеть; Г — {71,...,7т} - множество имеповаккых ТДП, где Ыыздая ТДП ji = (idi,Alphi,iri) кмеет идентификатор idi, Дж устранения неоднозначности в композиции сетевых объектов определяется портальная форма сетевого объекта, в которой все его ТДП имеют, различные имена: V7i,72 ■£ Г: 7i •fi.ft''* г Cootbctctdöseo, опредэляетс/а процедура нормализации сетевого объекта с ТДП.

Дпя_ дальнейшего использования сетевого объекта определяется операция композиции над сетевыми объектами через ТДП. Операция композиции определяется как объединение сетевых объектов и выполпецие спнхронизащш через определенные ТДП сетевого объекта. В результате спнхронизацш сети N через ТДП Oj и «2 получится новая сеть N' = T,ynck{N,ah а3), где S' ~S\T — Т \ Та.л U Т^, причем TaU = {г 6 Т | ai(t) £ т V (г2(<) ф т} и Г„уп = {it Uf2 I «ь«а € Г, <n(ii) в аа(*а). ^ г} (fi U Ц .= (*<i U* ij, ff(ii) U <т(<г)» t\ U Ц)). Операция синхропшации через ТДП создает новое множество переходов синхронизации Твуп и удаляет переходы, которые видны в ТДП а\ или о^Мкожество переходов синхронизации Г,„„ формируется путем перемЕозкеннь пар видимых переходов с одинаковыми именами в aj ii щ соответственно.

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

рсоиределеяпя (трянсфор;лации) существующих ТДП: а — {Alpk„,an)• . На основе бинарной операции синхронизации

Nlai®a,N2 & TtVnCh{Ni\J N7,aua2)

определяется композиция сетевых объектов

(El е04 Ег) - norm((N\ а®ц ЛГ2),П,Г>,

где П = {* 15г б П, U Пг}, Г = {7 | 7 6 (Pi \ ъ) U (Г2 \ 72)}.

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

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

Первый подход - еппхревшрппя через "-очки доступа па о ионе макропест рассмотрел более тщательно а-несколько шнре второго , что позволяет о'брспечпть плавное впадение-в'непггпЗпуго область' комтшэдш сегеЗ через места. Для начала на остозе владеняого понятия примитивной пометки мест определяете" операция синхронизации, для которой доказывается свойство коммутативности. Затем понятие пометка мест усложняется до простой номяткп п операция сипхрошпащш через нее. В конечном итога вводится понятие точек доступа через макроместа - ТДМ„, которая представляется з сети N — (S,T) множеством р С P(S), если верпы следующие условия: (1) VPb Рг £ р : Рх П Р2 = 0; (2) VP € р : sj, «2 € Р => *sj П "S2 — з* П sj> = 0. ТДМа представляет собой множество взаимно непересекающихся подмножеств мест (пункт 1), причем каждое такое подмножество называется макроместом. Два места одного u гого же макроместа не могут иметь общих входных п выходных переходов (пункт 2)-

Для непересекающихся ТДМ„ р\ and pi ( |!/5i||n||p2|| = 0) определяется операции синхронизации:

■ .Vsy {Рь/),} Л! (лГву тг)

-to-

где: (1) N" = <S",T");

(2)S" = S \ S12 U UPi x д, U Uft£pa fli x pj;

(3)Г = Г \Г12 О | í.e Г12}, где

<7(<) = *í\ s12 и ил€ЛС< ПPi)х/)2 и U W* пР2)хя

Q"(í) = Г \ S12 U Ufl6/,((í'nPi)x/;¡ U U^tfnPjJx/),

,(4)7Г - псметочнал функция, определенной па алфавите Д — pixp%: Í т, сели s e S \ S12;

= j (fí.ft), если 8 Ж (sbPj) е Рх ХР2, Р! е /51-, • . 1гели 8 = (52, Pi) е Р2хри Р: 6

Данная операция синхронизации реализует процесс синхронизации через макроместа двух сетей. Это соответствует тому факту, что если каждое макроместо одной ТДМ0 имеет хотя бы одно внутреннее место, содержащее метку, то это приводит к тему, что помещается но одной метки в каждое макроместо другой ТДМа. Показывается коммутатшшость операции синхронизации через ТДМа. Tas как внутренняя структура сети измгпяэтея, определяется операция трансформации ТДМадля р при выполнении (N ву {рирг})'

P = p\(pnpí)U{Plx№)xP2x{Fi} lPi £рПриР2 ер2}.

Вводится ойредекеше попарпъ сравнимых точек доступа, при мг'хро-.ншацпа через которые выполняется свойство ассоциативности. Стандартным способом вводится бинарная операция синхронизации через ТДМ„ '

N - (Nx N2) ^ (iVi U Щ) су {РъР%}.

Кс:.:аоз;щи;. сетей па сглгонашш информация о маршфовтга сети является альтернативным подходом по отношения) к композшцш через макроместа. Понятно точки доступа в данном подходе основывается на обобщении донятая г 'аркирськп сети. Точкой доступа через маркировки (ТДМ,) з сети N — (S,T) называется множество р = {МцМз, ...,Мт) безопасных маркировок m¡ £ V(S), 1 < t < ги таких, что VM,-,JWj 6 р : M¡ С Mj => M¡ — Mj. Из опредзлгния следует, что точка доступа через маркировки (в дальнейшем 6}'дст обозначаться как ТДМ.) представляется множеством безопасных кархаровох; вэапмпо-отличпых по отяорвенгоо к включению. Состояние езтп, п котором достигается' одна из маркировок М 6 р, Tp;¿i.i vcTca 2агс шщшое событие в ТДМ,.

Определяется операция сиыхрипизации через ТДМ, Р\ и p-¿, в результате которой получается сеть /V = Sivnch(N,Pi,P2), где:

(l)S' = 5 \ SiZ U S'xS2;

(2)7" = ЦЯиа(*)>Я2) I < е Г,М\ й риМ2 <Е л},где ¿?1 =' г \ 512 и ил, 6йС<ПЛГ)хЛ/а и 0У1 - \ 512 и иЯ'ел(<' П М') хМ2 и им»ей М х (Г Л М").

Трапсформация для ТДМ. р после выполпеппя Л" = Зп.пгм(М,гп,Р2) будет реализовываться в виде:

р = {М\о12 и (Д/Г.51)хМ2 и М1х(Л-/П52) | М е />, АЛ 6 /51, ЛГ2 £ />;}•

Доказывается свойство ассоциативности для бпнарсой операции синхронизации через ТДМ,.

Операции еппхропизациа мест через макроместа (ТДМ„) и маркировки (ТДМ,) могут служит в качестве базисных операций для построения наборов различны:! алгебраических операций. В результате такого полхода спасание исчисления, построениого на оспсге таких достаточно громоздко'определяемых операций, мохсет быть элегантным л не слойккм, что будет показано в дальнейшем.

Для спепнфнкация распределенных систем большой размерности следует попользовать модульный подход, что может быть достигнуто .за счет обобщенна лопатил сетевых объектов и пххомпозпцвп. Сетевой объект Переопределяете! до вида Е — (ДГ, П,Г), где П а Г представляют мпожество ТДМ и ТДП. Соответственно, изменяются определения нормального сетевого' объекта и процедуры зопмалтпатго, доопределяете." операция есмпозицип сетевых объектов.

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

В заключения данной' гловтл алгебраические опергцш: над сетями Егредставлзгстсг через комнезпттахз сотегых объектов, для чего гводат-• ся специальная форма сетевого обгггха Ер — (ЛГ,П,Г), я которой П = {!>,Ч,(1} представляет гойавпух», хвостовую п внутреннюю .ТДМ; Г ~ {7( ,?..,7,.} _ множество ТДП. Существует два способа получения сетевого объехта в таком представлении: л.~бо трансформация л уточнение существующего сетевого объекта, либо прпмспелле ужа готового сетевого объекта в форме Е?. Одппм из таких готогих объектов является атомарный объе.-хп, а котором сеть состоит чз одного перехода с одним входным п одним зкходатам мсстой. Пусть задали сетггче объекты Е\ — (Дг,, {.'.,,/,,¿0,Г-) л — тогда алге'Зргхчсскпе

операции пт>едстааляготся следующим образом:

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

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

(Е1 »Е2)--=погт{{Н1 ^),{к1,11,а1и^2},Г1иГ1).

о альтернативная композиция представляет описание недетерминированного выбора в конкретном месте состояния системы:

(ДО^О = погт((Лг1 Агг), {¿1 иАа,/, и !ьёх и ¿2}, Г5 иГ2).

• параллельная композиции! служит для спецификации синхронизации между сетевыми соъектаьш но определенным событиям, которые представлены с помощью ТДП:

(Ег а\У Е2) - погт{(Н\ „0, А'2), {/1, сГ}, {Г, иГ2\ {«,/?}}),

где Л = /¡1 © /12, I — ¡1® ¡2, в, = 0 Л2.

а итерацил описывает многократное повторение выполнения одного сетевого объекта:

«а разрушение позволяет специфицировать такие события, как прерывание выполнения одного сетевого объекта другим:

(Е1 о £2) = погт{(М{ А@кг N2), {ки!2,<?, и ¿2),Г1 иГ2).

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

В качестве платформы для реализации Была выбрала Мкгезой У/шс1оу/8, обладающая унифицированным многооконным графическим интерфейсом длй взаимодействия с пользователей. Общая архитектура системы изображена на рисунке 1 н состоит из редакторов трех типов (базовый, алгебраический н архитектурный), подсистем вернфакадии и анимации спецификаций. Такая структура АСРС обеспечивает возможность использования разработчиком спецификаций трех различных уровней абстракции:

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

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

Аритшура Сот Петри

Сеть Петри

Р:;с. 1: Архчтектура АСРС

оперировать понятиями посяедсяательностя и параллельности деи-стзпй, альтернативным выбором и итерацией, прерыванием одного действия другим;

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

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

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

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

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

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

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

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

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

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

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

Для решение первой проблемы предлагается представляет межпотоковую (и^ёге^еат) и вяутрипотезеозуго (ш!;га5£геат) еггпхроагоащгю объектов мультимедиа с помощью композиции сетевых объектов через точки доступа па основе переходов, при этом естественно помечая некоторым регулярным способом переходы во внутренних сетях Петрп. Более того, понятие объекта позволяет компактно специфицировать такие операции взаимодействия с пользователем (ОВП) как стоп п продолжить. Для спецификации ОВП прервать, начать заново, пропустить предлагается использовать синхронизацию сетей через ТДМ„ (конкретизируя их до

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

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

¡^МодслыроЕанпе^^- Бсрифцкацпя^ ^

•I Формальная модель - ко2лпозншональные сети Петри. :

Рис. 2: Схема технология спецификации миссии АПР.

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

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

Заключение и основные выводы

Основные выводы, результаты и рекомендации, полученные в диссертации:

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

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

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

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

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

зователсм па основе операций синхронизации через точки доступа ТДМ и ТДП. Разработала методологах применения АСРС в качестве среды визуального программирования: миссии автономного подводного робота.

Публикации по теме диссертации:

[1] Аннсимоз H.A., Голепков Е.А., Кишипскжй К.П., Коваленко A.A., Графический LOTOS па базе сетей Петри и средства его обработки// Технология программирования 90-х / Тез. докл. мшкд. коиф. (Киев, 14-17 мая, 1991), - Киев: ИК АН УССР, 1931, 97-98.

[2] Аписпмов H.A., Коваленко A.A., Поступальский П.Л., Скманчук A.C. Графический редактор протоколов сетей ЭВМ на базе сетей Петрп // Семнадцатая Международная школа - семинар по вычислительным сетям (Алма-Ата, 1992), -Mj. ВИНИТИ, 1S32, ч.2, с.3-8.

[3] Анпсемов H.A., Коваленко A.A., Поступальский П.А., Сиыанчук A.C. Автоматизированная система спецификации протоколов на базе сетей Петри // Тез. докл. V 'совещания по распределенным вычислительным системам и сетям (SDS-92), (7-11 сент. 1992, Калн-нштрад),-М: ИШШ РАН., 1992.

[4] Anisimov N.A., Kovalenko A.A., Posiupabki P.A., Simancuk A.S. A Graphical Petri Net Based Editor for Visualization ox Distributed and Parallel Systems, Lecture Hoiss ir. Computer Science 631, (SpringerVerlag, 1992) 847-848.

[о] Anisimov N.A., Kovalenko A.A., Postupalski P.A. Two-Levels Formal Model for Protocol Specification Based on Petri Nets // Network Information Processing Systems. Pros, of the IFIP TCG Int. Symp. ed. K. Bcyanov, (Bulgarian Academy of Sciences, 1993) 143-154.

[6] Anisimov N.A., Kovabnko A.A., Postupalski P.A. Compositional Petri Net Environment, Proc. of the 1994 IEEE Symposium on Emerging Technologies & Factory Automation: ETFA '94, November 6-10, 1994, Tokyo, Japan, 420-427.

[7] Anisiaiov N.A., Kovalenko A.A., Postupalski P.A., PN3-Editor: Compositional Petri Net Editor for Protocol Specification, Proc. of the. 3rd International Workshop on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems, (January 18-20,1995, Durham.

NC, USA), ed. P.Dowd, E.Gelenbe, (IEEE Computer Society Press, 1995) 325-323.

[8] Anisimov N.A., Kovalenko A.A., Towards Petri Net Calculi based on Synchronization via Flares, Proc. of the 1995 IEE3 Symposium en Parallel Algorithms/Architecture Synthesis, March 15-17, 1995, Aizu, Japan, 261-270.

[9] Anisimov N.A., Khaiitonov D.P., Kovalenko A.A., Postupalski P.A. Compositional Petri Net Environment for Specification of Communication Protocols, Proc. IFIP WG 6.1 15th International Symposium on Protocol Specification, Testing and Verification, Warsaw, Poland, 13-16 June, 1SS5, 463.

[10] Anisimov N.A., Kharitonov D.I., Kovalenko A.A.', "Folliipalski P.A,, Voioltb A.F., Modeling and Verification of Communication Protocols Using Petri Nets, Proc. Pacific Int. Conf. Mathematical Modeling and Cryptography (PMMC-95), August 13-20, 1995, Vladivostok, p. 12.

[llj Anisimov N.A., Kovalenko A.A., Pcstupals'd P.A., VUOng S., A Compositional Approach to the Specification of Multimedia Objects Using Petri Nets, Proc. Emerging Technologies & Applications in Communications (etaCOM-96), May 6-10, Oregon, Portland, 1S5G, pp. 38-41.

[12] Ardsimo. N., Kovalenko A., Asynchroncia Composition of Petri Nets via Places, Perspectives of System Infonnatics (Proc. Andrei Ershov . Second International Memorial Conference), - Novosibirsk? A.P.Ershov Institute of informatics Systems, 199G, pp. 214-219. '

Личный вклад автора.

Все резз'льтаты, составляющие основное содержание диссертации, получены автором самостоятельно. В работах, выполненных г еег^тсрстве, А.А.Коваченко внес следующий вклад: [1, 2, 3, 4, 7, 9] — рггработапы общая архитектура, внешний интерфейс я методология прзза^егггл базовой п алгебраической подсистем; [5, 6, .3, 10, 12] — сферкуллрсхглы п исследованы свойства синхрозязашга сетей Петри через мзета; [11] — развиты методы и способы применения хомпозициояалып.г<: cs rei: Петри для описания распределенных объектов мультимедиа.

КОВАЛЕНКО Алексей Алексеевич

РАЗРАБОТКА МЕТОДОВ И СРЕДСТВ СПЕЦИФИКАЦИИ ВЗАИМОДЕЙСТВИЯ РАСПРЕДЕЛЕННЫХ СИСТЕМ НА ОСНОВЕ КОМПОЗИЦИОНАЛЬНЫХ СЕТЕЙ ПЕТРИ

Подписало к печати 28.05.96г. Усл.и.л. 1,0. Уч.-пзд.н. 0,8 Формат 60x84/16. Тираж 100. Заказ .

Издало ПАПУ ДВО РАН. Владивосток, Радио, 5. Отпечатало участком оперативной печати ПАПУ ДВО РАН Владивосток, Радио, 5.