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

N = (T,P,A), T Ç Р = Ø,
где Т = {t₁, t₂, ..., t_n} - подмножество вершин, называющихся переходами;
Р = {p₁, р₂, ..., p_m} - подмножество вершин, называющихся местами;
А Í (T×P) Ç (P×T) - множество ориентированных дуг.

По определению, дуга соединяет либо место с переходом, либо переход с местом.

Пример 1

На рис. 4.3,а приведен пример сети Петри в графическом представлении. Переходы обозначены черточками, а места - окружностями. Каждый переход t имеет набор входных in{t} и набор выходных out{t} дуг. Сети Петри могут представляться также в форме продукционных правил (рис. 4.3,б).

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

a                             б

Рис 4.3

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

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

Фишка свидетельствует о том, что переменная/буфер имеет значение, а если место имеет, к примеру, 3 фишки, то это может интерпретироваться как наличие трех разных значений в буфере. Если место содержит фишку, то место маркировано и сеть называется маркированной. Начальное распределение фишек задает начальную маркировку М₀ сети. Маркировка сети определяет ее текущее состояние.

Сеть на рис. 4.4 в начальном состоянии содержит одну фишку в месте р₃. Маркировка формально задается функцией М: Р → I, I = {0,1,2,..}, а функция М представляется вектором, в котором i-й компонент задает маркировку места p_i. Например, начальная маркировка сети на рис. 4.4 представляется вектором М₀ = {1,0,0}.

Рис 4.4

На рис. 4.4 показана последовательность состояний сети Петри в ходе срабатывания переходов. Начальная разметка М₀ = (1,0,0) показана на рис. 4.4,а. В этом состоянии может сработать только переход t₁. Разметка сети M₁ = (1,1,1) после срабатывания t₁ показана на рис. 4.4,б. Последняя позволяет одновременно сработать переходам t₁ и t₂ , разметка М₂ = (1,2,3) после их срабатывания показана на рис. 4.4,в.

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

Рис 4.5

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

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

Рис 4.6

Пример 2

Рассмотрим пример конвейера. Пусть есть три обрабатывающих устройства t₀, t₁, t₂ организованные в виде конвейера. Это могут быть, например, станки на заводе или функциональные устройства конвейерного процессора и вообще любой конвейер, в котором каждое обрабатывающее устройство выполняет лишь часть общей работы, а результат будет выработан лишь последним из них.

Особенностью нашего конвейера является ограниченность емкости мест p₁ и р₂; место p₁ может вместить лишь два результата (место p₁ сети является 2-ограниченым) предшествующего этапа работы конвейера (вырабатывается переходом t₀ ), а место p₂ - 3-ограниченным. Символ n в месте р₀ означает наличие n фишек в нем, n - целое положительной число.

Сеть Петри, обеспечивающая необходимое прямое управление, приведена на рис. 4.7. Понятно, что в месте p₁ не может накопиться более 2 фишек при любых порядках срабатывания переходов сети. Места p₁ и р₂ часто еще называют асинхронными каналами, с их помощью реализуется программирование средствами асинхронного message passing interface (см. подраздел 4.3).

Рис 4.7

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

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

control procedure pipiline (t₀, p₄, t₁, p₅, t₂);
<описание сети примера 1>;

Теперь, при необходимости задать в программе конвейерное вычисление некоторых процедур, их имена подставляются в обращение к управляющей процедуре pipiline вместо формальных параметров t₀, t₁, t₂.

call pipiline (t₀ = procl, p₄ = 2, t₁ = proc2, p₅ = 3, t₂ = proc3.)

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

Сеть примера 2 может быть использована также для управления асинхронным каналом при описания и реализации message passing interface в языках с асинхронными взаимодействиями.