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

(19 4 С 06 Р 15/2 АНИЕ ИЗОБРЕТЕНИ ство СССР15/20, 1983.ДЕЛИРОВАНИЯ(54) УСТРОЙСТВОГРАФОВ ПЕТРИ области ожет быть нременных систем, тся и иучени ания етри явля одел искл ении тся повы"рованияченияпереходов енанабот нкциональиг. 2- блока синимер модедиаграмма рна фиг,ГОСУДАРСТВЕННЫЙ КОМИТЕТПЬ ИЗОБРЕТЕНИЯМ И ОЧНРЫТИЯМПРИ ГКНТ СССР(71) Институт проблем моделирования в энергетике АН УССР и Специальное конструкторско-технологическое бюро средств моделирования с опытным производством Института проблем моделирования в энергетике АН УССР (72) В.В. Васильев, В.В. Кузьмук, Г.Г. Купченко, Е.Б. Лисицин и В.А. Бумов(56) Питерсон Дж. Теория сетей Петри и 1 оделирование систем. М.: Мир, 1984 с. 246.Авторское свидетельУ 1171803, кл, С 06 Р Изобретение откосвычислительной технииспользовано для полдиаграмм функционироописываемых графами ПЦелью изобретенияшение достоверности мграфов Петри за счетконфликтов при выполв графе.На фиг. 1 представная схема устройствавременнаяхронизации 7) Изобретение относится к вычи ительной технике и может быть иользовано для получения временных диаграмм Функционирования систем, описываемых графами Петри. Целью изобретения являеТся повышение достоверности модепирования графов Петри за счет исключения конфликтов при выполнении переходов в графе. Введение приоритетов позволяет значительно повысить описательскую мощность и мощность моделирования сетей Петри, разрешить ряд возникающих при моделировании реальных объектов конфликтных ситуаций, В указанном обобщении сетей Петри каждой вершине перехода д ставится в соответствие некоторый уровень перехода. Переход с более высоким приоритетом обладает преимущественным правом запуска в случае С возникновения конфликтных ситуаций. 3 ил,лируемого графа Петри и таблица исходных данных для его моделиронания.Устройство содержит первую-третью группы из регистров 1-3 соответствен 1 но, где М - количество вершин переходов в графе Петри, группу из М счетчиков 4, первую и вторую группы из М блоков 5 и 6 соответственно элементов И, группу из М элементов И 7, группу из М элементов ИЛИ 8, группу из М элементов 9 задержки, группу из М блоков 10 поразрядного сравнения, первый-третий блоки 11-13 соответственно элементов ИЛИ, блок 14элементов ИСКЛЮЧАКЩЕЕ ИЛИ, блок 15 логического сложенная, коммутатор 16,регистр 17, с первого по пятый элементы 18 22 соответственно ИЛИ, первый и второй элементы 23 и 24 соответственно, блок 25 синхронизации, счетчик 26 и блок 27 памяти.Кроме того, на фиг. 1 обозначены входы 28 задания входного вектора К-й вершины перехода устройства, входы 29, входы 30 задания времени исполнения К-й вершины перехода устройства,.вход 31 начальной установки устройства, вход 32 пуска устрой ства, вход 33 задания начальной разметки устройства, первый-третий выходы 34-36 соответственно блока 25 синхронизации, вход 37 задания приоритетов переходов. 20Устройство работает следующим образом.Пусть требуется смоделировать систему, описанную графом Петри, представленным на фиг, 3. Особенностью графов Петри является наличие двух типов вершин: переходов 1 и мест Р, а также наличие меток, которые, показывают, какие вершины при обходе графа устройство моделирует в данный момент. Метки располагаются в вершинах мест РЕ и моделируют в динамике окончание реальных действий, местонахождение меток отображается вектором разметки ш"= (0,0,1,1,1,0, 0,0,1), Цифра "0" на первом месте обозначает, что место Р не содержит метку, а ",1" на третьем месте обозначает, что Р содержит метку. При составлении графа Петри устанавливается его топология и начальная разметка ш . Каждая вершина перехода к моделирует время выполнения какого-то действия в процессе. Переходсра-. батывает, если во всех местах Р дуги от которых направлены к Р находятся метки. Так, например, переход С может сработать,В,момент начала выполнения действия а, (переход й) метки из всех входных мест перехода й удаляются и после окон чания моделирования действия а(через время М) во все выходные места перехода(к которым от Р направлены дуги) записываются. Кажцый пе,реход .С характеризуется входным раз" 55екметочным вектором р и выходным раэ1меточным вектором " , которые отражают связи перехода с его входными и выходными местами (см. табл. фиг.3). Одним из наиболее известных и часто применяемых обобщений сетей Петри являются сети Петри с приоритетом. Введение приоритетов позволяет значительно повысить описательную мощность и мощность моделирования сетей Петри, разрешить ряд возникающих при моделировании реальных объектов конфликтных ситуаций, В названном обобщении сетей Петри каждой вершине перехода ставится в соответствие некоторый уровень приоритета, причем наибольшим приоритетом обладает переход для которого Р = 1, уровень Р = = 2, отражает более низкий приоритет и т.д. Переход с более высоким приоритетом обладает преимущественным правом запуска в случае возникновения конфликтных ситуаций. Так, например, на фиг. 3 при установившейся разметке возник конфликт в месте Рз переходы С и С претендует на одновременное использование метки из этого места, Введение уровней приоритета Р = 1, Рь = 2, определяет, что вначале будет запущен перехода переходможет быть запущен только по окончании срабатыванияНа фиг. 3 представлен пример моделируемого графа Петри при моделировании управления движением транспортеров в некоторой транспортной сети. Лва транспортера непрерывно движутся в этой сети, каждый по своему маршруту и транспортируют детали от общего места загрузки, моделируемого переходом 7, к местам разгрузки. Процессы разгрузки моделируются переходами э и . Переходы С(у Еу Е 59 Сб моделируют движение соответствующих транспортеров от места загрузки к местам выгрузки и наоборот. Места Р и Р обеспечивают поочередное направление транспортеров к разным местам выгрузки. Система управления должна обеспечить нали-, чие только одного транспортера в месте загрузки. Для этого в модель введено место Р , разрешающее срабатывание только одного из переходови 6 и только в случае незанятости места загрузки,что обеспечивается определением Р как выходного места для Р. Однако в алгорйтме управления возможно возникновение конфликтных ситуаций при одновременном подходе транспортеров к месту разгрузки, че 1483460 650е55 001 000001и заносится в регистр 17. му соответствует разметка графа Петри,приведенная на фиг. 3, В сетях Петритрадиционного определения нет средствдля разрешения подобных конфликтов..5Введение уровней приоритетов переходов позволяет решить эту проблему.При Р = 1 и Р = 2 определяетсяпреимущественное право проезда транспорта, циркулирующего по маршруту 10есМоделирование построенного графаПетри позволяет определить пропускную способность транспортной сети,частоту возникновения конфликтов,длительности простоя и т.д,Для загрузки графа Петри в устройствоесоставляется таблица топологии графа Петри (см. фиг, 3), позволяющая отразить входные ь и выходок -ь20ные р разметочные вектора переходовприоритеты переходов Р, началькную разметку и длительности срабатывания переходовВ процессе загрузки:,исходных данных в устройстве значения" р заносятся в К-е регистры 1 первой группызначения" р в К-е регистры 2 второйгруппы, Значения 6 й к заносятся вК-е регистры 3 третьей группы, значе- ЗОние шр заносится в регистр 17.Режим моделирования графа Петриначинается по заднему фронту импульса на входе 32 пуска устройства.Разрешение на запуск К-го переходапоступит при выполнении условиярк-ф феш, и при соответствии приоритетаК-го перехода текущему приоритету.По спаду импульса с выхода 35 блока25 синхронизации счетчик 26 обнуля 40ется и начинает пересчитывать значения приоритетов переходов начинаяс Р = 1,При изменении кода на адресномвходе блока 27 памяти па информационных выходах, соответствующих перехо 45дам, появляются разрешающие (при выек -еполнении р е ш,) или запрещающиезапуск перехода сигналы. При выполнении указанных условий первым запустится переход (см. фиг. 3), приэтом в состояние "Счет" переходитсчетчик 4, вычисляется новое значние вектора текущей разметки:ш О О 1 1 1 О О О 10 О 0 После перевода счетчика 4 в режим "Счет" он начинает работать в режиме вычитания, причем счетными для него являются импульсы, поступающие с выхода 35 блока 25 синхронизации, После обнуления пятого счетчика 4 на его выходе появитс сигнал признака окончания имитации 5, определяющий перезапись из пятого регистра 3 времени исполнения 5-й вершины перехода устройства в пятый счетчик 4, а также разрешающий подачу иэ второго регистра 2 значения выходного вектора на вход блока 15 логического сложения для сложения со значением вектора текущей разметки. Одновременно сигнал признака окончания моделирования разрешает запись нового значения вектора текущей разметки в регистр 17. Таким образом, моделирование переходабудет окончено по приходу восьмого импульса с выхода 35 блока 25 синхронизации (восьмой момент модельного времени). В девятый момент модельног.- времени в течение Тз (см. фиг. 2) будет запущен й, после окончания моделирования которого в 14-й момент модельного времени будут запущеныи т.д.После окончания моделирования в восьмой момент модельного времени значение ш будет следующим:па 00100001ОООО 1 ОООшЮ 1001 О 1 ООО 1Дапее устройство продолжает работать по описанному алгоритму.Таким образом, предлагаемое устройство позволяет моделировать графы Петри с приоритетом, описывающие параллельные процессы,Формула иэ обретенияУстройство для моделирования графов Петри, содержащее три группы из М регистров, где М - количество вершин переходов в графе Петри, группу из М элементов ИЛИ, группу из М блоков поразрядного сравнения, две группы иэ М блоков элементов И, группу из М счетчиков, группу из М элементов задержки, три блока элементов ИЛИ, четыре элемента ИЛИ, два элемента И, блок логического сложения, блок эле,ментов ИСКЛЮЧАЮЩЕЕ ИЛИ, коммутатор, регистр и блок синхронизации, входпуска которого является входом пуска устройства, причем вход задания входного вектора К-й вершины перехода устройства подключен к информационно 5 му входу К-го регистра первой группы (К=1 М), выход которого подключен к первому информационному входу К-го блока поразрядного сравнения и к информационному входу К-го бло О ка элементов И первой группы, выход которого подключен к К-му входу первого блока элементов ИЛИ, выход которого подключен к первому информационному входу блока элементов ИСКЛЮ ЧАЮЩЕЕ ИЛИ, выход которого подключен к первому информационному входу коммутатора, вход задания выходного вектора К-й вершины перехода устройства подключен к информационному входу К-го регистра второй группы, выход которого подключен к информациочному входу К-го блока элементов И второй группы, выход которого подключен к К-му входу второго блока 25 элементов ИЛИ, выход которого подключен к первому информационному входу блока логического сложения, выход которогб подключен к второму информационному входу коммутатора, вход задания времени исполнения К-й вершины перехода устройства подключен к информационному входу К-го регистра третьей группы, выход которого подключен кинформационному входу К-го счетчика группы, выход признака пере 35 хода через ноль которого подключен ,к входу К-го элемента задержки группы,:к управляющему входу К-го блока элементов И второй группы и к К-му входу первого элемента ИЛИ, выход которого подключен к первому входу первого элемента И, управляющий входК-го блока элементов И первой группы соединены с входом разрешения счета К-го счетчика группы и с К-м входом второго элемента ИЛИ, выход которого подключен к первому входу второго элемента И, выход первого элемента И подключен к первому управляющему входу коммутатора и к первому 50 входу третьего элемента ИЛИ, выход которого подключен к входу признака записи регистра, выход второго элемента И подключен к второму входу третьего элемента ИЛИ квторому управ 55 ,ляющему входу коммутатора, выход которого подключен к первому входу третьего блока элементов ИЛИ, выходкоторого подключен к информационномувходу регистра, выход которого подключен к второму информационному входу блока логического сложения, к второму информационному входу блока элементов ИСКЛЮЧАЮЩЕЕ ИЛИ и к вторыминформационным входам всех блоковпоразрядного сравнения группы, выход К-го элемента задержки группыподключен к первому входу К-го элемента ИЛИ группы, выход которогоподключен к входу признака записиК-го счетчика группы, вход заданияначальной разметки устройства подключен к второму входу третьего блокаэлементов ИЛИ, вход начальной устанонки устройства подключен к входампризнаков записи всех регистров всехгрупп, к вторым входам всех элементовИЛИ группы и к второму входу четвертого элемента ИЛИ, первый выход блокасинхронизации подключен к второмувходу второго элемента И, второй выход блока синхронизации подключен квторому входу первого элемента И ик вычитающнм входам всех счетчиковгруппы, о т л и ч а ю щ е е с ятем, что, с целью повышения достоверности моделирования графов Петри, засчет исключения конфликтов при выполнении переходов в графе, в него введены группа из К элементов И, счетчик,блок памяти, пятый элемент ИЛИ, кпервому входу которого подключен входначальной установки устройства, квторому входу пятого элемента ИЛИподключен второй выход блока синхронизации, выход пятого элемента ИЛИподключен к входу установки в "0"счетчика, третий выход. блока синхронизации подключен к суммирующему входу счетчика, выход которого подключен к адресному входу блока памяти,К-й разряд информационного выхода которого подключен к первому входу К-гоэлемента И группы, к второму входукоторого подключен выход признаканеравенства нулю результата сравнения К-го блока поразрядного сравнения группы выход К-го элемента Игруппы подключен к управляющему входу К-го блока элементов И первойгруппы, установочный вход блока памяти соединен с входом заданияпараметров переходов устройст -ва, 14834 бО1483460 о И тор О. Спесив ректор М. Пожо Тираж 668митета по изобретениям ва, Я, Раушская на Производственно-издательский комбинат "Патент" Ужго Гагарина, 10 Заказ 2834/ ВНИИПИ Госу Вко ф