какие системы позволяет моделировать аппарат сетей петри

Вложенные сети Петри и моделирование распределенных систем

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник

Сети Петри. Структура и правила выполнения сетей Петри.

Сети Петри [ ]

Сети Петри — математический аппарат для моделирования динамических дискретных систем. Впервые описаны Карлом Петри в 1962 году.

Пример работы сети Петри

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

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

Как и стандартные UML диаграммы, BPMN и EPC, сети Петри предоставляют возможность графически иллюстрировать процессы включающие выбор, итерации и одновременное выполнение. Но в отличие от данных стандартов, у сетей Петри четкая математическая формулировка и за ними стоит развитая математическая теория.

==Структура сетей Петри==

Сеть Петри состоит из 4-х элементов:

Пример сети Петри. Белыми кружками обозначены позиции, полосками — переходы, чёрными кружками — метки.

Правила выполнения сетей Петри [ ]

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

Переход запускается, если он разрешен. Переход называется разрешенным, если каждая из его входных позиций имеет число фишек по крайней мере равное числу дуг из позиции в переход. Фишки во входной позиции, которые разрешают переход, называются его разрешающими фишками. Например, если позиции р1 и р2 служат входами для перехода t1, тогда t1 разрешен, если р1 и р2 имеют хотя бы по одной фишке. Для перехода t3 с входным комплектом позиция р3 должна иметь не менее 3 фишек для разрешения перехода t3.

Определение. Переход маркированной сети Петри с маркировкой , разрешен, если для всех , .

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

>Переход t3 I(t3) = и O(t3) = разрешен каждый раз, когда в р2 будет хотя бы одна фишка. Переход t3 запускается удалением одной фишки из позиции р2 и помещением одной фишки в позицию р3 и р4 (его выходы). Переход t4, в котором I(t4) = и O(t4) = запускается удалением по одной фишке из позиций р4 и р5, при этом одна фишка помещается в р5 и две в р6 (рис. 2).

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

Источник

Курсовая работа: Использование сетей Петри в математическом моделировании

Курсовая работа на тему:

Использование сетей Петри в математическом моделировании

§2. Сетевое планирование

§3. Математические модели с использованием сетей Петри

§4. Построение динамической модели на основе сети Петри

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

§6. Моделирование процесса обучения с помощью вложенных сетей Петри

Список используемой литературы

Введение

Развитие ЭВМ и программного обеспечения приводит к ускорению и облегчению выполнения каждого шага моделирования. Увеличение быстродействия ЭВМ и развитие графического интерфейса позволяет получать и отображать результаты в графическом виде в темпе решения. При системном подходе к моделированию должен рассматриваться весь комплекс вопросов: планирование, проведение и обработка результатов вычислительного эксперимента.

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

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

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

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

Нами поставлены следующие задачи:

изучить литературу по теме;

изучить сетевое планирование;

рассмотреть применение сетевых моделей;

рассмотреть математические модели с использованием сетей Петри;

рассмотреть построение динамической модели на основе сети Петри.

§1. О сетях Петри

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

В другом подходе весь процесс проектирования и определения характеристик проводится в терминах сетей Петри. В этом случае задача заключается в преобразовании представления сети Петри в реальную информационную систему. [1]

Несомненным достоинством сетей Петри является математически строгое описание модели. Это позволяет проводить их анализ с помощью современной вычислительной техники (в том числе с массово-параллельной архитектурой). [2]

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

позволяет моделировать простые и цветные (CPN) сети Петри;

позволяет моделировать сети Петри со сложной структурой (включением подсетей-блоков в основную сеть) и большим количеством мест и переходов;

позволяет исследовать сети Петри на ограниченность (безопасность), наличие тупиков и достижимость разметок;

предоставляет удобный интерфейс пользователю.

Ни один из существующих программных комплексов моделирования сетей Петри не удовлетворяет этим требованиям.

Разработана система имитационного моделирования сетей Петри в трехуровневой архитектуре клиент-сервер. В основу системы было положено объектно-ориентированное описание сетей Петри в UML-нотации (Unified Modeling Language). Система реализована с помощью CASE-технологии DoomXL, разработанной в ЦОС и ВТ МФТИ. Применение современной промышленной СУБД Informix US в качестве серверной части системы позволяет:

хранить большие массивы данных по структуре сетей Петри;

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

Кроме того, примененный объектно-ориентированный подход позволяет реализовать модели сетей Петри со сложной структурой.

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

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

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

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

§2. Сетевое планирование

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

Наиболее распространенными направлениями применения сетевого планирования являются:

целевые научно-исследовательские и проектно-конструкторские разработки сложных объектов, машин и установок, в создании которых принимают участие многие предприятия и организации;

планирование и управление основной деятельностью разрабатывающих организаций;

планирование комплекса работ по подготовке и освоению производства новых видов промышленной продукции;

строительство и монтаж объектов промышленного, культурно-бытового и жилищного назначения;

реконструкция и ремонт действующих промышленных и других объектов;

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

Использование методов сетевого планирования способствует сокращению сроков создания новых объектов на 15-20%, обеспечению рационального использования трудовых ресурсов и техники.

Наибольшее распространение получило графическое представление сетевой модели на плоскости, называемое сетевым графиком.

Для быстрого «погружения» в постановку и решение задач сетевого планирования рассмотрим простейший пример, заимствованный нами из монографий.

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

Некоторые из этих подзадач должны предшествовать другим (например, задача «взять яйцо» должна предшествовать задаче «разбить яйцо»). Ряд подзадач может выполняться параллельно (например, задачи «взять яйцо» и «растопить жир»). Шеф-повар хотел бы выполнить заказ как можно быстрее, при этом предполагается, что число его помощников не ограничено.

Необходимо распределить работу среди помощников так, чтобы заказ был выполнен за минимально возможное время.

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

Давайте представим исходную задачу в виде графа. Каждая вершина графа представляет собой подзадачу, а каждая дуга (x,y) представляет требование, что задача y не может выполняться до тех пор, пока не завершено выполнение задачи x. Граф задачи показан на рисунке:

Период времени Помощник 1 Помощник 2

1. Взять яйцо Взять жир

2. Разбить яйцо Положить жир на сковороду

4. Вылить яйцо на сковороду

5. Ждать, пока яичница не изжарится

Автоматизируем процесс построения решения задачи, модифицируя алгоритм топологической сортировки, проиллюстрированный программой, следующим образом: while (Граф не пуст)

Распечатать эту группу узлов с указанием, что эти подзадачи

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

Удалить из графа данные вершины и инцидентные дуги>

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

typedefstruct Leader *Lref; // Тип: указательназаголовочныйузел.

typedefstruct Trailer *Tref; // Тип: указатель на дуговой узел.

// Описание типа заголовочного узла.

int Key; // Информационноеполе.

int Count; // Количество предшественников.

// Описание типа дугового узла.

Lref Head; // Указатель на список заголовочных узлов.

Lref Tail; // Указатель на фиктивный элемент

// в конце списка заголовочных узлов.

int z; // Количество узлов, не имеющих предшественников.

Head = Tail = new (Leader); z = 0; >;

Lref p,q; // Рабочие указатели.

p = Head; Head = NULL;

< q->Next = Head; Head = q; >

Lref Spisok:: L (int w)

// Функция возвращает указатель на ведущего с ключом w.

while (h->Key! =w) h = h->Next;

// В списке нет элемента с ключом w.

Tail = new (Leader); z++;

h->Count = 0; h->Trail = NULL; h->Next = Tail;

Lrefp,q; // Рабочие указатели.

Lref S,U; // Рабочие указатели.

if (p->Count==0) // Включение (*p) в список ведущих.

t = new (Trailer); t->Id = q; t->Next = p->Trail;

p->Trail = t; q->Count += 1;

Функции F и Н заданы матрицами

Фрагмент графа достижимости для сети Петри приведен на рис3.

[6]

§4. Построение динамической модели на основе сети Петри

1. Проверка синтаксиса функциональной модели и вывод динамической модели.

Динамическая модель строится на основании функциональной модели и синтезируется пакетом Design/IDEF автоматически во время проверки синтаксиса функциональной модели. Для того, чтобы проверка стала возможной, необходимо разрешить эмуляцию CPN-моделей. Это делается путем установки метки CPN в окне Edit-Set Options-Methodology-Simulations. После установки метки в строке меню главного окна появляется новое меню CPN.

Для проверки синтаксиса необходимо вызвать команду «Check CPN Syntax» в данном меню и в появившемся окне указать параметры проверки. По окончании проверки появляется окно с отчетом, где указываются ошибки (если есть), а на функциональной модели появляются элементы сети Петри.

2. Краткие теоретические сведения о сетях Петри.

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

Она представляет собой разновидность ориентированного графа, включающего в себя вершины двух типов: позиции и переходы. Позиции символизируют состояния и обозначаются как pi, а переходы обозначают собой действия (переходы из одного состояния в другое) и обозначаются как tj. Позиции и переходы соединены направленными дугами fk, каждая из которых имеет свой вес wk. Дуги также можно разделить на два типа: дуги, направленные от позиции к переходам, (p-t) и дуги, направленные от переходов к позициям (t-p). Исходя из этого, сеть Петри может быть формально представлена как совокупность множеств:

Каждая позиция может быть маркирована, т.е. содержать некоторое число фишек. Если обозначить числа фишек, находящихся в i-й позиции pi, как mi, то маркировка всей сети: M = . Тогда полное определение сети Петри, включая данные о началь-ной маркировке, можно записать в виде:

3. Отладка динамической модели.

Если в результате проверки синтаксиса функциональной модели были обнаружены ошибки, то их список будет выведен в окне отчета. В процессе устранения ошибок удобно переходить от одной ошибки к другой с помощью команды «Next Reference»/»Previous Ref-erence» меню Select. Все ошибки показываются выделением.

4. Надписывание позиций.

Для надписывания какой-либо позиции сети Петри необходимо сначала создать метку (команда Create Label), затем ее выделить и вызвать команду «Place Name» меню CPN. После этого достаточно указать надписываемый объект.

5. Надписывание переходов.

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

После того, как переход подписан в левом нижнем углу блока появляется квадрат, который подтверждает, что блок подписан.

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

Защита запрещает переход в соответствии с условиями на переменные, указанные в выражениях смежных дуг. Для ее установки требуется создать метку, содержащую выражение для защиты, затем командой «Guard» меню CPN она привязывается к переходу.

Кодовый сегмент определяет сегмент в коде Standard ML, который выполняется в эмуляторе Design/CPN всякий раз, когда будет срабатывать переход.

Задержка определяет время, которое характеризует продолжительность срабатывания перехода.

6. Надписывание дуг.

Каждая дуга может иметь свое имя и выражение, которые задаются как присоединяемые метки.

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

Выражение дуги характеризует мультинабор фишек, которые двигаются по дуге при любом срабатывании перехода, являющегося входным для дуги. Присоединение осуществляется аналогично вызовом пункта «Arc Expression» меню CPN.

7. Удаление и скрытие динамической модели.

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

При анализе сети Петри основное внимание уделяется, как правило, трем направлениям.

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

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

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

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

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

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

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

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

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

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

введены дополнительные виды вершин-переходов;

в любую позицию может входить не более одной дуги и выходить также не более одной.

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

Т-переход («исполнение», «простой переход»). Его графическое представление аналогично представлению вершины-перехода сети Петри (рис.4, слева). Переход срабатывает при наличии метки во входной позиции и отсутствии ее в выходной позиции. Формально это можно записать так:

Т-переход позволяет отразить в модели занятость некоторого устройства (подсистемы) в течение некоторого времени, определяемого параметром t (d). F-nepexod («разветвление»). Графическое представление приведено на рис.4 в центре. Срабатывает при тех же условиях, что и Т-переход:

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

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

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

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

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

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

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

Рассмотрим некоторые из них.

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

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

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

В целях повышения компактности и наглядности Е-сети для обозначения макропозиций используют специальные символы:

Аналогичным образом, путем композиции N однотипных переходов могут быть получены макропереходы всех типов: XN, YN, JN.

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

Рис.6. Пример описания вычислительной системы в виде Е-сети

На рисунке использованы следующие обозначения:

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

§6. Моделирование процесса обучения с помощью вложенных сетей Петри

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

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

Вложенные сети Петри.

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

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

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

Системно-автономный шаг, который соответствует срабатыванию непомеченного перехода в системной сети;

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

Пример вложенной сети Петри рассмотрен ниже.

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

Проиллюстрируем возможности вложенных сетей Петри для получения модели процесса обучения с подсистемами различного уровня. Рассмотрим модель процесса интерактивного обучения показанная на рис.7. В этой модели каждый обучаемый моделируется одной фишкой, обозначаемой переменной vars: STUDENT, которая соответствует целочисленному коду обучаемого. При этом информация об истории прохождении курса конкретным студентом теряется после того, как процесс обучения завершен. Кроме того, в модели на рис.7 отсутствует возможность дифференцированного оценивания успешности обучения. Также не предусмотрена возможность неудачного завершения курса, поскольку число попыток изучения материала и тестирования не ограничено. И, наконец, нет возможности моделировать взаимодействие учащихся.

Подготовка Обучение Тестирование Оценивание Принятие решения

приход обучаемого в систему (срабатывание перехода t₁ ), создание в системной сети SN сателлитной сети ЕN_s , в виде фишки s; в свою очередь, в сателлитной сети переменная s относится к цветовому множеству STUDENT;

выбор учебного модуля и начало процесса обучения срабатывание переходов t₁₁ ;

завершение процесса обучения и выбор тестов срабатывание переходов t₁₃ ;

Кроме описанных событий сеть ЕN_s , позволяет оценить количество баллов, набранных учащимся в процессе изучения модуля. Для этого введены дополнительные ресурсы, задаваемые цветовыми множествами:

и соответствующие переменные:

var β: BALL, var γ: FAILURE.

Рис.8. Вложенная сеть Е_s

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

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

Заключение

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

Источник