О структурних элементах компонентной сети Петри

Gespeichert in:

Bibliographische Detailangaben
Datum:	2015
1. Verfasser:	Lukyanova, E.A.
Format:	Artikel
Sprache:	Ukrainian
Veröffentlicht:	PROBLEMS IN PROGRAMMING 2015
Schlagworte:
Online Zugang:	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/49
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Problems in programming
Завантажити файл:

Institution

Problems in programming

id	pp_isofts_kiev_ua-article-49
record_format	ojs
resource_txt_mv	ppisoftskievua/74/8fec0c3a032480b694100848548f3174.pdf
spelling	pp_isofts_kiev_ua-article-492018-07-25T19:36:22Z О структурних элементах компонентной сети Петри Lukyanova, E.A. сети Петри Рассмотрены вопросы конструирования и работы структурных элементов компонентной сети Петри (CN-сети). Такими структурными элементами являются составные компоненты: компоненты-места и компоненты переходы. От эффективного выделения составных компонент зависит размер модели реальной системы и время на ее верификацию.The problems of designing and work of structural elements of a component Petri net (CN-net) are considered. Such elements are composite components: components-places and components passages. The size of model of real system and time for it`s verification depends on effective allocation of composite components. PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2015-09-10 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/49 PROBLEMS IN PROGRAMMING; No 2-3 (2012) ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 2-3 (2012) ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 2-3 (2012) 1727-4907 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/49/50 Copyright (c) 2015 ПРОБЛЕМИ ПРОГРАМУВАННЯ
institution	Problems in programming
baseUrl_str	https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date	2018-07-25T19:36:22Z
collection	OJS
language	Ukrainian
topic
spellingShingle	Lukyanova, E.A. О структурних элементах компонентной сети Петри
topic_facet	сети Петри
format	Article
author	Lukyanova, E.A.
author_facet	Lukyanova, E.A.
author_sort	Lukyanova, E.A.
title	О структурних элементах компонентной сети Петри
title_short	О структурних элементах компонентной сети Петри
title_full	О структурних элементах компонентной сети Петри
title_fullStr	О структурних элементах компонентной сети Петри
title_full_unstemmed	О структурних элементах компонентной сети Петри
title_sort	о структурних элементах компонентной сети петри
description
publisher	PROBLEMS IN PROGRAMMING
publishDate	2015
url	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/49
work_keys_str_mv	AT lukyanovaea ostrukturnihélementahkomponentnojsetipetri
first_indexed	2025-07-17T10:01:27Z
last_indexed	2025-07-17T10:01:27Z
_version_	1850411205229805568
fulltext	Теоретичні та методологічні основи програмування УДК 004.021: 004.312.4: 004.414.2 О СТРУКТУРНЫХ ЭЛЕМЕНТАХ КОМПОНЕНТНОЙ СЕТИ ПЕТРИ Е.А. Лукьянова Киевский национальный университет имени Тараса Шевченко, факультет кибернетики, проспект Академика Глушкова, 4 e-mail: lukyanovaea@mail.ru Рассмотрены вопросы конструирования и работы структурных элементов компонентной сети Петри (CN-сети). Такими структурными элементами являются составные компоненты: компоненты-места и компоненты переходы. От эффективного выделения составных компонент зависит размер модели реальной системы и время на ее верификацию. The problems of designing and work of structural elements of a component Petri net (CN-net) are considered. Such elements are composite components: components-places and components passages. The size of model of real system and time for it`s verification depends on effective allocation of composite components. Введение Практически любая реальная сложная система, как правило, состоит из нескольких или множества взаимодействующих друг с другом объектов. Взаимодействию составных частей системы между собой и с окружающей их средой присущ параллелизм. Способ взаимодействия объектов определяет вид параллельных процессов, протекающих в системе. Параллельные процессы могут быть асинхронными и синхронными, при этом один и тот же процесс может быть синхронным по отношению к одному из активных параллельных процессов и асинхронным по отношению к другому. Для организации взаимодействия параллельных процессов используются подходы, основанные на взаимном исключении и синхронизации. Реактивные распределенные системы характеризуются параллельным функционированием протекающих в системе процессов, наличием сложных межпроцессорных взаимодействий и дискретным изменением параметров работающей системы. Для моделирования и анализа поведения реактивных распределенных систем широко применяется теория сетей Петри [1], позволяющая путем установления связей между объектами и отслеживания изменений состояний системы, описывать динамические недетерминированные процессы этих сложных систем [2]. В терминах сетей Петри адекватно выражаются важные характеристики параллельных систем по синхронизации доступа к ресурсам и их корректной обработки. Анализ сетей Петри позволяет получить важную информацию о структуре и динамическом поведении моделируемой системы. Актуальной на сегодняшний день является задача, нахождения возможностей сокращения размеров модели Петри исследуемой системы. Эта задача для систем с параллелизмом может быть решена, например, за счет использования в качестве модели системы такого расширения сети Петри, как CN-сеть (компонентная сеть Петри) [3]. Выявление групп одинаковых или однотипных процессов в детальной (подробной) модели системы и оформление их в виде блоков составных компонент модели, позволяет значительно сократить размеры модели и получить модель системы в виде CN-сети, в которой однотипные процессы заключены в соответствующие блоки – составные компоненты (компоненты-места и компоненты-переходы). А двух аспектный подход к функционированию этих компонент открывает новые возможности для сокращения времени на верификацию модели. Цель данной работы – описание структуры и работы составных компонент CN-сети и демонстрация составных компонент из различных, ранее полученных, моделей (CN-сетей) [3, 4] широко известной задачи о пяти философах. 1. Предварительные сведения Компонентная сеть Петри (CN-сеть) – это ориентированный граф, описываемый упорядоченной пятеркой: ,,,,( WFTPCN = ),0M 25 © Е.А. Лукьянова, 2012 ISSN 1727-4907. Проблеми програмування. 2012. № 2-3. Спеціальний випуск mailto:lukyanovaea@mail.ru Теоретичні та методологічні основи програмування где P – конечное множество мест, состоящее из подмножеств и ( – конечное множество компонент- мест, – конечное множество мест, понимаемое в обычном смысле мест сетей Петри, оставшихся после выделения компонент-мест); – конечное множество переходов, состоящее из подмножеств и (соответственно множество компонент-переходов и множество переходов понимаемое в обычном смысле переходов сетей Петри, оставшихся после выделения компонент-переходов), – отношение инцидентности между местами и переходами, – функция кратности дуг, – начальная разметка сети. 1P 2P 1P 2P T 1T 2T PTTPF ××⊆ U }0{\: NFW → 0M Множества P и T удовлетворяют следующим условиям: ∅=∅≠∅≠ TPTP I,, (граф CN-сети должен содержать хотя бы один переход и одно место, причем вершина графа не может быть одновременно элементом множеств P и T ). Отношение инцидентности F и функция кратности дуг определяют функцию инцидентности задающую правило: и определяющую то, что элементы одного множества дугами соединены быть не могут, а также описывающую наборы входных и выходных элементов. W ,I NPTTPI →×× )()(: U Компонента-место представляет собой участок сети, моделирующий некоторый однотипный процесс, начинающийся и заканчивающийся местом (местами), компонента-переход – участок сети, моделирующий некоторый однотипный процесс, начинающийся и заканчивающийся переходом (переходами). pC tC Компонентная сеть функционирует, переходя от разметки к разметке, как и регулярная сеть Петри. Составные компоненты в CN-сети свои функции выполняют мгновенно: компонента-место – мгновенное использование условия реализации события, компонента-переход – мгновенная реализация события, приводящая к изменению разметки мест всех типов. pC tC Таким образом, компонентная сеть Петри имеет свои важные особенности. Места и переходы в CN- сети могут быть различных типов: конечные множества мест и переходов включают подмножества, состоящие из составных компонент (компонент-мест и компонент-переходов). Функционирование составных компонент в CN -сети понимается как мгновенное выполнение, что позволяет на этом уровне модели игнорировать внутреннюю работу составной компоненты. Но мгновенное срабатывание составной компоненты CN-сети для самой составной компоненты обуславливает нахождение ее некоторое время в активном состоянии. В этом и заключается двух аспектный подход к функционированию составных компонент, а значит и к функционированию детальной модели. Такой подход позволяет устанавливать структурные свойства модели согласно правилам [3]: 1) если исследуемое структурное свойство не выполняется на CN-сети, то это структурное свойство не выполняется и для детальной (базовой) модели исходной системы; 2) если исследуемое структурное свойство выполняется на CN-сети, то это структурное свойство выполняется для детальной модели системы, если оно выполняется на одном представителе из групп одинаковых составных компонент CN-сети. И c помощью теорем [4]. Теорема 1. Если компонентная сеть Петри имеет только компоненты-переходы и они живы, то структурное свойство для детальной модели исследуемой системы выполняется, если это структурное свойство выполняется на CN-сети. Теорема 2. Если компонентная сеть Петри имеет только компоненты-места и соответствующие этим компонентам-местам системы линейных неоднородных диофантовых уравнений (СЛНДУ) совместны, то структурное свойство для детальной модели исследуемой системы выполняется, если это структурное свойство выполняется на CN-сети. Теорема 3. Если у компонентной сети Петри компоненты-переходы являются живыми, а соответствующие компонентам-местам СЛНДУ совместны, то структурное свойство для детальной модели исследуемой системы выполняется, если это структурное свойство выполняется на CN-сети. Следовательно, исследование процесса конструирования и функционирования составных компонент является важной неотъемлемой частью исследования свойств исходной системы на модели в виде CN-сети. 26 Теоретичні та методологічні основи програмування 2. Составные компоненты CN-сети Выявление возможных групп одинаковых или однотипных процессов в проектируемой детальной модели начинается при анализе исходной сложной системы. На этапах построения модели определяются и неоднократно уточняются группы одинаковых или однотипных процессов, которые оформляются в виде блоков составных компонент модели (компонент-мест и компонент-переходов). В результате полученная модель исходной системы, является детальной (подробной) моделью системы, но в которой однотипные процессы заключены в соответствующие блоки – составные компоненты. Рассматривая составные компоненты как места и переходы, получим компактную модель (CN-сеть) исследуемой системы, которая представляет собой расширение стандартного формализма сетей Петри. При формировании составных компонент необходимо учесть, во-первых, все возможные внутренние конструкции составных компонент и, во-вторых, тот факт, что функционирование составных компонент и самой CN-сети не должны нарушать основополагающих правил функционирования сетей Петри. 2.1. Компоненты-места CN-сети. Сеть Петри – тройка ),,( FTPN = , где P – конечное множество вершин- мест, T – конечное множество вершин-переходов, PTTPF ××= U – отношение, задающее множество дуг, которые соединяют места и переходы. Компонента-место представляет собой сеть Петри, в которой указаны входные и выходные места. Формально составную компоненту определим следующим образом. pC pC Компонентой-местом будем называть тройку = где – сеть Петри, , – соответственно её входные (начальные) и выходные (заключительные) места, причем pC ),,,( YXN N PX ⊆ PY ⊆ ∅=YX I , – множество внутренних мест. Входные и выходные места не имеют соответственно входящих и исходящих дуг: , . При этом сама компонента , как элемент CN-сети, имеет входящие и исходящие дуги. Компонента-место , моделирующая некоторый однотипный процесс детальной модели исследуемой системы, как структурный элемент CN-сети, представляется местом и как в обычной сети Петри является условием определяющим возможность наступления события – срабатывания перехода в CN- сети. Выполнение условия связано с появлением одной или нескольких фишек в соответствующем этому условию месте и обеспечивает возможность реализации событий в CN-сети. )(\ YXP U :Xp ∈∀ ∅=• p :Yp ∈∀ ∅=•p pC pC pC Компоненты-места позволяют моделировать любые параллельные процессы детальной модели системы. Функционирование составной компоненты-места начинается после срабатывания её входного перехода. В этот момент компонента получает фишку или k фишек (в том случае, когда входной переход и компонента имеют k дуг). При этом имеют место следующие возможности. pC pC 1. Если рассматриваемая компонента-место является выходным местом только для одного перехода CN-сети, то фишка (k фишек) помещается в начальное место компоненты, если оно единственное, или во все начальные места компоненты, если мест более одного. Выходной переход (выходные переходы) компоненты сработают только тогда, когда компонента-место отработает. Для CN-сети это есть мгновенное выполнение условия , а для самой компоненты имеем, что фишка (фишки) переместятся в выходное место (во все выходные места) компоненты . То есть, пока фишки находятся в , компонента-место работает от начального до финального своего состояния, при этом начальная и финальная разметки компоненты не совпадут. pC pC pC pC pC pC 2. Если компонента , как место CN-сети, является выходным местом для двух и более переходов CN-сети и внутренняя составляющая имеет одно и более начальных мест, тогда будем считать, что начало нахождения в активном состоянии может быть следующим: pC pC pC 1) если срабатывает один из входных переходов компоненты , то получение фишки компонентой для внутренней структуры этой компоненты означает, что фишка поместилась в одно из начальных мест компоненты ; pC pC pC 27 Теоретичні та методологічні основи програмування 2) если срабатывают входных переходов компоненты , то по одной фишке поместится в начальных мест компоненты , при этом значение может быть меньше числа входных переходов и может быть меньше числа начальных мест компоненты ; k pC k pC k pC 3) если же начальное место у компоненты единственное, то срабатыванием каждого из входных переходов компоненты помещается по фишке в начальное место компоненты . pC pC pC Взаимодействие параллельных процессов, моделируемых компонентой-местом, осуществляется их синхронизацией за счет моделирования внутренней структуры компоненты-места. В этом случае, когда компонента отработает, все её выходные места получат фишки. При этом компонента-место может быть входным условием как для одного перехода, так и для нескольких. Последний случай отметим отдельно, когда, наоборот нужно сохранить асинхронность. После срабатывания входных переходов компоненты и помещения по фишке в начальных мест компоненты (при этом начальных мест у компоненты больше, чем ), составная компонента отработает и в выходных её местах (выходных мест у компоненты больше, чем ) поместится по фишке. Будем считать, что теперь могут сработать только выходных переходов компоненты . k pC k k k k k pC 2.2. Примеры CN-сетей с компонентами-местами. Рассмотрим CN-сети, показанные на рис. 1 и 2. Эти CN- сети являются моделями, реализующими задачу о пяти размышляющих философах, которые проголодавшись, могут утолить голод в столовой за круглым столом с пятью местами и пятью вилками, при условии, что философ ест, имея обязательно две вилки: в левой и в правой руке. Эта задача представляет собой систему взаимодействующих и конкурирующих за доступ к общим неразделяемым ресурсам процессов, такая система вследствие ошибок в управлении может попасть в состояние дедлока. Модель задачи должна учитывать все возможные варианты поведения философов и осуществлять синхронизацию их независимых действий. В частности, необходимо: 1) обеспечить регламентацию использования вилок двумя соседними философами (обеспечение взаимного исключения); 2) не допустить состояния вечного ожидания, когда один из философов так и не сумеет получить доступ к ресурсу (вилке); 3) не допустить заговора соседей, когда обедают одни и те же; 4) решить проблему, когда все философы сидят за столом, каждый из них взял по одной вилке, и никто не может начать прием пищи. На моделях (CN-сетях), показанных на рис. 1 и 2, вышеизложенные условия реализуются. Рис. 1. CN-сеть с ингибиторными дугами, моделирующая задачу о пяти философах, где – компонента-место, – компонента-переход (соответственно рис. 3, а и 4) ∗P ∗∗T 28 Теоретичні та методологічні основи програмування Рис. 2. CN-сеть, моделирующая задачу о пяти философах, где – компонента-место, моделирующая один и тот же процесс (рис. 3, б) ∗P Данные CN-сети (рис. 1 и 2) имеют составные компоненты-места , показанные на рис. 3, а и б соответственно. ∗P а б Рис. 3. Компоненты-места в CN-сетях (рис. 1, 2 соответственно) ∗P Компоненты-места моделируют следующие поведения отдельного i-го философа (i = 1 – 5): ∗P составная компонента, показанная на рис. 3, а, – условие пребывания i-го философа в столовой и взятия им левой вилки, составная компонента, показанная на рис. 3, б, – условие того, что i-й философ держит в руках левую и правую вилки, ест, заканчивает есть и готов положить левую, правую вилки. Моделирование систем CN-сетями дает возможность проводить эффективный анализ моделей с помощью формальных методов, основанных на применении методов линейной алгебры (фундаментального уравнения и инвариантов) [5 – 7] и значительно уменьшить время верификации. Так, в модели (рис. 2) задачи о пяти философах удалось выделить только один тип составных компонент (рис. 3, б). И хотя размеры выделенной компоненты-места достаточно небольшие, но ∗P ∗P 29 Теоретичні та методологічні основи програмування многократное её использование в модели, позволило построить матрицу инцидентности, отвечающую данной CN-сети, размерностью не 56х35, а 36х30. Выделение двух типов компонент – компоненты-места (рис. 3, а) и компоненты-перехода (рис. 4) в модели (рис. 1) для той же задачи о пяти философах позволило построить матрицу инцидентности компонентной сети Петри уже размерностью 11х10 [4]. ∗P ∗∗T 2.3. Компоненты-переходы CN-сети. Компоненту-переход представим в виде сети Петри, в которой отдельно выделим начальные и заключительные переходы. Такое определение корректно так, как отдельно от CN-сети составные компоненты не работают, реализация внутренней составляющей компоненты произойдет лишь после выполнения входного условия для этой компоненты . Формально составную компоненту определим следующим образом. tC tC tC tC 30 ⊆ Компонентой-переходом будем называть тройку = , где – сеть Петри, – её начальные переходы, – заключительные переходы, причем множества начальных и заключительных переходов не пересекаются: . Начальные и заключительные переходы не имеют соответственно входящих и исходящих дуг. При этом сама компонента , как элемент CN-сети, имеет входящие и исходящие дуги. tC ),,( VUN N TU TV ⊆ ∅=VU I tC Компонента-переход , моделирующая некоторый однотипный процесс детальной модели tC исследуемой системы, как структурный элемент CN-сети, является событием и представляется переходом CN- сети. При мгновенном срабатывании компоненты фишки из входных мест этого перехода перемещаются tC в выходные места, что соответствует совершению события в CN-сети. Компонента-переход tC компонентной сети Петри сработает, если место (все места) CN-сети, являющиеся входными для компоненты tC , получат фишки. Для CN-сети это срабатывание (реализация ) мгновенное. Нахождение же в активном tC состоянии для самой составной компоненты начинается с запуска её начального перехода, если он tC единственный или всех её начальных переходов, если их больше одного. Завершение работы компоненты- перехода характеризуется срабатывание её заключительного перехода (всех заключительных переходов) компоненты . Выделение компонент-переходов для верификации модели является благоприятным – tC начальная и финальная разметки компоненты C совпадают. Действительно, до того, как сработает начальный t переход компоненты, он должен запуститься, в это момент фишка (фишки) еще не переместятся и разметка компоненты не изменится. Допущение противного влечет нарушение определения функционирования сетей Петри. При анализе компоненты-перехода получим систему линейных однородных диофантовых уравнений (СЛОДУ), что позволяет установить T- и S-инварианты составной компоненты-перехода. Для эффективного выделения составной компоненты в моделях сложных систем рассмотрение tC только вышеописанной возможности функционирования компонент-переходов недостаточно. Желательно обеспечить возможность запуска в компоненте-переходе не всех сразу внутренних переходов компоненты. На данный момент имеются предложения по расширению функционирования составной компоненты-перехода и для проверки этих возможностей рассматриваются реальные сложные системы. 2.4. Примеры CN-сетей с компонентами-переходами. На рис. 4, 5, 7 показаны компоненты-переходы для моделей, показанных на рис. 1, 6 и 8 соответственно. Рис. 4. Компонента-переход в CN-сети с ингибиторными дугами (рис. 1) ∗∗T Теоретичні та методологічні основи програмування Компонента-переход (рис. 4) моделирует процесс взятия i-м философом правой вилки, приема пищи, возвращение левой, правой вилки, выхода философа из столовой. ∗∗T Рис. 5. Компонента-переход CN-сети, моделирующей задачу о пяти философах (рис. 6) Указанная структура компоненты-перехода (рис. 5) отвечает компонентам-переходам , , , , модели CN-сети, показанной на рис. 6. Эти составные компоненты моделируют следующие действия отдельного i-го философа: философ берет левую вилку, берет правую вилку, ест, кладет левую вилку, кладет правую вилку, выходит из столовой. Переходы и , а также и составной компоненты могут сработать независимо и одновременно. 6t 7t 8t 9t 10t 1t 2t 3t 4t Рис. 6. CN-сеть, моделирующая задачу о пяти философах, где , , , , – компоненты-переходы, моделирующие один и тот же процесс (рис. 5) 6t 7t 8t 9t 10t а б Рис. 7. Компоненты-переходы: а – компонента-переход ;∗t б – компонента-переход CN-сети с ингибиторными дугами (рис. 8) ∗∗t Компонента-переход (рис. 7, а) – первый тип компонент-переходов CN-сети, показанной на рис. 8, отражает процесс входа i-го философа в столовую и взятие им левого столового прибора. Второй тип компонент- ∗t 31 Теоретичні та методологічні основи програмування переходов (рис. 7, б) моделирует следующий процесс: i-й философ берет правую вилку, ест, кладет левую вилку, кладет правую вилку, выходит из столовой. Факт параллельности действий отображается параллельными ветвями сетей компонент (переходы , могут сработать независимо и одновременно) и параллельными компонентами-переходами CN-сети (переходы или переходы могут сработать независимо и одновременно). ∗∗t 3t 4t ∗t ∗∗t Рис. 8. CN- сеть с ингибиторными дугами, моделирующая задачу о пяти философах, где и компоненты-переходы (рис. 7) ∗t ∗∗t Заключение Основные проблемы, с которыми приходится сталкиваться при моделировании реальных сложных систем и объектов – размеры модели и адекватность полученной модели исследуемой системе. Сети Петри, являясь удобным средством детального моделирования и анализа таких систем, могут содержать сотни, а иногда и тысячи элементов, что делает анализ таких моделей практически неосуществимым. Компонентные сети Петри (CN-сети) за счет выделения однотипных составных компонент в детальной (базовой) сети Петри исследуемой системы позволяют значительно сократить размеры модели системы. При этом выполняемые CN- сетью функции вполне соответствуют функциям, выполняемым детальной моделью Петри. Составными компонентами CN-сети являются компоненты-места и компоненты-переходы. В работе даны формальные определения составных компонент CN-сети, рассмотрены вопросы конструирования, функционирования составных компонент и приведены примеры формирования возможных составных компонент на различных моделях задачи о пяти философах. При организации составных компонент основным критерием формирования таких структурных элементов было сохранение основополагающих правил функционирования сетей Петри. Возможности моделирования участков компонентной сети составной компонентой-местом шире возможностей составных компонент-переходов. 1. Котов В.Е. Сети Петри. – М.: Наука, 1984. – 157 с. 2. Котов В.Е. Алгебра регулярних сетей Петри // Кибернентика. – 1980. – № 5. – С. 10–18. 3. Лук`янова О.О. Про компонентне моделювання систем з паралелізмом // Наукові записки НаУКМА. Комп’ютерні науки. – 2012. – Т. 121 4. Лукьянова Е.А. О компонентном анализе параллельных распределенных систем // ТВИМ. – 2011. – № 2. – С. 71–81. 5. Murata T. Petri Nets: Properties, Analysis and Applications. in "Proceedings of the IEEE". –1989. – Vol. 77, N 4. – P. 541–580. 6. Крывый С.Л. О некоторых методах решения и критериях совместности линейных диофантовых уравнений в области натуральных чисел // Кибернетика и системный анализ. – 1999. – № 4. – С. 12–36. 7. Крывый С.Л. О вычислении минимального множества инвариантов сетей Петри // Штучний інтелект. – 2001. – № 3. – С. 199–206. 32

О структурних элементах компонентной сети Петри

Institution

Ähnliche Einträge