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

.801735869 А 2 Щ 5 г 06 Р 15/347 15/419 ЫЙ НОМИТЕТ ИЯМ И ОТКРЫТИЯМГОСУДАРСТВЕНГЮ ИЗОБРЕТЕНПРИ ГННТ ОС ИЗОБРЕТЕНИ ОП ЬСТВ ДЕ АВТОРСИО 2 (57), Изобретение относит лительной технике и може пользовано для исследова Петри. Цель изобретения ние области применения. тения достигается за сче ного введения в состав у четвертого блока памяти группы блоков схем сравн ,16-1 с и группы элемен ;17"1 с. 2 ил. адерино СССР7, 198ВАНИЯ 1(54) УСТРОЙСТВО ЛЛЯ ИССЛЕДСЕТЕЙ ПЕТРИ ся к вцчист быть исния сетей1 Изобретение относится к вычислительной технике, мажет быть исполь зовано для исследования сетей Петри) представленных матричным способом, и является усовершенствованием устройства по авт,св. 1 Г 1322312. Известно устройство для исследования сетей Петри, содержащее три блока памяти, блок регистров, группу блоков схем сравнения, регистр результатов сравнения, блок выцитания матриц, блок умножения матриц, блок сумматоров, блок сравнения с нулем и блок синхронизации, Это устройство позволяет исследовать на достижимость обычные (простые) сети Петри (СП), Ограниченность для моделирования обычных СП состоит в неспособности к проверке на нуль некоторой позиции, что часто является необходимым при моделировании реальных систем и процессов. Самым простым расшиоением СП, которое допускает проверку на нуль, являются сдерживающие дуги. Сдерживающая дуга на позиции Р; в переходе С имеет маленький кружок, а не стрелку у конца дуги, присоединенного к переходу.Правило запуска переходов по сравнению с обычными СП изменяется следующим образом.Переход является разрешенным,когда Фишки присутствуют во всех его (обычных) входах и отсутствуют в сдерживающих входах. Переход запус" кается удалением Фишек из всех его (обычных) входов.Под СП понимают двудольный граФ,характеризуемый четверкойС=СР, Т, 0,0 )где Р - Р Рр- конечноенепустоемножествопОзициЙ)ш,тО )Т = СС,:,), - конечноенепутоемножествопереходов,1 с) О;РПТЛ и 1) - матрицы, представляющие собой входную и выходную Функции,358694Каждая матрица имеет Е строк (поодной на. переход) и и) столбцов (поодному на позицию). где П - определяет входы в переход+Ф10 Б - определяет выходы из переходов,Ч матричном описании СП со сдерживающими дугами добавляется матрица сдерживаюц)их (ингибиторных) дуг15 В , содержащая также Е строк и щстолбцов. Элемент матрицы П1,Я == 1 тогда и только тогда, когда изпозиции Р), в переход 1 ведет сдерживающая дуга. Правила запуска пере 2 О ходов для СП со сдерживающими дуга"ми определены выше,Недостатком устройства являетсяневозможность исследования описанного расширения обычных СП, а имен 25 но СП со сдерживающими дугами,1 елью изобретения является расширение класса решаемых с помощью него задач за счет возможности иссле"дования помимо обычных расширенных30 СП (СП со сдерживающими дугами).Поставленная цель достигаетсятем, что устройство, содержащеетри блока памяти, блок регистров,группу блоков схем сравнения, ре-.гистр результатов сравнения, блоквычитания матриц, блок умноженияматриц, блок сумматоров, блок сравне"ния с нулем и блок синхронизации,введены цетвертый блок памяти, вто 4 О рая группа блоков схем сравнения,группа элементов И, причем выходблока регистров подключен к первыминФормационным входам блоков схемсравнения второй группы, с первого5 по 1-й выходы четвертого блока памяти, где.Е - количество строк висходных матрицах, подключены квторым инФормационным входам блоковсхем сравнения второй группы, выходы5 О признаков неотрицательного результата которых подключены к первым входам соответствующих элементов И группы, вторые входы которых соединеныс выходами признаков неотрицательно- .го сравнения первой группы, выходыэлементов И группы подключены к инФормационному входу регистра результатов сравнения, вход признака чтения четвертого блока памяти, вход ,50 и блока 7 вычитания матриц, к входупризнака записи регистра 6 результатов сравнения, к входу опросаблока8 умножения матриц и к входу признака чтения третьего блока 3 памяти 5 соответственно.Схемы введенных четвертого блока15 памяти и блоков 16-1 16-1 с схемсравнения второй группы являютсяизвестными и могут быть выполнены 5 173опроса блоков схем сравнения второйгруппы подключены к входам опросаблоков схем сравнения первой группь 1Благодаря четвертому блоку памяти появляется возможность дополнительно по сравнению с прототипомвводить для исследования СП сосдерживающими дугами, т,е, хранитьинформацию об ингибиторных связях.в ГП; введение второй группы блоковсхем сравнения и группы элементов Ипозволяет расширить логику проверкина активность и срабатывания переходов СП. В реальных условиях этоозначает возможность проверки на нулевую маркировку любой позиции СП,Известное устройство не обладает свойством проверки на нуль любой позицииСП, что соответственно не позволяетиспользовать его при исследовании широкого класса задач, требующих длясвоего решения возможности моделирования ситуации различных приоритетов, арбитров, прерыванийи т,д.СП со сдерживающими дугами позволяютизбежать таких трудностей, представляя возможность моделирования вышеперечисленных ситуаций.На Фиг.1 представлена Функциональная схема устройства; на Фиг.2 рассматриваемая СП,Устройство содержит четыре блока1-3, 15 памяти, блок 4 регистров дляхранения начальной маркировки первуюгруппу 5 блоков 5-15-1 с схем срав"нения, где 1 с - количество строк висходных матрицах, регистр 6 результатов сравнения, блок 7 вычитанияматриц, блок 8 умножения матриц,блок 9 сумматоров, блок 10 сравненияс нулем, блок 11 синхронизации,информационный выход 12 устройства,вход 12,начальной установки, вход14 пуска устройства, вторую группу15 блоков 16-1, 16-1 с, схем сравнения,группу 17 элементов И 17-1, 17"2,17-К, причем выход блока 4 регистровподключен к входу первого слагаемогоблока 9 сумматоров и к первым информационным входам блоков 5-1,5"Е,16-116-1 с схем сравнения первой.ивторой группы, с первого по К-йвыходы первого блока 1 памяти подключены к входу вычитаемого блока. 7 вычитания матриц и вторым информационным входом с первого по М-йблок 5-15-1 с схем сравнения пер"вой группы 5, выходы признаков не"отрицательного результата которых 58696 под ключ ены к п ер вым входам соот ве т с твующих элементов И группы, вторыевходы которых подключены к выходам, 5признаков неотрицательного результата сравнения соответствующих блоков16-1, ,16-1 с схем сравнения группы16, вторые входы которых соединены. с первым по 1 с-й соответствующими выходами четвертого блока 15 памяти,Соответствующие выходы элементов Игруппы 17 подключены к информационному входу регистра 6 результатовсравнения, выход которого подключенк входу первого сомножителя блока 8умножения матриц к информационномувходу блока 1 О сравнения с нулем,выход признака равенства нулю которого подключен к входу останкова блока 2 О 11 синхронизации и является информационнь.м выходом 12 устройства, Выход,второго блока 2 памяти подключен квходу уменьшаемого блока 7 вычитанияматриц, выход которого подключен к 25 информационному входу третьего блока 3 памяти. Выход блока 3 памятиподключен к входу второго сомножите"ля блока 8 умножения матриц, выходкоторого подключен к входу второго 30слагаемого блока 9 сумматоров. Выход блока 9 подключен к информационному входу блока 4 регистров. Входначальной установки блока 11 синхронизации подключен к входам начальной установки регистра 6 результатов 35 сравнения и третьего блока 3 памятии являются входом 13 начальной уста"новки устройства. Вход пуска блокасинхронизации является входом 14пуска устройства. С первого по седь мой выходы блока 11 синхронизацииподключены к входам признака чтенияпервого 1, второго 2 и четвертого15 блоков памяти и входу признаказаписи третьего блока 3 памяти, к 45 входу опроса блока 9 сумматоров,к входу признака записи блока 4 регистров, к входам опроса каждогоблока 5-15-1 с, 16-1 16-1 ссхем сравнения первой и второй групп(ц= (11 +хП,аналогично описанным в прототипе,.Элементы 7-1. 7-с И группы 17являются известными,Устройство работает следующимобразом (Фиг.2),В исходном состоянии схемы в блоке 1 находится матрица входов Лнапример в блоке 15 - матрица входов длясдерживающих дуг:+а в блоке 2 - матрица выходов Р, нап"ример т.е. данная СП имеет четыре позиции, три перехода. Сдерживающая дуга соединяет р( и й( . Первоначальная мар" кировка находится в блоке 4 и имеет вид 1 ц = (1,0,1,0) . Требуется определить, достижима ли маркировка р из маркировки М. Предполагаем, что маркировка М достижима из маркировки М . Тогда существуеу последовательность (возможно пустая) запусков переходов 6 ,(которая приводит изо к ю . Это оз" начает, что Г ) является неотрицательным целым решением следующего матричного уравнения для х:(Бсли 1 достижима из (1,(, уравнение (1) имеет решение в неотрицательных целых, если уравнение (1) не имеет реаения, Ч не достижима из М,Под дейстьием синхросигналов с блока .11 информация с выхода блока 1 поступает на вторые входы блоков 5 т 15-1 схем сравнения группы, где происходит ее сравнение со значе". нием начальной маркировки, поступающей на первые входы всех типов 5-1, 5-1 с. Гсли результат сравнения больше или равен нулю по всем срав 98ниааемым элементам (.-й строки матри"цы Л , (что соответствует тому, чтодля перехода 1; во всех его входныхпозициях, соединенных с ним обычнымидугами, число Фишек не меньше, чемкратность соединяющих дуг, т.е. выполняется правило запуска по обычнымвходам,на вторые входы соответствующих элементов И 17-117-1 группы поступает единица, иначе нуль.Одновременно с этим, под действиемсинхросигналов с блока 11 информацияс выхода блока 15 поступает на вторые входы блоков 16-116-1 схемсравнения группы, где происходит еесравнение со значениями начальноймаркировки, поступающей на первыевходы всех блоков 16-116-(с( Бс 20 ли результат сравнения меньше нуляпо всем сравниваемым элементам д-й. строки матрицы Р", на первые входысоответствующих элементов И 17-117-к поступает единица (т.е. для перехода й; в его сдерживающих входныхпозициях отсутствуют фишки, сталобыть, выполняется правило запуска поего сдерживающим (ингибиторным) входам,В случае отрицательного сравненияЗ 0 записывается нуль.Таким образом, при сравнении первоначальной маркировки (1, О, 1, О)со строками матрицы 0 , только третьястрока удовлетворяет правилу срав"5 нения. Это означает, что потенциально разрешено срабатывание по обычнымвходам третьего перехода. На вторыевходы группы элементов И 17-117-Е поступают сигналы (0,0,1) соотО ветственно. Одновременно при сравнении первоначальной маркировки (1,0,1,0) со строками матрицы Р", удовлетворяют правилу сравнения вторая и третья строки. Это означает потенциально разрешение срабатывания по сдерживающим дугам для переходов второго и третьего, На первые входы групп элементов И соответственно поступают следующие значения (0,1,1), В результате с выходов групп элементов 17 И в регистре 6 запишется (0,0,1). Параллельно информация из блока 2 посту- пает на вход уменьшаемого блока 7, на вход вычитаемого которого поступает информация с блока 1, Блок 7 под действием управляющих сигналов с блока 11 реализует операцию вычитасо сдерживающими дугами. Это существенно (1,2,4) расширяет класс. решаемых задач и соответственно областьприменения данного устройства. 1-1 "1 00=0 2 1-1 0 1 "19 1735869 10 ния матриц по Формуле рониэации работает аналогично блоку синхронизации прототйпа и поэтомП = 1+ - , его работу не рассматривают,Таким образом, предлагаемое устЗначение .полученной составной мат- Ройство позволяет производить анарицы изменений П записывается в блок лиэ достижимости не только обычных 3. Она имеет вид СП, но и их мощного расширения - СПДальше работа схемы направлена на. реализацию Формулы (1). При подста" новке полученных значений она имеет вид: (О = (1,0,1,0) + (0,0,1) х1 -1 -1 0 ,)( 0 2"0 0-1 1Под действием управляющих сигналов с блока 11 инФормация иэ.блока ,3 поступает в блок 8, где происходит сложение результата произведения со ,значением маркировки, в результате получается новая маркировка СП (1,0; 0,1), которая заносится в блок 4. Процесс работы устройства повторяется.На каждом шаге работы устройства происХодит проверка кода, находящего" ся в блоке 4, т.е. последовательнос,ти выпуска переходов на нуль в бло" ке 10; Если инФормация больше нуля, процесс работы продолжается. Если последовательность запуска переходов равна нулю, блок О вырабатывает сигнал, свидетельствующий о том, что СП при данной начальной маркировке . достигла передела выполнимости, т,е. достигла такого состояния, когда все переходы запрещены. Блок 11 синхФормулаизобретения Устройство для исследования се"тей Петри по авт.св. 8 1322312,о т л и ч а ю щ е е с я тем, что,с целью расширения области примене" 2 О ния; дополнительно введены четвертыйблок памяти, вторая группа блоковсхем сравнения, группа элементов И,причем выход блока регистров подключен к первым инФормационным входамблоков схем сравнения второй группы,выходы четвертого блока памяти под"ключены к вторым инФормационным входаи блоков схем сравнения второй груп.пы, выходы признаков неотрицательного результата которых подключены к ЗО первым входам соответствующих элементов И группы, вторые входы кеторыхсоединены с выходами йриэнаков неотрицательного результата сравнения соответствующих блоков схем сравнения 35 первой группы, выходы элементов Игрупны подключены к инФормационномувходу. регистра результатов сравнения,вход признака чтения четвертого блока памяти подключен и входам -признака 40:чтения первого и второго блоков па"мяти, входы опроса блоков схем сравнения второй группы подключены к входам опроса блоков схем сравнения первой группы.а кторЕ 4 уньнВвав каз 1818 Тираж Подписное НВИПИ Государственного комитета ао кэобретенияк и открытням пр 113035, москва, 3-35, Рауаская наб д. 4/5 НТ СССР Производственно"нздателвскнй комбннат патент", г. Уаг Ул. Гаг Составител Техред м,м А, Янковскийгентал Корректор И. Самборская