Сети Петри

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

Дадим вначале определение двудольного графа. Граф G = (X,E) называется двудольным, если X можно представить как объединение непересекающихся множеств, , так что каждое ребро имеет вид {a,b}, где . Таким образом, каждое ребро связывает вершину из A с вершиной из B, но никакие две вершины из A или из B не являются связанными. Если в двудольном графе каждая вершина из A соединена с каждой вершиной из B, то такой граф называется полным двудольным графом и обозначается , где m и n – число вершин соответственно в A и B.

Примеры двудольных графов , ,, :

Рассмотрим сеть Петри в грифовом представлении. Сеть Петри есть двудольный ориентированный мультиграф G = (V, E) , в котором V – множество вершин. Множество V может быть разбито на два непересекающихся подмножества P и T , таких, чтои . Множество называется множеством позиций (мест), множество множеством переходов. Множество E - множество дуг между P и T.

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

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

Маркировка M сети Петри – это функция, отображающая множество позиций P в множество неотрицательных чисел : . Маркировка может быть также определена как n- размерный вектор: , где n =|P| (количество позиций в сети), а i-ая компонента вектора задает маркировку позиции и соответствует количеству фишек в позиции . Если позиция содержит фишку, то позиция маркирована и сеть называется маркированной. Начальное распределение фишек по позициям задает начальную маркировку сети. Например, если в начальном состоянии сети Петри в первой позиции находилось 3 фишки, во второй -2 фишки, а в третьей одна, то начальная маркировка сети имеет вид: . Таким образом, маркировка - это присвоение фишек позициям сети Петри.

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

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

Рис. 1.

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

Рис. 2.

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

Из приведенных ниже графических иллюстраций все сразу станет понятно:

Рис. 3.

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

Маркировка сети: .Теперь разрешены два перехода и , и любой из них может быть запущен. Если сработал переход , то происходит удаление фишки из позиции и добавление по одной фишке в позиции и . Маркировка сети . Если теперь сработает переход , то удалится фишка из позиции и добавятся по одной фишке в позиции , , .. Маркировка сети станет: . Разметка сети указана на рис. 3.в. Вновь получили состояние, где оба перехода , разрешены и любой из них может сработать первым. Запуски могут осуществляться до тех пор, пока существует хотя бы один разрешенный переход.

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

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

Рис. 4.