Сети Петри.Введение

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

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

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

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

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

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

· в большой системе приходится учитывать состояние всех компонентов при каждой смене ее общего состояния, что делает модель громоздкой;

· при таком подходе исчезает информация о причинно-следственных связях между событиями в системе; такие понятия, как конфликты между компонентами системы (из-за ресурсов) или ожидание одним из компонентов результатов работы других компонентов, трудно выражаются в терминах смены состояний системы;

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

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

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

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

Условие имеет емкость: 0 - не выполнено;

1 - выполнено;

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

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

Таким образом, предполагается, что для решения задач достаточно представить системы как структуры, образованные из элементов двух типов - событий и условий.

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

Выполнение условия изображается разметкой соответствующей позиции, а именно помещением числа n или n

маркеров (фишек) в это место, где n >0 - емкость условия.

Динамика поведения моделируемой системы находит свое отражение в функционировании сети Петри. Неформально работу сети можно представить как совокупность локальных действий, которые называются срабатываниями переходов. Они соответствуют реализациям событий и приводят к изменению разметки позиций, т.е. к локальному изменению условий в системе.

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

Таким образом, сети Петри формализуют понятие абстрактной асинхронной системы - динамической структуры из событий и условий.