Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 67
Текст из файла (страница 67)
Так, маркировка сети Петри, приведенной на рис. 4.81, определяетсн как Уз(рг) = Уз(рз) = 1, Уз(рт) = Р(Р4) = Уз(рб) = б. Удобно представлять маркировку как и-вектор ул = (узг,улт,... ...,уз„) (где и = ~Р~), каждый элемент которого уз; есть уз(р;), а также как комплект и, в который входят позиции сети р; б Р и тг(Р' 1з) = уз(Р;). Сеть Петри С с определенной в ней маркировкой уз называется маркированной остью Летри.
Маркировка сети может изменяться в резулыате запуска переходов. Переход 8 маркированной сети Петри С с маркировкой уз называется разрешенным, если 1(8у) Э уз, т. е. в каждой входной позиции 11 находится не меньше фишек, чем из этой позиции исходит дуг в г,. Всякий разрешенный переход может запуститься. 84.11. Модели оаоние аешомошных сисгпем сегпеми Петри 315 В результате запуска перехода 81 маркировка сети уз изменяется на новую: уз' = уз — 1(81) + 0(8 ), т. е. из всякой входной позиции р; перехода Ц удаляется столько фишек, сколько дуг ведет из р; в гу, а в каждую выходную позицию рь помещается столько фипуек, сколько дуг ведет из 8! в рь. Последовательность запусков переходов называется выполнением согни Петри.
Рассмотрим зьзпакнеиие сетя Петри, иаебранеинай иа рис. 4.81. В мзчзльнаа маркэрзаке разрешен только переход ез. При егз запуске Оишка удалится ,ив рз, а аатем з пеэзщин рз и рз добавится па фншке, т. е. з реаупьтате запуске в какай маркировке рз появится Оишка еше и з рз. Теперь становятся разреизеиныии переходм Ез, Ее. Поскольку запуститься макет любой разрешенный переход, кредпзпзним, что аапускаегся переход со После ега аапуска иэ паанпий 'Рз н рз оишки удаляются, а з познани рз паязится эдне Оишка. В пааучизнзейся маркировке Пз не разрешен ни один переход. На этом выполнение сети Петри закеичиэается Рассмотрим маркировку уз сети Петри С = (Р, Т, 1, 0). Маркировка уз' называется непосредственно достижимой из уз, если найдется такай переход 1 б Т, разрешенный в ул, что при его Запуске получается маркировка,и'; в этом случае пара (уз, уз') принадлежит отношению непосредственной достижимосгпи, определенному на Р .
Транзитивное замыкание этого отношения называется отношением достижимости. Маркировки уз' такие, что пара (ул, уз') принадлежит отношению достижимости, называются достижимыми из уз. Множество достижимых из,и маркировок сети Петри С называется множеспзвом достижимости и обозначается В(С, уз). Интерпретация сетей Петри основана на понятиях условия и события. Состояние системы описывается совокупностью услаВий. Функционирование системы состоит в осуществлении последовательности определенных действий, т. е. событий. Для'возникновения события необходимо выполнение некоторых условий, называемых предусловиями.
Возникновение события может привести к нарушению предусловий и к выполнению некоторых других условий, называемых посгпусловиями. В сети Петри условия моделируются позициями, события — переходами. Предусловия события представляются входными позициями соответствующего перехода, постусловия — выходными позициями. Возникновение события моделируется запуском перехода. Выполнение условий представляется наличием фишек в со ответствуюшиХ позициях, невыполнение — их отсутствием. Рассмотрим, например, простую вычислительную систему, последовательно обрабатывающую задания, которые поступают во входную очередь. Когда процессор свободен и во входной очереди имеется задание, оно обрабатывается процессором, затем выводится.
Эту систему можно промоделировать сетью Петри, изображенной на рис. 4.82. 376 Гл. 4. Теория формальныг грамматик и автоматов Установим, какие особенности систем учитывают сети Петри. Это прежде всего аеингронмость. В сети Петри отсутствует понятие времени. Время возникновения событий никак не указывается, но тем не менее структура сети Петри устанавливает частичный порядок возникновения событий. Далее, поскольку возникновение событий представляется запуском переходов, предполагается, что события происходят мгновенно. Если же моделируемое событие имеет отличную от нуля длительность, как, например, событие "задание обрабатывается" (рис.
4.82), н это существенно, то она представляется в виде двух мгновенных событий типа "начало события", "конец события" и условия "событие происходит" (рис. 4.83). Кроме того, считается, что события происходят меоднооремемно. Действительно, если допустить одновременное возникновение некоторых событий т и у, которым в сети Петри соответствуют переходы Ц и 8т, то можно вести дополнительный переход гб су(т; ) = У(81)+Щ), 0(813) = О(8;)+0(1 ), интерпретируюшийся как одновременное Задание помещается возникновение событий т и у. В зтом случае переходы можно запускать последовательно. Задание обрабатывается Процессор свободен Задание не ждет Начало выполнения гадания Заверщенпе выполнения гадания Вывод гадания Рнс. 4.82 Рнс.
4.88 Другим важным свойством сетей Петри как инструмента моделирования является их способность представлять параллелизм н конфликтные ситуации. Параллелизм двух событий представляется двумя разрешенными переходами, множества входных позиций которых не пересекаются (рис. 4.84), конфликт — переходами с обшей входной позицией (рис. 4.85).
Сети Петри используют в основном как формальный аппарат при моделировании систем, которым присущ параллелизм. Если рассматривать процесс проектирования в целом, то возможны два принципиально различных подхода к использованию сетей Петри. В первом система моделируется сетью Петри, которая преобразуется по определенным правилам к некоторому "оптимальномуя виду. Полученная сеть Петри преобразуется в проект системы. Предполагается, что он также оптимальный.
Здесь сети Петри применяют непосредственно при проектировании. Этот подход, однако, имеет трудности, связанные с неоднозначностью обратного преобразования (сети Петри в проект системы), что подвер- $4.11. Моделирование автоматные систпсм сетпями Летри 377 гает сомнению оптимальность получаемого проекта. Во втором, более общепринятом подходе сначала с помощью обычных средств создается проект системы и по нему строится модель в виде сети Петри.
Затем исследуются свойства полученной сети и делаются выводы о свойствах и характеристиках проекта. Если они неуда- Рнс. 4.8б Рнс. 4.85 Рнс. 4.84 Илетворительны, то полученные в результате исследования сети .Петри данные используют для модификации проекта. Модифици'рованный проект снова преобразуется в сеть Петри, цикл повторя"Ется. Этот процесс заканчивается, когда сеть Петри будет обладать необходимыми свойствами. Рассмотрим, какие свойства сети Петри как модели системы могут интересовать проектировщика. Одно из важнейших свойств — безопасность. Позиция сети Петри называется 6еэояасноб, если число фишек в ней никогда не превышает 1.
Маркировайная сеть Петри безопасна, если безопасны все ее позиции. Эта свойство очень важно при интерпретации позиций как простых условий: если в позиции есть фишка, то условие выполняется, если нет, что не выполняется. Если интерпретация фишек более сложная, например, количество фишек показывает число информационных единиц, то может быть интересен вопрос: ограничено ли число фишек в данной позиции, и если да, то какова граница? Так приходим к свойству ограниченности. Позиция называется Й-ограниченной, если число фишек в ней в любой достижимой маркировке не превышает целого к.
Маркированная сеть Петри называется к-ограниченной, если ее позиции являются к-ограниченными. В сети Петри, приведенной на рис. 4.86, позиции рт, рт являются безопасными, позиция рз 2-ограниченная, вся сеть 2-ограниченная. В случае когда фишки интерпретируются как некоторые ресурсы, они не должны ни создаваться, нн уничтожаться. Иначе говоря, в сети должен действовать закон сохранения.
Маркированная сеть Петри называется строго сохраняющей, если мощность маркировки (как комплекта позиций) постоянна. В общем случае фишка может интерпретироваться как некоторое число зле- (1, О, О, 0) ~~э (1,и,о,о) (О,н,1,0) $)г (О,и,1 оэ) уй (О, и, 1, н) (О, О, 1, 0) $)3 (1, О, О, 0) (О, 1, О, 0) (О, О, О, 1) (О. О, 1, 0) Рис.
4.88 Рнс. 4.87 378 Гл.4. Теории формальных грамматик и автоматов ментарных ресурсов, причем это число меняется от позиции к позиции. Введем понятие вэвешиванил позиций: вектор Иг = = (ш), шэ, ..., ю„), где ю( — вес позиции р(. Сеть Петри называется сохраняющей по отношению к вектлору взвешивания И', если скалярное произведение вектора И' и маркировки (рассматриваемой как вектор) постоянно; сеть Петри сохраняющая, если она является сохраняющей по отношению к вектору взвешивания И', все элементы которого положительны.
Рассмотренные до сих пор свойства относятся как к последовательным, так и к параллельным системам. Но при переходе от последовательных систем к параллельным возникают принципиально новые трудности: вазможность тупиковых ситуаций. Туникам в сети Петри называется множество переходов, которые в некоторой достижимой маркировке ((' и в последующих достижимых пз )(' маркировках не разрешены. Свойство возможности возникновения тупиков в системе моделируется свойством активности в сетях Петри.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
