что такое сети петри

Сети Петри. Структура и правила выполнения сетей Петри.

Сети Петри [ ]

Сети Петри — математический аппарат для моделирования динамических дискретных систем. Впервые описаны Карлом Петри в 1962 году.

Пример работы сети Петри

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

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

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

==Структура сетей Петри==

Сеть Петри состоит из 4-х элементов:

Пример сети Петри. Белыми кружками обозначены позиции, полосками — переходы, чёрными кружками — метки.

Правила выполнения сетей Петри [ ]

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

Переход запускается, если он разрешен. Переход называется разрешенным, если каждая из его входных позиций имеет число фишек по крайней мере равное числу дуг из позиции в переход. Фишки во входной позиции, которые разрешают переход, называются его разрешающими фишками. Например, если позиции р1 и р2 служат входами для перехода t1, тогда t1 разрешен, если р1 и р2 имеют хотя бы по одной фишке. Для перехода t3 с входным комплектом позиция р3 должна иметь не менее 3 фишек для разрешения перехода t3.

Определение. Переход маркированной сети Петри с маркировкой , разрешен, если для всех , .

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

>Переход t3 I(t3) = и O(t3) = разрешен каждый раз, когда в р2 будет хотя бы одна фишка. Переход t3 запускается удалением одной фишки из позиции р2 и помещением одной фишки в позицию р3 и р4 (его выходы). Переход t4, в котором I(t4) = и O(t4) = запускается удалением по одной фишке из позиций р4 и р5, при этом одна фишка помещается в р5 и две в р6 (рис. 2).

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

Источник

Вложенные сети Петри и моделирование распределенных систем

Теоретические основы сетей Петри: принципы построения, алгоритмы поведения.

Сети Петри были разработаны и используются для моделирования систем, которые содержат взаимодействующие параллельные компоненты, например аппаратное и программное обеспечение ЭВМ, гибкие производственные системы, а также социальные и биологические системы. Впервые сети Петри предложил Карл Адам Петри в своей докторской диссертации «Связь автоматов» в 1962 году.

2. Сети Петри для моделирования систем: способы реализации.

2.1 События и условия.

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

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

3. Условия (предикаты) могут быть выполнены или не выполнены. Только выполнение условий обеспечивает возможность наступления событий (предусловия).

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

1. заготовка поступила;

2. автомат начинает обработку;

3. автомат заканчивает обработку;

4. деталь посылается в накопитель.

Условиями для системы являются:

2. заготовка загружена;

3. автомат выполняет обработку;

4. деталь обработана.

Сеть Петри рассматриваемого автомата имеет вид (рис.8)

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

2.2 Одновременность и конфликт.

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

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

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

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

Если в какой либо момент времени разрешено более одного перехода, то любой из них может стать “следующим”. Выбор запускаемого перехода осуществляется недетерминированным образом, то есть случайно и зависит от воли моделирующего систему. Недетерминорованность и неодновременность запусков переходов в моделировании паралельной системы показывается двумя способами. В одной ситуации два разрешённых перехода t_j и t_k не влияют друг на друга. В число возможных последовательностей событий входит последовательность, в которой первым срабатывает один переход и последовательность в которой первым срабатывает другой переход. Эти два перехода могут быть запущены в любом порядке, это называется недетерминированностью и неодновременностью, переход t_k может быть запущен в любом порядке, но обязательно при помощи маркеров в обеих позициях. Это называется одновременностью. Другая ситуация, в которой одновременное выполнение затруднено и которая характеризуется невозможностью одновременного запуска. Здесь переходы t_j и t_k находятся в конфликте, так как запуск одного из них удаляет маркёр из p_i и тем самым завершает другой переход. Эта ситуация называется конфликтом и в моделируемых системах отображает борьбу за общие ресурсы.

Существуют определённые области, в которых сети Петри являются идеальным инструментом для моделирования: это области, в которых события происходят синхронно и независимо. Одной из таких областей является использование сетей Петри для моделирования аппаратного и програмного обеспечения ЭВМ и других систем.

1. ‘ Моделирование распределенных автоматизированных систем и информационных сетей

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

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

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

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

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

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

В этом случае можно записать: эндогенные переменные: Т₀—среднее время обслуживания сообщений; Р_от — вероят ность отказа в обслуживании; экзогенные переменные: — инте нсивность входного потока сообщений; h — производительность абонентской ЭВМ; H — суммарная производительность главных ЭВМ сети; В — пропускная способность селекторных каналов ЭВМ; С — пропускная способность магистрального канала связи.

Источник

Сети Петри

6.1. Основные определения

Сети Петри (СП) и их многочисленные модификации являются одним из классов моделей, неоспоримым достоинством которых является возможность адекватного представления не только структуры сложных организационно-технологических систем и комплексов, но также и логико-временных особенностей процессов их функционирования. Сети Петри представляют собой математическую модель для представления структуры и анализа динамики функционирования систем в терминах «условие-событие». Это модель может быть успешно использована для описания так называемых динамических дискретных систем различных классов, таких как: вычислительные процессы и программы, технологические процессы, информационные, экономические, биологические, социальные и технические системы.

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

Позиция рi является входной позицией перехода tjв том случае, если piÎ I(tj); piявляется выходной позицией, если рiÎ O(tj). Входы и выходы переходов представляют собой комплекты позиций. Комплект является обобщением множества, в которое включены многократно повторяющиеся элементы — тиражированные элементы. Использование комплектов, а не множеств для входов и выходов перехода позволяет позиции быть кратным входом либо кратным выходом перехода. Кратность входной позиции piдля перехода tjесть число появлений позиции во входном комплекте перехода, #(pi, I(tj)). Аналогично кратность выходной позиции piдля перехода tjесть число появлений позиции в выходном комплекте перехода, #(pi, О(tj)). Если входная и выходная функции являются множествами (а не комплектами), то кратность каждой позиции есть либо 0, либо 1.

Существует и такой вариант определения входной и выходной функций переходов. I – входная функция переходов, которая определяется как отображение I: PTN0; O – выходная функция переходов, которое определяется как отображение O: TPN0, где N0 – множество натуральных чисел и ноль.

Ориентированные дуги (стрелки) соединяют позиции и переходы, при этом некоторые дуги направлены от позиций к переходам, а другие — от переходов к позициям. Дуга, направленная от позиции piк переходу tj, определяет позицию, которая является входом перехода. Кратные входы в переход указываются кратными дугами из входных позиций в переход. Выходная позиция указывается дугой от перехода к позиции. Кратные выходы также представлены кратными дугами.

Рис. 6.1. Граф сети Петри

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

Рис. 6.2. Маркированная сеть Петри

Связь между определениями маркировки как функции и как вектора очевидным образом устанавливается соотношением μ(pi) = μi.

Маркированная сеть Петри М = (С, μ) есть совокупность структуры сети Петри С = (Р, Т, I, О) и маркировки μ и может быть записана в виде М = (Р, Т, I, О, μ). На графе сети Петри фишки изображаются маленькой точкой в кружке, который представляет позицию сети Петри. На рис. 6.2 приведен пример графического представления маркированной сети Петри.

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

Переход tjÎ Т в маркированной сети Петри С — (Р, Т, I, О) с маркировкой μ разрешен, если для всех piÎ Р μ(pi) ³ #(pi, I(tj)).

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

В качестве примера рассмотрим маркированную сеть Петри, изображенную на рис. 6.3. При такой маркировке разрешены только три перехода: t1, t3и t4. Переход t2не разрешен, так как ни позиция р2, ни позиция р3, являющиеся входами перехода t2, не содержат ни одной фишки. Так как переходы t1,t3и t4разрешены, любой из них может быть запущен. Если запущен переход t4, то происходит удаление фишки из каждого входа и помещение фишки в каждый выход. При этом одна фишка удаляется из р5, одна фишка помещается в р3, а количество фишек в р 4 увеличивается с двух до трех. Новая маркировка, полученная в результате запуска перехода t4, показана на рис. 6.4.

В маркированной сети Петри, изображенной на рис. 6.4, разрешены только переходы t1и t3. При запуске перехода t1 осуществляется удаление фишки из р1 и помещение фишек в р2, р3 и р4 (в p4 — две фишки, так как эта позиция является кратным выходом перехода t1). Эта операция образует маркировку, приведенную на рис. 6.5.

Рис. 6.3. Маркированная сеть Петри для иллюстрации правил запуска. Переходы t1, t3 и t4 разрешены.

Рис. 6.4. Маркировка, полученная в результате запуска перехода t4в сети на рис. 6.3.

Рис. 6.5. Маркировка, полученная при запуске перехода t1 в сети на рис. 6.4.

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

Пространство состояний сети Петри. Состояние сети Петри определяется ее маркировкой. Запуск перехода изменяет состояние сети Петри посредством изменения маркировки сети. Пространство состояний сети Петри, обладающей nпозициями, есть множество всех маркировок, т. е. Nn. Изменение в состоянии, вызванное запуском перехода, определяется функцией изменения d, которую мы назовем функцией следующего состояния. Когда эта функция применяется к маркировке μ (состоянию) и переходу tj (он должен быть разрешен), она образует новую маркировку (состояние), которая получается при запуске перехода tjв маркировке μ.

Пусть дана сеть Петри С = (Р, Т, I, О) с начальной маркировкой μ°. Эта сеть может быть выполнена последовательными запусками переходов. Запуск разрешенного перехода tjв начальной маркировке образует новую маркировку μ1 = d (μ°, tj). В этой новой маркировке можно запустить любой другой разрешенный переход, например tk, образующий новую маркировку μ2 = d (μ1, tk). Этот процесс будет продолжаться до тех пор, пока в маркировке будет существовать хотя бы один разрешенный переход. Если же получена маркировка, в которой ни один переход не разрешен, то никакой переход не может быть запущен, функция следующего состояния не определена для всех переходов, и выполнение сети должно быть закончено.

Для сети Петри С = (Р, Т, I, О) с маркировкой μ маркировка μ’ называется непосредственно достижимой из μ, если существует переход tjÎ Т, такой, что d (μ, tj) = μ’.

Можно распространить это понятие на определение множества достижимых маркировок данной маркированной сети Петри. Если μ’ непосредственно достижима из μ, а μ» — из μ’, говорят, что μ» достижима из μ. Определим множество достижимости R(C, μ) сети Петри С с маркировкой μ как множество всех маркировок, достижимых из μ. Маркировка μ’ принадлежит R(С, μ), если существует какая-либо последовательность запусков переходов, изменяющих μ на μ’.

Множество достижимости R(C, μ) для сети Петри С = (Р, Т, I, О) с маркировкой μ есть наименьшее множество маркировок, определенных следующим образом:

2. Если μ’ Î R(С, μ) и μ» = d (μ’, tj) для некоторого tjÎ Т, то μ» Î R (С, μ).

6.2. Сети Петри для моделирования

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

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

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

В качестве примера рассмотрим задачу моделирования простого автомата-продавца. Автомат-продавец находится в состоянии ожидания до тех пор, пока не появится заказ, который он выполняет и посылает на доставку. Условиями для такой системы являются: а) автомат-продавец ждет; б) заказ прибыл и ждет; в) автомат-продавец выполняет заказ; г) заказ выполнен. Событиями будут: 1. Заказ поступил. 2. Автомат-продавец начинает выполнение заказа. 3. Автомат-продавец заканчивает выполнение заказа. 4. Заказ посылается на доставку. Предусловия события 2 (автомат-продавец начинает выполнение заказа) очевидны: (а) автомат-продавец ждет; (б) заказ прибыл и ждет. Постусловие для события 2: (в) автомат-продавец выполняет заказ. Аналогично мы можем определить предусловия и постусловия для всех остальных событий:

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

Сеть Петри на рис. 6.6 иллюстрирует модель приведенного выше автомата-продавца.

Рис. 6.6. Сеть Петри для простого автомата-продавца

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

Рис. 6.7. Моделирование простой вычислительной системы

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

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

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

Рис. 6.8. Моделирование» непримитивного события.

Для простоты обычно вводят следующее ограничение. Запуск перехода (и соответствующего события) рассматривается как мгновенное событие, занимающее нулевое время, и возникновение двух событий одновременно невозможно. Моделируемое таким образом событие называется примитивным; примитивные события мгновенны и неодновременны. Непримитивными называются такие события, длительность которых отлична от нуля. Они не являются неодновременными и, следовательно, могут пересекаться во времени. Так как осуществление большинства событий в реальном мире занимает некоторое время, то они являются непримитивными событиями и поэтому не могут должным образом моделироваться переходами в сети Петри. Однако это не приводит к возникновению проблем при моделировании систем. Непримитивное событие может быть представлено в виде двух примитивных событий: «начало непримитивного события», «конец непримитивного события» и условия «непримитивное событие происходит». Эта ситуация может быть промоделирована с помощью сети, показанной на рис. 6.8.

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

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

Рис. 6.9. Одновременность. Эти два Рис. 6.10. Конфликт. Переходы tj и tk

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

в любом порядке. одного из них удаляет фишку из pi

и тем самым запрещает другой.

один переход, так как при запуске он удаляет фишку из общего входа и запрещает другой переход.

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

6.3. Анализ сетей Петри

6.3.1. Задачи анализа сетей Петри

Безопасность. Позиция piÎ Pсети Петри С = (P, Т, I, О) с начальной маркировкой μявляется безопасной, если μ’ (pi) ≤ 1 для любой μ’ Î R(C, μ). Сеть Петри безопасна, если безопасна каждая ее позиция. Безопасность — очень важное свойство для устройств аппаратного обеспечения. Если позиция безопасна, то число фишек в ней равно 0 или 1. Следовательно, позицию можно реализовать одним триггером.

Ограниченность. Безопасность — это частный случай более общего свойства ограниченности. Позиция pi Î Pсети Петри С — (Р, Т, I, О) с начальной маркировкой μявляется k-безопасной, если μ'(р i) ≤ kдля всех μ’ Î R(C, μ). 1-безопасная позиция называется просто безопасной. Заметим, что граница kпо числу фишек, которые могут находиться в позиции, может быть функцией от позиции (например, позиция p1может быть 3-безопасной, тогда как позиция p2 — 8-безопасной). Однако, если позиция pik-безопасна, то она также и k’-безопасна для всех k’ ³ k. Поскольку число позиций конечно, можно выбрать k*, равное максимуму из границ каждой позиции, и определить сеть Петри k*-безопасной, если каждая позиция сети k*-безопасна.

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

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

Сеть Петри С = (Р, Т, I, О) с начальной маркировкой называется строго сохраняющей, если для всех μ’ Î R(C, μ)

.

Строгое сохранение — это очень сильное ограничение. Например, из него немедленно следует, что число входов в каждый переход должно равняться числу выходов, |I(tj )| = |O(tj )|. Если бы это было не так, запуск перехода изменил бы число фишек в сети.

.

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

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

Уровень 0: Переход tj обладает активностью уровня 0 и называется пассивным или мертвым, если он никогда не может быть запущен.

Уровень 1: Переход tj обладает активностью уровня 1 и называется потенциально активным или живым, если он потенциально запустим, т. е. если существует такая μ’ Î R(C, μ), что tj разрешен в μ’.

Уровень 2: Переход tj обладает активностью уровня 2, если для всякого целого nсуществует последовательность запусков, в которой tj присутствует по крайней мере nраз.

Уровень 3: Переход tj обладает активностью уровня 3, если существует бесконечная последовательность запусков, в которой tj присутствует неограниченно часто.

Уровень 4: Переход tj обладает активностью уровня 4 и называется активным или живым, если для всякой μ’ Î R(C, μ) существует такая последовательность запусков σ, что tj разрешен в δ (μ’, σ).

Устойчивость переходов и СП. Переход ti СП С = (Р, Т, I, О) с маркировкой μ называется устойчивым, если он активен при данной маркировке и никакой другой переход tk, тоже активный при маркировке μ, не может, сработав, сделать переход ti неактивным, т. е. лишив его возможности срабатывания. СП С = (Р, Т, I, О) с маркировкой μ называется устойчивой, если все ее переходы являются устойчивыми.

Достижимость и покрываемость. Большинство задач, к которым мы до сих пор обращались, касаются достижимых маркировок.

Задача достижимости. Для данной сети Петри С с маркировкой μ и маркировки μ’ определить: μ’ Î R(C, μ )? Задача достижимости, быть может, основная задача анализа сетей Петри; многие другие задачи анализа можно сформулировать в терминах задачи достижимости.

Задача покрываемости. Эта задача аналогична достижимости, но несколько отличается. Для данной сети Петри С с начальной маркировкой μи маркировки μ’ определить, существует ли такая достижимая маркировка
μ» Î R(C, μ ), что μ» ³ μ ‘.

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

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

6.3.2. Методы анализа

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

Дерево достижимости. Дерево достижимости представляет множество достижимости сети Петри. Рассмотрим, например, маркированную сеть Петри на рис. 6.11. Начальная маркировка ее — (1, 0, 0). В этой начальной маркировке разрешены два перехода: t1 и t2. Пусть корнем является вершина, соответствующая начальной маркировке, определим новые вершины в дереве достижимости для (достижимых) маркировок, получающихся в результате запуска каждого из этих двух переходов. Дуга, помеченная запускаемым переходом, приводит из начальной маркировки к каждой из новых маркировок (рис. 6.12). Это (частичное) дерево показывает все маркировки, непосредственно достижимые из начальной маркировки.

Теперь необходимо рассмотреть все маркировки, достижимые из новых маркировок. Из маркировки (1, 1, 0) можно снова запустить t1 (получая 1, 2, 0) и t2 (получая (0, 2, 1)); из (0, 1, 1) можно запустить t3 (получая (0, 0, 1)). Это порождает дерево, изображенное на рис. 6.13. Начиная с трех новых маркировок, необходимо повторить этот процесс, порождая новые маркировки, которые нужно ввести в дерево, как показано на рис. 6.14.

Рис. 6.11. Маркированная сеть Петри, Рис. 6.12. Первый шаг построения

для которой строится дерево достижимости. дерева достижимости

Заметим, что маркировка (0, 0, 1) пассивная; никакой переход в ней не является разрешенным, поэтому никакие новые маркировки из этой пассивной маркировки в дереве порождаться не будут. Кроме того, необходимо отметить, что маркировка (0, 1, 1), порождаемая запуском t3 в (0, 2, 1), была уже порождена непосредственно из начальной маркировки запуском t2.

Рис. 6.13. Второй шаг построения дерева достижимости.

Если эту процедуру повторять снова и снова, каждая достижимая маркировка окажется порожденной. Однако получившееся дерево достижимости может оказаться

Рис. 6.14. Третий шаг построения дерева достижимости.

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

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

Приведение к конечному представлению осуществляется несколькими способами. Нам необходимо найти те средства, которые ограничивают введение новых маркировок (называемых граничными вершинами) на каждом шаге. Здесь могут помочь пассивные маркировки — маркировки, в которых нет разрешенных переходов. Эти пассивные маркировки называются терминальными вершинами. Другой класс маркировок — это маркировки, ранее встречавшиеся в дереве. Такие дублирующие маркировки называются дублирующими вершинами; никакие последующие маркировки рассматривать нет нужды — все они будут порождены из места первого появления дублирующей маркировки в дереве. Таким образом, в дереве на рис. 6.14 маркировка (О, 1. 1), получившаяся в результате выполнения последовательности t1t2t3, не будет порождать какие-либо новые вершины в дереве, поскольку она ранее встречалась в дереве в результате выполнения последовательности t3 из начальной маркировки.

Представим бесконечное число маркировок, получающихся из циклов такого типа, с помощью специального символа ω, который обозначает «бесконечность». Для любого постоянного a определим

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

Покрываемость. Последняя задача, которую можно решить с помощью дерева достижимости, — задача покрываемости. В задаче покрываемости хотят для данной маркировки μ’ определить, достижима ли маркировка μ» ³ μ’. Данная задача решается проверкой дерева достижимости. Строим для начальной маркировки μ дерево достижимости. Затем ищем любую вершину х с μ [х] ³ μ’. Если такой вершины не существует, маркировка μ’ не покрывается никакой достижимой маркировкой; если она найдена, μ [x] дает достижимую маркировку, покрывающую μ’.

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

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

6.4. Обобщения сетей Петри

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

Сети Петри со сдерживающими дугами. Сдерживающая дуга из позиции pi в переход tj имеет маленький кружок (а не стрелку). Кружок означает отрицание (“не”). Правила запуска изменяются следующим образом: переход является разрешённым, когда фишки присутствуют во всех его (обычных) входах и отсутствуют в сдерживающих входах. Переход запускается удалением фишек из всех его (обычных) входов. Так можно описывать переходы, «исключающее ИЛИ». В обычных СП переход запускается, когда все его входы имеют фишки (логика И). Переход “исключающее ИЛИ” запускается тогда и только тогда, когда только один из его входов имеет фишки, а все другие фишек не имеют. Когда переход запускается, он удаляет фишку только из входа с фишками.

Рис. 6.16. Интерпретация перехода “исключающее ИЛИ” с помощью сдерживающих дуг

Имеются ещё два других важных расширений СП. Переходам могут быть поставлены в соответствие приоритеты так, что если ti и tk оба допустимы, то переход с высшим приоритетом будет запущен первым. Механизм назначения приоритетов может устанавливать порядок срабатывания переходов при возникновении конфликтов. Во-вторых, используют временные сети Петри. Во временных сетях Петри каждому переходу tj сопоставляются два момента времени τ1,j и τ2,j. Переход tj может быть запущен, только если он был разрешён к моменту времени τ1,j. Если он является разрешённым, то должен быть запущен до наступления момента времени τ2,j. Рассмотрим временные сети более подробно.

Формально временные сети задаются набором (P, T, I, O, μ°, Z), где P, T, I, O, μ имеют обычный смысл, а Z: P→R+ функция времени задержки меток в позициях сети. Работа временных сетей подчиняется следующим правилам:

▪ метки в позициях могут быть доступными или же недоступными;

▪ переходы считаются возбуждёнными, если все их входные позиции имеют метки и эти метки доступные;

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

▪ каждая метка, совершившая переход из в , будет недоступной в в течении времени , начиная с момента её появления в . По истечению времени метка становится доступной.

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

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

А теперь рассмотрим конкретные варианты реализации расширенных сетей Петри.

6.4.1. Временные сети событий (ВСС)

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

Механизм изменения состояний ВСС связан с выполнением переходов . Каждый переход можно записать в виде тройки . Здесь— условия возбуждения, — схема выполнения, — процедура перехода. Условие возбуждения — это предикат, определённый на множестве позиций из , истинный только в том случае, когда реализуется некоторая заданная разметка позиций множества . Кроме того, условие возбуждения, может включать ещё проверку значений атрибутов меток. Если значение какого-то атрибута является функцией времени, то обеспечивается соответствующая значению данной функции времени задержка. Схема выполнения определяет изменение разметки позиций сети при срабатывании перехода. Пусть — упорядоченное множество позиций, смежных с . Тогда схема — это вектор, элементы которого образуют биекцию с элементами множества . Любое положительное целое число в означает число меток, помещённых в соответствующую позицию после выполнения перехода. Целые отрицательные числа в указывают число удалённых меток из соответствующих позиций. Нулевые значения компонент отмечают изменяемые позиции (каждая изменяемая позиция не обязательно имеет единственную метку и образует с переходом цикл длины 2). Не изменяемые в результате срабатывания перехода позиции отмечаются в символом (*). Процедура перехода представляет собой правила вычисления атрибутов (для позиций, отмеченных в нулём) или добавления (удаления) меток.

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

Р – конечное непустое множество позиций сети P=<>; — множество периферийных (не внутренних) позиций; — множество решающих позиций. Позиции играют в Е-сетях ту же самую роль, что и в сетях Петри. Обозначаются графически также кружком. Периферийные позиции используются для моделирования взаимосвязей системы с внешней средой. Решающие позиции не имеют прямых аналогов в СП. С их помощью в Е-сетях обеспечивается разрешение конфликтов и синхронизация событий. С каждой решающей позицией связан некоторый список предикатов, применяемый для формального описания условий выполнения переходов. Задаются эти позиции шестиугольниками.

В каждом состоянии сети позиции могут иметь или не иметь метку. Число меток в каждой позиции ≤1 (М: Р→<0,1>). Отмечается метки жирной точкой.

Третий элемент набора I(A), O(A) – множество позиций, смежных с переходами по входу (I) и выходу (О). Пары и , составленные из смежных позиций и переходов, соответствуют дугам сети.

Четвёртый элемент набора функция Z: A→R+, с помощью которой в Е-сетях задаются значения времени выполнения переходов, т. о. имитируются временные задержки, связанные с реализацией моделируемых событий.

Пятый элемент набора задаёт непустое конечное множество переменных – количественных оценок состояния модели.

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

Восьмой элемент набора обозначает начальную маркировку позиций.

При построении Е-сетей используется ограниченный набор типов переходов: T, I, F, X, Y, MX, MY (см. табл.). Два последних являются макрорасширениями X и Y переходов.

Макропереходы определяются несколько сложнее, чем соответствующие схемы X и Y переходов. Однако, главным в них по-прежнему остаётся сравнение значений решающей позиции и меток инцидентных переходу дуг.

Каждый переход Е-сети имеет три характеристики и записывается как где — тип перехода; — время перехода; — процедура перехода. Переход выполняется в 3 этапа:

1. Проверяются условия активности перехода, а для X и Y переходов ещё и находятся значения решающей позиции и определяется конкретная схема срабатывания.

2. Реализуется задержка выполнения перехода на время Z и пересчитываются значения атрибутов метки по правилам, указанным в процедуре .

3. В соответствии со схемой перехода изменяются маркировки его входных и выходных позиций.

Объединение всех наборов атрибутивных переменных сети образует множество ATTR её локальных переменных.

Связи Е между позициями и переходами в К-сетях задаются обычным для сетей Петри способом: .

Необходимые условия возбуждения переходов описываются логическими выражениями. Переход может перейти в возбуждённое состояние, если соответствующее этому переходу логическое выражение будет истинным. Другое необходимое условие возбуждения связано с текущей разметкой входных и выходных позиций перехода. В тех случаях, когда количество маркеров в больше, чем это необходимо для возбуждения перехода, возникает вопрос о механизме выбора удалённых маркеров. Такими механизмами могут быть: FIFO, LIFO, HVF, LVF, согласно заданным приоритетам или по указанию пользователя.

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

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

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

Источник