NESTED PETRI NETS AND LOADED INSCRIPTION LABELS: DISTRIBUTED SYSTEM AND RECURSION
Journal: VESTNIK OF ASTRAKHAN STATE TECHNICAL UNIVERSITY. SERIES: MANAGEMENT, COMPUTER SCIENCE AND INFORMATICS
Volume 2015 № 2
, 2015
Rubrics: MANAGEMENT, MODELING, AUTOMATION
Authors:
1.
Novosibirsk State Technical University
2.
Novosibirsk State Technical University
Type:
Article
Pages:
from 23
to 31
Status:
Published
Received:
05.04.2015
Accepted:
25.04.2015
Published:
25.04.2015
Subject area:
VAC 05.12.2013 Системы, сети и устройства телекоммуникаций
VAC 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
VAC 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
VAC 05.13.10 Управление в социальных и экономических системах
VAC 05.13.18 Математическое моделирование, численные методы и комплексы программ
VAC 05.13.19 Методы и системы защиты информации, информационная безопасность
UDK 681.3
GRNTI 20.01 Общие вопросы информатики
GRNTI 28.01 Общие вопросы кибернетики
GRNTI 49.01 Общие вопросы связи
GRNTI 50.01 Общие вопросы автоматики и вычислительной техники
GRNTI 82.01 Общие вопросы организации и управления
VAC 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
VAC 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
VAC 05.13.10 Управление в социальных и экономических системах
VAC 05.13.18 Математическое моделирование, численные методы и комплексы программ
VAC 05.13.19 Методы и системы защиты информации, информационная безопасность
UDK 681.3
GRNTI 20.01 Общие вопросы информатики
GRNTI 28.01 Общие вопросы кибернетики
GRNTI 49.01 Общие вопросы связи
GRNTI 50.01 Общие вопросы автоматики и вычислительной техники
GRNTI 82.01 Общие вопросы организации и управления
Language:
Russian
Keywords:
nested Petri nets, loaded inscription labels, recursion, distributed systems, factorial, combined data type, horizontal and vertical synchronization of transitions
Abstract (English):
For modeling concurrent processes, complex multi-level systems without additional places, transitions, and their relationships, synchronization of different flows of information and views on different nets of the same places with different markings, nested Petri nets are used. An alternative to this type of the nets are nets with loaded inscription labels containing additional information about the structure of the system or history of its changes. Comparison of the approaches to construction of Petri nets based on the nested nets and nets with loaded inscription labels is made by the example of the analysis of the distributed system of car rent agency and the recursive task - finding factorial. The analysis of the distributed system of the agency is made on the basis of two-level nested Petri nets using vertical and horizontal synchronization. In order to compare, the analysis based on the loaded inscriptional labels is carried out in two ways. In the first case, the structure of the system net is taken as a basis; in the second case the net consists of three parts, to each of which a certain set of data types is added to display the possible system states. Finding factorial of the number y in the nested Petri nets is made through vertical synchronization of transitions between the system net and the element nets, and while using the loaded inscription labels it is carried out via the combined data type of the net parts. The variable of the first data type displays the number of the desired factorial, and in the second case the value of the current variable calculated in the previous step is observed. Modeling and automatic analysis of Petri nets for these examples occur in the software environment CPN Tools (version 4.0.0).
For modeling concurrent processes, complex multi-level systems without additional places, transitions, and their relationships, synchronization of different flows of information and views on different nets of the same places with different markings, nested Petri nets are used. An alternative to this type of the nets are nets with loaded inscription labels containing additional information about the structure of the system or history of its changes. Comparison of the approaches to construction of Petri nets based on the nested nets and nets with loaded inscription labels is made by the example of the analysis of the distributed system of car rent agency and the recursive task - finding factorial. The analysis of the distributed system of the agency is made on the basis of two-level nested Petri nets using vertical and horizontal synchronization. In order to compare, the analysis based on the loaded inscriptional labels is carried out in two ways. In the first case, the structure of the system net is taken as a basis; in the second case the net consists of three parts, to each of which a certain set of data types is added to display the possible system states. Finding factorial of the number y in the nested Petri nets is made through vertical synchronization of transitions between the system net and the element nets, and while using the loaded inscription labels it is carried out via the combined data type of the net parts. The variable of the first data type displays the number of the desired factorial, and in the second case the value of the current variable calculated in the previous step is observed. Modeling and automatic analysis of Petri nets for these examples occur in the software environment CPN Tools (version 4.0.0).
Keywords:
nested Petri nets, loaded inscription labels, recursion, distributed systems, factorial, combined data type, horizontal and vertical synchronization of transitions
nested Petri nets, loaded inscription labels, recursion, distributed systems, factorial, combined data type, horizontal and vertical synchronization of transitions
Введение Для верификации проектируемых моделей на семантические ошибки прибегают к использованию сетей Петри [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. Romannikov D. O. Razrabotka programmnogo obespecheniya s primeneniem UML diagramm i setey Petri dlya sistem upravleniya lokal'nym oborudovaniem: dis. … kand. tehn. nauk / D. O. Romannikov. Novosibirsk, 2012. 195 s.
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. Markov A. V. Analiz setey Petri pri pomoschi derev'ev dostizhimosti: / A. V. Markov, A. A. Voevoda // Sb. nauch. tr. Novosibir. gos. tehn. un-ta. 2013. № 1 (71). S. 78-95.
6. Markov A. V. Analiz otdel'nyh chastey dereva dostizhimosti setey Petri / A. V. Markov // Sb. nauch. tr. Novosibir. gos. tehn. un-ta. 2013. № 3 (73). S. 58-74.
7. Voevoda A. A. Inversiya prostoy ordinarnoy seti Petri / A. A. Voevoda, A. V. Markov // Nauch. vest. Novosibir. gos. tehn. un-ta. 2013. №4 (53). S. 215-218.
8. Markov A. V. Inversiya setey Petri / A.V. Markov // Sb. nauch. tr. Novosibir. gos. tehn. un-ta. 2013. № 4 (74). S. 97-121.
9. Markov A. V. Proverka dostizhimosti markirovki setey Petri pri pomoschi invertirovaniya derev'ev sostoyaniy dlya protokola peredachi dannyh / A. V. Markov, A. A. Voevoda // Dokl. Tomsk. gos. un-ta sistem upravleniya i radioelektroniki. 2014. №1 (31). S. 143-148.
10. Bandman M. K. Territorial'no-proizvodstvennye kompleksy: prognozirovanie processa formirovaniya s ispol'zovaniem setey Petri / M. K. Bandman, O. L. Bandman, T. N. Esikova. Novosibirsk: Nauka, 1990. 303 s.
11. Lomazova I. V. Vlozhennye seti Petri: modelirovanie i analiz raspredelennyh sistem s ob'ektnoy strukturoy / I. V. Lomazova. Moskva: Nauchnyy mir, 2004. 208 s.
12. Dvoryanskiy L. V. Imitacionnoe modelirovanie i verifikaciya vlozhennyh setey Petri s ispol'zovaniem CPN Tools / L. V. Dvoryanskiy, I. V. Lomazova // Modelirovanie i analiz informacionnyh sistem. 2012. T. 19. № 5. S. 115-130.
13. Markov A. V. Modelirovanie processa poiska puti v labirinte pri pomoschi setey Petri / A. V. Markov // Sb. nauch. tr. Novosibir. gos. tehn. un-ta. 2010. № 4 (62). S. 133-140.
14. Markov A. V. Poisk manipulyatorom kratchayshego puti v labirinte / A. V. Markov // Sb. nauch. tr. Novosibir. gos. tehn. un-ta. 2011. №4 (66). S. 75-90.
15. Voevoda A. A. Rekursiya v setyah Petri / A. A. Voevoda, A. V. Markov // Sb. nauch. tr. Novosibir. gos. tehn. un-ta. 2012. № 3 (69). S. 115-122.
16. Markov A. V. Ponyatie rekursii v setyah Petri: faktorial chisla, chisla Fibonachchi / A. V. Markov, A. A. Voevoda // Sb. nauch. tr. Novosibir. gos. tehn. un-ta. 2013. №1 (71). S. 72-77.
