| |
Сеть Петри ― графическая модель системы с высокой степенью распараллеливания вычислений, используемая для анализа определенных ее свойств.
Сети Петри были разработаны К.А.Петри в ФРГ в начале 60-х годов и используются для моделирования параллельных и асинхронных систем.
Сети Петри представляют собой двудольный ориентированный граф, в котором имеются вершины двух типов: вершины одного типа называются местами, а вершины другого типа - переходами. Элементарная сеть Петри изображена на рис. 1.
В графическом представлении сетей переходы отображаются абстрактными символами "барьерами" (черточками), а места - кружками. Условия-места и события-переходы связаны отношением непосредственной зависимости, которое изображается с помощью направленных дуг, ведущих из мест в переходы и из переходов в места. Места, из которых выходят дуги, направленные к данному переходу, называются его входными местами. Места, в которые входят дуги, исходящие из данного перехода, называются его выходными местами. Так, в элементарной сети на рис.1 место p1 является входным для перехода t , а место p2 - выходным.
Динамика поведения моделируемой системы находит свое отражение в функционировании (работе) сети Петри. Неформально работу сети можно представить как совокупность срабатываний переходов. Переход может сработать, если выполнены все условия реализации соответствующего события. Выполнение условия в сетях Петри отображается разметкой соответствующего места, то есть размещением в нем одного или нескольких маркеров (фишек) в соответствии с емкостью условия. В графическом представлении маркер обозначается точкой внутри соответствующего места. Так, если в место p1 на рис.1 поместить маркер, то это будет означать, что условие совершения события t имеет место (выполнено) и событие может произойти (рис. 2а).
Срабатывание перехода - неделимое действие, изменяющее разметку его входных и выходных мест следующим образом: из каждого входного места маркер изымается, а в каждое входное место - добавляется. Тем самым реализация события изменяет состояние непосредственно связанных с ним условий: предусловия возникновения события перестают существовать, зато возникают постусловия совершения события. Для элементарной сети факт срабатывания разрешенного перехода t отмечается изменением маркировки: маркер, находившийся в месте p1 в результате срабатывания перехода перемещается в место p2 (рис. 2б).
В общем виде, когда переход связан со своими местами не ординарными, а кратными дугами, правило срабатывания перехода звучит так: при срабатывании перехода t он изымает из каждого своего входного места столько маркеров, какова кратность дуги, связывающей этот переход с указанным местом, и добавляет в каждое свое выходное место количество маркеров, равное кратности связывающих их дуг (рис. 3). В настоящее время определены и изучены разнообразные классы сетей Петри.
Литература:
1. Котов В. Е. Сети Петри. - М.: Наука, 1984 г;
2. Писаренкова Н.С. Основы моделирования сетями Петри систем с параллелизмом, 1998 г.
|
|
