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

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

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

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

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

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

Рис. 5.7

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

Рис. 5.8	Рис. 5.9

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

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 + 1}) состояние агрегата определяется случайным оператором 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):

y = G [ t _d, z (t _d)]. (6.4)

Под агрегатом будем понимать любой объект, который описывается следующим образом (6.5):

A_n = < T, X, Y, Z, Z ^(Y), H, V, U, W, G >. (6.5)