Теория сетей петри кратко

Обновлено: 28.06.2024

4.1. Особенности сетей Петри и области их применения

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

Можно отметить следующие достоинства аппарата сетей Петри:

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

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

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

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

4.2. Основные определения. Способы задания сетей Петри

Сеть Петри – это двудольный ориентированный мультиграф, все множество X вершин которого разбито на два класса так, что дуги соединяют вершины только из разных классов. Эти классы вершин образуются:

множеством позиций P = < p 1 , p 2 . p n >,

которые обозначаются кружоч-

множеством переходов T = < t 1 , t 2 . t m >,

которые обозначаются планка-

ми —, при этом P È T = X , P I T = Æ .

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

На рис. 4.1 приведено графическое представление сети Петри, в которой

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

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

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

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

Начальная маркировка сети обозначается вектором m 0 = [ m 1 , m 2 . m n ], со-

ставляющие m i = m ( p i ) которого определяют для каждой позиции p i

ство фишек в этой позиции. Таким образом, составляющими вектора m являют-

ся неотрицательные целые числа.

C = ( P , T , F , H , m 0 ), где, кроме

позиций Р и переходов Т , задаются

входная F и выходная Н функции. Через F ( t j ) обозначается множество вход-

ных позиций, а через H ( t j )

позиций перехода t j ;

m 0 – начальная маркировка сети.

Так, например, сеть, изображенная на рис. 4.1, может быть представлена как P = < p 1 , p 2 , p 3 , p 4 >, T = < t 1 , t 2 , t 3 , t 4 >,

Здесь переход t 4

отображен в комплект позиций. Комплект – это обобще-

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

Матричная форма определения сети Петри эквивалентна аналитическому способу задания C = ( P , T , D - , D + , m 0 ). Здесь D – и D + – матрицы входных и выходных инциденций соответственно размером m ´ n , где m – число переходов и n – число позиций.

равен кратности дуг,

входящих в i- й переход из

равен кратности дуг, выходящих из i- ro перехода

во входную очередь

Задание ждет вывода

Для рассматриваемой сети Петри

p 1 p 2 p 3 p 4

t 1 é 1 0 0 0 ù

t 1 é 0 1 0 0 ù

D - = t 2 ê 0 0 1 0 ú

D + = t 2 ê 1 0 0 0 ú .

t 4 ë 0 0 1 1 û

t 4 ë 1 2 0 0 û

Матрица D = D + – D – называется матрицей инцидентности сети Петри,

4.3. Функционирование сетей Петри

Выполнение определенных условий связано с появлением меток в соответствующих этим условиям позициях. Последовательность событий, происходящих в моделируемой системе, отображается срабатыванием переходов. В результате срабатывания одного из переходов t i Î T сети происходит перерас-

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

Необходимое условие срабатывания перехода t i : каждая из его входных позиций должна иметь не меньше фишек, чем число дуг из этой позиции в переход, т. е. " P j Î F ( t i ) : m ( p j ) ³ 1. Переход t i , для которого выполняется данное

условие, называется разрешенным.

В результате срабатывания перехода t i из всякой входной позиции p j перехода t i удаляется столько фишек, сколько дуг ведет из p j в t i , а в каждую выходную позицию p k помещается столько фишек, сколько дуг ведет из t i в p k .

При начальной маркировке μ = [1021] сети Петри на рис. 4.1 разрешен-

ными являются переходы t 1 , t 2 и t 4 . Переход t 3 не разрешен, так как входящая в него дуга из позиции р 2 не подкреплена фишкой (μ 2 = 0). Переходы t 1 , t 2 и t 4 могут сработать в любом порядке, возникающий порядок появления событий не однозначен. Разрешенные переходы не влияют друг на друга.

Срабатывание перехода t 1 приводит к новой маркировке μ' = [0121], перехода t 2 – к маркировке μ' = [2011], перехода t 4 – к маркировке μ' = [2210].

Условие срабатывания перехода t 1 в имеющейся маркировке μ записывает-

ся следующим образом: m T ³ e T [ i ] × D - , i = 1, m ,

где e T [ i ] – вектор-строка, компоненты которого соответствуют переходам и все равны нулю, за исключением i- й, которая равна единице.

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

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

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

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

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

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

==Структура сетей Петри==

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

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

Определение

Сеть Петри С является четверкой, C=(P,T,I,O). P=1, p₂, . p_i, p_n> - конечное множество позиций, n>=0. T=< t₁, t₂, . t_j, t_m > - конечное множество переходов, m>=0. Множество позиций и множество переходов не пересекаются, то есть пересечение P и T равно пустому множеству. I: T->P ¥ является входной функцией - отображением из переходов в комплекты позиций. O: P ¥ ->T есть выходная функция - отображение из комплектов позиций в переходы.

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

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

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

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

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

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

Определение. Переход >" width="" height="" />
в маркированной сети Петри с маркировкой " width="" height="" />
может быть запущен всякий раз, когда он разрешен. В результате запуска разрешенного перехода >" width="" height="" />
образуется новая маркировка :

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

Содержание

История

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

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

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

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

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

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

ограниченность — число меток в любой позиции сети не может превысить некоторого значения K;
безопасность — частный случай ограниченности, K=1;
сохраняемость — постоянство загрузки ресурсов, постоянна. Где — число маркеров в i-той позиции, — весовой коэффициент;
достижимость — возможность перехода сети из одного заданного состояния (характеризуемого распределением меток) в другое;
живость — возможность срабатывания любого перехода при функционировании моделируемого объекта.

В основе исследования перечисленных свойств лежит анализ достижимости.

См. также

Примечания

↑ Джеймс Питерсон Теория сетей Петри и моделирование систем:Пер. с англ.-М.:Мир, 1984.-264с., ил. (стр. 11 "1.3. Зарождение теории сетей Петри")

Ссылки

Wikimedia Foundation . 2010 .

Полезное

Смотреть что такое "Сети Петри" в других словарях:

Петри, Карл Адам — Карл Адам Петри Carl Adam Petri Дата рождения … Википедия

Петри — Фамилия Известные носители: Петри, Бернгард Эдуардович российский и советский антрополог, археолог. Петри, Генри Вильгельм нидерландский скрипач. Петри, Дональд американский киноактёр и кинорежиссёр. Петри, Лаурентиус … … Википедия

Сети I — В Википедии есть статьи о других людях с именем Сети. Сети I XIX династия Новое царство … Википедия

ПЕТРИ СЕТЬ — математическая модель дискретных динамич. систем, в том числе информационных систем (параллельных программ, операционных систем, ЭВМ и их устройств, сетей ЭВМ), ориентированная на качественный анализ и синтез таких систем (обнаружение блокировок … Математическая энциклопедия

WF-сети — WF сети подкласс сетей Петри, называемый также сетями потоков работ. Формализм WF сетей введён Вил ван дер Аальстом (англ. Wil van der Aalst) для моделирования потоков работ в workflow системах. Сеть Петри PN = (P,T,F) называется сетью … Википедия

Асинхронная логика — Содержание 1 Принцип самосинхронности 2 Краткая история … Википедия

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

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

Составитель Кирюшин О.В., доц., канд. техн. наук

Рецензент Новоженин А.Ю., ст. преподаватель

ã Уфимский государственный нефтяной технический университет, 2006

Цель работы

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

Краткие теоретические сведения

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

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

где P = 1, p₂… p_n> – множество всех позиций (n – количество позиций);

Т = 1, t₂… t_m> – множество переходов (m – количество переходов);

G_p_-_t = (p´t), G_t_-_p = (t´p) – множества дуг, ведущих соответственно от переходов к позициям и от позиций к переходам (дуг, соединяющих однородные вершины, не существует);

W = 1, w₂… w_k> – множество весов дуг (k – количество дуг).

Каждая позиция может быть маркирована, т.е. содержать некоторое число маркеров. Если обозначить числа фишек, находящихся в i-й позиции p_i, как m_i, то маркировка всей сети: M = 1, m₂… m_n>. Тогда полное определение сети Петри, включая данные о начальной маркировке, можно записать в виде

где М₀ – начальная маркировка сети.

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

Другими словами, позиция – это имя существительное, а переход – глагол.

Пример. Схема принятия решений при попытке получить деньги из банкомата (см. рисунок 1).

Рисунок 1 – Пример сети Петри

Роль указателей мощности потоков выполняют маркеры (●), также именуемые фишками и метками. Формально маркер – это знак выполнения соответствующего условия. В приведенном примере позиции Р₁ и Р₂ содержат по одному маркеру, что говорит о наличии одной карточки на руках и одного исправного банкомата. В позиции Р₃ маркера пока нет, т.е. банкомат пока не запрашивает код.

При выполнении условий переходы срабатывают, что приводит к перемещению маркеров по сети.

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

Так, при срабатывании перехода t₁ в рассматриваемом примере (банкомат принимает карту и делает запрос кода) изымаются маркеры из позиций Р₁ и Р₂ и помещается один маркер в позицию Р₃. Это символизирует отсутствие карты на руках (она в банкомате) и свободного банкомата (вторую карту в него ввести нельзя), но при этом уже запрошен код.

В случае взвешенной СП количество перемещаемых маркеров соответствует весам дуг. Если во входной позиции маркеров больше, чем вес дуги, то забирается только часть маркеров. Например, при срабатывании перехода t₁₁ (рисунок 2,а) маркировка изменяется соответственно (рисунок 2,б). Видно, что общее число маркеров в сети изменилось.

В сети на рисунке 3 переход не сработает из-за недостатка маркеров в одной из входных позиций.

Рисунок 2 – Срабатывание перехода

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

Таким образом, граф достижимости представляется как

где V – массив вершин (маркировок, соответствующих вершинам):

М_i – i-я маркировка, q – количество маркировок;

Е = 1, e₂ … e_p> – массив дуг, связывающих вершины (р – количество дуг).

Каждая дуга представляется как совокупность e_i = 1, a₂, Т>, где a₁ и a₂ – номера начальной и конечной вершин графа; Т = 1, t₂, … t_k> – массив переходов, соответствующий дуге; k – количество одновременно срабатывающих переходов при переходе от одной маркировки к другой.

Алгоритм построения графа по исходной СП:

2.2 Для каждого разрешенного перехода или комбинации переходов производятся следующие действия:

2.2.1 Определяется маркировка М’, которая образуется при срабатывании данного перехода (комбинации переходов).

2.2.3 Просматриваются все маркировки графа. Если находится маркировка, равная новой, то в массив Е записывается новая дуга, у которой a₁ = a₂ и равны номеру найденной маркировки.

2.2.4 Если в п.п. 2.2 и 2.3 маркировки не найдены, то создается новая вершина графа, в которую записывается новая маркировка, в массив Е записывается дуга, у которой a₁ равна номеру исходной маркировки, a₂ - номеру новой маркировки, Т – набор переходов, срабатывание которых привело к переходу от одной маркировки к другой. Далее определяется массив всех разрешенных переходов и расчет продолжается, начиная с п. 2.2.

Для рассмотренного выше примера СП граф ГД имеет вид (рисунок 4), список маркировок приведен в таблице 1.

(Р₁ Р₂ Р₃ Р₄ Р₅ Р₆ Р₇ Р₈)
М₁	(11000000)
М₂	(00100000)
М₃	(00010000)
М₄	(00000100)
М₅	(00000001)
М₆	(00001000)
М₇	(00000010)

С помощью ГД могут быть определены свойства СП и, в конечном счете, моделируемой системы. К ним относятся:

- живость (отсутствие тупиковых состояний);

- правильность (если сеть безопасная и живая, то она правильная);

- обратимость (сеть обратима, если в графе имеется хотя бы одна дуга, направленная к начальной маркировке М₀);

- пассивность переходов (переход t_i пассивен, если он не соответствует ни одной дуге графа);

- число возможных состояний N_сост.

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

Любая система должна представляться правильной сетью.

Для рассмотренного примера можно сделать вывод, что сеть правильная, обратимая и без пассивных переходов.

Практическое значение и наиболее ясную интерпретацию имеют два вида СП:

1) маркированные графы – каждая позиция такой СП должна иметь не более одного входного и одного выходного перехода;

2) автоматные сети (А-сети) – каждый переход такой СП должен иметь не более одной входной и одной выходной позиции.

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

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

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

1.1. Моделирование

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

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

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

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

1.2. Природа систем

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

Действиям компонент системы присущи совмещенность или параллелизм. Действия одной компоненты системы могут производиться одновременно с действиями других компонент. В

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

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

1.3. Зарождение теории сетей Петри

Работа Петри привлекла также внимание группы, работающей над Проектом MAC в Массачусетском технологическом институте (МТИ). Руководимая профессором Дж. Б. Деннисом группа вычислительных структур стала источником значительных исследований и публикаций по сетям Петри, были написаны несколько Диссертаций на степень доктора философии и множество отчетов и меморандумов (см. библиографию). Группой вычислительных структур были проведены две большие конференции по сетям Петри: Конференция Проекта MAC по параллельным системам и

параллельным вычислениям в 1970 г. в Вудс Холле [73] и Конференция по сетям Петри и связанным с ними методам в 1975 г. в МТИ. Обе эти конференции внесли вклад в распространение результатов и методов теории сетей Петри.

За последние несколько лет использование и изучение сетей Петри значительно расширились. В 1977 г. в Париже и в 1979 г. в Гамбурге на лекциях по общей теории сетей проводились заседания рабочей группы по сетям Петри. В ФРГ была образована группа интереса по сетям Петри. Исследования и применения сетей Петри расширяют сферу действия.

1.4. Применение теории сетей Петри

Возможно несколько путей практического применения сетей Петри при проектировании и анализе систем. В одном из подходов сети Петри рассматриваются как вспомогательный инструмент анализа. Здесь для построения системы используются общепринятые методы проектирования. Затем построенная система моделируется сетью Петри, и модель анализируется. Любые трудности, встречающиеся при анализе, указывают на изъяны в проекте. Для их исправления необходимо модифицировать проект. Модифицированный проект затем снова моделируется и анализируется. Этот цикл повторяется до тех пор, пока проводимый анализ не приведет к успеху. Такой подход иллюстрируется на рис. 1.1. Заметим, что его можно использовать и для анализа уже существующих действующих в настоящее время систем.

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

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

Рис. 1.1. Использование сетей Петри для моделирования и анализа систем. Сначала система моделируется сетью Петри, затем модель анализируется. Оценка системы, являющаяся результатом анализа, приведет, как ожидается, к лучшей системе. Необходимы исследования, направленные на разработку автоматических методов моделирования и анализа систем сетями Петри.

1.5. Прикладная и чистая теории сетей Петри

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

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

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

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

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

Представленный в книге подход во многом основан на работе группы вычислительных структур МТИ и работах Денниса [72], Патила [231] и др., кончая работой Хэка [113]. Насодержание книги также оказал влияние Келлер — своим отчетом по системам замещения векторов [150] и своей точкой зрения на моделирование [152].

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

Читайте также: