ВЛОЖЕННЫЕ СЕТИ ПЕТРИ И НАГРУЖЕННЫЕ МЕТКИ: РАСПРЕДЕЛЕННАЯ СИСТЕМА И РЕКУРСИЯ
Авторы:
1.
Новосибирский государственный технический университет
2.
Новосибирский государственный технический университет
Тип:
Статья
Страницы:
с 23
по 31
Статус:
Опубликован
Получено:
05.04.2015
Одобрено:
25.04.2015
Опубликовано:
25.04.2015
Классификаторы:
ВАК 05.12.2013 Системы, сети и устройства телекоммуникаций
ВАК 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
ВАК 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
ВАК 05.13.10 Управление в социальных и экономических системах
ВАК 05.13.18 Математическое моделирование, численные методы и комплексы программ
ВАК 05.13.19 Методы и системы защиты информации, информационная безопасность
УДК 681.3
ГРНТИ 20.01 Общие вопросы информатики
ГРНТИ 28.01 Общие вопросы кибернетики
ГРНТИ 49.01 Общие вопросы связи
ГРНТИ 50.01 Общие вопросы автоматики и вычислительной техники
ГРНТИ 82.01 Общие вопросы организации и управления
ВАК 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
ВАК 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
ВАК 05.13.10 Управление в социальных и экономических системах
ВАК 05.13.18 Математическое моделирование, численные методы и комплексы программ
ВАК 05.13.19 Методы и системы защиты информации, информационная безопасность
УДК 681.3
ГРНТИ 20.01 Общие вопросы информатики
ГРНТИ 28.01 Общие вопросы кибернетики
ГРНТИ 49.01 Общие вопросы связи
ГРНТИ 50.01 Общие вопросы автоматики и вычислительной техники
ГРНТИ 82.01 Общие вопросы организации и управления
Язык материала:
русский
Ключевые слова:
вложенные сети Петри, нагруженные метки, рекурсия, распределенные системы, факториал, комбинированный тип данных, горизонтальная и вертикальная синхронизации срабатывания переходов
Аннотация (русский):
Для моделирования параллельных процессов, сложных многоуровневых систем без дополнительных мест, переходов и их взаимосвязей, синхронизации разных потоков информации и представления в разных сетях одинаковых мест с разной маркировкой используются вложенные сети Петри. Альтернативой данного вида сетей являются сети с нагруженными метками, которые содержат дополнительную информацию о структуре системы или об истории её изменений. Сравнение подходов построения сетей Петри на основе вложенных сетей и сетей с нагруженными метками выполняется на примере анализа распределенной системы агентства проката автомобилей и решения рекурсивной задачи - нахождения факториала числа. Анализ распределенной системы агентства выполнен на основе двухуровневых вложенных сетей Петри с использованием вертикальной и горизонтальной синхронизации. Для сравнения осуществляется анализ на основе сетей с нагруженными метками в двух вариантах. В первом случае за основу берется структура системной сети, во втором - сеть состоит из трёх мест, к каждому из которых добавляется определенный набор типов данных для отображения возможных состояний системы. Нахождение факториала числа у вложенных сетей Петри осуществляется через вертикальную синхронизацию срабатывания переходов между системной сетью и элементными сетями, а при использовании нагруженных меток - через комбинированный тип данных мест сети. Переменная первого типа данных отображает значение величины искомого факториала, а во втором случае отслеживается значение текущей переменной, вычисленной на предыдущем шаге. Моделирование и автоматический анализ сетей Петри для данных примеров происходит в программной среде CPN Tools (Version 4.0.0).
Для моделирования параллельных процессов, сложных многоуровневых систем без дополнительных мест, переходов и их взаимосвязей, синхронизации разных потоков информации и представления в разных сетях одинаковых мест с разной маркировкой используются вложенные сети Петри. Альтернативой данного вида сетей являются сети с нагруженными метками, которые содержат дополнительную информацию о структуре системы или об истории её изменений. Сравнение подходов построения сетей Петри на основе вложенных сетей и сетей с нагруженными метками выполняется на примере анализа распределенной системы агентства проката автомобилей и решения рекурсивной задачи - нахождения факториала числа. Анализ распределенной системы агентства выполнен на основе двухуровневых вложенных сетей Петри с использованием вертикальной и горизонтальной синхронизации. Для сравнения осуществляется анализ на основе сетей с нагруженными метками в двух вариантах. В первом случае за основу берется структура системной сети, во втором - сеть состоит из трёх мест, к каждому из которых добавляется определенный набор типов данных для отображения возможных состояний системы. Нахождение факториала числа у вложенных сетей Петри осуществляется через вертикальную синхронизацию срабатывания переходов между системной сетью и элементными сетями, а при использовании нагруженных меток - через комбинированный тип данных мест сети. Переменная первого типа данных отображает значение величины искомого факториала, а во втором случае отслеживается значение текущей переменной, вычисленной на предыдущем шаге. Моделирование и автоматический анализ сетей Петри для данных примеров происходит в программной среде CPN Tools (Version 4.0.0).
Ключевые слова:
вложенные сети Петри, нагруженные метки, рекурсия, распределенные системы, факториал, комбинированный тип данных, горизонтальная и вертикальная синхронизации срабатывания переходов
вложенные сети Петри, нагруженные метки, рекурсия, распределенные системы, факториал, комбинированный тип данных, горизонтальная и вертикальная синхронизации срабатывания переходов
Введение Для верификации проектируемых моделей на семантические ошибки прибегают к использованию сетей Петри [1], которые являются четверкой N = (P, T, F, mi), где P = {p1, p2, …, pn} - множество мест; T = {t1, t2, …, tm} - множество переходов, таких как P T =; - отношение; mi: P N - начальная маркировка (размещение меток в местах сети Петри). Анализ сетей Петри позволяет выявить тупиковые состояния , мертвые переходы[2], зацикливания , а также проверять свойства ограниченности[3] сети, достижимости и покрываемости маркировок. Одним из популярных способов анализа свойств сети Петри является построение и исследование графа состояний. Граф состояний представляется четверкой , где V - множество вершин; E - множество рёбер между вершинами; - отображает в каждом ребре вершину, из которой оно получено, и вершину, к которой приводит выполнение срабатывания перехода, соответственно. Существует стандартный способ, когда происходит хранение информации обо всех посещенных состояниях сети, и альтернативный способ: метод плавающей линии [2], побиговое хеширование о состоянии [3], метод возможных ребер (comeback метод) [4], метод анализа пространства состояний [5-9]. Существует большое количество классов (общие сети GN; общие сети без петель LFN; ординарные сети PN, бесконфликтные сети CFN, сети со свободным выбором FCN, маркированные графы MG, автоматные сети SM) [10] и видов сетей Петри (временные сети, стохастические, ингибиторные, простые, цветные, иерархические, вложенные [11], возможные модификации и др.). Остановимся подробнее на вложенных сетях Петри, в частности, на двухуровневых системах, которые представлены набором: где - множество меток имен переменных и имен констант ; - множество меток, использующихся для вертикальной и горизонтальной синхронизации срабатывания переходов; - конечный набор обыкновенных (элементных в NPN) сетей Петри; - частичная функция пометки переходов, выделяющая некоторые переходы системной сети метками и некоторые переходы в элементных сетях метками ; SN - сеть высокого уровня, которую представляют набором: где - сеть; - язык выражений для представления переменных и констант; U - модель языка L; W - функция, сопоставляющая каждой дуге некоторое выражение размерности n, где и n - арность позиции, инцидентной дуге (x, y); M0 - начальная разметка сети. Моделирование распределенной системы на основе вложенных сетей Петри Одним из вариантов представления вложенных сетей Петри является использование списков в маркировке мест [12, 13], которой сходно со способами, предложенными в [14]. Отдельно выделим сети Петри с нагруженными меткам[4] и [15], которые, по сути, являются альтернативным представлением вложенных сетей. В нагруженных метках информация о некоторых из позиций сети закладывается в тип данных некоторой метки. Данная информация интерпретирует количество меток в позиции, состояние или тип данных. Рассмотрим подробнее вложенные сети и сети с нагруженными метками на примере агентства по прокату автомобилей (рис. 1). Вложенная сеть, моделирующая работу агенства, состоит из системной сети SN и двух элементных сетей EN1 и EN2, представляющих клиентов и автомобили, соответственно. Для того, чтобы учитывать какой именно автомобиль получил конкретный клиент, удобно использовать в качестве фишек пары элементов. В нашем случае рассматриваются пары клиент-автомобиль. Соответственно сеть SN будет содержать фишки следующих типов: атомарные черные, сетевые - автомобили, сетевые - клиенты и пары маркированных сетей (клиент - автомобиль). В системной сети SN фишками в позициях s1, s4 будут черные атомарные фишки (для позиций, представляющих пропозициональные условия); в позициях s5, s8 - сетевые фишки[5] - автомобили; в позициях s2, s3 - сетевые фишки - клиенты; в позициях s6, s7 - пары сетевых фишек (клиент, автомобиль). Приведем значения мест и переходов. Места: s2 - клиенты, желающие арендовать автомобиль; s3 - клиенты, обратившиеся за автомобилем в агентство; s4 - количество арендованных автомобилей; s5 - свободные автомобили; s6 - клиенты вместе с арендованными автомобилями; s7 - клиенты, которые хотят вернуть автомобиль в агентство; s8 - автомобили на мойке; c1 - клиенты, не нуждающиеся в автомобиле; c2 - клиенты, которые хотят арендовать автомобиль; c3 - клиенты, обратившиеся в агентство за автомобилем; c4 - клиенты, использующие автомобиль; c5 - клиенты, желающие вернуть автомобиль в агентство; c6 - клиенты, обратившиеся в агентство, чтобы вернуть автомобиль; a1 - автомобиль в гараже агентства; a2 - автомобиль арендован; a3 - автомобиль используется; a4 - автомобиль находится на мойке. Переходы: l1 - клиенты, обратившиеся в агентстве за автомобилем (агентство, клиент); l2 - отказ в аренде (агентство, клиент); l3 - передача автомобиля клиенту (агентство, клиент, автомобиль); l4 - обращение в агентство для возврата автомобиля (агентство, клиент, автомобиль); l5 - возвращение автомобиля в агентство (агентство, клиент, автомобиль); l6 - возвращение автомобиля в гараж агентства (агентство, автомобиль). Рис. 1. Вложенная сеть Петри на примере агентства по прокату автомобилей (по [11]) В данном случае используются два вида синхронизации: вертикальная, когда переход в системной сети срабатывает одновременно с переходами в элементных сетях, и горизонтальная, когда одновременно срабатывают два перехода, находящихся в одной и той же позиции системной сети. Для их различия используют два вида меток: - для вертикальной синхронизации и - для горизонтальной. Данная сеть Петри реализует модель, в которой клиент арендует автомобиль при его наличии в агентстве, использует и возвращает обратно. Таким образом, количество элементных сетей зависит от количества клиентов и автомобилей в агентстве. Моделирование распределенной системы на основе сетей Петри с нагруженными метками Реализацию данной сети при использовании нагруженных меток представим, используя два способа. В первом сохраним структуру системной сети, а информацию об изменении состояний в элементных сетях представим при использовании комбинированных типов данных (рис. 2). Рис. 2. Сеть Петри с нагруженными метками на примере агентства по прокату автомобилей, способ 1 При проектировании данной сети использовались следующие типы данных и переменные: - colset INT = int; - colset CAC = product INT INT INT; - colset CC = product INT INT; - colset CA = product INT INT; - colset C = INT; - var cac : CAC; - var cc : CC; - var ca : CA. Места элементных сетей и преобразуются в переменные, добавленные к маркировкам у соответствующих мест, т. к. элементные сети интерпретируются при использовании нагруженных меток. Значение переменной соответствует индексу места, с которым она соотносится, например, в месте s2 находится фишка только со значением . Для удобства состояния системной сети добавлены к типам данных, например, позиция s7 содержит фишки с комбинированным типом данных (INT INT INT), т. е. можно отследить состояние клиента и автомобиля по отношению к агентству. Место a3 и переходы a1, a2 добавляются к системной сети из элементных . Изменение переменных происходит при срабатывании перехода за счет увеличения или уменьшения значений. Места c1 и s5 содержат пять и четыре фишки, соответственно, что означает пять потенциальных клиентов и четыре автомобиля в наличии у агентства. Анализ сети проводился в программной среде CPN Tools Version 4.0.0, которая автоматически исследует пространство состояний с последующим сохранением результатов в текстовый файл (таблица). Результаты анализа сети Петри State Space. Nodes: 54, Arcs: 116, Secs: 0, Status: Full Пространство имеет 54 состояния и 116 взаимосвязи между ними Dead Markings - None Тупиковых маркировок в сети нет Dead Transition Instances - None Мёртвых переходов в сети нет Live Transition Instances - All Все переходы живые, т. е. срабатывают при моделировании Для реализации второго способа используется три места {P = CAC} (Company, Automobile, Client) и восемь переходов (рис. 3). Проектирование данной сети осуществляется на основе следующих типов данных и переменных: - colset INT = int; - colset company = product INT INT INT INT INT INT INT INT; - colset automobile = product INT INT INT INT INT; - colset client = product INT INT INT INT INT INT; - var c0, c1, c2, c3, c4, c5, c6, c7, c8: INT; - var a0, a1, a2, a3, a4, a5 : INT; - var cl0, cl1, cl2, cl3, cl4, cl5, cl6: INT. Рис. 3. Сеть Петри с нагруженными метками на примере агентства по прокату автомобилей, способ 2 В данной сети место Company имеет фишку, состоящую из восьми переменных, каждая из которых имеет свой тип данных (Integer). Значение переменной совпадает с количеством фишек в месте (индекс имени места совпадает с порядковым номером переменной). Переменные к соответствующим дугам места Company даны слева, как и условия на срабатывание переходов. Необходимо отметить, что для реализации экземпляров у вложенных сетей необходимо построение новой сети, а для нагруженных меток - необходимо увеличить их количество в определенных местах или изменить значение переменной одного или нескольких типов данных. Условия срабатывания переходов, переменные и функции дуг сети становятся более сложными при использовании сетей Петри с нагруженными метками. Реализация рекурсии с использованием вложенных сетей Петри В представленном ранее примере сеть имеет только один уровень вложенности. Но существует вложенность нескольких уровней [11]: , где - конечный набор сетевых компонент (сетевых фишек); Aatom - конечный набор сетевых фишек; I - интерпретация констант в выражениях на дугах в ; - выделенная компонента (системная сеть); M0 - разметка системной сети над и Aatom. Данное свойство рассмотрим на примере реализации рекурсии [11-14], а именно - вычисления факториала (рис. 4). Рекурсивная NP-сеть RN, изображенная на рис. 4, состоит из системной сети F0 и элементной сети F. Константа F, приписанная дуге, интерпретируется как элементная сеть F с начальной разметкой. Значения переменной x - сеть F с возможными (достижимыми) маркировками. Исполнение рекурсивной RN происходит следующим образом. Изначально системная сеть имеет единственную фишку (черную точку) в позиции p1. Первый шаг выбирается недетерминировано и зависит от начального значения аргумента n вычисляемой функции. Если n = 0, то срабатывает переход t1 (что соответствует вычислению ) и вычисление завершается. Рис. 4. Рекурсивная вложенная сеть Петри нахождения факториала числа (по [11]) Если , то срабатывает переход t2, порождая элементную сеть F с начальной разметкой, что соответствует уменьшению n на 1 и внутреннему вызову процедуры вычисления факториала. После этого системная сеть F0 содержит сетевую фишку (сеть F с начальной разметкой) в позиции p3. Далее в этой сетевой фишке может сработать переход s2, что приведет к появлению новой сетевой фишки и нового уровня в сети RN. При срабатывании перехода s1 происходит синхронизация с переходом s3, помеченным меткой в сети предыдущего уровня. Это приводит к исчезновению сетевой фишки самого нижнего уровня и уменьшению числа уровней в NP-сети на 1. При срабатывании перехода s4 в сетевой фишке (текущего) самого нижнего уровня происходит синхронизация с переходом s3 в «родительской» сети, что также уменьшит число уровней на 1. Этот процесс будет продолжаться до тех пор, пока в разметке не останется только один уровень - системная сеть с черной точкой в позиции p3, после чего исполнение завершится. Реализация рекурсии с использованием сетей Петри с нагруженными метками При использовании нагруженных меток для вычисления факториала (рис. 5) используется комбинированный тип данных (INT INT), переменная первого типа отображает значение числа искомого факториала, а второго - значение, вычисленное на предыдущем шаге. В данном исполнении нахождение факториала происходит от искомого числа до единицы с уменьшением текущего значения на каждом шаге. Если значение на предыдущем шаге равно 0, то срабатывает переход Recursion 1, который декрементирует значение первой переменной и вычисляет вторую посредством произведения текущего значения числа, уменьшенного на 1. Если значение первой переменной не равно 1, а вторая переменна не равна 0, то сработает переход Recursion 2, который декрементирует значение первой переменной и вычисляет вторую посредством произведения текущего значения числа полученным на прошлом шаге произведением. Если первая переменная равна 1, то сработает переход Complete: в место Complete попадет фишка с найденным значением искомого факториала. Рис. 5. Сеть Петри с нагруженными метками нахождения факториала числа Из вышеизложенного следует, что лучше использовать нагруженные метки вместо вложенных сетей с вертикальной синхронизацией переходов. Заключение На основе проведенных исследований вложенных сетей Петри и сетей с нагруженными метками сделаны предположения о подходящих областях их использования. Представлены положительные и отрицательные аспекты видов сетей на примере агентства по прокату автомобилей. Вложенные сети - это мощный инструмент, на основе которого показаны параллельные процессы, сложные многоуровневые системы без дополнительных мест, переходов и их взаимосвязей, синхронизация разных потоков информации и представление в разных сетях одинаковых мест с разной маркировкой, что весьма удобно. Отметим, что предпочтительным является применение сетей с нагруженными метками (метки с дополнительной информацией о структуре системы или об истории её изменений), если предполагается использование вложенных сетей одного или двух уровней. Вложенные сети Петри выполняют рекурсивные задачи за счет вертикальной синхронизации срабатывания переходов, что показано на примере нахождения факториала числа. Отмечено, что при выполнении задачи более предпочтительным является использование сетей с нагруженными метками, чем вложенных сетей с вертикальной синхронизацией переходов.
1. Романников Д. О. Разработка программного обеспечения с применением UML диаграмм и сетей Петри для систем управления локальным оборудованием: дис. … канд. техн. наук / Д. О. Романников. Новосибирск, 2012. 195 с.
2. Christensen S. A. Sweep-Line Method for State Space Exploration / S. A. Christensen, L. M. Kristensen, T. Mailund // URL: http://www.tzi.de/~edelkamp/lectures/dmc/slides/sweep.pdf.
3. Holzmann G. J. An Improved Protocol Reach ability Analysis Technique / G. J. Holzmann // URL: http://spinroot.com/spin/Doc/spe88.pdf.
4. Westergaard M. Behavioural Verification and Visualisation of Formal Models of Concurrent Systems / M. Westergaard // URL: https://westergaard.eu/wp-content/uploads/2009/10/thesis.pdf.
5. Марков А. В. Анализ сетей Петри при помощи деревьев достижимости: / А. В. Марков, А. А. Воевода // Сб. науч. тр. Новосибир. гос. техн. ун-та. 2013. № 1 (71). С. 78-95.
6. Марков А. В. Анализ отдельных частей дерева достижимости сетей Петри / А. В. Марков // Сб. науч. тр. Новосибир. гос. техн. ун-та. 2013. № 3 (73). С. 58-74.
7. Воевода А. А. Инверсия простой ординарной сети Петри / А. А. Воевода, А. В. Марков // Науч. вест. Новосибир. гос. техн. ун-та. 2013. №4 (53). С. 215-218.
8. Марков А. В. Инверсия сетей Петри / А.В. Марков // Сб. науч. тр. Новосибир. гос. техн. ун-та. 2013. № 4 (74). С. 97-121.
9. Марков А. В. Проверка достижимости маркировки сетей Петри при помощи инвертирования деревьев состояний для протокола передачи данных / А. В. Марков, А. А. Воевода // Докл. Томск. гос. ун-та систем управления и радиоэлектроники. 2014. №1 (31). С. 143-148.
10. Бандман М. К. Территориально-производственные комплексы: прогнозирование процесса формирования с использованием сетей Петри / М. К. Бандман, О. Л. Бандман, Т. Н. Есикова. Новосибирск: Наука, 1990. 303 с.
11. Ломазова И. В. Вложенные сети Петри: моделирование и анализ распределенных систем с объектной структурой / И. В. Ломазова. Москва: Научный мир, 2004. 208 с.
12. Дворянский Л. В. Имитационное моделирование и верификация вложенных сетей Петри с использованием CPN Tools / Л. В. Дворянский, И. В. Ломазова // Моделирование и анализ информационных систем. 2012. Т. 19. № 5. С. 115-130.
13. Марков А. В. Моделирование процесса поиска пути в лабиринте при помощи сетей Петри / А. В. Марков // Сб. науч. тр. Новосибир. гос. техн. ун-та. 2010. № 4 (62). С. 133-140.
14. Марков А. В. Поиск манипулятором кратчайшего пути в лабиринте / А. В. Марков // Сб. науч. тр. Новосибир. гос. техн. ун-та. 2011. №4 (66). С. 75-90.
15. Воевода А. А. Рекурсия в сетях Петри / А. А. Воевода, А. В. Марков // Сб. науч. тр. Новосибир. гос. техн. ун-та. 2012. № 3 (69). С. 115-122.
16. Марков А. В. Понятие рекурсии в сетях Петри: факториал числа, числа Фибоначчи / А. В. Марков, А. А. Воевода // Сб. науч. тр. Новосибир. гос. техн. ун-та. 2013. №1 (71). С. 72-77.
