Труды КНЦ вып.3 (ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ вып.1 3/2010(3))

состояние сети Петри характеризуется неупорядо­ ченным набором позиций. Каждой позиции сети ста­ вится в соответствие натуральное число, указываю­ щее количество фишек в данной позиции. Это число называют разметкой позиции, а совокупность таких чисел для всех позиций сети называют разметкой сети. Позиция может и не содержать фишек, т.е. иметь нулевую разметку. Процесс перераспределе­ ния фишек называется выполнением сети Петри. Позиции и переходы соединены направленными ду­ гами, каждая из которых имеет свой вес. Дуги можно разделить на два типа: дуги, направленные от пози­ ции к переходам и дуги, направленные от переходов к позициям. При срабатывании перехода фишка уда­ ляется из каждой его входной позиции и вносится в каждую выходную позицию. Срабатывание перехода происходит мгновенно - за нулевое время. Если од­ новременно активированы два либо более переходов, то срабатывает только один из них (одновременное срабатывание двух переходов в сетях Петри не до­ пускается). Выбор запускаемого перехода осуществ­ ляется случайно, в этом смысле сети Петри - неде­ терминированная модель. Помимо недетерминиро­ ванности сеть Петри характеризуется асинхронно- стью - она работает не в физическом, а в логическом (дискретном) времени, определяемом частичной упорядоченностью событий (переходов). Для детер- минизации сетей Петри необходимо дополнительно привлечь механизм выбора - ввести управление се­ тью. Рис.1. Пример сети Петри P1 - P6 обозначают позиции, tl- t8 обозначают переходы, чёрный кружок — фишка (метка или маркер). При срабатывании перехода tl фишка переносится из позиции P1 в позицию P2, присрабатывании перехода t2 фишка переносится из позиции P2 в позиции P3 и P4 и т.д. Сети Петри занимают промежуточное положение между машинами Тьюринга и конечными автомата­ ми. Вообще говоря, конечные автоматы являются частным случаем сетей Петри. Сети Петри лучше всего подходят для описания любых асинхронных систем, тогда как конечные автоматы - для последо­ вательных систем. Наглядность динамики и компо­ зиционные возможности сетей Петри выше, чем у конечных автоматов, но при этом компактность представления предпочтительнее у конечных авто­ матов. Конечные автоматы эквивалентны автомат­ ным сетям Петри - сетям, в которых каждый переход может иметь одну входную и одну выходную пози­ цию. Конечные автоматы анализировать гораздо проще, чем сети Петри и проще, чем машины Тью­ ринга. Что касается отношения сетей Петри к маши­ не Тьюринга, то достаточно расширить сеть Петри сдерживающими дугами (позволяющими определять отсутствие фишек в данной позиции), как она тут же становится эквивалентной машине Тьюринга [7]. Сети Петри можно интерпретировать по-разному. Можно представить себе, что позиции представляют условия (буфер пуст, файл закрыт и т.д.), а переходы - события (получение информации в буфер, запись в файл). Однако основная интерпретация сетей Петри для моделирования систем дается в терминах событий и условий. Переходы сетевой модели интерпретиру­ ются как события, входные позиции перехода - как условия возникновения события (предусловия), вы­ ходные позиции - как условия, возникающие после совершения события (постусловия). Состояние систе­ мы описывается совокупностью условий. Функциони­ рование системы состоит в осуществлении последова­ тельности событий. Для возникновения события не­ обходимо выполнение некоторых предусловий. Воз­ никновение событий может привести к выполнению постусловий. В сети Петри условия моделируются позициями, события - переходами. Наглядность сетевого моделирования систем су­ щественно повышается, если использовать теорети­ ко-графовое представление сети Петри в виде дву­ дольного ориентированного мультиграфа. Напом­ ним, что двудольный граф - это такой граф, множе­ ство вершин которого разбивается на два подмноже­ ства и не существует дуги, соединяющей две верши­ ны одного подмножества. Граф сетей Петри является мультиграфом, т.к. он допускает существование кратных дуг от одной вершины к другой [8]. Сеть Петри представляет собой ориентированный граф с вершинами двух типов - позициями и переходами, где дугами могут соединяться только вершины раз­ личных типов. Предметом теоретического исследования сетей Петри является процесс их функционирования, т.е. возможные последовательности срабатывания пере­ ходов и свойства получаемых при этом разметок се­ ти. И, как обычно в математике, такие исследования формулируются в виде утверждений двух основных типов - утверждение о существовании и утверждения об обязательности. Анализ сетей Петри заключается в распознавании ряда свойств, характеризующих сеть. Основными свойствами сети Петри являются: • ограниченность - число фишек в любой пози­ ции сети не может превысить некоторого значения K. Под ограниченностью понимают свойство сети не допускать превышения количества фишек в данной позиции некоторого фиксированного числа; • безопасность - частный случай ограниченно­ сти, К=1. Безопасной является такая сеть Петри, в которой ни при каких условиях не может появиться более одной метки в каждой из позиций. Для иссле­ дуемой системы это означает возможность функцио­ нирования ее в стационарном режиме. На основе 36