Сети Петри

Назначение

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

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

Для моделирования таких систем применяются сетевые модели, предложенные в 1962 году Карлом Петри.

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

Кроме того, сети Петри (СП) присутствуют в той или иной мере в моделях, описывающих параллельные вычисления.

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

Компоненты системы и их действия представляются абстрактными событиями: выполнение оператора программы, генерация прерывания и т.д.

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

В теории автоматов события представляются как комбинации символов алфавита.

События в системе представляются как элементарные, т.е. неделимые.

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

Условие имеет емкость:

0 – условие не выполнено;

1 – условие выполнено;

n – условие выполнено с n-кратным запасом.

Определенные состояния условий разрешают реализоваться событию (предусловия события), а реализация события изменяет некоторые условия (постусловия события), т.е. события взаимодействуют с условиями, а условия – с событиями.

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

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

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

Выполнение условия отображается разметкой сети, т.е. помещением в данное место n фишек, где n – емкость условия.

a б в

Примеры сетей Петри

На рис. а изображен последовательный вычислительный процесс.

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

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

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