Функционирование сети Петри. Области применения сетей Петри

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

1) Осуществляется начальная разметка сети, при которой в ее узлы помещаются метки – носители определенной информации. Число меток совпадает с числом адресов, по которым должен быть разослан результат решения поставленной задачи. Каждая из меток содержит всю необходимую информацию об адресате, т.е. о конечном узле и о результатах срабатывания переходов.

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

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

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

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

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

На рис. 4.1з представлено положение, когда два параллельных процесса P₁P₂ могут обратиться к одним и тем же общим данным. Каждый процесс имеет два состояния – активное и пассивное, которые определяются двумя узлами. Каждый из процессов может изменять свое состояние, перемыкая соответствующий переход.

Циклы обеих процессов связаны так называемым узлом-семафором (переключателем) S (раздел 6.2). Чтоб обратиться к общим данным, процесс должен поменять свое пассивное состояние на активное. Это можно сделать, если метка семафора S не используется в это время другим процессом.

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

Моделирование вычислений. На рис.4.1и представлена сеть Петри в виде сумматора, который определяет сумму пяти чисел, находящихся в узле Y. В сети имеются специальный "стартовый" узел St с меткой "1",с которогоначинаются вычисления, и узел "готовности" результата Fin, который помечается только после окончания суммирования и получения суммы.

Процесс сложения чисел, находящихся в узле Y, осуществляется следующим образом. После срабатывания перехода s метка перемещается в узел Р и активизирует переход t . Переход u заблокирован в это время дугой-отрицанием (см. п.4.3в).

После срабатывания перехода t первое число из Y перемещается в узел хранения суммы Х, а метка из Y попадает в узел Р, снова активизируя переход t . Процесс суммирования чисел в узле Х продолжается до тех пор, пока все метки не уйдут из Y, а связанные с ними числа не перейдут в узел Х.

При отсутствии меток в узле Y переход t блокируется и активизируется переход u, что приводит к окончанию процесса суммирования.

Моделирование параллельных алгоритмов. Параллельные алгоритмы, программируемые с использованием традиционных языков программирования ("Си", "Паскаль" и др.), легко моделируются сетями Петри: переходы соответствуют исполняемым операторам, а узлы – условным операторам if, then, else и др.

На рис. 4.1к представлена сеть Петри, моделирующая схему работы параллельного алгоритма, где Р₁,Р₂,Р₃,Р₄, - параллельные процессы вычислений.

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