Лекции по "Информационному технологии"

Лекция. Исследование и анализ проектных решений ИС

 с использованием аппарата сетей Петри

                                                                                   

                                                                                                      Лекция № 9

 

 

 

 

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

 

 

Содержание

(Программные вопросы лекции)

 

1. Формальное определение  и способы представления сетей  Петри 

2. Маркировка сетей  Петри. Условие срабатывания переходов

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

 

Литература

1. [16], с.3-20, 33-44.

Учебно-материальное обеспечение

1.

Организационно-методические указания

Лекция читается для  учебной группы методом устного  изложения учебного материала с отображением рисунков на классной доске.

 

Введение

 

 

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

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

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

 

Учебные вопросы

 

1. Формальное определение и способы представления сетей Петри

Представление системы сетью Петри (СП) основано на двух понятиях: событиях и условиях. События – это действия, имеющие место в системе. Например, в системе производства полетов в а/ч событиями являются "Обеспечить взлет (посадку) ЛА", "Собрать полетную информацию", "Выдать информацию по полетам" и т.д.

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

Условие имеет емкость: 0 – не выполнено; 1 – выполнено; n – условие выполнено  с n-кратным запасом. Условие соответствует  таким ситуациям в моделируемой системе, как наличие данных для выполнения вычислительного процесса, наличие ЛА в зоне выхода к аэродрому посадки и т.п. Сочетания условий разрешают реализоваться некоторому событию, а реализация события изменяет некоторые условия, т.е. события взаимодействуют с условиями, а условия – с событиями.

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

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

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

Выполнение условия изображается разметкой соответствующей позиции, а именно помещением числа n маркеров (фишек) в это место, где n > 0 – емкость позиции.

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

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

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

Формально СП может  быть задана тремя способами:

графически;

аналитически (теоретико-множественное описание);

матрично.

Рассмотрим в общих  чертах первые два способа.

Графическое представление  сетей Петри

Граф G сети Петри есть двудольный ориентированный мультиграф

G = <V, A>,

где: V = {v₁, ... , v_s} – множество вершин,

A = {a₁, ... , a_r} – множество направленных дуг.

Дуга графа инцидентна связываемым вершинам, следовательно,

a_i = (v_j, v_k), v_j, v_kÎV.

"Двудольность" означает, что множество V  состоит из  двух непересекающихся подмножеств P (позиции) и T (переходы) (V = P T  и P T = Æ)  и для любой направленной дуги a_i ÎA,  a_i = (v_j, v_k,) или v_j ÎP, а v_k ÎT, либо  v_j ÎT, а v_kÎP.

Дуги в графе помечаются весами (целыми положительными числами). Дугу с весом k (взвешенный граф) можно  считать эквивалентной k  параллельным  дугам (мультиграф). Указание на единичный вес опускается.

Таким образом, граф G задает структуру "N" сети Петри.

При использовании теоретико-множественного подхода СП формально может быть определена как пятерка вида:

С=(P, T, I, O, m ),                                (1)

где - конечное множество позиций, n³0;

 -  конечное множество переходов, m³0;

- входная функция из переходов в комплекты позиций (позиция p_i является входной перехода t_j, если p_iÎI(t_j));

 - выходная функция из переходов в комплекты позиций (позиция p_i является выходной перехода t_j, если p_iÎO(t_j));

 – маркировка сети (N – множество натуральных чисел);

 – множества позиций и переходов не пересекаются.

 

 

2. Маркировка  сетей Петри. Условие срабатывания  переходов

Маркировка используется для фиксирования состояний СП и осуществляется путем применения одномерного вектора, число компонентов которого равно числу позиций сети n=|P|,  а значение i-го компонента есть натуральное число m(p_i), определяющее количество маркеров (меток) в позиции p_i,

Тогда начальная маркировка M₀ (как и текущая маркировка M, которая соответствует некоторому состоянию сети в текущий момент модельного времени ) имеет вид

M₀={m₀(p1), m₀(p2), ... , m₀(p_i), ... , m₀(p_n)},

где значение m₀(p_i) – целое неотрицательное число (включая "0"), следовательно, k-ая маркировка Mk = {m_k(p_i)}, .

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

Переход  может сработать, если для всех позиций перехода t_j (p_iÎI(t_j)) выполняется условие m (p_i) ³ 1.

Переход, для которого выполняется это условие, называется возбужденным.

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

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

 

 

 

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

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

Совокупность данных свойств составляют:

достижимость;

безопасность;

ограниченность;

активность;

обратимость;

покрываемость;

устойчивость.

1. Достижимость. Запуск  разрешенного перехода в СП приводит к изменению расположения фишек в сети по правилу перехода. При выполнении СП получается последовательность переходов, которая обозначается как m_о(t₁) m₁(t₂) m₂(t₃) m₃... m_n(t_n) или t₁t₂...tn. Последовательности переходов соответствует последовательность маркировок. Маркировка m_n достижима из маркировки m_o, если существует последовательность запусков, приводящих из m_o в m_n. Множество всех маркировок, достижимых в сети – (N, m_o) от m_o, обозначается через R(N, m_o) или R(m_o)  и называется множеством достижимости.

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

2. Безопасность. СП называется безопасной, если число фишек в любой позиции не превышает 1 для любой маркировки принадлежащей к множеству достижимости R(m_o). Позиция СП называется безопасной, если число маркеров в ней не превышает 1 для любой маркировки из R(m_o). В безопасной СП все позиции являются безопасными.

3. Ограниченность. СП называется k-ограниченной (ограниченной), если для любой маркировки, достижимой от m_o, количество фишек в любой позиции не превышает конечного числа k. Позиция СП называется k-ограниченной, если число фишек в ней не превышает конечного числа k для любой маркировки m из R(m_o). Для k-ограниченной СП все позиции k-ограничены.

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

5. Обратимость. СП обратима, если для любой маркировки m из множества достижимости R(m_o) маркировка m достижима из m_o.

6. Покрываемость. Маркировка m в СП (N, m_o) покрываема, если существует маркировка m' из R(m_o) такая, что для любой позиции p сети справедливо соотношение m'(p) не меньше m(p).

7. Устойчивость. СП (N, m_o) называется устойчивой, если для любых двух разрешенных переходов запуск одного из них не приводит к запрещению срабатывания другого перехода.

 

Заключение

 

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

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

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