Питерсон Дж. - Теория сетей Петри и моделирование систем - 1984 (1184511), страница 36
Текст из файла (страница 36)
Фактически автоматные сети Петри эквивалентны автоматам, как они определяются в теории автоматов и формальных языков (см. разд. 3.3.1). Таким образом, эти модели имеют ограниченный интерес, несмотря на их мощность разрешения, из-за ограниченной мощности моделирования конечных автоматов. 7.4.2. Маркированные графы Другим, часто упоминаемым в литературе подклассом сетей Петри является класс маркированных графов. Маркированный граф есть сеть Петри, в которой каждая позиция является входом для точно одного перехода н выходом точно одного перехода.
Иначе говоря, мы можем сказать, что каждая позиция имеет точно один вход н один выход. Определение 7.2. А1аркированный граф есть сеть Петри С = (Р, Т, 7, О), такая, что для каждой р; ~ Р: ~ «Р,) ~ = ! (1; ! Р; Е 0 (~т)) ~ = 1 и ~ 0 (Р,) ~ =- = ! (1; ! Гч Е7(17)) ! = 1. Маркированные графы двойственны автоматным сетям Петри в теоретико-графовом смысле, поскольку в автоматных сетях Петри переходы имеют адин вход и один выход, в то время как в маркированных графах один вход и один выход имеют позиции. Они являются двойственными также и с точки зрения моделирования. В автоматных сетях Петри легко представить конфликтные ситуации с помощью позиции с несколькими выходами, но нельзя моделировать создание и уничтожение фишек, необходимых для моделирования параллельности, илн ожидания, свойственные задачам синхронизации.
С другой стороны, маркированные графы могут моделировать параллельность и синхронизацию, но не могут моделировать конфликты нли принятие решений, зависящие от данных. Риеииренные и ограниченные людели сетей Петри 20! Изучены такие свойства маркированных графов, как активность, безопасность и достижимость. Наиболее интересными структурными компонентами маркированного графа при изучении указанных свойств являются его цгисгги. Цикл в маркированном графе — это последовательность переходов 1~,, 1;, 1~„-", 1;„— такая, что для каждой пары переходов 1;, и 1~,, из этой последовательности существует позиция ргт — такая, что рт„Е 0(1;„) и р, ~ Г(~,- ). ра Рис. 7ЛЗ.
Маркированный граф. Таким образом, цикл есть замкнутый путь из какого-либо перехода обратно в этот же переход. Например, в маркированном графе на рис. 7.13 последовательность гфА является циклом, как и последовательности Г,1а~а и ~аГа~з~А- Важность циклов в маркированных графах вытекает из следующей теоремы, Теорема 7.1. Число фишек в цикле маркированного графа не изменяется в результате запусков переходов. Используя эту теорему, легко показать следукхцее. Теорема 7.2. Маркировка является активной тогда н только тогда когда в каждом цикле маркированного графа присутствует по м шей мере одна фишка. Теорема 7.3. Активная маркировка является безопасной тогда " только тогда, когда каждая позиция маркированного гран находится в цикле с числом фишек, равным единице. Эти теоремы предоставляют простой и легкий путь исследования струк1уры маркированного графа и определения из его структуРы 8 — 562 Глава 1 202 и начальной маркировки, является ли маркированный граф активным нли безопасным.
Можно также показать, что задача достижимостн маркировок для маркированных графов разрешима. Например, отметим следующее. Теорема 7.4. Маркировками' достижима нз активной маркировки (г в сильно связном маркированном графе тогда н только тогда, когда общее число фишек в каждом цикле маркированного графа совпадает для маркировок р, н р,'. Большая мощность разрешения маркированных графов очевидна из следующих теорем и работ по маркированным графам (127, 54, 91, 136, 209(. Однако существует связь между мощностью разрешении и мощностью моделирования, и высокая мощность разрешения маркированных графов частично проистекает из низкой мощности моделирования. Поэтому исследователи пытались выделить другие подклассы сетей Петри, которые оставляли бы высокой мощность разрешения маркированных графов н увеличивали их мощность моделирования.
7.4.3. Сети Петри со свободным выбором Хэк в своей диссертации на степень магистра в МТИ (107) определил н исследовал один такой подкласс сетей Петри — сети Петри со свободным выбором. Зтот подкласс допускает н конфликты автоматных сетей Петри, и параллельность маркированных графов. но в более ограниченном виде, чем в обычных сетях Петри. Определение 7.3.
Сеть Петри со свободным выбором есть сеть Петри С = (Р, Т,1, Р) — такая, что для всех (~ Е Тн р; е 1((;) либо 1(( ) = (рД, либо Р(р,) = (11). Важность этого определения заключается в том способе, которым оно допускает управляемые конфликты.
Конфликт появляется только тогда, когда одна позиция является входом нескольких переходов. По определению сетей Петри со свободным выбором, если позиция является входом для нескольких переходов (потенциальный конфликт), то она является единственным входом всех этих переходов. Следовательно, либо все этн конфликтующие переходы одновременно являются разрешенными, либо ни один нз них. Зто позволяет свободно осуществлять выбор (разрешенне конфликта) запускаемого перехода, присутствие фишек в других позициях не влияет на выбор запускаемого перехода. Зта ограниченная форма конфликтов была допущена Хэком (107) для доказательства необходимого и достаточного условия того, чтобы маркированная сеть Петри со свободным выбором являлась активной или безопасной. Условие активности связано с маркировками ловушек н тупиков в сети.
Ловушка — зто такое множество позиций, что каждый переход, входом для которого является одна Расширенные и ограниненнае модели сетей Петри 2ОЗ Разрешены Не раэрешееег и 6. Ю. ,м м М ма ьЪ $~~~ь %с $,$ е Рис. 7Л4. диаграмма осушествнмости некоторых структурных конфигура- ций в различных сетях Петри. из позиций множества„имеет выходом другую позицию того же множества. Это означает, что если в какой-либо позиции ловушки имеется фишка, то она будет в одной из позиций ловушки всегда.
Запуск перехода может перемещать фишку между позициями, но удалить фишку из ловушки он не может. Тупик есть такое множество позиций, что каждый переход, который имеет в качестве выхода одну из позиций тупика, использует какую-либо позицию тупика в качестве входа.
Это означает, что если все позиции тупика в какой-то момент станут пустыми, то все зто множество позиций останется пустым всегда. Ни один переход не может помеслить фишку в тупик потому, что в тупике нет фишек, которые сделали бы разрешенным переход, выходом которого служит позиция из тупика. Хзк доказал, что необходимым и достаточным условием активности маркированной сети Петри со свободным выбором является требование того, чтобы каждый тупик содержал ловушку с фишкой Зте Глава 7 Эта теорема основывается на работе Коммонера (53, 1071. Для определения необходимого н достаточного условия безопасности нужно показать, что сеть Петри со свободным выбором покрывается объединением автоматных сетей Петри. Детали этого представлення содержатся в работе П071.
К сожаленню, дальнейшего развития работы по сетям Петри со свободным выбором не цолучнлн, н поэтому свойства сетей Петри со свободным выбором, связанные с досппкнмостью, эквивалентностью, вкточеннем, языками н т. д., рассмотрены не были. ?.4.4. Правильные сети Петри Хэном также был определен другой подкласс сетей Петри, названный правильными сетями Петри (1071. В правильных сетях требуется, чтобы каждый переход имел не более одной входной позицнн, которая совместно используется с другим переходом н поэтому служнт для ограничения возможностей возннкновення конфлнктов. Исследования свойств этого подкласса сетей Петри до снх пор не проводились. У.з. Замечания к литературе Доказательство Патнла (2331 того факта, что РЮ-системы не могут решить всех задач синхронизации, н контрдокззательство Парнаса (2301 весьма кратки н интересны.
Онн привели к доказательству в (159, 7) того, что сети Петри не могут моделировать все без исключения параллельные системы. Этн результаты привели Агервалу к исследованию вопроса о том, что должно прнсутствовать в модели, которая может описывать все системы !4, 51. Главной работой по ограниченным моделям сетей Петри является ранняя работа !128) н работа (541, а также более поздняя!1071.
В некоторых работах продолжено изучение маркированных графов ! 136, 209), но очень мало было сделано по другим моделям. Некоторые обнадеживающне результаты для сетей Петри со свободным выбором, в которых 10(р~)1 = 1, получены в работах (62 н 1611. Задачи достяжнмостя н активности разрешимы для сетей, свобаднык от конфликтов. У.Ь. Темы дпя дапьиеишеге изучения 1. Одно нз предложений по расширению состоит в сопоставлении фишкам информации. Это сопоставление может быть представлено как сеть Петри с окрашенными фишками. Определите модель сетя Петри с окрашенными фншкамн.
Используйте эту растьнренную модель для проверки гнпогез: (а) онн зквнвалентны обычным сетям Петри, (б) онн эквивалентны машинам Тьюринга (допуская про- Расгииренные и ограни«енине надели сетей Петри верку на нуль). Основной задачей будет определение действий пе- рехода с окрашенными фишками. 2. Продолжите исследование свойств «правильных» сетей Петри, сетей Петри, свободных от конфликтов, и сетей Петри со свободным выбором. 3.
Охарактеризуйте класс сетей Петри, которые являются и марки- рованными графами, и автоматными сетями Петри. 4. Каковы свойства класса сетей Петри, переходы которых имеют либо непересекаюшиеся входы (г(с;) й 1(гн) = й), либо идентич- ные ЩГ~) = 1(гн))й Этот класс сетей Петри строго включает сети Петри со свободным выбором„и мы склонны ожидать, что свойства этого нового класса будут очень похожи на свойства сетей со сво- бодным выбором. ГЛАВА й МОДЕЛИ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ Сети Петри определены как модели систем с параллельными действиями. И, как мы видели, сети Петри имеют хорошие возможности моделирования, с их помощью можно моделировать большое число скстем. Однако сети Петри— не единственная модель параллельных вычислений. Предложено, исследуется и используется множество других моделей. В этой главе мы представим некоторые из этих моделей и исследуем их взаимосвязь с сетями Петри.
Целью этой главы является определение моделей, которые могут использоваться в системах моделирования, и нх сравнительной мощности моделирования. Основной задачей, проистекающей нз намерения соотнести различные модели друг с другом, является задача установления соответствующего метода сравнения моделей параллельных вычислений. Ь[ы хотели бы иметь возможность доказывать, что модель А являетсн «менее мощной», чем модель В, нли что модель А «эквивалентна» модели В.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
