книги / Теория наведенной неоднородности и ее приложения к проблеме устойчивости пластин и оболочек

Приложение 4. Применение аппарата сетей Петри Приложение 4.1. Основные понятия сетей Петри

общениями между взаимодействующими процессами, представлен­ ными в виде объектов. Для моделирования механизма обмена сооб­ щениями между взаимодействующими процессами имеется разрабо­ танный математический аппарат сетей Петри. Сети Петри модели­ руют структуру и динамику функционирования систем и процессов. Они занимают промежуточное положение между конечными автома­ тами и машинами Тьюринга. Рассмотрим основные понятия сетей Петри.

- конечное множество переходов, ш>0. Множество позиций и мно­ жество переходов не пересекаются. I : Т-»Р® является входной функ­ цией-отображением переходов в комплекты позиций. О : Т-»Р® - вы­ ходная функция, представляющая отображение переходов в ком­ плекты позиций. Позиция Pj является входной позицией перехода tj, если Pjel(tj); Pi является выходной позицией, если PjeO(tj). Входы и выходы переходов представляют собой комплекты, то есть пред­ ставляют обобщения множеств, в которые включены повторяющиеся элементы. Обозначение Рп применяется для комплекта, построенного

комплектов позволяет позиции быть кратным входом либо кратным выходом перехода.

Кратность входной позиции pi для перехода tj есть #(Pi,I(tj)), а кратность выходной позиции рк есть #(pk,0(tj)), где #(е,Е) обозначает число повторений элемента е в комплекте Е.

Графовым представлением сети Петри является двудольный ориентированный мультиграф. При изображении графа сети Петри позиции представляются кружками, а переходы - планками. Ориен­ тированные дуги соединяют позиции и переходы. Дуга, направлен­ ная от позиции pi к переходу tj, определяет позицию, которая.явля­

ется входом перехода. Выходная позиция изображается дугой от пе­ рехода к позиции. Кратные входы и выходы изображаются кратными дугами.

Таким образом, граф сети Петри есть двудольный ориентиро­ ванный мультиграф G=(V,A), где V={vi,v2,...,vs} - множество вершин, a A={ai,a2,...,ar} - комплект направленных дуг, ai=(vj,vk), где Vj,VjeV. Множество V может быть разбито на два непересекающихся под­ множества Р и Т, таких, что для любой направленной дуги aieA, если ai=(Vj,Vk), то либо VjeP и vkeT, либо vkeP, a VjeT. Кроме того, имеют место соотношения:

S((Pi,tj),A)=#(pj,I(tj)),

#((1з,рО,А)=#(рьОаз)).

В этом случае граф G эквивалентен сети Петри С.

Маркировкой [1 сети Петри С=(Р,Т,1,0) называется функция р: P-»N, отображающая множество позиций Р в множество неотрица­ тельных целых чисел N. Маркировка также может быть представ­ лена в вйде вектора p=(pi,p2,...,pn), где n-, PI и каждое p;eN, i=l,2,....n. p i есть количество фишек в позиции pj. Таким образом, p(pi)=Pi. Маркированная сеть Петри может быть представлена в виде пятерки М=(Р,Т,1,0,р). На графе сети Петри маркировка изобра­ жается точкой в соответствующем кружочке-позиции.

Переход ЪеТ в маркированной сети Петри С=(Р,Т,1,0,р) назы­ вается разрешенным, если vpieP р(р0>#(р,,1(^)). Переход tj может быть запущен, если он разрешен. В результате запуска разрешенного перехода tj образуется новая маркировка р \ определяемая соотноше­ нием:

ц'(ро=ц(ра-#(ри1ед)+#(рь0(у).

Состояние сети Петри определяется ее маркировкой. Запуск перехода изменяет состояние сети Петри, определяемое функцией 5:NnxT->Nn, называемой функцией следующего состояния. Функ­ ция следующего состояния для сети Петри С с переходом tj опреде­ лена тогда и только тогда, когда vpjeP. fi(pi)^#(pi,I(tj)). Если 5(p,tj) определена, то p1=6(p,tj).

Выполнение сети Петри определяется двумя последовательно­ стями: последовательностью маркировок (р^р1,...) и последова­ тельностью соответствующих переходов (tj°,tj\-.), которые были за­ пущены.

Для сети Петри С с маркировкой р маркировка р 1 называется непосредственно достижимой из р, если существует переход tjeT, такой, что 6(p,tj)=pI.

Таким образом, получается отношение непосредственной дос­ тижимости (р,р‘) на множестве маркировок. Определятся также от­ ношения достижимости как рефлексивное, транзитивное замыкание отношения непосредственной достижимости.

Множеством достижимости R(C,p) для сети Петри С с марки- ровЕсой р называется наименьшее множество маркировок, удовле­ творяющее условиям:

1 ) peR(C,p):

2) Если pJ€R(C,p) и pn=5(pl,t) для некоторого tjeT, то n"eR(C,n).

В теории сетей Петри зачастую используется расширенная функция следующего состояния 8(pltji,tj2,...,tjk), определенная для по­ следовательности разрешенных переходов 8(p,tji,tj2,...,tjk) следующим образом: для пустой последовательности переходов \ p=8(p,t), а для последовательности о Stp^a^SCSCp^tJ.o).

Одним из важнейших свойств сети Петри, моделирующей ре­ альный процесс, является безопасность. Позиция сети Петри называ­ ется безопасной, если число фишек в ней никогда не превышает 1. Таким образом, У т ^ (С ,р ) р‘(р0*1. Сеть Петри безопасна, если безопасны все ее позиции.

Безопасность - это частный случай более общего свойства огра­ ниченности. Позиция pieP сети Петри С с начальной маркировкой р называется k-безопасной или к-ограниченной, если она к-безопасна для некоторого к. Сеть Петри ограничена, если все ее позиции огра­ ничены.

Выполнение сети Петри можно представить последовательно­ стью срабатывающих переходов. Если пометить переходы из Т символами некоторого алфавита I, то каждому выполнению сети Петри будет сопоставлена цепочка символов из множества всех це­ почек I* символов I. Таким образом определяется понятие языков сетей Петри, которые могут быть полезны при исследовании мно­ гих важных свойств сетей Петри.

Для определения языка сети Петри введем функцию помечания £: T*-»S*, отображающую последовательности переходов Т на последовательности символов из I .

языков.

Различают четыре следующих основных типа языков сетей Петри:

1.Языки L-типа. В этом случае С: 5(p,p)eF, где ц - начальная маркировка, a F - конечное множество заключительных маркировок.

2.Языки G-типа. С: 3pf €F 5(p,P)>mf.

3.Языки Т-типа. С: 6(р,Р) определено, но VteT 8(5(p,p).t) не определено.

4.Языки P-типа. С: 5(ц,р) не определено.

Наиболее изученными в настоящее время являются языки L-

типа.

Приложение 4.2. Моделирование передачи сообщений сетями Петри

Рассмотрим применение сетей Петри к моделированию конечного множества процессов, взаимодействующих с помощью сообщений (схема Риддла ). Сообщения посылаются и запрашиваются специаль­ ными канальными процессами, представляющими комплект сооб­ щений, которые посланы, но еще не приняты, или комплект запросов на сообщения, которые выданы, но еще не удовлетворены. Другие процессы системы называются программными. Они описываются на языке моделирования программных процессов (ЯМПП). Сообще­ ния являются абстрактными элементами, единственной характери­ стикой которых является тип. Число типов сообщений в системе может быть только конечным. Сообщения посылаются из или при­ нимаются в буфер сообщений в каждом из процессов. Существует только по одному буферу на процесс. Командами ЯМПП являются:

Set t : Поместить сообщение типа t в буфер сооб­ щений.

Send ): Послать сообщение в буфер сообщений ка­ нального процесса 1.

Receive 1: Запросить сообщение из канального процесса 1. Ждать, пока не будет получено сообщение. Сообщение помещается в буфер сообщений.

сеть Петри, язык которой используется для исследования структуры системы и организации правильного функционирования.

Для моделирования процесса сетью Петри используется по од­ ной фишке на процесс в качестве программного счетчика. Присут­ ствие сообщения в канальном процессе также представляется фиш­ кой. Поскольку сообщения идентифицируются типом, то необходи­ мо моделировать каждый тип сообщений в канальном процессе от­ дельной позицией. Важным свойством системы является конечность числа сообщений. Каждый программный процесс также конечен. Только очередь сообщений потенциально не ограничена. Способ­ ность моделировать канальные процессы и правильно представлять команды Send и Receive являются наиболее важными аспектами пре­ образования описания на ЯМПП в сеть Петри. Моделируя каналь­ ные процессы множествами позиций (по одной на каждый тип со­ общения), можно представить команду Send переходом, который помещает фишку в позицию, представляющую соответствующий ка­ нальный процесс и тип сообщения. Команда Receive удаляет фишку из любой позиции канального процесса. Конкретная позиция, пред­ ставляющая фишку, определяет тип получаемого сообщения. Эта информация может использоваться в любой последующей команде Unless.

Единственным символом при передаче сообщений является тип сообщений, который посылается или принимается от канального процесса. Поскольку каждый переход в сети Петри приводит к появ­ лению символа в языке для этой сети, то только команды Send и Receive могут быть промоделированы в системе.

Таким образом, существуют два вида позиций в сети Петри. Один вид позиций, помеченных Pnmj. действует как счетчик числа сообщений типа mj в канальном процессе \,. Другой вид позиций

представляет признак завершения команды Send или Receive. Пусть эти команды однозначно помечены символами si,...,sr. Пометим по­ зицию, представляющую признак завершения команды Si с сообще­ нием типа mj символом Рнпу> наличие фишки в такой позиции озна­ чает, что соответствующая команда уже выполнена. Таким образом, команды s: Send 1 и s: Receive 1моделируются сетью Петри следую­ щим образом (рис.Зп):

Рис.3п

Здесь символом Ps,m>помечена команда, предшествующая мо­ делируемой команде, ш - тип сообщения в буфере сообщений ка­ нального процесса 1, установленный командой Set ш перед выполне­ нием команды s: Send 1, a mi,...,mn - возможные типы сообщений в канальном процессе 1, которые могут быть распознаны командами Unless mj (i=l,...,n) после выполнения команды s: Receive 1. Позиция Ps,m, является признаком завершения команды, предшествующей команде s.

Таким образом, входные позиции перехода играют роль пред­ условия, а выходные - постусловия моделируемой команды. По­ скольку постусловия предшествующей команды включают предусло­ вия последующей команды, то соответствующие позиции сети Пет­ ри можно ассоциировать с парой, состоящей из предшествующей и последующей команд. Каждую команду Send или Receive можно рассматривать как пару, состоящую из признака завершения коман­

ды и типа сообщения. При этом каждая команда с различными ти­ пами сообщений в буфере сообщений канального процесса будет мо­ делироваться сетью Петри различным образом. Возникает пробле­ ма моделирования команды, предшествующей первой команде, программного процесса. Наиболее простой способ решения этой проблемы состоит в запуске в начале каждой программы стартовой команды, которая представляется стартовой позицией и служит ос­ новой для порождения всех возможных команд Send и Receive с со­ ответствующим им содержимым буфера сообщений. Этот процесс повторяется, пока все команды Send и Receive не будут порождены, а их последователи не будут идентифицированы. Поскольку число команд и число типов сообщений конечно, то порождается конечное число пар команда-тип сообщения.

Приложение 4.3. Модельный пример взаимодействия объектов, основанного на обмене сообщениями

В качестве примера рассмотрим систему из двух объектов: объекта ReadList, построенного на основе ранее рассмотренного типа comelem и объекта Dialogue, обеспечивающего диалог с поль­ зователем. Объект ReadList,кроме методов, реализованных на основе операций типа comelement, содержит специальный метод HandleMessage, служащий для обработки сообщений. Такой же ме­ тод имеет объект Dialogue. Взаимодействие объектов основано на обмене сообщениями. Методы HandleMessage в ходе обработки принятых или при подготовке отправляемых сообщений вызывают другие методы объектов. Таким образом достигается инкапсуляция не только данных, но и методов объектов.

Пусть объекты ReadList и Dialogue обмениваются сообщения­ ми по общему каналу L. При этом используются следующие типы сообщений:

Процессы инициализируются сообщением List, помещаемым в буфер канального процесса. Поэтому начальная маркировка сети представлена двумя фишками, по одной в каждой из позиций SD и L,List. Для обеспечения нормального завершения процессов мно­ жество конечных маркировок должно содержать фишки в позици­ ях L,Quit и Р6.

Исследуем язык построенной сети Петри. Алфавит языка пред­ ставлен символами List, Element, Eol, Read и Quit.

Рассматриваемый язык можно описать в виде следующей диа­ граммы:

где направленные дуги связывают возможные предшествующие и последующие символы. Данный язык может быть представлен в ви­ де регулярного выражения:

List-(Read2-(List2+Element2+Eol2))*-(1+Read2-Eod2)-Quit

При построении регулярного выражения приняты обычные со­ глашения :

1 .0 - соответствует пустому множеству ф;

1- соответствует множеству из {е} пустой строки е.

2.Если L={XI,X2,...,X„} г конечное множество строк, то множеству L ставится в соответствие xi+x2+...+xn.

3.Если Г1 - регулярное выражение, соответствующее множеству Li, а г2 - регулярное выражение, соответствующее множеству L2, то выражение ri+r2 соответствует множествуЕцЛ^; выражение ггг2 со­ ответствует множеству LJL2; выражение т* (Ы ) соответствует мно­