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

СОЮЗ СО 8 ЕТСКИХСОЦИАЛИСТИЧЕСКИРЕСПУБЛИК 19)41 ННЫЙ КОМИТЕТНИЯМ И ОТКРЫТИЯМР ГОСУДАР СТПО ИЗОБРЕПРИ ГКНТ ЕТЕН ВТОРСКОМУ СВ ТЕЛЬС А.А. Бянки.В, Дольство СССР5/347, 986.Я ИССЛЕДОВАНИЯ осится к вычислитель ыть использованодл ие сопо одной дному на оды;реходов. ется фун озиц й Р ых чисел кци вм ржащее тргруппу бл сссОПИСАНИЕ ИЗ(54) УСТРОЙСТВО ДЛСЕТЕЙ ПЕТРИ(57) Изобретение отнной технике и может Изобретение относится к вычиспительнойтехнике и может быть использовано длярешения линейных матричных уравнений,для исследования сетей Петри на безопасность, живость и достижимость.Сеть Петри - .двудольный граф с кратными дугами, характеризуемый четверкойС (РТ 0,О ),где Р =(р 1,р 2равд, е О - конечное непустое множество позиций;Т = (цд 2,.дк), 3 с0 - конечное непустоемножество переходов;РПТ=И 0 и 0 - матрицы, представля й входную и выходную функции Каждая матрица имеет М строк переход) и щ столбцов (по о зицию).(1 ) Ю .(р 1 (т ОВ, = Ю (р 0(Ч е О - определяет входы в перех О - определяет выходы из пе И Маркировкой р сети С называ я, отображающая множество и ножество неотрицательных целрешенИя линейных матричных уравнений, исследования сетей Петри на безопасность, живость и достижимость. Целью изобретения является расширение функциональных возможностей устройства за счет анализа сетей Петри на безопасность и живость, Перед началом работы задается некоторая начальная и некоторая желаемая маркировка. сети Петри, В процессе моделирований определяется, достижима ли желаемая маркировка из начальной, т.е, проверяется, является ли исследуемая сеть Петри безопасной и живой, 2 ил. ф= 1,и (р 1), и (р 2) ,и (рв) ).Маркировка,и" достижима в сети С от маркировки,и, если существует последова- тельность следующих друг за другом маркировок,и от,идо,и".Обозначим через В(с) множество всех Г маркировок сети С, достижимых от начальной маркировки,и (включая и 0). Переход т сети С называют живым, если от любоймаркировки,и из множества В(с) достижима хотя бы однамаркировка и, при которой переход т срабатывает.Сеть называют живой, если каждый ее переход-живой. Сеть Петри назь 1 вают безопасной, если В(с) содержит только такие маркировки и, при которых,и (р) ( 1 для всехре Р.Модели на сетях Петри широко исполь, зуются для решения задач, связанных с анализом, моделированием и представлением причинно-следственных связей в сложных системах параллельно, асинхронно действующих объектов и процессов,Известно устройство, соде иблока памяти; блок регистров, о 1709350ков схем сравнения, регистр результатов сравнения, блок вычитания матриц, блок сумматоров, блок сравнения с нулем и блок синхронизации,Недостатком данного устройства является ограниченность класса решаемых задач, заключающаяся в невозможности анализа устройством таких важных свойств . сетей Петри, как безопасность и живость, Кроме того, данное устройство позволяет исследовать только одну сторону проблемы достижимости, а именно; возможность достижения исследуемой сетью Петри при заданной начальной маркировке предела выполнимости, т.е, такого состояния, когда все переходы запрещены, Таким образом, устройство не позволяет исследовать сеть Петри на возможность достижения любой наперед заданной маркировки из множества всех возможных маркировок данной сети, что также существенно сужаеткласс решаемых задач.Цель изобретения - расширение функциональных возможностей устройства за счет анализа сетей Петри на безопасность и живость.Указанная цель достигается тем, что в известное устройство, содержащее три блока памяти, блок регистров, группу блоков схем сравнения, регистр результатов сравнения, блок вычитания матриц, блок умножения матриц, блок сумматоров, блок сравнения с нулем и блок синхронизации, введены блок регистров задаваемой маркировки, блок сравнения и блок. анализа, причем выход блока регистров задаваемой маркировки подключен к первому входу блока сравнения, второй вход которого , подключен к выходу блока регистров, выход блока сравнения подключен к выходу блока сравнения с нулем, первый информационный вход блока анализа подключен к выходу регистра результатов сравне; ия, второй информационный вход блока анализа подключен к выходу блока сумматоров, вход начальной установки блока анализа подключен к входу начальной установки устройства, вход признака записи блока анализа подключен к входу признака записи блока регистров, первый и второй выходы блока анализа являются соответственно вторым и третьим информационными выходами устройства.Изобретение обеспечивает достижение моделируемым с помощью сети Петри объектом или процеСсом не только конечного своего состояния, но и определенныхпромежуточных состояний. Требование безопасности сети Петри можно интерпретировать как ограничения, накладываемые55 подключен к входу второго слагаемого блока 9 сумматоров, выход которого одновременно подключен к информационному входу блока 4 регистрови второму информационному входу блока 15 анализа, вход на-чальной установки блока 11 синхронизации 10 1525 30 3550 на моделируемые сетью объекты и процессы (сигналы, данные, состояния регистров.накопителей и т.п,). Требование живости сети Петри означает отсутствие в моделируемых системах ситуаций, которые никогда не возникнут, и их следовательно, можно исклочить из рассмотрения, а также отсутствиетупиковых ситуаций, например взаимныхблокировок и т.п.На фиг.1 представлена функциональная схема устройства, на.фиг,2 - схема блока анализа.Устройство для исследования сетей Петри содержит три блока 1 - 3 памяти, блок 4 регистров, группу 5 блоков 51-5 схемсравнения, где к - количество строк в исходных матрицах, регистр 6 результатов сравнения, блок 7 вычитания матриц, блок 8 умножения матриц, блок 9 сумматоров,блок 10 сравнения с нулем, блок 11 синхронизации, блок 15 анализа, блок 16 регистров задаваемой маркировки и блок 17сравнения, причем выход блока 4 регистров одновременно подключен к выходупервого слагаемого блока 9 сумматоров,. первому информационному входу каждого блока 51 - 5 к схем сравнения группы и второму входу блока 17 сравнения, к первому входу которого подключен выход блока 16 регистров задаваемой маркировки, с первого по Е-й выходы первого блока 1 памяти подключены к входу вычитаемого блока 7 вычитания матриц и вторым входам с первого по 1-й блоков 51-5 схем сравнения группы 5, выходы признаков неотрицательного результата которых подключенык информационному входу регистра б. результатов сравнения, выход которого одновременно подключен к входу первого сомножителя блока 8 умножения матриц, первому информационному входу блока 15 анализа и информационному входу блока 10 сравнения с нулем, выход признака равенства нулю которого одновременно подключен к входу останова блока 11 синхронизации, выходу блока 17 сравнения и является первым информационным выходом 12 устройства, выход второго блока 2памяти подключен к входу уменьшаемого блока 7 вычитания матриц, выход которого подключен к информационному входу третьего блока 3 памяти, выход которогоподключен к входу второго сомножителя блока 8 умножения матриц, выход которого1709350 одновременно подключенк входам начальной установки регистра 6 результатов срав, нения, третьего блока 3 памяти и,блока 15 .анализа и является входом 13 начальной , установкиустройствэ, входпуска блокасин ,. хронизации является входом 14 пуска устройства, с первого по седьмой выходы блока 11 синхронизации подключены к входам признака чтения первого и второго блоков 2 и 1 памяти, входу признака записи 10 третьего блока 3 памяти, входу опроса блока 9 сумматоров, входам признака записи блока 4 регистров и блока 15 анализа, входам опроса каждого блока 51-5 и схем сравнения группы и блока .7 вычитания матриц, .15 входу признака записи регистра 6 результатов сравнения, входу опроса блока 8 умножения матриц и входу признака чтения третьего блока 3 памяти соответственно, первый и вто. рой выход блока 15 анализа являются соответственно вторым информационным ,. выходом 18 и третьим информационным вы ходом 19 устройства.Схемы блока 16 регистров и блока 17. сравнения известны. .25Блок 15 анализа содержит элементы И 201-20, 22, 251-25 п, Т-триггеры 211 - 21 ь 261-26 п, элементы ИЛИ 241-24 п, 27 и дешифраторы 231 - 23. Схемы элементов И, ИЛИ, Т-триггеров, дешифраторов извест ны.Устройство работает следующим образом.В исходном состоянии схемы в блоке 1 находится матрица входов О, например 35 1110 0001 ,0010(3) Сеть, Петри является живой, если все ее. переходы окажутся живыми, т,е. сработаютпри достижении конечной маркировки.Переход 11 может сработать при некоторой маркировке р сети С, если каждое вход ное место р Перехода тИмеет маркировкуне меньшую, чем кратность Р дуги, соединяющей р и т 1, т.е. 1000 0210 0001 р: Е(с); (4) 50 где кратность Е дуги, соединяющей р 1 и Чопределена элементами матрицы входов О .Под действием синхросигналов блока11 информация с выхода блока 1 памяти поступает на вторые входы блоков 51:-5 а 55 схем сравнения группы и сравнивается созначением начальной маркировки,и, поступающей на первые входы всех блоков 51-5 ь Если результат сравнения больше или равен нулю по всем сравниваемым злемеНтам а в блоке 2- матрица выходов О, например т.е. данная сеть Петри имеет четыре позиции и три перехода, Первоначальная маркировка находится в блоке 4 регистров и имеет вид:р(1,0 1,0),Маркировка,и", которой мы хотим достигнуть из начальной маркировки р, находится в блоке 16 регистров задаваемой маркировки и имеет вид: р" = (1,2,1,0),где,и" - некоторая маркировка из множества всех возможных маркировок данной сети Петри. Требуется определить, достижима лимаркировка р" из маркировки,и и является ли исследуемая сеть Петри безопасной й живой,Предполагают, что маркировка р" достижима из маркировки р. Тогда существует последовательность (возможно пустая) запусков переходов д которая приводит из,и к р", Это означает, чт т (о) . являе 1 ся,. " неотрицэтельнйм целым решением следую" .щего матричного уравнейия для Х р=р+ Х О, (1) где О - О - О - : составная матрица изменений;,р - некоторая маркировка из множества всех достижимых маркировок данной сети Петри,и выполняется условие Множество всех достижимых маркировок данной сети Петри в общем случае является подмножеством множества всех возможных для этой сети маркировок, т.е.8 АЕсли р" достижима иэ р, то уравнение (1) имеет решение в неотрицательных целых и выполняется условие (2). Если уравнение (1) не имеет решения и условие (2) не выполняется, то.,и" не достижима изр.Сеть Петри является безопасной, если для каждой позиции сети р 1 выполняется условиестроки матрицы О, в соответствующий разряд регистра 6 записывается единица, иначе - нуль.Таким образом, при сравнении первоначальной маркировки (1,0,1,0) со строками матрицы О только третья строка удовлетворяет правилу сравнения. Это означает, что срабатывание третьего перехода разрешено. В регистре 6 записано(0,0,1). Параллельно информация из блока 2 поступает на вход уменьшаемого блока 7, на вход вычитаемого которого поступает информация блока 1. Блок 7 под действием управляющих сигналов с блока 11 реализует операцию вычитания матриц по формуле;О=О -О.Значение полученной составной матрицы изменений О записывается в блок 3 памяти вида 0-1 - 1 О 0+2+1 - 1 0 0-1+1 О= Дальше работа схемы направлена на реализацию формулы(1) и проверкуусловий (2),(З) и (4),Подставив полученные значения, преобразуют формулу (1) к виду 0 - 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 = (1,0,0,1), которая вновь заносится в блок 4, Процесс работы устройства повторяется. На втором шаге работы .устройства следующей будет маркировка ,и 2 = (1,2,1,0),На каждом шаге. работы происходит проверка кода, находящегося в блоке 6, т,е. последовательности запусков переходов, на нуль в блоке 10, Если информация больше нуля, работа продолжается. Одновременно в блоке 17 код сравнивается на выходе блока 4 со значением кода заданной маркировки и", поступающего из блока 16. Если значейия кодов текущей и заданной маркировок совпадают, блок 17 вырабатывает сиг.- нал, свидетельствующий о том, что сеть Петри приданной начальной маркировки и достигла заданного значения маркировки,и", Сигнал поступает на вход останова блока 11 синхронизации и работа устройствапрекращается. Для приведенного примера такое событие произойдет на втором5 шаге (й 2 =,и"). Если результат сравнениякодов в блоке 17 отрицательный, а последовательность запусков переходов с выходаблока 6 равна нулю, блок 10 вырабатываетсигнал, прекращающий дальнейшую работу10 устройства и свидетельствующий о том, чтопри данной начальной маркировке,и заданное значение маркировки ,и" для даннойсети Петрй является недостижимым, а самасеть достигла предела выполнимости, т.е.15 достигла такого состояния, когда все переходы запрещены.Одновременно на каждом шаге устройства последовательность запусков переходов с выхода блока 6 поступает на первый20 информационный вход блока 15 анализа, навторой информационный вход которого с. выхода блока 9 поступают значения текущих маркировок сети, В блоке 15 фиксируются срабатывания каждого перехода и25 проверяется текущая маркировка каждой.позиции сети Петри. Сигналы на информационных выходах 18 и 19 по окончании работы устройства свидетельствуют о наличии(либо отсутствии) у исследуемой сети Петри30 соответственно свойств живости и безопасности,Анализ свойств сети Петри показывает,что данная сеть является живой (все переходы оказываются живыми уже на третьем ша 35 ге работы устройства), но не являетсябезопасной (начиная со второго шага работы устройСтва число маркеров во второй позиции стало равно двум).Блок 15 анализа работает следующим,40 образом.По сигналу начальной установки, поступающему на Й-входы начальной установкиТ-триггеров, прямые выходы Т-триггеров211-21 ь 261-26 п устанавливаются в нуле 45 вое, а инверсные выходы - в единичное состояние,Блок анализа включает в себя две функциональные независимые схемы: схему анализа живости сети и схему анализа50 безопасности исследуемой сети Петри.Схема анализа живости сети включает всебя элементы И 201 - 20 ь 22 и Т-триггеры211-21 ь где к - количество переходов в сети .Петри. Последовательность запусков пере 55 ходов о в виде к-разрядного кода с выходарегистра 6 поступает на первые входы элементов И 201-20 ь, на вторые входы которыхпоступает уровень "1" с соответствующихинверсных выходов Т-триггеров 211 - 21.наличии сигнала "1" на любом из выходов .А 2-А 1-го дешифратора, свидетельствуюСостояния выходов Т-триггера меняютсяна противоположные при поступлении на,Т-вход сигнала "1" и сохраняются неиз- .менными при Т = О. Пусть разрешено срабатывание первого перехода сети Петри, т.е.на первый вход элемента И 201 поступаетсигнал "1". На входе триггера 211 появляется сигнал Т = 1, триггер изменяет своесостояние на противоположное, на первый вход элемента И 22 с прямого выходатриггера поступает сигнал "1". С инверсного выхода триггера 211 на второй входэлемента И 201 поступает сигнал "0" и вдальнейшем (до поступления сигнала начальной установки) состояние триггера остается неизменным, Работа остальныхэлементов схемы для каждого разрядавходного кода осуществляется аналогично. В случае срабатывания всех переходов. сети Петри по окончании работы устройства на выходе элемента И 22, являющемсяпервым информационным выходом блока15 анализа, появляется сигнал "1", что свидетельствует,о том, что исследуемая сетьПетри - живая.Схема анализа безопасности сети включает в себя дешифраторы 231-.23, элементы ИЛИ 241-24 а, 27, элементы И 251-25 в иТ-триггеры 261-26, где в - количество позиций в исследуемой сети Петри. Значения. кодов маркировок каждой позиции р(р) свыхода блока 9 сумматоров поступают насоответствующие входы Оо-Он дешифраторов 231-23, где й - максимальная разрядность двоичного кода, соответствующего:максимально допустимым значенияммаркировок позиций сети Петри. Работасхемы разрешается только при устано.вившихся значениях сигналов на выходеблока 9 сумматоров, что достигается одновременной подачей сигнала записи навход признака записи. блока 4 и на входызаписи Ч дешифраторов 231-23 п в блоке 15анализа, Наличие сигнала "1" на одном извыходов А 1 - А дешифратора, где 1. = 2показывает количество маркеров в соответствующей данному дешифратору позициисети,Согласно требованию (3) безопасностисети Петри каждая позиция не должнаиметь более одного маркера. Поэтому выходы А 1 дешифраторов в схеме для анализа неиспользуются. Выходы А 2-А 1. дешифраторов 231-23 в соединены с входами соответствующих элементов ИЛИ 241-24 в. При щем о нарушении требования безопасности формулаизобретения 30 Устройство для исследования сетейПетри по.авт.св, %1322312, отл и ч ающ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет анализа сетей Петри на безопас ность и живость, в него введены блок регистров задаваемой маркировки, блок сравнения и блок анализа, причем выход блока регистров задаваемой маркировки подключен к первому ийформационному.40 входу блока сравнения, второй информационный вход которого подключен к выхо-, ду блока регистров, выход блока сравнения - к выходу блока сравнения с нулем, первый информационный вход бло ка анализа - к выходу регистра результатов сравнения, второй информационный вход блока анализа - к выходу блока сумматоров, вход начальной установки блока анализа - к входу начальной установки ус тройства, вход признака записи блока ана-,лиза - к входу признака записи блока регистров, первый и второй информационные выходи блока анализа - вторым и третьим информационными выходами уст ройства соответственно. сети, сигнал с выхода соответствующего 5 элемента ИЛИ 24 поступает на первыйвход соответствующего элемента И 25.Далее работа элементов И 251-25 и Т- триггеров 261-26 происходит аналогично работе элементов И 201-20 С и Т-триггеров .10 211-21 в схеме анализа живости сети. Вслучае нарушения требования (3) хотя бы на одном из прямых выходов триггеров 261-26 появляется сигнал "1", который . через элемент ИЛИ 27 поступает на второй 15 информационный выход 19 блока анализа15, что свидетельствует о том, что исследуемая сеть Петри не является безопасной.Таким образом, предлагаемое устройство для исследования сетей Петри позволя,ет исследовать матричное представлениесетей, может быть использовано для решений линейных матричных уравнений и позволяет существенно расширить класс .решаемых задач за счет осуществления ана лиза сетей Петри на безопасность, живостьи достижимость задаваемых произвольныхмаркировок.1709350Б;.ок анализаСоставитель М. Поповдактор Л. Пчолинская Техред М.Моргентал Корректор М. Кучерявая Заказ 428 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР113035, Москва, Ж, Раушская наб., 4/5одственно-издательский комбинат "Патент", г, Ужгород, ул. Гагарин