7.4. Подклассы сетей Петри

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

Многие задачи, связанные с подклассами сетей Петри, могут быть решены. И цель этой части исследований сетей Петри достаточно проста: определить подкласс сетей Петри, который может моделировать большой класс систем (все или почти все интересующие нас системы), но для которого еще существуют простые процедуры анализа (по крайней мере для интересующих нас проблем). Необходимо также, чтобы существовал простой способ для определения, является ли какая-либо сеть Петри членом определенного подкласса. Все определенные подклассы являются синтаксическими или структурными подклассами, и можно легко проанализировать структуру сети Петри для выяснения, является ли эта сеть Петри членом определенного подкласса. В этом их отличие от подклассов, которые можно определить в соответствии с динамическими свойствами, такими, как устойчивые сети Петри [161] или ограниченные сети Петри. Такие подклассы могут иметь очень хорошие свойства, но для них очень трудно определить, является ли произвольная данная сеть Петри устойчивой или ограниченной.

Достаточно полно изучены только два главных подкласса модели сетей Петри: автоматные сети Петри и маркированные графы. Кроме того, Хэк [107] изучил подкласс, названный сетями Петри со свободным выбором, и сформулировал предположения, что другой подкласс, правильные сети Петри могут иметь хорошие свойства с точки зрения разрешимости. Мы представим каждый из этих классов и укажем их основные свойства, достоинства и недостатки.

7.4.1. Автоматные сети Петри

Автоматная сеть Петри — это сеть Петри, в которой каждый переход может иметь точно один выход и один вход.

Определение 7.1. Автоматная сеть Петри — это сеть Петри такая, что для всех

Некоторые свойства автоматных сетей Петри очевидны. Прежде всего автоматные сети Петри — строго сохраняющие. Это означает, что число фишек в такой сети никогда не изменяется, и мы получаем таким образом конечную систему. Отсюда следует, что дерево достижимости для автоматной сети Петри является конечным, и, следовательно, все вопросы анализа для автоматных сетей Петри разрешимы. Фактически автоматные сети Петри эквивалентны автоматам, как они определяются в теории автоматов и формальных языков (см. разд. 3.3.1). Таким образом, эти модели имеют ограниченный интерес, несмотря на их мощность разрешения, из-за ограниченной мощности моделирования конечных автоматов.

7.4.2. Маркированные графы

Другим, часто упоминаемым в литературе подклассом сетей Петри является класс маркированных графов. Маркированный граф есть сеть Петри, в которой каждая позиция является входом для точно одного перехода и выходом точно одного перехода. Иначе говоря, мы можем сказать, что каждая позиция имеет точно один вход и один выход.

Определение 7.2. Маркированный граф есть сеть Петри , такая, что для каждой

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

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

Рис. 7.13. Маркированный граф.

Таким образом, цикл есть замкнутый путь из какого-либо перехода обратно в этот же переход.

Например, в маркированном графе на рис. 7.13 последовательность является циклом, как и последовательности и

Важность циклов в маркированных графах вытекает из следующей теоремы.

Теорема 7.1. Число фишек в цикле маркированного графа не изменяется в результате запусков переходов.

Используя эту теорему, легко показать следующее.

Теорема 7.2. Маркировка является активной тогда и только тогда, когда в каждом цикле маркированного графа присутствует по меньшей мере одна фишка.

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

Эти теоремы предоставляют простой и легкий путь исследования структуры маркированного графа и определения из его структуры

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

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

Большая мощность разрешения маркированных графов очевидна из следующих теорем и работ по маркированным графам [127, 54, 91, 136, 209]. Однако существует связь между мощностью разрешения и мощностью моделирования, и высокая мощность разрешения маркированных графов частично проистекает из низкой мощности моделирования. Поэтому исследователи пытались выделить другие подклассы сетей Петри, которые оставляли бы высокой мощность разрешения маркированных графов и увеличивали их мощность моделирования.

7.4.3. Сети Петри со свободным выбором

Хэк в своей диссертации на степень магистра в МТИ [107] определил и исследовал один такой подкласс сетей Петри — сети Петри со свободным выбором. Этот подкласс допускает и конфликты автоматных сетей Петри, и параллельность маркированных графов, но в более ограниченном виде, чем в обычных сетях Петри.

Определение 7.3. Сеть Петри со свободным выбором есть сеть Петри такая, что для всех либо либо

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

Эта ограниченная форма конфликтов была допущена Хэком [107] для доказательства необходимого и достаточного условия того, чтобы маркированная сеть Петри со свободным выбором являлась активной или безопасной. Условие активности связано с маркировками ловушек и тупиков в сети. Ловушка — это такое множество позиций, что каждый переход, входом для которого является одна

Рис. 7.14. (см. скан) Диаграмма осуществимости некоторых структурных конфигураций в различных сетях Петри.

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

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

Эта теорема основывается на работе Коммонера [53, 107]. Для определения необходимого и достаточного условия безопасности нужно показать, что сеть Петри со свободным выбором покрывается объединением автоматных сетей Петри. Детали этого представления содержатся в работе [107].

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

7.4.4. Правильные сети Петри

Хэком также был определен другой подкласс сетей Петри, на званный правильными сетями Петри [107]. В правильных сетях требуется, чтобы каждый переход имел не более одной входной позиции, которая совместно используется с другим переходом и поэтому служит для ограничения возможностей возникновения конфликтов. Исследования свойств этого подкласса сетей Петри до сих пор не проводились.

7.5. Замечания к литературе

Доказательство Патила [233] того факта, что P/V-системы не могут решить всех задач синхронизации, и контр доказательства Парнаса [230] весьма кратки и интересны. Они привели к доказательству в [159, 7] того, что сети Петри не могут моделировать все без исключения параллельные системы. Эти результаты привели Агервалу к исследованию вопроса о том, что должно присутствовать в модели, которая может описывать все системы [4, 5].

Главной работой по ограниченным моделям сетей Петри является ранняя работа [128] и работа [54], а также более поздняя [107]. В некоторых работах продолжено изучение маркированных графов [136, 209], но очень мало было сделано по другим моделям. Некоторые обнадеживающие результаты для сетей Петри со свободным выбором, в которых получены в работах [62 и 161]. Задачи достижимости и активности разрешимы для сетей, свободных от конфликтов.

7.6. Темы для дальнейшего изучения

1. Одно из предложений по расширению состоит в сопоставлении фишкам информации. Это сопоставление может быть представлено как сеть Петри с окрашенными фишками. Определите модель сети Петри с окрашенными фишками. Используйте эту расширенную модель для проверки гипотез: (а) они эквивалентны обычным сетям Петри, (б) они эквивалентны машинам Тьюринга (допуская

проверку на нуль). Основной задачей будет определение действий перехода с окрашенными фишками.

2. Продолжите исследование свойств «правильных» сетей Петри, сетей Петри, свободных от конфликтов, и сетей Петри со свободным выбором.

3. Охарактеризуйте класс сетей Петри, которые являются и маркированными графами, и автоматными сетями Петри.

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