Сети Петри

Введение

Сети Петри являются простым и удобным средством, предназначенным для моделирования различных распределенных систем и процессов. Данную модель изобрел немецкий ученый Карл Петри в 1939-ом году, для того чтобы описать различные химические процессы. Однако начало официальной истории сетей Петри относится к 1962-ому году, когда Карл Петри сумел защитить диссертацию «Kommunikation mit Automaten», где он и представил понятие «сети Петри».

Сети Петри

Сеть Петри является двудольным ориентированным графом, содержащим вершины двух типов:

• «места», которые следует обозначать кружками,
• «переходы», которые следует обозначать прямоугольниками.

Каждая дуга может вести или от вершины типа «места» в вершину типа «переход», или же наоборот. Дуги, которые соединяют два «места» или два «перехода», являются запрещенными. Места, которые не имеют входящих дуг, именуются входными. Места, которые не обладают исходящими дугами, именуются выходными.

Любое место сети Петри может иметь нуль или больше меток, которые называются маркерами (tokens). Все метки должны считаться как одинаковые и неотличимые друг от друга. Распределение меток по местам сети именуется ее разметкой. Работа сети должна начинаться с изначальной разметки.

Метки можно переносить с одного места на другое. Перенос меток должен выполняться по следующим правилам:

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

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

На рисунке ниже изображен пример работы сети Петри для последовательности срабатываний $C_t = [t_i, t_3]$.

Рисунок 1. Пример работы сети Петри. Автор24 — интернет-биржа студенческих работ

Активные переходы для каждого случая помечены звездочкой. Следует отметить, что для той же сети существует еще лишь одна возможная последовательность срабатываний $Ct = [t1, t2]$.

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

1. Зеленый цвет.
2. Желтый цвет.
3. Красный цвет.

Рисунок 2. Моделирование работы простого светофора. Автор24 — интернет-биржа студенческих работ

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

Формально сети Петри могут быть определены следующими компонентами: S, T,W, µ0, где:

1. S является конечным множеством мест (|S| = n).
2. T является конечным множеством переходов (|T| = m).
3. W : (S х T) U (T х S) → Z+ является мультимножеством дуг.
4. µ0 : S → Z+ является начальной разметкой сети.
5. Символом Z+ обозначено множество неотрицательных целых чисел.

Сети Петри могут быть заданы и в компактном векторно-матричном формате. В таком варианте, структура сети Петри, то есть ее граф, должна описываться при помощи двух матриц, а именно, W + и W-, имеющих размер nxm. Из матриц W+ и W- может быть составлена еще одна матрица W = W+ - W-, которая, как правило, применяется, для того чтобы вычислить новое состояние (разметку) сети после применения к ней требуемой последовательности срабатываний. Начальная разметка сети должна задаваться целочисленным вектором µ0, имеющим длину n.

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

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

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