Устройство для исследования сетей петри

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (st)s G 06 F 15/419

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) 1322312 (21) 4836704/24 (22) 10.04.90 (46) 30.01.92. Бюл. М 4 (72) В.П. Обрученков, А.А. Бянкин, В.В. Дорошенко и В.M. Ларин (53) 681.333(088.8) (56) Авторское свидетельство СССР

М 1322312, кл, G 06 F 15/347, 1986. (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ

СЕТЕЙ ПЕТРИ (57) Изобретение относится к вычислительной технике и может быть использовано для

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

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

С (РТ0,0), где Р = (р1,рг,...,pm}, m >Π— конечное непустое множество позиций;

Т = (ц,тг,.„дк}, k > 0 — конечное непустое множество переходов;

ОТ=И:

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

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

0Ц, ) = М (р,1(т ));

0 (),!) = Ф {pi,0(t )), где 0 — определяет входы в переходы;

0 — определяет выходы из переходов.

/а

Маркировкой /c сети С называется функция, отображающая множество позиций Р . в множество неотрицательных целых чисел:,,5U 1709350 А2 решения линейных матричных уравнений, исследования сетей Петри на безопасность, живость и достижимость. Целью изобретения является расширение функциональных возможностей устройства за счет анализа сетей Петри на безопасность и живость, Перед началом работы задается некоторая начальная и некоторая желаемая маркировка. сети Петри. В процессе моделирований oriределяется, достижима ли желаемая маркировка из начальной, т.е. проверяется, является ли исследуемая сеть Петри безопасной и живой. 2 ил. ф = ф(p1) р (p2) . ° ./» (pm) }.

Маркировка,и" достижима в сети С от маркировки,и, если существует последова- тельность следующих друг за другом маркировок /4 от fc до у .

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

t сети С называют живым, если от любой маркировки,и из множества R(c) достижима хотя бы одна маркировка р, при которой переход t срабатывает.

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

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

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

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

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

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

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

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

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

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

Устройство для исследования сетей

Петри содержит три блока 1 — 3 памяти, блок

4 регистров, группу .5 блоков 51-5 схем сравнения, где k — количество строк в исходных матрицах, регистр 6 результатов сравнения, блок 7 вычитания матриц, блок 8 умножения матриц, блок 9 сумматоров, блок 10 сравнения с нулем, блок 11 синхронизации, блок 15 анализа, блок 16 регистров задаваемой маркировки и блок 17 сравнения, причем выход блока 4 регистров одновременно подключен к выходу первого слагаемого блока 9 сумматоров, первому информационному входу каждого блока 51 — 5 схем сравнения группы и второму входу блока 17 сравнения, к первому входу которого подключен выход блока 16 регистров задаваемой маркировки, с первого по k-й выходы первого блока 1 памяти подключены к входу вычитаемого блока 7 вычитания матриц и вторым входам с первого по k-й блоков 51-5 схем сравнения группы 5, выходы признаков неотрицательного результата которых подключены к информационному входу регистра б. результатов сравнения, выход которого одновременно подключен к входу первого сомножителя блока 8 умножения матриц, первому информационному входу блока 15 анализа и информационному входу блока

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

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

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

Блок 15 анализа содержит элементы И

201-20к, 22, 251-25m, T-триггеры 21! — 21!, 261-26>, элементы ИЛИ 241.-24п, 27 и дешифраторы 231 — 23 . Схемы элементов И, ИЛИ, Т-триггеров, дешифраторов извест- 30 ны.

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

B исходном состоянии схемы в блоке 1 находится матрица входов О, например 35 (2) !

И =/C".

0001 ,0010

И (р!) (1, Сеть, Петри является живой, если все ее . переходы окажутся живыми, т.е. сработают при достижении конечной маркировки.

Переход tf может сработать при некоторой маркировке р сети С, если каждое вход45 ное место pi перехода t! èìååò маркировку не меньшую, чем кратность F дуги, соединяющей р! и tj, т.е.

0001

Р = F(tf) (4)

50 где кратность F дуги, соединяющей р! и tf определена элементами матрицы входов 0 .

Под действием синхросигналов блока

11 информация с выхода блока 1 памяти поступает на вторые входы блоков 5>

55 схем сравнения группы и сравнивается со значением начальной маркировки,и, поступающей на первые входы всех блоков 5!-5ь

Если результат сравнения больше или равен нулю по всем сравниваемым злемеНтам а в блоке 2- матрица выходов D, например т.е. данная сеть Петри имеет четыре позиции и три перехода. Первоначальная маркировка находится в блоке 4 регистров и имеет вид: р = (1,0.1.0).

Маркировка,и", которой мы хотим достигнуть из начальной маркировки,и, находится s блоке 16 регистров задаваемой маркировки и имеет вид:,и" = (1,2,1,0), где,и" — некоторая маркировка из множества всех возможных маркировок данной сети

Петри.

Требуется определить, достижима ли маркировка р" из маркировки,и и является ли исследуемая сеть Петри безопасной и живой, Предполагают, что маркировка p" достижима из маркировки pt. Тогда существует последовательность (возможно пустая) запусков переходов 0; которая приводит из,и к,и", Это означает, чт f (о). является., неотрицэтельнйм целым решением следую- . щего матричного уравнейия для Х

ð=!+ Х О, (1) где 0- 0 - 0 —: составная матрица изменений;

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

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

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

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

1709350 строки матрицы О, в соответствующий разряд регистра 6 записывается единица, иначе — нуль.

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

Блок 7 под действием управляющих сигналов с блока 11 реализует операцию вычитания матриц по формуле;

D=D -D.

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

0-1 — 1 О

0+2+1 — 1

О 0-1+1

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

Π— 1 —,10

0+2+1-1

0 0-1+1,й= (1,0,1,0) + (0,0,1) .

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

/ сети Петри,и = (1,0,0,1), которая вновь заносится в блок 4. Процесс работы устройства повторяется. На втором шаге работы .устройства следующей будет маркировка ,и г = (1,2,1,0), На каждом шаге. работы происходит проверка кода, находящегося в блоке 6, т.е. последовательности запусков переходов, на нуль в блоке 10, Если информация больше нуля, работа продолжается. Одновременно в блоке 17 код сравнивается на выходе блока 4 со значением кода заданной маркировки и", поступающего-из блока 16. Если значейия кодов текущей и заданной маркировок совпадают, блок 17 вырабатывает сиг.нал, свидетельствующий о том, что сеть

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

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

10 устройства и свидетельствующий о том, что при данной начальной маркировке,и заданное значение маркировки,и" для данной

I сети Петрй является недостижимым, а сама сеть достигла предела выполнимости, т.е.

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

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

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

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

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

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

По сигналу начальной установки, поступающему на R-входы начальной установки

Т-триггеров, прямые выходы Т-триггеров

211-21», 261-26® устанавливаются в нуле45 вое, а инверсные выходы — в единичное состояние, Блок анализа включает в себя две функциональные независимые схемы: схему анализа живости сети и схему анализа

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

Схема анализа живости сети включает в себя элементы И 20> — 20», 22 и Т-триггеры

21 -21», где k — количество переходов в сети .

Петри. Последовательность запусков пере55 ходов o в виде k-разрядного кода с выхода регистра 6 поступает на первые входы элементов И 201-20», на вторые входы которых поступает уровень "1" с соответствующих инверсных выходов Т-триггеров 21> — 21».

1709350

Формула изобретения

30 Устройство для исследования сетей °

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

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

45 ка.анализа — к выходу регистра результатов сравнения, второй информационный вход блока анализа — к выходу блока сумматоров, вход начальной установки блока анализа — к входу начальной установки ус50 тройства, вход признака записи блока ана-, лиза — к входу признака записи блока регистров, первый и второй информационные выходи блока анализа — вторым и третьим информационными выходами уст55 ройства соответственно.

Состояния выходов Т-триггера меняются на противоположные при поступлении на.

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

15 анализа, появляется сигнал "1", что свидетельствует .о том, что исследуемая сеть

Петри — живая.

Схема анализа безопасности сети включает в себя дешифраторы 231-23, элементы ИЛИ 241-24, 27, элементы И 25 -25m и

T-триггеры 261-26, где m — количество позиций в исследуемой сети Петри. Значения . кодов маркировок каждой позиции,и(р ) с выхода блока 9 сумматоров поступают на соответствующие входы Dp-DN дешифраторов 231-23m, где N — максимальная разрядность двоичного кода, соответствующего: максимально допустимым значениям маркировок позиций сети Петри. Работа схемы разрешается только при устано.вившихся значениях сигналов на выходе блока 9 сумматоров, что достигается одновременной подачей сигнала записи на вход признака записи. блока 4 и на входы записи V дешифраторов 23 -23 в блоке 15 анализа. Наличие сигнала "1" на одном из

N выходов А1 — А1 дешифратора, где 1 = 2 показывает количество маркеров в соответствующей данному дешифратору позиции сети.

Согласно требованию (3) безопасности сети Петри каждая позиция не должна иметь более одного маркера . Поэтому выходы А1дешифраторов в схеме для анализа не используются. Выходы А2-А1 дешифраторов 231 23m соединены с входами соответ° ствующих элементов ИЛИ 24>-24я . При наличии сигнала "1" на любом из выходов А2-А I-ro дешифратора, свидетельствующем о нарушении требования безопасности сети, сигнал с выхода соответствующего

5 элемента ИЛИ 24 поступает на первый вход соответствующего элемента И 25 .

Далее работа элементов И 251-25m и Ттриггеров 261-26> происходит аналогично работе элементов И 20 -20к и Т-триггеров .

10 21 -21 в схеме анализа живости сети. В случае нарушения требования (3) хотя бы на одном из прямых выходов триггеров

261-26 появляется сигнал "1", который через элемент ИЛИ 27 поступает на второй

15 информационный выход 19 блока анализа

15, что свидетельствует о том, что исследуемая сеть Петри не является безопасной.

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

1709350

5;.ок анализа

Составитель M. Попов

Редактор Л. Пчолинская Техред М.Моргентал Корректор M. Кучерявая

Заказ 428 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., 4/5

Производственно-издательский комбинат "Патент", г, Ужгород, ул. Гагарина, 101.