Общие сведения о сетях Петри

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

Причинно-следственная связь событий в асинхронных системах задается множеством отношений вида "условия-события".

Построение моделей систем в виде сетей Петри заключается в следующем:

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

2. Определяются события-действия, последовательность выполнения которых управляется состояниями системы. Состояния системы задаются множеством условий, формируемых в виде предикатов. Количественно условия характеризуются величиной которая выражается числами натурального ряда.

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

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

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

а) б)

Рис 1. а) − изображение позиции; б) − изображение перехода.

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

Рис.2. Пример графа сети Петри.

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

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

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

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

а) б)

Рис.3, а − возбужденный переход, б) − невозбужденный переход.

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

Для более глубокого понимания существа использования аппарата сетей Петри при описании совместной работы совокупности параллельных взаимодействующих процессов рассмотрим основные типы взаимодействия и синхронизации процессов. Взаимодействие процессов требует распределения ресурсов между ними. Чтобы система работала правильно распределением ресурсов необходимо управлять. Это управление в основном сводится к задачам синхронизации взаимодействия процессов. При этом изучается ряд задач синхронизации ставших классическими:

- задача о взаимном исключении;

- задача о производителе/потребителе;

- задача об обедающих мудрецах;

- задача о чтении/записи;

- - и - операции над семафорами.

Другие механизмы синхронизации процессов включают решение перечисленных задач. Знание этих задач и приобретение навыков их применения позволяет успешно справляться с весьма не простым делом описания функционирования систем сетями Петри.