1.7.3 Применение сетевых моделей для описания параллельных процессов

Одним из распространенных средств описания параллель­ных процессов являются сети Петри.

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

При графической интерпретации сеть Петри представляет собой граф осо­бого вида, состоящий из вершин двух типов — позиций и переходов, соединен­ных ориентированными дугами, причем каждая дуга может связывать лишь раз­нотипные вершины (позицию с переходом или переход с позицией). Вершины-позиции обозначаются кружками, вершины-переходы - черточками. С содержательной точки зрения, переходы соответствуют событиям, присущим исследуемой системе, а позиции - условиям их возникновения. Таким образом, совокупность переходов, позиций и дуг позволяет описать причинно-следствен­ные связи, присущие системе, но в статике. Чтобы сеть Петри «ожила», вводят еще один вид объектов сети - так называемые фишки, или метки позиций. Пе­реход считается активным (событие может произойти), если в каждой его вход­ной позиции есть хотя бы одна фишка. Расположение фишек в позициях сети называется разметкой сети (пример перемещения фишек по сети приведен на рис. 1.10).

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

где     - конечное непустое множество позиций;

          - конечное непустое множество переходов;

          - входная функция (прямая функция инцидентности), которая для каждого перехода задает множество его входных позиций;

          - выходная функция (обратная функция инцидентности), которая для каждого перехода задает множество его выходных позиций;

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

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

 (для всех входных позиций разметка должна быть больше либо равно 1).

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

,

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

Основные направления анализа сети Петри следующие:

1.     Проблема достижимости: в сети Петри с начальной разметкой  требуется определить, достижима ли принципиально некоторая разметка  из .

С точки зрения исследования моделируемой системы, эта проблема интерпретируется как проблема достижимости (реализуемости) некоторого состояния системы.

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

Анализ модели на свойство живости позволяет выявить невозможные состо­яния в моделируемой системе (например, неисполняемые ветви в программе).

3.     Безопасность сети. Безопасной является такая сеть Петри, в которой ни при каких условиях не может появиться более одной метки в каждой из позиций.

Для исследуемой системы это означает возможность функционирования ее в стационарном режиме. На основе анализа данного свойства могут быть определе­ны требования к буферным накопителям в системе.

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

1)     позволяют моделировать ПП всех возможных типов с учетом вероятных кон­фликтов между ними;

2)     обладают наглядностью и обеспечивают возможность автоматизирован­ного анализа;

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

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

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

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

1) имеются несколько типов вершин-позиций: простые позиции, позиции-оче­реди, разрешающие позиции;

2) фишки (метки) могут снабжаться набором признаков (атрибутов);

3) с каждым переходом может быть связана ненулевая задержка и функция пре­образования атрибутов фишек.

4) введены дополнительные виды вершин-переходов.

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

где     - тип перехода,

               - функция задержки,

 - функция преобразования атрибутов.

Некоторые базовые переходы Е-сети описаны ниже.

Т-переход («исполнение», «простой переход»). Его графическое представление аналогично представлению вершины-перехода сети Петри:

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

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

 

F-переход («разветвление»).

Графическое представление:

Срабатывает при тех же условиях, что и Т-переход:

С содержательной точки зрения F-переход отображает разветвление потока информации в системе.

 

J-переход («объединение»).

Графическое представление:

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

Он моделирует объединение потоков или наличие нескольких условий, определяющих некоторое событие.

 

X-переход («переключатель»).

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

Логика его срабатывания задается следующими соотношениями:

X-переход изменяет направление потока информации. Сущность разрешающей процедуры заключается в проверке выполнения условий разветвления потока (с точки зрения программиста разрешающая позиция аналогична условному оператору типа if).

 

Y-переход («выбор», «приоритетный выбор»). Этот переход также содержит разрешающую позицию:

Логика срабатывания Y-перехода:

 

Y-переход отражает приоритетность одних потоков информации по сравнению с другими. При этом разрешающая процедура может быть определена различным образом: как операция сравнения фиксированных приоритетов меток; как функция от атрибутов меток. В некотором смысле он работает аналогично оператору выбора case.

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

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

Макропозиция очередь представляет собой линейную композицию вершин-по­зиций и Т-переходов; количество вершин-позиций определяет «емкость» очереди:

Макропозиция генератор позволяет представлять в сети источник меток (транзактов):

Если необходимо задать закон формирования меток, то «генератор» может быть дополнен разрешающей позицией.

Поскольку в Е-сети нельзя «накапливать» метки, то вводится макропозиция поглощения: