Задания к лабораторной работе

Использование сетей Петри при моделировании событий в информационных системах

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

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

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

 

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

 

 

 

 

Рис. 1

Смысл позиций: Р₁ – карта (ее наличие); Р₂ –банкомат исправен и свободен; Р₃ – введенный код; Р₄ – код набран правильно, запрашивается сумма; Р₅ – код набран неправильно; Р₆ – сумма доступна; Р₇ – сумма недоступна (нет такого количества денег на карте); Р₈ – деньги (получены). Смысл переходов: t₁ – банкомат принимает карту и делает запрос в банк, t₂ - ввод кода; t₂ – запрос суммы; t₃ – повторный ввод кода; t₅ – выдача сообщения о недоступности суммы; t₆ – выдача денег; t₇ – повторный набор суммы; t₈ – забрать карту из банкомата (другой исход: имеется другая карта, с которой также нужно снять деньги – см. дуги, обозначенные пунктиром); t₉ – выдача сообщения, что код неверный.

То есть, банкомат сможет принять карту только в том случае (переход t₁), если на руках имеется карта (позиция Р₁ символизирует ее наличие) и банкомат исправен (позиция Р₂). Если эти два условия выполняются, то банкомат принимает карту и просит ввести код (результат действия – введенный код, символизируемый позицией Р₃). Далее возможны два варианта развития событий: код оказывается правильным (в этом случае выполняется действие t₂ - запрос суммы) ИЛИ неправильным (в этом случае выполняется действие t₉ - выдается сообщение об ошибке). И так далее.

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

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

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

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

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

 

Таблица 1

	(Р1 Р2 Р3 Р4 Р5 Р6 Р7 Р8)
М1	(11000000)
М2	(00100000)
М3	(00010000)
М4	(00000100)
М5	(00000001)
М6	(00001000)
М7	(00000010)

 

 

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

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

- ограниченность (сеть ограниченна, если ни в одной вершине графа скапливается не больше маркеров, чем их число в начальной позиции);

- безопасность (сеть безопасна, если в метки вершин входят только «0» и «1», что означает отсутствие зацикливаний);

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

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

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

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

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

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

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

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

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

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

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

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

Задания к лабораторной работе

Даны описания действий, которые выполняются в некоторой системе (варианты заданий выдаются преподавателем).

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

Программным обеспечением лабораторной работы является программа PetriNetWork.

Поделиться:

Воспользуйтесь поиском по сайту: