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

Выполнение сетей петри

ЦЕЛЬ РАБОТЫ

15.1.1 Ознакомиться с теоретическими сведениями.

15.1.2 Получить практические навыки по выполнению сетей Петри.

МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ

15.2.1 Методические указания по выполнению практической работы.

ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ

15.3.1 Изучить методические указания к практической работе.

15.3.2 В соответствии с полученным вариантом выполните сеть Петри.

15.3.3 В соответствии с полученным вариантом описать свойства сети Петри

СОДЕРЖАНИЕ ОТЧЕТА

15.4.1 Цель работы

15.4.2 Методические рекомендации

15.4.3 Порядок выполнения работы

15.4.4 Ответы на контрольные вопросы

15.4.5 Выводы

КОНТРОЛЬНЫЕ ВОПРОСЫ

15.5.1 Что называется сетью Петри?

15.5.2 Назовите статистические свойства сети Петри?

15.5.3 Назовите динамические свойства сети Петри?

15.5.4 Что называется маркировкой сети Петри?

15.5.5 Какой переход маркированной сети Петри называется разрешенным?

ПРИЛОЖЕНИЕ 1

ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

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

Формализм сетей Петри общего вида основан на понятии комплекта, являющемся в некотором роде обобщением понятия множества. Как и множество, комплект – это набор элементов, но всякий элемент и множества, заменяются на функцию числа экземпляров элемента в комплекте, которая обозначается как #(x, B) (читается: «число х в комплекте В»). Множество – частный случай комплекта.

Многие понятия теорий множества распространяются и на комплект. Так, пустой комплект аналогичен пустому множеству. Мощность комплекта есть общее число экземпляров элементов в комплекте. Комплект А включен в комплект В (является под комплектом), если для всякого x#(x, A)£#(x, B). С помощью функции # легко определяются операции над комплектами: для объединения комплектов А и В #(x, AÈB) = max (#(x, A), #(x, B)); для пересечения комплектов А и В #(x, AÇB) = min (#(x, A), #(x, B)); для сумм комплектов А и В #(x, A+B) = #(x, A)+#(x, B); для разности комплектов А и В #(x, A-B) = #(x, A)-#(x, AÇB). Если М – множество, то M¢¢ - множество всех комплектов, построенных из элементов М, что #(x, B)£n, BÎMⁿ; M^¥ - множество всех комплектов, построенных из элементов М без ограничения на число экземпляров элемента в комплекте.

Сети Петри – это четверка C=(P, T, I, O), где З – конечное множество позиций, Т – конечное множество переходов, I: Т®Р^¥ - входная функция, отображающая переходы в комплекты позиций, О: Т®Р^¥ - выходная функция, отображающая переходы в комплекты позиций. Графически сеть Петри изображаются в виде мультиграфа с вершинами двух видов: кружки соответствуют позициям, планки – переходам. Функции I и О представляются дугами (рис.1).

Позиции, дуги из которых ведут в переход t_j, называются выходными для t_j; аналогично, позиции, в которые ведут дуги из перехода t_j, называются выходными для t_j. Множество входных позиций обозначают I(t_j), а выходные – O(t_j). В сети Петри, изображенной на рис.1, I(t₁)={p₁, p₁, p₁}, O(t₁)={p₃, p₄, p₄}. Функции I и О удобно обобщить на отображение из позиций в комплекты переходов (Р®Т^¥), что позволяет обозначать множества входных и выходных переходов позиции p_i, определяемые аналогично множествам входных и выходных позиций перехода, соответственно как I(p_i) и O(p_i). В сети Петри, изображенной на рис. 1, I(p₃)={t₁, t₂}, O(p₃)={t₂, t₄}.

Введенные понятия относятся к статистической структуре сети Петри. Динамические свойства сети Петри определяются с помощью понятия маркировки. Маркировка m сети Петри C=(P, T, I, O) – это функция, отображающая множество позиций Р в множестве неотрицательных чисел N. Маркировка изображается с помощью помещаемых внутрь позиций фишек (точек). Так, маркировка сети Петри, приведенной на рис. 1, определяется как m(p₁)= m(p₃)= 1, m(p₂)= m(p₄)= m(p₅)=0.

Удобно представлять маркировку как n-вектор m=(m₁, m₂, …,m_n) (где n=|P|), каждый элемент которого m_i есть m(p_i), а также как комплект m, в который входят позиции сети p_iÎP и #(p_i, m) = m(p_i). Сеть Петри С с определенной в ней маркировкой m называется маркированной сетью Петри.

Рассмотрим выполнение сети Петри, изображенной на рис. 1. В начальной маркировке разрешен только переход t₂. При его запуске фишка удалится из р₃, а затем в позиции р₂ и р₃ добавится по фишке, т.е. в результате запуска в новой маркировке m¢ появится фишка еще в р₂. Теперь становится разрешенным переходы t₂, t₄. Поскольку запуститься может любой разрешенный переход, предположим, что запускается переход t₄. После его запуска из позиции р₂ и р₃ фишки удаляются, а в позиции р₅ появится одна фишка. В получившейся маркировке m² не разрешен ни один переход. На этом выполнение сети Петри заканчивается.