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

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

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

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

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

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

1. Моделируемые процессы (явления) совершаются в системе, описываемой множеством событий и условий, которые эти события определяют, а также причинно-следственными отношениями, устанавливаемыми на множестве «события-условия».

2. Определяются события-действия, последовательность наступления которых управляется состоянием системы. Состояния системы задаются множеством условий. Условия формулируются в виде предикатов. Количественные условия характеризуются емкостью. Емкость условий выражается числами натурального ряда.

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

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

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

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

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

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

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

Рис. 5.3

Если в какой либо момент времени разрешено более одного перехода, то любой из них может стать «следующим». Выбор запускаемого перехода осуществляется недетерминированным (случайным) образом. Недетерминированность и неодновременность запусков переходов в моделировании параллельной системы показывается двумя способами. Одна из них представлена на рис. 5.8. В этой ситуации два разрешённых перехода t_j и t_k не влияют друг на друга. В число возможных последовательностей событий входит последовательность, в которой первым срабатывает один переход и последовательность, в которой первым срабатывает другой переход. Эти два перехода могут быть запущены в любом порядке, это называется недетерминированностью и неодновременностью. Переход t_k (рис. 5.4) может быть запущен в любом порядке, но обязательно при помощи маркеров в обеих позициях. Это называется одновременностью. Другая ситуация, в которой одновременное выполнение затруднено и которая характеризуется невозможностью одновременного запуска, показана на рис. 5.5. Здесь переходы t_j и t_k находятся в конфликте, так как запуск одного из них удаляет маркер из p_i и, тем самым, завершает другой переход. Эта ситуация называется конфликтом и в моделируемых системах отображает борьбу за общие ресурсы.


Рис. 5.4	Рис. 5.5

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

6. Обощенные модели (A -схемы)

Обобщенный подход базируется на понятии агрегативной системы (aggregate system), представляющей собой формальную схему общего вида (А-схему). Этот подход позволяет описывать поведение непрерывных и дискретных, детерминированных и стохастических систем.

А -схема должна выполнять несколько функций:

- являться адекватным математическим описанием объекта моделирования;

- позволять в упрощенном варианте (для частных случаев) проводить аналитические исследования.

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

Элементом А -схемы является агрегат. Связь между агрегатами (внутри системы S и с внешней средой E) осуществляется с помощью оператора сопряжения R. Агрегат может рассматриваться как А -схема,т.е. может разбиваться на элементы (агрегаты) следующего уровня.

Характеристиками агрегата являются множества моментов времени T, входных X и выходных Y сигналов, состояний Z в каждый момент времени t.

Пусть переход агрегата из состояния z (t ₁) в состояние z (t ₂) ¹ z (t ₁) происходит за малый интервал времени d z. Переходы из состояния z (t ₁) в z (t ₂) определяются внутренними параметрами агрегата h (t) Î H и входными сигналами x (t) Î X.

В начальный момент времени t ₀ состояния z имеют значения, равные z ⁰, т.е. z ⁰ = z (t ₀), которые задаются законом распределения L [ z (t ₀)]. Пусть изменение состояния агрегата при входном сигнале х_п описывается случайным оператором V. Тогда для момента времени t_n Î T при поступлениивходного сигнала х_n состояние определяется по формуле (6.1):

z (t_n + 0) = V [ t_n, z (t_n), x_n ]. (6.1)

Если на интервале времени (t_n, t_n + i) нет поступления сигналов, то для t Î (t_n, t_n ₊₁) состояние агрегата определяется случайным оператором U, и его можно записать следующим образом (6.2):

z (t) = U [ t, t_n, z (t_n + 0)]. (6.2)

Так как на оператор U не накладываются никакие ограничения, то допустимы скачки состояний d z в моменты времени, не являющимися моментами поступления входных сигналов x.

Моменты скачков d z называются особыми моментами времени t_s, состояния z (t_s) – особыми состояниями А -схемы. Для описания скачков состояний d z в особые моменты времени t_s используется случайный оператор W, которыйпредставляет собой частный случай оператора U (6.3):

z (t _d + 0) = W [ t _d, z (t _d)]. (6.3)

На множестве состояний Z выделяется такое подмножество Z ⁽ ^Y ⁾, что если z (t _d) достигает Z ⁽ ^Y ⁾, то это состояние является моментом выдачи выходного сигнала. Выходной сигнал можно описать оператором выходов (6.4):