Polytech-soft.com

ПК журнал
0 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Безопасная сеть петри

Сети Петри. Структура и правила выполнения сетей Петри.

Сети Петри Править

Сети Петри — математический аппарат для моделирования динамических дискретных систем. Впервые описаны Карлом Петри в 1962 году.

Пример работы сети Петри

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

Событием называют срабатывание перехода, при котором метки из входных позиций этого перехода перемещаются в выходные позиции. События происходят мгновенно, либо разновременно, при выполнении некоторых условий.

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

$ Введите сюда формулу $ ==Структура сетей Петри==

Сеть Петри состоит из 4-х элементов:

  • множество позиций P,
  • множество переходов T,
  • входная функция I,
  • выходная функция O.

Пример сети Петри. Белыми кружками обозначены позиции, полосками — переходы, чёрными кружками — метки.

Входная и выходная функции связаны с переходами и позициями. Входная функция I отображает переход tj в множество позиций I(tj) , называемых входными позициями перехода . Выходная функция O отображает переход pi в множество позиций O(pi) , называемых выходными позициями перехода . Структура сети Петри определяется её позициями, переходами, входной и выходной функциями.

Сеть Петри С является четверкой, C=(P,T,I,O). P=1, p2, . pi, pn> — конечное множество позиций, n>=0. T=< t1, t2, . tj, tm > — конечное множество переходов, m>=0. Множество позиций и множество переходов не пересекаются, то есть пересечение P и T равно пустому множеству. I: T->P ¥ является входной функцией — отображением из переходов в комплекты позиций. O: P ¥ ->T есть выходная функция — отображение из комплектов позиций в переходы.

Произвольный элемент P обозначается символом pi , i=1, . n, а произвольный элемент T — символом tj, j=1, . m.

Правила выполнения сетей Петри Править

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

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

Читать еще:  Скачать лечение жесткого диска

Определение. Переход $ t_j in T $ маркированной сети Петри $ C = (P, T, I, O, mu) $ с маркировкой $ mu $ , разрешен, если для всех $ p_j in P $ , $ mu (p_i) geq # (p_i, I(t_j)) $ .

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

>Переход t3 I(t3) = и O(t3) = разрешен каждый раз, когда в р2 будет хотя бы одна фишка. Переход t3 запускается удалением одной фишки из позиции р2 и помещением одной фишки в позицию р3 и р4 (его выходы). Переход t4, в котором I(t4) = и O(t4) = запускается удалением по одной фишке из позиций р4 и р5, при этом одна фишка помещается в р5 и две в р6 (рис. 2).

Определение. Переход $ t_j $ в маркированной сети Петри с маркировкой $ mu $ может быть запущен всякий раз, когда он разрешен. В результате запуска разрешенного перехода $ t_j $ образуется новая маркировка $ mu^ <'>$ :

$ mu^ <'>(p_i) = mu (p_j) — # (p_i, I(t_j) + # (p_i, O(t_j)) $

Задачи анализа сетей Петри

Безопасность

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

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

Если pi I(tj) и pi О(tj), тогда добавить pi к О(tj).

Если pi О(tj) и pi I(tj), тогда добавить pi к I(tj).

Простая сеть Петри на рис. 4.1 преобразована в безопасную на рис. 4.2.

Рис. 3.1. Небезопасная сеть Петри. Рис. 3.2 Безопасная сеть Петри

Ограниченность

Безопасность – это частный случай более общего свойства ограниченности. Позиция является k-безопасной или k-ограниченной, если количество фишек в ней не может превышать целое число k.

1-безопасная позиция называется просто безопасной. Заметим, что граница k‘ по числу фишек, которые могут находиться в позиции, может быть функцией от позиции (например, позиция p1 может быть 3-безопасной, тогда как позиция р2 – 8-безопасной). Однако, если позиция pi k -безопасна, то она также и k‘-безопасна для всех k‘ ≥ k. Поскольку число позиций конечно, можно выбрать k, равное максимуму из границ каждой позиции, и определить сеть Петри k-безопасной, если каждая позиция сети k-безопасна.

Читать еще:  Домашний телефон не видит сеть

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

Сохранение

Определение 4.3. Сеть Петри С = (Р, Т, I, О) с начальной маркировкой μ называется строго сохраняющей, если для всех μ’ R(C, μ )

.

Строгое сохранение – это очень сильное ограничение. Например, из него немедленно следует, что число входов в каждый переход должно равняться числу выходов, |I(tj)| = |О(tj)| . Если бы это было не так, запуск перехода изменил бы число фишек в сети.

Однако для более общего представления о свойстве сохранения рассмотрим рис. 4.3. Изображенная на нем сеть Петри не является строго сохраняющей, поскольку запуск перехода t1 или t2 уменьшит число фишек на 1, а запуск перехода t3 или t4 добавит фишку к маркировке. Мы можем тем не менее преобразовать эту сеть Петри в сеть на рис. 4.4, являющуюся строго сохраняющей.

Рис. 3.3. Не строго сохраняющая сеть Петри Рис. 3.4. Строго сохраняющая сеть Петри

В общем можно определить взвешивание фишек. Взвешенная сумма для всех достижимых маркировок должна быть постоянной. Фишкам, не являющимся важными, можно присвоить вес 0; другим фишкам можно присвоить веса 1, 2, 3 или любое другое целое.

Фишка определяется ее позицией в сети, все фишки в позиции неразличимы. Следовательно, веса связываются с каждой позицией сети. Вектор взвешивания w = (w 1, w 2, . w n) определяет вес w i для каждой позиции pi P.

Сеть Петри С = (Р, Т, I, О) с начальной маркировкой μ называется сохраняющей по отношению к вектору взвешивания w, w = (w 1, w 2, . w n), n = |Р|, w i ≥ 0, если для всех μ’ R(C, μ )

.

Строго сохраняющая сеть Петри является сохраняющей по отношению к вектору взвешивания (1, 1, . 1). Все сети Петри являются сохраняющими по отношению к вектору взвешивания (0, 0, . 0). Поэтому сеть Петри будем называть сохраняющей, если она сохраняющая по отношению к некоторому положительному ненулевому вектору взвешивания w > 0 (с положительными ненулевыми весами, wi > 0). Так сеть Петри с рис. 4.3 является поэтому сохраняющей, поскольку она сохраняющая по отношению к (1, 1, 2, 2, 1). Сеть Петри с рис. 3.4 не является сохраняющей.

Читать еще:  Вконтакте социальная сеть войти

Активность

Тупик в сети Петри – это переход (или множество переходов), которые не могут быть запущены. Переход называется активным, если он не заблокирован (нетупиковый). Это не означает, что переход разрешен, скорее он может быть разрешенным. Переход tj сети Петри С называется потенциально запустимым в маркировке μ, если существует маркировка μ’ R(C, μ), в которой tj разрешен. Переход активен в маркировке μ, если потенциально запустим во всякой маркировке из R(C, μ). Следовательно, если переход активен, то всегда возможно перевести сети Петри из ее текущей маркировки в маркировку, в которой запуск перехода станет разрешенным.

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

Уровень 0: Переход tj обладает активностью уровня 0, если он никогда не может быть запущен.

Уровень 1: Переход tj обладает активностью уровня 1, если он потенциально запустим, т.е. если существует такая tj μ’ R(C, μ), что tj разрешен в μ’.

Уровень 2: Переход tj обладает активностью уровня 2, если для всякого целого n существует последовательность запусков, в которой tj присутствует по крайней мере n раз.

Уровень 3: Переход tj обладает активностью уровня 3, если существует бесконечная последовательность запусков, в которой tj присутствует неограниченно часто.

Уровень 4: Переход tj обладает активностью уровня 4, если для всякой μ’ R(C, μ) существует такая последовательность запусков σ, что tj разрешен в δ(μ’, σ).

Переход, обладающий активностью уровня 0, называется пассивным. Переход, обладающий активностью уровня 4, называется активным. Сеть Петри обладает активностью уровня i, если каждый ее переход обладает активностью уровня i.

В качестве примера, иллюстрирующего уровни активности, рассмотрим сеть Петри на рис. 3.5.

Переход t не может быть запущен никогда; он пассивен. Переход t1 можно запустить точно один раз; он обладает активностью уровня 1. Переход t2 может быть запущен произвольное число раз, но это число зависит от числа запусков перехода t3. Если мы хотим запустить t2 пять раз, мы запускаем пять раз t3, затем t1 и после этого пять раз t2. Однако, как только запустится t1 (t1 должен быть запущен до того, как будет как будет запущен t2), число возможных запусков t2 станет фиксированным. Следовательно, t2 обладает активностью уровня 2, но не уровня 3. С другой стороны, переход t3 можно запускать бесконечное число раз, и поэтому он обладает активностью уровня 3, но не уровня 4, поскольку, как только запустится t1, t3 больше запустить будет нельзя.

Ссылка на основную публикацию
Adblock
detector