Полная версия

Главная arrow Информатика arrow Имитационное моделирование

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Сети Петри

Сеть Петри — это сеть «мест-переходов» N = (Р, Т, F, Н, S), состоящая из следующих объектов: Р и Т — непересекающие- ся множества, на которые разбивается множество всех узлов сети. Узлы из Р называются местами, или позициями, узлы из Г — переходами. Функции F и Н указывают для каждого перехода подмножество мест, связанных с ним дугами: F(t) — множество входных мест перехода t, из которых дуги входят в t; H(t) — множество выходных мест, в которые дуги выходят из t.

Функция S помечает переходы, т. е. S(t) — метка перехода t (разные переходы могут быть помечены одинаково).

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

В аналитической форме сеть Петри может быть представлена следующим образом:

где В = {bj} — конечное непустое множество позиций; D — = {d,} — конечное непустое множество переходов; / : В х D —> —» {0, 1} — входная функция (прямая функция инцидентности), которая для каждого перехода задает множество его входных позиций; О: D х В ^ (0, 1} — выходная функция (обратная функция инцидентности), которая для каждого перехода задает множество его выходных позиций; М — функция разметки сети, М: В —> —> (0, 1, 2, ...}, ставит каждой позиции в соответствие неотрицательное целое число (равное числу меток в данной позиции).

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

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

Срабатывание перехода dt изменяет разметку сети М(В) на разметку М'(В) по следующему правилу:

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

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

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

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

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

В зависимости от целей моделирования компоненты настройки могут изменяться.

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

1. Однотипные элементы СП не могут между собой связываться дугами непосредственно (рис. 2.1, а).

Рис. 2.1

  • 2. СП, в которой нет ни одного маркера, называется неразмеченной и не может функционировать.
  • 3. Срабатывание перехода в классических СП происходит мгновенно (tcp = 0) в момент выполнения логического условия, разрешающего срабатывание перехода.
  • 4. В графическом представлении классических СП любые два (неоднотипных) элемента сети могут быть связаны между собой необходимым количеством дуг. Если число дуг больше единицы, их называют кратными, или дугами кратности К, где К — количество «параллельных» дуг (на рис. 2.1, б кратные дуги показаны пунктирным эллипсом с указанием значения кратности К).
  • 5. Логическое условие срабатывания перехода — для срабатывания перехода в каждой позиции, связанной выходящей (ими) дугой(ами) со входом(ами) рассматриваемого перехода, должно находиться количество маркеров (М), не меньшее кратности К (см. рис. 2.1, б).
  • 6. При срабатывании перехода из каждой позиции, связанной К выходными дугами со входами сработавшего перехода (К = 1, 2, 3, ...), удаляются К маркеров.
  • 7. При срабатывании перехода в каждую позицию, связанную входящей (ими) в позицию дугой (ами), выходящей (ими) с выхода(ов) сработавшего перехода, придет количество маркеров, равное количеству связывающих их дуг (т. е. кратности связи).
  • 8. Количество маркеров, поступивших на входы перехода при его срабатывании, не связано с количеством маркеров, вышедших при срабатывании этого перехода. На каждой выходящей с перехода дуге появится по одному маркеру.

Входная и выходная функции сети Петри (7 и О) позволяют описать любую сеть с помощью двух матриц размером т х п (матриц входных и выходных позиций), имеющих следующую структуру:

Динамика работы перехода иллюстрируется на рис. 2.2 и 2.3. На рис. 2.2 изображен переход Т с тремя входными и двумя выходными позициями и с кратными дугами (два пунктирных эллипса с численным указанием кратности), для которого на рис. 2.3 приведена временная диаграмма срабатывания перехода при появлении меток в позициях П1? П2, П3, связанных своими выходами с переходом Т, и в позициях П4, П5, связанных своими входами с выходами перехода Т, с отображением изменения количества маркеров в позициях.

Рис 2.2

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

где ty — момент выполнения условия срабатывания перехода.

Рис. 2.3

Для отображения неразделяемого (монопольного) ресурса, в котором в любой момент времени не может находиться более одного маркера, применяют отображение ресурса с помощью двух позиций — и П2. Маркер может находиться в любой момент времени только в одной из этих позиций. Тогда количество маркеров т1 и т2 для монопольного ресурса в Пл и П2 определяется уравнением

Для разделяемого ресурса, который может одновременно использоваться несколькими «пользователями», если суммарный ресурс R достаточен, используется то же уравнение, но вместо 1 будет указана другая емкость ресурса, а именно R:

На рис. 2.4, ав приведены следующие примеры:

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

Рис. 2.4

Наиболее мощное расширение сетей Петри — так называемые Е-сети (от англ. Evaluationоценка).

В отличие от сетей Петри, в Е-сетях [7]:

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

В связи с этим любой переход может быть описан тройкой параметров

Здесь S — тип перехода, t(d,) — функция задержки, отражающая длительность срабатывания перехода, р(<2;0 — функция преобразования атрибутов меток.

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

В качестве заключительного примера на рис. 2.5 приведена структура системы массового обслуживания (СМО), а на рис. 2.6, а, б представлены два варианта СП при бесприори- тетных потоках заявок и потоках с относительными приоритетами соответственно: на рис. 2.5 — СМО с двумя источниками заявок с общей очередью на R мест и одним обслуживающим прибором; на рис. 2.6, а — СП для СМО при равных приоритетах заявок (дисциплина FIFO); на рис. 2.6, б — СП для СМО при относительных приоритетах ПРХ > ПР2. П Т1 и П2, Т2 интерпретируют работу генераторов заявок (Гх и Г2 соответственно). Пунктирными прямоугольниками объединены позиции, представляющие один единый элемент СМО.

Рис. 2.5

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

Рис. 2.6

Рис. 2.7

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

Начальный цвет метки в Р0 равен Сь и дуга (Р0, t-Д окрашена в Cv Поэтому условие возбуждения выполнимо для перехода tj. После срабатывания метка возвращается в Р0, имея цвет С2, поскольку дуга (t1? Р0) раскрашена в цвет С2. Раскрашивание дуг обеспечивает возбуждение только одного из переходов, следующих за Р0, при любом состоянии системы. При данной раскраске алгоритм работы супервизора представлен последовательностью срабатывания переходов tb t2, (t3, t4), t5, t6, t. e. происходит запуск первого процессора, затем второго, после чего следует их освобождение и цикл повторяется.

Для моделирования такой сети Петри требуется ее формальное описание. Оно может быть представлено в различных языковых системах. Ниже дано описание, ориентированное на синтаксис языка Паскаль. Рассмотрим пример сети, изображенный на рис. 2.8, а (на рис. 2.8, б показана эквивалентная ей обыкновенная сеть Петри).

Puc. 2.8

Аналитическое представление сети определяет ее статическое описание и исходное состояние; динамика представляется прохождением фишек от позиции к позиции.

Статическое описание содержит следующие параметры: множество позиций:

type Р = (рх, р2) р3); множество переходов: type Т = (t);

множество дуг А = Ар kj Af, Ар = {al} а2}, Af = {а3}:

ах = рх to tj a2 = р2 to t, a3 = t to p3; type AP = (ax, a2); type AT = (a3); var aXJ a2 : AP; van a3 : AT;

переменные:

Van x : colorC; Var у : colorE;

множества цветов:

type colorC = (г, g, b); colonE = (e);

цветовая функция

colorC if p in [p2, p3]; colorE if p in [p.J;

функция E(a), задающая выражения на дугах:

Е(аД = l'e;

E(a2) = if x = r then 1'r

else if x = g then l'g else l'b;

E(a3) = if (x = r and у = e) then l'r

else if (x = g and у = e) then l'g

else if (x = b and у = e) then l'b;

функция инициализации /(p), задающая начальную маркировку:

m0(Pi) = (З'е); m0(p2) = (l'r, l'g, l'b); m0(p3) = 0.

Поясним описание сети. Для позиции р} разрешен цвет е, для позиций р2, р3 разрешены цвета г, g,b. Переход t может сработать, если в позиции рг находится хотя бы одна фишка цвета е и в позиции р2 находится хотя бы одна фишка цветов г, g,b.

В позицию р3 при срабатывании перехода пересылается та фишка, которая была извлечена из р2 при срабатывании перехода. Начальная маркировка — три фишки цвета е в позиции р1} по одной фишке всех цветов в позиции р2. В позиции р3 фишек нет.

Дерево маркировок описывает все возможные варианты последовательности пересылки фишек. В табл. 2.1 приведено полное дерево маркировок рассмотренной сети.

Таблица 2.1

Исходное

состояние

1 такт

2 такт

3 такт

т0 ={3'е, 1'г, l'g, l'b, 0}

t: х = r,y = е

{2'е, l'g, l'b, 1»

t: x = g, у = e

(l'e, l'b, l'r, l'g}

t: x = b,y = e

{0, 0, l'r, l'g, IV}

Исходное

состояние

1 такт

2 такт

3 такт

t: x = b,y = e

{IV, l'g, l'r, l'b}

t:x = g,y = e

{0, 0, l'r, l'b, l'g}

t:x = g,y = e

{2'e, IV, l'b, 1 'g>

t: x — г, у — e

{IV, l'b, l'g, l'r}

t: x = b,y = e

{0, 0, l'g, l'r, l'b}

t: x = b,y = e

{IV, l'r, l'g, l'b}

t :x = r,y = e

{0, 0, l'g, l'b, l'r}

t: х = b, у = e

{2'e, l'r, l'g, l'b}

t: x = g, у = e

{0, 0, l'b, l'r, l'g}

t:x = g,y = e

{IV, l'r, l'b, l'g}

t: x = r,y = e

{0, 0, l'b, l'g, l'r}

Рассмотрим в качестве примера некоторые ситуации в работе сети.

При работе сети переменная х принимает поочередно (в произвольном порядке) значения г, g, Ъ, а переменная у — значение е. Пусть переменная х приняла значение г. Тогда в первом такте в позиции р: останется две фишки цвета е, в позиции р2 — фишки цветов g и b и в позиции р3 — одна фишка цвета г. Если теперь переменная х примет значение g (цвет переменной у = е ), то в вершине рг останется одна фишка цвета е, в позиции р2 — фишка цвета Ь, в позиции р3 — фишки цветов г и g . Если теперь на втором такте переменная х примет значение b (переменная рг по- прежнему равна е), то на третьем такте в позициях рь р2 не останется фишек, зато в позиции р3 будут фишки цветов г, g,b.

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

При анализе сети Петри основное внимание уделяется, как правило, трем направлениям.

  • 1. Проблема достижимости. В сети Петри с начальной разметкой т0 требуется определить, достижима ли принципиально некоторая разметка М' из m0. С точки зрения исследования моделируемой системы эта проблема интерпретируется как проблема достижимости (реализуемости) некоторого состояния системы.
  • 2. Оценка живости переходов сети. Под живостью перехода понимают его срабатывание в данной сети при начальной разметке т0. Анализ модели на свойство живости позволяет выявить невозможные состояния в моделируемой системе (например, неисполняемые ветви в программе).
  • 3. Оценка безопасности сети. Безопасной является такая сеть Петри, в которой ни при каких условиях не может появиться более одной метки в каждой из позиций. Для исследуемой системы это означает возможность функционирования в стационарном режиме. Например, на основе анализа данного свойства могут быть определены требования к буферным накопителям в системе.

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

  • — позволяют моделировать параллельные процессы всех типов с учетом возможных конфликтов между ними;
  • — обладают наглядностью и обеспечивают возможность автоматизированного анализа;
  • — позволяют переходить от одного уровня детализации описания системы к другому (за счет раскрытия/закрытия переходов).

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

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

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>