Лекция о сетях Петри от Шамаля (547780), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

На рис. 5 изображена сеть Петри, моделирующая систему, известную как «задача о волке, козле и капусте», которую должен решить лодочник: как перевезти на другой берег реки всех троих, если в лодку с собой лодочник может брать не более одного «пассажира», а, с другой стороны, нельзя оставлять без присмотра волка вместе с козлом и козла вместе с капустой?

Н
аличие фишки в позициях интерпретируется как то, что, соответственно, лодочник, волк, козел и капуста находятся на левом (правом) берегу. При начальной маркировке все находятся на левом берегу.

Переходы обозначают следующие события:

– переезд лодочника с левого берега на правый (с правого на левый), соответственно, без пассажиров, с волком, с козлом и с капустой;

– волк съедает козла, козел съедает капусту на левом берегу (на правом берегу), пока лодочник находится на правом берегу (на левом берегу).

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

Пример 4.

На рис. 6 изображена модель решения задачи об «обедающих философах». Позиция представляет комнату, в которой философы ведут свои философские споры. В начальной маркировке в этой позиции находится фишек ( – количество философов). Рядом находится столовая, в середине которой стоит круглый стол. Вокруг стола расположено кресел, перед каждым из которых находится блюдо с рисом, а между ними лежит палочка для еды. Если кресло свободно, то любой «философствующий» философ из первой комнаты может его занять для последующего принятия пищи. Для того, чтобы начать есть, необходимы две палочки, которые занявший кресло философ может взять, соответственно, только справа и слева от своего блюда с рисом. Поев, философ возвращает палочки на свои прежние места, покидает кресло и возвращается в первую комнату для продолжения философских споров.

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

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

Языки сетей Петри.

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

1. -типа – для определения языка сети Петри рассматриваются истории достижения маркировок из заданного конечного подмножества :

  ,

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

  ,

1. -типа – для определения языка сети Петри рассматриваются истории достижения любых тупиковых маркировок:

  ,

1. -типа – для определения языка сети Петри рассматриваются истории достижения любых достижимых в сети маркировок (маркировок из ):

  .

В сочетании с тремя основными способами раскрашивания переходов в сети:

• свободного раскрашивания,

• произвольного раскрашивания (произвольными буквами из заданного алфавита),

• -раскрашивания (произвольными буквами из заданного алфавита или символом пустого слова ; в последнем случае переход иногда называют не окрашенным),

получается 12 основных классов формальных языков сетей Петри:

Известны следующие результаты о включениях этих классов языков:

На рис. 7-9 приведены примеры сетей, реализующих некоторые языки -типа (с использованием произвольного и -раскрашивания переходов). На рис. 10 показано, как по сети , реализующей некоторый язык -типа с произвольным или -раскрашиванием переходов, построить реализующую этот же язык сеть с семантикой -типа и тем же способом раскрашивания переходов. При построении множество позиций остается неизменным, а каждому переходу в сети в сети сопоставляется подмножество переходов, окрашенных так же, как и исходный переход в сети . По построению очевидно, что для всякого слова  , такого, что для сети , найдется история поведения сети , такая, что она не приведет не приведет к получению «лишних» фишек (из разности маркировок), т.е. для сети выполняется , так как раскраска переходов в сети сохраняется и в сети . Верно также и обратное - если  , то есть для сети , то найдется история поведения сети , такая, что . Иными словами, на этом рисунке дана иллюстрация доказательства включений и .

П

ри анализе языков сетей Петри важную роль играет довольно очевидный результат. Пусть и - сети отличающиеся только своими начальными маркировками и , причем такими, что , имеет место соотношение . Тогда очевидно, что если для некоторой последовательности переходов значение определено, то и определено, причем . Это свойство обычно называют семантической монотонностью сетей Петри. Отсюда, в частности следуют следующие утверждения относительно языков сетей Петри с любым способом раскрашивания переходов:

•    ,

•    ,

•    .

Специальные подклассы сетей Петри

Автоматные сети. Для автоматных сетей вводится ограничение на функции и : , т.е. все переходы имеют одну входную дугу и одну выходную дугу. Если в начальной маркировке есть единственная фишка в некоторой позиции, то такие сети с -раскрашиванием переходов ничем принципиально не отличаются от так называемых графов переходов (позиции сети представляют состояния графа переходов), рассматриваемых в теории конечных автоматов. Как следствие, языки таких сетей Петри являются регулярными. При наличии большего числа фишек в начальной маркировке язык этой сети является «смесью» языков сетей Петри с тем же графом и с начальными маркировками , такими, что . Напомним, что «смесь» двух формальных языков и в алфавите определяется так:

;

если и , то

.

О
чевидно, что автоматные сети являются ограниченными, т.к. количество фишек в автоматных сетях не меняется в результате срабатывания любого перехода. Из этого, в частности, следует, что смесь регулярных языков представляет собой тоже регулярный язык.

На рис. 11 приведен пример автоматной сети.

Маркированные графы. Если для некоторой сети Петри выполняется условие:

то эта сеть называется маркированным графом.

Циклом в маркированном графе называется «кольцо» переходов  , такое, что . Известны следующие результаты:

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

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

3. Маркированный граф является безопасной сетью, если для каждого его цикла в начальной маркировке есть ровно одна фишка в позициях, связывающих переходы этого цикла.

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

На рис. 12 приведен пример маркированного графа.

Расширения и обобщения формализма сетей Петри

Обратной стороной простоты и изящества применения формализма сетей Петри при описании относительно простых параллельных систем являются недостатки, проявляющиеся при моделировании более сложных систем. Во-первых, существенным ограничивающим фактором является семантическая монотонность обычных сетей Петри. Во-вторых, абстрактное понимание ресурсов как ничем не отличающихся «фишек» приводит к быстрому росту сложности графа сети при моделировании систем, требующих дифференциации ресурсов. Эти и другие прак тические недостатки базового формализма привели к многочисленным предложениям по его обобщению, модификации и расширению. Рас смотрим некоторые наиболее известные из этих предложений.

Характеристики

Список файлов лекций