Сети Петри

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

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

Сети Петри функционируют в непрерывном времени. Динамика функционирования определяется правилами срабатывания переходов. Изменение состояния сети связано с механизмом изменения маркировок позиций. В случае простой временной сети Петри:

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

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

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

ПРИМЕР смены маркировок простой сети Петри при разрешении конфликта.

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

Элементарный цикл обслуживания моделируется простой временной сетью Петри, представленной на рис. 16.

С переходами на рис. 16 связаны времена выполнения следующих действий: t₁ –поступление заявки на обслуживание во входную очередь; t₂ – начало обслуживания; t₃ – конец обслуживания; t₄ –выход заявки из цикла обслуживания. Позиции этой сети Петри соответствуют условиям: Р₁ – наличие заявки, ожидающей обслуживания, во входной очереди; Р₂ – наличие заявки на обслуживании в процессоре; Р₃ – процессор свободен; Р₄ – наличие обслуженной заявки в выходной очереди. Маркировка сети Петри, показанной на рис. 16, соответствует начальному состоянию системы обслуживания: заявок, ожидающих обслуживание, во входной очереди нет, и процессор свободен (вершина P₃ содержит метку).

Другая маркировка сети Петри, моделирующей элементарный цикл обслуживания, показана на рис. 17.

Маркировка, показанная на рис. 17, соответствует следующему состоянию: заявка ожидает обслуживания и процессор свободен: вершины Р₁ и P₃ содержат метки, и, следовательно, переход t₂ активизирован. Моделирование дальнейших событий в пошаговом режиме показано на рис. 18.

После срабатывания перехода t₂ метки из его входных вершин Р₁ и P₃ будут изъяты, а в выходной вершине Р₂ метка появиться, что соответствует наличию заявки на обслуживание в процессоре. Метка в вершине Р₂ активизирует переход t₃, который сработает по истечению времени обслуживания. В результате срабатывания перехода t₃ метка изымается из вершины Р₂, а в вершинах Р₄ и P₃ метки появляются. Срабатывание перехода t₄, соответствующее удалению обслуженной заявки из цикла, изымет метку из вершины Р₄, и система вернется к начальной маркировке (см. рис. 16).

В общем случае в позиции может быть более одной метки. Тогда, для срабатывания перехода вида n/m требуется наличие во входных позициях суммарного количества меток не менее n. При срабатывании перехода из всех входных позиций по числу исходящих дуг удаляются в сумме n меток, а во всех выходных позициях по числу выходных дуг появляются m меток (см. рис. 19).

Для удобства в графическом представлении сетей Петри и в программном обеспечении моделирования, как правило, при задании переходов типа n/m вместо множественных дуг используют одну, задавая ее вес. Также из соображений удобства количество меток в вершине более 2-х можно указывать числом вместо множества меток. В таком представлении пример, приведенный на рис. 19, будет иметь вид, показанный на рис. 20.

Переходы типа n/m используются для моделирования процессов, сопровождаемых изменением типа моделируемого ресурса. Например, для моделирования процессов сборки в технологической системе, процессов пакетирования заявок в вычислительной сети (в этом случае n>m) или процесса разделения материальных потоков, процесса создания копий заявок (в этом случае n<m).

ПРИМЕРЫ сетей Петри для моделирования процесса пакетирования заявок и синхронного моделирования элемента И-НЕ.

Для моделирования средств вычислительной техники и процессов обработки информации используются разновидности сетей Петри, различающиеся способами разрешения конфликтов. В стохастических сетях Петри дополнительно вводятся случайные задержки или вероятности срабатывания активных переходов. В примере на рис. 21-а сработает либо переход t₁ (c вероятностью р₁), либо t₂ (c вероятностью 1-р₁). В приоритетных сетях конфликтные ситуации разрешаются введением различных приоритетов для ветвей. Конфликт, показанный в примере на рис. 21-б, всегда будет разрешаться в пользу перехода t₁, так как он имеет приоритет, а переход t₂ сможет сработать только в том случае, если, при наличии меток в вершинах Р₂ и Р₃, метки в вершине Р₁ не окажется.

Особой разновидностью сетей Петри являются ингибиторные сети, которые в дополнение к обычным дугам (ветвям) графа сети содержат запрещающие, так называемые ингибиторные ветви. Такая ветвь запрещает активацию перехода при наличии достаточного количества меток во входных вершинах обычных дуг до тех пор, пока в ее входной вершине имеются метки. Во фрагменте сети Петри, приведенном на рис.22-а, ветвь а запрещает запуск перехода t₁ при наличии метки в позиции P₁. Пример реализации простейшего цикла обслуживания с использованием ингибиторной сети Петри представлен на рис.22-б. Здесь переход t₂ при наличии метки в позиции Р₂ будет «заперт» не смотря на наличии метки в вершине Р₁ до тех пор, пока метка не покинет Р₂ через переход t₃, что эквивалентно завершению очередного обслуживания.

Рассмотрим примеры моделирования сетями Петри различных процессов и систем.

Сеть Петри для моделирования магистрального канала передачи данных. Пусть к общему каналу связи подключены N абонентов и возможна связь любых абонентов друг с другом. Абонент-отправитель осуществляет попытку связи в случайный момент времени Т₁. Если канал занят передачей информации от другого абонента, это обнаруживается по наличию сигналов несущей частоты в канале связи. Абонент задерживает передачу на время t₁, являющееся реализацией равномерно распределенной в заданном диапазоне случайной величины t. Если в момент времени (Т₁+t₁) канал связи опять занят, то передача задерживается по тому же правилу. Если два абонента или более пытаются начать передачу одновременно, возможны конфликты. Одновременность описывается условием DТ<e, где DТ – промежуток времени между моментами начала передачи данных различными абонентами, e>0. При конфликте передача начинается, но передаются искаженные данные. Ликвидация конфликта заключается в том, что все абоненты, начавшие одновременно передачу данных, прекращают ее и пытаются начать работу через промежуток времени, индивидуальный для каждого абонента и являющийся функцией t.

В модельной реализации (см. рис. 23) источник (открытый переход t₂) имитирует поток заявок на передачу от всех абонентов. Если канал свободен и конфликта нет, заявка проходит через t₃, t₆, t₇, t₁₀, t₁₁ и выходит из системы обслуженной, причем в t₆ происходит задержка на время e, а в t₁₀ - на время (Т_п-e), где Т_п – время передачи пакета.

Если канал занят (заявка задержана в t₁₀), то попытка другого абонента начать передачу приводит к прохождению заявки по маршруту t₃, t₆, t₉, и далее в один из переходов t₁₂..t_n. Срабатывание перехода t₉, а не t₇, происходит потому, что предыдущая заявка, прошедшая через t₇ и еще не вышедшая из t₁₀, изъяла метку из позиции р₉. Тем самым переход t₇ оказался запрещенным, а t₉ разрешенным.

Переходы t₁₂...t_n моделируют задержку пакетов на время t_i. Через время t_i заявка переходит к р₃, т. е. предпринимается новая попытка передачи сообщения. Конфликты возникают, если новая заявка приходит в позицию р₃, когда предыдущая еще не покинула переход t₆. Поэтому метка не может пройти переход t₃, но может пройти через переход t₄ в позицию р₆. Теперь вышедшая из t₆ заявка сможет пройти через t₈ на переходы t₁₂...t_n, где обе заявки будут задержаны на случайные отрезки времени перед повторными попытками передачи. Чтобы метка из р₈ перешла в t₈, а не в t₉, ветви, ведущей в t₈, присваивается более высокий приоритет. Переход t₅ срабатывает в случае, если в конфликт вошло более двух заявок [3, 20-23].

ПРИМЕРЫ сетей Петри различных систем и процессов и их реализации в программе IngProject – см. Лабораторную работу №7

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

При функционировании данной системы могут иметь место следующие ситуации:

- все три рабочих блока исправны, запасной и резервный блоки готовы к использованию;

- один из рабочих блоков отказал и запасной готов к использованию (в этом случае будет произведена замена и отказавший блок будет отправлен на восстановление для последующей передачи в запас);

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

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

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

- если резервный блок уже восстановлен, то очередной отказавший блок будет отправлен на восстановление и, далее, в запас.

Заданную систему моделирует ингибиторная приоритетная сеть Петри, представленная на рис. 24.

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

Таблица 10

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

ПРИМЕР сети Петри для моделирования процессов возникновения отказов и устранения неисправностей в технологической системе с дополнительным резервом (второй вариант).

Таблица 11