Применение сетевых моделей для описания параллельных процессов.

Сети Петри. В середине 60-х годов прошлого века, он предложил новый тип сетей. Они представляют собой математическую модель, для представления структуры и анализы динамики функционирования систем в терминах условие – событие. Модель нашла широкое применение для описания динамических дискретных систем различной природы. Сети Петри, и их обобщения являются удобным и мощным средством моделирования асинхронных, параллельных распределенных процессов. К настоящему времени имеет большое количество разновидностей сетей Петри. Одно из достоинств сетей Петри, это то что они могут представленные как в графической форме, что обеспечит наглядность, так и в аналитической, что позволяет автоматизировать процесс анализа. Графические сети Петри, изображаются в виде своеобразного графа, который состоит из вершин двух типов, позиций и переходов, соединенных ориентированными дугами. Причем каждая дуга, может связывать лишь разнотипные вершины. Переходы соответствуют событиям имеющимся в моделируемой системе, а позиции условия их возникновения. Таким образом, сеть Петри позволяет описать причинно-следственную связь имеющиеся в системе, но в статике. Что бы отразить динамку, добавляется ещё один вид объектов сети, так называемые метки. Считается, что переход активен ( событие может произойти) если в каждой его входной позиции, есть хотя бы одна метка. Расположение меток в позициях сети, называется разметкой сети.

Лекция 9. 8.04.11

Формальное представление сети Петри.

C=(P,T,I,O,M)

P- конечное не пустое множество позиций.

T – конечное непустое множество переходов.

I – входная функция переходов .

I : P * T -> (0,1) – входная функция переходов, которая для непустого перехода дает множество его входных позиций.

O : T * P -> (0,1) – Выходная функция (обработанная функция), которая для непустого перехода задает множество его выходных позиций.

M : P -> (0,1,2,3…) – Разметка сети ставит в соответствие каждую позицию сети целое неотрицательное число, равное числу меток в данной позиции.

Правило изменения разметки сети.

M_i (T) = M_i-1 (T) – I(t_i) + O(t_i)

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

Матрица входных позиций.

1	1	0	0
0	1	0	0
0	0	1	0
0	0	1	1
0	0	0	0

I =

Матрица выходных позиций.

0	0	1	0	0
0	0	0	1	0
0	0	1	0	0
0	0	0	0	1

O =

(Матрицы составлены для графа Петри).

Задачи достижимости:

Проблема достижимости.

1. Можно ли в сети с начальной разметкой M₀ получить разметку M_i (математически).

Может ли система переходить в лекот.состояние M_i находиться в состояние M₀? (физически).

2. Оценка активности переходов, возможность срабатывать перехода t₃ при наличии разметки t₀.

3. Оценка безопасности сети. Безопасной является такая сеть Петри, у которой не при каких условиях не может появится более 1 метки в каждой из позиций. Недостаток сетей Петри : при моделировании с помощью таких сетей время срабатывания перехода = O . Это позволяет исследовать…

При имитационном моделирование используют расширения сетей Петри :

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

2. Метки могут считать набором атрибутов.

3. Используются дополнительные виды вершин переходов.

4. В любую позицию может входить не более 1 дуги и выходить также не более 1 дуги.

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

Ни одна из вершин, позиций сети не может иметь более 1 метки.