close

Вход

Забыли?

вход по аккаунту

?

Olenev

код для вставкиСкачать
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное
образовательное учреждение высшего образования
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ
В. Л. Оленев
МОДЕЛИРОВАНИЕ СИСТЕМ
ПРИ ПОМОЩИ СЕТЕЙ ПЕТРИ
Учебно-методическое пособие
Санкт-Петербург
2017
УДК004
ББК 32.81
О53
Рецензент
кандидат технических наук, доцент
Н. Н. Майоров
Утверждено
редакционно-издательским советом университета
в качестве учебно-методического пособия
Оленев, В. Л.
О53 Моделирование систем при помощи сетей Петри: учеб.-метод.
пособие / В. Л. Оленев. – СПб.: ГУАП, 2017. – 35 с.
Издается для бакалавров, обучающихся по направлению «Информатика и вычислительная техника» для использования при выполнении проектов по дисциплине «Моделирование» и проведении
исследований и разработок по теме дипломных работ. Дается описание сетей Петри как наиболее часто применяемого математического
аппарата для моделирования динамических и параллельных систем
и методы их анализа. Приведено задание на семестровый студенческий проект и пример реализации такого проекта.
УДК 004
ББК 32.81
©
©
Оленев В. Л., 2017
Санкт-Петербургский государственный
университет аэрокосмического
приборостроения, 2017
ВВЕДЕНИЕ
В последние годы моделирование используется повсеместно:
в авиастроении, автомобилестроении, космической и мобильной
индустрии, экономике, юриспруденции и других вещах, без которых жизнь современного человека уже сложно представить. Многие модели отражают работу сложных и громоздких систем, которые состоят из большого числа составляющих, которые должны
взаимодействовать между собой. Именно поэтому моделирование
становится все более необходимым элементом проектирования,
разработки и анализа сложных систем. Оно позволяет обнаружить
ошибки на ранних этапах проектов, значительно уменьшить само
время разработки, а также в дальнейшем использовать полученные
модели для тестирования и исследований. В данном курсе для исследования и анализа сложных многокомпонентных систем предлагается использовать формальный механизм сетей Петри.
В методическом пособии дан краткий теоретический курс по сетям Петри, необходимый для выполнения проекта. Далее приведен
процесс формирования задания на проект и само задание. Пособие
заканчивается упрощенным примером реализации студенческого
проекта с комментариями.
Обучение по данной дисциплине построено в соответствии со
стандартами всемирной инициативы CDIO – это международный
проект, направленный на устранение дисбаланса между теорией
и практикой в инженерном образовании. CDIO предполагает усиление практической направленности обучения, а также введение
системы проблемного и проектного обучения. Задачей инициативы
является обучение студентов, в основе которого лежит освоение инженерной деятельности в соответствии c моделью «Conceive (Планировать) – Design (Проектировать) – Implement (Производить) –
Operate (Применять)». Согласно концепции CDIO, модернизация базового инженерного образования заключается в подготовке выпускников к комплексной инженерной деятельности на основе высокой
научной подготовки в комбинации с практическими знаниями и
навыками организации работ. Она включает в себя изучение потребностей рынка в продуктах инженерной
деятельности и поиск возможностей для их
удовлетворения, планирования производства
продукции, проектного менеджмента и так
далее. Инициатива CDIO имеет три основных
цели – обучение студентов, способных:
3
• овладеть глубокими знаниями технических основ;
• руководить процессом создания и эксплуатации новых продуктов и систем;
• понимать важность и последствия воздействия научного и технологического прогресса на общество.
Основной целью внедрения CDIO является то, что выпускники
приобретут опыт реальной работы в проектах, управления проектами и коммуникативные навыки, в дополнение к базовым предметным знаниям. Это приведет к увеличению спроса на таких студентов на рынке труда после окончания учебы, к повышению конкурентоспособности университета на мировом рынке образовательных услуг. Для сотрудников университета это дает возможность
роста как специалистов в инженерной области, заводить полезные
знакомства с представителями отрасли. Также высокий уровень
знаний и опыта выпускников к тому же, является большим плюсом
для университета, повышающим его рейтинг.
В дополнение к теоретическим знаниям, данное учебно-методическое пособие помогает организовать работу над совместными студенческими проектами и таким образом повысить у студентов коммуникативные навыки, навыки работы в команде, лидерства, получить полезные компетенции по защите результатов своей работы.
4
1. ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ
1.1. Декомпозиция сложных систем
Декомпозиция – это научный метод, использующий структуру
задачи и позволяющий заменить решение одной большой задачи
решением серии меньших задач, пусть и взаимосвязанных, но более простых. Таким образом, декомпозиция системы – это разделение ее на достаточно независимые части.
Декомпозиция позволяет рассматривать любую исследуемую
систему как сложную, состоящую из отдельных взаимосвязанных
подсистем, которые, в свою очередь, также могут быть разделены
на части. В качестве систем могут выступать не только материальные объекты, но и процессы, явления и понятия.
При декомпозиции руководствуются следующими правилами:
1. Каждое расчленение образует свой уровень.
Исходная система располагается на нулевом уровне. После её
разделения получаются подсистемы первого уровня. Разделение
этих подсистем или некоторых из них приводит к появлению подсистем второго уровня и т. д.
Упрощённое графическое представление декомпозированной
системы называется её иерархической структурой.
2. Система разбивается только по одному, постоянному для всех
уровней, признаку.
В качестве признака декомпозиции может быть:
• функциональное назначение подсистем,
• конструктивное устройство,
• структурные признаки,
• предметные характеристики,
• и другие.
Вычленяемые подсистемы в сумме должны полностью характеризовать систему. Но при этом вычленяемые подсистемы должны
взаимно исключать друг друга. Например, если при перечислении
частей автомобиля опустить, допустим, мотор, то функциональное
взаимодействие остальных подсистем не обеспечит нормальное
функционирование всей системы (автомобиля) в целом. К неоднозначности может привести использование на одном уровне взаимно пересекающихся подсистем, например, «двигатели электрические» и «двигатели переменного тока», так как неясно куда же
нужно в таком случае отнести асинхронный двигатель.
3. Глубина декомпозиции.
5
Степень подробности описания и количество уровней определяются требованиями обозримости и удобства восприятия получаемой иерархической структуры, её соответствия уровням знания
работающему с ней специалисту.
Обычно в качестве нижнего (элементарного) уровня подсистем
берут такой, на котором располагаются подсистемы, понимание
устройства которых или их описание доступно исполнителю. Таким образом, иерархическая структура всегда субъективно ориентирована: для более квалифицированного специалиста она будет
менее подробна.
Число уровней иерархии влияет на обозримость структуры:
много уровней – задача труднообозримая, мало уровней – возрастает число находящихся на одном уровне подсистем и сложно установить между ними связи. Обычно, в зависимости от сложности
системы и требуемой глубины проработки, выделяют 3–6 уровней.
В процессе проектирования декомпозиция неразрывно связана
с последующей композицией, то есть сборкой и увязкой отдельных
частей (подсистем) в единую систему с её проверкой на реализуемость в целом, совместимость (особенно подсистем, принадлежащих разным ветвям) и согласованность параметров (восходящее
проектирование). В процессе согласования может возникать потребность в новой, корректирующей декомпозиции [1].
1.2. Блочный принцип построения модели системы
При проведении моделирования систем наиболее ответственными и наименее формализованными моментами являются проведение границы между системой и внешней средой, упрощение описания системы и построение сначала концептуальной, а затем формальной модели системы. Модель должна быть адекватной, иначе
невозможно получить положительные результаты моделирования,
т. е. исследование процесса функционирования системы на неадекватной модели вообще теряет смысл. Под адекватной моделью понимается модель, которая с определённой степенью приближения
на уровне понимания моделируемой системы разработчиком модели отражает процесс её функционирования во внешней среде.
Наиболее рационально строить модель функционирования системы по блочному принципу. При этом могут быть выделены три
автономные группы блоков модели. Блоки первой группы представляют собой имитатор воздействий внешней среды на систему; блоки второй группы являются собственно моделью процесса
6
функционирования исследуемой системы; блоки третьей группы –
вспомогательные, служат для машинной реализации блоков двух
первых групп, а также для фиксации и обработки результатов моделирования.
В данном методическом пособии приводится пример формализованного подхода к построению структуры будущей модели по
блочному принципу. Он может дать общее представление о том,
как подойти к процессу разбиения системы на различные составляющие, однако не обязателен к использованию в том виде, в котором
он представлен.
Механизм перехода от описания процесса функционирования
некоторой гипотетической системы к модели этого процесса включает следующие этапы.
1. Для наглядности вводится представление об описании свойств
процесса функционирования системы, т. е. об её концептуальной
модели MK как совокупности некоторых элементов, условно изображённых квадратами так, как показано на рис. 1. Эти квадраты
представляют собой описание некоторых подпроцессов исследуемого процесса функционирования системы, воздействия внешней
среды и т. д.
2. Переход от описания системы к её модели в этой интерпретации сводится к исключению из рассмотрения некоторых второстепенных элементов описания (элементы 5–8, 39–41, 43–47). Предполагается, что они не оказывают существенного влияния на ход
процессов, исследуемых с помощью модели.
3. Часть элементов (14, 15, 28, 29, 42) заменяется связями h1,
отражающими внутренние свойства системы.
1
2
3
4
5
–
6
–
7
–
8
–
9
10
11
12
S1
13
14
15
16
S2
17
18
19
20
S3
21
22
23
24
25
26
27
28
29
28
29
32
33
34
35
36
37
38
39
–
40
–
41
–
42
43
–
44
–
45
–
46
–
47
–
Рис. 1. Концептуальная модель системы
7
4. Часть элементов (10, 11, 24, 25, 38) образует входное воздействие x.
5. Выделяют элементы (1–4), характеризующие воздействие
внешней среды v1.
6. Возможны комбинированные замены: элементы (9, 18, 19,
32, 33) заменены внутренней связью h2 и воздействием внешней
среды v2.
7. Группируют элементы (22, 23, 36, 37), отражающие воздействие системы на внешнюю среду y.
8. Оставшиеся элементы системы группируют в блоки S1, S2,
S3, отражающие процесс функционирования исследуемой системы. Каждый из этих блоков достаточно автономен, что выражается в минимальном количестве связей между ними. Поведение этих
блоков должно быть хорошо изучено, и для каждого из них построена математическая модель, которая, в свою очередь, может содержать ряд подблоков.
9. Построенная таким образом блочная модель (рис. 2) процесса
функционирования исследуемой системы предназначена для анализа характеристики этого процесса, который может быть проведён при машинной реализации полученной модели.
После перехода от описания моделируемой системы к её модели MK, построенной по блочному принципу, необходимо построить
формальное описание процессов, происходящих в различных блоках. Формальная модель представляет собой совокупность соотношений (например, уравнений, логических условий, операторов),
определяющих характеристики процесса функционирования системы в зависимости от структуры системы, алгоритмов поведения,
параметров системы, воздействий внешней среды, начальных условий и времени. Такая модель является результатом формализации
процесса функционирования исследуемой системы, т. е. построения
формального описания процесса с необходимой в рамках проводимого исследования степенью приближения к действительности.
V2 Внешняя среда
V1
Система
x
S1
h1
S2
h2
y
S3
Рис. 2. Блочная модель системы
8
Таким образом, формализации процесса функционирования
любой системы должно предшествовать изучение составляющих
его явлений. В результате появляется содержательное описание
процесса, которое представляет собой первую попытку чётко изложить закономерности, характерные для исследуемого процесса, и
постановку прикладной задачи. Содержательное описание является исходным материалом для последующих этапов формализации:
построения формализованной схемы процесса функционирования
системы и математической модели этого процесса. Для моделирования процесса функционирования системы на ЭВМ необходимо
преобразовать математическую модель процесса в соответствующий моделирующий алгоритм и машинную программу [2].
1.3. Общие сведения о сетях Петри
Сети Петри – это мощный инструмент исследования систем, который делает возможным моделирование системы путем математического представления ее в виде сети Петри. Анализ сетей Петри дает возможность получить важную информацию о структуре и динамическом
поведении моделируемой системы. Эта информация полезна для оценки данной системы и выработки предложений по ее усовершенствованию и изменению. Развитие сетей Петри основывалось на применении
их к моделированию и проектированию систем. Но вычислительные
системы очень сложны, часто громоздки, включают множество взаимодействующих между собой компонент и различных подсистем. При
этом каждая компонента также может быть достаточно сложной.
Сети Петри являются самым распространенным в настоящее
время формализмом, описывающим структуру и взаимодействие
параллельных систем и процессов. Отличительной особенностью
сетей Петри является также их способность отображать динамку
поведения системы. Язык сетей Петри обладает формальной семантикой, наглядным графическим представлением и выразительностью. Его развитый математический аппарат позволяет проверять
множества свойств моделируемого объекта и вырабатывать различные методы анализа. Благодаря этим особенностям сети Петри
нашли широкое применение в сфере моделирования [3].
Для иллюстрации понятий теории сетей Петри самым удобным
является графическое представление. Теоретико-графовым представлением сети Петри является двудольный ориентированный
мультиграф, а структура сети Петри представляет собой совокупность позиций и переходов.
9
Граф сети Петри обладает двумя типами узлов, показанными на рис. 3.
Позиции и переходы соединяют ориентированные дуги (стрелки), при этом некоторые
– переход
из них направлены от позиций к переходам, а
другие – от переходов к позициям. Сеть Петри
Рис. 3. Два типа
допускает существование кратных дуг от одной
узлов сети Петри
вершины графа к другой. Кратность дуги означает, что позиция и переход связаны не одной дугой, а несколькими. Например, кратность дуги равная четырем показывает, что
между позицией и переходом нарисованы четыре дуги, направленные в одну сторону.
Каждая дуга должна соединять элементы, принадлежащие разным множествам элементов (P и T). Таким образом, в сети Петри дуг
между двумя переходами или двумя позициями быть не может [4].
Пример простейшей сети Петри показан на рис. 4. На нем видно,
что сеть Петри состоит из трех позиций p0, p1, p2 и трех переходов
t0, t1, t2. Кратность дуг обозначается фигурной стрелкой, над ней
подписывается число исходящих дуг, либо просто проводится необходимое число дуг между элементами сети Петри. Например, на
рис. 4 видно, что кратность дуги из позиции p0 в переход t0 равна
трем. А кратность дуги из p2 в t2 равна двум (по числу дуг).
Маркировка сети Петри – это присвоение фишек ее позициям.
Фишка (или маркер) – это примитивное понятие сетей Петри подобно позициям и переходам. Она может символизировать любой
объект, движущийся по сети Петри. Фишки могут быть присвоены
только позициям. Число и положение фишек при выполнении сети
Петри могут изменяться. Это зависит от ее структуры.
Маркировка µ сети Петри С – (Р, Т, I, О) есть функция, отображающая множество позиций Р в множество
t0
p0
p1
неотрицательных целых чисел N. Маркировка (или разметка) µ может быть также
3
5
представлена в виде n‑вектора µ = (µ1, µ2,
…, µn), где n = |P| и каждое µi ∈ N, i = 1,
…, n. Вектор µ сопоставляет число фиt1
шек в позиции сети Петри с конкретной
t2
p2
позицией pi. Число фишек в позиции pi
записывается как µ(pi). Например, если
в третьей позиции сети Петри стоят две
фишки, то запись будет выглядеть так:
Рис. 4. Пример
µ(pi) = 2.
сети Петри
– позиция
10
Маркированная сеть Петри М = (С, µ) есть совокупность структуры сети Петри С = (Р, Т, I, О) и маркировки µ и может быть записана в виде М = (Р, Т, I, О, µ). На графе сети Петри фишки изображаются точкой, которая ставится в позицию сети Петри (рис. 4,
позиция p1). Если число фишек в позиции сети Петри велико, то
вместо необходимого их числа допускается запись в этой позиции
числа, которое означает число фишек в данной позиции (рис 4, позиция p0). Так как число фишек, которое может быть определено
для каждой позиции, неограниченно, то в целом для сети Петри существует бесконечно много маркировок.
Чаще всего маркированная сеть Петри записывается как
М = (Р, Т, I, О, µ0), где µ0 – начальная маркировка (разметка) сети
Петри; µi, i = 1, …, n, обозначаются все следующие маркировки, которые получены в процессе выполнения сети Петри. Для сети Петри, изображенной на рис. 4, µ0 = {5, 1, 0}.
1.4. Представление системы в виде сети Петри
Простое представление системы сетью Петри основано на двух
основополагающих понятиях: событиях и условиях.
События – это действия, происходящие в системе. Возникновением событий управляет состояние системы. Состояние системы
может быть описано множеством условий.
Условие есть предикат или логическое описание состояния системы. Условие может принимать либо значение «истина», либо
значение «ложь». События являются действиями, а каждое событие в системе когда-либо происходит. Для того чтобы событие произошло, необходимо выполнение соответствующих условий.
В сети Петри условия моделируются позициями, события –
переходами. При этом входы перехода являются предусловиями
соответствующего события, выходы – постусловиями. Возникновение события равносильно запуску соответствующего перехода.
Выполнение условия представляется фишкой в позиции, соответствующей этому условию. Запуск перехода удаляет разрешающие
фишки, представляющие выполнение предусловий и образует новые фишки, которые представляют выполнение постусловий [5].
В качестве примера рассмотрим задачу моделирования простой
бортовой сети малого спутника (рис. 5). Бортовой компьютер находится в состоянии ожидания до тех пор, пока не появится информация с датчиков, он эту информацию обрабатывает и посылает в систему передачи данных на Землю.
11
Антенна
Датчик 1
Датчик 2
Бортовой компьютер
Коммутатор
Датчик 3
Датчик 4
Рис. 5. Схема работы бортового компьютера малого спутника
Условиями для такой системы являются:
• бортовой компьютер ждет;
• бортовой компьютер свободен;
• данные обработаны;
• данные готовы к отправке.
Событиями, заставляющими сеть переходить в новое состояние,
являются:
• данные с датчиков поступили;
• начало обработки данных;
• завершение обработки данных;
• отправка данных на Землю.
Сеть Петри для бортовой сети малого спутника показана на рис. 6.
Очевидно, что для того чтобы эта сеть Петри работала, в позицию «Бортовой компьютер ждет» необходимо поставить фишку.
Данные
с датчиков
поступили
Начало
обработки
данных
Бортовой
компьютер
свободен?
Завершение
обработки
данных
Данные
обработаны?
Отправка
данных
на Землю
Данные готовы
к отправке?
Бортовой компьютер
ждет
Рис. 6. Сеть Петри для бортовой сети малого спутника
12
Переход «данные с датчиков поступили» всегда разрешен, поэтому
фишки из него могут поступать бесконечно.
1.5. Анализ сетей Петри
Анализ сетей Петри помогает получить важную информацию
о структуре и динамическом поведении моделируемой системы.
Эта информация может быть полезна для оценки моделируемой
системы и выработки предложений по ее усовершенствованию и
изменению. Анализ результатов может свидетельствовать о том,
какие действия происходят, какие состояния им предшествовали и
какие состояния примет система после выполнения действия, в каких состояниях она пребывала или не пребывала, какие состояния
в принципе недостижимы.
1.5.1. Безопасность
Одно из важнейших свойств сети Петри, которая должна моделировать реальное устройство, – безопасность. Позиция сети Петри
является безопасной, если число фишек в ней никогда не превышает
единицы. Сеть Петри безопасна, если безопасны все позиции сети.
Безопасность – очень важное свойство для устройств аппаратного
обеспечения. Если позиция безопасна, то число фишек в ней равно 0
или 1. Следовательно, позицию можно реализовать одним триггером.
1.5.2. Ограниченность
Безопасность – это частный случай более общего свойства сетей
Петри – ограниченности. Некоторые соображения относительно
реального ограничения на аппаратную реализацию позиций позволяют прийти к заключению, что безопасность – необязательное
требование. Безопасность позволяет реализовать позицию триггером, но в более общем случае можно использовать счетчик. Однако любой аппаратно-реализованный счетчик ограничен по максимальному числу, которое он может представить.
Позиция является k-безопасной или k-ограниченной, если число
фишек в ней не может превышать целое число k. Сеть Петри называется k‑ограниченной, если число фишек в каждой ее позиции не
может превышать числа k.
1.5.3. Сохранение
Для некоторых сетей Петри важным свойством является сохранение. В таких сетях фишки никогда не создаются и не уничто13
жаются, и общее число их в сети остается постоянным. Такая сеть
Петри называется строго сохраняющей. Строгое сохранение – это
очень сильное ограничение. Например, из него немедленно следует, что число входов в каждый переход должно равняться числу выходов. Если бы это было не так, запуск перехода изменил бы число
фишек в сети.
1.5.4. Активность
Следующей важной характеристикой сети Петри является активность. Активность показывает, какие переходы сети могут
быть запущены (из текущей маркировки или потенциально). Переход называется активным, если он не заблокирован (не тупиковый). Это не означает, что переход разрешен только в данной
маркировке, он может быть разрешен в принципе когда-нибудь
в течение выполнения сети Петри. Если переход активен, то всегда
возможно перевести данную сеть из ее текущей маркировки в маркировку, в которой запуск перехода станет разрешенным. Переход
сети Петри называется потенциально запустимым в маркировке
µ, если существует маркировка µ′, в которой он разрешен.
Тупик в сети Петри – это переход (или множество переходов),
которые не могут быть запущены. Тупики можно разбить на категории по уровню активности и определить для сети Петри с маркировкой µ следующим образом:
уровень 0 – переход tj обладает активностью уровня 0, если он
никогда не может быть запущен;
уровень 1 – переход tj обладает активностью уровня 1, если он
потенциально запустим, т. е. если существует такая маркировка,
в которой он разрешен;
уровень 2 – переход tj обладает активностью уровня 2, если для
всякого целого n существует последовательность запусков, в которой tj присутствует по крайней мере n раз;
уровень 3 – переход tj обладает активностью уровня 3, если существует бесконечная последовательность запусков, в которой tj
присутствует неограниченно часто;
уровень 4 – переход tj обладает активностью уровня 4, если для
всякой маркировки µ′ существует такая последовательность запусков, что tj разрешен в каждом из них.
Переход, обладающий активностью уровня 0, называется пассивным. Переход, обладающий активностью уровня 4, называется
активным. Сеть Петри обладает активностью уровня i, если каждый ее переход обладает активностью уровня i.
14
1.5.5. Достижимость и покрываемость
Все задачи, которые рассматриваются выше, касаются достижимых маркировок. Достижимость определяет, достижима ли маркировка µ′ из маркировки µ. Задача достижимости, быть может, основная задача анализа сетей Петри. Многие другие задачи анализа
можно сформулировать в терминах задачи достижимости.
Задача покрываемости состоит в определении для сети Петри
с начальной маркировкой µ и маркировкой µ′, существует ли достижимая маркировка µ″, в которую можно перейти из маркировки µ через µ′.
В некоторых случаях при анализе сети Петри можно игнорировать содержимое некоторых позиций и принимать во внимание
сравнение или покрытие содержимого нескольких самых важных
позиций, которые и дадут необходимые для анализа данные. Такие
задачи называются задачами достижимости подмаркировки и покрываемости подмаркировки.
1.5.6. Деревья достижимости
Дерево достижимости представляет собой множество достижимости сети Петри. Деревом достижимости сети Петри называется дерево, вершины которого помечены маркировками, которые достигаются в процессе выполнения этой сети. Корневая вершина дерева достижимости помечена начальной маркировкой µ0, а дуги, исходящие из
вершины, помечены всеми возможными переходами t, которые могут сработать при маркировке µ0, и ведут соответственно в вершины,
помеченные непосредственно достижимыми маркировками µ1, µ2,…
Далее, из каждой вершины µ1, µ2,… выходят новые дуги в соответствии со всеми возможными из этой маркировки переходами, и т. д.
Дерево представляет все возможные последовательности запусков переходов. Всякий путь в дереве, начинающийся в корне, соответствует допустимой последовательности переходов.
Однако зачастую, при моделировании сложных систем, получившееся дерево достижимости может оказаться бесконечным.
Бесконечное дерево достижимости сложно для проведения анализа.
Поэтому для превращения его в полезный инструмент анализа был
создан алгоритм, ограничивающий дерево до конечного размера.
Для сведения дерева достижимости к конечному представлению
используется символ ω, обозначающий бесконечное число фишек
в позиции. Значок ω ставится в том случае, если в каждой новой
маркировке число фишек в этой позиции возрастает, и растет до
бесконечности.
15
В разработанном алгоритме каждая вершина дерева достижимости связывается с расширенной маркировкой µi, в которой число
фишек в позиции может быть либо неотрицательным целым, либо
ω. Каждая вершина дерева достижимости классифицируется как:
• граничная – вершина, которая еще не была обработана алгоритмом;
• терминальная – маркировка, в которой отсутствуют разрешенные переходы;
• дублирующая – маркировка, уже ранее встречавшиеся в дереве,
никакие последующие маркировки рассматривать нет необходимости, так как все они будут аналогичны маркировкам, полученным
из места первого появления дублирующей маркировки в дереве;
• внутренняя – вершина, которая уже была обработана алгоритмом.
В процессе работы алгоритм превращает граничные вершины
в терминальные, дублирующие или внутренние. Действие алгоритма начинается с определения граничной вершины, которая является корнем дерева. Алгоритм выполняется до тех пор, пока имеются
граничные вершины:
1) выберем граничную вершину, которую необходимо обработать;
2) если в дереве имеется другая вершина, не являющаяся граничной (уже обработана алгоритмом), и с ней связана та же маркировка, то обрабатываемая вершина дублирующая;
3) если для маркировки в обрабатываемой вершине ни один из
переходов не разрешен, то это – терминальная вершина;
4) для каждого перехода, который разрешен в текущей маркировке, создается новая вершина дерева достижимости. Маркировка, связанная с этой вершиной, определяется для каждой позиции
следующим образом:
а) если в какой-то позиции маркировки, связанной с предыдущей вершиной, стоит символ ω, то и для текущей вершины тоже
ставится ω;
б) если в маркировке, связанной с предыдущей вершиной, в конкретной позиции число фишек меньше, чем в текущей маркировке, и видно, что дальше число фишек бесконечно увеличивается, то
в текущей вершине на эту позицию также ставится ω;
в) в противном случае в вершину ставится маркировка, получающаяся после срабатывания перехода, подписанного на стрелке;
5) предыдущая вершина переопределяется как внутренняя, текущая вершина становится граничной (еще не обработанной алгоритмом);
16
6) когда все вершины дерева терминальные, дублирующие или
внутренние, алгоритм останавливается.
Более подробные и углублённые сведения по теоретической части курса «Моделирование» можно найти в учебном пособии «Моделирование систем» [6].
17
2. РУКОВОДСТВО ПО ВЫПОЛНЕНИЮ
ЛАБОРАТОРНЫХ РАБОТ
2.1. Формирование проектной команды
Для выполнения лабораторных работ студенты должны самостоятельно разделиться по проектным командам, в каждой из которых
должно быть 4–5 человек. На весь семестр каждой команде дается
одно общее задание (проект), который студенты выполняют самостоятельно, получая необходимые консультации преподавателя.
В каждой команде выбирается руководитель проекта. Руководителем проекта является студент, который несет ответственность
за выполнение проекта, организовывает работу в команде.
Состав проектных команд согласовывается с преподавателем.
В течение семестра проектная команда показывает преподавателю
результаты работы над проектом в основных контрольных точках,
и таким образом согласовывает правильность выбранного направления работы.
По окончании семестра проект защищается командой на проекторе. Команда должна полностью описать свою работу над заданием, показать основные достижения. Докладывается команда в полном составе.
Для защиты проекта студентами оформляется презентация, демонстрирующая все этапы реализации проекта, и заканчивающаяся выводами.
2.2. Формирование задания на проект
Задание на проект студенты формируют самостоятельно. Для
этого выбирается крупная система, моделирование работы которой
студенты будут пытаться осуществить. Например, такой системой
может быть:
• аэропорт,
• конструкторское бюро,
• солнечная система,
• болото и т. п.
Система должна быть достаточно сложной, чтобы иметь возможность ее моделировать в соответствии с требованиями текущего методического пособия.
Проектная команда должна в достаточной степени представлять
следующее:
• как функционирует выбранная система;
18
• из каких составляющих она состоит;
• какими данными обмениваются между собой эти составляющие.
Выбранное задание согласовывается с преподавателем и закрепляется за проектной командой на весь семестр. Менять задание по
ходу семестра не разрешается.
2.3. Этапы выполнения проекта
Вся работа над проектом делится на 4 основных этапа:
1) декомпозиция системы и построение архитектурной схемы;
2) построение сети Петри для этой системы;
3) анализ полученной сети Петри;
4) исследование системы при помощи сети Петри.
2.3.1. Этап 1: Декомпозиция системы
В соответствии с выбранным заданием команда студентов должна спроектировать архитектурную схему будущей модели, отталкиваясь от своих знаний о системе, которую они будут моделировать.
Для этого необходимо проделать следующие действия:
1. Разбить систему на более простые подсистемы, минимально
связанные друг с другом по внутренней функциональности, но непосредственно взаимодействующие. Таких подсистем должно быть
не менее 5 штук. Например, для небольшого самолета: электропитание, пассажирский салон, кабина пилота, багажное отделение, двигатели.
2. В свою очередь каждую из подсистем разбить на 5 составляющих. Каждая из таких составляющих отвечает за определенную
функцию, которую выполняет подсистема. Например, для электропитания в самолете: лампы подсветки в салоне, генератор, система управления, внешние огни и система экстренного оповещения.
Таким образом, получится схема из нескольких подсистем,
включающих функциональные составляющие. Упрощенный пример такой декомпозиции показан на рис. 7. В примере всего 4 подсистемы, по 3–4 составляющие в каждой.
1. Для каждой составляющей необходимо четко определить и
записать в отчет:
• основная функциональность составляющей;
• входные данные;
• выходные данные;
• соотношение с другими составляющими (возможно, и из другой подсистемы);
19
Система
Составляющая
№1
Составляющая
№2
Подсистема № 1
Составляющая
№1
Составляющая
№2
Подсистема № 2
Составляющая
№3
Составляющая
№4
Составляющая
№3
Составляющая
№4
Составляющая
№1
Составляющая
№2
Составляющая
№1
Составляющая
№2
Подсистема № 3
Составляющая
№3
Подсистема № 4
Составляющая
№3
Составляющая
№4
Рис. 7. Декомпозиция системы (шаг 1)
Система
Составляющая
№1
Составляющая
№2
Подсистема № 1
Составляющая
№1
Составляющая
№2
Подсистема № 2
Составляющая
№3
Составляющая
№4
Составляющая
№3
Составляющая
№4
Составляющая
№1
Составляющая
№2
Составляющая
№1
Составляющая
№2
Подсистема № 3
Составляющая
№3
Подсистема № 4
Составляющая
№3
Составляющая
№4
Рис. 8. Декомпозиция системы (шаг 2)
20
2. После этого необходимо отобразить описанные взаимосвязи
на архитектурной схеме системы. Связи должны выставлять только между составляющими. Сами подсистемы между собой не связываются. Пример схемы, отражающей взаимодействие между составляющими системы, показан на рис. 8.
2.3.2. Этап 2: Составление сети Петри
После проведения декомпозиции системы необходимо построить Сеть Петри, описывающую работу этой системы по архитектурной схеме, разработанной на Этапе 1. При построении сети Петри
необходимо руководствоваться следующим правилом. Условия
моделируются позициями сети Петри, события – переходами. При
этом входы перехода являются предусловиями соответствующего
события, выходы – постусловиями. Возникновение события равносильно запуску соответствующего перехода.
Далее проводится маркировка сети Петри. То есть в ней расставляются фишки, отвечающие за разные данные (или предметы), которыми обмениваются составляющие сети. Фишки должны
расставляться так, чтобы модель функционировала однозначно, и
четко описывала логику событий, происходящих в оригинальной
моделируемой системе. По результатам составления сети Петри необходимо продемонстрировать преподавателю ее работу, показать
ее начальную маркировку, а также один (или несколько) вариантов возможной конечной маркировки. Если система работает бесконечно, необходимо обозначить, какая маркировка будет в конце
каждого цикла работы.
2.3.3. Этап 3: Анализ сети Петри
Провести анализ сети Петри по параметрам, описанным в п. 1.4
данного методического учебного пособия:
1) безопасность;
2) ограниченность;
3) сохранение;
4) активность (есть ли тупики в сети Петри).
Анализ достижимости проводится посредством построения дерева достижимости. Однако, для крупных систем дерево достижимости может быть достаточно громоздким, поэтому при работе над
проектом студентам разрешается построить только основные ветви
дерева достижимости. Таких ветвей может быть 3–4 штуки, и выбираются они в соответствии с логикой работы модели и моделируемой системы.
21
2.3.4. Этап 4: Исследование параметров системы
После построения и анализа сети Петри необходимо придумать
три параметра моделируемой системы и определить, каким образом их можно проанализировать при помощи механизма теории сетей Петри. Параметры могут отражать какие-либо количественные
характеристики вашей системы, зависимости между ними и т. п.
Параметры выбираются таким образом, чтобы можно было указать
конкретное место в сети Петри, которое говорит о значении этого
параметра. Если такого места в сети Петри нет, то можно внести изменения в сеть Петри (добавив несколько позиций или переходов),
чтобы построенной системы и полученной на ее основе сети Петри
было достаточно для исследования системы.
22
3. ПРИМЕР РЕАЛИЗАЦИИ ПРОЕКТА
В данном разделе приведен пример реализации студенческого
проекта, начиная с выбора задания и заканчивая Этапом 4. Приведенный пример значительно проще, чем те проекты, которые необходимо реализовывать проектным командам в течение семестра, но
он показывает, как выполнять задания и в какую сторону двигаться.
Для данного примера возьмем задание «Автозаправочная станция». Она будет состоять из места, где хранится топливо, самих заправочных колонок, магазина и склада, где хранятся товары.
3.1. Этап 1: Декомпозиция системы «АЗС»
Разобьём нашу моделируемую систему на три основные подсистемы:
1. Система заправки автомобилей, отвечающая за обслуживание автомобилей на АЗС.
2. Система сервиса, отвечающая за продажу бензина и товаров
в магазине.
3. Вспомогательная система, отвечающая за контроль за системой снабжения колонок топливом и освещение АЗС.
По заданию, каждая из полученных подсистем должна быть разбита на составляющие, и для каждой из составляющих должны быть
определены функциональность, входные данные, выходные данные.
1. Рассмотрим систему заправки автомобилей. Принцип ее работы состоит в том, что бензин поступает из топливного хранилища
(баков) в заправочные колонки, а потом в автомобиль.
 Топливные баки:
 входные данные: нет (не рассматриваем поставки бензина на АЗС);
 выходные данные: бензин в колонки.
 Колонки:
 входные данные: бензин из баков, разрешение на заправку от
системы контроля топлива, электроэнергия;
 выходные данные: бензин в автомобиль.
 Автомобиль:
 входные данные: бензин из колонки;
 выходные данные: водитель, идущий оплачивать бензин в магазин.
2. Рассмотрим систему сервиса и обслуживания клиентов. Товар
на полки поступает со склада, а пассажир автомобиля его покупает.
После этого Пассажир садится в автомобиль и уезжает с заправки.
23
 Склад:
 входные данные: освещение (не рассматриваем поставки товара на склад);
 выходные данные: товары в магазин.
 Магазин:
 входные данные: освещение, товары со склада;
 выходные данные: товары, купленные клиентом.
 Пассажир:
 входные данные: купленные товары;
 выходные данные: клиент уходит в машину.
3. Рассмотрим вспомогательные системы. Генератор дает энергию для освещения. Освещение нужно колонкам (подсветка), магазину, складу и системе контроля топлива для индикации. Система
контроля топлива получает данные из топливных баков и дает разрешение на включение колонки.
 Генератор:
 входные данные: нет (АЗС автономная);
 выходные данные: электроэнергия в модуль освещения.
Заправка а\м
Сервис
Топливные баки
Склад
Колонки
Магазин
Машины
Пассажир
Вспомогательные системы
Освещение
Генератор
Контроль
топлива
Рис. 9. Архитектурная схема АЗС
24
 Освещение:
 входные данные: электроэнергия из генератора;
 выходные данные: электроэнергия на колонки, в магазин и
склад, на систему контроля топлива.
 Система контроля топлива:
 входные данные: электроэнергия, индикация из топливных баков о наличии топлива;
 выходные данные: разрешение на заправку в колонки.
На основании произведенной декомпозиции и определения всех
зависимостей между составными частями АЗС, можно нарисовать
архитектурную схему АЗС, она показана на рис. 9.
На этом Этап 1, декомпозиция системы, завершен и можно переходить к Этапу 2.
3.2. Этап 2: Составление сети Петри «АЗС»
На втором этапе архитектурную схему АЗС следует преобразовать в сеть Петри, которая полностью отражает работу АЗС. Для
решения этой задачи можно сначала составить Сети Петри для отдельных подсистем. Составляется она, руководствуясь правилом,
что условия превращаются в позиции, а события – в переходы сети
Петри. При этом, не обязательно, что в подсистеме будет столько
позиций, сколько составляющих было в подсистеме. Сеть Петри
должна правильно отразить логику работы, и если необходимо добавить больше позиций и переходов – можно смело это сделать. Например, сеть Петри для подсистемы заправки автомобилей отражена на рис. 10.
Колонка
готова
к заправке?
В топливном баке
есть топливо?
Подаем
топливо
на колонку
Заправляем
машину
Водитель
идет
в магазин
Водитель
Разрешение
Подаем
пришел
подачи электричество
из магазина
топлива
в колонки
Индикация
наличия
топлива
p0
Машина
заправлена?
p1
p2
Рис. 10. Сеть Петри
для подсистемы
заправки автомобилей (шаг 1)
25
t3
t2
t1
t0
t4
t5
t8
Далее присваиваем каждой позиции и переходу имя:
• в топливном баке есть топливо – p0;
• подаем топливо на колонку – t0;
• колонка готова – p1;
• заправляем машину – t1;
• машина заправлена – pКолонка
2;
В топливном
баке
готова
Машина
• водитель
идет
в магазин
– t2;
есть топливо?
к заправке?
заправлена?
• индикация наличия топлива – t3;
Колонка– t ;
• разрешение
топлива
4
В топливномподачи
баке
готова
Машина
есть электричество
топливо?
• подаем
в колонки – t5;заправлена?
к заправке?
• водитель пришел
из магазинаЗаправляем
– t8.
Подаем
Водитель
Таким образом, топливо
получаем схему,машину
показанную на рис.
11.
идет
на колонку
в магазин
Перейдем к следующей подсистеме, описывающей
магазин.
Подаем отражена
Заправляем
Сеть Петри для магазина
на
рис.
12.
Водитель
топливо
машину
идет которое не
Водитель
Разрешение
Подаем
Далее Индикация
присваиваем
каждой
позиции
и переходу
имя,
на колонку
в магазин
пришел
подачи электричество
наличия
должно повторяться
в рамках
всей
сети
Петри,
поэтому
из магазина необходитоплива
в колонки
топлива
Водитель
Разрешение
Подаем
подачиp1 электричество p2 пришел
из магазина
топлива
в колонки
Индикация
p0
наличия
топлива
p0
p1
p2
t2
t1
t0
t3
t5
t4
t8
t1
t0
Рис. 11. Сеть Петри для подсистемы
t5
t8
t3
t4
Товар
Покупатель
заправки
автомобилей
(шаг
2)
На складе есть
товар?
разложен
по полкам?
завершил
покупки?
Товар
разложен
по полкам?
На складе есть
товар?
Покупатель
завершил
покупки?
Продаем
товар
Несем товар
на полки
t2
Покупатель
уходит
в машину
Продаем
Покупатель
Несем товар
Подаем
товар
уходит
Подаем на полки Приходит
электричество
в машину
электричество
покупатель
в
магазин
на склад
из машины
Подаем
Подаем
Приходит
электричество
покупатель электричество
в магазин
на склад
из машины
p4
p5
Рис. 12. Сеть Петри для подсистемы
магазина АЗС (шаг 1)
p4
26
t7
t6
t9
p5
t10
t2
t6
t7
p0
p1
p0
p2
p1
p2
мо учитывать имена,t0данные на предыдущем
этапе. Также
нужно
t2
t1
иметь в виду, чтоt некоторые
переходы
уже
присутствуют
в сети
Пеt
t8 t2
t4
t1 5
3 t0
три предыдущей подсистемы,
и уже имеют
имена:
t5
t8
t3
t4
• на складе есть
товар
– p3;
• несем товар на полки – Товар
t6;
Покупатель
На складе
есть по полкам
разложен
завершил
• товар
разложено
– p4;
товар?
Покупатель
поТовар
полкам?
покупки?
• продаем
товар
На складе
есть – t7; разложен
завершил
товар?покупатель
по полкам?
• приходит
из машины – покупки?
t2 (уже есть в подсистеме
топлива);
• покупательНесем
завершил
покупкиПродаем
– p5;
Покупатель
товар
уходит
• водитель идет
– t8; товар
нав машину
полки
Продаем
Покупатель
Несем товар
в машину
• подаем электричество
на
склад
–
t
;
товар9
уходит
на полки
в машину
• подаем электричество в магазинПодаем
– t10.
Подаем
Приходит
Таким
образом, получаем
схему, показанную на рис. 13.
электричество
покупатель электричество
Подаем
в
магазин
Подаем
на склад
Приходит
Перейдем
к следующей
подсистеме,
описывающей вспомогаиз машины
электричество
покупатель электричество
в
магазин
тельные на
системы.
Сеть
Петри
для
вспомогательных
систем отражесклад
из машины
на на рис. 14.
p4
p5
p4
p5
t7
t6
t9
t6
t9
t7 t10
t2
t10
t2
Рис. 13. Сеть Петри для подсистемы
магазина АЗС (шаг 2)
Есть
энергия?
Есть
энергия?
Выдаем
энергию
Выдаем
энергию
Топливо
и электричество
Топливо
есть?
и электричество
есть?
Подача эл-ва
в контр.топлива
Подача эл-ва
в контр.топлива
Включаем
колонку
Включаем
колонку
Подача
Подача
Подача Индикация
наличия
эл-ва
эл-ва
эл-ва
Индикация
Подача
топлива
в
колонки Подача
на склад Подача
в магазин
наличия
эл-ва
эл-ва
эл-ва
в колонки на склад в магазин топлива
Рис. 14. Сеть Петри для вспомогательной подсистемы
p6
p7
p8
АЗС
(шаг 1)
p6
p7
p8
t6
t6t5
t5
t7
t9
t9
t7t10
t10
27
t4
t3 t
4
Товар
разложен
по полкам?
На складе есть
товар?
Покупатель
завершил
покупки?
Далее присваиваем каждой позиции и переходу имя, которое не
должно повторяться в рамках всей сети Петри, поэтому необходимо учитывать имена,
на предыдущих
этапах.
Также нужно
Продаем
Покупатель
Несем данные
товар
товаруже присутствуют
уходит в сетях
полки
иметь в виду, чтонанекоторые
переходы
в машину
Петри предыдущих подсистем, и уже имеют имена:
• генератор включен – p6
Подаем
Подаем
Приходит
электричество
• выдаем
энергию – tпокупатель
электричество
11;
в магазин
на склад – p ; из машины
• есть энергия
7
• подача электричества в колонки – t5 (уже есть в подсистеме топлива);
• подача электричества в магазин
– t10 (уже
p4
p5 есть в подсистеме
сервиса);
• подача электричества на склад – t9 (уже есть в подсистеме сервиса);
• подача электричества
в контроль топлива
– t12;
t7
t6
• топливо и электричество
есть
–
p
;
8
t10
t9
t
• включаем колонку
– t24 (уже есть в подсистеме топлива);
• индикация наличия топлива – t3 (уже есть в подсистеме топлива).
Таким образом, получаем схему, показанную на рис. 15.
После того, как сеть Петри составлена для каждой из подсиТопливо
стем – составляем общую сеть
все связи между
ЕстьПетри, учитывая
и электричество
энергия?
подсистемами и отдельными
составляющимиесть?
в этих подсистемах.
При этом искомые сети Петри, полученные на предыдущем шаге,
могут претерпеть некоторые изменения, поскольку логика, заложенная в них,Выдаем
может не совсем соответствовать
ожиданиям разраПодача эл-ва
Включаем
ботчика модели.
Предварительный
вариант сети Петри
после объэнергию
в контр.топлива
колонку
единения в одну сеть показан на рис. 16.
Пунктирной линией на рис. 16 показаны
три подсистемы.
Подача
Подача
Подача Индикация
Далее необходимо
провести
Петри, чтобы отобраналичия
эл-ва
эл-варазметку
эл-ва сети
топлива
колонки Фишки
на склад не
в магазин
зить динамику еев работы.
имеют различий,
но будут отображать разные параметры, однако сеть Петри должна учитывать
этот факт.
p6
p7
p8
t6
t5
t7
t9
t10
t3
t4
Рис. 15. Сеть Петри для вспомогательной подсистемы
АЗС (шаг 2)
28
p0
p1
t3
p2
p3
p4
t1
t0
p6
p7
p8
t6
t5
p0
p1
t8
t7
t10
t6
t2
t9
t4
p5
t7
p2
p3
p4
p5
Рис. 16. Предварительная сеть Петри для АЗС
t1
t8
t7
t6
t10
t9 t2
t
Разметим
4 сеть Петри так, чтобы она отражала процесс обслужиp0
p1
p2
p3
p4
p5
t3
t0
вания одной машины. Для этого нам нужно иметь бензин в баках,
а также нужно выдавать индикацию об этом в систему контроля
p6 t
p7
p8
t7
t8 этом
t6 в позиции
1
0
топливаt – tпоэтому
нужно
будет
две фишки
p , при
t10 0
t2
t9
3
t4
одна из них будет
символизировать
бензин, а вторая – индикацию.
t6
t7
Одновременно с этимt5нужно подать
в систему электричество – ставим фишку в позицию p6. И фишка в позиции p3 будет говорить о
p6
p7
p8
том, что на складе уже
есть товар.
Размеченная
сеть Петри показана на рис. 17.
t
t
6
7
t5
p0
p1
t3
p3
p4
t1
t0
t4
p0
p2
p1
t0
p2
p3
t11
p6 t1
t3
t9
p7
p8
t6
t5
t6
t2
p4
t6
p5
t7
t10
t8
p5
t8
t7
t10
t9
t7
p6
4
p7
p8
t6
t7
Рис. 17. Размеченная сеть Петри для АЗС
p0
p0
p1
t0
p1
p2
t1
p2
t11
t2
p3
p3
t
p4
t6
p4
29
p5
t7
p5
t8
Однако, можно улучшить работу сети Петри, поскольку ее функционирование не будет следовать той логике, которую хотелось бы
заложить:
1. Для начала, обратим внимание, что у нас нет фишки, говорящей о том, что машина приехала на заправку. Добавим фишку в позицию p1.
2. Для того, чтобы начать заправку автомобиля, нужно, чтобы
были выполнены 3 условия: есть бензин, есть разрешение от системы контроля топлива и есть электричество. Поэтому логичнее сделать условия, описываемые позициями p0, p8 и p7 предусловиями
для выполнения действия t0. Поэтому удалим переходы t4 и t5, а
все три стрелку пусть идут в переход t0. Таким образом, без наличия фишек в p0, p8 и p7 колонка не начнет заправлять машину – как
и было нужно.
3. Чтобы машина не могла уехать не заправленной, а фишка,
символизирующая ее, ждала фишку, символизирующую бензин –
для осуществления перехода t1 зададим кратность 2 (дорисуем еще
одну стрелку из p1 в t1). Из t1 в p2 будет по-прежнему идти одна
стрелка, и в p2 придет одна фишка, которая будет символизировать
заправленную машину.
4. Переход t2, символизирующий то, что водитель пошел оплачивать топливо и купить что-то в магазине, сейчас может забрать
фишку из позиции p2, которая символизирует заправленную машину, а это неправильно. Поэтому мы удалим переход t2, а в позицию p2 будем осуществлять переход прямо из t1. Таким образом получится, что заправленная машина останется в p2, а водитель сразу
после заправки уйдет в магазин p4.
5. Аналогично пункту 3, чтобы без электричества нельзя было вынести со склада товар в магазин, добавляем дополнительную стрелку
из p3 в t6. Чтобы без электричества и наличия покупателя нельзя было
продать товар в магазине, добавляем две дополнительные стрелки из
p4 в t7. Чтобы без электричества система контроля топлива не могла
разрешить заправку, добавляем дополнительную стрелку из p8 в t0.
6. Для того, чтобы отобразить, что заправленная машина со
счастливым водителем, который совершил покупки, уехала с заправки, добавим переход t11 в, который будем переходить из позиции p2, причем переход будет иметь кратность 2, чтобы вывести из
системы обе фишки (автомобиля и водителя).
7. Для того, чтобы снабдить электричеством все необходимые
части АЗС, нужно соответствующее количество фишек в p7, поэтому сделаем кратность стрелки из t6 в p7 равную четырем.
30
p0 t
3
t0
t4
p1
t1
p2
p3 t
9
t6
t2
p4
t7
t10 p5
t8
Таким образом, получим сеть Петри, отображенную на рис. 18.
t
t7
t0
t8
t6 мы удаляли
Однако,t она
не будет1финальной, поскольку
t10 и добавляt2
3
p6
p7
p8 t9
t
ли переходы,4а значит необходимо будет перенумеровать их, чтобы
не было пропусков номеров.
t6
t7
Сеть Петри с перенумерованными
позициями и переходами поp6 t5
p7
p8
казана на рис. 19.
Этап 2 успешно завершен,
сетьt Петри для модели АЗС построеt6
7
на. Теперь можно переходить
к Этапу
3 – анализу сети Петри.
t5
p0
p1
p0
t3
t0
p1
t0
t1
p2
t11
p3
p2
t11
p3 t
9
p5
p4
t7
t10 p5
t8
t7
t10
t8
t6
t1
p6
t3
t6
p4
4
p8 t9
p7
t6
p6
t7
4
p7
p8
t6
t7
Рис. 18. Доработанная сеть Петри для АЗС
p0
p1
p0
t3
t0
p1
t0
t1
p2
t2
p3
p2
t2
p3 t
7
p6
p4
4
p7
p6
p5
t5
t8
p5
t6
t6
t5
t8
p8 t7
t9
t10
4
p7
p8
t9
p0
t4
t4
t1
t3
p4
t10
p1 Рис. 19.
p2 Доработанная
p3сеть Петри
p4
t2
p5
для АЗС с новой нумерацией переходов
p0
t3
t0
t0
t3
p1
t1
p2
t2
p9
t1
p6
p3 t
7
p7
t4
t4
p8 t7
p4
t5
t8
t5
t8
p5
t6
t6
31
3.3. Этап 3: Анализ сети Петри для «АЗС»
Безопасность: Данная сеть Петри не является безопасной, поскольку число фишек в ней может превышать единицу.
Ограниченность: Данная сеть Петри ограниченная, поскольку
число фишек в каждой ее позиции не превышает числа 3.
Сохранение: Сеть Петри не является сохраняющей, поскольку
общее число фишек в сети постоянно меняется.
Активность: Сеть Петри активна, поскольку в ней нет тупиков.
В данном методическом пособии будет приведена только одна,
самая сложная ветка дерева достижимости для сети Петри АЗС, которая отражает, как машина была заправлена, водитель оплатил
заправку и уехал. Эта ветка дерева представлена на рис. 20.
210100100
t9
Начальная маркировка
210100040
t3
Подали электричество
110100041
t10
Пришла индикация, что бензин есть в баках
110100032
t0
Подали освещение на систему контроля топлива
020100020
t1
Выдали разрешение на заправку машины
001110020
t7
Машина заправлена, водитель ушел в магазин
001210010
t8
Подали освещение на склад
001220000
t4
Подали освещение в магазин
001030000
t5
Товары со склада поступили на полки магазина
001001000
t6
Покупатель купил что-то в магазине и оплатил бензин
002000000
t2
Покупатель сел обратно в машину
000000000
Машина уехала с заправки
Рис. 20. Ветка дерева достижимости
(заправка автомобиля)
32
p0
p1
p2
p3
t11
p4
p5
Финальная разметка сети Петри получилась
00000000. Но не
t6
t0
t1
t8
t7
обязательно
она будет
такой во всех случаях
и
во
всех
проектах
–
t9
t10
t3
это зависит то того, как составлена сеть Петри и какая логика работы в нее заложена.
На этом закончен Этап 3 и можно переходить к последнему этаp6
p7
p8
пу – Этапу 4 Исследование
4 параметров системы.
t6
t7
3.4. Этап 4: Исследование параметров «АЗС»
На данном этапе нужно определить параметры системы, которые мы можем проанализировать при помощи сети Петри. В данном учебном пособии будет рассмотрен только один параметр – выберемp количество
было
заправлено
на АЗС.
p1 машин,
p2 которое
p3
p4
p5
t2
0
Для того, чтобы проанализировать
этот параметр
в сеть
Петри
нужно добавить еще одну позицию, которая
будет
являться
счетчиt4
t0
t1
t6
ков количества
уехавших
автомобилей.t На рис. 21t5это
позиция
p9,
t8
7
t3
выделенная жирным. Когда автомобиль уезжает с заправки – информация об этом попадает в эту позицию. Таким образом, сколько
машин уехало – столько
фишек
окажется
в позиции p9.
p6
p7
p8
Очевидно, что в текущем
примере, который
ориентирован на об4
служивание только одной
машины
–
этот
параметр
будет равен 1.
t9
t10
Но если выход модели замкнуть на вход и после обслуживания
автомобиля вернуть все фишки в начальные позиции, то система
будет работать циклически. В этом случае количество автомобилей
будет возрастать до бесконечности.
p0
p1
t0
p2
p3
t2
p4
t4
t1
t5
t8
t7
t3
p5
t6
p9
p6
4
p7
p8
t9
t10
Рис. 21. Анализ параметра
«количество заправленных машин»
p1
p0
t0
t
p2
t1
p3
p4
t4
t2
t7
33
p5
t5
t8
t6
p1
p0
t0
p2
p3
p4
t4
t2
t1
t7
t3
p6
4
t9
p7
p5
t5
t8
t6
p8
t10
Рис. 22. Сеть Петри АЗС
с возможностью бесконечного функционирования
Пример того, как можно заставить сеть Петри для АЗС работать
бесконечно показан на рис. 22. Для этого из перехода t2 нарисуем
пять новых дуг (на рис. 22 показаны жирными стрелками):
• две дуги в позицию p0, чтобы вернуть туда две фишки, отвечающие за индикацию наличия топлива и само топливо;
• одну дугу в позицию p3, чтобы вернуть туда одну фишку, отвечающую за наличие товара на складе;
• одну дугу в позицию p6, чтобы вернуть туда одну фишку, отвечающую за работоспособность генератора;
• одну дугу в позицию p1, чтобы вернуть туда одну фишку, отвечающую за прибытие машины на заправку.
Таким образом, после выполнения перехода t2, который означает, что машина уехала с заправки, мы вернем все фишки на свои
места, как было в начальной разметке {2,1,0,1,0,0,1,0,0}.
Таким образом, в рамках данного примера мы создали архитектурную схему простой автозаправочной станции, затем создали ее
модель при помощи механизма сетей Петри. После этого мы проанализировали сеть Петри и исследовали на ней параметр «количество заправленных машин». Работа выполнена успешно и соответствует поставленным задачам на студенческий проект.
34
Список использованных источников
1. Хорошев А. Н. Введение в управление проектированием механических систем: учеб. пособие. Белг., 1999. 372 с.
2. Тюкин В. Н. Моделирование систем: учеб. пособие. Вологда:
ВоГТУ, 2009. 134 с.
3. Оленев В. Л. Проектирование программных моделей сетевых протоколов для встроенных систем: дис. ... канд. техн. наук:
05.13.11: защищена 07.02.2012: утв. 30.08.2012. СПб., 2011. 235 с.
4. Котов В. Е. Сети Петри. М.: Наука, 1984. 160 с.
5. Питерсон Дж. Теория сетей Петри и моделирование систем.
М.: Мир, 1984. 264 с.
6. Оленев В. Л. Моделирование систем: учеб. пособие. СПб.:
ГУАП, 2015. 95 с.
СОДЕРЖАНИЕ
Введение.................................................................................... 1. Теоретические сведения........................................................... 1.1. Декомпозиция сложных систем.......................................... 1.2. Блочный принцип построения модели системы..................... 1.3. Общие сведения о сетях Петри............................................ 1.4. Представление системы в виде сети Петри........................... 1.5. Анализ сетей Петри.......................................................... 1.5.1. Безопасность............................................................. 1.5.2. Ограниченность......................................................... 1.5.3. Сохранение............................................................... 1.5.4. Активность............................................................... 1.5.5. Достижимость и покрываемость................................... 1.5.6. Деревья достижимости................................................ 2. Руководство по выполнению лабораторных работ......................... 2.1. Формирование проектной команды..................................... 2.2. Формирование задания на проект....................................... 2.3. Этапы выполнения проекта................................................ 2.3.1. Этап 1: Декомпозиция системы.................................... 2.3.2. Этап 2: Составление сети Петри.................................... 2.3.3. Этап 3: Анализ сети Петри........................................... 2.3.4. Этап 4: Исследование параметров системы..................... 3. Пример реализации проекта..................................................... 3.1. Этап 1: Декомпозиция системы «АЗС»................................ 3.2. Этап 2: Составление сети Петри «АЗС»................................ 3.3. Этап 3: Анализ сети Петри для «АЗС»................................. 3.4. Этап 4: Исследование параметров «АЗС». ............................ Список использованных источников ............................................. 3
5
5
6
9
11
13
13
13
13
14
15
15
18
18
18
19
19
21
21
22
23
23
25
32
32
35
35
Учебное издание
Оленев Валентин Леонидович
МОДЕЛИРОВАНИЕ СИСТЕМ
ПРИ ПОМОЩИ СЕТЕЙ ПЕТРИ
Учебно-методическое пособие
Публикуется в авторской редакции.
Компьютерная верстка С. Б. Мацапуры
Сдано в набор 07.02.17. Подписано к печати 06.03.17.
Формат 60×84 1/16. Усл. печ. л. 2,09.
Уч.-изд. л. 2,25. Тираж 50 экз. Заказ № 71.
Редакционно-издательский центр ГУАП
190000, Санкт-Петербург, Б. Морская ул., 67
Документ
Категория
Без категории
Просмотров
0
Размер файла
1 293 Кб
Теги
olenen
1/--страниц
Пожаловаться на содержимое документа