Сети Петри

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

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

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

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

Наилучшими возможностями описания параллельных систем обладают сети Петри. Они не менее мощные, чем PVM, MPI, SDL и другие, но чтобы их выполнять на процессорах необходимо сделать из описания параллельного распределенное.

Сеть первого рода - это цветная сеть Петри, описанная на языке предписаний.

Сеть второго рода - это сеть, представленная в виде иерархической композиции объектов.

Теория сетей Петри.

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

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

к началу документа

Простые сети Петри.

Сеть Петри из трех элементов: множество мест , множество переходов и отношение инцидентности.

Определение: Простая сеть Петри

    Простой сетью Петри называется набор , где

1. - множество мест;

2. - множество переходов таких, что .

3. - отношение инцидентности такое, что

(а) ;

(б)

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

Определение: Входное и выходное мультимножества мест и переходов

    Пусть задана сеть .

1. Если для некоторого перехода имеем , то будем обозначать ;

2. .

Будем говорить, что - входные, а - выходные места перехода . Таким образом, согласно определению, справедливо . Далее будем говорить, что место инцидентно переходу если или .

Расширим функции и на мультимножества переходов. Пусть есть мультимножество переходов такое, что . Тогда положим

.

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

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

    В качестве простого примера расссмотрим сеть , где

1. ;

2. ;

3.

В графической форме сеть представлена на Рис.1. Сеть имеет четыре места и три перехода. Отношение задает дуги сети. Так, например, элемент задает четыре дуги: из в и из в с кратностями 2, из в и из в с единичными кратностями. Для перехода справедливо и . Для места можно вычислить и .

Рис. 1: Пример графа сети Петри

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

Определение: Маркированная сеть Петри

    Маркированной сетью Петри называется набор , где

1. - сеть;

2. - начальная маркировка.

Пример. Пример маркированной сети.

    На Рис.2 приведен пример маркированной сети. В начальной маркировке место имеет две метки (токена), место - одну метку, а места , - ни одной метки, т.е. .

Рис. 2: Пример маркированной сети Петри

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

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

Определение: Правило срабатывания переходов

Пусть маркированная сеть.

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

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

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

Рис. 3: Новая сеть с маркировкой .

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

Определение: Определение T-точки доступа.

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

1. - имя (идентификатор) t-точки доступа;

2. - некоторый алфавит;

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

Определение: Определение S-точки доступа

Пусть задана сеть . Тогда s-точкой доступа сети N называется набор , где

1. - имя (идентификатор) s-точки доступа;

2. - множество такое, что .

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

1. Операция слияния переходов - позволяет порождать и описывать синхронизацию параллельных процессов (tmerge);

2. Операция слияния мест - позволяет применять к сетям операции последовательной композиции, выбора, итерации и другие (smerge).

Рис. 4: Пример операции слияния переходов

Рис. 5: Пример операции слияния мест

Приведённые операции имеют следующий смысл:

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

При слиянии переходов – определяется алфавит событий, видимых из t-точки доступа. Каждый переход в сети помечается либо невидимым событием, либо комбинацией событий из алфавита точки доступа. Слияние по переходам производится так, что если при срабатывании одной сети возникает некоторая комбинация событий, то эта же комбинация событий происходит во второй сети.

Цветные сети Петри.

Расширение простых сетей в цветные заключается в добавлении информации к элементам сети, основываясь на которой, при определённых условиях, можно преобразовать цветные сети в простые ([8]).

1. Токены вместо простого обозначения содержимого места преобразуются в объект, который может содержать в себе один или более параметров, каждый из которых может принимать дискретный набор значений. В соответствии с этим токены различаются по типам параметров (переменных). Чтобы отличать токены различных типов их можно окрашивать в различные цвета (поэтому сети называют цветными)

2. К местам добавляется информация о типах токенов, которые могут находится в данном месте.

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

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

(and )

5. К дугам, исходящим из переходов, добавляется информация о типах токенов, исходящих из перехода и о преобразовании переменных.

6. К начальной маркировке сети добавляется информация о значении переменных, содержащихся в токенах.

В графическом представлении информацию, которую можно однозначно достроить из сопутствующей информации, можно пропускать. Приведем пример цветной сети Петри (Рис. 6)

Рис. 6: Пример цветной сети Петри (очередь)

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

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

Точки доступа в цветной сети.

S-точка доступа. Как видно из определения s-точки доступа, она задаётся множеством маркировок, которые считаются эквивалентными в смысле наступления состояний, определённых этими маркировками, в синхронизируемых по s-точке доступа сетях. При задании s-точки доступа в цветной сети, маркировки могут содержать в себе места, в которые могут поступать токены различных типов. Такие места при преобразовании в простую сеть разбиваются на множество мест, количество которых равно мощности множества значений токенов допустимых в этом месте. Согласно смыслу операции мы обязаны будем в синхронизированной сети раздробить эти места, чтобы удовлетворить множеству значений токенов во второй сети. Получается, что при синхронизации мест одинакового типа (с одинаковыми допустимыми типами токенов) значение параметров одной сети никак не влияет на значение параметров другой, то есть смысл операции в цветных и простых сетях может пониматься по-разному. Чтобы этого избежать, надо доопределить s-точку доступа:

Определение:

Пусть заданы: цветная сеть N и С – множество типов токенов в этой сети. Тогда s-точкой доступа сети N называется набор , где

1. - имя (идентификатор) s-точки доступа;

2. - некоторый алфавит;

3. - множество такое, что .

4. , где , причём если . - пометочная функция мест, ставящая в соответствие каждому типу токена в месте уникальное имя из алфавита.

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