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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКРЕСПУБЛИК 7424 6 Р 1 Яхф 1 ф 11Я ПИСА БРЕТЕ ДЕТЕЛЬСТВУ ВТОРСКОМ В 6С.Ю.ПерерньппеветельствР 15/20,ельствоГ 15/347 аров,СССР1983ССР1979.) .УСТРОЙСТВО ДЛЯЕЙ ПЕТРИ С СЛЕДОВАНИЯ ОСУДАРСТВЕННЫЙ КОМИТЕТ СССРО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИИ(57) Изобретение относится к вычислительной технике, может быть использовано для исследования сетей Петрии позволяет расположить разрешенныев сети переходы в порядке их срабатывания во времени, Так как сетиПетри обладают свойством параллелизма, возможно появление критических 13, БИЗЛИд : ( ситуаций, т.евозможности срабатывания перехода от двух маркированныхпозиций или двух разрешенных переходов от одной маркированной позиции,Если от двух или более маркированныхпозиций есть входные дуги в переход,то очередность срабатывания переходадолжна определяться каким-либо критерием. В данном устройстве в качестве критерия срабатывания переходавыбрано время срабатывания. С этойцелью в устройстве задаются матрицавходов сети Петри, матрица временсрабатывания переходов и значениеначальной маркировки. Путем сравнения начальной маркировки со строкамиматрицы входов отыскиваются разрешенные для срабатывания переходы.После этого указанные переходы упорядочиваются в соответствии с их временем срабатывания и записываютсяв один из блоков памяти, 2 ил.Изобретение относится к вычислительной технике и может быть использовано для исследований сетей Петри.Целью изобретения является расширение функциональных возможностей устройства за счет расположения разрешенных в сети переходов в порядке их срабатывания во времени.На фиг. 1 изображена структурная схема устройства для исследования сетей Петри; на фиг. 2 - функциональ. ная схема блока управления.Устройство содержит два регистра 1 и 2, блок 3 управления, первый блок 4 памяти, первую схему 5 сравнения, три дешифратора 6-8, второй блок 9 памяти, второй элемент 10 задержки, первый счетчик 11, второй элемент .ИЛИ 12, первый элемент ИЛИ 13, первый элемент 14 задержки, вторую схему 15 сравнения, третий блок 16 памяти, первый элемент И 17, элемент НЕ 18, второй элемент И 19, пятый элемент 20 задержки, третий элемент И 21, четвертый элемент 22 задержки, кольцевой регистр 23 сдвига, третийэлемент 24 задержки, четвертый блок 25 памяти, второй счетчик 26, шестой элемент 27 задержки, информационный вход 28, вход 29,пуска,Блок 3 управления содержит счетчик 30, схему 31 сравнения, триггер 32, элементы И 33-35, генератор 36 тактовых импульсов, регистр 37, элемент ИЛИ 38, триггер 39, элемент 40 задержки, элемент ИЛИ 41, элемент 42 ИЛИ, элемент 43 задержки, выход 44 номера перехода, первый 45, второй 46, третий 47 выходы синхронизации, вход 48 признака начала работы, тактовый.выход 49, вход 50 начальной установки, вход 51 управления режимом работы.Устройство работает следующим образом.Сеть Петри задается четверкой, С = Р, 1, Т, О, Р = Р , Р , Р- конечное множество позиций, и , О. Т = с с , с,3- конечное множество периодов, шО. Множество позиций и множество периодов не пересекаются, РПТ = Ф . 1 = Т Р является входной функцией - отображением их переходов в комплекты позиций. О = Т. Р ф - выходная фуйкция - отображение из переходов в комплекты позиций. Структура сети Петри представляет собой совокуп 5 10 15 20 25 30 35 40 45 50 55 ность позиций и переходов. Сеть Петри может быть представлена в видеграфа с двумя типами вершин - позиции и переходы. При описании сетьюПетри каких-либо процессов или системпозиций принимают знание состояния.или условие события. Для описаниядинамики вводится понятие маркировкир, т.е. присвоение фишек позициямсети Петри, которые используются дляопределения выполнения сети Петри.Маркированная сеть Петри М = С, рэто совокупность структуры сети Петри С = Р, 1, Т, 01 и маркировки иможет быть записана в виде М = Р,1, Т, О,р.Выполнением сети, Петри управляютколичество и распределение фишек всети. Фишки находятся в позициях иуправляют выполнением переходов сети.Сеть Петри выполняется посредствомзапусков переходов. Переход запускается управлением фишек изего входныхпозиций и образованием новых фишек,помещаемых в его выходные позиции.Переход может запускаться только втом случае, если он разрешен, т,е.каждая из его входных позиций имеетчисло фишек по крайней мере равноечислу дуг из позиций в переход.Один из переходов к анализу Петриоснован на матричном представлениисетей Петри, Альтернативным по отношению к анализу сети Петри в виде(Р, Т, 1, О) является определениедвух матриц 0 и Э, представляющихвходную и выходную функции. Каждаяматрица имеет ш строк, по одной напереход, и и столбцов, по одному напозицию.Определяем П Ц, = (Р;,1(с ,П+ ,Ц = (Р;,О(г. ,где Э - определяет входы в переходы,П определяет выходы ( = 1,ш, 1 - 1, , и),Сети Петри обладают свойствомпараллелизма, в связи с чем возможноявление так называемых критическихситуаций, т.е. воэможность срабаты-,вания перехода от двух маркированныхпозиций или двух разрешенных переходов от одной маркированной позиции.Если от двух или более позиций естьвходные дуги в переход и они маркированы, то очередность срабатыванияперехода должна определяться какимлибо критерием, значение которого3 1374назначено для каждой позиции. В предлагаемом устройстве, предназначенномдля разрешения критических ситуаций,в качестве критерия срабатывания перехода выбрано время,5В исходном состоянии схемы в блоке 4 памяти находится матрица входовР", в блоке 25 памяти находятся времена срабатывания переходов, имеющих-ося в. матрице 0 , в последовательностисрабатывания. На вход 50 блока 3 управления поступает сигнал установки,обнуляющий через элементы ИЛИ 12 н13 счетчики 11 и 26 соответственно.На вход 28 устройства поступает сигнал, записывающий в регистр 1 значение нормальной маркировки. Работаустройства протекает в два этапа: выбор разрешенных переходов и записьих в блок 9 памяти; расположение разрешаемых переходов в порядке срабатывания с учетом времени срабатыванияи их последовательная запись в блок16 памяти. 25Первый этап начинается с подачисигнала на вход 29 устройства. После,этого блок 3 управления начинает вы-.рабатывать управляющие сигналы, поддействием которых информация с блока 3 О4 памяти построчно поступает на первый вход схемы 5 сравнения, где происходит ее сравнение со значениемначальной маркировки, поступающейна второй вход схемы 5 сравнения с35регистра 1. Если в результате сравнения значение строки блока 4 памятии значение начальной маркировки совпадают по всем сравниваемым разрядам,вырабатывается управляющий сигнал,поступающий на суммирующий вход счетчика 11 и разрешающий запись в блок9 памяти информации выходов с выхода44 блока 3 управления, Содержимоесчетчика 11 на каждом такте записи 45номера очередного разрешенного перехода поступает через дешифратор 7,в позиционном коде на блок 9 памяти,указывая адрес записи. Первый этапработы устройства заканчивается послепросмотра всех строк блока 4 памятии перезаписи всех разрешенных переходов с блока 4 памяти в блок 9 памяти. По окончании первого этапа сигнал с выхода 47 блока 3 управленияустанавливает 0 через элемент ИЛИ115512 счетчик 11. При этом номер последней позиции блока 9 памяти, по адресу которой был записан последний раз 242 4решенный переход, остается записанным в регистре 2,Работа устройства на втором этапезаключается в следующем. С выходаблока 3 управления подаются тактовыеимпульсы через элемент 22 задержкина вход сдвига кольцевого регистра 23,который выбирает двоичные номера переходов в порядке их срабатывания изблока 25 памяти и подает их на схему15 сравнения. Одновременно из блока9 памяти на схему 15 сравнения подаются двоичные номера разрешенных переходов. Это осуществляется следующим образом. Тактовые импульсы с выхода 49 блока 3 управления поступаютчерез элемент 20 задержки и элементИ 17 на вычитающий вход счетчика 11,а на второй вход элемента И 17 подается высокий потенциал с выхода нулевого разряда дешифратора 7. Крометого, тактовые импульсы поступаютна первый вход элемента И 19, который закрывается на данном этапе, таккак на второй его вход через элементНЕ 18, подается высокий потенциал свыхода нулевого разряда дешифратора7. В каждом такте происходит перезапись двоичного номера перехода в схему 15 сравнения, где он сравниваетсяс двоичным кодом перехода, имеющимна данном этапе наименьшее время срабатывания.После того, как содержимое счетчика 11 станет равным нулю, с выхода нулевого разряда дешифратора 7низкий потенциал закроет элементИ 17 и через элемент 18 НЕ, откроетэлемент И 19. Тактовые импульсы начнут поступать на вход признака записи счетчика 11. При этом все разрешенные переходы выбраны и в блок9 памяти возможна запись новых разрешенных переходов при смене матрицыЭ . или при записи в регистр 1 новоймаркировки. Если в результатесравнения двоичные номера переходовсовпали, то схема 15 сравнения вырабатывает управляющий сигнал, поступающий через элемент 27 задержкина вход признака записи блока 16 памяти и на суммирующий вход счетчика26, который формирует адрес записиразрешенного переход из блока 9 памяти. После сравнения всех двоичныхномеров разрешенных переходов из блока 9 памяти с двоичными номерами переходов из блока 25 памяти в блокерешенные переходы в порядке ихсрабатывания,Появление в старшем разряде коль 5цевого регистра 23 сдвига единицы,поступающей на первый вход элементаИ 21, означает, что просмотрены всеномера переходов, расположенные впорядке срабатывания в блоке 25 памяти, При этом открывается элементИ 21, на второй вход которого через 15 20 45 второго блока памяти и входу первого дешифратора, выходы которого под 50 ключены к адресным входам первого блока памяти, выход которого подключен к второму информационному входу первой схемы. сравнения, выход признака равенства которой подключен к входу первого элемента задержки, суммирующему входу первого счетчика и входу управления режимом блока управле 16 памяти остаются записанными разэлемент 24 задержки поступает сигнал с выхода, 49 блока 3 управления и с выхода которого импульс через элементы ИЛИ 12 и 13 поступает на вход установки в "О" счетчиков 1.1 и 26 соответственно. Кроме того, импульс поступает на второй вход блока 3 управления,Таким образом, предлагаемое устройство позволяет производить анализ сетей Петри на последовательность срабатывания разрешенных переходов в критических ситуациях. формула изобретения Устройство для исследования сетей Петри, содержащее два регистра, блок управления, блок памяти, первую схе:му сравнения и три дешифратора, причем выход первого регистра подключен к первому информационному входу первой схемы сравнения, о т л и ч а ющ е е с я тем, что, с целью расширения класса решаемых задач за счет расположения разрешенных в сети переходов в порядке их срабатывания во времени, в него введены второй,третий и четвертый блоки памяти, шесть элементов задержки, три элемента И,два элемента ИЛИ, два счетчика, кольцевой регистр сдвига, вторая схемасравнения и элемент НЕ, причем входпуска устройства подключен к входупризнака начала работы блока управления, выход номера перехода которого подключен к информационному входу 30 35 40 ния, первый выход синхронизации 1:торого подключен к входу второго элемента задержки, выход которого подключен к входу опроса первой схемы сравнения, информационный вход устройства подключен к информационному входу первого регистра, вход признака записи которого подключен к второму выходу синхронизации блока управления, третий выход синхронизации которого подключен к первому входупервого элемента ИЛИ и первому входувторого элемента ИЛИ, выход которогоподключен к входу установки в "О"первого счетчика, выход которого подключен к входу второго дешифратора и информационному входу второго регистра, выход которого подключен кинформационному входу первого счетчика, выходы второго дешифратора, исключая выход нулевого разряда, подключены к адресным входам второго блока памяти, выход нулевого разряда второго дешифратора подключен к первому входу первого элемента И и входу элемента НЕ,выход которого подключен к первому входу второго элемента И, выход которого подключен к входу признака записи первого счетчика, выход первого элемента задержки подключен к входу признака записи первого блока регистров, выход которого подключен к первому информационному входу второй схемы сравнения и к информационному входу третьего блокапамяти, тактовый выход блока управления подключен к входу третьего элемента задержки, выход которого подключен к входу опроса второй схемы сравнения, входу четвертого элемента задержки, первому входу третьего эле. мента И и входу пятого элемента задержки, выход которого подключен к второму входу второго элемента И и второму входу первого элемента И, вы ход которого подключен к вычитающему входу первого счетчика,выходчетвертого элемента задержки,подключен к входу признака сдвига кольцевого регистра сдвига, выходы разрядовкоторого подключены к адресным входам четвертого блока памяти, выходстаршего разряда кольцевого регистрасдвига подключен к второму входу третьего элемента И, выход которого под-.ключен к входу признака записи второго регистра, второму входу второгоэлемента ИЛИ, входу начальной установки блока управления и второму входу первого элемента ИЛИ, выход которого подключен к входу установки в"0" второго счетчика, выход которого подключен к входу дешифратора, выходы которого подключены к адреснымвходам третьего блока памяти, выход четвертого блока памяти подключен квторому информационному входу второйсхемы сравнения, выход которой подключен к суммирующему входу второгосчетчика и входу шестого элементазадержки, выход которого подключенк входу признака записи третьего блока памяти.1374242 Составитель А.МишинТехред Л.Сердюкова Корректор, М,Шароши Редактор Е.Копча Тираж 704 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035 Москва, Ж, Раушская наб., д. 4/5