1.3. Анализ сетей Петри

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

Безопасность. Позиция p_iÎ Pсети Петри С = (P, Т, I, О) с начальной маркировкой μявляется безопасной, если μ' (p_i) ≤ 1 для любой μ' Î R(C, μ). Сеть Петри безопасна, если безопасна каждая ее позиция. Безопасность — очень важное свойство для устройств аппаратного обеспечения. Если позиция безопасна, то число фишек в ней равно 0 или 1. Следовательно, позицию можно реализовать одним триггером.

Ограниченность. Безопасность — это частный случай более общего свойства ограниченности. Позиция p_i Î Pсети Петри С — (Р, Т, I, О) с начальной маркировкой μявляется k-безопасной, если μ'(р _i) ≤ kдля всех μ' Î R(C, μ). 1-безопасная позиция называется просто безопасной. Заметим, что граница kпо числу фишек, которые могут находиться в позиции, может быть функцией от позиции (например, позиция p₁может быть 3-безопасной, тогда как позиция p₂ — 8-безопасной). Однако, если позиция p_ik-безопасна, то она также и k'-безопасна для всех k' ³ k. Поскольку число позиций конечно, можно выбрать k^*, равное максимуму из границ каждой позиции, и определить сеть Петри k^*-безопасной, если каждая позиция сети k^*-безопасна.

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

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

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

.

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

Сеть Петри должна сохранять ресурсы, которые она моделирует. Однако взаимно однозначного соответствия между фишками и ресурсами нет. Фишка может представлять и один программный счетчик или какой-нибудь другой элемент и может представлять несколько ресурсов сразу. Во втором случае фишка позже используется для создания кратных фишек (по одной на ресурс) путем запуска перехода с большим числом выходов, чем входов. В общем, следует определить взвешивание фишек. Взвешенная сумма для всех достижимых маркировок должна быть постоянной. Фишкам, не являющимся важными, можно присвоить вес 0; другим фишкам можно присвоить веса 1, 2, 3 или любое другое целое. Фишка определяется ее позицией в сети, все фишки в позиции неразличимы. Следовательно, веса связываются с каждой позицией сети. Вектор взвешивания w= (w₁, w₂, ..., w_n ) определяет вес w_i для каждой позиции p_iÎ P.

Сеть Петри С = (Р, Т, I, О) с начальной маркировкой μ называется сохраняющей по отношению к вектору взвешивания w = (w₁, w₂, ..., w_n ), n= |P|, w_i ³ 0, если для всех μ' Î R(С, μ)

.

Строго сохраняющая сеть Петри является сохраняющей по отношению к вектору взвешивания (1, 1, ..., 1). Все сети Петри являются сохраняющими по отношению к вектору взвешивания (0, 0, ..., 0). Этот факт вносит в теорию некоторую нестройность. Поэтому можно потребовать, чтобы сеть Петри называлась сохраняющей, если она сохраняющая по отношению к некоторому положительному ненулевому вектору взвешивания w > 0 (с положительными ненулевыми весами w_i > 0).

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

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

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

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

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

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

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

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

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

Устойчивость переходов и СП. Переход t_i СП С = (Р, Т, I, О) с маркировкой μ называется устойчивым, если он активен при данной маркировке и никакой другой переход t_k , тоже активный при маркировке μ, не может, сработав, сделать переход t_i неактивным, т.е. лишив его возможности срабатывания. СП С = (Р, Т, I, О) с маркировкой μ называется устойчивой, если все ее переходы являются устойчивыми.

Достижимость и покрываемость. Большинство задач, к которым мы до сих пор обращались, касаются достижимых маркировок.

Задача достижимости. Для данной сети Петри С с маркировкой μ и маркировки μ' определить: μ' Î R(C, μ )? Задача достижимости, быть может, основная задача анализа сетей Петри; многие другие задачи анализа можно сформулировать в терминах задачи достижимости.

Задача покрываемости. Эта задача аналогична достижимости, но несколько отличается. Для данной сети Петри С с начальной маркировкой μи маркировки μ’ определить, существует ли такая достижимая маркировка μ" Î R(C, μ ), что μ" ³ μ '.

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

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

Задачи эквивалентности и подмножества. Последний класс задач порожден соображениями оптимизации. Пусть сети Петри присуще некоторое поведение, определяемое ее множеством последовательностей запусков переходов или ее множеством достижимости. Можно ли изменить (оптимизировать) сеть Петри, не изменяя ее поведения? Изменение означает удаление пассивных переходов (которые никогда нельзя запустить) или пассивных позиций {которые никогда не могут быть маркированы), или переопределение некоторых переходов. Можно ли показать, что две различные маркированные сети Петри с одинаковым числом переходов (но с различным числом позиций) будут порождать одинаковые последовательности запусков переходов или что две различные маркированные сети Петри с одинаковым числом позиций (но с различным числом переходов) будут порождать одно множество достижимости? Это позволило бы модифицировать сети Петри для увеличения параллелизма, уменьшения стоимости реализации или улучшения других оптимизируемых функционалов. В этих случаях затрагивается проблема определения того, являются ли две сети Петри эквивалентными или является ли одна из них подмножеством другой. Для точного определения понятия эквивалентности или включения необходимо быть особенно внимательным. Если определить эквивалентность как равенство множеств достижимости, тогда нельзя будет изменять число позиций, если потребовать равенства множеств последовательностей — нельзя будет изменять переходы. Поэтому определение задачи, которое дается, исключительно важно.