Устройство для исследования сетей Петри Советский патент 1992 года по МПК G06F15/173 

Изобретение относится к вычислительной технике и может быть использовано для решения линейных матричных уравнений, для исследования сетей Петри на безопасность, живость и достижимость.

Сеть Петри --двудольный граф с кратными дугами, характеризуемый четверкой

C (P.T.D-.D,

где Р {pi.p2.....pm). m 0 - конечное непустое множество позиций;

Т {ti.t2,...,tk), k О - конечное непустое множество переходов;

РПТ 0;

D и D - матрицы, представляющие собой входную и выходную функции.

Каждая матрица имеет k строк (по одной на переход) и m столбцов (по одному на позицию).

,| # (pi.1(tj));

.l # (pi,0(tj)). где D - определяет входы в переходы;

D - определяет выходы из переходов.

Маркировкой /сети С называется функция, отображающая множество позиций Р в множество неотрицательных целых чисел:

(«(р1),/(Р2), .. ./(Рт)}.

Маркировка /f достижима в сети С от маркировки fi, если существует последовательность следующих друг за другом маркировок flROfi.

Обозначим через R(c) множество всех маркировок сети С, достижимых от начальной маркировки fio (включая ). Переход tj сети С называют живым, если от любой маркировки из множества R(c) достижима хотя бы однамаркировка /f, при которой переход tj срабатывает.

Сеть называют живой, если каждый ее переход - живой. Сеть Петри называют безопасной, если R(c) содержит только такие маркировки ft, при которых/г (pi) 1 для всех Pi 6 Р.

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

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

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

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

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

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

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

0 Нафиг.1 представлена функциональная схема устройства; ,2 - схема блока анализа.

Устройство для исследования сетей Петри содержит три блока 1-3 памяти, блок

5 4 регистров, группу-5 блоков 5i-5k схем сравнения, где k-количество строк в исходных матрицах, регистр 6 результатов сравнения, блок 7 вычитания матриц, блок 8 умножения матриц, блок 9 сумматоров,

0 блок 10 сравнения с нулем, блок 11 синхронизации, блок 15 анализа, блок 16 регистров задаваемой маркировки и блок 17 сравнения, причем выход блока 4 регистров одновременно подключен к выходу

5 первого слагаемого блока 9 сумматоров,. первому информационному входу каждого блока 5i-5k схем сравнения группы и второму входу блока 17 сравнения, к первому входу которого подключен выход блока 16

0 регистров задаваемой маркировки, с первого по k-й выходы первого блока 1 памяти подключены к входу вычитаемого блока 7 вычитания матриц и вторым входам с первого по k-й блоков 5i-5k схем сравнения

5 группы 5, выходы признаков неотрицательного результата которых подключены к информационному входу регистра 6 результатов сравнения, выход которого одновременно подключен к входу первого

0 сомножителя блока 8 умножения матриц, первому информационному входу блока 15 анализа и информационному входу блока 10 сравнения с нулем, выход признака равенства нулю которого одновременно под5 ключен к входу останова блока 11 синхронизации, выходу блока 17 сравнения и является первым информационным выходом 12 устройства, выход второго блока 2 памяти подключен к входу уменьшаемого

0 блока 7 вычитания матриц, вь1ход которого

подключен к информационному входу

третьего блока 3 памяти, выход которого

подключен к входу второго -сомножителя

, блока 8 умножения матриц, выход которого

5 подключен к входу второго слагаемого блока 9 сумматоров, выход которого одновременно подключен к информационному входу блока 4 регистров и второму информа. ционному входу блока 15 анализа, вход начальной установки блока 11 синхронизации

одновременно подключен к входам начальной установки регистра 6 результатов сравнения, третьего блока 3 памяти и,блока 15 . анализа и является входом 13 начальной установки устройства, вход пуска блока син- 5 хронизации является входом 14 пуска устройства, с первого по седьмой выходы блока 11 синхронизации подключены к входам признака чтения первого и второго блоков 2 и 1 памяти, входу признака записи 10 третьего блока 3 памяти, входу опроса блока 9 сумматоров, входам признака записи блока 4 регистров и блока 15 анализа, вхО дам опроса каждого блока схем сравнения группы и блока 7 вычитания матриц, .15 входу признака записи регистра 6 результатов сравнения, входу опроса блока 8 умножения матриц и входу признака чтения третьего блока 3 памяти соответственно, первый и второй выход блока 15 Знализа являются соот- 20 ветственно вторым информационным выходом 18 и третьим информационным выходом 19 устройства.

Схемы блока 16 регистров и блока 17 Сравнения известны.25

Блок 15 анализа содержит элементы И 20i-20k, 22, 25i-25m. Т-триггеры 21i-21k. 26i-26m, элементы ИЛИ 24i-24m, 27 и дешифраторы 23i-23m. Схемы злементов И, ИЛИ, Т-триггеров, дешифраторов извест- 30 ны..

Устройство работает следующим образом.

В исходном состоянии схемы в блоке 1 находится матрица входов D, например 36

1110

D 0001 ,0010 а в блоке 2 - матрица выходов D, например т.е. данная сеть Петри имеет четыре позиции и три перехода. Первоначальная маркировка находится в блоке 4 регистров и имеет вид: /4 (1,0,1,0). Маркировка /, которой мы хотим достигнуть из начальной маркировки ft, находится в блоке 16 регистров задаваемой маркировки и имеет вид: / (1,2,1,0), где / - некоторая маркировка из множества всех возможных маркировок данной сети Петри,

Требуется определить, достижима ли маркировка fT из 41аркировки ft и является ли исследуемая сеть Петри безопасной и живой..

Предполагают что маркировка ft достижима из маркировки /л. Тогда существует последовательность (возможно пустая) запусков переходов сг, которая приводит из ft к /,Э to означает, чт f ({ является , неотрицательн14 « целым решением следую- щего мatpичнoro уравнения для X

(1)

,

где D составная матрица изменений;

7 некоторая маркировка из множества всех достижимых маркировок данной сети Петри, и выполняется условие

.

(2)

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

Если/{ достижима из /, то уравнение (1) имеет решение в неотрицательных целых и выполняется условие. (2). Если уравнение (1) не имеет решения и условие (2) не выполняется, то уИ не достижима из/г.

Сеть Петри является безопасной, если для каждой позиции сети р1 выполняется условие

(pi)1.

(3) Сеть Петри является живой, если все ее переходы окажутся живыми, т.е. сработают при достижении конечной маркировки. ч Переход tj может сработать при некоторой маркировке /{сети С, если каждое вход ноё место PI перехода tj имеет маркировку не меньшую, чем кратность F дуги, соединяющей PI и tj, т.е.(tj).(4) где кратность F дуги, соединяющей pi и tj определена элементами матрицы входов D. Под действием синхросигналов блока 11 информация с Ъыхода блока 1 памяти поступает на вторые входы блоков схем сравнения группы и сравнивается со значением начальной маркировки fi, поступающей на первые входы всех блоков 5i-5k. Если результат сравнения больше или равен нулю по всем сравниваемым элементам

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

Таким образом, при сравнении первоначальной маркировки (1,0,1,0) со строками матрицы D только третья строка удовлетворяет правилу сравнения. Это означает, что срабатывание третьего перехода разрешено. В регистре 6 записано (0,0,1). Параллельно информация из блока 2 поступает на вход уменьшаемого блока 7, на вход вычитаемого которого поступает информация блока 1. Блок 7 под действием управляющих сигналов с блока 11 реализует операцию вычитания матриц по формуле:

D .

Значение полученной составной матрицы изменений D записывается в блок 3 памяти вида

0-1-10 04-2+1-1

D О 0-1+1

Дальше работа схемы направлена на реализацию формулы (1) и проверку условий (2),(3)и(4).

Подставив полученные значения, преобразуют формулу (1) к виду

0-1 -1 О

X(1.0,1.0)-f(0,0,l) 0+2-ЬЫ О 0-1+1

Под действием управляющих сигналов с блока 11 информация из блока 3 поступает в блок 8, в котором происходит перемножение матриц. Результат умножения (0,0,-1,+1) поступает в блок 9, в котором происходит сложение результата произведения со значением маркировки из блок)а 4, в результате получается новая маркировка сети Петри /n-i (1,0,0,1) , которая вновь заносится в блок 4. Процесс работы устройства повторяется. На втором шаге работы .устройства следующей будет маркировка /2 (1,2,1,0)., ,

На каждом шаге .работы происходит проверка кода, находящегося в блоке 6, т.е. последовательности запусков переходов, на нуль в блоке 10. Если информация больше нуля, работа продолжается. Одновременно в бяоке 17 код сравнивается на выходе блока 4 со значением кода заданной маркировки fi, поступающего из блока 16. Если значейия кодов текущей и заданной ма|экировок совпадают, блок 17 вырабатывает сигнал, свидетельствующий о том, что сеть Петри приданной начальной маркировки/г достигла заданного значения маркировки

fi. Сигнал поступает на вход останова блока 11 синхронизации и работа устройства прекращается. Для приведенного примера такое событие произойдет на втором

шаге («2 /) Если результат сравнения кодов в блоке 17 отрицательный, а последовательность запусков переходов с выхода блока б равна нулю, блок 10 вырабатывает сигнал, прекращающий дальнейшую работу

устройства и свидетельствующий о том, что приданной начальной маркировке fi заданное значение маркировки /г для данной сети Петри является недостижимым, а сама сеть достигла предела выполнимости, т.е.

достигла такого состояния, когда все переходы запрещены.

Одновременно на каждом шаге устройства последовательность запусков переходов с выхода блока 6 поступает на первый

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

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

соответственно свойств живости и безопасности.

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

Блок 15 анализа работает следующим,

образом.

По сигналу начальной установки, поступающему на R-входы начальной установки Т-триггеров, прямые выходы Т-триггеров 21i-2lk, 26i-26m устанавливаются в нулевое, а инверсные выходы - в единичное состояние.

Блок анализа включает в себя две функциональные независимые схемы: схему анализа живости сети и схему анализа

безопасности исследуемой сети Петри.

Схема анализа живости сети включает в себя злементы И 20i-20k, 22 и Т-триггеры 21 i-21k, где k- количество переходов в сети Петри. Поаледовательность запусков переходов сг в виде k-разрядного кода с выхода регистра 6 поступает на первые входы злементов И 20i-20k, на вторые,входы которых поступает уровень 1 с соответствующих инверсных выходов Т-триггеров 21i-21k.

Состояния выходов Т-триггера меняются на противоположные при поступлении на Т-вход сигнала 1 и сохраняются неизменными при Т 0. Пусть разрешено срабатывание первого перехода сети Петри, т.е. на первый вход элемента И 20i поступает сигнал 1. На входе триггера 211 появляется сигнал Т 1, триггер изменяет свое состояние на противоположное, на первый вход элемента И 22 с прямого выхода триггера поступает сигнал 1. С инверсного выхода триггера 21i на второй вход элемента И 20i поступает сигнал О и в дальнейшем (до поступления сигнала начальной yctaнoвки) состояние триггера осгается неизменным. Работа остальных элементов схемы для каждого разряда входного кода осуществляется аналогично. В случае срабатывания всех переходов сети Петри по окончании работы устройства на выходе элемента И 22, являющемся первым информационным выходом блока 15 анализа, появляется сигнал 1, что свидетельствует .о том, что исследуемая сеть Петри-живая.

Схема анализа безопасности сети включает в себя дешифраторы 23i-23m, элементы ИЛИ 24i-24m, 27, элементы И 25i-25m И Т-триггеры 26i-26m, где m - количество позиций в исследуемой сети Петри. Значения . кодов маркировок каждой позиции fi (pi) с .выхода блока 9 сумматоров поступают на соответствующие входы DO-DN дешифраторов 23i-23m, где N - максимальная разрядность двоичного кода, соответствующего максимально допустимым значениям маркировок позиций сети Петри. Работа схемы разрешается только при установившихся значениях сигналов на выходе блока 9 сумматоров, что достигается одновременной подачей сигнала записи на вход признака записи блока 4 и на входы записи V дешифраторов 23i-23m в блоке 15 анализа. Наличие сигнала 1 на одном из выходов AI-AL дешифратора, где L 2, показывает количество маркеров в соответствующей данному дешифратору позиции сети.

Согласно требованию (3) безопасности cetи Петри каждая позиция не должна иметь более одного маркера. Поэтому выходы AI дешифраторов в схеме для анализа не используются. Выходы A2-AL дешифраторов 23i-23m соединены с входами соответствующих элементов ИЛИ 24i-24m. При

наличии сигнала Г на любом из вь1ходов 1-го дешифратора, свидетельствующем о нарушении требования безопасности сети, сигнал с выхода соответствующего элемента ИЛИ 24i поступает на первый вход соответствующего элемента И 25i. Далее работа элементов И 25i-25m и Ттриггеров2б1-26т происходит аналогично работе элементов И 20i-20k и Т-триггеров 211-21 k в схеме анализа живости сети . В случае нарушения требования (3) хотя бы на одном из прямых выходов триггеров 26i-26m появляется сигнал 1, который через элемент ИЛИ 27 поступает на второй информационный выход 19 блока анализа 15, что свидетельствует о том, что исследуемая сеть Петри не является безопасной.

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

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

И

ur

см

to

Изобретение относится к вычислительной технике и может быть использовано длярешену1Я линейных матричных уравнений, исследования сетей Петри на безопасность, живость и достижимость. Целью изобретения является расширение функциональных возможностей устройства за счет анализа сетей Петри на безопасность и живость. Перед началом работы задается некоторая начальная и некоторая желаемая маркировка сети Петри. В процессе моделирования определяется, достижима ли желаемая маркировка из начальной, т.е. проверяется, является ли исследуемая сеть Петри безопасной и живой. 2 ил.

се

1Г

и

,

4-7

г

/V

-3 .

Блок анализа

Фиг.2, .