4.4. Анализ сетей Петри
Моделирование систем сетями Петри, прежде всего, обусловлено необходимостью проведения исследования их поведения. Этот подход предполагает сведения исследования свойств реальной системы к анализу определенных свойств моделирующей сети Петри. Следовательно, для проведения такого исследования необходимы методы анализа свойств самих сетей Петри.
Позиция p P сети Петри N = ( P , Т , I , O ) c начальной маркировкой M 0 является k — ограниченной , если M ( p ) ≤ k для любой достижимой марки-
П р и м е р. Пусть есть три обрабатывающих устройства t 0 , t 1 , t 2, организованные в виде конвейера (рис. 4.22). Это могут быть, например, станки на заводе или функциональные устройства конвейерного процессора и вообще любой конвейер, в котором каждое обрабатывающее устройство выполняет лишь часть общей работы, а результат будет выработан лишь последним из них.
Особенностью данного конвейера является ограниченность емкости позиций p 1 и р 2 . Понятно, что в позиции p 1 не может накопиться более 2 фишек при любых порядках срабатывания переходов сети. То есть позиция p 1 является 2-ограниченной, соответственно p 2 – 3-ограниченной. Символ n в позиции р 0 означает наличие n фишек в нем, n > 0.
Рис. 4.22. Конвейер с тремя обрабатывающими устройствами
Сеть Петри ограничена , если все ее позиции ограничены. Если ни в одной позиции сети при любой последовательности срабатываний переходов количество фишек не превышает некоторого значения k , то такую сеть называют k -ограниченной.
Например, сеть на рис. 4.23 является ограниченной – при любом срабатывании сети количество фишек в любой позиции не превысит 1. Заметим, что само функционирование этой сети – бесконечно. То есть у данной сети отсутствует тупиковая разметка.
Также не достигается тупиковая разметка сети на рис. 4.24. Однако эта сеть не является ограниченной – количество фишек в любой позиции может увеличиваться бесконечно.
Рис. 4.24. Неограниченная сеть
Позиция p P сети Петри N = ( P , Т , I , O ) c начальной маркировкой M 0 является безопасной , если она 1 — ограниченная. Сеть Петри безопасна , если безопасны все позиции сети (рис. 4.23). Любая достижимая в сети маркировка представляет собой вектор из нулей и единиц.
Безопасной сетью можно задавать прямое управление в программах. Безопасная сеть никогда не допустит, чтобы в переменную было положено новое значение, если старое еще не было использовано по назначению. Нарушения этого правила часто являются причиной ошибок в параллельных программах.
Ограниченность и безопасность характеризуют емкость условий. Например, в дискретной информационной системе, моделируемой сетью Петри, можно ограничить емкость накопителей, необходимых для хранения условий наступления событий.
Сеть Петри N = ( P , Т , I , O ) c начальной маркировкой M 0 называется сохраняющей (или консервативной ), если сумма фишек по всем позициям остается постоянной в процессе выполнения сети, т. е. для любой достижимой маркировки M справедливо следующее равенство:
Это свойство особенно присуще сетям, в которых фишки интерпретируются как ресурсы: фишки не должны ни создаваться, ни уничтожаться, следовательно, число входов в каждый переход должно равняться числу выходов.
Тупик в сети Петри – это переход (или множество переходов), который в имеющейся маркировке M и в последующих достижимых из M маркировках не разрешен.
Под живостью перехода t понимают принципиальную возможность его срабатывания при функционировании сети Петри.
Переход t в сети Петри N = ( P , Т , I , O , M 0 ) называется потенциально живым при маркировке M R ( N , M 0 ), если
т. е. существует достижимая из М маркировка М ’, при которой переход t может сработать. Если М = М 0 , то t называется потенциально живым в сети N . Переход t – мертвый при М , если он не является потенциально живым при М . Переход t – мертвый, если он мертв при любой достижимой в сети маркировке.
Переход t в сети Петри N называется живым , если
M R ( N , M 0 ), M ‘ R ( N , M ) : M ≥ ‘ F ( t ),
т. е. переход t является потенциально живым при любой достижимой в сети N маркировке. Переход t – потенциально мертвый, если существует M R ( N , M 0 ) такая, что при любой маркировке M ’ R ( N , M ) переход t не может сработать. Маркировка М в этом случае называется t- тупиковой.
Если она t -тупиковая для всех t T , то она является тупиковой. Сеть называется живой , если все ее переходы – живые.
Сети Петри присуще некоторое поведение, которое определяется множеством ее возможных последовательностей запусков переходов или ее множеством достижимых маркировок. Понятие эквивалентности сетей Петри определяется через равенство множеств достижимых маркировок.
Сеть Петри N = ( P , Т , I , O , M 0 ) и сеть Петри N ’ = ( P ’, Т ’, I ’, O ’, M 0 ’)
эквивалентны , если справедливо R ( N , M 0 ) = R ( N ’, M 0 ’).
Понятие эквивалентности сетей Петри может быть определено также через равенство множеств возможных последовательностей запусков переходов.
Более слабым, по сравнению с эквивалентностью, является свойство включения , которое определяется аналогично свойству эквивалентности:
При анализе сетей Петри большое значение имеют задачи дости-
Задача достижимости формулируется следующим образом. Достижима ли маркировка M для данной сети Петри N с начальной маркиров-
Задача покрываемости : для данной сети Петри N с начальной маркировкой M 0 и маркировки M определить, существует ли такая достижимая маркировка M ’ R ( N , M 0 ), что M ’ ≥ M . (Отношение M ’ ≥ M истинно, если каждый элемент маркировки M ’ не меньше соответствующего элемента маркировки M .)
Конечная цель теории сетей Петри – автоматический анализ свойств сетей, их автоматические синтез и преобразования, на основании чего могут быть построены практические алгоритмы анализа, синтеза и преобразований дискретных систем, моделируемых сетями. В частности, полезно найти алгоритмы, с помощью которых для любой предъявленной сети можно установить, обладает ли она интересующим для нас свойством – является ли она ограниченной, живой, устойчивой и т. п. В первую очередь нужно выяснить существование таких алгоритмов.
Эти вопросы формулируются как массовые алгоритмические проблемы для сетей: проблема ограниченности (существует ли алгоритм, который позволяет узнать, является ли данная сеть ограниченной), проблема потенциальной живости переходов, проблема живости сетей, проблема устойчивости, проблема безопасности. Говорят, что проблема разрешима, если соответствующий алгоритм распознавания свойств существует, в противном случае проблема не разрешима.
Рассмотрим метод анализа сетей Петри, который основан на использовании покрывающего дерева. Покрывающее дерево представляет все достижимые маркировки сети Петри, а также все возможные последовательности запусков ее переходов. На рис. 4.25 приведена сеть Петри и соответствующее ей частичное покрывающее дерево для трех шагов выполнения.
Рис. 4.25. Сеть Петри и покрывающее дерево
Для сети Петри с бесконечным множеством достижимых маркировок покрывающее дерево является бесконечным. Сеть Петри с конечным множеством достижимых маркировок также может иметь бесконечное покрывающее дерево (как, например, сеть на рис. 4.25). Для превращения бесконечного дерева в полезный инструмент анализа строится его конечное представление. При построении конечного покрывающего дерева для обозначения бесконечного множества значений маркировки позиции вводится специальный символ, расширяющий множество натуральных чисел ω : Nat ω = Nat < ω >. Для ω и любого натурального числа n Nat характерны следующие свойства:
2) n + ω = ω + n = ω + ω = ω – n = ω – ω = ω ;
Алгоритм построения конечного покрывающего дерева
Данный алгоритм состоит из следующих шагов:
1. Первоначально предполагается, что дерево содержит единственную вершину-корень М 0 и не имеет дуг.
2. Пусть М – вершина дерева, которая еще не объявлена листом (т. е. вершиной, из которой не исходит ни одна дуга), но в дереве нет исходящих из нее дуг. Возможны четыре случая:
а) ни один из переходов сети не может сработать при разметке М , т.
е. t T : M ≠ * F ( t ) . В этом случае вершина М объявляется листом.
б) на пути из корня дерева в вершину М существует вершина М ’ такая, что М = М ’. Вершина М объявляется листом.
г) если ни один из вышеперечисленных случаев не имеет места, то М – внутренняя вершина дерева. Для каждого перехода t T такого, что М ≥ * F ( t ), в дерево добавляется новая вершина М ’ = М – * F ( t ) + F * ( t )
и дуга, ведущая из М в М ’, помеченная символом t .
П р и м е р. На рис. 4.26 показана сеть Петри и ее конечное покрывающее дерево.
Рис. 4.26. Сеть Петри и ее конечное покрывающее дерево
Важнейшим свойством алгоритма построения конечного покрывающего дерева является то, что он за конечное число шагов заканчивает работу.
4.4.3. Анализ свойств сетей Петри на основе покрывающего дерева
Анализ безопасности и ограниченности. Сеть Петри ограниченна тогдаи только тогда, когда символ ω отсутствует в ее покрывающем дереве.
Присутствие символа ω в покрывающем дереве ( M x ( p ) = ω для некоторой вершины дерева x и позиции p ) означает, что для произвольного положительного целого k существует достижимая маркировка со значением в позиции p , большим, чем k (а также бесконечность множества достижимых маркировок). Это, в свою очередь, означает неограниченность позиции p , а следовательно, и самой сети Петри.
Отсутствие символа ω в покрывающем дереве означает, что множество достижимых маркировок конечно. Следовательно, простым перебором можно найти верхнюю границу как для каждой позиции в отдельности, так и общую верхнюю границу для всех позиций. Последнее означает ограниченность сети Петри. Если граница для всех позиций равна 1, то сеть Петри безопасна.
Анализ сохранения. Так как покрывающее дерево конечно, для каждой маркировки можно вычислить сумму начальной маркировки. Если эта сумма одинакова для каждой достижимой маркировки, то сеть Петри является сохраняющей. Если суммы не равны, сеть не является сохраняющей. Если маркировка некоторой позиции совпадает с ω , то эта позиция должна был исключена из рассмотрения.
Анализ покрываемости. Требуется для заданной маркировки M ‘ определить, достижима ли маркировка M » ≥ M ‘. Такая задача решается путем простого перебора вершин покрывающего дерева. При этом ищется такая вершина х , что M x ≥ M ‘. Если такой вершины не существует, то маркировка M ‘ не является покрываемой. Если она найдена, то M x определяет покрывающую маркировку для M ‘. Если компонента маркировки M x , соответствующая некоторой позиции p, совпадает с ω , то конкретное ее значение может быть вычислено. В этом случае на пути от начальной маркировки к покрывающей маркировке имеется повторяющаяся последовательность переходов, запуск которой увеличивает значение маркировки в позиции p . Число таких повторений должно быть таким, чтобы значение маркировки в позиции p превзошло или сравнялось с M ‘( p ).
Анализ живости. Переход t сети Петри является потенциально живым тогда и только тогда, когда он метит некоторую дугу в покрывающем дереве этой сети.
Покрывающее дерево можно использовать для решения задач безопасности, ограниченности, сохранения и покрываемости. К сожалению, в общем случае его нельзя использовать для решения задач достижимости,
активности и эквивалентности. Решение этих задач ограничено существованием символа ω . Символ ω означает потерю информации: конкретные количества фишек отбрасываются, а учитывается только существование их большого числа.
Контрольные вопросы и задания
1. При исследовании систем с помощью сетей Петри сначала строится система, а затем она моделируется сетью Петри, или сначала строится сеть Петри, а затем сеть преобразуется в реальную систему? Или же возможен любой из описанных подходов?
2. Сеть Петри является синхронной или асинхронной моделью сис-
3. Можно ли с помощью сетей Петри моделировать последовательные процессы?
4. Может ли сеть Петри иметь бесконечное множество маркировок?
5. Каково максимальное число фишек, которые может содержать позиция в сети Петри?
6. Какой переход сети Петри называется живым, потенциально живым, мертвым?
7. Какая сеть Петри называется безопасной?
8. Анализ каких свойств сетей Петри можно выполнить при помощи покрывающего дерева?
9. Сформулируйте задачу достижимости и задачу покрываемости.
10. Почему покрывающее дерево нельзя использовать при решении задачи достижимости?
Источник