Питерсон Дж. - Теория сетей Петри и моделирование систем - 1984 (1184511), страница 16
Текст из файла (страница 16)
Последовательности запусков Другой, предложенный к анализу подход основан не на позициях, а йа последовательностях запусков переходов, т. е. связан с активностью, поскольку уместен вопрос: может ли переход быть запущен (иначе, не является ли он пассивным)? В более общем случае можно потребовать определить, возможна ли заданная последовательность запусков переходов или возможна ли какая-либо последовательность из множества последовательностей запусков. В сети Петри на рис. 4.8, например, взаимное исключение было бы нарушенным, если бы могла осуществиться последовательность Ф«1« или 1«1 е, или, более общо, если бы могла возникнуть последовательность 1«о1„где о — произвольная последовательность запусков, не включающая йн Эти вопросы анализа приводят к понятию языков сетей Петри и будут исследованы более детально в гл. 6. 1 4.1.7. Задачи эквивалентности и подмножества Последний класс задач порожден соображениями оптимизации.
Пусть сети Петри присуще некоторое поведение, определяемое ее ) т '„" множеством последовательностей запусков переходов или ее мно, жеством достижнмосги. Можно ли изменить (оптнмизировать) сеть ', Петри, не изменяя ее поведения? Изменение означает удаление - пассивных переходов (которые никогда нельзя запустить), илн пас,'„сивных позиций (которые никогда не могут быть маркированы), плн переопределение некоторых переходов. Можно лн показать, Глава 4 что две различные маркированные сети Петри с одинаковым числом переходов (но с различным числом позиций) будут порождать одинаковые последовательности запусков переходов или что две различные маркированные сети Петри с одинаковым числом позиций (но с различным числом переходов) будут порождать одно множество достижимости? Это позволило бы нам модифицировать сети Петри для увеличения параллелизма, уменьшения стоимости реализации нлн улучшения других оптимизируемых функционалов.
В этих случаях мы затрагиваем проблему определения того, являются ли две сети Петри эквивалентными или является лн одна из них подмножеством другой. Для точного определения понятия эквивалентности или включения необходимо быть особенно внимательным. Если мы определим эквивалентность как равенство множеств достижнмости, тогда нельзя будет изменить число позиций, если потребуем равенства множеств последовательностей— нельзя будет изменять переходы.
Поэтому определение задачи, которое мы дадим, исключительно важно. 4Л. Методы анализа Задачи, которые были представлены здесь, являкпся наиболее общими, тем не менее существует множество других задач, решение которых может потребоваться для сетей Петри. Можно ли разработать методы анализа сетей Петри для решения этих задач) Причем иас интересуют особенно те методы, которые легко реализовались бы на ЭВМ, что важно для осуществления автоматического анализа моделируемых систем. В этом разделе мы представим два основных метода анализа сетей Петри, которые описывают механизмы решения некоторых из уже перечисленных задач.
Первый метод анализа, используемый для сетей Петри, — это дерева дастижимоелни, второй метод"связан с матричными уравнениями. Обсудим каждый из них. 4.2.1. Дерево достижимостм Дерево достижимости представляет множество достнжимости сети Петри.
Рассмотрим, например, маркированную сеть" Петри на рис. 4.9. Начальная маркировка ее — (1, О, О). В этой начальной маркировке разрешены два перехода: 1, и 1,. Поскольку мы хотим рассмотреть все множества достижимости, определим новые вершины в дереве достнжимостим для (достнжимых) маркировок, получающихся в результате запуска каждого из этих двух переходов.
Дуга, помеченная запускаемым переходом, приводит из начальной маркировки к каждой из новых маркировок (рис. 4.10). И Корневой (начальной) является вершина,соответствующая начальной маркировке. — Приль. нарев. Аиоаиа сетей Петри 91 с)то (частичное) дерево показывает все маркировки, непосредственно достижимые из начальной маркировки. Теперь необходимо рассмотреть все маркировки, достижимые из новых маркировок. Из маркировки (1, 1, О) можно снова запустить г! (получая 1, 2, 0) и 8а (получая (О, 2, 1)); из (О, 1, 1) можно запустить |а (получая (О, О, 1)).
Это порождает дерево, изображенное на рис. 4.11. Начиная с трех новых маркировок, необходимо повторить этот процесс, порождая новые маркировки, которые нужно (1,0,0) гд Ру г1 Ра Од,о) (0,1,1) ! Рис. 4.9. Маркированная сеть Пет- Рнс. 4.10. Перимй гиаг построения ри, для которой строится дерево до- дерева достижимости, и стижимости 4,, ввести в дерево, как показано на рис. 4.12. Заметим, что марки- ,'1 ровка (О, О, 1) пассивная; никакой переход в ней не является разрешенным, поэтому никакие новые маркировки из этой пассивной , маркировки в дереве порождаться не будуг. Кроме того, необхо- ~!', димо отметить, что маркировка (О, 1, 1), порождаемая запуском )! 1а в (О. 2, 1), была уже порождена непосредственно из начальной „маркировки запуском (а.
Если эту процедуру повторять снова и снова, каждая достижи- ' мая маркировка окажется порожденной. Однако получившееся (1,0,0) (1,1,0) гэ (1,2,0) (0,2,!) (0,0,!) Рис. 4.11. Второй шаг построения дерева досгижимости. тт тт Ряс. 4Л2. Третей шаг построения дерева доотижвмости. дерево достижимости может оказаться бесконечным.
Будет порождена каждая маркировка из множества достижимостн, поэтому для любой сети Петри с бесконечным множеством дастижимости соответствувхцее дерево также должно быть бесконечным. Даже сеть Петри с конечным множеством достижимости может иметь бесконечное дерево (рис. 4.13). Дерево представляет все возможные последовательности запусков переходов. Всякий путь в дереве, начинающийся в корне, соответствует допустимой последовательности переходов.
Для превращения дерева в полезный' инструмент анализа необходимо найти средства ограничения его до конечного размера. (Заметим, что если какое-то представление бесконечного множества конечно, то бесконечное множество маркировок должно отображаться в такое представление. В общем случае это приведет к потере информации и, возможно, к тому, что некоторые свойствз сетей Петри определить будет нельзя, но все зависит от того, как представление было получено.) Приведение к конечному представлению осуществляется несколькими способами. Нам необходимо найти те средства, которые ограничивают введение новых маркировок (называемых граничными вершинами) на каждом шаге.
Здесь могут помочь пассивные маркировки — маркировки, в которых нет разрешенных переходов. Эти пассивные маркировки нааывэются терминальными вершинами. Другой класс маркировок — это маркировки, ранее А навез сетей Петри встречавшиеся в дереве. Такие дублирующие маркировки называются дублирдюи(ими еерилишми; никакие последующие маркировки рассматривать нет нужды — все они будут порождены из места первого появления дублирующей маркировки в дереве. Таким образом, в дереве на рис. 4.12 маркировка (О, 1, 1), получившаяся «,о> ~т <о,П «,о1 <о, П «,о1 ~с, Рис. 4«Э.
Простая сеть Петри с бесиоиечиым деревом достижимости. в результате выполнения последовательности 1,1е1а, не будет порождать какие-либо новые вершины в дереве, поскольку она ранее ~ встречалась в дереве в результате выполнения последовательности 1е из начальной маркировки. Для сведения дерева достижнмости к конечному представлению используется еще одно средство. Рассмотрим последовательность запусков переходов о, начинающуюся в начальной маркировке р, и кончающуюся в маркировке (ь', )ь' ) р. Маркировка (ь' совпадает с маркировкой р, за исключением того, что имеет некоторые «дополнительнынь фишки в некоторых позиш1ях, т.
е. р' = р + ()ь'— — (ь) и ((ь' — тр)) О. Теперь, поскольку на запуски переходов лишние ~ряшки не влияют, последовательность а можно запустить снова, начиная в р', приходя к маркировке р . Так как действие последовательности переходов а добавило р,' — р фишек к маркировке и, она добавит также р' — р фишек н к маркировке р', по.этому р" = р'+ (р' — р) или р" = р+ 2(р' — р).
В общем можно запустить последовательность о и раз, получив в результате маркировку р+ пОь' — р). Следовательно, для тех позиций, ко, торые увеличивают число фишек последовательностью а, можно создать произвольно большое число фишек, просто повторяя последовательность о столько, сколько это нужно. В сети Петри на Гла«о 4 рис. 4.9, например, можно запустить переход Г, столько рзз, сколько необходимо для того, чтобы получить произвольное число фишек в рь Представим бесконечное число маркировок, получающихся из циклов такого типа, с помощью специального символа гь, который обозначает «бесконечностыь Для любого постоянного а определим е+а=-«, а(оъ м — а = в, в «~ е. Для построения дерева достнжимсстн необходимы только зтн операции над гь. Теперь можно точно сформулировать действительный алгоритм построения дерева достижнмости.
Каждая вершина 1 дерева связывается с расширенной маркировкой у(11; в расширенной маркировке число фишек в позиции может быть либо неотрицательным целым, либо а. Каждая вершина классифицируется или как гранячная вершина, терминальная вершина, дублирующая вершина, или как внутренняя вершина. Граничными являются вершины, которые еще не обработаны алгоритмом; алгоритм превратит их в терминальные, дублирующие или внутренние вершины. Алгоритм начинает с определения начальной маркировки корнем дерева, т. е. граничной першиной.
До тех пор пока имеются граничные вершины, они обрабатываются алгоритмом. Пусть х — граничная вершина, которую необходимо обработать. 1. Если в дереве имеется другая вершина у, не являющаяся граничной, н с ией связана та же маркировка, рЫ = р(у1, то вершина х — дублируюп1ая. 2. Если для маркировки р(х! нн один из переходов не разрешен (т. е. 6(рЫ, гт) не определено для всех Гт Е Т), то х — лмрмииальнах вернллш. 3. Для всякого перехода Гг Е Т, разрешенного в р [х1 (т. е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
