Книжка по сетям Петри, страница 5

Множество всех слов, полученных выписыванием символов переходов вдоль путей, начинающихся в Ме, образует множество последовательностей срабатыва. ний сети, ипи ее свободный язык. Так, язык рассматри. ваемой сети включает слове [Л, гы гт, Ф ~ты гага, гтгз, ггг4, г\Пгнг1Гюгнгфтзгз, Г[ ге та, Рис. 1.4. Ггтчтг, ГгГг(гты Ггт~тгтг, Г~тгтгтз. Ггтгтгтч, Ггтгтчтг ...). СПЕДУЮОгалтЕО- рема характеризует аффект увеличения начальной разметки в сети. Теорема 1.1.Пустей( (Р, Т, Р, И~, Ме), д( = (Р, Т, Р, ьу, Ме + К), где КЕ(г(' '. Тогда а) МЕгг(ДГ) и (И+К! ЕЯ((У ); 6) Е(ДГ) ~(.(Д( ),' в! М, [т ) Мг ~ (Мг + К) [т ) (Мг + К!. Д о к а з а т е л ь с т в о.

Воспользуемся индукцией по длине срабатываемых последовательностей. Прежде всего Ме Е ГГ(дб и (Ме + К! Е Е Н (й') . Заметим также, что Ме [Л) Ме, где Л вЂ” пустая последовательность, ЛЕГ(Д(! и ЛЕ Г(ЛГ'). Предположим,что Ме[т)М в )у и (Ме +К) [т)(М+К! Покажем,что ЖГЕТ: М[Г)И (М+К) [Г)(М +К). Если Г может сработать при разметкеМвсети)у,т.е.М> Р(Г),тот может сработать и при разметке (М+ К) > М в сети д( . Это означает, что последовательность срабатываний тт принадлежит как Г ()у), так и Г.

(ЛГ ) . (Если Г НЕ МОжЕт Сработать при М вд(, то зто не исключает возможности срабаты. вания Г при (И+ К) > И везти д(.) После срабатывания перехода т в И и соответственно в гУ разметка в обеих сетях изменяется следующим об. разом: М вЂ” 'Р(Г) + Р'(Г) М', (И+ К) — У(Г) + Р (Г! = (М вЂ” Е(Г) + Р'(ГП+ К = М'+ К. Тем самым установлена справедливость соотношений а) и 6) . Аналогично можно убедиться в том, что имеет место соотношение в) .(') ГЛАВА 2 СВОЙСТВА СЕТЕЙ ПЕТРИ И ИХ АНАЛИЗ Для постановок задач анализа сетей Петри прежде всего необходимо указать и формально определить те свойства сетей, которые целесообразно анализировать.

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

3 2.1. Ословцые свойства сетей Петри Первое из рассматриваемых ниже свойств сетей Петри связано с ограниченной емкостью реальных условий реализаций событий. Действительно, из определения правил срабатывания переходов сети следует, что для реализации события, моделируемого некоторым переходом, достаточно. чтобы каждое его входное место-условие содержало некоторое конечное число фишск, равное кратности дуги, соединяющей его с переходом. Однако при работе сети Петри общего вида некоторые ее места могут накапливать неограниченное число фишек (например, место рз в сети на рис. 1.3) . Если интерпретировать места как накопители (буферы) данных, сигналов или деталей в моделируемых системах, то естественно потребовать. что при любом варианте функционирования этих систем не происходило бы переполнение накопителей, которые в реальных ситуациях имеют конечную, фиксированную емкость.

Следующие понятия формалнзуют такие требования. Место р в сети Петри )У = (Р, Т, г, ИГ, Ме) называется ограниченныат„ если существует число л такое, что для любой достижимой в сети разметки М справедливо неравенство М(р) <л. Сеть)уназываетсяограниченной сетью, если любое ее место ограничено. Ясно,что множество достижимых разметок Я(Л/) конечно, если н только если )У вЂ” ограниченная сеть.

8 сети на рис. 1.3 места Л~ и рз ограничены, так как каждое из них может содержать не более одной фишки. В то же время место р, не ограничено, и поэтому зта сеть не является ограниченной. Сеть на рис. 1,2 ограничена: любое место в ней не может содержать более 2 фишек. Место р называется безопасным, если туМЕЯ()у): М(р) <1; соответственно сеть безопасна, если все ее места безопасны.

Любая достижимая в безопасной сети разметка представляет собой вектор из 0 и 1. Сети на рис. 1,2 и 13 не являются безопасными (в отличив от сети на рис. 2.4, см. ниже). Ограниченность и безопасность характеризуют емкость условий: в дис. кретной информационной системе, моделируемой соответствующими сетями, можно ограничить емкость накопителей, необходимых для хране- 20 ния условий наступления событий. Родственным этим понятиям является понятие консервативной сети, в которой сумма фишек во всех ее местах остается постоянной при работе сети, т.е. уМыМг ЕВ(~): 2: М~(р) = Х Мг(р).

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

Это означает, что в моделируемых системах могут появляться ситуации, тупиковые для некоторых событий, "исключающие их из дальнейшей игры". Например, в операцмон. ных системах подобные случаи имеют место при взаимных блокировках процессов (деад)ос)сз) (см. главу 8). Следующие определения связаны с выявлением таких ситуаций в сетях Петри. Переход г в сети Петри Д( = (Р, Т, Р, Иг, Ме) называется потенциально живым при разметке М Е ВОУ), если 3 М е В Оу, М): М Э' р(г), т.е. существует достижимая от М разметка М, при которой переход г может сработать. Если М Ме, то г называется лотенииепьно живым е сети. д(.

Переход г — мертвый при М, если он ме является потенциально живым при М. Переход г — мертвый, если он мертв при любой достижимой в сети разметке. Переход г в сети Петри ЛГ называется живым, если ту м е В ( у), 8 м е В )й, м): м > 'р(г), т,е. переход Г является потенциально живым при любой достижимой в сети Д( разметке.

Переход г — погекииепьно мертвый, асли существует М Е В (В) такая, что при любой разметке М' Е В (Л( М) переход г ме может сработать. Разметка М в атом случае называется г-тупиковой; если она г.тупиковая для всех т Е Т, то она является тупиковой. Если М -тупиковая разметка, то В ( Л(. М) = (М). Сеть называется живой. если все ее переходы живы.

8 сети на рис. 1.2 есе переходы потенциально живы и все переходы потенциально мертвы, так как в ней достижима тупиковая разметка (рис. 1.2, г) . Эта сеть не может быть живой, так как содержит потенциально мертвые переходы. Сеть на рис. 1.3 также ме является живой, так кек в ней достижимы тупиковые разметки вида (О, п, О), и > О.

Переход г называется устойчивым в сети Л( еслм юг е тт(г), 1УмеВ(дб: (м~ 'р(г)я(м>''р(г')) (м>'р(г)+ 'р(г')), т.е. если переход г может сработать, то никакой другой переход не может, сработав, лишить его этой возможности. Сеть )У устойчива, если все ее пе. реходы устойчивы. 21 В сети на рис. 12 устойчивы переходы г,, г,, гэ, 14, в сети на рис. 1З устойчив только переход г,.

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

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

Говорят, что проблема разрешима, если соответствующий алгоритм распознавания свойств существует, в противном случае проблема неразрешима. Большинство из перечисленных выше проблем связано с определением возможности достижения некоторых специальных разметок в сети (напри. мер, с достижением г-тупиковых резметок для денного перехода г), т.е. с проблемой достижимостн заданной разметки. В этой проблеме ставится вопрос о существовании алгоритма, с помощью которого можно узнать для произвольной сети ДГ и произвольной разметки М, принадлежит лн М множеству Я (Д[) .

Ниже будет показано. например, что проблемы живости и достижимости эквивалентны в том смысле, что решение одной из них автоматически решает другую. Несколько особняком стоят проблемы Я-включения и Я-эквивалентности сетей Петри. Пусть задан класс сетей, которые имеют одно и то же множество мест [или их множества мест иэоморфны) . В первом случае необходимо выяснить существование алгоритма, устанавливающего для любых двух сетей из этого класса, имеет ли место соотносоение Я Щ ) ы Я ()Уз ), во втором — Я[И, ) = Я(Д[з ) .

'ч 2.2. Проблемм ограквчениости и безопасности Некоторое место р в сети )У может оказаться неограниченным по двум причинам. Первая заключается в следующем. Пусть свободный язык сети [. (д[) содержит последовательность срабатываний г = т, гз такую, что (Ме[т~ ) М1) Л (М, [тз ) Мз) Л (Мз ЭМ~) Л (Мз(Р! >М,(Р) ). Поскольку М, > М,, то любая подпоследовательность срабатываний, начинающаяся при разметке М,, может повториться и начиная с раззаетки М,. Это означает, что любая последовательность вида т, т", также принадлежит [. (Д[), каким бы большим не было и. Следовательно, разметка места р может безгранично расти.