Newcomposers.ru

IT Мир
0 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Расширенная сеть петри позволяет снять ограничения

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

Сети Петри моделируют широкий класс систем, но для некоторых распространенных специальных классов систем удобно применять сети Петри не общего вида, а некоторые их подклассы или расширения (иерархические сети, раскрашенные сети Петри, сети событий, временные сети событий, КОМБИ-сети, ЕД-диаграммы), более адекватные рассматриваемым системам.

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

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

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

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

Расширенная сеть петри позволяет снять ограничения

На этом шаге мы кратко опишем некоторые модификации сетей Петри.

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

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

Рис.1. Виды расширенных сетей Петри

Рассмотрим подробнее некоторые типы сетей Петри.

Ингибиторная сеть представляет собой сеть Петри, дополненную специальной функцией инцидентности IIN: Р х Т -> , которая вводит ингибиторные (запрещающие) дуги для тех пар (p, t), для которых IIN(Р, Т) = 1. Ингибиторные дуги связывают только позиции с переходами, на рисунках их изображают заканчивающимися не стрелками, а маленькими кружочками.

Переход t в ингибиторных сетях может сработать, если каждая его входная позиция, соединенная с переходом обычной дугой с кратностью w(p, t) содержит не менее w(p, t) фишек, а каждая входная позиция, соединенная с переходом t ингибиторной дугой (ее кратность всегда равна 1), имеет нулевую разметку.

Например, используя ингибиторную дугу, можно промоделировать оператор условного вычитания (если xi<>0, то xi = xi— 1) и получить фрагмент ингибиторной сети (рисунок 2).

Читать еще:  Смартфон не находит сеть

Рис.2. Фрагмент ингибиторной дуги

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

В приоритетных сетях вводят приоритеты срабатывания переходов. Если несколько переходов являются разрешенными, то срабатывает тот из них, который имеет наивысший приоритет. Такие сети используются для моделирования систем на уровне задач.

В структурированных сетях некоторые из переходов являются сложными. При их срабатывании запускается сеть другого уровня иерархии (рисунок 3).

Рис.3. Структурированная сеть Петри

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

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

В цветных сетях вводится понятие цвета для фишек. В общем случае может быть n цветов. В вычислительной технике используются трехцветные сети (n = 3). Такие сети используются для моделирования аппаратных средств.

В сетях с изменяемой структурой кратность ребер не является постоянной.

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

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

Количественными характеристиками являются: время работы некоторого маршрута в программе, время прохождения сигнала в схеме и т. д.

Во временных сетях переходам ставится в соответствие их времена срабатывания, либо позициям ставится в соответствие времена нахождения фишек в позициях.

В стохастических сетях указанные характеристики являются вероятностными, т. е. вводится функция плотности вероятности времен срабатывания переходов или времен нахождения фишек в позициях.

Предикатные сети — это сети с логическим описанием состояния системы.

Со следующего шага мы начнем рассматривать созданное приложение «Редактор сетей Петри» для моделирования систем.

Расширенная сеть петри позволяет снять ограничения

Мы показали, что все предложенные расширения модели сетей Петри допускают возможность проверки позиции на нуль. Насколько это важно по отношению к мощности разрешения сетей Петри? Влияет ли это на возможность анализа сетей Петри?

Проверка на нуль уменьшает мощность разрешения сети Петри. Агервала [4], Хэк [115], Томас [290] и др. показали, что появление способности проверки на нуль у модели сетей Петри позволяет

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

Доказательство эквивалентности расширенных сетей Петри и машин Тьюринга относительно просто. Легче всего его представить в терминах регистровых машин Шепардсона и Стургиса [276] или программных машин Минского [200].

Регистровая машина есть абстрактная модель ЭВМ с несколькими регистрами, которые используются для хранения произвольно больших чисел. Для манипулирования этими регистрами пишется программа. Программа есть последовательность инструкций вида «увеличить регистр на 1», «уменьшить регистр на 1 (только если регистр не равен «перейти к предложению если регистр не равен нулю», и т. д. Ниже представлена программа сложения содержимого регистра 2 с регистром 1.

1. Если регистр 2 равен нулю, то идти к инструкции 5.

2. Вычесть 1 из регистра 2.

3. Прибавить 1 к регистру 1.

4. Идти к инструкции 1.

Шепардсон и Стургис показали, что регистровая машина со следующими инструкциями эквивалентна машине Тьюринга.

1. увеличить регистр на 1.

2. уменьшить регистр на 1 (регистр не равен нулю).

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

Для представления регистровой машины расширенной сетью Петри представим регистров, используемых в программе, позициями Мы также используем позицию для представления положения счетчика инструкций либо перед предложением 1 (начальная маркировка), либо после предложения для В программе из предложений. Каждая инструкция в программе представляется переходом. На рис. 7.12 показано, как каждая из трех вышеприведенных инструкций представляется переходом в расширенной сети Петри. Из этого видно, что регистровая машина может быть преобразована в расширенную сеть Петри, и, следовательно, расширенная сеть Петри эквивалентна машине Тьюринга. Эта эквивалентность машине Тьюринга разрушает все надежды на возможность анализа расширенных сетей Петри. Однако это же доказывает, что расширенные сети Петри могут моделировать любую систему (или по крайней мере любую вычислимую систему). Таким образом, мы видим, что увеличение мощности

Читать еще:  Как войти в сеть в стиме

Рис. 7.12. (см. скан) Преобразование инструкции регистровой машины в переход расширенной сети Петри со сдерживающими дугами. а увеличить содержимое регистра на 1; уменьшить содержимое регистра на 1 (содержимое регистра должно быть положительным); в — переход к инструкции в случае нулевого значения регистра

моделирования в этом случае приводит к определенному уменьшению мощности разрешения.

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

Существуют другие предложения по расширению, которые не поднимают сети Петри до уровня машин Тьюринга. Первыми в качестве расширений были предложены петли и кратные входные и выходные дуги. Но как это было показано в разд. 5.3, такие сети Петри фактически эквивалентны простым сетям Петри. Аналогично добавление входов ИЛИ, выходов ИЛИ, выходов исключающее ИЛИ не увеличило бы мощность моделирования сетями Петри.

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

Расширенная сеть петри позволяет снять ограничения

Расширения Сетей Петри

Раскрашенные (цветные) сети Петри

Появление сетей этого класса связано с концепцией использования различных меток. Ранее все метки предполагались одинаковыми. Механизм функционирования сетей был связан только лишь с количествами меток во входных позициях переходов и определялся общими для всех меток условиями возбуждения переходов и правилами изменения различных позиций при выполнении сети. В цветных сетях каждая метка получает свой цвет. Условия возбуждения и правила срабатывания переходов для меток каждого цвета задаются независимо.[3] Множество используемых при реализации цветных сетей красок выбирается конечным или бесконечным (например, счётным). При моделировании систем цветные сети чаще всего используются для построения компактных формальных и графических представлений, в составе которых имеются однотипные по структуре и характеру функционирования группы объектов. Пример моделирования раскрашенными СП процесса проверки регистрации (рис.5).

Рис.5 Моделирование раскрашенными СП процесса обработки параметров.

Временные Сети Петри

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

Читать еще:  Сервер не видит сеть

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

Пример моделирования дискретно-временными СП процесса запроса таблицы рекордов. (рис.6).

Рис.6 Моделирование дискретно-временными СП процесса запроса таблицы рекордов

Описание инструмента моделирования

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

Сеть Петри есть совокупность четырех элементов: С=P, T, I, O

P — множество позиций P=

T — множество переходов T=

Маркировка — присвоение фишек позициям сети Петри.

Вектор определяет для каждой позиции Рi сети Петри количество фишек в этой позиции. (pi)= i. Маркированная сеть Петри М= есть совокупность структуры сети Петри С=

и маркировки и может быть записана в виде: М=

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

Выполнением сети Петри управляют количество и распределение фишек в сети.

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

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

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

Сети Петри моделируют широкий класс систем, но для некоторых распространенных специальных классов систем удобно применять сети Петри не общего вида, а некоторые их подклассы или расширения (иерархические сети, раскрашенные сети Петри, сети событий, временные сети событий, КОМБИ-сети, ЕД-диаграммы), более адекватные рассматриваемым системам.

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

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

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

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

Ссылка на основную публикацию
Adblock
detector