Книжка по сетям Петри (547616), страница 26
Текст из файла (страница 26)
Назовем сати из класса 8а строго ицецзкичеекими. Из определений асах трах классов следует„что За - 81 Г1 Г18ы так как в класса За условия заваршаиилеоставмыхпараходовсвлзаны только е локальными маетами этих парахшмю. Возникает вопрос, ка. колы моделирующие возможности строго иерархических сатай1 Т а о р а м а 6.1В. Юмсс сгроао иарархичаских свгвд сгроао мощнвв классов сотай Петри и регулярных сагой. Д о к а з а т а л ь с т в о.
Сати на рис. 6.9 являютсл строго иарархичаскими, так как на содержат мает, сторонних для составных переходов. Как установлено в таорама ВЛ1, зти сати порождают языки, на принадпажацив классам языков сетей Петри. П В то жа время класс строго иерархических сетей оказывается на "универсально мощным". В работа [9) яоказэно, что класс мнгнбиторных сетей строго мощнее класса Зч, так как существуют ингибиторныа сати, для которых нат Х.эквивалантных еатай из класса 8а.
Примером такой сети может служить ингибиторнап сеть на рис. 6.12, я В целом сравнительный анализ выразительной мощности иерархических свтай и сетей Патри показывает, что введение марархим в сатавыа ьюдзли сущвствамно улучшает мцпалирующма способности медалей. В свою очв. раль наличие межуровневых связей в иерархических системах увеличивает сложность их функционирования, и такие системы на модалируютсл "хо. рошо структурированными" сетями такими, как строго иерархические сети. ГЛАВА 7 СЕТИ СИСТЕМЫ И СЕТИ-ПРОЦЕССЫ Сать Петри является абстракциай динамической системы в том смысла, что ее переходы соотватствуют событиям в системе, а места — условиям наступления событий. Событие — зто некоторый факт в системе, обычно трактуемый как потенциальное действие компонента системы, которое может осуществляться саин, несколько раэ или ни разу. Функционирование системы в целом (нлн некоторой ае части — яодсистемы) порождает гсзочесс — арзнжированную во времени или некоторым другим способом совокупность дээлизжлгд собыгид (дадсгеид) и измененид услоаид, В об.
щем случае система может порождать разные процессы, а множество всех процессов, порождаемых системой, полностью характеризует динамику по. ВЭДЭНИЯ СИСТЕМЫ, Одним из способоВ изучения множества Всех ленжюссов, порождаемых системой, служит изучение языков соответствующей сети Пэтргь Однако языки сати Петри надостзточно полно отражают поведение моделируемой енотам ы. Для описания процессов, исследованил их свойств и изучения связей мюхду свойствами нужна некоторая синтаксическая форма представланил процессов (протоколы процессов).
В этой главе рассматривеотся методы сетевого представления процессов и устанмлмваотся взеимосаязи между свойствами сетей, моделирующих системы, и саойствамн сетай. Моделирующих процессы. Идея разреботки обшад творим систем и процессов а терминах сетей восходит к ранним работам К. Петри, конкретизируется в статье (74( н развивается в (жде последующих работ Петсж и других авторов Р7, 21.
22. 23( В работах. [10, 1б( так же, как и в данной главе. понятна парал. лепьного процесса обобщеется эа счет допущения в процессах наряду с параллелизмом действий (н условий) альтернативы, возникающей в тех случаях, когда разрешено в процессе указывать небор взаимоисключающих действий, а также конкуренции, исключающей строгий паралпалнзм (одновременность), но допусквощвй произвольный порядок елэдования действий. Изучение взаимосвязи между сетямисистамеми и сетями.процессами нацелено прежде всего не выявлениа требований к осмысленным, хороню устроенным" сетям, моделирующим "реалистичные" систамы н процессы. С этой целью вводитсл ряд структурных свойств длл сетей.яроцессов, с помацью которых выделяются хорошо устроениыа сатичтроцассьь Зетам формулируются требования к сетям системам, которые могут порождать только такие, хорошо устроенные процессы.
Этот круг исследований эще далеко не завершен, но в силу его важности для целенаправленного развития общей теории сатай„опирающейся на строгие баэоВые сэмВнтическне понятия, мы п(жеш(нм В этой Главе неко торые начальные результаты, говорящие о продвижении в данном напрев. ленни 101 б У.(,Пр ц При определении функционирования сети Петри были использованы такие понлтип, как граф разметан, множество достижимых резметок, мно.
жество яоспадоаатальностей сребатыаеннй (см, $1.2». Путь ° графе реэметок от корневой аерщины или последовательность срабатываний можно рассматривать как представление некоторого процесса, порождаемого сетью Петри, в форме линейно упорядоченной посладсаательности симво. лоа пареходоа и рээметок мест или просто символов переходоа. б послед.
нем спу ае такая поеледсвательность - это слово а алфавите 7, ° все мно. жктво возможных в сати яроцессоа харектеризуетсп свободным языком Х энь тл. сети Петри. Этих понятий достеточно бьщо дпп формулировки н анепнаа матеметическнх свойств сетей, но они не всегда адекватно отражают струк. турные и поведенческие аспекты сетей, в честности. при сояостаалении их с нападением модепируамых систем, особенно если речь идет о модалирова. нии перэллельных асинхронных систем, В этих случелх представление про.
цессов а аиде последоветепьноотей реалиэеций событий отодвигает не вто. рой план такие отнощанил между ними, как переллелнзм или конфликты из за ресурсов. Например, простея сеть на рис, уЛ, а порождает дпя да~ О свободный терминальный пзык (г~гы гзг~). Этот язык описывает мно. жество возможных строгих упорлдочаний действий в процессах, яорождае. мых данной сетью, При атом оказывеетсп, что такой же свободный термн. непьный пзык порождеетсн показанной не рис, 7,1, б сетью Петри другой структуры н с процессами другого харэктарэ. Действительно, в системе, моделируемой первой сетью, событил г~ и гт могут произойти одно.
° раменно (т.е. ° множестве возможных процессов существует процесс, в котором события г~ и гт параллельны». С другой стороны. среди процессов, порождаемых второй сетью, такого процесса нет: событил г~ и гт могут реализоваться в любом последовательном порядке, но только не одновременно. Можно протоколировать процессы с помощью временных диаграмм, ° которых по одной оси откпадыааетсп дискретное время, а яо другой— выполнивщиесп действия. Этот способ описенил процессов, вопераых, громоздок, а во вторых, обладает теми недостатками временного представ. лепил процессов в кинхронных системах, о которых гоаорилосьв%1 1, Поиск новых форм лредстевленнл процессов, которьа были бы иэбав. лены от укаэанных напостетков, приводит к идее залепил процессов в аиде структур сетевого типа, подобных структурам порождащцнх зти процессы систем.
При таком определении процесс выглядит как совокУпность реализеций событий и изменений условий системы, связанных отнощенипми разного типа, и задаат, по существу, не единственный временной протокол функционироаанил системы, е некоторое множество временнйх протока. 102 пое, рвзпичаащихсп конкретными привязками действий ко времени, Другими словами, процесс представппет собой клаас эквивалентности дпл времвннйх протоколов, а котором эквивалентные яротокопы хврактери.
вуютсп одним и тем же набором прнчнниоюпедстаанных и других отноще. ний между дейатенлми н успоаилмн. Базовыми, неопрадаяаннымн понптмлмм, из которых строится процесс, служат деа типе элементов процесса: дж7атаия и изменения уаеовид[ Действие ° процессе — ато режжзвцил собьпня смстамы, порождаощей про.
цаса, Изманание условия - это рвзовап реализация факта маменеиж неко. торого уалоанл в системе. Процесс предатввплет собой множество знамен тов процесса, содвржащав котя бы одно действие, хотп бы одно изменение условия и некоторую совокупность отнощвний, определенных ма атом мно. жвствв элементов, Вае элементы процесса уникальны (различны!. В понптим процесса, кам оно введено в работах Петри [74, 77[, кеждый элемент рэапизувтап ° про. цесса равно один рзз. Однако ниже мы будем рвасметриаать обобщение по пятил процесса «процессы с апьтернатиавми.
В представлении такого про. цесаа могут содаржатьап альтернативные действия и изменения усповмй. которые взаимно исключают друг друга. если выпопнпвтап, например, одно действ«а, то другое не реапнзуатсп, и наоборот, но ровно одно мз этих действий обязательно происходит. Типы отнощвнмй. салзывмащих элементы процессе. определяют тип процесса, Все онн ааодптан через бвзовое оптоиюиие тэтедиюсгеоевиия элементов процесса, которое обозначветая символом <. Пусть к и у — элементы некоторого процвсаа. Запив ° к< у трвктуетап таким обрезом, что элемент к входит в процесс "раньще, чем" апемвнт у, т.е.
действие ипи изменение условип к авверщится до того, кек начинается действие ипи изменение условия у. Псм причинноследственной трактовке процессе эта запись означеет, что появление элемента у в этом процессе пв. ппетсп следствием появления а нам элемента к. Поступируетсл, что отноще. нив предщеатвоаания на рефлексивно и трвнзитивно. (более точно: к < у «В в б и: [т„< т„1 Л 'Фп б П: (т«< г, ог т„< г„(, где П - множество всех временных яротокояоа процесса, т„- момент зваврщаннп реапизацмм элемента к, тк - момент нвчама реализации элемента у, Оу - ЛОГИЧЕСКап Олэрацня "ИСКЛЮЧнтаПЬНОЕ Ил»Г' (»В ОГ В м~ (»В Л [В! Ч Ч ( 14ЛФ1!. Отнвиениеакедагеия й между элементами безальтернативного процессе опредеппетая следующим обрезом: кйу ° ° (к<уоту<к[Ч[к у[.. Если элементы «н у связаны отнощенивм й ° процесса, то возможен только один из двух вариантов: либо к всегда резпизуатая а яроцасса рэньщц чем у, либо у рввпизуется е процессе рвньще, чем к.
Отнощеммв следования рефлексивно (кйк[, симметрично (кйу» ° у11к[ и нетрвнзитивно (нэ «йуЛ уй« неслапуат,что ко[. Ргиомю»иа яцзвллваизма ее опредеппетсп свщующмм образом дпл про. цеасов бев альтернатив: «еоу» ° ( [(к<у[Л йу<«И Ч(к у[ ° Это отнощанма на накладывает никекмх огрениченнй на порядок щюдованип элементов и нв устанавливает никаких причинноследственных свп. зей между ними. Оно рефлекс зно, симметрично н нетрвнзмтивно.
Оп«ошение конкуренции соп определяется следующим образом; ксопу [х < у Л у < к) Ч (х = у) . Зто отношение, в отличие от отношения следования Н, разрешает элементам к и.у реализоваться в процессе в любом порядке:х может как предшествовать у. так и следовать за ним. Однако х и у не могут реализоваться "одновременно". Отношение еоп рефлексивно, симметрмчно и нетранзи. тивма Для того чтобы определить ОтнОШЕНИЕ алЬтариатИВЫ, Впадем специаль.
мый фиктивный эламамт й в процесс, который по опредалению реализует; ся "позже всех других элементов процесса". Тогда высказывание« < й выполнимо для элемента к, реализоваашегося в процессе, и только для него. Запись 1[х < й) означает, что элемент к не реализовался в процессе. Огиошениеальгернагиаы а! определяется следующимобразом: ха1у ° ° (к < й ~ ")(у < й)) 1/ [«у) . Если процесс содержит элементы к и у, находящиеся в отношении а(, то реализация одного из этих элементов исключает возможность рвализацим другого.
Это отношение также рефлексивно, симметрично и нетранэитиано. Данные выше определения отношений следования и пареплелизма относились к элементам процессов без альтернативы, когда каждый элемент реализуется в процессе ровно один раз. Обобщим зти Олределения на слу. чай процессов с альтернативами, в которых некоторые из альтернативных элементов могут не реализовэться: «Ну ч~ ((к< О Л у<й) ° (к<уогу<х)) у (х ~ у), «соу ~ ч ((х < й Л у < ь1) ( 1(к < у) Л 1(у < к))) 1/ (к = у), Обобщение состоит в том, что дополнительно выделаны случаи, когда один из элементов к и у или оба элемента могут нереализоваться засчет того, что реализованы их альтернативы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
