Сети Петри
-
математический аппарат для моделирования динамических дискретных систем. Описаны в диссертационной работе Карла Петри "Kommunikation mit Automaten" на соискание степени доктора наук в 1962 году.
Сеть Петри представляет собой двудольный ориентированный граф, состоящий из вершин двух типов - позиций и переходов, соединённых между собой дугами. Вершины одного типа не могут быть соединены непосредственно.
В позициях могут размещаться метки (маркеры), способные перемещаться по сети.
Пример сети Петри. Белыми кружками обозначены позиции, полосками — переходы, чёрными кружками — метки.
Событие в сети Петри
-
это срабатывание перехода в сети, при котором метки из входных позиций этого перехода перемещаются в выходные позиции. События происходят мгновенно, либо разновременно, при выполнении некоторых условий.
Сети Петри разрабатывались для моделирования систем с параллельными взаимодействующими компонентами. Сети Петри впервые предложил Карл Адам Петри. В докторской диссертации "Связь с автоматами" он сформулировал основные понятия теории связи асинхронных компонент вычислительной системы.
Сети Петри - инструмент моделирования
В настоящее время сети Петри применяются, в основном, в моделировании. Во многих
областях исследований явление изучается не непосредственно, а
косвенно, через модель. Модель - это представление, как правило, в
математических терминах того, что считается наиболее характерным в
изучаемом объекте или системе. Манипулируя моделью системы, можно
получить новые знания о ней, избегая опасности, дороговизну или
неудобства анализа самой реальной системы. Обычно модели имеют
математическую основу.
Развитие теории сетей Петри проводилось по двум направлениям. Формальная
теория сетей Петри занимается разработкой основных средств,
методов и понятий, необходимых для применения сетей Петри. Прикладная
теория сетей Петри связана главным образом с применением сетей Петри к
моделированию систем, их анализу и получающимся в результате этого
глубоким проникновением в моделируемые системы.
Моделирование в сетях Петри осуществляется на
событийном уровне. Определяются, какие действия происходят в
системе, какие состояние предшествовали этим действиям и
какие состояния примет система после выполнения действия.
Выполнения событийной модели в сетях Петри описывает поведение
системы. Анализ результатов выполнения может сказать о том, в
каких состояниях пребывала или не пребывала система, какие состояния
в принципе не достижимы. Однако, такой анализ не дает числовых
характеристик, определяющих состояние системы. Развитие теории
сетей Петри привело к появлению, так называемых, "цветных" сетей
Петри. Понятие цветности в них тесно связано с понятиями
переменных, типов данных, условий и других конструкций, более
приближенных к языкам программирования. Несмотря на
некоторые сходства между цветными сетями Петри и программами, они еще
не применялись в качестве языка программирования.
Не смотря на описанные выше достоинства сетей
Петри, неудобства применения сетей Петри в качестве языка
программирования заключены в процессе их выполнения в
вычислительной системе. В сетях Петри нет строго понятия процесса,
который можно было бы выполнять на указанном процессоре. Нет также
однозначной последовательности исполнения сети Петри, так как
исходная теория представляет нам язык для описания параллельных процессов.
Наилучшими возможностями описания параллельных систем обладают сети
Петри. Они не менее мощные, чем MPI, PVM, SDL, UML и другие, но чтобы их выполнять на
процессорах необходимо сделать из описания параллельного распределенное.
Сеть Петри первого рода
-
это цветная сеть Петри, описанная на языке предписаний.
Сеть Петри второго рода
-
это сеть, представленная в виде иерархической композиции объектов.
Динамика сети Петри
Процесс функционирования сети Петри может быть наглядно представлен графом достижимых маркировок. Состояние сети однозначно определяется её маркировкой - распределением фишек по позициям. Вершинами графа являются допустимые маркировки сети Петри, дуги помечены символом срабатывающего перехода. Дуга строится для каждого активированного перехода. Построение прекращается, когда мы получаем маркировки, в которых не активирован ни один переход либо маркировки, содержащиеся в графе.
Отметим, что
граф достижимых маркировок
-
представляет собой автомат.
Пример траектории в сети Петри
Виды сетей Петри
Некоторые виды сетей Петри:
Временная сеть Петри
-
такая сеть, где переходы обладают весом, определяющим продолжительность срабатывания (задержку).
Стохастическая сеть Петри
-
сеть, в которой задержки являются случайными величинами.
Функциональная сеть Петри
-
сеть, в которой задержки определяются как функции некоторых аргументов, например, количества меток в каких-либо позициях, состояния некоторых переходов.
Цветная сеть Петри
-
сеть, в которой метки могут быть различных типов, обозначаемых цветами, тип метки может быть использован как аргумент в функциональных сетях.
Ингибиторная сеть Петри
-
сеть, в которой возможны ингибиторные, то есть подавляющие, дуги, запрещающие срабатывания перехода, если во входной позиции, связанной с переходом ингибиторной дугой, находится метка.
Иерархическая сеть Петри
-
сеть, содержащая немгновенные переходы, в которые вложены другие, возможно, также иерархические, сети. Срабатывание такого перехода характеризует выполнение полного жизненного цикла вложенной сети.
WF-сети Петри
-
подкласс сетей Петри, называемый также сетями потоков работ. Формализм WF-сетей введён Вил ван дер Аальстом (англ. Wil van der Aalst) для моделирования потоков работ в workflow-системах.
Сеть Петри PN = (P,T,F) называется сетью потоков работ (WF-сетью), если выполняются следующие условия:
существует только одна исходная позиция i, такая что отсутствуют переходы входящие в i;
существует только одна конечная позиция o, такая что отсутствуют переходы выходящие из o;
каждый узел данной сети расположен на пути от i к о.
WF-сети используются для проверки графов потоков работ на наличие таких
структурных конфликтов, как "тупики" (англ. deadlocks) и "недостатки синхронизации"
(англ. lack of synchronization). Структурные конфликты отсутствуют, если WF-сеть
является бездефектной.
Свойство бездефектности, правильной завершаемости
-
соответствует следующим требованиям:
конечная позиция o достижима при любой последовательности переходов от позиции i;
WF-сеть не содержит лишних позиций (которые никогда не будут выполнены);
при достижении конечной позиции данной сети не должно оставаться фишек в промежуточных позициях.
Свойство бездефектности соответствует двум хорошо известным свойствам сетей
Петри - живости и ограниченности.
Анализ сетей Петри
Основными свойствами сети Петри являются:
ограниченность сети Петри
-
свойство сети, число меток которой в любой позиции сети не может превысить некоторого значения K;
безопасность сети Петри
-
есть частный случай ограниченности, K=1;
сохраняемость сети Петри
-
есть постоянство загрузки ресурсов, когда ΣA_i N_i постоянна. Где N_i - число маркеров в i-той позиции, A_i - весовой коэффициент;
достижимость сети Петри
-
возможность перехода сети из одного заданного состояния (характеризуемого распределением меток) в другое;
живость сети Петри
-
возможность срабатывания любого перехода при функционировании моделируемого объекта.
В основе исследования перечисленных свойств лежит анализ достижимости. Методы анализа свойств сетей Петри основаны на использовании графов достижимых (покрывающих) маркировок, решении уравнения состояний сети и вычислении линейных инвариантов позиций и переходов. Применяются также вспомогательные методы редукции, позволяющие уменьшить размер сети Петри с сохранением ее свойств, и декомпозиции, разделяющие исходную сеть на подсети.
Универсальная сеть Петри
В 1974 году Тилак Аджервала показал, что ингибиторная сеть Петри является универсальной алгоритмической системой. В монографии В. Е. Котова приведен набросок доказательства, указывающий правила кодирования ингибиторной сетью программы счетного автомата Минского. Дж. Питерсон приводит примеры других расширенных классов сетей Петри, являющихся универсальной алгоритмической системой: синхронных и приоритетных. Построенная в явном виде универсальная сеть Петри насчитывала несколько тысяч вершин и недавно была уменьшена до 56 вершин.
Бесконечные сети Петри
Бесконечные сети Петри были введены для верификации вычислительных решеток и позволяют определять свойства сетей Петри для регулярных структур (линейная, древовидная, квадратная, треугольная, шестиугольная и гиперкуб) произвольного размера, полученных путем композиции типовых фрагментов.
Теория сетей Петри является хорошо известным и популярным формализмом,
предназначенным для работы с параллельными и асинхронными системами. Основанная в начале 60-х
годов немецким математиком К. А. Петри, в настоящее время она содержит
большое количество моделей, методов и средств анализа, имеющих
обширное количество приложений практически во всех отраслях
вычислительной техники и даже вне ее.
Знаете ли Вы, что оптимизационная модель - это математическая модель, имеющая форму задачи математического программирования и цель - нахождение некоторого оптимума.
