Труды КНЦ вып.3 (ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ вып.1 3/2010(3))

Й1ИИК ЩЧНЬВТЩДМ2011 СЕТИ ПЕТРИ И МОДЕЛИРОВАНИЕ М.В. Мальков, С.Н. Малыгина Эмпирические системы - события и явления внешнего мира, называемые «ситуациями», являют­ ся системами, состоящими из взаимосвязанных час­ тей, каждая из которых вносит свой вклад в характе­ ристики целого. При анализе эмпирические системы абстрагируются до уровня системы асинхронно взаимодействующих процессов и задают поведение данной системы. В настоящее время большой и ус­ тойчивый интерес проявляется к средствам модели­ рования и анализа сложных параллельных и распре­ деленных систем. Такими системами являются, на­ пример, вычислительные машины и комплексы с параллельной и распределенной архитектурой, па­ раллельные программы и алгоритмы, протоколы взаимодействия (коммуникационные, верифици­ рующие), модели технологических и бизнес- процессов. При исследовании сложной системы нас могут интересовать различные ее свойства. Матема­ тические методы во многих случаях позволяют по­ лучить однозначный ответ на подобные вопросы. При этом значение имеет первоначальный выбор используемого формализма, то есть способа модели­ рования реальной системы. Для решения задач ана­ лиза и верификации в теории параллельных и рас­ пределенных вычислений в настоящее время предла­ гаются различные способы моделирования реальных систем. К числу наиболее известных формализмов можно отнести конечные автоматы, алгебры процес­ сов, CCS Р. Милнера, языки трасс, а также различ­ ные их модификации, в том числе с добавлением конструкций времени и вероятности. Различные классы моделей обладают различными свойствами выразительности и алгоритмической разрешимости. Причем эти два параметра модели, как правило, про­ тиворечат друг другу: выбранный формализм может оказаться или очень выразительным и не поддаю­ щимся анализу, или же позволяющим эффективно решать все необходимые проблемы, но при этом слишком слабым, недостаточно полно описываю­ щим моделируемую систему. Для формализации процессов в дискретных динамических системах са­ мой разной природы необходимо обратиться к абст­ ракциям условий, событий, причинно-следственных связей и т.п. А если этим абстракциям поставить в соответствие определенные графические примитивы и связать их линиями, несущими определенную ло­ гику, то получится некая сеть, т.е. графический образ процесса. Сетевые методы описания и анализа про­ цессов хороши тем, что используемые в них абст­ ракции близки к интуитивным представлениям о процессах. Сеть является графическим образом про­ цесса. Пример - сети Петри или N -схемы [8]. Сети Петри - математический аппарат для моделирования динамических дискретных систем. Впервые описаны Карлом Петри в 1962 г. Популярность сетей Петри вызвана удачным представлением различных типов объектов, присутствующих во многих моделируемых системах и “событийным” подходом к моделирова­ нию. Они обладают наилучшими возможностями для описания взаимосвязей и взаимодействий парал­ лельно работающих процессов. Сети Петри являются мощным инструментом исследования моделируемых систем благодаря их возможности описания многих классов дискретных, асинхронных, параллельных, распределенных, недетерминированных систем, бла­ годаря наглядности представления их работы, разви­ тому математическому и программному аппарату анализа. Сети Петри - достаточно выразительная модель параллелизма, обладающая в то же время значительным набором разрешимых свойств. Сети Петри разрабатывались специально для моделирова­ ния тех систем, которые содержат взаимодействую­ щие параллельные компоненты, например аппарат­ ное и программное обеспечение ЭВМ, гибкие произ­ водственные системы, а также социальные и биоло­ гические системы. Существуют определённые об­ ласти, в которых сети Петри являются идеальным инструментом для моделирования: это области, в которых события происходят синхронно и независи­ мо. Одной из таких областей является аппаратное и программное обеспечение ЭВМ и других систем. Существует несколько формальных определений сети Петри, отличающихся способами задания эле­ ментов и связей в сети. Анализ сетей Петри помогает получить важную информацию о структуре и динамическом поведении моделируемой системы. Эта информация может быть полезна для оценки моделируемой системы и выработки предложений по её усовершенствованию и изменению. Анализ результатов может сказать о том, какие действия происходят, какие состояния им предшествовали, и какие состояния примет система после выполнения действия, в каких состояниях пре­ бывала или не пребывала система, какие состояния в принципе недостижимы. В сетях Петри нет строгого понятия процесса. Нет также однозначной последо­ вательности исполнения. Это позволяет гибко ис­ пользовать данный формализм для отображения и анализа причинно-следственных связей в самых раз­ нообразных процессах, происходящих в дискретных динамических системах, вне зависимости от их при­ роды. Поведение системы описывается выполнением событийной модели. Сеть Петри моделирует некото­ рую структуру и динамику ее функционирования. В настоящее время определены и изучены разнообраз­ ные классы сетей Петри. Сеть Петри имеет четыре базовых элемента: по­ зиции, переходы, дуги и метки (фишки или маркера) - см. рис.1. Позиция - это состояние, в котором на­ ходится система или определенная ее часть. Текущее 35