Сети Петри. 
Вычислительные системы, сети и телекоммуникации. 
Моделирование сетей

Часто аналитики в задачах моделирования и анализа сложных параллельных и асинхронных систем обращаются к формальным системам, основанным на использовании математического аппарата сетей Петри. Формальная часть теории сетей Петри, основанная в начале 60-х годов немецким математиком Карлом Петри, в настоящее время содержит большое количество моделей, методов и средств анализа, имеющих обширное количество приложений практически во всех отраслях вычислительной техники [14].

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

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

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

Итак, сеть Петри — это набор

(3.14).

где  — подмножество вершин, называющихся переходами;  — подмножество вершин, называющихся позициями (местами);  — множество ориентированных дуг.

В сетях Петри вводятся объекты двух типов: динамические — изображаются метками (маркерами) внутри позиций и статические — им соответствуют вершины сети Петри.

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

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

Переходы в сети Петри являются событиями, которые изменяют состояния в реальной системе. На рис. 3.2 приведен пример интерпретации сети Петри.

Таблица 3.1.

Элементы сетей Петри

Название элемента.	Изображение элемента.
Позиция (?).
Переход (?).
Дуга.

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

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

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

Основными свойствами сети Петри являются:

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

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

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

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

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

Большого внимания заслуживают сети высокого уровня, такие как раскрашенные сети Петри (Color Petri Net), являющиеся модификацией сетей Петри и отличающиеся хорошо разработанным математическим аппаратом. Они широко применяются для самых разнообразных практических целей. Основной причиной высокой эффективности этих формальных моделей является то, что они без потери возможностей формального анализа позволяют исследователю получить значительно более краткие и удобные описания, чем те, которые могут быть сделаны с помощью сетей низкого уровня. В сетях высокого уровня сложность моделей может быть разделена между структурой сети, надписями и описаниями. Это позволяет осуществлять описание значительно более сложных систем и анализировать процессы преобразования данных с помощью общепринятых математических выражений вместо сложного набора позиций, переходов и дуг. Раскрашенные сети Петри, в отличие от обычных сетей Петри, позволяют описывать структуру системы в виде иерархии диаграмм.

Но у данного аппарата моделирования также не устранен ряд недостатков, которые присущи сетям Петри. К таким недостаткам можно отнести:

• • необходимость знания разработчиком специфического языка описания моделей [6];
• • отсутствие использования принципов объектно-ориентированного подхода;
• • низкую гибкость и трудоемкость описания систем в случае их декомпозиции до уровня некоторых элементарных операций.

Раскрашенные сети Петри до сих пор часто применяются для моделирования сетей.

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

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

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

Выводы по главе

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

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

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