Пособие ТСиСА

t5

P5

в

P2

P3

P9

P4

P5

P1

P6

P7

P8

г

Рис. 58. Пример сети Петри

130

Заключение

Таким образом, анализ сети Петри включает в себя предварительный этап, на котором специалист определяет:

–в каких состояниях находилась или не находилась система;

–какие состояния в принципе не являются достижимыми;

–является ли построенная модель системы оптимальной;

–работает ли модель должным образом и все ли ошибки устра-

нены;

–является ли конечным число ее состояний (свойство ограниченности);

–возможно ли возникновение или уничтожение ресурсов в моделируемой системе (свойство сохраняемости);

–имеется ли возможность срабатывания любого перехода при функционировании моделируемой системы (свойство живости);

–гарантирована ли работа системы при следующем запуске;

–присутствуют ли конфликтные позиции (свойство устойчиво-

сти);

–порождает ли сеть Петри маркировки, для которых другие маркировки недостижимы.

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

133

ГЛАВА 5. ВИДЫ СЕТЕЙ ПЕТРИ

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

5.1. Общие теоретические сведения

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

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

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

134

Ординарные Сети Петри

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

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

Итак, цветные сети Петри или раскрашенные сети Йенсена2 характеризуются следующими особенностями (рис. 60, а–б):

– разметка сети задается с помощью индивидуальных, т. е. различимых маркеров;

2 Теория раскрашенных сетей Петри (Coloured Petri Net, CP-net) разрабатывается более 30 лет рабочей группой (CPN Group) университета г. Орхуса (University of Aarhus, Denmark) под руководством профессора Курта Йенсена (Kurt Jensen)

135

–за каждым маркером в раскрашенной сети может быть закреплен соответствующий цвет (тип);

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

–позиции также могу иметь цвет, при этом позиция может содержать маркеры только приписанного ей цвета (типа);

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

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

–за каждым элементом раскрашенной сети Петри закрепляется соответствующая метка: имя, множество цветов, инициализирующее выражение или охранные функции;

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

–переход может содержать два типа меток: имя перехода и охранные функции (логическое выражение, которое должно быть выполнено до срабатывания перехода);

–дуга может быть описана двумя типами меток: инициализирующим выражением и множеством цветов;

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

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

136

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

Голубой

а

Голубой

б

Рис. 60. Простейшая раскрашенная Сеть Петри:

а– ситуация до срабатывания перехода t1;

б– ситуация после срабатывания перехода t1

Рассмотрим модель процесса сдачи экзамена для системы кафедра. Имеется три типа позиций: студенты, преподаватель и экзаменационные билеты. Определены три множества цветов: множество с элементами «студент», множество с элементами «преподаватель» и множество с элементами «экзаменационный билет». Чтобы запустить переход t1 (принятие экзамена), необходимо наличие маркеров в позициях студент, преподаватель и экзаменационный билет (рис. 61, а). Переменные «студент, «преподаватель» и «билет» используются для извлечения маркеров из входных позиций и добавления их в выходные позиции сети.

137

После того, как один из студентов сдаст экзамен, из студенческой группы выбирается следующий студент, экзаменационный билет и преподаватель. Студент, который был извлечен из позиции P1, будет помещен в позицию P4, так как выходной дуге перехода t1, присвоена переменная с именем «студент». Преподаватель, который был извлечен из позиции P2, будет возвращен в позицию P2, так как выходной дуге перехода t1, присвоена переменная с именем «преподаватель». Экзаменационный билет, который был извлечен из позиции P3, будет помещен в позицию P5, так как выходной дуге перехода t1, присвоена переменная с именем «билет» (рис. 61, б).

билеты=29

б

Рис. 61. Пример цветной сети Петри:

а– ситуация до срабатывания перехода t1;

б– ситуация до срабатывания перехода t1

138

на специальность «Электромеханика»; P4 – принятие документов на специальность «Налоги и налогообложение»; P5 – объявление результатов конкурса; P6 –обучение в университете; t1 – проверка наличия в перечень необходимых документов сертификата ЕГЭ по информатике; t2 – проверка наличия в перечень необходимых документов сертификата ЕГЭ по физике; t3 – проверка наличия в перечень необходимых документов сертификата ЕГЭ по обществознанию; t4, t5 и t6 – получение результатов конкурса (абитуриент выбывает из

t4

t5

t6

Рис. 62. Пример цветной сети Петри, описывающей процесс подачи документов на специальность

139