Cети петри

7. СЕТИ ПЕТРИ 1. Назначение и общая характеристика сетей Петри Среди многих методов описания и анализа дискретных параллельных систем выделяют подход, который основан на использовании сетевых моделей, относящихся к сетям специального вида, предложенных Карлом Петри для моделирования асин- хронных информационных потоков в системах преобразования данных. Сети Петри обеспечивают описание как алгоритмов и программ, так и собст- венно вычислительных систем

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

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

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

В общем случае одна и та же система может функционировать в одних и тех же усло- виях по-разному, порождая некоторое множество процессов, т. е. функционировать недетерминированно. Реальная система функционирует во времени, событие происходит в некоторые моменты времени и длится некоторое время. В синхронных моделях дискретных систем события явно привязаны к определенным моментам или интервалам времени, в которые происходит одновременное изменение состояния всех компонентов систе-

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

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

При этом глобальные ситуации в системе формируются с помощью локальных операций, называемых условиями реа- лизации событий. Условие имеет емкость условие не выполнено емкость 0 , выполнено ем- кость 1 , условие выполнено с n-кратным запасом емкость n, где n целое поло- жительное число . Условие соответствует таким ситуациям в моделируемой системе, как наличие данных для операции в программе, состояние некоторого регистра в ЭВМ и т. п. Определенные сочетания условий разрешают реализоваться

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

называемых соответственно множеством пере- ходов и множеством позиций. В графическом представлении сетей переходы изо- бражаются барьерами или планками t , а позиции кружками Р рис. 7.1 . Условия и события-переходы связаны отношением непосредственной зависи- мости, которое изображается с помощью направленных дуг, ведущих из позиции в переходы и из переходов в позиции. Позиции, из которых ведут дуги на данный пере- ход, называются его выходными позициями.

Позиции, на которые ведут дуги из дан- ного перехода, называются его входными позициями. 103 t1 t2 Р1 Р2 t3 Р3 Р5 Р4 t4 Р6 Рис. 1. Графическое изображение сети Петри Выполнение условий изображается разметкой соответствующей позиции, а именно помещением числа n фишек маркеров в соответствующее место, где n 0 емкость условия. Например Р - условие р не выполнено Р - условие р имеет емкость 3

Р - условие р выполнено Р - условие р имеет емкость 5. Неформально работу сети можно представить как совокупность локальных действий, которые называются срабатываниями переходов. Они соответствуют реа- лизациям событий и приводят к изменению разметки позиций, т. е. к локальному из- менению условий в системе. Таким образом, сети Петри позволяют перейти от понятий абстрактной асин- хронной системы к динамической структуре из событий

и условий. В общей теории сетей сеть Петри рассматривается как один из способов сетевого моделирования сис- тем. Вводятся обобщенные сетевые модели. Их единую основу образует понятие не- интерпретированной ориентированной сети из условий и событий, которая описывает только статическое строение системы. Если сеть Петри описывает функциональную схему моделируемой системы, то работа сети моделирует процесс, происходящий при функционировании системы. 7.2. Структура и способы представления сетей

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

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

Выделяют четыре типа задач исследования объектов с помощью сетей Петри 1 интерпретация программирование объекта , связанная с адекватным пред- ставлением моделируемого объекта соответствующей сетью Петри 2 программирование модели в конкретной операционной среде 3 исследование модели 4 кросс-трансляция с языка сетей Петри на языки программирования. Возможности сетей Петри ограничиваются для автоматных сетей и маркиро- ванных графов, которые допускают

один вход и один выход для переходов и позиций соответственно. Введение в рассмотрение мультипликативности для дуг и количества фишек в позициях позволяет моделировать не только функционирование параллель- ных систем, но и динамику объемов ресурсов. 7.2.1. Структура сетей Петри Сеть Петри состоит из 4-х элементов множество позиций Р, множество пере- ходов Т, входная функция I и выходная функция

О. Входная и выходная функции связаны с переходами и позициями. Входная функция I отображает переход tj в мно- жество позиций I tj , называемых входными позициями перехода. Выходная функция О отображает переход tj в множество позиций О tj , называемых выходными пози- циями перехода. Структура сети Петри определяется ее позициями, переходами входной и вы- ходной функции.

Определение Сеть Петри С является четверкой С Р, Т, I, О , где Р р1, p2 pn конечное множество позиций, n ? 0 Т t1, t2 tm конечное множество переходов, m ? 0. Множество позиций и множество переходов не пересекаются, Р ? Т ? I T ? P? есть входная функция отображение из переходов в комплекты по- зиций

О T ? P? есть выходная функция отображение из переходов в комплекты позиций. Мощность множества Р есть число n, а мощность множества Т есть число m. Произвольный элемент Р обозначается символом рi, i 1 n, а произвольный эле- мент Т символом tj, j 1 m. Позиция pi является входной позицией перехода tj в том случае, если pi ?I tj pi является выходной позицией, если pi ?О tj .

Входы и выходы переходов представляют собой комплекты позиций. Ком- плект является обобщением множества, в которое включены многократно повто- ряющиеся элементы тиражированные элементы. Использование комплектов, а не множеств для входов и выходов перехода позволяет позиции иметь кратный вход ли- бо кратный выход для соответствующего перехода. Кратность входной позиции pi для перехода tj есть число появлений позиции во входном комплекте перехода

pi, I tj . Аналогично кратность выходной позиции pi для перехода tj есть число появле- ний позиции в выходном комплекте перехода pi, О tj . Если входная и выходная функции являются множествами а не комплектами , то кратность каждой позиции есть либо 0, либо 1. Входные и выходные функции используются для отображения позиций в ком- плекты переходов или наоборот для отображения переходов в комплекты позиций. Определим, что переход tj является входом позиции pi,

если pi есть выход tj. Переход tj есть выход позиции pi, если pi есть вход tj. 7.2.2. Графы сетей Петри Наглядность сетевого моделирования систем существенно повышается, если использовать теоретико-графовое представление сети Петри в виде двудольного ори- ентированного мультиграфа. В соответствии с данным подходом структура сети Петри представляет собой совокупность позиций и переходов, а граф сети два типа узлов, соединенных дуга- ми стрелками .

Кружок О является позицией, а планка переходом. Ориентированные дуги соединяют позиции и переходы, при этом одни дуги направлены от позиций к пере- ходам, а другие от переходов к позициям. Дуга, направленная от позиции рi к пере- ходу tj, определяет позицию, которая является входом перехода. Кратные входы в пе- реход указываются кратными дугами из входных позиций в переход. Выходная пози- ция указывается дугой от перехода к позиции.

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

или позиций следовательно, такой граф является двудольным ориентированным мультиграфом. В дальнейшем для простоты будем называть его просто графом сети Петри. Определение. Граф G сети Петри есть двудольный ориентированный мульти- граф G V, A , где V v1, v2 vs множество вершин А а1, а2 аr комплект направленных дуг аi vj, vk , где vj, vk ?V. Множество V может быть разбито на два непересекающихся подмножест- ва

Р и Т, таких, что V Р ? Т и P ? Т Кроме того для любой направленной дуги ai ?А, если аi vj, vk , при условии, что тогда либо vj ?Р и vk ?Т, либо vj ?Т и vk ?Р. Для демонстрации эквивалентности двух представлений сети Петри структуры сети Петри и графа сети Петри рис. 7.2 и 7.3 покажем, каким образом можно пре- образовать одно представление сети в друге. Предположим, что дана структура сети

Петри С Р, Т, I, О с Р р1, p2 pn и Т t1, t2 tm . Тогда граф сети Петри можно определить следующим образом. Пусть V Р ? Т. Определим А как комплект направленных дуг, такой что для всех рi ?Р и tj ?Т pi, tj , A pi, I tj tj, pi , A pi, O tj , тогда G V, A есть граф сети Петри, эквивалентный структуре сети

Петри С Р, Т, I, О . Структура сети Петри С Р, Т, I, О , где Р p1, p2, p3, p4, p5 , T t1, t2, t3, t4 , I t1 p1 , I t2 p2, p3, p5 , I t3 p3 , I t4 p4 , О t1 p2, p3, p5 , О t2 p5 , О t3 p4 , О t4 p2, p3 . Рис. 7.2. Структура сети Петри С Р, Т, I, О На рис. 7.2 структура сети Петри представлена в виде четверки, которая состо- ит

из множества позиций Р , множества переходов Т , входной функции I T ? P? и выходной функции О T ? P Р2 t1 t4 t2 Р4 Р1 Р5 Р3 t3 Рис. 7.3. Граф сети Петри G V, A Таким образом, граф сети Петри, изображенный на рис. 7.3 эквивалентен структуре сети Петри на рис. 7.2. 7.2.3. Маркировка сетей Петри Маркировка сети

Петри заключается в присвоении фишек маркеров пози- циям сети Петри. Маркировка сети Петри есть функция, отображающая множество позиций Р в множество неотрицательных целых чисел N. Р ? N. Если маркированная сеть Петри М С, есть совокупность структуры сети Петри С Р, Т, I, О и маркировки , то она может быть записана в виде

М Р, Т, I, О На рис. 7.4 представлена маркированная сеть Петри. Р2 t1 t4 t2 Р4 Р1 Р5 Р3 t3 Рис. 7.4. Маркированная сеть Петри. Маркировка 0, 2, 0, 5, 1 P1 t2 P2 47 13 t1 t3 7 P3 42 P4 Рис. 7.5. Маркированная сеть Петри с очень большой маркировкой 47, 13, 7, 42 7.2.4. Работа сетей Петри Работа сети Петри заключается в перемещении фишек из одних позиций в дру- гие.

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

равное числу дуг из позиции в переход. Кратные фишки необходимы для кратных входных дуг. Фишки во входной позиции, которые разрешают переход, называются его разрешающими фишками. Например, если позиции р1 и р2 служат входами для перехода t4, тогда t4 разрешен, если р1 и р2 имеют хотя бы по одной фиш- ке. Для перехода t7 с входным комплектом p6, p6, p6 позиция р6 должна обладать по крайней мере тремя фишками, для того чтобы t7 был разрешен.

Определение. Переход tj ?Т в маркированной сети Петри С Р, Т, I, О с маркировкой разрешен, если для всех pi ?P pi ? pi, I tj . Переход запускается удалением всех разрешающих фишек из его входных по- зиций и последующим помещением в каждую из его выходных позиций по одной фишке для каждой дуги. Кратные фишки создаются для кратных выходных дуг.

Например, переход t3 с I t3 p2 и О t3 p7, р13 разрешен всякий раз, ко- гда в р2 будет хотя бы одна фишка. Переход t3 запускается удалением одной фишки из позиции р2 и помещением одной фишки в позицию р7 и в р13 его выходы . Дополни- тельные фишки в позиции р2 не влияют на запуск t3 хотя они могут разрешать до- полнительные запуски t3 . Переход t2, в котором I t2 p21, р23 и О t2 p23, р25, р25 запускается удалением одной фишки из р21 и одной фишки из р23, при

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

реход не разрешен и не может быть запущен. Определение. Переход tj в маркированной сети Петри с маркировкой может быть запущен всякий раз, когда он разрешен. В результате запуска разрешенного пе- рехода tj образуется новая маркировка , определяемая следующим соотношением pi pi pi, I tj pi, O tj . 7.3. Анализ сетей Петри С помощью сетей Петри можно моделировать широкий класс систем, пред- ставляя должным образом взаимодействие

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

Петри. Для этого рассмотрим типы задач, которые могут решаться с применением сетей Петри. Цель анализа сети Петри получение ответа на вопрос о конкретной сети Петри. 7.3.1. Безопасность сети Петри Одно из важнейших свойств сети Петри, которая должна моделировать реаль- ное устройство, безопасность. Позиция сети Петри является безопасной, если число фишек в ней никогда не превышает 1.

Сеть Петри безопасна, если безопасны все по- зиции сети. Определение. Позиция pi ?P сети Петри С Р, Т, I, О с начальной маркиров- кой является безопасной, если pi ? 1 для любой ?R C Сеть Петри безо- пасна, если безопасна каждая ее позиция. Безопасность очень важное свойство для устройств аппаратного обеспечения. Если позиция безопасна, то число фишек в ней равно 0 или 1.

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

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

если pi ?I tj и pi ?О tj , тогда добавить pi к О tj если pi ?О tj и pi ? j , тогда добавить pi к I tj . I t Цель введения этой новой позиции pi представить дополнительное условие pi пуста . Следовательно pi и pi находятся в следующей зависимости pi имеет фишку, только если pi не имеет фишки и наоборот. Любой переход, удаляющий фишку из pi должен помещать фишку в pi , а всякий переход, удаляющий фишку из pi , должен помещать фишку в pi.

Начальная маркировка также должна быть модифи- цирована для обеспечения того, чтобы только одна фишка была либо в pi , либо в pi . Такая принудительная безопасность возможна лишь для позиций, которые в началь- ной маркировке являются безопасными, и входная, и выходная кратность которых равна 0 или 1 для всех переходов. Позиция, имеющая для некоторого перехода вы- ходную кратность 2, будет получать при его запуске две фишки и, следовательно, не может быть безопасной.

На рис. 7.6 простая сеть Петри а преобразована в безо- пасную б . P3 P3 P1 P2 P1 P2 t1 t2 t3 t2 t1 t3 P1 P2 а б Рис. 7.6. а сеть Петри, не являющаяся безопасной б безопасная сеть Петри, эквива- лентная сети а 7.3.2. Анализ живучести сохранения сетей Петри Сети Петри можно использовать для моделирования систем распределения ре- сурсов.

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

является выходной. Сети Петри такого типа должны обладать свойством живучести или сохране- ния. Для этого фишки, представляющие ресурсы, не должны создаваться или унич- тожаться, общее число фишек в сети должно оставаться постоянным. Определение. Сеть Петри С Р, Т, I, О с начальной маркировкой называ- ется строго сохраняющей, если для всех ?R C p i ? p i . pi ?p pi ?p Строгое сохранение требует, чтобы число входов в каждый переход должно равнялось

числу выходов I tj O tj . Если это условие не будет выполняться, то за- пуск перехода изменил бы число фишек в сети. Рассмотрим график сети Петри рис. 7.7 , которая не является строго сохра- няющей. В этой сети запуск перехода t1 или t2 уменьшает число фишек на 1, а запуск переходов t3 или t4 добавит фишку к маркировке. Эту сеть можно преобразовать в сеть строго сохраняющую рис. 7.8 . Сеть Петри должна сохранять ресурсы, которые она моделирует.

Однако вза- имно однозначного соответствия между фишками и ресурсами нет. Фишка может представлять собой один программный счетчик или какой- нибудь другой элемент или несколько ресурсов сразу. В этом случае фишка исполь- зуется для создания кратных фишек путем запуска перехода с большим числом выхо- дов, чем входов. P1 P2 P5 t1 t2 P3 P4 t3 t4 Рис. 7.7. Сеть Петри, не являющаяся строго сохраняющей

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

P1 P2 P5 t1 t2 P3 P4 t3 t4 Рис. 7.8. Строго сохраняющая сеть Петри, эквивалентная сети, изображенной на рис. 7.7 Вектор взвешивания w w1, w2 wn определяет вес wi для каждой позиции pi ?Р. Определение. Сеть Петри С P, T, I, O с начальной маркировкой называет- ся сохраняющей по отношению к вектору взвешивания w, где w w1, w2 wn , при n P , wi 0, если для всех ?

R C w i ? p i ? w i ? p i . i i Строго сохраняющая сеть Петри является сохраняющей по отношению к век- тору взвешивания 1, 1 1 . Все сети Петри являются сохраняющими по отношению к вектору взвешивания 0, 0 0 . 7.3.3. Активность сети Петри Рассмотрим систему, включающую два различных ресурса q и r и два процесса а и b. Если оба процесса нуждаются в обоих ресурсах им необходимо будет совмест- но использовать ресурсы.

Для выполнения этого требуется, чтобы каждый процесс запрашивал ресурс, а затем освобождал его. Предположим, что процесс а сначала за- прашивает ресурс q, затем ресурс r и, наконец, освобождает и q, и r. Процесс b рабо- тает аналогично, но сначала запрашивает r, а затем q рис. 7.9 . Процесс а Процесс b Р4 P1 Р6 t1 t4 Р5 P2 Р7 t2 t5 P3 Р8 t3 t6 Рис. 7.9. Распределение ресурсов для случая двух процессов а и b и двух ресурсов q моделируется

Р4 и r моделируется Р5 Начальная маркировка помечает ресурсы q Р4 и r Р5 доступными и указыва- ет на готовность процессов a и b. Одним выполнением этой сети является t1 t2 t3 t4 t5 t6 другим t4 t5 t6 t1 t2 t3 . Ни одно из этих выполнений не приводит к тупику. Однако рас- смотрим последовательность, которая начинается переходами t1, t4, а процесс а обла- дает ресурсом q, чтобы получить r процесс b обладает ресурсом r,

чтобы получить q. Система заблокирована, то есть никакой процесс продолжаться не может. Тупик в сети Петри это переход или множество переходов , которые не могут быть запущены. В сети Петри рис. 7.9 тупик возникает, если нельзя запустить переходы t2, t5. Переход называется активным, если он не заблокирован нетупиковый . 7.3.4. Достижимость и покрываемость Определение. Задача достижимости.

Для данной сети Петри С P, T, I, O с маркировкой и маркировки определить ?R C Задача достижимости основная задача анализа сети Петри. Многие задачи анализа могут быть сформулированы в терминах такой задачи достижимости. Множество достижимости сети Петри представляет собой дерево достижимости. Пусть имеется сеть Петри, представленная на рис. 7.10.

Ее начальная маркировка 1, 0, 0 . В этой начальной маркировке разрешены t1 и t2. Чтобы рассмотреть все мно- жество достижимости, определим новые вершины в дереве достижимости для других достижимых маркировок, получающихся в результате запуска каждого из этих двух переходов. Начальной корневой является вершина, соответствующая начальной маркировке. Дуга, помеченная запускаемым переходом, приводит из начальной мар- кировки к каждой из новых маркировок

рис. 7.11 . Это частичное дерево показывает все маркировки, непосредственно достижимые из начальной маркировки. P2 1, 0, 0 t1 t3 t1 t2 1, 1, 0 0, 1, 1 t2 P1 P3 Рис. 7.10. Маркированная сеть Петри, Рис. 7.11. Первый шаг для которой строится дерево достижимости построения дерева достижимости Теперь необходимо рассмотреть все маркировки, достижимые из новых марки- ровок.

Из маркировки 1, 1, 0 можно снова запустить t1 получая 1, 2, 0 и t2 получая 0, 2, 1 из 0, 1, 1 можно запустить t3 получая 0, 0, 1 . Это порождает дерево, изо- браженное на рис. 7.12. Начиная с трех новых маркировок, необходимо повторить этот процесс, порождая новые маркировки, которые нужно ввести в дерево, как пока- зано на рис. 7.13. 1, 0, 0 t1 t2 1, 1, 0 0, 1, 1 t1 t2 t3 1, 2, 0 0, 2, 1 0, 0, 1

Рис. 7.12. Второй шаг построения дерева достижимости 113 1, 0, 0 t1 t2 1, 1, 0 0, 1, 1 t1 t2 t3 1, 2, 0 0, 2, 1 0, 0, 1 1, 3, 0 0, 3, 1 0, 1, 1 Рис. 7.13. Третий шаг построения дерева достижимости Заметим, что маркировка 0, 0, 1 пассивная никакой переход в ней не является разрешенным, поэтому никакие новые маркировки из этой пассивной маркировки в дереве порождаться не будут. Кроме того, необходимо отметить, что маркировка 0, 1, 1 , порождаемая запуском t3 в 0, 2, 1 была уже

порождена непосредственно из на- чальной маркировки запуском t2. Если эту процедуру повторять снова и снова, каждая достижимая маркировка окажется порожденной. Однако получившееся дерево достижимости может оказаться бесконечным, так как будет порождена каждая маркировка из множества достижимо- сти. Поэтому для любой сети Петри с бесконечным множеством достижимости соот- ветствующее дерево также должно быть бесконечным.

Даже сеть Петри с конечным множеством достижимости может иметь бесконечное дерево рис. 7.14 . 1, 0 t1 t2 t1 0, 1 t2 1, 0 t1 0, 1 t2 1, 0 t1 Рис. 7.14. Простая сеть Петри с бесконечным деревом достижимости Дерево представляет все возможные последовательности запусков переходов. Всякий путь в дереве, начинающийся в корне, соответствует допустимой последова- тельности переходов.

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

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

Такие маркировки называются дублирующими вершинами никакие после- дующие маркировки можно не рассматривать все они будут порождены из места первого появления дублирующей маркировки в дереве. Таким образом, в дереве на рис. 7.13 маркировка 0, 1, 1 , получившаяся в результате выполнения последова- тельности t1, t2, t3, не будет порождать какие-либо новые вершины в дереве, посколь- ку она ранее встречалась в дереве в результате выполнения последовательности t2 из начальной маркировки.

Каждая вершина может классифицироваться как граничная вершина, терми- нальная вершина, дублирующая вершина или как внутренняя вершина. Граничными являются вершины, еще не обработанные алгоритмом, а после обработки они могут стать терминальными, дублирующими или внутренними вершинами. Алгоритм обычно начинается с определения начальной маркировки корнем де- рева, т. е. граничной вершиной. Пусть х граничная вершина, которую необходимо обработать, тогда 1 если в дереве имеется другая вершина

у, не являющаяся граничной, и с ней связана та же маркировка, х у , то вершина х дублирующая 2 если для маркировки х ни один из переходов не разрешен, то х терми- нальная вершина 3 дуга, помеченная tj, направлена от вершины х к вершине у. Вершина х пере- определяется как внутренняя, вершина у становится граничной. Если все вершины дерева терминальные, дублирующие или внутренние, то обработка данным алгоритмом останавливается. Определение. Задача покрываемости.

Для заданной сети Петри С с начальной маркировкой и маркировки определить, существует ли такая достижимая марки- ровка ?R C что Маркировка покрывает . Это требование можно усложнить, если определять достижимость и покрывае- мость для множества маркировок, тогда можно перейти к задачам достижимости множества и покрываемости множества. Однако, если множество конечно, то та- кие задачи можно решить обычным многократным решением соответствующих задач достижимости и покрываемости для одной маркировки.

7.4. Моделирование алгоритмов с помощью сетей Петри Моделирование алгоритмов с помощью сетей Петри имеет ряд особенностей. Одной из особенностей является свойственные сетям и их моделям параллелизм или одновременность. В модели сети Петри два разрешенных невзаимодействующих со- бытия могут происходить независимо друг от друга. Синхронизировать события, пока это не требуется моделируемой системе, нет необходимости.

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

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

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

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

Основное положение теории относительности утверждает, что передача чего- либо не может быть мгновенной. Любая информация о возникновении события рас- пространяется в пространстве со скоростью, ограниченной скоростью света с. Это оз- начает, что если два события и произойдут одновременно, то порядок возникновения этих событий для двух разных наблюдателей может оказаться различным. Для простоты обычно вводят следующее ограничение.

Запуск перехода и со- ответственно события рассматривается как мгновенное событие, занимающее нуле- вое время, и возникновение двух событий одновременно невозможно. Моделируемое таким образом событие называется примитивным примитивные события мгновен- ны и неодновременны. Непримитивными называются такие события, длительность которых отлична от нуля. Они не являются неодновременными и, следовательно, могут пересекаться во времени.

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

Начало Конец непримитивного непримитивного события события Рис. 7.15. Моделирование непримитивного события При моделировании сложных вычислительных систем на нескольких иерархи- ческих уровнях сети Петри представляются в отдельные элементы сети целыми под- сетями. Отдельными элементами в этом случае являются прямоугольники, представ- ляющие непримитивные события, а планки представляют примитивные события. Та- кое моделирование вычислительной системы представлено

на рис. 7.16. Задание помещается во входную очередь Процессор свободен Задание ждет Задание обрабатывается Задание ожидает вывода Вывод Задания Рис. 7.16. Моделирование вычислительной системы с использованием непримитивного перехода Недетерминированность и неодновременность запусков переходов при моде- лировании параллельной системы показываются двумя способами.

Один из них пред- ставлен на рис. 7.17. В этой ситуации имеется два разрешенных перехода, которые в любом случае не влияют друг на друга. В число возможных последовательностей со- бытий входит последовательность, в которой первым срабатывает один переход или последовательность, в которой первым будет запущен другой переход. Такая ситуа- ция называется одновременностью. t j t к Рис. 7.17. Одновременность. Эти два перехода могут быть запущены в любом порядке

Другая ситуация, в которой одновременное выполнение затруднено и которая характеризуется невозможностью одновременного возникновения событий, показана на рис. 7.18. Здесь два разрешенных перехода находятся в конфликте. Может быть запущен только один переход, так как при запуске он удаляет фишку из общего входа и запрещает другой переход. t j Р i t к Рис. 7.18. Конфликт. Переходы tj и tk находятся в конфликте, т. е. запуск

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

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

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

Петри. Конвейер представляется набором операций, которые могут выполняться одновременно. Когда операция k завершается, она передает свой результат операции k 1 и ожидает от операции k - 1 нового задания. Если каждая операция занимает t единиц времени и всего существует n операций, то за- вершение обработки одного операнда потребует nt единиц времени. 7.5. Расширенные сети Петри В п. 7.4 отмечалось, что сети

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

целевой направленности, получившие назва- ние расширенные. Классификация расширенных сетей Петри приведена на рис. 7.19. Рассмотрим подробнее некоторые типы сетей Петри. Ингибиторная сеть представляет собой сеть Петри, дополненную специаль- ной функцией инцидентности I IN Р х Т ? 0, 1 , которая вводит ингибиторные за- прещающие дуги для тех пар p, t , для которых

I IN Р, Т 1. Ингибиторные дуги связывают только позиции с переходами, на рисунках их изображают заканчиваю- щимися не стрелками, а маленькими кружочками. Расширенные сети Петри Ориентированные на Ориентированные на описание и описание и качественный анализ количественный анализ С неизменной С изменяемой С применением С применением структурой структурой аналитических имитационных методов методов Ингибиторные Предикатные Временные

Оценивающие Приоритетные Самомодифицируемые Стохастические Числовые Структурированные Функцио нальные Цветные Рис. 7.19. Расширенная сеть Петри Переход t в ингибиторных сетях может сработать, если каждая его входная позиция, соединенная с переходом обычной дугой с кратностью w p, t содержит не ме- нее w p, t фишек, а каждая входная позиция, соединенная с переходом t ингибитор- ной дугой ее кратность всегда равна 1

, имеет нулевую разметку. Например, используя ингибиторную дугу, можно промоделировать оператор условного вычитания если xi ? 0, то xi xi - 1 и получить фрагмент ингибиторной сети рис. 7.20 . P x l i l хi - 1 t ? t l l P P l l Рис. 7.20. Фрагмент ингибиторной дуги Ингибиторные сети используются для разработки диагностических моделей средств вычислительной техники. В приоритетных сетях вводят приоритеты срабатывания переходов.

Если не- сколько переходов являются разрешенными, то срабатывает тот из них, который име- ет наивысший приоритет. Такие сети используются для моделирования систем на уровне задач. В структурированных сетях некоторые из переходов являются сложными. При их срабатывании запускается сеть другого уровня иерархии рис. 7.21 . Срабатывание t2 приводит к запуску сети другого уровня.

Выполнение слож- ного перехода заключается в помещении во входную позицию по сети фишки. После выполнения сети фишка появляется в ее выходной позиции, затем формируются фишки в выходных позициях сложного перехода. Р3 t1 t3 t Р1 t1 Входная позиция Выходная Р4 t4 позиция t2 Р2 Р1 Р2 t2 Рис. 7.21. Структурированная сеть Петри Преобразование сети к виду, имеющему один вход и один выход, всегда воз- можно.

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

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

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

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

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

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

Это дает возможность установления связи теории сетей Петри с теорией формальных языков, чтобы определить класс языков сетей Петри как класс языков, порождаемых сетями Петри. Рассмотрим в качестве примера конечные автоматы и регулярные выражения. Конечный автомат S есть пятерка Q, А, q0, F , где Q конечное множество состояний А алфавит символов

А множество всех строк из символов А, включая пустую строку А А Q x A ? Q функция переходов q0 ?Q начальное состояние F ?Q конечное множество заключительных состояний. Функция переходов ? естественным образом обобщается на случай отображе- ния из Q x A в Q. Язык L S , порождаемый конечным автоматом, это множество строк над А , определяемое следующим образом L S a q0, a ?

F . A Всякому конечному автомату соответствует язык, а класс всех языков, порож- даемых конечными автоматами, называется классом регулярных языков. Каждый ав- томат определяется своим языком. Если два конечных автомата имеют одинаковые языки, то они эквивалентны. Основные понятия, используемые для получения регулярного языка по конеч- ному автомату, применимы и к сетям Петри для образования теории языков сетей Петри.

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

переходов порождает строку символов языка. Связь символов с переходами осу- ществляется функцией помечения ? Т ? А . Определение заключительных состояний сети Петри оказывает наибольшее влияние на язык сети Петри. Одно из определений взято по аналогии с соответствующим понятием для ав- томатов множество заключительных состояний F определяется как конечное мно- жество заключительных маркировок.

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

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

На низком уровне вычислительные системы могут быть описаны конечными автоматами. Автомат это пятерка Q, X, Y, где Q конечное множество состояний Х конечный входной алфавит Y конечный выходной алфавит ? Q x X ? Q функция следующего состояния ? Q x X ? Y функция выхода. Автоматы часто представляют в виде графов переходов рис.

7.22 . В графе пе- реходов состояния представляются кружками, являющимися вершинами. Дуга из со- стояния qi в qj, помеченная a b означает, что находясь в состоянии qi , автомат при входе а перейдет в состояние qj, выдавая при этом символ b. Формально можно запи- сать ? qi, a qj и ? qi, a b. 0 0 0 1 1 1 q1 q2 R R R R 1 0 Рис. 7.22. Граф переходов для конечного автомата, вычисляющего дополнение

до двух двоичного числа Этот автомат преобразует двоичное число, представленное последовательно- стью бит, начиная с младшего, в дополнение до двух. В данном случае входной и вы- ходной алфавиты состоят из трех символов 0, 1, R. Автомат начинает работать в со- стоянии q1. Символ сброса R означает конец или начало числа и возвращает авто- мат в исходное состояние. Выход автомата для символа сброса является просто его повторением.

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

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

7.24 . Задав представление позиций, соответствующих символам входа и выхода, можно завершить построение модели системы конечных состояний. Текущее состоя- ние отмечается фишкой, все остальные позиции пусты. Входы Выходы Входы Выходы Представление Представление сетью сетью Петри Петри конечного конечного втомата автомата Рис. 7.23. Общий подход Рис. 7.24. Альтернативный подход к моделированию

Теперь для определения переходов из состояния в состояние можно ввести пе- реходы сети следующим образом. Для каждой пары состояние и выходной символ определяем переход, входными позициями которого являются позиции, соответст- вующие состоянию и входному символу, а выходными позициями позиции, соот- ветствующие следующему состоянию и выходу рис. 7.25 . 0 0 q 1 1 R q R Рис. 7.25. Сеть Петри, эквивалентная автомату на рис.

7.22 Таким образом, для конечного автомата Q, X, Y, ? определена сеть Петри P, T, I, O следующим образом Р Q ? X ? Y, T tq, x q ?Q и x ?X , I tq, x q, x , O tq, x ? q,x q, x . Полученная сеть Петри является моделью конечного автомата. 7.8. Разработка модели сложения двух чисел с плавающей запятой Модель сложения двух чисел с плавающей запятой разрабатывается в следую- щей последовательности 1 выделить

экспоненты обоих чисел 2 сравнить экспоненты и изменить, если необходимо, должным образом поря- док большей и меньшей экспонент 3 сдвинуть точку в числе с меньшей экспонентой для их уравнения 4 сложить дроби 5 нормализовать результат 6 проверить экспоненту на переполнение и сформировать экспоненту и дробь результата. Каждый из этих шагов может быть выполнен отдельным вычислительным бло- ком, где каждый отдельный операнд передается от блока к блоку для выполнения операции сложения.

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

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

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

регистра для вычисления значения выходного буферного ре- гистра. Очевидно, что пока входной регистр блока не будет очищен путем пересылки содержимого во входной регистр следующего блока, новое входное значение не мо- жет появится в его входном регистре. Таким образом, для управления блоком k кон- вейера необходимо знать, когда выполняются следующие условия - входной регистр заполнен - входной регистр пуст - выходной регистр заполнен - выходной регистр пуст

- блок занят - блок свободен - пересылка осуществлена. На рис. 7.26 и 7.27 показано, как можно промоделировать асинхронный кон- вейер такого типа. На рис. 7.26 приведена блок-схема конвейера, моделируемого се- тью Петри рис. 7.27 . Выходной Входной Выходной Входной регистр регистр регистр регистр Блок Блок блока k-1 блока k блока k блока k 1 k-1 k

Рис. 7.26. Блок-схема устройства управления асинхронной ЭВМ с конвейерной обработкой Выходной регистр Выходной регистр k-1 пуст Блок k-1 занят k-1 заполнен Входной регистр Входной регистр k заполнен k пуст Пересылка из k-1 в k Выходной регистр Выходной регистр k пуст k заполнен Блок k занят Входной регистр Входной регистр k 1 заполнен k 1 пуст

Пересылка из k в k 1 Рис. 7.27. Модель сети Петри устройства управления асинхронной ЭВМ с конвейерной обработкой Отметим, что эта модель моделирует реальную работу блоков конвейера как непримитивных событий. Это позволяет нам проигнорировать на данном уровне кон- кретные детали того, что происходит в блоках, и сосредоточиться на их правильном взаимодействии. Каждая операция также может промоделироваться сетью

Петри. Затем сети Петри для каждого блока можно объединить в обобщенную сеть Петри рис. 7.27 моделируемой системы. Такая возможность моделирования системы на нескольких различных уровнях абстракции, т. е. иерархическим образом, может быть весьма полезна. ЗАКЛЮЧЕНИЕ Понятие структурной теории автоматов, методы структурного синтеза автома- тов и методы анализа сетей Петри, оказываются мощным инструментом моделирова- ния динамических систем.

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

Петри. В этом направлении есть много нерешенных проблем, в том числе и вопросы применения способов программирования алгебраических сетей. В целом сети Петри представляют собой перспективную область исследований, в которой со- единяются, обогащая друг друга, усилия специалистов самых разных направлений. 12. Котов В. Е. Сети Петри. М. Наука, 1984. 158 с. Леснин А. А. и др. Сети Петри в моделировании и управлении.

Л. Наука, 1989. 133 с. Питерсон Д. Теория сетей Петри и моделирование систем. М. Мир, 1984. 264 с.