Цель работы

Общие положения

Как указано в [8], сети Петри являются удобным аппаратом моделирования параллельных процессов, т.е. процессов, протекающих в системе независимо один от другого. На выполнение таких процессов не накладываются какие-либо условия синхронизации. Моменты начала и завершения параллельных процессов, интервалы их реализации не являются в системе взаимообусловленными. Параллельным процессам соответствуют состояния сетей Петри, в которых разрешены сразу несколько переходов, и каждый из них может сработать. Однако, какой именно переход сработает решается всякий раз случайным образом по правилам равновероятного выбора. Сети Петри широко используются при моделировании и управлении гибкими производственными системами.

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

Сети Петри, как и конечные автоматы, функционируют в дискретном времени, но естественный ход времени в сетях Петри не моделируется, т.к. события упорядочены не по отношению «следует непосредственно после» (как в конечных автоматах), а лишь по отношению «следует после».

Для полного описания функционирования сети Петри С задаются:

1. Непустое конечное множество позиций Р = (р₁,…,р_n).

2. Непустое конечное множество переходов Т = (t₁,…,t_m); эти множества не пересекаются: РÇТ = 0.

3. Начальная маркировка или разметка сети: М₀ = (М₀(р₁),…,М₀(р_n)) Î - n-вектор, компоненты которого целые, неотрицательные числа; они указывают количество меток или фишек в каждой позиции сети Петри в начальный момент времени. В результате функционирования сети Петри в каждый момент времени k возникает текущая разметка:

M_k = (M_k(p₁),…,M_k(p_n)), M_k(p₁) Î Z₀,

Определяющая состояние сети в этот момент времени (М₀ – начальное состояние).

4. Взаимосвязь позиций и переходов задается множествами:

– позиции на входах перехода ;

– позиции на выходах перехода ;

– переходы на входах позиции ;

– переходы на выходах позиции .

5. Функция переходов f, определяющая М^~ - возможное состояние сети С при начальной маркировке М₀ следующее за состоянием М, но не обязательно непосредственно за М.

Функция f определяется правилами функционирования:

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

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

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

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

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

Цель работы

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