Описание параллельных процессов. СЕТИ Петри

Обычные схемы алгоритмов не приспособлены для наглядного описания и представления параллельных процессов. Для решения задач формализации дискретных параллельных процессов были разработаны специальные сетевые модели и, в первую очередь, сети Петри (1960г, C. Petry). Этап алгоритмизации модели реализуется с наибольшим успехом, если модель можно представить достаточно наглядно и формально.

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

Элементы сети Петри:

Вершины:

a) позиции “O” - условное возникновение событий;

b) переходы “|” - сами события.

Дуги - связывающие разнотипные вершины.

Фишки (метки) - объект представления динамического процесса.

Активный переход - в каждой входной позиции есть хотя бы одна фишка.

Разметка сети - это конфигурация расположения фишек в сети.

Аналитическая форма сети Пети представляется в виде вектора:

,

где - множество позиций, - множество переходов,

- множество входов, - множество выходов, M - разметка сети.

Условие срабатывания перехода :

.

Это условие означает, что во всех входных позициях перехода находится хотя бы по одной фишке. Срабатывание перехода изменяет разметку сети следующим образом:

.

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

Пример срабатывания переходов и перемещений фишек приведен на рис.20.

Рис.23. Две фазы состояний сети Петри.

Основные направления анализа сетей Петри:

Проблема достижимости – требуется определить, возникла ли разметка при работе сети при начальной разметке .

Свойство живости – выявление элементов, где не появляются фишки при заданной начальной разметке .

Безопасность сети – исследование возможности появления более одной фишки в позиции для заданной начальной разметки .

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