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

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

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

Использование сетей Петри для моделирования процессов синхронизации. Задача Д.Питерсона. PERT-диаграммы и сети Петри. Примеры.

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

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

Среди задач синхронизации: задача о взаимном исключении, производителе/потребителе , обедающих мудрецах , чте­нии/записи и др.

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

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

Но в большей части эта «очевидность» является результатом того, что сети Петри были определены и раз­работаны главным образом для этой цели.

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

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

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

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

PERT-диаграмма и сеть Петри взаимосвязаны: PERT-диаграмма легко преобразуется в сеть Петри. Каждый этап PERT-диаграммы представляется позицией, причинно-следственные связи — пере­ходами. Диаграмма на рис. 3.35 может быть преобразована в экви­валентную сеть Петри, изображенную на рис. 3.36.

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

Конвейерная обработка, описанная в разд. 3.3.2, является част­ным случаем производственной системы . Сборочная линия — другой пример производственной системы. Производственные систе­мы и сборочные линии могут быть промоделированы сетями Петри.

Одно из первых применений сетей Петри — применение в качестве средства генерации оптимального кода для компилятора с [ Фортрана CDC 6600.

Подход к решению этой задачи, предложенный , заключался в моделировании программы на Фортране | сетью Петри   способом,  подобным моделированию блок-схемы £(разд. 3.4.1).

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

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

         10y=x+1 ,

         20y=y+1,

         30z=x+y.

Они написаны таким образом, что оператор 10 предшествует опера­тору 20, но такая последовательность вовсе необязательна. Поря­док, в котором будут выполнены операторы 10 и 20 (или они будут выполнены одновременно), не имеет значения для программы.

Од­нако оператор 30 должен следовать только после операторов 10 и 20. После изменения упорядочения операторов необходимо рас­смотреть и поток управления. Этот анализ заключается в примене­нии условий Бернстайна для обеспечения детерминированности.

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

Это требует отображения переменных в регистры и упорядочения инструкций для получения полностью упорядоченной последовательности ин­струкций машинного языка.  CDC 6600 — это ЭВМ с несколькими регистрами и кратными функциональными блоками (разд. 3.3.3).

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

Сеть Петри, моделирующая программу и представляющая ограничения, налагаемые программой, объединя­ется с сетью Петри, моделирующей устройство управления CDC 6600 и представляющей ограничения, налагаемые аппаратным обе­спечением.

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

Две (или более) последовательности образуются вся кий раз, когда два (или более) перехода одновременно разрешены. Запуск одного перехода будет порождать одну последовательность; запуск другого перехода — другую. Например, сеть Петри на рис. 3.37 представляет последовательности abcdef, bacdef, abcedf, bacedf. После того как последовательности получены, вычисляются необходимые затраты времени на их выполнение, и наиболее быст­рая последовательность генерируется компилятором для действи­тельного выполнения.

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

Н2С204 →   2СОа + 2Н+ + 2е-

2е- + 2Н+ + Н202 → 2Н20.

Можно представить и реакции катализа. Соединение водорода и этилена образует этан (Н2 + С2Н4 → С2Н6) только в присутствии платины. Это отражено на рис. 3.39.

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

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

40 является моделью начальных стадий гражданского процесса.

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

В этой задаче существенно при­сутствует параллелизм, и поэтому она попадает в класс задач, для которых определены сети Петри.

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

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

Однако мы видели по крайней мере один пример (задача о чте­нии/записи), который нельзя промоделировать с помощью сети Петри.

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

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

Источник: https://studizba.com/lectures/10-informatika-i-programmirovanie/1621-lekcii-po-setjam-petri/30498-ispolzovanie-setej-petri-dlja-modelirovanija-processov-sinhronizacii.html

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

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

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

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

Оглавление

Введение

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

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

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

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

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

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

Заключение

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

Введение

Развитие ЭВМ и программного обеспечения приводит к ускорению и облегчению выполнения каждого шага моделирования.

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

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

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

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

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

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

Объект работы – сети Петри.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Разработана система имитационного моделирования сетей Петри в трехуровневой архитектуре клиент-сервер.

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

Применение современной промышленной СУБД Informix US в качестве серверной части системы позволяет:

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

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

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

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

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

Модель – это представление, как правило, в математических терминах того, что считается наиболее характерным в изучаемом объекте или системе.

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

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

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

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

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

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

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

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

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

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

Сетевое планирование – метод управления, основанный на использовании математического аппарата теории графов и системного подхода для отображения и алгоритмизации комплексов взаимосвязанных работ, действий или мероприятий для достижения четко поставленной цели. Разработаны в начале 50-х г. ХХ в.

Наиболее известны практически одновременно и независимо разработанные метод критического пути – МКП и метод оценки и пересмотра планов – PERT.

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

Основная цель сетевого планирования – сокращение до минимума продолжительности проекта.

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

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

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

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

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

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

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

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

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

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

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

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

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

Сетевая модель – информационная модель реализации некоторого комплекса взаимосвязанных работ, рассматриваемая как ориентированный граф без контуров, отображающий естественный порядок выполнения этих работ во времени; может содержать некоторые дополнительные характеристики (например, время, стоимость, ресурсы), относящиеся к отдельным работам и (или) к комплексу в целом. [5]

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

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

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

Взять яйцо – —> Разбить яйцо – —> Взять жир – —>

–> Положить жир на сковороду – —> Растопить жир – —>

–> Вылить яйцо на сковороду – —>

–> Ждать, пока яичница не изжарится – —> Снять яичницу

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

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

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

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

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

Рис.1. Граф задачи

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

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

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

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

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

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

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

3. Растопить жир

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

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

6. Снять яичницу

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

{Определить вершины, не имеющие предшественников.

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

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

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

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

#include

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

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

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

typedefstruct Leader

{

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

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

Tref Trail;

Lref Next;

};

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

typedefstruct Trailer

{

Lref Id;

Tref Next;

};

class Spisok {

private:

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

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

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

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

public:

Spisok () { // Инициализация списка заголовочных узлов.

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

Lref L (int);

void Poisk ();

void Vyvod ();

};

void Spisok:: Poisk ()

{

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

p = Head; Head = NULL;

while (p! =Tail)

{

q = p; p = p->Next;

if (q->Count==0)

{ q->Next = Head; Head = q; }

}

}

Lref Spisok:: L (int w)

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

{

Lref h = Head;

Tail->Key = w;

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

if (h==Tail)

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

{

Tail = new (Leader); z++;

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

}

return h;

}

void Spisok:: Vyvod ()

{

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

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

Tref t;

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

{ p->Next = U; U = p; }

t = t->Next;

}

q = q->Next;

}

q = U;

}

if (z! =0)

cout y;

p = A. L (x); q = A. L (y);

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

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

cout > x;

cout

Источник: https://www.bestreferat.ru/referat-140662.html

Medic-studio
Добавить комментарий