ФЭНДОМ


Теоретические основы сетей Петри: принципы построения, алгоритмы поведения.

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

2. Сети Петри для моделирования систем: способы реализации.

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

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

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

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

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

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

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

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

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

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

1. заготовка поступила;

2. автомат начинает обработку;

3. автомат заканчивает обработку;

4. деталь посылается в накопитель.

Условиями для системы являются:

1. автомат ждет;

2. заготовка загружена;

3. автомат выполняет обработку;

4. деталь обработана.

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

File12 html m2695297a

Сеть Петри рассматриваемого автомата имеет вид (рис.8)

File12 html m7c5ed9d8

Рис. 9

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

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

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

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

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

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

File12 html 5e48752d

Рис. 10

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

File12 html 351b19de

рис. 11, рис. 12

Если в какой либо момент времени разрешено более одного перехода, то любой из них может стать “следующим”. Выбор запускаемого перехода осуществляется недетерминированным образом, то есть случайно и зависит от воли моделирующего систему. Недетерминорованность и неодновременность запусков переходов в моделировании паралельной системы показывается двумя способами.  В одной ситуации два разрешённых перехода tj и tне влияют друг на друга. В число возможных последовательностей событий входит последовательность, в которой первым срабатывает один переход и последовательность в которой первым срабатывает другой переход. Эти два перехода могут быть запущены в любом порядке, это называется недетерминированностью и неодновременностью, переход tk   может быть запущен в любом порядке, но обязательно при помощи маркеров в обеих позициях. Это называется одновременностью. Другая ситуация, в которой одновременное выполнение затруднено и которая характеризуется невозможностью одновременного запуска.  Здесь переходы tj и tk находятся в конфликте, так как запуск одного из них удаляет маркёр из pi и тем самым завершает другой переход. Эта ситуация называется конфликтом и в моделируемых системах отображает борьбу за общие ресурсы.

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

1.     'Моделирование распределенных автоматизированных систем и информационных сетей

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

Техническое обеспечение — одна из основных составных частей АСУ, той материально-технической базы, с помощью которой реализуются экономико-математические методы управления. Комплекс технических средств включает в себя разнообразные средства вычислительной техники, сбора и передачи информации, обеспечивающие своевременную и качественную переработку управляющей информации, причем территориальная удаленность объектов управления в АСУ требует применения средств передачи информации, основная задача которых — обмен информацией между местом ее возникновения и информационно-вычислительным центром с необходимой скоростью и достоверностью.

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

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

Petri network 1

Рис. 1

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

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

В этом случае можно записать: эндогенные переменные: Т0—среднее время обслуживания сообщений; Рот — вероятность отказа в обслуживании; экзогенные переменные: $ \lambda_{\Sigma} $— интенсивность входного потока сообщений; h — производительность абонентской ЭВМ; H — суммарная производительность главных ЭВМ сети; В — пропускная способность селекторных каналов ЭВМ; С — пропускная способность магистрального канала связи.