Книжка по сетям Петри, страница 3

Динамика поведения моделируемой системы находит свое отрвкение в функционировании (работе) сети Петри, Неформально рэботу сети можно представить как совокупность локальных действий, которые неэывэют(ж сребегыеаниями переходов. Онн соответствуют реализациям событий и приводят к изменению разметки мест, т.е. к локальному изменению условий в системе. Переход может сработать, если выполнены все условия реализации соответствующего событгю. Например, для тэк называемых ординарных сетей Петри (честный случай принятой в настоящее время версии сетей Петри, введенный им в первой работе! все входные месте перехода должны содержать хотя бы по одной фишке. Срабатывание 'переходе — неделимое действие, изменяющее разметку его входных и выходных мест следующим обрезом: из каждого входного месте изымвется по одной фишке, а в кэждое выходное место добавляется по одной фишке. Тем самым реализация события, изображаемого переходом, изменяет состояние (емкость) непосре2ютвенно связанных с ним условий тек, что емкость предусловий, вызвавших реализацию этого события, уменьшается, а емкость постусловий, нэ которые оно влияет, увеличивается.

Переход г~ нэ рис. 1.1, а может сработать, тэк как обе его входных места р~ ирз содержат фишки, э после срабатывания г~ разметке его входных и выходных мест изменяется так, кэк показано не рис. 1.1, 6. Если двэ (и более) перехода могут сработать и они не имеют общих входных мест, то их срабатывания являются независимыми действиями, осуществляемыми в любой последовательности или параллельно. Если несколько переходов могут сработать и имеют общее входное место (кэк переходы г, и гз нэ рис. 1.1, е), то срабатывает только авен, любой из них. При этом может оказаться, что, сработав, этот переход лишит возможности сработать другие переходы (рис. 1.1, б н г) .

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

поведение сети носит недоопределенный недетермннироеенный характер. Аналогичным конфликт возникает в том случае, когда несколько переходов могут сработать и сни имеют общие выходнью места, кэк переходы гз игч (рис. 1.1, б и е). В процессе функционирования сети происходит смене рээметок мест кек результат срабатывания ее переходов. Сеть останэвливэется, если ни олин нз ее переходов не может сработэть (рис. 1.1, е и г) . Не рис. 1.2, а показан еще один пример сети Петри с некоторой начальной разметкой мест, при которой может сработать только переход г„так как его единственное входное место р~ содержит фишку. Переходы гз, тз и тч имеют по одному входному месту, не содержащему фишки, поэтому они не могут срэботэть. Переходы тз й г4 имеют по двэ входных места.

Это оенечеет, что общее условие реализации события, представленного переходом 12 г, или гы является конаюнкцией из двух условий. Для какдого из переходовюобытнй выполнено лишь одно условие, позтому нн гг, нй гч не могут сработать. В результате срабатывания перехшьз П место Р~ лишитсЯ фишки, а места Рг нрг получат по одной фишке (рис. 1.2, 6), изменилась разметка сети и прн новой разметке могут сработать два перехода — гг и гч. Срабатывание любого из них поменяют Фишку в место рт, после чего возможно срабатьь ванне переходов Г, и Г,.

При атом, если срабатываот оба перехода Гг и тедо того, как сработают гг и гы то местор, будет содержать две фишки (рис. 1.2, в), в противном случае — одну. )йасторт — Общее входное масте для переходов гг и гы Если рт содержит одну фишку, то сможет сработать только один нз переходов Гг или Гы так как сработавший переход заберет единственную фишку.

Если жерт содержит две Фишки, то возможны различные продолжения работы сети: [1) сработает гвреход т„затем — пареход гь; (2) сработает переход гы затем — переход (Э) дважды сработает гь аз, не может реалиаовать возможность срабатывания; [4) дважды сработает гы а г, не сможет сработать ни разу.

В первых двух случаях местаР, и р, получат по фишке, в последних двух случаях одно из няст Рг или Рг будет содержать лве фишки, а второе не будет иметь фишек. Если р, и р, соде)нхат ло фишке, то срабатывание переходов Г, н г, приведет к разметке, которая уже возникла ранее в про. цессе функционирования сети (рис.

1.2, б), и последующая работа сети будет повторять описанную выше. Если же одно место содержит две фишки (например, Рг), то сработать может (дважды) только адин переход (в длн- НОМ СЛУЧав тг), ПОСЛЕ ЧЕГО КажДЫй ИЗ ПЕРЕХОДОВ Гг И Гч ИМЕЕТ В ОДНОМ входном месте две Фишки, а в другом — ни одной (рис. 1.2, з) . Возникает разметка.

при которой ни один из переходов сети не может сработать, и сеть Петри останавливается. Анализ Работы сети Петри, показанный на рис. 1.2, позволяет сделать некоторые выводы о функционировании моделируемой сетью системы (зто может быть, например, фрагмент операционной системы, состоящей нз параллельных циклических процессов, взаимодействующих друг с другоы) . В частности, можно отметить, что система способна функционировать циклически как угодно долго. но может и остановиться в "тупиковой" ситуации, показанной на рис.

1.2, г. Таким образом, сети Петри формализуют понятие абстрактной асинхронной системы — динамической структуры из событий и условий. В общей теории сетей сеть Петри рассматривается как один из способов сетевого моделирования систем. Вводятся болев общие сетевые модели. Их единую основу образует понятие неинтерпретированной ориентйрованной сети из условий и событий:, которая описывает только статическое строение системы [форыальное определение сети дано в % 1.2) . Самой общей в спектре динамических сетевых моделей является, по-вндимому, условнособытнйная систама [37[, которая представляет собой сеть, дополненную правилами изменений условий в результате реализации событий.

Сеть Петри можно считать конкретизацией условноообытийной системы. Если сеть Петри описывает функциональную схему моделируемой системы, то работа сети моделирует процесс, происходящий прн Функционировании системы. Поскольку процесс протекает во времени, для его изучения нужно зафиксировать его в форме некоторой' "истории процесса", которую обычно отождествляют с самим процессом. Недетерминирован- 13 ный характер функционирования асинхронной системы и соответствую.

шей сети Петри приводит к тому, что система может порождать не единственный процесс, а множество всаможных процессов. Кроме того, процес сы, порождаемые такими системами, являются параллельными. Возникает вопрос, каким обрезам Формализовать понятие параллельного процесса, в какой системе понятий можно удобно и полно описывать параллельные процессы (а также множества параллельных процессов) и изучать их. Другими словами, возникает необходимость в разработке моде. лей параллельных процессов.

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

Подробнее этот вопрос обсуждается в главе 7. $ 1.2. Фармельпое опредеделяе сетя Петрп Зафиксируем основные математические обозначения, которые будем использовать в формальных определениях. ( а, Ь,..., с( — множество, состоящее из злемемтов а, Ь,..., с; (а, Ь,..., с( — упорядочемное множество (набор(, состоящее из злемен',х ( А (х)1 — множество значений переменной х, удовлетворяющих условию А(х(; х,.... у Е Х вЂ” злементы х,..., у принадлежат множеству Х; Х,..., У ъ, Е -множества Х, ... У являются частью (подмножествами) множества Е," 4, ~ — отрицание отношений Е и С; (Х ( — мощность (чиело злементов( множества Х; ф — пустое множество; О, Гт, ~ — тезретико-множественные операции объединения, пересечения и разности множеств; 4, Х...