Polytech-soft.com

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

Сеть петри это

Сети Петри — математический аппарат для моделирования

Пример сети Петри. Белыми кружками обозначены позиции, полосками — переходы, чёрными кружками — метки.

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

Сети Петри — инструмент моделирования

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

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

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

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

Наилучшими возможностями описания параллельных систем обладают сети Петри. Они не менее мощные, чем MPI, PVM, SDL, UML и другие, но чтобы их выполнять на процессорах необходимо сделать из описания параллельного распределенное.

Динамика сети Петри

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

Пример траектории в сети Петри

Виды сетей Петри

Некоторые виды сетей Петри:

WF-сети используются для проверки графов потоков работ на наличие таких структурных конфликтов, как «тупики» (англ. deadlocks) и «недостатки синхронизации» (англ. lack of synchronization). Структурные конфликты отсутствуют, если WF-сеть является бездефектной.

Свойство бездефектности соответствует двум хорошо известным свойствам сетей Петри — живости и ограниченности.

Анализ сетей Петри

Основными свойствами сети Петри являются:

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

Универсальная сеть Петри

В 1974 году Тилак Аджервала показал, что ингибиторная сеть Петри является универсальной алгоритмической системой. В монографии В. Е. Котова приведен набросок доказательства, указывающий правила кодирования ингибиторной сетью программы счетного автомата Минского. Дж. Питерсон приводит примеры других расширенных классов сетей Петри, являющихся универсальной алгоритмической системой: синхронных и приоритетных. Построенная в явном виде универсальная сеть Петри насчитывала несколько тысяч вершин и недавно была уменьшена до 56 вершин.

Бесконечные сети Петри

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

Читать еще:  Zyxel не видит жесткий диск

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

Сети Петри. Структура и правила выполнения сетей Петри.

Сети Петри Править

Сети Петри — математический аппарат для моделирования динамических дискретных систем. Впервые описаны Карлом Петри в 1962 году.

Пример работы сети Петри

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

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

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

$ Введите сюда формулу $ ==Структура сетей Петри==

Сеть Петри состоит из 4-х элементов:

  • множество позиций P,
  • множество переходов T,
  • входная функция I,
  • выходная функция O.

Пример сети Петри. Белыми кружками обозначены позиции, полосками — переходы, чёрными кружками — метки.

Входная и выходная функции связаны с переходами и позициями. Входная функция I отображает переход tj в множество позиций I(tj) , называемых входными позициями перехода . Выходная функция O отображает переход pi в множество позиций O(pi) , называемых выходными позициями перехода . Структура сети Петри определяется её позициями, переходами, входной и выходной функциями.

Сеть Петри С является четверкой, C=(P,T,I,O). P=1, p2, . pi, pn> — конечное множество позиций, n>=0. T=< t1, t2, . tj, tm > — конечное множество переходов, m>=0. Множество позиций и множество переходов не пересекаются, то есть пересечение P и T равно пустому множеству. I: T->P ¥ является входной функцией — отображением из переходов в комплекты позиций. O: P ¥ ->T есть выходная функция — отображение из комплектов позиций в переходы.

Произвольный элемент P обозначается символом pi , i=1, . n, а произвольный элемент T — символом tj, j=1, . m.

Правила выполнения сетей Петри Править

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

Переход запускается, если он разрешен. Переход называется разрешенным, если каждая из его входных позиций имеет число фишек по крайней мере равное числу дуг из позиции в переход. Фишки во входной позиции, которые разрешают переход, называются его разрешающими фишками. Например, если позиции р1 и р2 служат входами для перехода t1, тогда t1 разрешен, если р1 и р2 имеют хотя бы по одной фишке. Для перехода t3 с входным комплектом позиция р3 должна иметь не менее 3 фишек для разрешения перехода t3.

Определение. Переход $ t_j in T $ маркированной сети Петри $ C = (P, T, I, O, mu) $ с маркировкой $ mu $ , разрешен, если для всех $ p_j in P $ , $ mu (p_i) geq # (p_i, I(t_j)) $ .

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

>Переход t3 I(t3) = и O(t3) = разрешен каждый раз, когда в р2 будет хотя бы одна фишка. Переход t3 запускается удалением одной фишки из позиции р2 и помещением одной фишки в позицию р3 и р4 (его выходы). Переход t4, в котором I(t4) = и O(t4) = запускается удалением по одной фишке из позиций р4 и р5, при этом одна фишка помещается в р5 и две в р6 (рис. 2).

Определение. Переход $ t_j $ в маркированной сети Петри с маркировкой $ mu $ может быть запущен всякий раз, когда он разрешен. В результате запуска разрешенного перехода $ t_j $ образуется новая маркировка $ mu^ <'>$ :

Читать еще:  Контакт контакт vkontakte социальная сеть вход

$ mu^ <'>(p_i) = mu (p_j) — # (p_i, I(t_j) + # (p_i, O(t_j)) $

Сети Петри

Основные соотношения. Для формального описания структуры и взаимодействия параллельных систем и процессов, а также анализа причинно-следственных связей в сложных системах используются сети Петри (англ. Petri Nets), называемые Nсхемами.

Графы специального вида, получившие в дальнейшем название “Сети Петри” были впервые введены Карлом Петри в 60-х годах. В следующем десятилетии начался “бум” разработок в этом направлении. Популярность сетей Петри вызвана удачным представлением различных типов объектов, присутствующих во многих моделируемых системах и “событийным” подходом к моделированию.

Формально N-схема задается четверкой вида

где В – конечное множество символов, называемых позициями, B ¹ O;
D
– конечное множество символов, называемых переходами D ¹ O,
B
Ç D = O; I – входная функция (прямая функция инцидентности)
I: B ´ D ® <0, 1>; О – выходная функция (обратная функция инцидентности),
О: B ´ D ® <0, 1>. Таким образом входная функция I отображает переход dj в множество входных позиций bj Î I(dj), а выходная функция O отображает переход dj в множество выходных позиций bj Î О(dj). Для каждого перехода
dj Î D можно определить множество входных позиций перехода I(dj) и выходных позиций перехода O(dj) как

i = ; j = ; n = | B |, m = | D |.

Аналогично для каждой позиции bi Î B вводятся определения множеств входных переходов позиции I(bi) и выходных переходов
позиции O(bi):

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

Рис. 1. Графическое изображение N-схемы

Пример. Представим формально N-схему, показанную в виде графа на рис. 1:

Входные позиции перехода Выходные позиции перехода

Возможные приложения N-схем. Приведенное представление
N-схемы может использоваться только как отражение статики моделируемой системы (взаимосвязи событий и условий), но не позволяет отразить в модели динамику функционирования моделируемой системы. Для представления динамических свойств объекта вводится функция маркировки (разметки) позиций М: В ® <0, 1, 2, …>. Маркировка М есть присвоение неких абстрактных объектов, называемых метками (фишками), позициям N-схемы, причем количество меток, соответствующее каждой позиции, может меняться. При графическом задании N-схемы разметка отображается помещением внутри вершин позиций соответствующего числа точек (когда количество точек велико, ставят цифры).

Маркированная (размеченная) N-схема может быть описана в виде NМ = .

Функционирование N-схемы отражается путем перехода от разметки к разметке. Начальная разметка обозначается как М: В ® <0, 1, 2, …>.
Смена разметок происходит в результате срабатывания одного из переходов dj Î D сети.

Правило срабатывания перехода

Функционирование многих систем можно описать в терминах состояний системы и изменения ее состояний. При моделировании динамики системы состояние, или маркировка сети Петри, сменяется согласно правилу запуска перехода:

1) переход разрешен, если все входные значения b помечены не менее чем w(b, d) фишками, где w(b, d) — вес дуги от b к d;

2) запуск разрешенного перехода носит случайный характер (в зависимости от наступления или ненаступления соответствующего события.

3) запущенный переход d изымает w(b, d) фишек из каждой своей входной позиции и добавляет w(d, b) фишек в каждую свою выходную позицию. Здесь w(d, b) — вес дуги, ведущей из d в b.

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

Пример. Рассмотрим размеченную N-схему с начальной разметкой M = <1, 0, 0, 0, 1, 0, 1>, которая приведена на рис. 2.8, а. При такой начальной разметке N-схемы единственным готовым к срабатыванию является
переход d2, срабатывание которого ведет к смене разметки на M1, где
M1 = <0, 1, 1, 0, 1, 0, 1>(рис. 2).

Рис.2. Пример функционирования размеченной N-схемы:

а

в

Рис. 2. (Окончание)

При разметке M1 возможно срабатывание переходов d1 d3 и d5. В зависимости от того, какой переход сработал первым, получается одна из трех возможных новых маркировок (рис. 2., в, г, д). Функционирование N-схемы продолжается до тех пор, пока существует хотя бы один возможный переход.

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

Читать еще:  Локальная вычислительная сеть обозначается

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

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

Пример. Требуется описать с помощью сети Петри функционирование системы из предприятий A, В и С. Предприятия А и В поставляют узлы Х1 и X2 соответственно, а на предприя­тии С происходит сборка, в каждый сборочный узел входит один узел X1 и два узла X2. На рис. 2.10 предприятиям А, В и С соответствуют переходы t1, t2 и t3.

Рис. 3. Сеть Петри для примера

Срабатывание перехода t3 происходит только в том случае, если, во-первых, в позиции pl имеется метка, а в позиции р2 не менее двух меток, что означает поступление от предприятии А и В соответствующих комплектующих, и, во-вторых, имеется метка в позиции p4, что означает, что предприятие С закончило сборку предыдущего изделия и готово приступить к сборке следующего. Пока очередное изделие не будет собрано, метки в p4 не будет, следовательно, запросы, пришедшие во входные позиции р1 и р2, вынуждены ожидать срабатывания перехода t4. Переходам t1, t2 и t3 поставлены в соответствие процедуры вычисления задержек срабатывания. Задержки в первых двух переходах равны интервалам времени между появлениями готовых узлов, задержка в t3 равна времени сборки изделия.

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

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

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

Несомненным достоинством сетей Петри является математически строгое описание модели. Это позволяет проводить их анализ с помощью современной вычислительной техники.

Поведенческие свойства сетей Петри

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

Множество всех маркировок, достижимых в сети (N, M0) от М0, обозначается как R(N, M0), или просто R(M0).

Таким образом, проблема достижимости в сетях Петри заключается в том, чтобы при заданной маркировке Мn в сети (N, M0) установить принадлежность Mn к множеству R(M0).

Множество разметок, достижимых в порядке срабатывания сети, представляется разверткой сети.

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

Пример. Следующая сеть (рис. 4а.) определяет управление двумя параллельно протекающими процессами с синхронизацией. Граф достижимости показан на рис. 4в. Граф развертки сети бесконечен (рис 4б), однако после состояния М3 в каждой ветви повторяется один и тот же фрагмент и потому возможно конечное представление графа достижимости (рис. 4в).

Рис. 4. Пример сети Петри (а) с ее графом развертки (б) и графом достижимости (в).

Другое направление исследования функционирования сети Петри связано с изменением количества фишек в конкретной или произвольной позиции в процессе функционирования сети.

Сеть Петри называется К-ограниченной, или просто ограниченной, если для любой маркировки, достижимой от маркировки М0, количество фишек в любой позиции не превышает некоторого числа К, т .е. М(р)

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