Внимание!!!
В выложенном на сайте тексте могут быть ошибки,
оригинальную версию методички одним файлом в формате .doc (MS Word)
6.1. Сеть Пэтри - как математическая структура и
ориентированный граф
Для представления и исследования паралельных процессов с отражением механизмов взаимодействия все шире используется язык сетей Пэтри.
Это математический аппарат описания процессов, которые позволяют воспроизводить поведение заявок в системе, использование ресурсов, взаимодействие заявок между собой и заявок с ресурсами.
Удобство сетей Пэтри - этот язык может быть использован на самых различных уровных описания /при моделировании ЭВМ, системный уровень/.
В отличии от марковских цепей в сетях Пэтри отражается специфика реализации взаимодействия и отражается состояние различных ресурсов цепи.
Имеются простые переходы от модели на основе стохастической модели сетей Пэтри к марковской цепи.
ОПРЕДЕЛЕНИЕ 1. Сети Пэтри - математическая структура, представляемая четверкой
СП= {P, T, I, Q},
I - множество позиций сети P={P1...Pn};
T={t1,t2,...tm}- множество переходов в сети, на которых задаются следующие функции:
функции I(tj)представлены I={I(t1), I(t2),..., I(tn) входов-переходов;
Q(tj)- функции выходов-переходов.
Q(tj)= {Q(t1),...,Q(tn)}
Эти функции представляются как некоторые векторы, которые отражают конфигурацию системы и определены на всех позициях сети.
Вектор отображает все позиции сети на входы реакций
P tj ,
- как отображение всех позиций сети на выходы tj переходов.
Сеть Пэтри может быть задана четырьмя множителями, как математическая структура.
ПРИМЕР:
P={P1, P2, P3} T{t1, t2, t3, t4}
I(t1)={P1} Q(t1)={P2}
I(t2)={P2} Q(t2)={P3}
I(t3)={P1, P2} Q(t3)={P1, P3}
I(t4)={P3} Q(t4)={P2, P2}.
Наиболее удобно и наглядно представление сети Пэтри своим графом.
ОПРЕДЕЛЕНИЕ 2. Граф сети Пэтри: /G/= представляет собой двудольный мультиграф, задаваемый парой , где
V - множество вершин графа, разделяемое на два непересекаемые подмножества: P и T;
V=P T; P T=0.
А каждый переход связан с позицией и наоборот.
A - множество дуг равное ={ 1,..., s}, соединяющих переходы с позициями, либо позиции с переходами /P c T/.
G - мультиграф, т.к. одна и та же позиция может быть несколько раз связана с одним и тем же переходом.
Соответствующая позиция обозначается ,
а соответствующий переход - планкой - мгновенный,
- временной.
Рассмотрим граф общей сети Пэтри, которая задана как математическая структура /согласно вышеизложенного примера/.
Позиции, представленные функциями входов I(ti) , являются входными позициями по отношению к переходу ti, а позиции представленные функциями выходов Q(ti) , являются выходными позициями для ti .
Граф сети Пэтри обладает свойством дуальности; соответственно графом сети Пэтри мы можем представить дуальный граф, в котором все позиции заменены переходами и наоборот /P T /.
Тогда I, T будут заданы на множестве переходов относительно позиций: I(Pi), Q(Pi) .
Дуальные графы используются в связи с несколько иной интерпритацией состояния системы
